Способ распределить ключи по узлам так, чтобы добавление или потеря узла двигали лишь малую долю данных, а не всё сразу.
Ключевые тезисы
- Обычный остаток от деления при смене числа узлов переносит почти все ключи — кластер встаёт.
- переносит в среднем 1/n данных при добавлении узла.
- выравнивают нагрузку: без них дисбаланс между машинами достигает разов.
Какую задачу решает
Данных больше, чем влезает на одну машину, значит, их надо разложить по многим. Простейший способ — взять хеш ключа и поделить с остатком на число серверов. Работает ровно до , когда сервер добавили или потеряли.
Беда в том, что при смене числа серверов меняется остаток почти у всех ключей. Перейдя с четырёх машин на пять, вы переносите не пятую часть данных, а около восьмидесяти процентов: кластер несколько часов занят только перекладыванием, и всё это время он не работает.
убирает эту катастрофу. Ключи и серверы кладутся на одно кольцо, ключ обслуживает ближайший по часовой стрелке сервер. Добавление сервера отбирает данные только у соседа — в среднем 1/n от общего объёма.
Поставьте на кольцо четыре сервера случайными точками. Промежутки между ними получатся разной длины — это свойство случайных точек, а не невезение: ожидаемая разница между самым большим и самым маленьким промежутком примерно четырёхкратная. Значит, один сервер получит вчетверо больше ключей другого и упрётся в диск, пока соседи простаивают. Лечение: представить каждый сервер не одной точкой, а двумя сотнями. Промежутки усредняются, и разброс нагрузки падает до единиц процентов. Отсюда практическое правило — 256 на узел по умолчанию.
Подробный разбор
Возьмите четыре сервера и ключ с хешем 1237. Остаток от деления на 4 — единица, ключ идёт на второй сервер. Добавьте пятый сервер: остаток от деления на 5 — двойка, и тот же ключ должен переехать. Так происходит почти со всеми ключами.
| Было серверов | Стало | Доля переезжающих ключей |
|---|---|---|
| 4 | 5 | ≈ 80% |
| 10 | 11 | ≈ 91% |
| 100 | 101 | ≈ 99% |
меняет саму схему владения. Хеш-пространство замыкают в кольцо; на него кладут и ключи, и серверы. Ключ обслуживает первый сервер, встреченный при движении по часовой стрелке.
Теперь добавление сервера отбирает у соседа только тот участок кольца, который новичок перекрыл. Всё остальное кольцо не шелохнулось: переезжает в среднем данных.
Если каждый сервер — одна случайная точка на кольце, промежутки между ними получаются разной длины. Это свойство случайности, а не невезение: у случайных точек ожидаемое отношение самого длинного промежутка к самому короткому растёт с .
- Перекос нагрузки в разы: один узел упирается в диск, соседи простаивают.
- Потеря узла целиком ложится на одного соседа — он получает удвоенную нагрузку и падает следом.
- Добавление узла разгружает ровно одного соседа, а не кластер.
Лечение — представить каждый физический сервер сотнями точек на кольце. Промежутки усредняются, разброс падает до единиц процентов, а нагрузка выбывшего узла размазывается по всем остальным.
В это параметр num_tokens, по умолчанию 256 (в новых версиях 16 с более умным распределением). В Dynamo и её потомках — та же идея под названием «».
Для отказоустойчивости ключ пишут не на один узел, а на подряд идущих по кольцу. Схема даёт бесплатно две вещи: понятный список реплик для любого ключа и естественное после отказа — данные упавшего узла уже лежат у соседей.
Важная поправка: «следующие по кольцу» надо считать с учётом стоек и датацентров. Иначе три реплики окажутся в одной стойке, и обесточивание стойки уничтожит все копии сразу. Настройка называется rack-aware или topology-aware репликацией и включается не по умолчанию.
Где применяется
- Распределённые кешиMemcached и Redis Cluster раскладывают ключи именно так.
- NoSQL-хранилища и DynamoDB построены на кольце с виртуальными узлами.
- Балансировка запросовЛипкая маршрутизация: один пользователь всегда на один бэкенд.
- Шардирование данныхРазложение таблицы по машинам с возможностью добавить машину без простоя.
Плюсы, минусы и альтернативы
Плюсы
- Добавление узла двигает 1/n данных вместо почти всех.
- Потеря узла затрагивает только его долю — остальные не замечают.
- Не нужен центральный каталог: владельца ключа считает любой клиент.
Минусы
- Без виртуальных узлов нагрузка распределяется неравномерно — разброс в разы.
- Диапазонные запросы невозможны: соседние ключи попадают на разные машины.
- Изменение схемы репликации всё равно требует массового переноса.
Брать, если
- Кластер меняет размер, а простой на перекладывание недопустим.
- Доступ идёт по точному ключу, а не по диапазону.
Не брать, если
- Число узлов фиксировано навсегда — обычного остатка достаточно.
- Нужны запросы по диапазону ключей: там берут диапазонное шардирование.
Чем заменяют
Видеолекции
Записи университетских курсов, где эта тема звучит. Ссылка открывает запись с той секунды, где о ней говорят, — искать по трёхчасовой лекции не нужно.
Всё, что названо в описании, разобрано здесь же или в соседней теме — переходы под каждым определением.
Кольцо хешей
Пространство хешей замкнуто в круг; ключ идёт к ближайшему серверу по часовой стрелке.
Разбор ниже: Кольцо вместо остаткаВиртуальные узлы
Каждый физический сервер представлен сотнями точек на кольце — так выравнивается нагрузка.
Разбор ниже: Виртуальные узлыКоэффициент перемещения
Доля ключей, меняющих владельца при изменении состава кластера. Здесь она 1/n.
Разбор ниже: Кольцо вместо остаткаРепликация по кольцу
Копии кладут на следующие N узлов — отсюда естественная схема отказоустойчивости.
Разбор ниже: Репликация по кольцуСпрашивают на собеседовании: Arenadata — Платформа данных.
Глава «Инженерия данных» последний раз правилась . Нашли ошибку — напишите.