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

王晓桐; 房俊华; 张蓉

doi:10.3969/j.issn.1000-5641.2016.05.010

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

doi: 10.3969/j.issn.1000-5641.2016.05.010

1.
华东师范大学数据科学与工程研究院上海高可信计算重点实验室, 上海 200062

基金项目:

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

详细信息

通讯作者:
张蓉, 女, 博士, 副教授, 研究方向为分布式数据管理. E-mail: rzhang@sei.ecnu.edu.cn.

计量
- 文章访问数: 262
- HTML全文浏览量: 9
- PDF下载量: 538
- 被引次数: 0
出版历程
- 收稿日期: 2016-06-24
- 刊出日期: 2016-09-25

Distributed and scalable stream join algorithm

1.
Institute for Data Science and Engineering, Shanghai Key Laboratory of Trustworthy Computing, East China Normal University, Shanghai 200062, China

摘要

摘要: 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-artstrategies in resource utilization, throughput and system latency.
- stream join processing Join-Matrix partitioning scheme distributed computing /

HTML全文

参考文献(1)

[1]

[ 1 ] DITTRICH J-P, SEEGER B, TAYLOR D S, et al. Progressive merge join: A generic and non-blocking sort-based join algorithm [C]//Proceedings of the 28th VLDB Conference. 2002: 299-310.
[ 2 ] URHAN T, FRANKLIN M J. XJoin: A reactively-scheduled pipelined join operator [J]. IEEE Data Eng Bull, 2000, 23(2): 27-33.
[ 3 ] WANG S, RUNDENSTEINER E. Scalable stream join processing with expensive predicates: Workload distribution and adaptation by time-slicing [C]//Proceedings of the 12th Conference on EDBT. 2009: 299-310.
[ 4 ] GOUNARIS A, TSAMOURA E, MANOLOPOULOS Y. Adaptive query processing in distributed settings [J]. Intelligent Systems Reference Library, 2013, 36: 211-236.
[ 5 ] LIU B, JBANTOVA M, RUNDENSTEINER E A. Optimizing state-intensive non-blocking queries using run-time adaptation [C]//Proceedings of the 2007 IEEE 23rd ICDEW. IEEE, 2007: 614-623.
[ 6 ] PATON N W, BUENABAD-CHAVEZ J, CHEN M, et al. Autonomic query parallelization using non-dedicated computers: An evaluation of adaptivity options [J]. The VLDB Journal, 2009, 18(1): 119-140.
[ 7 ] STAMOS J W, YOUNG H C. A symmetric fragment and replicate algorithm for distributed joins [J]. IEEE Transactions on Parallel & Distributed Systems, 1993, 4(12): 1345-1354.
[ 8 ] EPSTEIN R, STONEBRAKER M, WONG E. Distributed query processing in a relational data base system [C]//Proceedings of ACM SIGMOD Conference on Management of Data. 1978: 169-180.
[ 9 ] OKCAN A, RIEDEWALD M. Processing theta-joins using MapReduce [C]//Proceedings of ACM SIGMOD Conference on Management of Data. 2011: 949-960.
[10] ELSEIDY M, ELGUINDY A. Scalable and adaptive online joins [J]. The VLDB Endowment, 2014, 7(6): 441-452.
[11] GEDIK B. Partitioning functions for stateful data parallelism in stream processing [J]. The VLDB Journal, 2013, 23(4): 517-539.
[12] Apache storm[EB/OL]. [2016-06-10]. http://storm.apache.org.
[13] The TPC-H benchmark[EB/OL]. [2016-06-10]. http://www.tpc.org/tpch.