Keyed state, operator state and the indivisible key

Why does union state not scale?

Keyed state versus operator state, and the indivisible key

Keyed state: one writer per key

Parallelism requires that each instance owns a disjoint slice of the state, so that no coordination is needed per record. Partitioning by key achieves this. hash(key) decides the owner, so every key has exactly one writer. The engine gets serializability per key (the effect is the same as processing that key's records one at a time, in order) for free, by construction, rather than by concurrency control. Systems with shared data need locks, multi-version storage and conflict checks. Here none of that is needed, because the partitioning already guarantees a single writer.

The price: order exists per key and nowhere else. There is no global order across keys. (Independence of keys is assumed, which is the "independence" law again.)

Operator state: per-instance, no key

Operator state belongs to an instance, not to a key. Examples: the source's offsets, a sink's open transaction handle, a connector's cursor. Because there is no key to hash, rescaling needs an explicit redistribution scheme:

• Split-list (round-robin): the old instances' lists are concatenated and divided among the new instances.
• Union (broadcast): every entry is sent to every new instance.

Union redistribution is a scaling trap. State that every instance holds in full grows with entries × parallelism.

It works at 10 instances and dies at 500.

The indivisible key

The most streaming-specific skew failure follows immediately: a single key's state is indivisible. All records of one key go to one instance, and that key's accumulator lives in exactly one slot (one instance's share of the state).

Pre-reducing is the only escape: salt the key over k sub-keys, aggregate each, then combine the partial results (two-phase aggregation). It works only for associative and commutative aggregates (sum, count, max), adds a shuffle and a latency stage, and does nothing at all for joins, pattern matching, or anything that depends on order.