12 октября 2026Команда Сарнас

Consistent hashing: что на самом деле доказывают формулы, которые все используют на веру

Консистентное хеширование все принимают на веру: кольцо, ключ идёт к следующему серверу, нагрузка делится поровну. Но за тремя привычными обещаниями — равномерностью, монотонностью и минимумом перемещений — стоят разные математические величины, и «1/k нагрузки» здесь скорее интуиция, чем формула. Статья разбирает модель по шагам — от CDF длины сегмента до комбинаторики разброса — и показывает, где именно упрощения расходятся с точными оценками.

Консистентное хеширование обычно описывают одной фразой: «ключи и серверы раскладываются по окружности, ключ идёт к следующему серверу по часовой стрелке». Из этого сразу выводят три обещания — равномерность, монотонность и минимизацию перемещений. Но что именно стоит за каждым из них: вероятность, математическое ожидание или коэффициент вариации? И почему интуиция «нагрузка делится как 1/k» — это упрощение, а не формула? Разберём механику по шагам: от модели окружности до комбинаторики, которая даёт точную оценку разброса.

Что именно обещают три свойства

хеш-функция переводит и объекты, и серверы на единичную окружность, после чего каждый объект назначается следующему серверу по часовой стрелке. Это даёт равномерное распределение объектов между серверами. При добавлении или удалении сервера перераспределяется лишь часть объектов: добавление n-го сервера перемещает только 1/n долю.

Математическое описание строится через длину сегмента. Для неё вводятся CDF как P(L ≤ x) и PDF как производная CDF по x. CDF выражается формулой 1 − (1 − x)^(H − 1), PDF — формулой (H − 1)(1 − x)^(H − 2). Ошибка равномерности для N серверов с k хешами задаётся формулой Err_k = sqrt((N − 1)/(kN + 1)).

Ключевая тонкость: «равномерность» здесь — не одно число, а распределение. И именно из него выводятся и ожидаемая доля нагрузки, и разброс вокруг неё.

Модель: окружность, хеши и точки серверов

Состояние кольца в одной из реализаций хранится в двух структурах: словаре, где ключ — хеш точки на окружности, а значение — имя сервера, и срезе хешей, отсортированном по возрастанию. При добавлении сервера под блокировкой на запись для каждого из replicationFactor экземпляров вычисляется хеш от имени сервера с числовым суффиксом, результат записывается в словарь и добавляется в срез, после чего срез сортируется. Поиск сервера для ключа идёт под блокировкой на чтение: вычисляется хеш ключа, затем бинарным поиском находится индекс первого элемента среза, который не меньше хеша, с закольцовыванием на 0 при выходе за границу.

Хеш здесь 64-битный: blake2b.Sum512 вычисляет полную 512-битную сумму, а binary.LittleEndian.Uint64 берёт из неё младшие 64 бита — этого достаточно, чтобы получить компактный числовой ключ для позиции на окружности. В другом варианте реализации используются 32-битные хеши, словарь с 32-битными ключами, множество имён серверов и счётчик серверов; функция добавления заполняет словарь, после чего пересобирает отсортированный срез из его ключей. Выбор хеш-функции там переключается между FNV и CRC32 — переключатель позволяет выбрать между скоростью и качеством разброса в зависимости от нагрузки.

Блокировки разделены по типу операции: изменение состояния (добавление, удаление, обновление нагрузки, инкремент и декремент) берёт блокировку на запись, а чтение (поиск сервера, поиск наименее загруженного, перечисление хостов и участников, выбор двух и N серверов) — блокировку на чтение.

Один хеш на сервер: откуда берётся CDF длины сегмента

Классическая схема — один хеш на сервер. Тогда длина сегмента L — это расстояние от 0 до ближайшего хеша. События L ≤ x и L > x дополняют друг друга, поэтому CDF(L) = 1 − P(L > x). Вероятность P(L > x) — это вероятность того, что все остальные H − 1 хешей больше x. Хеши независимы, значит эта вероятность раскладывается в произведение H − 1 множителей, а для одного хеша вероятность оказаться больше x равна 1 − x. Отсюда:

CDF(L) = 1 − (1 − x)^(H − 1)

PDF получается дифференцированием CDF по x: производная константы 1 равна нулю, производная (1 − x)^(H − 1) даёт −(H − 1)(1 − x)^(H − 2), и минус на минус даёт итог (H − 1)(1 − x)^(H − 2).

