主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公编辑办公English
2018-2019年专刊出版计划 微信服务介绍 最新一期:2019年第10期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
房俊华,王晓桐,张蓉,周傲英.分布式数据流上的高性能分发策略.软件学报,2017,28(3):563-578
分布式数据流上的高性能分发策略
High-Performance Data Distribution Algorithm on Distributed Stream Systems
投稿时间:2016-07-31  修订日期:2016-09-14
DOI:10.13328/j.cnki.jos.005168
中文关键词:  分布式数据流  负载倾斜  基于Key操作  均衡调整  负载迁移
英文关键词:distributed data stream  workload skew  Key-based operation  workload balance  workload migration
基金项目:国家高技术研究发展计划(863)(2015AA015307);国家自然科学基金(61232002,61332006,61572194)
作者单位E-mail
房俊华 华东师范大学 计算机科学与软件工程学院, 上海 200062
上海市高可信计算重点实验室(华东师范大学), 上海 200062 
 
王晓桐 华东师范大学 计算机科学与软件工程学院, 上海 200062
上海市高可信计算重点实验室(华东师范大学), 上海 200062 
 
张蓉 华东师范大学 计算机科学与软件工程学院, 上海 200062
上海市高可信计算重点实验室(华东师范大学), 上海 200062 
rzhang@sei.ecnu.edu.cn 
周傲英 华东师范大学 计算机科学与软件工程学院, 上海 200062
上海市高可信计算重点实验室(华东师范大学), 上海 200062 
 
摘要点击次数: 728
全文下载次数: 700
中文摘要:
      随着大数据应用的普及,高效可扩展的数据流操作在实时分析处理中扮演着越来越重要的角色.分布式并行处理架构是应对大流量、低延时数据流处理任务的一种有效解决方案.然而在Key-based分组并行处理中,由于数据的倾斜分布及数据流本身的实时、动态和数据规模不可预知等特性,使得数据流分布并行处理系统存在持续且动态负载不均衡现象,这会造成系统时效性降低、硬件资源浪费等问题.现有的研究工作处理均衡负载有两种方案:(1)基于key粒度的迁移,使得并行处理节点负载达到均衡;(2)基于元组粒度级别的拆分,采用随机分发使系统均衡.前者将系统调整至给定的均衡容忍范围内,类似于一维装箱的NP问题;后者对key的拆分势必带来新的为维护Key-based操作的正确性而增加的额外代价,如内存及网络通信成本.综合两种方法,提出对key按需拆分、尽量合并的方法,通过轻量级均衡调整算法以及保证Key-based操作特性的拆分方法,使系统既能达到后者的均衡,又能减少细粒度均衡所带来的额外代价.
英文摘要:
      Along with the popularization of big data applications, scalable and efficient stream join processing plays a more important role in online real-time analysis. The distributed parallel processing framework provides an effective solution which facilitates processing of massive data stream with low latency. For Key-based calculations, data skewness and inherent features of stream data, such as real-time, dynamics and unpredictability on data volume, lead to load imbalance to distributed processing systems. Such phenomenon can produce poor performance and waste hardware resources. There have been two solutions to load imbalance:1) Key-based migration scheme that keeps balance among parallel processing nodes; 2) tuple-based partitioning scheme that distributes data randomly to achieve load balance. The former scheme adjusts system to the defined equilibrium range, which resembles the one-dimensional packing problem. And the latter maintains the accuracy of Key-based operations, which certainly incurs additional memory cost and network communication cost. This paper presents a novel parallel processing scheme that combines both Key-based and tuple-based schemes to partition keys on demand. The proposed scheme adopts a lightweight load balance algorithm and a partitioning scheme which retains the characteristics of Key-based operations, thus realizing the load balance of tuple-base strategy while reducing the additional cost of fine-grained balance.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

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