Dynamic scaling of stateful operators

What does rescaling a stateful job cost, and why is autoscaling it so hard?

Changing parallelism changes the key-to-instance mapping, so state must physically move. Key groups make this tractable:

• Reassign contiguous ranges of groups, rather than remapping keys.
• With incremental checkpointing, you can hand a new instance a set of files corresponding to its ranges, instead of re-partitioning record by record.
• When a range splits across a file boundary, the receiving instance must still filter or split the underlying files. So rescaling by a factor that divides the key-group count is cheaper than an arbitrary factor.

Example: with 128 groups, going from 8 to 16 instances gives each new instance exactly 8 groups, cutting old ranges cleanly in half. Going from 8 to 10 gives instances 12 or 13 groups each (128 ÷ 10 = 12.8), so the new ranges cut across the old ones.

The cost: stop-and-restore plus catch-up

The usual procedure is to stop the job, redistribute state, and restore. Downtime ≈ state moved ÷ network bandwidth + restore. Then comes the catch-up arithmetic from Incremental checkpoints and recovery time, which is the dominant term. Scaling a 500 GB job is a multi-minute outage plus a lag drain. (Ana's 14 minutes of downtime, followed by a long drain.)

Why autoscaling is hard

An autoscaler is a control loop, and one whose actuation is expensive, slow, and itself increases lag will oscillate unless heavily damped (hysteresis, cooldowns, asymmetric thresholds). For a stateful job it is worse than for a stateless fleet: scaling up during a backlog makes the backlog worse before it makes it better, because the job is down while its state moves.

This is the single strongest argument for disaggregated state (remote state): it makes the actuator cheap, which changes the control problem rather than merely improving a constant.