Всем привет, меня зовут Михаил Алексеев, я работаю программистом в студии ITT, пишу бэкенд на Java. Перформанс — это моя страсть, как и распределенные системы. Но еще больше я люблю, когда математика встраивается в перформансные цели и задумки.

В этом тексте я расскажу про разницу между Consistent и Rendezvous хэшированием, а также на примерах покажу, с какими проблемами мы сталкиваемся в работе.

В чем особенности Consistent хэширования

Начну с примера. Допустим, у нас был крутой Key Value Storage, который мы решили масштабировать из-за роста нагрузки. У нас есть клиент, который хочет положить в хранилище данные по ключу 24.

Как клиенту выбрать ноду, которая ответственна за этот ключ? Не будем рассматривать относительно странные варианты, которые скорее всего окажутся неэффективными. Например, когда мы с помощью Round-robin выбираем ноду, потом этот маппинг сохраняем и реплицируем на другие клиенты.

Я предлагаю просто взять и поделить 24 на количество нод — их четыре. И взять остаток от деления.

Мы получаем некоторый индекс. Скажем, если у нас синяя нода лежит по индексу 0, красная — по индексу 1 и так далее, то логично сделать вывод, что синяя нода ответственна за ключ 24. Ей отправляем значение по этому ключу. Она теперь его хранит. Результат этого деления является истиной для всех клиентов в мире для этого ключа.

Подобным образом 41 делим на 4, получаем единицу в остатке, отправляем на красную, таким же образом распределяем 15 на оранжевую, 34 на зеленую.

И если мы хотим получить значение по ключу 41, мы делим на 4, получаем остаток единицу, идем в красную ноду, забираем значение.

Приведенный выше подход — это по сути обычная HashMap, с которой все, вероятно, знакомы. Но все работает хорошо до того момента, пока оранжевая нода не выходит из строя.

Теперь, когда мы хотим получить значение 41, мы уже делим на 3, а не на 4. В остатке получаем 2. Идем в зеленую ноду, запрашиваем данные, а она ничего дать не может, так как маппинги сломались. И аналогичным образом они сломались бы, если бы новая нода встала в кластер.

Это совсем не то, чего мы хотели. Проблема в том, что при структурном изменении кластера происходит и структурное изменение массива — он уменьшается или увеличивается. Было бы здорово просто не трогать массив, но ведь нода упала (или добавилась новая), поэтому с ним нужно что-то сделать. С этим может помочь Consistent Hashing Ring.

Вот как это работает. Возьмем для примера какое-то число, допустим, 100. Теперь у нас есть диапазон всех наших возможных хэшей — [0; 100). Мы делим его на количество нод и получаем 4 диапазона, каждый из которых состоит из 25 элементов. Затем каждый диапазон маппим на ноду. Но не просто маппим, а как бы закручиваем эти диапазоны в кольцо. И теперь, если какая-то нода упадет, то ее диапазон подхватит нода из следующего диапазона.

Каждому диапазону назначим токен. Токен — это первый элемент диапазона (0, 25, 50, 75). Для того, чтобы определить, какая нода ответственна за некоторый ключ, возьмем остаток от деления ключа на 100 и с помощью бинарного поиска найдем ближайший к полученному остатку токен. Найденному токену соответствует какая-то нода — она и ответственна за этот ключ.

Но бинарный поиск, как известно, работает за логарифм. Логарифм — все еще очень хорошо, но раньше была возможность определять ноду за константу, поэтому упомяну возможный вариант оптимизации алгоритмической сложности в ущерб памяти: можно было бы создать массив из 100 элементов и разложить ноды в этот массив в соответствии с их диапазонами ([0; 24], [25; 49], ...). Тогда, посчитав хэш от ключа, можно просто извлечь ноду из массива по индексу, таким образом выполнив поиск за константу.

Вернемся к нашему примеру. Теперь клиент хочет положить значение по ключу 124. Делит на 100, получает в остатке 24. Это синяя нода, поэтому данные отправляются туда. Аналогичное происходит с ключами 141, 251, 378.

Когда оранжевая нода падает, а клиент хочет забрать значение по ключу 251, ничего не меняется. Мы опять делим на 100, получаем в остатке 51, идем к красной ноде, она отдает значение. А что с ключем 378? Он, как и все прочие ключи оранжевой ноды, теперь обрабатывается на следующей ноде по кругу. В нашем случае это синяя нода.

Не совсем понятно, что делать, если в кластер добавится новая нода. Тогда нам нужно будет как-то забрать часть диапазона у другой ноды. Но это не главная проблема.

Основной вопрос в том, почему упала оранжевая нода? Если это произошло из-за высокой нагрузки, то следом вся нагрузка перейдет на синюю — и она тоже может упасть. А потом может упасть и зеленая, и красная. Мы не можем такого допустить, поэтому надо искать другое решение.

Наши диапазоны получились не очень гибкими и удобными. Будет намного лучше, если каждый из них поделить на несколько небольших и раздать другим нодам. Но проблема в том, что у нас ровно четыре физические ноды — именно поэтому мы и делили на 4. Как же теперь маппить?

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

