Consistent Hashing — Simple

Problem statement (interviewer prompt)

Design a key-distribution scheme that maps keys to N storage nodes such that adding or removing one node moves only ~K/N keys. Support weighted nodes, replication to neighbours, and handle heterogeneous hardware.

Hash both keys and servers onto a ring; each key is owned by the next server clockwise. Adding/removing 1 server moves only K/N keys.

flowchart LR
  K1[key A]
  K2[key B]
  K3[key C]
  K4[key D]
  N1((Node 1))
  N2((Node 2))
  N3((Node 3))
  K1 --> N1
  K2 --> N2
  K3 --> N3
  K4 --> N1

    classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
    classDef edge fill:#cffafe,stroke:#0e7490,stroke-width:1px,color:#0f172a;
    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
    classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
    classDef queue fill:#ede9fe,stroke:#5b21b6,stroke-width:1px,color:#0f172a;
    classDef compute fill:#d1fae5,stroke:#065f46,stroke-width:1px,color:#0f172a;
    classDef storage fill:#e5e7eb,stroke:#374151,stroke-width:1px,color:#0f172a;
    classDef external fill:#fce7f3,stroke:#9d174d,stroke-width:1px,color:#0f172a;
    classDef obs fill:#f3e8ff,stroke:#6b21a8,stroke-width:1px,color:#0f172a;
    class K1,K2,K3,K4 service;
    class N1,N2,N3 queue;