Skip to content

Consistent Hashing Strategy

1. Decision

Implement Consistent Hashing to partition data and route traffic across dynamic distributed nodes (caching clusters, database shards, load balancers), minimizing key re-mapping to \(K/N\) keys when nodes are added or removed from the system.

2. 30-Second Answer

Traditional modulo hashing (hash(key) mod N) breaks catastrophically in dynamic distributed systems: adding or removing a single node changes \(N\), causing nearly 100% of keys to rehash to different nodes, wiping out caches and triggering database thundering herds. Consistent Hashing maps both keys and server nodes to a logical \(2^{32}\) circular hash space (Hash Ring). A key is routed to the first server node encountered moving clockwise around the ring. When a server node is added or removed, only \(K/N\) keys are remapped (where \(K\) is total keys and \(N\) is total nodes), while all other key assignments remain completely unchanged. Using Virtual Nodes (Vnodes) prevents uneven key distribution and traffic hotspotting across physical hardware nodes.

3. Decision Matrix

Option Best For Avoid When Latency Scalability Consistency Operational Complexity
Traditional Modulo Hashing (hash % N) Static arrays, fixed multi-threading within a single process Dynamic multi-node clusters where nodes join, leave, or fail frequently Sub-microsecond (Simple modulo math) Extremely Poor (Adding 1 node invalidates ~100% of key mappings) Deterministic static mapping Very Low
Consistent Hashing with Virtual Nodes (Vnodes) Distributed caches (Memcached Ketama, Redis Cluster), distributed databases (Cassandra, DynamoDB), load balancers Small static 2-node setups with zero node churn Low (\(O(\log N)\) binary search lookup on ring) Extremely High (Linear dynamic node addition/removal with minimal key movement) Minimizes cache miss waves & data migration overhead Medium (Ring management, Vnode tuning)

4. Selection Rules

Requirement Best Choice Rationale / Example
Dynamic Cache Node Cluster (Memcached / Redis) Consistent Hashing (Ketama) Adding a 10th cache node invalidates only 10% of cache keys instead of 100%
Masterless Distributed NoSQL (Cassandra / DynamoDB) Consistent Hashing + Vnodes Nodes own ranges on the ring; data partitions automatically rebalance on node failure
Prevent Uneven Load / Hotspotting on Ring Virtual Nodes (Vnodes = 100-250) Assign 150 virtual ring points per physical server to smooth key distribution
Consistent API Gateway Request Routing Consistent Hashing Route requests by user_id to the same backend container for local state affinity
Replicate Data to Clockwise Successors Consistent Hashing Ring Store primary key on Node A, and replicate to next \(N-1\) clockwise successor nodes

5. Tradeoffs

  1. Minimal Key Re-mapping vs Ring Binary Search Lookup
  2. Gain: Adding/removing a node only moves \(\frac{1}{N}\) of the dataset.
  3. Lose: Lookup requires \(O(\log V)\) binary search over sorted Virtual Node array vs \(O(1)\) direct modulo math.
  4. Virtual Nodes (Vnodes) Uniformity vs Ring Memory Footprint
  5. Gain: Higher Vnode count (e.g., 256 Vnodes/physical node) eliminates non-uniform key distribution hotspots.
  6. Lose: Consumes memory storing larger Vnode ring arrays on routers/clients.
  7. Graceful Node Scale-Out vs Heterogeneous Hardware Capacity
  8. Gain: Powerful physical servers can be assigned more Vnodes to handle proportionally higher traffic.
  9. Lose: Misconfiguring Vnode counts causes hardware utilization imbalance.
  10. Ring Partition Ownership vs Anti-Entropy Synchronization
  11. Gain: Node failure only affects the immediate adjacent ring range.
  12. Lose: Surrounding nodes must fetch missed data ranges via background anti-entropy repairs (Merkle trees).

6. Interview Counter Questions

  1. How does the Logical Hash Ring (\(2^{32}-1\)) work in Consistent Hashing?
  2. What is the mathematical problem with traditional hash(key) mod N when \(N\) changes?
  3. What are Virtual Nodes (Vnodes) and why are they necessary in Consistent Hashing?
  4. How many Virtual Nodes per physical node should be configured in production (e.g. Cassandra)?
  5. How does Consistent Hashing handle Data Replication across nodes (Clockwise Successor rule)?
  6. What is the Libmemcached Ketama algorithm and how does it implement Consistent Hashing?
  7. How does a client or router locate which node owns a key on the Hash Ring?
  8. How does Cassandra use Merkle Trees and Anti-Entropy repair when a node on the Hash Ring recovers from a failure?
  9. What happens when a physical node with 200 Vnodes crashes? How is the load redistributed?
  10. How does Consistent Hashing compare to Rendezvous Hashing (Highest Random Weight / HRW)?

