Scalable Distributed Stream Join Processing

Efficient and scalable stream joins play an important role in performing real-time analytics for many cloud applications. However, like in conventional database processing, online theta-joins over data streams are computationally expensive and moreover, being memory-based processing, they impose high memory requirement on the system. In this paper, we propose a novel stream join model, called join-biclique, which organizes a large cluster as a complete bipartite graph. Join-biclique has several strengths over state-of-the-art tech-niques, including memory-efficiency, elasticity and scalabil-ity. These features are essential for building efficient and scalable streaming systems. Based on join-biclique, we de-velop a scalable distributed stream join system, BiStream, over a large-scale commodity cluster. Specifically, BiStream is designed to support efficient full-history joins, window-based joins and online data aggregation. BiStream also sup-ports adaptive resource management to dynamically scale out and down the system according to its application work-loads. We provide both theoretical cost analysis and ex-tensive experimental evaluations to evaluate the efficiency, elasticity and scalability of BiStream. 1