Сегодня тема, с которой можно столкнуться в суровых highload-проектах или на сисдиз-интервью. На практике я с таким не работала, но для сисдиза разбиралась в теме и решила сделать пост.
Consistent Hashing — это подход, который минимизирует количество переназначений ключей при изменении числа узлов в распределённой системе.
Он используется в распределенных базах данных и распределенных кэшах, чтобы определить, на какой узел положить объект по ключу. Может использоваться в балансировщиках, когда нужна sticky session, вместо обычного хэширования.
👀 Какую проблему решаем
Возьмем балансировщик нагрузки. Допустим, мы хотим поддержать sticky session, то есть направлять запросы пользователя на тот же сервер бэкенда, куда он попал в первый раз.
У нас есть 4 инстанса бэкенд-сервера. Для получения инстанса, на который нужно направить пользователя, определяем хэш от ip-адреса пользователя и берем остаток от деления на 4:
hash("ip-user123") % 4 = 0 -> user123 отправится на узел 0
hash("ip-user456") % 4 = 2 -> user456 отправится на узел 2
...Нагрузка растет, мы решаем добавить 5-й инстанс. Но теперь если мы используем тот же алгоритм, то все привязки сломаются, так как остаток от деления будет не на 4, а на 5:
hash("ip-user123") % 5 = 3 -> user123 теперь отправится на узел 3
hash("ip-user456") % 5 = 4 -> user456 теперь отправится на узел 4Consistent Hashing — это способ распределения данных по множеству узлов, при котором в случае добавления или удаления узлов будет переноситься минимальное количество данных.
⌛ Как устроен Consistent Hashing
Представьте кольцо, как циферблат часов.
Есть некая хэш-функция, которая выдает результат в диапазоне 0 до 2³²–1. Такой диапазон используется в реальных системах, но мы возьмем для упрощения диапазон значений кольца от 0 до 59.
Каждый узел (инстанс бэкенда, шард БД, кэш-сервер) размещаем на кольце (также с помощью хэширования). Например:
Node-1: hash = 0
Node-2: hash = 15
Node-3: hash = 30
Node-4: hash = 45
Чтобы определить узел для размещения конкретного ключа, вычисляем хэш ключа и смотрим его положение на кольце.
Например,
hash("ip-user123") = 8.Двигаемся от этой точки по часовой стрелке к ближайшему узлу.
Для значения 8 ближайший по часовой стрелке узел Node-2 находится в точке 15. Соответственно определяем запрос от нашего пользователя user123 на Node-2.
⬆️ Если мы добавим Node-5 с
hash = 50, то переназначить сервер потребуется только пользователям с хэшами от 46 до 50 (у них теперь будет Node-5 вместо Node-1). Остальные сохранят прежние привязки.⬇️ Если Node-2 упадёт, то его пользователи перейдут к Node-3. Остальные также сохранят прежние привязки.
🤌 Минимизация переназначений — это ключевая фишка consistent hashing.
Продолжение ⬇️
#сисдиз