7. Gold Standard Answers

  1. Hash function (e.g., MD5/Murmur3) maps keys and server IDs to an integer range \([0, 2^{32}-1]\) represented as a circular ring. Keys are routed by finding the smallest server hash value \(\ge\) key hash value (clockwise).
  2. If \(N\) changes from 10 to 11, hash(key) mod 10 \(\neq\) hash(key) mod 11 for \(\approx 91\%\) of keys, triggering a massive cache wipeout and slamming the primary database.
  3. Without Vnodes, physical nodes map to single points on the ring, causing non-uniform key distribution (hotspots) and uneven load shedding when a node dies. Vnodes map multiple virtual points per physical node across the ring.
  4. Production systems (e.g., Cassandra) typically use 128 to 256 Vnodes per physical node to achieve \(<5\%\) variance in key distribution across physical servers.
  5. Store primary record on the first node encountered clockwise (N0). For replication factor \(RF=3\), replicate data to the next 2 distinct physical nodes encountered moving clockwise on the ring.
  6. Ketama hashes server IPs multiple times (server1-1, server1-2) into a 1024-entry array. Clients binary-search the array to route key requests efficiently.
  7. Router/Client maintains a sorted array of Vnode hash positions. It hashes the key, performs a Binary Search (\(O(\log V)\)) to find the first Vnode \(\ge \text{hash}(\text{key})\), and routes to its physical node IP.
  8. When a node recovers, neighboring nodes compare Merkle Trees (hierarchical hash trees of data ranges). Only mismatched sub-branches are transferred over the network to resynchronize the node efficiently.
  9. Its 200 Vnodes are scattered evenly across the ring. When it dies, its load is distributed evenly across all remaining physical nodes in the cluster, avoiding overloading a single successor.
  10. Consistent Hashing uses a shared ring (\(O(\log N)\) lookup). Rendezvous Hashing computes \(W_{i} = \text{hash}(\text{key}, \text{node}_i)\) for all nodes and picks the node with highest weight (\(O(N)\) lookup, but uniform distribution without Vnodes).

8. Common Mistakes

  • Implementing Consistent Hashing without Virtual Nodes, leading to severe key distribution hotspots and imbalanced hardware utilization.
  • Using simple modulo hashing (key % N) for distributed caching clusters where nodes auto-scale or fail.
  • Allocating too few Virtual Nodes (<10 Vnodes), causing high load variance across physical servers.
  • Using cryptographically heavy slow hash functions (like bcrypt/PBKDF2) instead of fast non-cryptographic hashes (MurmurHash3, FNV-1a, xxHash) for ring positioning.
  • Forgetting to filter out duplicate physical nodes when picking clockwise successor nodes for data replication.

9. Keywords

Consistent Hashing, Hash Ring, Virtual Nodes, Vnodes, Modulo Hashing, Ketama, MurmurHash3, Clockwise Successor, Merkle Trees, Anti-Entropy, Rendezvous Hashing, HRW, Replication Factor, Load Variance.

10. Cheat Sheet

  • Core Metric: Adding/removing a node in Consistent Hashing remaps only \(\frac{K}{N}\) keys (where \(K\)=keys, \(N\)=nodes). Modulo hashing remaps ~100% of keys.
  • Ring Structure: Keys and Nodes are hashed onto a circular \(2^{32}-1\) integer ring. Keys route to first node encountered clockwise.
  • Virtual Nodes (Vnodes): Map 128–256 virtual ring points per physical node. Eliminates hotspots and distributes failed node traffic evenly across ALL cluster nodes.
  • Hash Functions: Use fast non-cryptographic hashes: MurmurHash3, xxHash, or FNV-1a. Never use bcrypt or SHA-256 for ring routing!
  • Replication Rule: Replicate keys to the next \(RF-1\) distinct physical nodes encountered moving clockwise on the ring.
  • Lookup Complexity: \(O(\log V)\) binary search over sorted Vnode array.

11. Related Decisions