Art of Codeartofcode
Lesson 14 of 15

28. Consistent Hashing

1
The picture to keep in your head
2
28.1 What's the problem with mod N?
3
28.2 What is the hash ring?
4
28.3 How do you find a key's server?
5
28.4 What happens when you add or remove servers?
6
28.5 What are virtual nodes?
7
28.6 How does replication work on the ring?
8
28.7 Where is consistent hashing used?
9
28.8 What is rendezvous hashing, in brief?
10
Memory card and where the analogy breaks
11
Practice: five levels
12
Interview questions
13
Solutions
14
Sources
15
Code lab
28. Consistent Hashing

Sources

3 min read+10 XP

Source notes

  • Consistent hashing: David Karger et al., "Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web", STOC 1997.
  • Dynamo's ring, virtual nodes, preference lists and hinted handoff: Giuseppe DeCandia et al., "Dynamo: Amazon's Highly Available Key-value Store", SOSP 2007. Cassandra tokens and virtual nodes: Apache Cassandra documentation.
  • Rendezvous (highest random weight) hashing: David Thaler and Chinya Ravishankar, "Using Name-Based Mappings to Increase Hit Rates", IEEE/ACM Transactions on Networking, 1998.
  • Jump consistent hash: John Lamping and Eric Veach, "A Fast, Minimal Memory, Consistent Hash Algorithm", 2014.
  • Maglev: Daniel E. Eisenbud et al., "Maglev: A Fast and Reliable Software Network Load Balancer", NSDI 2016. Envoy load-balancing policies (ring hash, Maglev): Envoy documentation.
  • Redis Cluster's 16,384 hash slots: Redis Cluster specification (see Chapter 13).
  • Page counts, server sizes and request rates are illustrative assumptions; arithmetic computed 2026-10-08.
  • Level 3 and Level 4 code: tested 2026-10-08 (code/ch28_consistent_hashing.py, all checks pass).