Как consistent hashing ограничивает перераспределение ключей при добавлении узла?
Consistent hashing размещает узлы и ключи на логическом кольце. При добавлении узла перемещаются в основном только ключи из участка кольца, который новый узел забирает у своего следующего соседа, а не весь набор данных.
При равномерном распределении один новый узел получает в среднем около 1/(N+1) ключей, где N — прежнее число узлов. Это снижает объём миграции, но не устраняет его полностью и не гарантирует равномерность без дополнительных механизмов.
При обычном распределении по формуле hash(key) mod N изменение числа узлов меняет результат для большинства ключей. Поэтому добавление или удаление одного узла может потребовать массового перемещения данных и создать значительную нагрузку на сеть, диски и хранилища.
Consistent hashing был предложен как способ уменьшить масштаб такого перераспределения в распределённых системах. Вместо прямого вычисления номера узла ключ и узлы отображаются в одно логическое пространство, а ключ принадлежит следующему узлу по кольцу.
Пусть кластер хранит данные на N узлах, а маршрутизатор определяет узел по ключу. После добавления нового узла маршрутизация должна измениться так, чтобы часть ключей стала обслуживаться им.
Неверный выбор алгоритма может привести к массовой миграции, резкому росту задержек, исчерпанию пропускной способности и временной перегрузке отдельных узлов. Если разные компоненты используют разные версии кольца, один и тот же ключ может направляться на разные узлы, что приводит к ошибкам чтения или записи.
В consistent hashing каждому узлу назначается позиция на кольце хешей. Ключ также хешируется в позицию, после чего выбирается первый узел по направлению обхода кольца. Узел отвечает за диапазон между предыдущим узлом и своей позицией.
При добавлении нового узла он занимает только часть диапазона своего преемника. Ключи в этом диапазоне меняют владельца, остальные ключи продолжают обращаться к прежним узлам. При удалении узла его диапазон обычно переходит следующему узлу.
Распределение может оказаться неравномерным, если узлы представлены одной точкой или хеш-функция даёт неудачное размещение. Поэтому применяют виртуальные узлы: один физический узел получает множество позиций на кольце. Это улучшает баланс и позволяет точнее задавать веса узлов, но увеличивает объём метаданных и стоимость управления кольцом.
Математическое уменьшение миграции не означает, что данные переместятся мгновенно. Нужны процедура копирования, переключение владельца, обработка записей во время миграции и удаление старой копии только после подтверждения корректности. Для этого часто используют версии диапазонов, журналирование изменений или временную двойную запись.
У алгоритма есть ограничения. Он не защищает от горячих ключей: один популярный ключ может перегрузить владельца независимо от качества распределения. Репликация также требует отдельного решения: перемещение первичного владельца не обязательно означает перемещение всех реплик, а изменение набора реплик может временно влиять на доступность и согласованность.
Основные компромиссы таковы: больше виртуальных узлов обычно улучшает баланс, но усложняет маршрутизацию и миграции; агрессивная миграция быстрее освобождает старый узел, но сильнее нагружает кластер; осторожная миграция снижает риск перегрузки, но дольше оставляет систему в промежуточном состоянии.
В кластере распределённого хранилища четыре узла, и один из них необходимо заменить более производительным. При использовании hash(key) mod N изменение числа узлов заставило бы маршрутизировать большую часть ключей заново, поэтому команда рассмотрела три варианта.
Первый вариант — оставить старое число логических узлов и постепенно передать их новому физическому серверу. Это уменьшает одномоментную миграцию, но усложняет соответствие между логическими и физическими узлами и не решает проблему при частых изменениях состава кластера.
Второй вариант — использовать централизованную таблицу соответствия ключей и узлов. Такой подход даёт точный контроль и позволяет учитывать размер данных, но требует масштабирования и высокой доступности самого сервиса маршрутизации.
Третий вариант — перейти на consistent hashing с виртуальными узлами, ограничить скорость миграции и переключать диапазоны после проверки скопированных данных. Выбрали его, поскольку кластер часто масштабируется, а равномерное постепенное перераспределение важнее полного централизованного контроля.
В результате при добавлении узла переносилась только его доля диапазонов, а нагрузка миграции ограничивалась. Дополнительно настроили мониторинг горячих ключей и согласованную публикацию версии кольца, поскольку один только алгоритм хеширования не решает эти проблемы.
1. Обязательно ли при добавлении одного узла перемещается ровно 1/(N+1) данных?
Нет. Это средняя оценка при равномерном размещении и одинаковом размере ключей. Реальный объём зависит от позиций узлов на кольце, количества виртуальных узлов, распределения размеров объектов и выбранной стратегии балансировки.
Если данные сильно различаются по размеру, равное число ключей не означает равный объём данных. Поэтому для крупного хранилища контролируют не только количество ключей, но и байты, нагрузку на диски, операции ввода-вывода и частоту запросов.
2. Чем consistent hashing отличается от простого хеширования по модулю?
При хешировании по модулю изменение N меняет результат для большинства ключей, потому что номер узла вычисляется непосредственно из нового размера кластера. В consistent hashing узлы и ключи находятся на общем кольце, поэтому добавление узла затрагивает преимущественно один или несколько локальных диапазонов.
Это не делает маршрутизацию бесплатной: нужно распространять изменения кольца, мигрировать данные и синхронизировать участников. Преимущество состоит именно в ограничении масштаба перераспределения, а не в отсутствии операционных затрат.
3. Как обрабатывать запись ключа во время его миграции между узлами?
Нельзя просто скопировать текущий снимок и немедленно удалить источник: запись, пришедшая после снимка, может потеряться. Обычно применяют журнал изменений, повторное проигрывание записей, временную двойную запись или механизм блокировки диапазона — конкретный выбор зависит от требований к доступности и задержке.
После копирования нужно определить момент безопасного переключения владельца и согласовать его со всеми маршрутизаторами. Более строгая координация уменьшает риск потери или расхождения данных, но повышает задержки и усложняет восстановление после сбоя; более доступная схема может временно читать из нескольких мест и должна уметь разрешать конфликты.