Здесь стоит остановиться: PDF может принимать значения больше 1. Это не ошибка — плотность вероятности не обязана быть вероятностью. Поэтому вероятность конкретного значения ищут через гистограммы, а вероятность попадания в диапазон вычисляют как интеграл PDF по этому диапазону или, что то же самое, как разность CDF на границах.

Именно эта разность служит масштабированной аппроксимацией плотности в точке и позволяет сравнить расчёт с результатами симуляции.

Почему абсолютное отклонение обманывает

Стандартное отклонение длины сегмента задано в абсолютных единицах. Из формулы видно, что оно падает обратно пропорционально общему числу хешей. Но доля диапазона, покрываемая одним сегментом, тоже падает обратно пропорционально общему числу хешей. В результате абсолютная ошибка может оказаться почти равна ожидаемому размеру сегмента. При H = 100 стандартное отклонение около 0.99%, ожидаемый размер сегмента 1% — то есть разброс в обе стороны от ожидания почти равен самому ожиданию.

Сравнивать конфигурации по такому числу бессмысленно. Поэтому переходят к коэффициенту вариации: он определяется как стандартное отклонение, делённое на ожидаемое значение, то есть ошибка приводится к масштабу ожидаемой величины. Для одного хеша на сервер:

CV(L) = SD(L) / Exp(L) = sqrt((H − 1)/(H + 1))

При H = 100 это даёт ошибку 99%. И главное: для почти всех значений H ошибка остаётся постоянной и составляет около 100%. Одно-хешевая схема плоха не в каком-то частном режиме — она плоха всегда.

Несколько хешей: комбинаторика вместо интуиции

Схема с k хешами на сервер (виртуальные узлы) меняет картину. При создании задаётся 20 реплик на сервер, добавление размещает сервер в кольце для каждого индекса от 0 до NumberOfReplicas − 1, используя хеш от имени с этим индексом. Удаление симметрично проходит те же индексы и убирает соответствующие ключи. Поиск находит ближайший по часовой стрелке узел; выбор двух серверов после первого найденного продолжает идти по кругу, пока не встретит сервер, отличный от первого.

Математически задача формулируется так: найти распределение суммы первых k сегментов числовой прямой. Ключевой приём — сведение суммы первых k сегментов к позиции (k + 1)-го наименьшего хеша. Если расставить все хеши на числовой прямой по возрастанию, то длины сегментов — это расстояния между соседними хешами, поэтому сумма длин первых k сегментов равна расстоянию от начала координат до (k + 1)-й точки. Через CDF это записывается как вероятность того, что сумма не превышает x, а затем переписывается через счётчик хешей меньше x.

Чтобы получить замкнутое выражение, вводится параметризованная функция Beta(C, n, m) = C·∫₀¹ xⁿ(1 − x)ᵐ dx — она нужна, чтобы многократно применить интегрирование по частям. После одного прохода степень x уменьшается на 1, степень (1 − x) увеличивается на 1, а множитель C умножается на n/(m + 1). После i проходов состояние записывается как Cᵢ∫₀¹ x^{nᵢ}(1 − x)^{mᵢ}dx, откуда получаются переобозначения nᵢ = n − i, mᵢ = m + i и Cᵢ = C·n!m!/((n − i)!(m + i)!). При i = n, когда nᵢ = 0, интеграл сводится к C·n!m!/(m + n + 1)!. Это и даёт ожидаемую долю нагрузки Exp_k(L) = k/H.

Промежуточная комбинаторика устроена так: вводится функция Bᵢ(x) = C(H − 1, i)(H − 1 − i)·xⁱ(1 − x)^{H − 2 − i}, где C(H − 1, i) — биномиальный коэффициент, и рядом A_{i+1}(x) = −C(H − 1, i + 1)(i + 1)·xⁱ(1 − x)^{H − 2 − i}, причём Bᵢ(x) = −A_{i+1}(x). Сумма PDF_k(x) = Σ_{i=0}^{k−1} Aᵢ(x) + Bᵢ(x) после подстановки сокращается попарно, и остаётся PDF_k(x) = A₀(x) − A_k(x). В итоговой формуле k — число хешей на сервер, H — общее число хешей.

Финальная формула и её частный случай

Финальное выражение для ошибки — коэффициент вариации:

Err_k = CV_k(L) = sqrt((H − k)/(k(H + 1)))

