中文摘要：

随着大数据应用的普及,高效可扩展的数据流操作在实时分析处理中扮演着越来越重要的角色.分布式并行处理架构是应对大流量、低延时数据流处理任务的一种有效解决方案.然而在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. Thispaper 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.