Consistent hashing is a distribution technique that maps both data keys and storage nodes onto the same circular hash space, so that each key is assigned to the next node encountered clockwise on the ring. When a node joins or leaves, only the keys in its immediate neighbourhood are remapped rather than the entire key space, minimising data movement. Virtual nodes are commonly used to smooth load distribution across heterogeneous servers.
Overview
- Consistent hashing solves the rehashing problem of naive modulo-based partitioning, where changing the number of nodes forces almost every key to move. By placing nodes and keys on a shared ring, the scheme localises disruption to the segment adjacent to the changed node. It underpins distributed caches, key-value stores, and peer-to-peer overlays.
Mechanisms
- Keys and nodes are hashed onto a fixed-size circular identifier space
- Each key is owned by the first node clockwise from its position on the ring
- Node addition or removal remaps only O(keys/nodes) keys on average
- Virtual nodes assign multiple ring positions per physical node to balance load
- Replication is achieved by walking to the next several distinct nodes on the ring
Applications
- Partitioning data across distributed key-value stores and databases
- Routing requests in distributed caches such as content delivery layers
- Locating data in peer-to-peer distributed hash tables
- Sharding stateful services while keeping rebalancing cheap