Оно получается как отношение стандартного отклонения нагрузки к её ожидаемому значению. Для частного случая, когда на каждый сервер приходится одинаковое число хешей H = Nk, формула упрощается до sqrt((N − 1)/(kN + 1)). Автор прямо оговаривает: это не та формула из краткого изложения, и версия из краткого изложения была базовой — для случая одинакового числа хешей на всех серверах. Коэффициент вариации показывает, насколько нагрузка на одном сервере может отличаться от ожидаемой.

Пограничные случаи: что происходит при изменении состава

При добавлении или удалении сервера подавляющее большинство объектов сохраняют прежнее назначение. Добавление n-го сервера перемещает лишь 1/n долю объектов. При удалении сервера переназначаются только те объекты, которые были отображены на отказавший сервер, — они переходят к следующему серверу по часовой стрелке. При добавлении сервера переназначаются только те объекты, для которых новый сервер стал следующим по часовой стрелке, то есть ранее назначенные существующему серверу.

В реализации для поиска сервера используется бинарное дерево поиска. В нём находят преемника. При вставке, если значение больше всех идентификаторов серверов, объект помещается на сервер с наименьшим идентификатором. При удалении объект удаляется с возвращённого сервера, а если преемника нет — с наименьшего идентификатора.

Отдельный вопрос — одновременное добавление нескольких серверов. Рассматривается только распределение суммы k сегментов, где k — число хешей одного сервера. Формула для k хешей описывает распределение нагрузки одного сервера с k хешами, но не совместное добавление нескольких серверов. Это ограничение стоит держать в голове: формулы отвечают на вопрос о разбросе нагрузки одного сервера, а не о том, что произойдёт, если в кольцо войдут несколько узлов сразу.

Расширения, без которых схема не балансирует

Виртуальные узлы — это дублирующие метки, указывающие на один реальный сервер. Их количество для конкретного сервера называется весом. Они нужны, чтобы избежать перекоса нескольких узлов внутри радиана — то есть участка окружности между двумя соседними точками серверов: из-за неравномерного распределения серверов по окружности такие участки получаются разной длины, и нагрузка ложится на серверы неравномерно. При отказе сервера объекты, назначенные каждой из его реплик, переназначаются разным серверам по часовой стрелке — так перераспределение получается более равномерным.

Если один объект становится «горячим» и обслуживается многими серверами, он может быть назначен нескольким смежным серверам при обходе окружности. Если два «горячих» объекта хешируются рядом, они используют один и тот же набор смежных серверов; это смягчается выбором для каждого объекта своей хеш-функции отображения серверов на окружность.

Bounded loads реализованы через поиск наименее загруженного хоста, способного обслужить ключ: хосты перебираются по кольцу с проверкой порога. Максимальная нагрузка одного хоста вычисляется как (total_load / number_of_hosts) * 1.25, а проверка порога использует ту же формулу с (totalLoad + 1).

Как это реализовано: нагрузка, счётчики и пересборка

Добавление сервера под блокировкой на запись для каждой реплики вычисляет ключ и кладёт его в кольцо, помечает сервер в множестве участников, пересчитывает отсортированный срез и увеличивает счётчик серверов. Удаление делает обратное: для каждой реплики удаляет ключ из кольца, убирает сервер из множества, пересчитывает срез и уменьшает счётчик.

Пересборка отсортированного среза берёт его же срез нулевой длины, при необходимости обнуляет его и заново собирает все ключи кольца, сортирует и присваивает обратно. Условие обнуления: если отношение ёмкости среза к произведению числа реплик на 4 превышает длину кольца, срез сбрасывается в nil — чтобы не удерживать лишнюю память. Иначе говоря, порог срабатывает, когда выделенная ёмкость более чем вчетверо превышает текущее число ключей.

Счётчики нагрузки обновляются атомарно: инкремент увеличивает нагрузку хоста и общую нагрузку на 1, декремент уменьшает обе на 1. При удалении хоста его нагрузка не декрементируется — хост просто удаляется из карты нагрузок. Декремент нужен именно при завершении запроса, потому что проверка порога сравнивает текущую нагрузку плюс один с порогом средней нагрузки на узел. Без уменьшения нагрузки при завершении запроса хост навсегда остался бы перегруженным, и поиск наименее загруженного хоста больше его не выбирал бы.

Как сравнивали и что получилось

