支持大规模流数据处理的弹性在线MapReduce模型及拓扑协议

doi:10.13229/j.cnki.jdxbgxb201604031

吉林大学学报(工学版) ›› 2016, Vol. 46 ›› Issue (4): 1222-1231.doi: 10.13229/j.cnki.jdxbgxb201604031

支持大规模流数据处理的弹性在线MapReduce模型及拓扑协议

魏晓辉^{1, 2}, 李翔¹, 李洪亮^{1, 2}, 李聪¹, 庄园¹, 于洪梅¹

1.吉林大学计算机科学与技术学院,长春130012;
2.吉林大学符号计算与知识工程教育部重点实验室,长春130012

收稿日期:2015-05-15 出版日期:2016-07-20 发布日期:2016-07-20
通讯作者: 李洪亮(1983-),男,讲师,博士.研究方向:分布式计算,集群计算.E-mail:lihongliang@jlu.edu.cn
作者简介:魏晓辉(1972-),男,教授,博士生导师.研究方向:分布式计算,集群计算和网络安全.E-mail:weixh@jlu.edu.cn
基金资助:
国家自然科学基金项目(61170004); 国家深部探测技术与实验研究专项项目(SinoProbe-09-01); 高等学校博士学科点专项科研基金项目(20130061110052); 吉林省科技发展计划重点科技攻关项目(20140204013GX)

Flexible Online MapReduce model and topology protocols supporting large-scale stream data processing

WEI Xiao-hui^{1, 2}, LI Xiang¹, LI Hong-liang^{1, 2}, LI Cong¹, ZHUANG Yuan¹, YU Hong-mei¹

1.College of Computer Science and Technology,Jilin University, Changchun 130012,China;
2.Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education, Jilin University, Changchun 130012,China

Received:2015-05-15 Online:2016-07-20 Published:2016-07-20

摘要/Abstract

摘要： 针对现阶段大规模流数据在线处理的广泛需求,本文提出了弹性在线MapReduce流数据处理模型及相关的动态拓扑结构协议。该模型兼容现有MapReduce模型,采用内存计算模式,并具有动态的作业拓扑结构,支持大规模流数据处理作业在运行过程中的弹性调整,从而满足流数据的时效性、动态性和突发性等特殊要求。在弹性在线MapReduce模型的基础上建立了流数据处理作业动态拓扑结构管理机制,设计了作业在线初始化协议和在线调整协议。为进一步提高系统灵活性和整合资源,提出了作业间的操作共享概念,设计了作业共享协议。通过协议分析,本文提出的在线初始化协议、在线动态调整协议及作业共享协议的最大复杂度均为O(n);在数据流量发生突发性变化时,系统具有良好的可伸缩性。

关键词: 计算机系统结构, 流数据处理, 内存计算, MapReduce, 拓扑结构, 操作共享

Abstract: To meet the rapid growing requirements of large-scale data online processing, this paper proposes a Flexible Online MapReduce model and related dynamic topology protocols for streaming data processing. This model is compatible with existing MapReduce application, adopts in-memory computing, and possesses a dynamic job topology. It can support flexible adjustments of large-scale stream data in runtime to meet the requirements of real-time processing, dynamic flow and burst of data. Based on Flexible Online MapReduce model, the system architecture is designed to facilitate the model and a series of protocols are introduced, including Online Topology Initialization Protocol (OTIP), and Online Dynamic Adjusting Protocol (ODAP) for stream data job. To further integrate the system resources, the concept of operation sharing is introduced and Job Sharing Protocol (JSP) is designed. Protocol analyses illustrate that the communicating complexity of the protocol is O(n), and the system is able to adapt to the burst of stream data.

Key words: computer system organization, stream processing, memory computing, MapReduce, topology structure, job sharing

中图分类号:

TP391

魏晓辉, 李翔, 李洪亮, 李聪, 庄园, 于洪梅. 支持大规模流数据处理的弹性在线MapReduce模型及拓扑协议[J]. 吉林大学学报(工学版), 2016, 46(4): 1222-1231.

WEI Xiao-hui, LI Xiang, LI Hong-liang, LI Cong, ZHUANG Yuan, YU Hong-mei. Flexible Online MapReduce model and topology protocols supporting large-scale stream data processing[J]. 吉林大学学报(工学版), 2016, 46(4): 1222-1231.

参考文献

