mufassall

Шпаргалка · Данные и хранение

Консистентное хеширование

12 мин · Средний · mufassall.dtwin.uz/ru/l/consistent-hashing/

← Открыть урок

Проблема

API профилей держит горячие данные в трёх кеш-серверах. Четвёртый должен был помочь, но с `hash % N` он опустошает почти весь кеш. Как хеш-кольцо переносит только четверть ключей и зачем ему виртуальные узлы.

Чему вы научитесь

  • Почему при hash % N смена N переносит почти каждый ключ
  • Как хеш-кольцо выбирает узел: следующая точка по часовой стрелке
  • Почему при добавлении или уходе узла переезжает лишь ~1/N ключей
  • Что чинят виртуальные узлы: неравные дуги и нагрузку упавшего узла
Итоговая сцена
66%44%67%66%

Диаграмма как код

Итоговая схема урока в виде текста: вставьте её в 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 down

Mermaid: последовательность запросов

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

D2

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_d

PlantUML: последовательность запросов

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

PlantUML: компоненты

@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%

Шаги

  1. Кейс Три кеша, одно правило: hash % 3

    API отдаёт около 5 000 профилей в секунду.

  2. Проблема Четвёртый кеш опустошает остальные три

    Памяти мало, добавили четвёртый кеш, и правило стало hash % 4.

  3. Проблема Каждый промах падает на базу

    Hit rate упал с 95% до 24%.

  4. Решение Ключи и узлы на одном кольце

    Откатываемся к трём кешам и меняем правило.

  5. Решение Новый узел забирает только одну дугу

    Кеш D встаёт в точку 0x4CC00000.

  6. Проблема Четыре точки режут кольцо на неравные дуги

    Когда у кеша одна точка, дуги так же случайны, как хеши.

  7. Решение Виртуальные узлы: много маленьких точек на кеш

    Теперь каждый кеш получает 128 точек на кольце (cache-a#0 … cache-a#127), у каждой свой хеш.

  8. Кейс Когда кеш падает, его ключи расходятся

    Кеш B перестал отвечать, и API убрал его с кольца.

  9. Итоги Итог

    hash % N хорош, пока N не меняется.

Термины

Консистентное хеширование
Узлы и ключи размещают на одном кольце, ключ принадлежит следующему узлу по часовой стрелке. При добавлении или уходе узла переезжает лишь ~1/N ключей, а виртуальные узлы выравнивают нагрузку.