Consistent hashing
hash(key) mod N переотображает почти каждый ключ при смене N — решардинг из ада. Consistent hashing кладёт узлы и ключи на кольцо, так что добавление или удаление одного узла двигает лишь ~1/N ключей, а виртуальные узлы дают баланс.
Команда держала здоровый флот из 10 узлов Memcached, маршрутизируя каждый ключ через hash(key) mod 10. Трафик рос, поэтому добавили два узла и сменили модуль на 12. Деплой ушёл чисто — и база легла через тридцать секунд. Hit rate кеша рухнул с 95% почти до нуля, потому что смена делителя с 10 на 12 переотобразила почти каждый ключ на другой узел. Каждый запрос промахивался, каждый промах бил в базу, и рутинный апгрейд ёмкости стал сбоем. Ошибка была не в добавлении узлов; она была в использовании функции маршрутизации, где добавление одного узла инвалидирует весь кеш. Consistent hashing — починка: способ добавить или убрать узел и потревожить лишь малую долю ключей.
Проблема «перехешировать всё»
Прошлый урок назвал это вскользь; вот почему это так жестоко. С шард = hash(key) mod N назначение ключа зависит от N — числа узлов. Меняешь N — меняешь делитель для каждого ключа разом. Переход с mod 10 на mod 12 не просто переназначает ключи, которым «следует» переехать на новые узлы; он перетасовывает почти весь простор ключей, ведь hash(key) mod 10 и hash(key) mod 12 расходятся для подавляющего большинства ключей.
ключ "user:42" → hash = …739
mod 10 = 9 → узел 9
mod 12 = 7 → узел 7 ← переехал, и почти все остальные тожеДля шардированной базы это почти полная миграция данных. Для кеша хуже и быстрее: каждый ключ теперь хешируется на неправильный узел, так что каждый запрос промахивается, и вся нагрузка чтения бьёт в базовое хранилище — сбой из hook. Корень — функция маршрутизации с вшитым N, так что изменения ёмкости глобальны, а не локальны.
Хеш-кольцо
Consistent hashing рвёт эту связь, хешируя узлы и ключи в один простор и располагая его как кольцо (круг хеш-значений, скажем 0…2^32 − 1, с заворотом).
- Хешируй каждый узел (по имени/IP) в точку на кольце.
- Хешируй каждый ключ в точку на кольце.
- Ключ принадлежит первому узлу, найденному при движении по часовой от позиции ключа.
узел A
·──────· иди по часовой от ключа
· · к следующему узлу на кольце:
· k1→A узел B k1 → A, k2 → B, k3 → C
· ·
· k3→C k2→·
·──────·
узел CТеперь добавь узел D. Он садится где-то на кольце и забирает лишь ключи в дуге между предшественником и собой — те, что раньше шли по часовой мимо этой дуги к следующему узлу. Все прочие ключи всё так же идут к тому же узлу, что и раньше. Удаление узла — зеркало: двигаются лишь его ключи, к следующему узлу по часовой. Изменение членства тревожит примерно 1/N ключей, а не все — это единственное свойство и есть вся суть, и оно превращает «добавить узел» из глобальной перетасовки в локальную передачу.
Виртуальные узлы ради баланса
У простого consistent hashing есть изъян: с горсткой случайно разбросанных по кольцу точек узлов дуги между ними неровные. Один узел может владеть 40%-й дугой, другой 5%-й, так что нагрузка перекошена — а когда узел умирает, вся его дуга валится на единственный следующий по часовой, который тогда может опрокинуться (каскадный отказ).
Починка — виртуальные узлы (vnodes): вместо одной точки на физический узел размести его во многих точках на кольце (скажем, 100–200 каждый, через hash(node + "#0"), hash(node + "#1"), …). Теперь каждый физический узел владеет многими малыми дугами, разбросанными по кольцу. Два выигрыша:
- Баланс: много случайных малых дуг усредняются, так что каждый физический узел получает почти равную долю простора (закон больших чисел).
- Гладкий отказ: когда узел умирает, его много малых дуг наследуют много разных преемников, размазывая осиротевшую нагрузку по кластеру вместо сброса всей на одного соседа.
Vnodes ещё позволяют взвешивать разнородное железо: дай большей коробке больше виртуальных точек — она владеет пропорционально большей долей кольца. Так распределяют данные Dynamo-подобные системы и Cassandra; число vnodes на узел — реальная ручка настройки (мало → дисбаланс, много → большее кольцо в управлении).
▸Почему это работает
Почему кольцу вообще нужны виртуальные узлы — разве «хешировать узел на кольцо» недостаточно? Потому что малое число случайных точек распределено плохо. С, скажем, 5 узлами, хешированными по разу на 32-битное кольцо, ты кладёшь 5 случайных точек на круг; зазоры между ними следуют перекошенному распределению, так что вполне вероятно, что один узел владеет дугой в несколько раз больше другого. Дисбаланс убывает с добавлением точек, так что дав каждому физическому узлу ~150 виртуальных точек, ты превращаешь 5 случайных размещений в 750, и отношение наибольшей дуги к наименьшей резко стягивается. Глубже — та же статистика, что за хешированием ради ровной нагрузки в прошлом уроке: равномерность — асимптотическое свойство многих выборок, а не гарантия немногих; vnodes дёшево покупают тебе «много выборок».
Bounded-load и где это используется
Consistent hashing балансирует простор ключей, но урок прошлого занятия всё ещё кусает: ровные дуги не значат ровную нагрузку, если один ключ — знаменитость. Уточнение, consistent hashing с ограниченной нагрузкой (подход, описанный Google и стоящий за частью балансировщиков), добавляет потолок: каждый узел держит не более c × среднее нагрузки; если ключ сел бы на узел уже на потолке, он переливается по часовой на следующий узел со свободным местом. Это не даёт одному узлу захлебнуться от горячей дуги, сохраняя свойство «двигать мало при смене членства» — прямой ответ на проблему горячего шарда для маршрутизации запросов.
Где встретишь consistent hashing на практике:
- Распределённые кеши (клиентский шардинг Memcached/Redis) — чтобы добавление узла кеша не сносило hit rate (hit rate — доля запросов, обслуженных кешем), ровно починка из hook.
- Dynamo-подобные key-value хранилища (DynamoDB, Cassandra, Riak) — размещать партиции по узлам и дёшево ребалансировать при росте кластера или отказе узла. (Dynamo сочетает это кольцо с кворумной репликацией урока 01.)
- Балансировщики нагрузки — отображать запрос (часто по сессии или клиентскому ключу) на консистентный бэкенд, чтобы sticky-маршрутизация пережила смену пула бэкендов.
Каждый раз, когда одна из этих систем добавляет или убирает узел, ты наблюдаешь локальную передачу дуги — не глобальную перетасовку. Без кольца каждое такое изменение ёмкости было бы тем самым сбоем из hook.
▸Частая ошибка
Классическая ошибка — тянуться к consistent hashing, когда хватило бы простого хеширования, и платить его сложность ни за что. Если набор узлов фиксирован (статичное, редко меняющееся число шардов) и нагрузка ровная, hash(key) mod N проще, кольца в управлении нет, и всё прекрасно; consistent hashing нужен лишь когда членство меняется в рантайме (автомасштабируемые кеши, растущий key-value кластер, отказывающие и возвращающиеся узлы). Обратная ошибка не менее плоха: использовать consistent hashing, но со слишком малым числом виртуальных узлов, и затем удивляться перекошенной нагрузке и жестоким каскадам при отказе — ровно проблемам, ради которых vnodes существуют. Согласуй инструмент с волатильностью набора узлов, а если используешь кольцо — дай ему достаточно виртуальных узлов, чтобы реально балансировать.
Флот кеша маршрутизирует ключи через hash(key) mod N. Ты добавляешь один узел (N: 20 → 21), и hit rate рушится почти до нуля. Что произошло и какая схема маршрутизации это предотвращает?
Ты реализуешь хеш-кольцо с каждым физическим узлом ровно в одной точке. Нагрузка сильно перекошена, и когда один узел умирает, его преемника раздавливает. В чём починка?
На хеш-кольце ключ назначается первому узлу, найденному при движении _______ от позиции ключа — поэтому новый узел крадёт лишь ключи единственной дуги прямо перед собой, оставляя все прочие на их текущем узле.
- 01Почему hash(key) mod N переотображает почти всё при смене N и чего это стоит?
- 02Опиши хеш-кольцо и почему добавление узла двигает лишь ~1/N ключей.
- 03Какие проблемы решают виртуальные узлы и что такое bounded-load consistent hashing?
У hash(key) mod N из прошлого урока N вшит в маршрутизацию, так что смена числа узлов переотображает почти каждый ключ разом — почти полный переезд данных для шардированной БД и мгновенный снос кеша (сбой из hook), где каждый запрос промахивается и базовое хранилище ложится. Consistent hashing развязывает маршрутизацию и N: хешируй узлы и ключи в один кольцевой простор и назначай каждый ключ первому узлу, найденному по часовой. Поскольку каждый узел владеет непрерывной дугой, добавление или удаление узла трогает лишь одну дугу — двигается ~1/N ключей, а не все. Виртуальные узлы (каждый физический узел в ~150 точках кольца) чинят два изъяна наивного кольца: балансируют нагрузку многими малыми дугами и размазывают нагрузку мёртвого узла по многим преемникам вместо раздавливания одного соседа — а ещё дают взвешивать неровное железо. Bounded-load consistent hashing ограничивает каждый узел c×среднее и переливает излишек по часовой, укрощая горячие дуги. Кольцо встретишь в распределённых кешах (чтобы масштаб не сносил hit rate), Dynamo-подобных хранилищах (вместе с кворумной репликацией урока 01) и балансировщиках — а тянешься к нему лишь когда членство меняется в рантайме; для фиксированного набора узлов простой mod N проще и достаточен. Теперь, когда увидишь, что узел Memcached добавляется во флот или нода Cassandra входит в кольцо — ты распознаешь передачу дуги и будешь знать, почему hit rate не рухнул.
Практика
Начни сверху. Задачи идут от простого к сложному: вспомнить факт, применить к случаю, затем senior-уровень. Открой, попробуй, потом открой ответ.
Что-то непонятно?
Задай вопрос по этому уроку. Вопросы анонимны и попадают напрямую автору — урок станет лучше.
Примени это
Примени этот урок в реальном проекте.