[1] Dean J,Ghemawat S. MapReduce: simplified data processing on large clusters[J].Commun ACM, 2008,51(1):107-113.
[2] Apache Hadoop[EB/OL].[2012-10-10].http:∥hadoop.apache.org/
[3] Isard B M, Budiy M,Yu Y,et al. Dryad: Distributed data-parallel programs from sequential building blocks[J]. Proceedings of ACM SIGOPS Operating Systems Review, 2007,41(3):59-72.
[4] Lam W, Liu L, Prasad S T S, et al. Muppet: MapReduce-style processing of fast data[J]. Proceedings of the VLDB Endowment, 2012, 5(12): 1814-1825.
[5] Brito A, Martin A, Knauth T, et al. Scalable and low-latency data processing with stream MapReduce[C]∥IEEE Third International Conference on Cloud Computing Technology and Science (CloudCom), 2011: 48-58.
[6] Gannon D,Deelman E,Shields M, et al.Workflows for e-Science.Introduction[M].Berlin:Springer,2007:1-9.
[7] Nykiel T,Potamias M, Mishra C,et al.MRShare: sharing across multiple queries in MapReduce[J].Proceedings of the VLDB Endowment,2010,3(1-2):494-505.
[8] Nykiel T, Potamias M, Mishra C, et al. Sharing across Multiple MapReduce Jobs[J]. Acm Transactions on Database Systems, 2014, 39(2):1-46.
[9] Luckham D C. The Power of Events: An Introduction to Complex Event Processing in Distributed Enterprise Systems[M]. Boston, MA, USA: Addison-Wesley Longman Publishing Co, Inc, 2001.
[10] Marz N. Storm-distributed and fault-tolerant realtime computation[EB/OL].http:∥storm-project. net/,2013-02-01.
[11] Neumeyer L, Robbins B, Nair A, et al. S4: distributed stream computing platform[C]∥Proceedings of IEEE International Conference on Data Mining Workshops, 2010:170-177.
[12] Condie T, Conway N, Alvaro P, et al. MapReduce online[J].Proceedings of the 7th USENIX Symposium on Networked Systems Design and Implementation, 2010,10(4):313-328.
[13] Backman N, Pattabiraman K, Fonseca R, et al. C-MR: continuously executing MapReduce workflows on multi-core processors[C]∥International Workshop on Mapreduce and ITS Applications, Mapreduce,2012:1-8.

相关文章 15

[1]	余宜诚, 胡亮, 迟令, 初剑峰. 一种改进的适用于多服务器架构的匿名认证协议[J]. 吉林大学学报(工学版), 2018, 48(5): 1586-1592.
[2]	董坚峰, 张玉峰, 戴志强. 改进的基于狄利克雷混合模型的推荐算法[J]. 吉林大学学报(工学版), 2018, 48(2): 596-604.
[3]	赵博, 秦贵和, 赵永哲, 杨文迪. 基于半陷门单向函数的公钥密码[J]. 吉林大学学报(工学版), 2018, 48(1): 259-267.
[4]	刘磊, 刘利娟, 吴新维, 张鹏. 基于ECPMR的编译器测试方法[J]. 吉林大学学报(工学版), 2017, 47(4): 1262-1267.
[5]	董立岩, 王越群, 贺嘉楠, 孙铭会, 李永丽. 基于时间衰减的协同过滤推荐算法[J]. 吉林大学学报(工学版), 2017, 47(4): 1268-1272.
[6]	于斌斌, 武欣雨, 初剑峰, 胡亮. 基于群密钥协商的无线传感器网络签名协议[J]. 吉林大学学报(工学版), 2017, 47(3): 924-929.
[7]	邓昌义, 郭锐锋, 张忆文, 王鸿亮. 基于平衡因子的动态偶发任务低功耗调度算法[J]. 吉林大学学报(工学版), 2017, 47(2): 591-600.
[8]	魏晓辉, 刘智亮, 庄园, 李洪亮, 李翔. 支持大规模流数据在线处理的自适应检查点机制[J]. 吉林大学学报(工学版), 2017, 47(1): 199-207.
[9]	郝娉婷, 胡亮, 姜婧妍, 车喜龙. 基于多管理节点的乐观锁协议[J]. 吉林大学学报(工学版), 2017, 47(1): 227-234.
[10]	车翔玖, 梁森. 一种基于大顶堆的SPIHT改进算法[J]. 吉林大学学报(工学版), 2016, 46(3): 865-869.
[11]	董悦丽, 郭权, 孙斌, 康玲. 药物分子对接动态任务迁移优化[J]. 吉林大学学报(工学版), 2015, 45(4): 1253-1259.
[12]	李抵非, 田地, 胡雄伟. 基于分布式内存计算的深度学习方法[J]. 吉林大学学报(工学版), 2015, 45(3): 921-925.
[13]	匡哲君，师唯佳，胡亮. 基于无线传感器网络的角色成员关系剩余能量新算法[J]. 吉林大学学报(工学版), 2015, 45(2): 600-605.
[14]	张忆文，郭锐锋. 实时系统混合任务低功耗调度算法[J]. 吉林大学学报(工学版), 2015, 45(1): 261-266.
[15]	张忆文^{1, 2}, 郭锐锋¹. 制的容错节能调度算法[J]. 吉林大学学报(工学版), 2014, 44(4): 1112-1117.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

支持大规模流数据处理的弹性在线MapReduce模型及拓扑协议

Flexible Online MapReduce model and topology protocols supporting large-scale stream data processing

RICH HTML

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 10