  When processing data streams with highly skewed and nonstationary key
distributions, we often observe overloaded partitions when the hash
partitioning fails to balance data correctly. To avoid slow tasks that delay
the completion of the whole stage of computation, it is necessary to apply
adaptive, on-the-fly partitioning that continuously recomputes an optimal
partitioner, given the observed key distribution. While such solutions exist
for batch processing of static data sets and stateless stream processing, the
task is difficult for long-running stateful streaming jobs where key
distribution changes over time. Careful checkpointing and operator state
migration is necessary to change the partitioning while the operation is
running.
  Our key result is a lightweight on-the-fly Dynamic Repartitioning (DR) module
for distributed data processing systems (DDPS), including Apache Spark and
Flink, which improves the performance with negligible overhead. DR can
adaptively repartition data during execution using our Key Isolator Partitioner
(KIP). In our experiments with real workloads and power-law distributions, we
reach a speedup of 1.5-6 for a variety of Spark and Flink jobs.
