Problem
Hash-based partitioning (`hash % N`) remaps almost all keys when N changes. Consistent hashing moves only K/N keys.
scalingestablished · low operational burden
Consistent Hashing
Also known as: consistent-hash, hash-ring, ketama, rendezvous-hashing
Intent
Distribute keys across nodes with minimal reshuffling when nodes join/leave, using a hash ring with virtual nodes.
Forces
- •Minimal disruption: node add/remove affects few keys
- •Uniform distribution: keys spread evenly across nodes
- •Deterministic: same key always maps to same node (given ring state)
- •Scalable: O(log N) lookup, O(1) with virtual nodes
Solution
✓ When to Use
- •Dynamic node membership (add/remove nodes)
- •Distributed cache or sharding
- •Minimal reshuffle on scaling
✗ When Not to Use
- •Static cluster (simple hash % N fine)
- •Small N (<5) where distribution skew matters
- •Team not ready for hash ring debugging
Pros
- +Minimal reshuffle: O(K/N) keys move on node change
- +Uniform: vnodes distribute evenly
- +Deterministic: no central coordinator for routing
- +Scalable: O(log N) lookup
Cons
- −Hot keys: single key overloads one node
- −Small cluster skew: vnodes mitigate but not eliminate
- −Implementation complexity: ring, vnodes, binary search
- −No query locality: related keys not co-located
Cost Profile
Infrastructure
None — algorithm
Operational
Low — monitor distribution
Cognitive
Medium — ring, vnodes, replication
Failure Modes
Hot key: single key → one node overwhelmed
Node failure: keys redistributed, temporary load spike
Skew: poor hash function or too few vnodes
Replication lag: replica not caught up on failover
Real-World Examples
Alternatives
- hash-modulo
- range-partitioning
- directory-based
- rendezvous-hashing
Related Patterns
- partitioning-strategies
- sharding
- distributed-cache
- load-balancing
- dynamodb
- cassandra
Competency Domains
scalingdata statereliability opsdistribution communicationeconomics evolution