Skip to main content
Definition Website Computer and Technology

Consistent Hashing

Subject: Computer and Technology noun /kənˈsɪs.tənt ˈhæʃ.ɪŋ/ 1 definition

  1. Definition (noun)

    Entry #72 · Updated

    Consistent 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 count N invalidates nearly every key placement, adding or removing a node under consistent hashing relocates only the keys in the adjacent ring segment—roughly 1 / N of 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 N sequentially indexed buckets (0 through N - 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 / 9 of the dataset) migrate from adjacent ring segments, keeping nearly 89% of cached entries warm on their existing nodes.