Last Minute Notes
  • Github
  • Docs
  • Learn
    @sayanstwt
Lessons
0/37 done
  • SQL vs NoSQL
  • Indexes & Storage Engines
  • Replication
  • Sharding
  • Consistent Hashing
  • Object Storage & Uploads
  • Search & Inverted Indexes
Learn/System Design/Data & Storage

Consistent Hashing

8 min Intermediate 10 steps

Resize a fleet of servers and move only a small slice of the data.

Servers
4
Keys moved
-
Biggest share
33%fair 25%
server = hash(key) % 4A% 4 = 0B% 4 = 1C% 4 = 2D% 4 = 3
key owned arc moved key
In this lessonStep 1 of 10
  1. The problem
  2. The ring
  3. Keys
  4. Add a server
  5. Remove one
  6. Uneven
  7. Virtual nodes
  8. Replicas
  9. In practice
  10. Recap
Step 1 / 10problem

hash % N reshuffles everything

You run 4 cache servers. The obvious way to pick one is server = hash(key) % N. It spreads keys evenly and needs no lookup table.

Traffic grows, so you add a fifth server. N changes from 4 to 5, and almost every remainder changes with it. Watch how many keys land somewhere new.

Key idea

With mod-N, going from N to N+1 servers moves about N/(N+1) of all keys. For a cache that is a miss storm on the database. For a datastore it is a full migration.

←→ step·R replay·Space pause

You'll learn

  • Why hash % N breaks when the fleet resizes
  • How a key finds its server on the ring
  • Why a resize moves only about 1/N of keys
  • How virtual nodes fix lumpy load
  • Replication and where rings show up in practice
Read the full notesHLD Building Blocks, 10.3