mufassall

Cheat sheet · Data & storage

Consistent hashing

12 min · Intermediate · mufassall.dtwin.uz/en/l/consistent-hashing/

← Open the lesson

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 % N remaps 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
Final scene
66%44%67%66%

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 down

Mermaid: 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: PING

D2

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_d

PlantUML: 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
@enduml

PlantUML: 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
@enduml

Recap

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

MetricStartEnd
Cache hit rate95%72%
DB reads250/s1 400/s
Keys moved0%25%

Steps

  1. Case Three caches, one rule: hash % 3

    The API serves about 5 000 profile reads a second.

  2. Problem A fourth cache empties the other three

    Memory is tight, so a fourth cache is added and the rule becomes hash % 4.

  3. Problem Every miss lands on the database

    The hit rate fell from 95% to 24%.

  4. Fix Put keys and nodes on one ring

    Roll back to three caches and change the rule.

  5. Fix Now a new node takes only one arc

    Cache D is added at point 0x4CC00000.

  6. Problem Four points cut the ring into unequal arcs

    With only one point per cache, the arcs are as random as the hashes.

  7. 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.

  8. Case When a cache dies, its keys spread out

    Cache B stops answering and the API removes it from the ring.

  9. Recap Recap

    hash % N is 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.