Consistent Hashing¶

By mapping both keys and nodes to positions on a ring (hash space), data can be distributed across nodes such that adding or removing nodes only requires remapping keys from/to adjacent positions, minimizing redistribution during scaling.

Tension Addressed¶

Consistency vs. Availability (enables rebalancing with minimal disruption during node changes)

Recognizable As¶

Hash rings; virtual nodes; token ranges; "rebalancing" operations; consistent routing in caches, load balancers, and databases

Canonical Sources¶

Karger et al., "Consistent Hashing and Random Trees" (1997); DeCandia et al., "Dynamo" (2007)

Transfers To¶

Caching (distributed cache routing), Load Balancing (sticky sessions), Database Sharding (partition assignment), Content Delivery (request routing)

Traditional modulo-based hashing (key mod N) requires remapping nearly all keys when N changes. Consistent hashing limits disruption to 1/N of keys on average. This enables elastic scaling without massive data movement.

Sub-concepts: - Virtual Nodes: Multiple positions per physical node for better distribution and incremental capacity adjustment