主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公编辑办公English
2018-2019年专刊出版计划 微信服务介绍 最新一期:2018年第12期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
王春凯,孟小峰.应对倾斜数据流在线连接方法.软件学报,2018,29(3):869-882
应对倾斜数据流在线连接方法
Online Join Method for Skewed Data Streams
投稿时间:2017-07-31  修订日期:2017-09-05
DOI:10.13328/j.cnki.jos.005440
中文关键词:  分布式数据流管理系统  在线连接  数据倾斜  状态迁移  二部图连接模型
英文关键词:distributed data stream management system  online join  data skew  state migration  bipartite graph-based join model
基金项目:国家自然科学基金(61532016,61379050,61532010,91646203,61762082);国家重点研发计划(2016YFB1000602,2016YFB1000603);中国人民大学科学研究基金(11XNL010);河南省科技开放合作项目(172106000077)
作者单位E-mail
王春凯 中国人民大学 信息学院, 北京 100872  
孟小峰 中国人民大学 信息学院, 北京 100872 xfmeng@ruc.edu.cn 
摘要点击次数: 753
全文下载次数: 777
中文摘要:
      并行环境下的分布式连接处理要求制定划分策略以减少状态迁移和通信开销.相对于数据库管理系统而言,分布式数据流管理系统中的在线θ连接操作需要更高的计算成本和内存资源.基于完全二部图的连接模型可支持分布式数据流的连接操作.因为连接操作的每个关系仅存放于二部图模型的一侧处理单元,需复制数据,且处理单元相互独立,因此该模型具有内存高效、易伸缩和可扩展等特性.然而,由于数据流速的不稳定性和属性值分布的不均衡性,导致倾斜数据流的连接操作易出现集群负载不均衡的现象.针对倾斜数据流的连接操作,模型法动态分配查询节点,并需要人工干预数据分组的参数设置.尤其是应对全部历史数据的连接查询,模型效率更低.基于上述问题,提出了管理倾斜数据流连接的框架,使用基于键值和元组混合的划分样式,有效应对二部图模型的各侧倾斜数据.设计了重新动态分配查询节点的策略和状态迁移算法,以支持全历史数据的连接查询和自适应的资源管理.针对合成数据和真实数据的实验结果表明,该方案可有效应对倾斜数据的连接操作,并进一步提升分布式数据流管理系统的吞吐率,特别是降低云环境中的计算成本.
英文摘要:
      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.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利