流式处理系统的动态数据分配技术

J4 ›› 2014, Vol. 36 ›› Issue (10): 1846-1853.

流式处理系统的动态数据分配技术

王成章1,林学练1,谭静芳2

(1.北京航空航天大学计算机学院，北京 100191；2.泰山学院物理与电子工程学院，山东泰安 271021)

收稿日期:2014-06-11 修回日期:2014-08-24 出版日期:2014-10-25 发布日期:2014-10-25
基金资助:
国家973计划资助项目(2014CB340300)

Dynamic data distribution for stream processing system

WANG Chengzhang1,LIN Xuelian1,TAN Jingfang2

(1.School of Computer Science and Engineering,Beihang University,Beijing 100191;
2.School of Physics and Electronic Engineering,Taishan University,Taian 271021,China)

Received:2014-06-11 Revised:2014-08-24 Online:2014-10-25 Published:2014-10-25

摘要/Abstract

摘要：

流式数据处理中，数据倾斜等原因易导致计算节点的负载不均衡，降低系统处理能力。传统的负载均衡方法，比如算子分配、算子迁移和负载脱落等技术因为相对较高的性能代价，在流式处理系统中没有得到广泛的应用。针对流式处理系统的特点，提出一种新的负载均衡方法。在该方法中，计算单元的数据被划分为若干分区，并且数据分区可以在计算单元中动态分配和迁移，在较少干扰系统运行的情况下，通过动态调整各计算单元的分区，平衡各个计算单元的输入流和利用率，以此达到负载平衡的目的。在此基础上，设计并实现了流式处理系统的负载均衡算法和数据在线迁移技术。实验结果表明，该方法能够显著减少数据处理的平均延迟，提高系统吞吐量。

关键词: 数据流, 流式处理, 负载均衡, 数据分配, 数据迁移

Abstract:

In stream processing systems,data skew often leads to load imbalance among computing nodes,thereby increases the response time of data process.Traditional load balancing methods such as operator distribution,operator migration and load shedding have never been widely applied in stream processing systems because of a relatively high performance penalty.Considering the characteristics of stream processing systems, a new load balancing mechanism is proposed. In this mechanism, the data on computing units are split into some sections,and each section can be allocated and migrated dynamically among computing units.Then,for the purpose of load balancing, the input streams and utilizations are balanced among computing units by adjusting sections with few disturbances on steam processing systems. Based on this,we design and implement a load balancing algorithm as well as an online data migration method.The experimental results show that our mechanism can reduce the average latency of data processing and improve the system throughput significantly.

Key words: data stream;stream processing;load balancing;data distribution;data migration

王成章1,林学练1,谭静芳2. 流式处理系统的动态数据分配技术[J]. J4, 2014, 36(10): 1846-1853.

WANG Chengzhang1,LIN Xuelian1,TAN Jingfang2. Dynamic data distribution for stream processing system [J]. J4, 2014, 36(10): 1846-1853.

参考文献［24］

［1］	Abadi D, Ahmad Y, Balazinska M. The design of the borealis stream processing engine［C］∥Proc of the 2005 CIDR Conference,2005:277289.
［2］	Golab L, Ozsu M T. Issues in data stream management［J］. ACM SIGMOD Record, 2003, 32(2):514.
［3］	Gupta D, Bepari P. Load sharing in distributed systems［C］∥Proc of the National Workshop on Distributed Computing, 1999:204217.
［4］	Shirazi B A, Hurson A R, Kavi K M. Scheduling and load balancing in parallel and distributed systems［M］. Washington DC:IEEE Computer Science Press, 1995.
［5］	Kumar V, Cooper B, Cai Z, et al. Resourceaware distributed stream management using dynamic overlays［C］∥Proc of ICDCS, 2005:783792.
［6］	Brathergsengen K. Hashing methods and relational algebra operations［C］∥Proc of VLDB, 1984:9199.
［7］	Carney D, Cetintemel U, Cherniack M, et al. Monitoring streamsA new class of data management applications［C］∥Proc of VLDB Conference, 2002:215226.
［8］	Motwani R, Widom J, Arasu A, et al. Query processing, approximation, and resource management in a data stream management system［C］∥Proc of the 2003 CIDR Conference, 2003:92105.
［9］	KyongHa Lee, YoonJoon Lee, Hyunsik Choi,et al. Parallel data processing with MapReduce:A survey［J］. SIGMOD Record, 2011, 40(4):1120.
［10］	Neumeyer L，Robbins B.S4:Distributed stream computing platform［C］∥Proc of IEEE International Conference on Data Mining Workshops,2010:170177.
［11］	Xing Ying, JeongHyon Hwang, Stan Zdonik. Providing resiliency to load variations in distributed stream processing［C］∥Proc of VLDB ’06,2006:775786.
［12］	http://storm.incubator.apache.org/.
［13］	Murray D G, McSherry F, Isaacs R, et al. Naiad:A timely dataflow system［C］∥Proc of the 24th ACM Symposium on Operating Systems Principles (SOSP), 2013:320327.
［14］	Mehta M A. Designing an effective dynamic load balancing algorithm considering imperative desing issues in distributed systems［C］∥Proc of CSNT, 2012:397401.
［15］	Penmatsaa S,Chronopoulos A T.Gametheoretic static load balancing for distributed systems［J］. Journal of Parallel Distributed Computing, 2011,71:537555.
［16］	Mehta M A, Jinwala D C. Analysis of significant components for designing an effective dynamic load balancing algorithm in distributed systems［C］∥Proc of ISMS, 2012:531536.
［17］	Shardul Jain,Himanshu Singh,Ankur Chauhan,et al. Heuristicsaided load balancing in distributed systems and node prioritization:An intelligent approach［C］∥Proc of ICCMS, 2010:521526.
［18］	Repantis T,Drougas Y,Kalogeraki V.Adaptive component composition and load balancing for distributed stream processing applications［J］. PeertoPeer Networking and Applications, 2009(2):6074.
［19］	Ghada F, Kabbany E I, Wanas N M, et al. A dynamic load balancing framework for realtime applications in message passing systems［J］. International Journal of Parallel Programming,2011,39(2):143182.
［20］	Rosas C, Sikora A, Jorba J. Improving performance on dataintensive applications using a load balancing methodology based on divisible load theory［J］. International Journal of Parallel Programming,2014,42(1):94118.
［21］	Guha S, Koudas N. Approximating a data stream for querying and estimation:Algorithms and performance evaluation［C］∥Proc of the 18th International Conference on Data Engineering, 2002:567576.
［22］	Cherniack M, Balakrishnan H, Balazinska M, et al. Scalable distributed stream processing［C］∥Proc of CIDR, 2003:11011104.
［23］	Drougas Y,Repantis T,Kalogeraki V.Load balancing techniques for distributed stream processing applications in overlay enviroments［C］∥Proc of ISORC, 2006:356367.
［24］	http://spark.apache.org/streaming/.

