Skip to content
Back to System DesignAll lessons

System Design

Consistent Hashing

O(n) to build the ring (n = number of servers) · O(n) per lookup in this simple version (real systems use a sorted structure for O(log n) lookups). The big win here is not speed. It's that scaling the cluster only moves a small slice of keys.

The idea, in plain English

Picture seats arranged in a big circle. Each server gets a seat on the circle. Each piece of data (a 'key') gets a seat too. To find which server owns a piece of data, start at the key's spot. Walk clockwise until you reach the first server seat. Here's the clever part: if you add or remove a server, only the keys near that one seat need to move. Everyone else stays exactly where they were.

How it works

  1. 1Turn each server's name into a number — a position on the circle — using a hash function.
  2. 2Sort the servers by position. They now form a ring around the circle.
  3. 3For any key, hash it to a position too. Walk clockwise to find the first server at or after that position. That server owns the key. If you reach the end of the circle, wrap back to the first server.

When you'd use it

Use this when you spread data or traffic across many servers, and you want adding or removing a server to be cheap. A distributed cache — like a Redis or Memcached cluster — is a good example: you don't want to reshuffle almost everything each time you scale up or down.

Common beginner mistakes

  • Using a hash function that is too weak. Then server names cluster together on the ring instead of spreading out, and most keys pile onto just one server.
  • Forgetting to wrap around the circle. If a key's position is past every server, it belongs to the very first server — not nowhere.

Try it — edit and run

Click the code to edit · press ⌘/Ctrl+↵ to run

Editable code. Tab and Shift+Tab indent. Press Escape, then Tab, to move focus out of the editor.

Expected output — hit Run to try it
Ring: borealis@129, delta@162, atlas@173, cascade@348
alice -> delta
bob -> cascade
carol -> atlas
dave -> borealis
erin -> borealis
frank -> atlas
Added vale. Ring: vale@64, borealis@129, delta@162, atlas@173, cascade@348
alice -> delta
bob -> cascade
carol -> atlas
dave -> vale
erin -> borealis
frank -> atlas
Keys that moved: 1 out of 6

Not sure this is the right topic? See the learning paths → or where this leads →