  Streaming applications frequently encounter skewed workloads and execute on
heterogeneous clusters. Optimal resource utilization in such adverse conditions
becomes a challenge, as it requires inferring the resource capacities and input
distribution at run time. In this paper, we tackle the aforementioned
challenges by modeling them as a load balancing problem. We propose a novel
partitioning strategy called Consistent Grouping (CG), which enables each
processing element instance (PEI) to process the workload according to its
capacity. The main idea behind CG is the notion of small, equal-sized virtual
workers at the sources, which are assigned to workers based on their
capacities. We provide a theoretical analysis of the proposed algorithm and
show via extensive empirical evaluation that our proposed scheme outperforms
the state-of-the-art approaches, like key grouping. In particular, CG achieves
3.44x better performance in terms of latency compared to key grouping.
