2015/10/26 by Muhammad Anis Uddin Nasir, Gianmarco De Francisci Morales, Nasir, Muhammad Anis Uddin +8
Computer Science · #Advanced Database Systems and Queries #Cloud Computing and Resource Management #Distributed #Distributed systems and fault tolerance #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC) #cs.DC
paper · pdf · doi:10.48550/arxiv.1510.07623
14 pages. arXiv admin note: substantial text overlap with arXiv:1504.00788
arxiv created 2015/10/26 · openalex publication_date 2015/10/26 · arxiv updated 2015/10/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the problem of load balancing in distributed stream processing engines, which is exacerbated in the presence of skew. We introduce Partial Key Grouping (PKG), a new stream partitioning scheme that adapts the classical "power of two choices" to a distributed streaming setting by leveraging two novel techniques: key splitting and local load estimation. In so doing, it achieves better load balancing than key grouping while being more scalable than shuffle grouping. We test PKG on several large datasets, both real-world and synthetic. Compared to standard hashing, PKG reduces the load imbalance by up to several orders of magnitude, and often achieves nearly-perfect load balance. This result translates into an improvement of up to 175% in throughput and up to 45% in latency when deployed on a real Storm cluster. PKG has been integrated in Apache Storm v0.10.