Консистентное хеширование: сколько ключей переезжает при смене состава

Что здесь на самом деле спрашивают

Лестница выглядит так:

1. «Как разложить ключи по узлам?» — разминка: ответ на неё — деление по модулю.
2. «Что произойдёт при добавлении узла?» — здесь начинается содержание, и ответ «часть ключей переедет» уже неверен по величине.
3. «Что такое консистентное хеширование?» — вопрос про механизм.
4. «Зачем виртуальные узлы?» — вопрос, на котором видно, считал ли собеседник перекос или пересказывает.
5. «Чем платят за виртуальные узлы?» — вопрос про размен.
6. «Где эта схема не спасает?» — вопрос про границы.

Числа получены прогоном bench/hashring/ring.py и bench/hashring/practice.py. Это не модель и не симуляция: раскладка ключей по узлам считается точно, и доля переехавших получается пересчётом. Случайны здесь только сами ключи, и они порождены фиксированным зерном.

База: как узнают, на каком узле лежит ключ

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

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

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

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

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

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

Механизм 1: модуль переносит почти всё

Теперь то же самое в числах. Вот что происходит с делением по модулю при добавлении узла:

1. MODULO SHARDING: ADDING ONE NODE MOVES ALMOST EVERYTHING
-----------------------------------------------------------
         nodes   -> nodes    keys moved   ideal share
             8          9        88.9%        11.1%
             8         10        80.2%        20.0%

  times more than the minimum, +1 node           8.0

Читать надо две колонки рядом, и первую строку — с названными допущениями. Строка описывает переход с восьми узлов на девять: к восьми узлам добавляется один такой же, равноправный, а ключи раскладываются поровну. При этих допущениях ideal share — необходимый минимум: девятому узлу должна достаться примерно девятая часть ключей, то есть 11,1 % обязаны переехать в любой схеме, которая раскладывает ключи поровну. А переехало 88,9 % — в восемь раз больше. Оба числа относятся именно к этому переходу: у другого состава и другого числа добавляемых узлов будут свои, что и показывает вторая строка.

Почему так. При делении по модулю узел ключа — не свойство ключа, а свойство текущего числа узлов. Меняется делитель — меняется ответ сразу для всех: ключ с хешем 17 при восьми узлах жил на первом, при девяти живёт на восьмом, и никакого отношения к появлению нового узла это не имеет.

Ради этого следствия раздел и существует в разговоре: добавление узла в такую схему — это перенос почти всех данных. Для кеша это значит, что почти девять ключей из десяти спросят не тот узел, то есть промахнутся; для хранилища — что почти весь набор данных придётся передать по сети. И то и другое случается ровно тогда, когда узел добавляют из-за нехватки ёмкости.

Обратите внимание и на вторую строку: добавление двух узлов перенесло 80,2 % — меньше, чем добавление одного. «Больше добавили — больше переехало»: такого правила здесь нет. Доля определяется арифметикой остатков, а не размером изменения, и заранее её не угадать — только посчитать.

Механизм 2: кольцо переносит близко к минимуму

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

Тогда появление нового узла отбирает только тот участок окружности, который оказался прямо перед ним. Остальные пары «ключ — узел» не меняются вообще: их не с чем сравнивать заново.

2. A RING MOVES ONLY WHAT IT HAS TO
-----------------------------------
    vnodes per node   keys moved, +1 node   ideal share
                  1                11.5%        11.1%
                 16                10.9%        11.1%
                128                10.7%        11.1%

Те же восемь узлов, тот же девятый, те же ключи. Кольцо, у которого на каждый узел приходится одна точка, перенесло 11,5 % против 88,9 % у деления по модулю — то есть практически необходимый минимум. Нижние строки блока забегают вперёд: там у узла на кольце не одна точка, а несколько — зачем так делают, разбирается дальше, и на долю переезда это почти не влияет.

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

Отсюда и название: схема консистентна в том смысле, что ответ для конкретного ключа не меняется без причины, касающейся именно этого ключа.

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

Механизм 3: удаление узла не трогает чужие ключи

Добавление узла мы уже видели. Теперь обратное действие — то самое, ради которого схему и придумали. Уберём один узел из восьми:

5. REMOVING A NODE MOVES ITS KEYS AND NOBODY ELSE'S
---------------------------------------------------
  share of keys the removed node owned           11.7%
  share of keys that moved in total              11.7%
  share of OTHER nodes' keys that moved          0.0%

