Cheat sheet · Data & storage
Consistent hashing
The problem
A profile API keeps hot data in three cache servers. Adding a fourth one should help, but with `hash % N` it empties almost the whole cache. How a hash ring moves only a quarter of the keys, and why it needs virtual nodes.
What you learn
- Why
hash % Nremaps almost every key when N changes - How a hash ring picks a node: the next point clockwise
- Why only about 1/N of the keys move when a node joins or leaves
- What virtual nodes fix: uneven arcs and a dead node's load
Diagram as code
The lesson's final design as text: paste it into Jira, GitLab, GitHub, Notion or your docs, where Mermaid renders by itself. There are D2 and PlantUML (Confluence, IntelliJ) versions too.
Mermaid: flowchart
flowchart LR
n_client(["App"])
n_api["Profile API"]
n_cache_a{{"Cache A"}}
n_cache_b{{"Cache B"}}
n_cache_c{{"Cache C"}}
n_db[("Users DB")]
n_cache_d{{"Cache D"}}
n_client --> n_api
n_api --> n_cache_a
n_api --x|"lost"| n_cache_b
n_api --> n_cache_c
n_api --> n_db
n_api --> n_cache_d
classDef down fill:#fde2e2,stroke:#c62828,color:#4a0d0d,stroke-dasharray:4 3
class n_cache_b downMermaid: request sequence
sequenceDiagram
participant n_api as Profile API
participant n_cache_b as Cache B
participant n_cache_d as Cache D
participant n_db as Users DB
participant n_cache_c as Cache C
Note over n_api,n_cache_b: Three caches, one rule: hash % 3
n_api->>n_cache_b: GET user:u_42
n_cache_b-->>n_api: #34;plan=pro#59;lang=uz#34;
Note over n_api,n_cache_d: A fourth cache empties the other three
n_api->>n_cache_d: GET user:u_42
n_cache_d-->>n_api: (nil)
Note over n_api,n_db: Every miss lands on the database
n_api->>n_db: SELECT plan, lang FROM users
n_db-->>n_api: pro #124; uz (1 row, 410 ms)
Note over n_api,n_cache_b: Put keys and nodes on one ring
n_api->>n_cache_b: DEBUG ring lookup user:u_42
n_cache_b-->>n_api: #34;plan=pro#59;lang=uz#34;
Note over n_api,n_cache_d: Now a new node takes only one arc
n_api->>n_cache_d: INFO ring add cache-d at 0x4CC00000
Note over n_api,n_cache_c: Four points cut the ring into unequal arcs
n_api->>n_cache_c: INFO keyspace
n_cache_c-->>n_api: #35; Keyspace
Note over n_api,n_cache_c: Virtual nodes: many small points per cache
n_api->>n_cache_c: INFO ring rebuilt: 4 nodes x 128 vnodes
Note over n_api,n_cache_b: When a cache dies, its keys spread out
n_api-xn_cache_b: PINGD2
direction: right
n_client: "App" {
shape: rectangle
}
n_api: "Profile API" {
shape: rectangle
}
n_cache_a: "Cache A" {
shape: hexagon
}
n_cache_b: "Cache B" {
shape: hexagon
style.fill: "#fde2e2"
style.stroke: "#c62828"
style.stroke-dash: 3
}
n_cache_c: "Cache C" {
shape: hexagon
}
n_db: "Users DB" {
shape: cylinder
}
n_cache_d: "Cache D" {
shape: hexagon
}
n_client -> n_api
n_api -> n_cache_a
n_api -> n_cache_b: "lost" {
target-arrowhead.shape: cross
}
n_api -> n_cache_c
n_api -> n_db
n_api -> n_cache_dPlantUML: request sequence
@startuml
participant "Profile API" as n_api
collections "Cache B" as n_cache_b
collections "Cache D" as n_cache_d
database "Users DB" as n_db
collections "Cache C" as n_cache_c
note over n_api, n_cache_b : Three caches, one rule: hash % 3
n_api -> n_cache_b : GET user:u_42
n_cache_b --> n_api : "plan=pro;lang=uz"
note over n_api, n_cache_d : A fourth cache empties the other three
n_api -> n_cache_d : GET user:u_42
n_cache_d --> n_api : (nil)
note over n_api, n_db : Every miss lands on the database
n_api -> n_db : SELECT plan, lang FROM users
n_db --> n_api : pro | uz (1 row, 410 ms)
note over n_api, n_cache_b : Put keys and nodes on one ring
n_api -> n_cache_b : DEBUG ring lookup user:u_42
n_cache_b --> n_api : "plan=pro;lang=uz"
note over n_api, n_cache_d : Now a new node takes only one arc
n_api -> n_cache_d : INFO ring add cache-d at 0x4CC00000
note over n_api, n_cache_c : Four points cut the ring into unequal arcs
n_api -> n_cache_c : INFO keyspace
n_cache_c --> n_api : # Keyspace
note over n_api, n_cache_c : Virtual nodes: many small points per cache
n_api -> n_cache_c : INFO ring rebuilt: 4 nodes x 128 vnodes
note over n_api, n_cache_b : When a cache dies, its keys spread out
n_api ->x n_cache_b : [lost] PING
@endumlPlantUML: components
@startuml
left to right direction
agent "App" as n_client
component "Profile API" as n_api
stack "Cache A" as n_cache_a
stack "Cache B" as n_cache_b #fde2e2;line:c62828;line.dashed
stack "Cache C" as n_cache_c
database "Users DB" as n_db
stack "Cache D" as n_cache_d
n_client --> n_api
n_api --> n_cache_a
n_api -[#c62828,dashed]-> n_cache_b : lost
n_api --> n_cache_c
n_api --> n_db
n_api --> n_cache_d
@endumlRecap
hash % N is fine while N never changes. Change N and almost every key moves.
1) Put nodes and keys on one ring; a key belongs to the next node clockwise. 2) A node joining or leaving moves only about 1/N of the keys. 3) Give every node many virtual points so arcs and load even out. 4) Every client must use the same node list.
Numbers: at the start and at the end
| Metric | Start | End |
|---|---|---|
| Cache hit rate | 95% | 72% |
| DB reads | 250/s | 1 400/s |
| Keys moved | 0% | 25% |
Steps
- Case Three caches, one rule:
hash % 3The API serves about 5 000 profile reads a second.
- Problem A fourth cache empties the other three
Memory is tight, so a fourth cache is added and the rule becomes
hash % 4. - Problem Every miss lands on the database
The hit rate fell from 95% to 24%.
- Fix Put keys and nodes on one ring
Roll back to three caches and change the rule.
- Fix Now a new node takes only one arc
Cache D is added at point
0x4CC00000. - Problem Four points cut the ring into unequal arcs
With only one point per cache, the arcs are as random as the hashes.
- Fix Virtual nodes: many small points per cache
Each cache now gets 128 points on the ring (
cache-a#0…cache-a#127), each from its own hash. - Case When a cache dies, its keys spread out
Cache B stops answering and the API removes it from the ring.
- Recap Recap
hash % Nis fine while N never changes.
Terms
- Consistent hashing
- Nodes and keys sit on one ring, and a key belongs to the next node clockwise. When a node joins or leaves only about 1/N of the keys move; virtual nodes even out the load.