华东师范大学学报(自然科学版)

• 计算机科学 • 上一篇    下一篇

分布式可扩展数据流连接算法

王晓桐, 房俊华, 张 蓉   

  1. 华东师范大学 数据科学与工程研究院 上海高可信计算重点实验室, 上海 200062
  • 收稿日期:2016-06-24 出版日期:2016-09-25 发布日期:2016-11-29
  • 通讯作者: 张蓉, 女, 博士, 副教授, 研究方向为分布式数据管理. E-mail: rzhang@sei.ecnu.edu.cn.
  • 基金资助:

    国家 863 计划项目(2015AA015307)；国家自然科学基金重点项目(61232002, 61332006);  国家自然科学基金(61432006)

Distributed and scalable stream join algorithm

WANG Xiao-tong, FANG Jun-hua, ZHANG Rong   

  1. Institute for Data Science and Engineering, Shanghai Key Laboratory of Trustworthy Computing, East China Normal University, Shanghai 200062, China
  • Received:2016-06-24 Online:2016-09-25 Published:2016-11-29

RichHTML

12

PDF

755

摘要：

Join-Matrix 是一种高性能的连接矩阵模型, 方便部署于分布式环境下, 支持任意连接谓词的数据流连接操作. 由于采取随机分发元组作为路由策略, Join-Matrix 可利用对元组内容的不敏感性来有效抵御数据倾斜. 为了实现工作节点的负载均衡以及网络传输代价的最小化, 基于连接矩阵模型设计一种高效的数据划分方案尤为重要. 针对数据流连接处理, 本文设计并实现了一种新颖的连接算子, 可灵活地进行划分方案的自适应调整, 以应对实时动态变化的数据分布. 具体来说, 我们根据数据流流量的采样信息和系统额定负载, 通过一个轻量级的决策器制定出一个数据划分方案和相应的数据迁移计划, 在保证输出结果完整性与正确性的情况下, 实现迁移代价的最小化. 本文在多种不同的数据集上进行了大量对比实验, 结果证明, 在资源利用率、系统吞吐率与时间延迟等方面, 该连接算子较对比系统具有更高的性能体现.

关键词: 数据流连接, Join-Matrix, 数据划分, 分布式计算

Abstract:

Join-Matrix is a high-performance model for stream join processing in a parallel shared-nothing environment, which supports arbitrary join operations and is
resilient to data skew for taking random tuple distribution as its routing policy. To evenly distribute workload and minimize network communication cost, designing an efficient partitioning policy on the matrix is particularly essential. In this paper, we propose a novel stream join operator that continuously adjust its partitioning scheme to real-time data dynamics. Specifically, based on the sample statistics of streams and rated load of each physical machine, a lightweight scheme generator produces a partitioning scheme; then the corresponding solutions for state relocation are generated by a migration plan generator to minimize migration cost while ensuring result correctness.Our experiments on different kinds of data sets demonstrate that our operator outperforms the static-of-the-art strategies in resource utilization, throughput and system latency.

Key words: stream join processing, Join-Matrix, partitioning scheme, distributed computing