Skip to content
Tutorials Center
My learning

Topics

Lesson 15 of 65 ยท Load Balancing and Traffic

Consistent Hashing

Learn how consistent hashing places keys and servers on a ring so adding or removing nodes moves few keys, with virtual nodes and a Python implementation.

Many systems must split a large set of keys across a group of servers: cache nodes, database shards, file stores. The usual need is the same: given a key, find its server quickly and the same way from every client. The obvious tool is hash(key) % number_of_servers, but as the previous lesson showed, it fails badly when the number of servers changes. Going from 4 to 5 servers remaps about 80% of keys.

Consistent hashing is the technique that fixes this. When a server joins or leaves, only about 1/N of the keys move, where N is the number of servers. It is used in distributed caches, databases like Cassandra and DynamoDB, CDNs and many load balancers.

The hash ring

Imagine the output range of a hash function as a circle, say from 0 up to 2^32 - 1, where the largest value wraps around to 0.

  1. Place servers on the ring: hash each server's name (or ID) to get a position.
  2. Place keys on the ring: hash each key the same way.
  3. Assign each key to a server: walk clockwise from the key's position and pick the first server you meet.
flowchart LR
  subgraph Ring["Hash ring (clockwise)"]
    direction LR
    K1["key a"] --> SA["Server A"]
    K2["key b"] --> SB["Server B"]
    K3["key c"] --> SB
    K4["key d"] --> SC["Server C"]
  end

Figure: each key belongs to the next server clockwise from its position.

Now see what happens when the cast changes:

  • A server is added: it takes over only the keys between its position and the previous server counterclockwise. Everything else stays.
  • A server is removed (or fails): only its keys move, to the next server clockwise. Others are untouched.

On average only K/N of K keys move, instead of nearly all of them.

Consistent hashing in four steps

A ring Hash values wrap from the top back to zero.
Hash the servers Each server sits at a point on the ring.
Hash the keys Walk clockwise to the first server.
Change the pool Only nearby keys move.

Most keys stay put when nodes come and go.

1 / 2

A first implementation

To find "the first server clockwise" quickly, keep the server positions in a sorted list and use binary search on the key's hash. If the search passes the end of the list, wrap around to the first server.

Python A basic 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.

Compared with the 80% of keys moved by modulo hashing, far fewer keys move here. But look at the second printed line: the distribution is uneven. With only a handful of random points on the ring, one server may own a big arc and another a tiny one. That leads to the next idea.

Virtual nodes

A server hashed to one spot gets a random-sized slice of the ring, sometimes much too large. The fix is virtual nodes (vnodes): place each physical server on the ring many times, under names like server-A#0, server-A#1, ..., server-A#199. Each server now owns many small slices scattered around the ring, and by the law of large numbers the totals become nearly equal.

Virtual nodes also let you weight servers: give a strong machine 300 vnodes and a weak one 100 so it owns three times the keys. And when a server fails, its many small slices are taken over by many different neighbors, so no single server inherits the whole load.

Python Virtual nodes even out the load

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.

As vnodes grow, the relative spread shrinks, so the servers carry nearly equal shares. And when C fails, only C's own keys move, spread across the surviving servers rather than dumped on one neighbor.

Replication on the ring

Databases such as Cassandra and Dynamo-style stores also use the ring to place replicas: a key is stored on the first server clockwise and the next N-1 distinct servers after it. If the first is down, the others still have the data. With virtual nodes you must skip vnodes that belong to a physical server already chosen, so replicas land on different machines (ideally different racks or zones).

  • Rendezvous (highest random weight) hashing: for each key compute a score for every server and choose the highest. It also moves only 1/N keys on changes, needs no ring, and is easy to weight, but costs O(N) per lookup.
  • Jump consistent hash: a tiny, fast algorithm that maps keys to buckets numbered 0 to N-1 with minimal movement, great when servers only grow or shrink at the end.
  • Maglev hashing: used by large load balancers; builds a lookup table for very fast, even assignment.
Python Rendezvous hashing

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.

Where you will see it

  • Distributed caches: a client library maps keys to cache nodes with a ring so adding a cache node does not empty the cache (distributed caches).
  • Sharded databases and key-value stores: assigning partitions to nodes.
  • Load balancing with affinity: send a user or a video to the same backend for cache locality.
  • CDNs: choosing which edge server holds which object.

Limits to remember: the ring tells you where data should be, but not whether the node is alive (you still need health checks), and hot keys (one extremely popular key) overload their owner no matter how well the ring is balanced. Hot keys need replication or local caching.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What is the main advantage of consistent hashing over hash(key) % N?

    Most keys keep their owner when the node set changes, so caches stay warm.
  2. 2. On a hash ring, which server owns a key?

    Servers and keys share one ring; ownership goes to the next server clockwise, wrapping around.
  3. 3. Why use virtual nodes?

    Many scattered points per server average out arc sizes and share failover load.
  4. 4. How do you find the owner quickly in the implementation?

    Sorted positions plus bisect give O(log n) lookups, with wrap-around at the end.
  5. 5. A single extremely popular key still overloads one node. Which fix helps?

    The ring balances keys, not traffic per key; hot keys need replication or caching.

Summary

  • Consistent hashing places servers and keys on a ring; each key belongs to the next server clockwise.
  • Adding or removing a node moves only about 1/N of the keys, unlike modulo hashing.
  • Virtual nodes smooth the distribution, allow weights and spread a failed node's load.
  • Lookups use a sorted list and binary search; replicas go on the next distinct servers.
  • Alternatives include rendezvous, jump consistent hash and Maglev; hot keys need separate handling.

Next: Health Checks and Failover