Skip to content
Tutorials Center
My learning

Topics

Lesson 20 of 37 ยท Distributed Caching

Consistent Hashing and the Hash Ring

Learn why modulo hashing breaks a cache cluster when a server is added or lost, and how a consistent hash ring moves only a small share of keys. Runnable Python.

A single Memcached server has a hard limit: the RAM of one machine. When your working set no longer fits, you add more servers. But Memcached servers know nothing about each other. They never exchange data, never replicate and never forward requests. So the client library must decide which server owns each key. That decision is the heart of distributed caching, and getting it wrong can empty your whole cache the moment you add a node.

This lesson shows the naive approach, why it fails, and how a consistent hash ring fixes it. Everything runs as plain Python, so you can see the numbers yourself. The real Memcached servers are not part of the live editors; the code here is a stand-in that implements the same placement logic the real clients use.

The naive way: hash modulo N

The simplest rule is: hash the key to a number and take the remainder when dividing by the server count.

Python
server_index = hash(key) % number_of_servers

With three servers every key lands on server 0, 1 or 2, and the load is spread evenly. The trouble starts when the number of servers changes. If you go from 3 to 4 servers, the divisor changes, and almost every key now maps somewhere else. Your cache effectively starts cold, and the database receives the full read load at once.

Python Modulo hashing remaps most keys

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

In theory the ideal answer is that only the keys that belong to the new server should move, about one quarter when going from three to four. Modulo hashing moves around three quarters. Losing a node is just as bad.

The hash ring

A consistent hash ring places both servers and keys on the same circular number line, for example the range 0 to 2^32 - 1, where the largest value wraps back to zero.

  1. Hash every server name (for example cache1:11211) to a point on the circle.
  2. To find the owner of a key, hash the key to a point and walk clockwise until you hit the first server point. That server owns the key.

When a server is added, it takes over only the keys between its point and the previous server's point. When a server disappears, its keys flow to the next server clockwise. Every other key stays where it was.

flowchart LR
  K1["key: user:7"] --> S2["cache2 (next clockwise)"]
  K2["key: cart:3"] --> S3["cache3 (next clockwise)"]
  S1["cache1"] --- S2
  S2 --- S3
  S3 --- S1

Each key belongs to the first server found clockwise from its position on the ring. The line is drawn flat here; the real ring wraps around.

Looking up a key quickly

Store the server points in a sorted list. For a key, use binary search to find the first point greater than or equal to the key's hash; if you run past the end, wrap to index 0. Python's bisect module does exactly this.

Python A tiny consistent hash ring

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

You will see that far fewer keys move than with modulo, and that every moved key lands on the new server. That is the minimal disruption property.

Why one point per server is not enough

With only one point per server the arcs between points can be very different in length. A server that happens to own a long arc gets far more keys than the others, and the new node in the example above may take much more or much less than a quarter. The fix is virtual nodes, which the next lesson, Virtual Nodes and Load Balance, explains and measures.

What real clients do

Real Memcached client libraries implement this idea, usually under the name ketama (after the original library that popularised it). Typical behaviour:

  • Each server is hashed many times (often 100 to 200 points, weighted by server memory).
  • Points are built from md5 or murmur-style hashes of "host:port-index".
  • Clients configured with the same server list in the same order produce the same ring, so every web server agrees on where each key lives. If two app servers use different lists or different algorithms, they will read and write different servers and see misses for each other's data.

Keep the server list identical across all application servers, and change it in a coordinated way. A client that still sees the old list while others see the new one will make cache misses and, worse, can serve stale data (see Stale Data and Race Conditions).

A common mistake: relying on Python's hash()

Python's built-in hash() for strings is randomised per process. Two app servers would disagree on every key. Always use a stable hash such as MD5 or CRC32 for placement, as the examples above do. The hash only needs to be well mixed, not secure.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why does hash(key) % N cause trouble when a server is added?

    Changing N changes the remainder for most keys, so a large share of the cache becomes unreachable and the database takes the load.
  2. 2. On a hash ring, which server owns a key?

    Both keys and servers are hashed onto the circle, and the key belongs to the next server point clockwise, wrapping at the end.
  3. 3. When a node joins a consistent hash ring, which keys move?

    The new node takes over only the arc just before its point; every other key keeps its server.
  4. 4. Why should clients never use Python's built-in hash() to pick a server?

    Python randomises string hashes per process. Placement needs a stable hash like MD5 or CRC32.

Summary

  • Memcached servers are isolated; the client chooses the server for each key.
  • Modulo hashing remaps most keys when the server count changes.
  • A hash ring places servers and keys on a circle; the owner is the next server clockwise.
  • Adding or removing a node moves only the keys in its arc.
  • All clients must use the same stable hash and the same server list.

Next: Virtual Nodes and Load Balance