| 本文已被：浏览 3495次 下载 6718次 |
码上扫一扫！ |
|
|
| 分布式数据流上的高性能分发策略 |
|
房俊华1,2, 王晓桐1,2, 张蓉1,2, 周傲英1,2
|
|
1.华东师范大学 计算机科学与软件工程学院, 上海 200062;2.上海市高可信计算重点实验室(华东师范大学), 上海 200062
|
|
| 摘要: |
| 随着大数据应用的普及，高效可扩展的数据流操作在实时分析处理中扮演着越来越重要的角色.分布式并行处理架构是应对大流量、低延时数据流处理任务的一种有效解决方案.然而在Key-based分组并行处理中，由于数据的倾斜分布及数据流本身的实时、动态和数据规模不可预知等特性，使得数据流分布并行处理系统存在持续且动态负载不均衡现象，这会造成系统时效性降低、硬件资源浪费等问题.现有的研究工作处理均衡负载有两种方案：（1）基于key粒度的迁移，使得并行处理节点负载达到均衡；（2）基于元组粒度级别的拆分，采用随机分发使系统均衡.前者将系统调整至给定的均衡容忍范围内，类似于一维装箱的NP问题；后者对key的拆分势必带来新的为维护Key-based操作的正确性而增加的额外代价，如内存及网络通信成本.综合两种方法，提出对key按需拆分、尽量合并的方法，通过轻量级均衡调整算法以及保证Key-based操作特性的拆分方法，使系统既能达到后者的均衡，又能减少细粒度均衡所带来的额外代价. |
| 关键词: 分布式数据流 负载倾斜 基于Key操作 均衡调整 负载迁移 |
| DOI：10.13328/j.cnki.jos.005168 |
| 分类号:TP311 |
| 基金项目:国家高技术研究发展计划（863）（2015AA015307）；国家自然科学基金（61232002，61332006，61572194） |
|
| High-Performance Data Distribution Algorithm on Distributed Stream Systems |
|
FANG Jun-Hua1,2, WANG Xiao-Tong1,2, ZHANG Rong1,2, ZHOU Ao-Ying1,2
|
|
1.School of Computer Science and Software Engineering, East China Normal University, Shanghai 200062, China;2.Shanghai Key Laboratory of Trustworthy Computing(East China Normal University), Shanghai 200062, China
|
| Abstract: |
| 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. |
| Key words: distributed data stream workload skew Key-based operation workload balance workload migration |
