分布式数据流上的高性能分发策略

来源：软件学报杂志2017年第3期北京时间：

作者：房俊华,王晓桐,张蓉,周傲英

单位：房俊华，华东师范大学 计算机科学与软件工程学院, 上海 200062;上海市高可信计算重点实验室(华东师范大学), 上海 20006211,王晓桐，华东师范大学 计算机科学与软件工程学院, 上海 200062;上海市高可信计算重点实验室(华东师范大学), 上海 20006202,张蓉，华东师范大学 计算机科学与软件工程学院, 上海 200062;上海市高可信计算重点实验室(华东师范大学), 上海 20006203,周傲英，华东师范大学 计算机科学与软件工程学院, 上海 200062;上海市高可信计算重点实验室(华东师范大学), 上海 20006204

摘要：随着大数据应用的普及，高效可扩展的数据流操作在实时分析处理中扮演着越来越重要的角色.分布式并行处理架构是应对大流量、低延时数据流处理任务的一种有效解决方案.然而在Key-based分组并行处理中，由于数据的倾斜分布及数据流本身的实时、动态和数据规模不可预知等特性，使得数据流分布并行处理系统存在持续且动态负载不均衡现象，这会造成系统时效性降低、硬件资源浪费等问题.现有的研究工作处理均衡负载有两种方案：（1）基于key粒度的迁移，使得并行处理节点负载达到均衡；（2）基于元组粒度级别的拆分，采用随机分发使系统均衡.前者将系统调整至给定的均衡容忍范围内，类似于一维装箱的NP问题；后者对key的拆分势必带来新的为维护Key-based操作的正确性而增加的额外代价，如内存及网络通信成本.综合两种方法，提出对key按需拆分、尽量合并的方法，通过轻量级均衡调整算法以及保证Key-based操作特性的拆分方法，使系统既能达到后者的均衡，又能减少细粒度均衡所带来的额外代价.

关键词：分布式数据流;负载倾斜;基于Key操作;均衡调整;负载迁移

基金资助：国家高技术研究发展计划（863）（2015AA015307）；国家自然科学基金（61232002，61332006，61572194）