Partitioning

What Stays vs Moves

A key moves exactly when its old and new partitions differ.

highlighted = computed this step

What stays and what moves

A rebalance table is the old route and new route for each key. A key stays only when those partition names match. Note: the moved and stayed lists are recomputed from the route comparison.

stays iff route unchanged\text{stays iff route unchanged}

Range moved set

In the range case, moved count is 1 and stayed count is 4.

moved=1,stayed=4\text{moved}=1,\quad \text{stayed}=4

Range and hash sharding are exact routing functions on tiny pinned key sets; real sharding adds consistent hashing, skew, hot partitions, and rebalancing cost, which are empirical and operational concerns beyond this model - no product claims.

Range stays and moves - moved: 28; stayed: 2,12,24,26keyfromtostatus2P0P0stayed12P1P1stayed24P2P2stayed26P2P2stayed28P2P3moved

Hash moved set

In the hash case, moved count is 5 and stayed count is 3. Note: same keys can move differently under a different routing function.

moved=5,stayed=3\text{moved}=5,\quad \text{stayed}=3

Range and hash sharding are exact routing functions on tiny pinned key sets; real sharding adds consistent hashing, skew, hot partitions, and rebalancing cost, which are empirical and operational concerns beyond this model - no product claims.

Hash stays and moves - moved: 3,4,5,6,7; stayed: 0,1,2keyfromtostatus0P0P0stayed1P1P1stayed2P2P2stayed3P0P3moved4P1P0moved5P2P1moved6P0P2moved7P1P3moved

Summary

Moved-key sets are the exact audit trail of a rebalance. Note: the model names movement but does not estimate migration cost.

movement is recomputed\text{movement is recomputed}