Consistent hashing is a distributed hashing scheme that uses hash rings to assign keys to servers such that only a few keys need to be remapped when servers are added or removed. This enables caching and scaling with minimal turnover.
Hash rings map keys and servers around a circular space. Servers are assigned ranges based on their hashes. Keys are assigned to the nearest server clockwise from their hash location.
When servers are scaled in/out, only keys near the change points need rebalancing. Contrast with standard hashing where all keys remap randomly, causing mass cache turnover.
Consistent hashing requires balanced, randomized hashes. Algorithms like rendezvous hashing improve on basic consistent hashing. Fast non-crypto hashes like xxHash, MurmurHash and FNV are commonly used.
With consistent hashing, servers and keys map to the same hash space. Keys are assigned to the nearest server clockwise on the ring.
When servers are added/removed, only keys near the change points get remapped. Most keys remain assigned to their original server.
Virtual replicas improve the distribution. Hashing algorithms like MD5, SHA-1 are used.
Consistent hashing enables scaling, load balancing and high availability for distributed data systems. Only minimal remapping is needed when the server pool changes.
Use cases include distributed caches, databases, cloud storage systems and content delivery networks like Akamai that require scalability.
It minimizes key turnover when servers are added or removed compared to naive hash assignment. This is critical for distributed data systems.
It provides a hash distribution algorithm that reduces cache invalidation and rebalancing when scaling up servers and handling failures.
xxHash is an extremely fast non-cryptographic hash algorithm focused on speed and efficiency for checksums and hash tables.
Read more ->MurmurHash is a series of fast non-cryptographic hash functions optimized for hash tables and CPU cache performance.
Read more ->The FNV hash is a fast, simple non-cryptographic hash function that uses modular arithmetic operations to achieve good distribution.
Read more ->
.svg)