应对倾斜数据流在线连接方法

并行环境下的分布式连接处理要求制定划分策略以减少状态迁移和通信开销。相对于数据库管理系统而言，分布式数据流管理系统中的在线θ连接操作需要更高的计算成本和内存资源。基于完全二部图的连接模型可支持分布式数据流的连接操作。因为连接操作的每个关系仅存放于二部图模型的一侧处理单元，无需复制数据，且处理单元相互独立，因此该模型具有内存高效、易伸缩和可扩展等特性。然而，由于数据流速的不稳定性和属性值分布的不均衡性，导致倾斜数据流的连接操作易出现集群负载不均衡的现象。针对倾斜数据流的连接操作，模型无法动态分配查询节点，并需要人工干预数据分组的参数设置。尤其是应对全部历史数据的连接查询，模型效率更低。基于上述问题，提出了管理倾斜数据流连接的框架，使用基于键值和元组混合的划分样式有效应对二部图模型的各侧倾斜数据。并设计了重新动态分配查询节点的策略和状态迁移算法，以支持全历史数据的连接查询和自适应的资源管理。针对合成数据和真实数据的实验表明，该方案可有效应对倾斜数据的连接操作并进一步提升分布式数据流管理系统的吞吐率，特别是降低云环境中的计算成本。

Online Join Method for Skewed Data Streams

Scalable distributed join processing in a parallel environment requires a partitioning policy to transfer data while minimizing the size of migrated statement and the number of communicated messages. Online theta-joins over data streams are more computationally expensive and impose higher memory requirement in distributed data stream management systems (DDSMS) than database management systems (DBMS). The complete bipartite graph-based model can support distributed stream joins, and has the characteristics of memory-efficiency, elasticity and scalability. Because each relation is stored in its corresponding processing units without data replicas and the units are independent of each other. However, due to the instability of data stream rate and the imbalance of attribute value distribution, the online theta-joins over skewed data streams lead to the load imbalance of cluster. In this case, the bipartite graph-based model is unable to allocate the query nodes dynamically, and requires to set parameters about the grouping manually. What is more serious is that the effect of the full-history join is worse. In this paper, we present a framework for handling skewed stream join, enhancing the adaptability of the join model and minimizing the system cost based on the varying workloads. Our proposal includes a mixed key-based and tuple-based partitioning scheme to handle skewed data in each side of the bipartite graph-based model, a strategy for redistribution of query nodes in two sides of this model, and a migration algorithm about state consistency to support full-history joins and adaptive resource management. Experiments with synthetic data and real data show that our method can effectively handle skewed data streams and improve the throughput of DDSMS. It proves the effectiveness of our method, especially on reducing the operational cost in the cloud environment.