Шпаргалка · Данные и хранение
Консистентное хеширование
Проблема
API профилей держит горячие данные в трёх кеш-серверах. Четвёртый должен был помочь, но с `hash % N` он опустошает почти весь кеш. Как хеш-кольцо переносит только четверть ключей и зачем ему виртуальные узлы.
Чему вы научитесь
- Почему при
hash % Nсмена N переносит почти каждый ключ - Как хеш-кольцо выбирает узел: следующая точка по часовой стрелке
- Почему при добавлении или уходе узла переезжает лишь ~1/N ключей
- Что чинят виртуальные узлы: неравные дуги и нагрузку упавшего узла
Диаграмма как код
Итоговая схема урока в виде текста: вставьте её в Jira, GitLab, GitHub, Notion или документацию, там Mermaid рисуется сам. Есть варианты для D2 и PlantUML (Confluence, IntelliJ).
Mermaid: схема
flowchart LR
n_client(["Приложение"])
n_api["API профилей"]
n_cache_a{{"Кеш A"}}
n_cache_b{{"Кеш B"}}
n_cache_c{{"Кеш C"}}
n_db[("База пользователей")]
n_cache_d{{"Кеш D"}}
n_client --> n_api
n_api --> n_cache_a
n_api --x|"потеряно"| 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: последовательность запросов
sequenceDiagram
participant n_api as API профилей
participant n_cache_b as Кеш B
participant n_cache_d as Кеш D
participant n_db as База пользователей
participant n_cache_c as Кеш C
Note over n_api,n_cache_b: Три кеша, одно правило: 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: Четвёртый кеш опустошает остальные три
n_api->>n_cache_d: GET user:u_42
n_cache_d-->>n_api: (nil)
Note over n_api,n_db: Каждый промах падает на базу
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: Ключи и узлы на одном кольце
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: Новый узел забирает только одну дугу
n_api->>n_cache_d: INFO ring add cache-d at 0x4CC00000
Note over n_api,n_cache_c: Четыре точки режут кольцо на неравные дуги
n_api->>n_cache_c: INFO keyspace
n_cache_c-->>n_api: #35; Keyspace
Note over n_api,n_cache_c: Виртуальные узлы: много маленьких точек на кеш
n_api->>n_cache_c: INFO ring rebuilt: 4 nodes x 128 vnodes
Note over n_api,n_cache_b: Когда кеш падает, его ключи расходятся
n_api-xn_cache_b: PINGD2
direction: right
n_client: "Приложение" {
shape: rectangle
}
n_api: "API профилей" {
shape: rectangle
}
n_cache_a: "Кеш A" {
shape: hexagon
}
n_cache_b: "Кеш B" {
shape: hexagon
style.fill: "#fde2e2"
style.stroke: "#c62828"
style.stroke-dash: 3
}
n_cache_c: "Кеш C" {
shape: hexagon
}
n_db: "База пользователей" {
shape: cylinder
}
n_cache_d: "Кеш D" {
shape: hexagon
}
n_client -> n_api
n_api -> n_cache_a
n_api -> n_cache_b: "потеряно" {
target-arrowhead.shape: cross
}
n_api -> n_cache_c
n_api -> n_db
n_api -> n_cache_dPlantUML: последовательность запросов
@startuml
participant "API профилей" as n_api
collections "Кеш B" as n_cache_b
collections "Кеш D" as n_cache_d
database "База пользователей" as n_db
collections "Кеш C" as n_cache_c
note over n_api, n_cache_b : Три кеша, одно правило: 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 : Четвёртый кеш опустошает остальные три
n_api -> n_cache_d : GET user:u_42
n_cache_d --> n_api : (nil)
note over n_api, n_db : Каждый промах падает на базу
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 : Ключи и узлы на одном кольце
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 : Новый узел забирает только одну дугу
n_api -> n_cache_d : INFO ring add cache-d at 0x4CC00000
note over n_api, n_cache_c : Четыре точки режут кольцо на неравные дуги
n_api -> n_cache_c : INFO keyspace
n_cache_c --> n_api : # Keyspace
note over n_api, n_cache_c : Виртуальные узлы: много маленьких точек на кеш
n_api -> n_cache_c : INFO ring rebuilt: 4 nodes x 128 vnodes
note over n_api, n_cache_b : Когда кеш падает, его ключи расходятся
n_api ->x n_cache_b : [потеряно] PING
@endumlPlantUML: компоненты
@startuml
left to right direction
agent "Приложение" as n_client
component "API профилей" as n_api
stack "Кеш A" as n_cache_a
stack "Кеш B" as n_cache_b #fde2e2;line:c62828;line.dashed
stack "Кеш C" as n_cache_c
database "База пользователей" as n_db
stack "Кеш D" as n_cache_d
n_client --> n_api
n_api --> n_cache_a
n_api -[#c62828,dashed]-> n_cache_b : потеряно
n_api --> n_cache_c
n_api --> n_db
n_api --> n_cache_d
@endumlИтог
hash % N хорош, пока N не меняется. Сменили N — переехал почти каждый ключ.
1) Узлы и ключи кладутся на одно кольцо; ключ принадлежит следующему узлу по часовой стрелке. 2) Добавление или уход узла переносит только ~1/N ключей. 3) Дайте каждому узлу много виртуальных точек, чтобы выровнять дуги и нагрузку. 4) Все клиенты должны работать с одним и тем же списком узлов.
Показатели: в начале и в конце
| Показатель | В начале | В конце |
|---|---|---|
| Попадания в кеш | 95% | 72% |
| Чтения из базы | 250/с | 1 400/с |
| Переехало ключей | 0% | 25% |
Шаги
- Кейс Три кеша, одно правило:
hash % 3API отдаёт около 5 000 профилей в секунду.
- Проблема Четвёртый кеш опустошает остальные три
Памяти мало, добавили четвёртый кеш, и правило стало
hash % 4. - Проблема Каждый промах падает на базу
Hit rate упал с 95% до 24%.
- Решение Ключи и узлы на одном кольце
Откатываемся к трём кешам и меняем правило.
- Решение Новый узел забирает только одну дугу
Кеш D встаёт в точку
0x4CC00000. - Проблема Четыре точки режут кольцо на неравные дуги
Когда у кеша одна точка, дуги так же случайны, как хеши.
- Решение Виртуальные узлы: много маленьких точек на кеш
Теперь каждый кеш получает 128 точек на кольце (
cache-a#0…cache-a#127), у каждой свой хеш. - Кейс Когда кеш падает, его ключи расходятся
Кеш B перестал отвечать, и API убрал его с кольца.
- Итоги Итог
hash % Nхорош, пока N не меняется.
Термины
- Консистентное хеширование
- Узлы и ключи размещают на одном кольце, ключ принадлежит следующему узлу по часовой стрелке. При добавлении или уходе узла переезжает лишь ~1/N ключей, а виртуальные узлы выравнивают нагрузку.