应对倾斜数据流在线连接方法
作者:
作者单位:

作者简介:

王春凯(1981-),男,河南开封人,博士,主要研究领域为分布式数据流管理;孟小峰(1964-),男,博士,教授,博士生导师,CCF会士,主要研究领域为Web数据管理,移动数据管理,XML数据管理,云数据管理,隐私保护.

通讯作者:

孟小峰,E-mail:xfmeng@ruc.edu.cn

中图分类号:

TP311

基金项目:

国家自然科学基金(61532016,61379050,61532010,91646203,61762082);国家重点研发计划(2016YFB1000602,2016YFB1000603);中国人民大学科学研究基金(11XNL010);河南省科技开放合作项目(172106000077)


Online Join Method for Skewed Data Streams
Author:
Affiliation:

Fund Project:

National Natural Science Foundation of China (61532016, 61379050, 61532010, 91646203, 61762082);The National Key Research and Development Program of China (2016YFB1000602, 2016YFB1000603);The Research Funds of Renmin University (11XNL010);the Science and Technology Opening up Cooperation project of He'nan Province (172106000077)

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    并行环境下的分布式连接处理要求制定划分策略以减少状态迁移和通信开销.相对于数据库管理系统而言,分布式数据流管理系统中的在线θ连接操作需要更高的计算成本和内存资源.基于完全二部图的连接模型可支持分布式数据流的连接操作.因为连接操作的每个关系仅存放于二部图模型的一侧处理单元,无需复制数据,且处理单元相互独立,因此该模型具有内存高效、易伸缩和可扩展等特性.然而,由于数据流速的不稳定性和属性值分布的不均衡性,导致倾斜数据流的连接操作易出现集群负载不均衡的现象.针对倾斜数据流的连接操作,模型无法动态分配查询节点,并需要人工干预数据分组的参数设置.尤其是应对全部历史数据的连接查询,模型效率更低.基于上述问题,提出了管理倾斜数据流连接的框架,使用基于键值和元组混合的划分样式,有效应对二部图模型的各侧倾斜数据.设计了重新动态分配查询节点的策略和状态迁移算法,以支持全历史数据的连接查询和自适应的资源管理.针对合成数据和真实数据的实验结果表明,该方案可有效应对倾斜数据的连接操作,并进一步提升分布式数据流管理系统的吞吐率,特别是降低云环境中的计算成本.

    Abstract:

    Scalable distributed join processing in a parallel environment requires a partitioning policy to transfer data while minimizing the size of migrated statement and the number of communicated messages. Online theta-joins over data streams are more computationally expensive and impose higher memory requirement in distributed data stream management systems (DDSMS) than standalone database management systems (DBMS). The complete bipartite graph-based model can support distributed stream joins, and has the characteristics of memory-efficiency, elasticity and scalability. This is because each relation is stored in its corresponding processing units without data replicas and the units are independent of each other. However, due to the instability of data stream rate and the imbalance of attribute value distribution, the online theta-joins over skewed data streams can lead to the load imbalance of cluster. In this case, the bipartite graph-based model is unable to allocate the query nodes dynamically, and requires to set parameters about the grouping manually. The more serious issue is that the effect of the full-history join is worse. In this paper, a framework for handling skewed stream join is presented for enhancing the adaptability of the join model and minimizing the system cost based on the varying workloads. The proposal includes a mixed key-based and tuple-based partitioning scheme to handle skewed data in each side of the bipartite graph-based model, a strategy for redistribution of query nodes in two sides of this model, and a migration algorithm about state consistency to support full-history joins and adaptive resource management. Experiments with synthetic data and real data show that the presented method can effectively handle skewed data streams and improve the throughput of DDSMS, and it also effective especially on reducing the operational cost in the cloud environment.

    参考文献
    相似文献
    引证文献
引用本文

王春凯,孟小峰.应对倾斜数据流在线连接方法.软件学报,2018,29(3):869-882

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2017-07-31
  • 最后修改日期:2017-09-05
  • 录用日期:
  • 在线发布日期: 2017-12-05
  • 出版日期:
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号