CONCEPT Cited by 1 source
Static hash partitioning¶
Static hash partitioning assigns keys to nodes via a
fixed modulo: node_id = hash(key) mod N where N is the
total node count. O(1) lookup, trivial to implement, and
the thing consistent hashing was invented to replace
(Source: sources/2023-02-22-highscalability-consistent-hashing-algorithm).
Why it fails under dynamic load¶
When N changes — one node added, one crashed — the modulo
result changes for most keys, not just the ones on the
affected node. The mapping between keys and nodes is
destroyed wholesale:
"The removal of a node (due to a server crash) breaks the existing mappings between the keys and nodes. The keys must be rehashed to restore mapping between keys and nodes."
Operational consequences:
- Massive data movement when node count changes — most keys need to migrate.
- Mass cache miss during migration — requests hit the wrong node, fail, and fall back to the origin.
- Origin overload — "the heavy load on the origin server might swamp and degrade the service", a classic thundering herd on the backing store.
Why it persists anyway¶
hash(key) mod N is what every first-year engineer reaches
for because it's one line of code and it's O(1). It works
fine for:
- Fixed-size clusters that never resize (rare in practice — even "fixed" clusters have failures).
- Stateless request dispatch where a cache miss is cheap (per-request routing to worker pools).
- Application-layer bucketing where the buckets are logical and the key set is small (e.g. 64 rollout buckets).
For stateful partitioning — caches, databases, storage — consistent hashing is strictly better.
Collision handling is a separate question¶
Static hash partitioning collisions (two nodes land on the same array index) are resolved via open addressing or chaining — both degrade the O(1) guarantee under load. Consistent hashing sidesteps this by operating in a much larger output space (32-bit or 64-bit) where collisions are rare.
Related¶
- concepts/consistent-hashing — the replacement.
- concepts/hash-sharding — the production family; almost always uses consistent hashing under the hood.
- concepts/horizontal-sharding — the broader problem.
- concepts/thundering-herd — the origin-overload failure mode on mass cache miss.