CSE Roadmap

Core tier · about 3 hours · 8 parts

Part 1 of 8 · 1 min read

Why this page comes now

In this module you will

  • Show why hash mod N reshuffles most keys when a server is added or removed.
  • Place servers and keys on a hash ring and find the server for a key by walking clockwise.
  • Find which keys move when a server joins or leaves.
  • Explain virtual nodes: the two problems they solve, and the cost of using many.
  • Place replicas on the ring, and say where consistent hashing is used and its limits.

Modules 4 and 5 chose partitions by key ranges or hash ranges, and showed that hash mod N moves too much data. Consistent hashing is the classic cure and shows up everywhere in design interviews: caches, databases, load balancers and chat servers. The tier is Core. The numbers are made up to show the idea, unless the text names a book.