Расчётное распределение сравнивают с симуляцией: вероятность попадания сегмента в дискретный диапазон вычисляется через разность CDF на границах диапазона, что позволяет сопоставить рассчитанное распределение с результатами симуляции. При больших N распределение приближается к 1/k·√(1/k). В системе с 50 и более серверами разница между фактическим значением ошибки и этой аппроксимацией составляет около 1%.

Оговорка: эти цифры описывают сходимость аппроксимации при большом числе серверов, а не абсолютную точность схемы. При малых N аппроксимация 1/k·√(1/k) работает хуже, и пользоваться ею вместо точной формулы не стоит.

Сравнение с альтернативами

Для N узлов и K ключей консистентное хеширование добавляет и удаляет узел за O(K/N + log N), тогда как классическая хеш-таблица выполняет обе операции за O(K). Поиск, добавление и удаление ключа у консистентного хеширования — O(log N), у классической хеш-таблицы — O(1). Слагаемое O(K/N) — средняя стоимость перераспределения ключей, а O(log N) возникает потому, что для поиска следующего узла на кольце нужен бинарный поиск среди углов узлов.

Rendezvous hashing разработан в 1996 году и описывается как более простая и более общая техника: он позволяет полностью распределённо согласовать набор из k вариантов из n возможных. Консистентное хеширование — частный случай rendezvous hashing, и из-за простоты и общности rendezvous hashing теперь используется вместо консистентного хеширования во многих приложениях. Если значения ключей всегда монотонно возрастают, альтернативный подход с хеш-таблицей с монотонными ключами может оказаться более подходящим.

Пример реализации на Java и его ограничения

В примере Tom White класс ConsistentHash<T> хранит кольцо как SortedMap<Integer, T>, создаваемый как TreeMap; ключи — целые хеш-значения, значения — узлы. Конструктор принимает хеш-функцию, число реплик и коллекцию узлов, сохраняет их и для каждого узла вызывает добавление. Добавление для i от 0 до numberOfReplicas кладёт в кольцо пару «хеш от имени узла с числовым суффиксом → узел». Удаление для тех же i удаляет записи по тем же хешам.

Поиск при пустом кольце не находит узел. Иначе вычисляется хеш ключа, и если такого ключа в кольце нет, берётся tailMap от хеша и выбирается первый ключ из него, а если tailMap пуст — первый ключ всего кольца (замыкание по кругу). Если хеш ключа точно совпал с точкой сервера, ветка поиска следующего узла не выполняется и берётся значение по этому же ключу.

Ограничения этого подхода по сравнению с реализацией на Go: нет отдельного множества участников, нет счётчика серверов, нет буфера для пересборки, нет выбора между crc32 и fnv, нет блокировок чтения-записи и нет ошибки пустого кольца — при пустом кольце узел не находится, а не сообщается об ошибке.

Что из этого следует на практике

«Равномерность» — это не одно число, а распределение. Ожидаемая доля нагрузки на сервер равна k/H, но разброс вокруг неё описывается коэффициентом вариации, и именно он определяет, насколько один сервер может оказаться перегружен относительно другого.
Один хеш на сервер не работает: коэффициент вариации sqrt((H − 1)/(H + 1)) при почти любом H даёт около 100%. Виртуальные узлы — не оптимизация, а необходимое условие работоспособности.
Абсолютное стандартное отклонение длины сегмента обманчиво: оно падает вместе с размером сегмента, поэтому сравнивать конфигурации нужно по безразмерной мере — коэффициенту вариации.
Формула sqrt((N − 1)/(kN + 1)) — это частный случай для одинакового числа хешей на всех серверах. Общая формула — sqrt((H − k)/(k(H + 1))). Если серверы имеют разный вес, частный случай неприменим.
Аппроксимация 1/k·√(1/k) расходится с точным значением примерно на 1% только при 50 и более серверах. При меньшем числе серверов её использовать нельзя.
При добавлении n-го сервера перемещается 1/n доля объектов; при удалении — только объекты отказавшего сервера. Это и есть минимизация перемещений.
Bounded loads требуют парного учёта: инкремент при взятии запроса и декремент при завершении. Без декремента хост навсегда останется перегруженным и выпадет из выбора.
Консистентное хеширование — частный случай rendezvous hashing, и по сложности операций оно проигрывает классической хеш-таблице: поиск ключа O(log N) против O(1). Выбор в пользу консистентного хеширования оправдан именно минимизацией перемещений при изменении состава узлов, а не скоростью отдельных операций.