Nothing Gets Rehashed

A key-value store is built on a fixed ring of 256 partitions. A key's partition is decided once, by the top bits of its hash, and never recomputed. The cluster runs on 8 nodes, so each node owns 32 partitions.

You double the cluster to 16 nodes. Ignore replication.

What moves?

Half the keys land in a different partition, but only 128 of those partitions change host, so about 25 percent of the bytes move

128 partitions change owner, so roughly half the bytes cross the network, and no key changes partition: only the partition-to-node assignment is rewritten

Every key is rehashed, because $\mathrm{hash}(k) \bmod n$ changes when $n$ goes from 8 to 16

16 partitions move, one to each new node, so about 6 percent of the bytes cross the network