[1]	丁滟, 王闯, 冯了了, 王锋, 常俊胜. 基于区块链监管的联盟数据可信流通[J]. 计算机工程与科学, 2022, 44(10): 1771-1780.
[2]	李文佳, 史岚, 季航旭, 罗意彭. 面向Flink的负载均衡任务调度算法的研究与实现[J]. 计算机工程与科学, 2022, 44(07): 1141-1151.
[3]	徐浩桐, 黄山, 孙国璋, 贺菲莉, 段晓东, . 面向云环境的Flink负载均衡策略[J]. 计算机工程与科学, 2022, 44(05): 779-787.
[4]	张喜龙, 韩萌, 陈志强, 武红鑫, 李慕航. 基于Hellinger距离的不平衡漂移数据流Boosting分类算法[J]. 计算机工程与科学, 2022, 44(05): 788-799.
[5]	罗晓霞, 王佳, 罗香玉, 李嘉楠 . 一种基于GN算法的动态图划分方法[J]. 计算机工程与科学, 2022, 44(02): 306-311.
[6]	李力, 汪硕, 黄韬, 刘韵洁, . 数据中心网络四层负载均衡技术综述[J]. 计算机工程与科学, 2022, 44(01): 48-59.
[7]	乔冠杰, 吕高锋, 谭靖, 莫露莎. 大规模数据流统计中冷热流替换策略优化[J]. 计算机工程与科学, 2021, 43(09): 1567-1573.
[8]	黄山, 房六一, 徐浩桐, 段晓东, . 面向容器环境的Flink的任务调度优化研究[J]. 计算机工程与科学, 2021, 43(07): 1173-1184.
[9]	朱广林, 吕方, 赖庆宽, 陈华英, 何先波, . 编译器中激进蝴蝶优化方法的研究与实现[J]. 计算机工程与科学, 2021, 43(06): 962-968.
[10]	陈俊彦, 李玥, 梁楚欣, 雷晓春. SDN多控制器部署及流量均衡研究[J]. 计算机工程与科学, 2021, 43(05): 830-835.
[11]	丁峻宏, 苗新强, 李根国. 面向异构超算的结构分析高效并行计算方法[J]. 计算机工程与科学, 2020, 42(12): 2133-2140.
[12]	文凯, 耿小海, 朱璐伟, 许萌萌, . 基于AO算法的数据流频繁项集挖掘[J]. 计算机工程与科学, 2020, 42(12): 2259-2264.
[13]	王丽, 郭振华, 曹芳, 高开, 赵雅倩, 赵坤. 面向模型并行训练的模型拆分策略自动生成方法[J]. 计算机工程与科学, 2020, 42(09): 1529-1537.
[14]	张开琦, 刘晓燕, 王信, 吉春山, 严馨. 基于动态权重的一致性哈希微服务负载均衡优化[J]. 计算机工程与科学, 2020, 42(08): 1339-1344.
[15]	熊菊霞1,2,3,吴尽昭1,2,3. 异构复杂信息网络敏感数据流动态挖掘[J]. 计算机工程与科学, 2020, 42(04): 628-633.