Три строки, и вся суть в третьей. Переехало ровно столько ключей, сколько принадлежало ушедшему узлу, и ни одного чужого.

Это то самое свойство, которого нет у деления по модулю: там уход узла меняет делитель и, значит, ответ для всех. Здесь уход узла стирает его точки с кольца, и ключи, которые на них указывали, переходят к соседям справа. Все остальные ключи по-прежнему указывают на те же точки, и им нет дела до состава.

В этом расчёте у каждого узла на кольце не одна точка, а сто двадцать восемь. На само свойство их число не влияет: важно только то, что точки ушедшего узла исчезают, а чужие остаются на местах. Зачем точек делают много — отдельный разговор.

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

Глубже: перекос и виртуальные узлы

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

Разложим ключи по восьми узлам, поставив на кольцо по одной точке на узел:

3. WITHOUT VIRTUAL NODES THE RING IS BADLY SKEWED
-------------------------------------------------
    vnodes per node   smallest share   largest share   max/min
                  1            0.4%          33.3%     90.5x
                 16            8.7%          16.3%      1.9x
                128           11.0%          15.1%      1.4x
                512           12.1%          13.6%      1.1x

Один узел получил треть всех ключей, другой — четыре десятых процента. Разница в 90,5 раза, при том что узлов восемь и «поровну» означало бы по одной восьмой на каждого.

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

Виртуальные узлы — это лечение: вместо одной точки узел получает много, и его доля складывается из множества маленьких дуг. Много маленьких случайностей усредняются, восемь больших — нет. При 128 точках перекос падает до 1,4 крата.

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

Чем платят за виртуальные узлы

4. WHAT VIRTUAL NODES COST
--------------------------
    vnodes per node   points on the ring   max/min
                  1                    8     90.5x
                 16                  128      1.9x
                128                 1024      1.4x
                512                 4096      1.1x

Точки на кольце — не абстракция: это структура, по которой ищут владельца каждого ключа и которую обязан держать каждый участник, знающий раскладку. Восемь узлов при 512 точках — это кольцо из 4096 записей.

Смотреть надо на форму размена. Переход от 1 к 16 точкам убирает почти весь перекос: 90,5 крата превращаются в 1,9. Переход от 128 к 512 учетверяет структуру ради последних процентов равномерности: 1,4 против 1,1.

Отсюда и ответ на вопрос «сколько ставить виртуальных узлов»: столько, чтобы перекос стал приемлемым, и ни одной точкой больше. Число это зависит от того, сколько у вас узлов и какой перекос вы готовы терпеть, — и его считают, а не берут из статьи.

Как отвечать на собеседовании

Короткий ответ: деление по модулю привязывает владельца ключа к числу узлов, поэтому любое изменение состава пересчитывает всё; кольцо привязывает владельца к позиции ключа, поэтому меняются только ключи рядом с изменением. Посчитано на 100 000 ключей: добавление девятого узла к восьми переносит 88,9 % ключей при модуле и 11,5 % на кольце с одной точкой на узел.

Этого достаточно, чтобы ответить верно. Дальше — то, что добавляют, если собеседник копает.

Если интервьюер копает глубже

Хороший ответ отличают три вещи. Первая — вы объясняете причину, а не название: у модуля узел ключа зависит от числа узлов, у кольца — от позиции ключа. Вторая — вы сами называете цену: кольцо без виртуальных узлов даёт перекос, и в этом расчёте он составил 90,5 крата. Третья — вы говорите, чем платят за виртуальные узлы: размером структуры, которую держат все участники, и приводите форму размена — от 1 к 16 точкам почти весь выигрыш, от 128 к 512 последние проценты.

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

Чего говорить не стоит: «консистентное хеширование переносит только 1/N ключей». Это верно для добавления одного равноправного узла при ровной раскладке ключей и неверно как общее утверждение — и скрывает перекос, который в расчёте оказался важнее.

Дальше спросят

Частые заблуждения

Практика

Две задачи. Сначала ответьте, потом сверьтесь с настоящим выводом: в обеих правильный ответ печатает сам скрипт расчёта.

print(f"{modulo:.1%}")
print(f"{ring_moved:.1%}")
print(f"{others:.1%}")

88.9%
11.7%
0.0%

11.1%
11.7%
0.0%

88.9%
11.7%
11.7%

88.9%
88.9%
0.0%

Проверка знаний