Consistent Hashing
Subject: Computer and Technology noun /kənˈsɪs.tənt ˈhæʃ.ɪŋ/ 1 definition
- distributed-systems
- key-value-storage
- high-availability
- system-architecture
-
Definition (noun)
Entry #72 · UpdatedConsistent Hashing is a distributed partitioning and routing technique that maps both data keys and cluster nodes onto a shared circular identifier space—commonly called a hash ring—using a deterministic hash function. Each key is assigned to the first node encountered when moving clockwise from the key's hash position around the ring, wrapping from the maximum hash value back to zero. Unlike naive modulo hashing (
hash(key) % N), where changing the node countNinvalidates nearly every key placement, adding or removing a node under consistent hashing relocates only the keys in the adjacent ring segment—roughly1 / Nof the total keyspace on average—preserving cache locality and minimizing rebalancing overhead across elastic clusters, while requiring supplemental balancing techniques when clusters are small or server capacities differ.Common Forms
Basic Ring Hashing: Places each physical node at a single position on a circular hash space and routes every key to the next node clockwise, delivering O(log N) lookup via binary search while remaining prone to uneven load distribution in small clusters.
Virtual-Node (Vnode) Hashing: Maps each physical server to dozens or hundreds of distinct token positions around the ring—and optionally weights token counts by hardware capacity—to smooth key-distribution skew and spread failover traffic evenly across surviving nodes.
Bounded-Load Consistent Hashing: Caps each node at a configurable factor above the average cluster load and advances clockwise past saturated nodes during lookup, protecting individual servers from hot-key overload under skewed traffic.
Jump Consistent Hash: Maps 64-bit keys to
Nsequentially indexed buckets (0throughN - 1) in O(ln N) time with zero stored ring state by jumping bucket indices via a seeded pseudorandom generator, trading arbitrary middle-node removal for uniform balance and minimal memory overhead.
Example
A distributed Memcached tier partitions 1.2 million user-session records across eight servers arranged on a 32-bit consistent hash ring with 150 virtual nodes per host. When a ninth server joins the cluster to handle peak traffic, only about 133,000 keys (roughly
1 / 9of the dataset) migrate from adjacent ring segments, keeping nearly 89% of cached entries warm on their existing nodes.