На гифке выше виртуальных нод получилось меньше, но принцип от этого не поменялся.

Все это работает по той же логике, что и раньше. 124 делим на 100, в остатке получаем 24. Ищем виртуальную ноду, которая ответственная за этот ключ — это синяя нода 22-27. Отправляем ключ туда. И так далее.

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

Зачем использовать Rendezvous хэширование

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

С Rendezvous клиент может посчитать хэш не просто от ключа 364, а хэш от пар. 364 и нода 1, 364 и нода 2. Так и делаем, считаем хэши. У нас получаются, допустим, вот такие значения.

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

Отмечу, что наибольший хэш от ключа 364 и ноды 1 будет максимальным у всех клиентов вообще. Подобным образом берем ключ 215, снова считаем хэши, сортируем массив, получаем максимальное и отправляем на ноду 2. Так же поступаем с 107 и 124.

Теперь, когда мы хотим получить значение, мы считаем хэши, сортируем, выбираем максимальное, забираем со второй ноды. И даже если нода 4 упадет, ничего не изменится — все еще максимальный хэш от пары 215 и 2.

А кто теперь ответственен за ключ 124? Чтобы ответить на этот вопрос, мы считаем хэши, сортируем массив, вычеркиваем выбывшую ноду и выбираем следующую из полученного списка.

Получается, что у нас бесплатно прямо в алгоритм заложено перераспределение ключей между нодами, причем оно скорее всего будет относительно честным, в отличие от консистентного. Не факт, что в этом списке для всех ключей после ноды 4 будет лежать нода 1. Может и 2, и 3. И какая-нибудь еще, если у нас их больше.

Есть и другие преимущества. Если мы решим, что первая нода в этом списке — это coordinator-нода, а другие — это реплики, то она сможет реплицировать значение на две следующие, когда получит ключ. То есть coordinator-нода тоже может посчитать эти хэши.

Либо клиент может сам взять и отправить значение сразу на три ноды, но ждать подтверждения только от двух из них, то есть осуществить запись по кворуму.

Но есть проблема — что будет, если добавится новая нода и при этом хэш для какого-то ее ключа станет максимальным в списке?

Ноду придется как-то прогревать. И в Consistent тоже придется это как-то делать. А чтобы понять, как прогревать, надо смотреть на характер нашей системы.

Если это распределенный кэш, то у него будет база данных. Мы сможем прогреть ноду из нее.

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

Раньше мы считали всего один хэш, а теперь считаем N. Для небольших кластеров это не будет проблемой, а для больших можно сделать за логарифм с помощью Skeleton вариации.

Итак, у нас 24 ноды — это вполне осязаемое N. Допустим, они разделены вот на такие кластеры.

Мы просто объединяем их в виртуальный скелет, в дерево.

Когда мы хотим что-то сделать с ключом 124, мы просто берем и рекурсивно применяем Rendezvous по дереву. То есть у виртуальной ноды 0 есть два ребенка — 1 и 2. Считаем два хэша, сортируем и выбираем максимальный.

Ключ 124 едет на виртуальную ноду 2.

Далее считаем хэши от детей ноды 2 и сортируем, выбираем максимальное.

Но считаем не просто от 1, 2 и 3, а от чисел, где старшим разрядом является номер текущей ноды, а младшим — номер дочерней ноды. Потому что на предыдущем шаге, когда мы были в ноде 0 и посчитали хэши, максимальным было с двойкой. И когда мы будем считать, единицу мы точно уже не выберем — у нас будет либо 2, либо 3. Это истина для всех ключей, которые попадут в виртуальную ноду 2. Часть нод просто мертвые. Это плохо, поэтому мы идем на небольшую хитрость, чтобы распределение было более случайным и ко всему был доступ. Соответственно, 124 едет в виртуальную ноду 1.

Тут точно так же считаем хэши, выбираем максимальное число.

И в итоге 124 обрабатывается на ноде 4. Логарифм. Девять хэшей вместо 24.

Если четвертая нода падает, мы уже знаем, что делать. Мы вычеркиваем ее и выбираем следующую из списка.

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

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

Но и у Rendezvous есть ответ на это — взвешенная Rendezvous вариация. Хотя у нее есть один недостаток: в Consistent мы можем вручную передавать виртуальные ноды, а в Rendezvous — нет.

Хоть подходы Consistent и Rendezvous решают одни и те же задачи за примерно одну и ту же стоимость, они значительно разнятся — особенно сильно это ощущается на практике.

В базовом варианте алгоритмическая сложность у Consistent лучше. Поэтому, скорее всего, для больших кластеров мы будем выбирать консистентный подход. Хотя у нас есть модификация в Rendezvous. На бесконечности просто логарифм недалеко уходит от константы, поэтому небольшая жертва за прочие плюсы зачастую бывает вполне оправдана. Также Consistent, вероятно, позволяет вручную балансировать нагрузку.

Вот что нам дает Rendezvous: прямо в алгоритме заложено равномерное распределение в случае структурного изменения кластера, а также простая натуральная репликация.

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