FlexSP:(1 + β)-Choice based Flexible Stream Partitioning for Stateful Operators

This is the authors' abstract. We don't add key points for this paper.

Stream partitioning has a fundamental effect on the efficiency of data parallelism in distributed stream processing systems. The skewed and time-varying nature of streaming data makes it challenging to achieve load balancing while minimizing the cost incurred. The requirement of adaptivity further complicates the problem, that the partitioning mechanism should not only be able to capture the changes in workload and adjust itself but also be quite tolerant of the changes because of the lag in statistics. Existing approaches use one-choice or multiple-choice schemes to make tradeoffs between these factors, but they tend to treat them as opposites, which either fails to achieve good load balancing or incurs excessive cost. There is a lack of deeper insight into how partitioning behavior affects load balancing, cost, and adaptivity when the keys have a different number of candidate choices. Also, it requires a flexible partitioning scheme to allow different trade-offs among the three factors for various scenarios.