Перейти к основному содержимому

Консистентное хеширование

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

Проблема перехеширования​

Если у вас есть n кэш-серверов, распространенный способ балансировки нагрузки — использовать следующий метод хеширования:

serverIndex = hash(key) % N, где N — размер пула серверов.

Рассмотрим пример, чтобы понять, как это работает. Как показано в таблице 1, у нас есть 4 сервера и 8 строковых ключей вместе с их хешами.

ключхешхеш % 4
key0183586171
key1261435840
key2181311462
key3358634960
key4340858091
key5275817033
key6381649782
key7225303513

Таблица 1

Чтобы получить сервер, на котором хранится ключ, мы выполняем операцию по модулю f(key) % 4. Например, hash(key0) % 4 = 1 означает, что клиент должен обратиться к серверу 1, чтобы получить кэшированные данные. На рисунке 1 показано распределение ключей на основе таблицы 1.

Изображение показывает простую схему распределения ключей по четырем серверам с помощью консистентного хеширования. В верхней части приведена формула serverIndex = hash % 4, указывающая, что значение хеша ключа берется по модулю 4, чтобы определить номер сервера от 0 до 3. Ниже изображены четыре сервера (server 0, server 1, server 2, server 3) в виде цветных прямоугольников. Под ними показаны ключи (key1, key0, key2, key5, key6, key7), визуально связанные с соответствующими серверами на основе результата операции по модулю. В целом диаграмма иллюстрирует базовую стратегию балансировки нагрузки, при которой ключи распределяются по серверам при помощи хеш-функции.

Рисунок 1

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

ключхешхеш % 3
key0183586170
key1261435840
key2181311461
key3358634962
key4340858091
key5275817030
key6381649781
key7225303510

Таблица 2

На рисунке 2 показано новое распределение ключей на основе таблицы 2.

Изображение показывает простую схему распределения ключей по трем серверам. В верхней части приведена формула serverIndex = hash % 3, показывающая, что сервер определяется как остаток от деления значения хеша на 3. Ниже показаны столбцы с индексами серверов 0, 1 и 2, а также серверы server 0, server 1 и server 2. В разделе с ключами перечислены примеры ключей (key0, key1, key2, key3, key4, key5, key6), которые распределяются между серверами на основе своих хешей. Диаграмма концептуально показывает сопоставление ключей серверам при использовании операции по модулю.

Рисунок 2

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

Консистентное хеширование​

Согласно Wikipedia, «консистентное хеширование — это особый вид хеширования, при котором при изменении размера хеш-таблицы и использовании консистентного хеширования в среднем требуется переназначить только k/n ключей, где k — количество ключей, а n — число слотов. В отличие от этого, в большинстве традиционных хеш-таблиц изменение числа слотов массива приводит к переназначению почти всех ключей» [1].

Пространство хешей и хеш-кольцо​

Теперь, когда мы понимаем определение консистентного хеширования, давайте разберемся, как оно работает. Предположим, что в качестве хеш-функции f используется SHA-1, а диапазон выходных значений хеш-функции таков: x0, x1, x2, x3, …, xn. В криптографии пространство хешей SHA-1 простирается от 0 до 2^160 - 1. Это означает, что x0 соответствует 0, xn соответствует 2^160 - 1, а все остальные значения хеша посередине лежат между 0 и 2^160 - 1. На рисунке 3 показано пространство хешей.

Изображение показывает упрощенную диаграмму, иллюстрирующую обработку или преобразование данных. Длинный прямоугольник изображает систему или процесс. Слева стрелка с подписью x0 указывает на вход в систему, а справа стрелка с подписью xn указывает на выход из нее. Такая схема иллюстрирует линейное пространство значений от x0 до xn.

Рисунок 3

Если соединить оба конца, мы получим хеш-кольцо, как показано на рисунке 4:

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

Рисунок 4

Хеширование серверов​

Используя ту же хеш-функцию f, мы отображаем серверы на кольцо по IP-адресу сервера или его имени. На рисунке 5 показано, как 4 сервера отображаются на хеш-кольцо.

Изображение показывает концептуальную схему из четырех серверов (server 0, server 1, server 2, server 3), каждый из которых представлен цветным квадратом слева и узлом на кольце справа. Узлы s0, s1, s2, s3 соединены серой окружностью, образуя кольцевую топологию. Стрелка и подпись f(server 0) показывают, что серверы отображаются на кольцо при помощи хеш-функции.

Рисунок 5

Хеширование ключей​

Важно отметить, что используемая здесь хеш-функция отличается от той, что применялась в разделе «проблема перехеширования», и здесь нет операции взятия по модулю. Как показано на рисунке 6, 4 ключа кэша (key0, key1, key2 и key3) хешируются на хеш-кольцо.

Изображение показывает круговую схему компонентов архитектуры. Серая окружность служит основой, на которой расположены четыре цветных узла s0, s1, s2, s3, представляющих серверы, и четыре черных узла k0, k1, k2, k3, представляющих ключи. Все узлы размещены на кольце, что иллюстрирует сопоставление как серверов, так и ключей одному и тому же хеш-пространству.

Рисунок 6

Поиск сервера​

Чтобы определить, на каком сервере хранится ключ, мы движемся по кольцу по часовой стрелке от позиции ключа, пока не встретим сервер. Рисунок 7 объясняет этот процесс. Двигаясь по часовой стрелке, key0 хранится на server 0; key1 хранится на server 1; key2 хранится на server 2, а key3 хранится на server 3.

Изображение показывает кольцевую схему из серверов и ключей. Четыре цветных узла s0, s1, s2, s3 представляют серверы, а черные узлы k0, k1, k2, k3 представляют ключи. Черные стрелки показывают направление сопоставления: k0 указывает на s0, k1 — на s1, k2 — на s2, k3 — на s3. Слева дополнительно приведен список серверов в виде цветных блоков.

Рисунок 7

Добавление сервера​

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

На рисунке 8 после добавления нового server 4 перераспределить нужно только key0. k1, k2 и k3 остаются на тех же серверах. Давайте внимательнее посмотрим на логику. До добавления server 4 ключ key0 хранился на server 0. Теперь key0 будет храниться на server 4, потому что server 4 — первый сервер, который встречается при движении по часовой стрелке от позиции key0 на кольце. Остальные ключи, согласно алгоритму консистентного хеширования, не перераспределяются.

Изображение показывает круговую схему из серверов и ключей. Пять цветных узлов s0, s1, s2, s3, s4 представляют серверы 0–4, а черные узлы k0, k1, k2, k3 представляют ключи. Сплошная стрелка показывает, что k0 теперь сопоставляется с s4, а пунктирная стрелка указывает прежнее сопоставление k0 с s0. Диаграмма показывает, что при добавлении нового сервера перераспределяется только часть ключей.

Рисунок 8

Удаление сервера​

Когда сервер удаляется, при консистентном хешировании перераспределяется только небольшая часть ключей. На рисунке 9 при удалении server 1 только key1 должен быть переназначен на server 2. Остальные ключи не затрагиваются.

Изображение показывает кольцевую топологию с четырьмя серверами s0, s1, s2, s3 и четырьмя ключами k0, k1, k2, k3. Цветные узлы серверов расположены по дуге, а черные узлы ключей находятся между ними. Схема иллюстрирует, что после удаления одного сервера перераспределяется только небольшая часть ключей.

Рисунок 9

Две проблемы базового подхода​

Алгоритм консистентного хеширования был предложен Karger и соавторами из MIT [1]. Базовые шаги таковы:

  • Отобразить серверы и ключи на кольцо при помощи равномерно распределенной хеш-функции.

  • Чтобы выяснить, какому серверу соответствует ключ, двигаться по часовой стрелке от позиции ключа до первого найденного на кольце сервера.

У этого подхода есть две проблемы. Во-первых, невозможно сохранять одинаковый размер разделов на кольце для всех серверов, учитывая, что сервер может быть добавлен или удален. Раздел — это участок хеш-пространства между соседними серверами. Возможна ситуация, когда размер разделов на кольце, назначенных серверам, очень мал или, наоборот, довольно велик. На рисунке 10, если s1 удаляется, раздел s2 (выделен двунаправленными стрелками) становится в два раза больше, чем разделы s0 и s3.

Изображение показывает кольцевую схему из четырех серверов s0, s1, s2, s3, изображенных цветными кругами на сером кольце. Слева показан список серверов в виде цветных прямоугольников. Яркая розовая дуга подчеркивает, что один из разделов кольца становится значительно больше других, демонстрируя неравномерность размеров партиций после удаления сервера.

Рисунок 10

Во-вторых, на кольце может возникнуть неравномерное распределение ключей. Например, если серверы отображены в позиции, показанные на рисунке 11, большинство ключей будет храниться на server 2. При этом server 1 и server 3 не будут содержать данных.

Изображение показывает кольцевую схему серверов, где цветные узлы s0, s1, s2, s3 расположены по окружности неравномерно. Между ними есть дополнительные пустые позиции, а слева приведен список серверов. Такая диаграмма иллюстрирует ситуацию, в которой большая часть ключей оказывается на одном сервере, а другие серверы остаются без данных.

Рисунок 11

Для решения этих проблем используется техника, называемая виртуальными узлами или репликами.

Виртуальные узлы​

Виртуальный узел ссылается на реальный узел, и каждый сервер представлен на кольце несколькими виртуальными узлами. На рисунке 12 и server 0, и server 1 имеют по 3 виртуальных узла. Число 3 выбрано произвольно; в реальных системах количество виртуальных узлов намного больше. Вместо использования s0 мы применяем s0_0, s0_1 и s0_2 для представления server 0 на кольце. Аналогично, s1_0, s1_1 и s1_2 представляют server 1 на кольце. При использовании виртуальных узлов каждый сервер отвечает за несколько разделов. Разделами (дугами) с меткой s0 управляет server 0. С другой стороны, разделами с меткой s1 управляет server 1.

Изображение показывает архитектурную схему с двумя серверами (server 0 и server 1), использующими кольцевую топологию. На кольце расположены виртуальные узлы s0_0, s0_1, s0_2 для server 0 и s1_0, s1_1, s1_2 для server 1. Толстая серая линия изображает кольцо, а цветные участки показывают, какие разделы кольца относятся к каждому реальному серверу.

Рисунок 12

Чтобы определить, на каком сервере хранится ключ, мы движемся по часовой стрелке от позиции ключа и ищем первый виртуальный узел, встреченный на кольце. На рисунке 13, чтобы понять, где хранится k0, мы движемся по часовой стрелке от его позиции и находим виртуальный узел s1_1, который ссылается на server 1.

Изображение показывает архитектурную схему с двумя серверами server 0 и server 1 и кольцевой сетью. На кольце расположены шесть узлов: три фиолетовых узла s0_0, s0_1, s0_2 для server 0 и три голубых узла s1_0, s1_1, s1_2 для server 1. Отдельный черный узел k0 расположен рядом с кольцом. Диаграмма показывает, что ключ сопоставляется первому виртуальному узлу, найденному по часовой стрелке.

Рисунок 13

По мере увеличения числа виртуальных узлов распределение ключей становится более сбалансированным. Это связано с тем, что стандартное отклонение уменьшается при росте числа виртуальных узлов, что приводит к более равномерному распределению данных. Стандартное отклонение показывает, насколько сильно данные разбросаны. Результат эксперимента, описанного в материале [2], показывает, что при наличии ста или двухсот виртуальных узлов стандартное отклонение составляет от 5% (200 виртуальных узлов) до 10% (100 виртуальных узлов) от среднего значения. При увеличении количества виртуальных узлов стандартное отклонение становится еще меньше. Однако для хранения данных о виртуальных узлах требуется больше места. Это компромисс, и количество виртуальных узлов можно настраивать в соответствии с требованиями системы.

Поиск затронутых ключей​

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

На рисунке 14 server 4 добавляется на кольцо. Затронутый диапазон начинается с s4 (нового добавленного узла) и движется против часовой стрелки по кольцу, пока не встретится сервер (s3). Следовательно, ключи, расположенные между s3 и s4, должны быть перераспределены на s4.

Изображение показывает кольцевую схему из пяти серверов s0, s1, s2, s3, s4 и нескольких ключей. Серая дуга соединяет серверы по кругу, сплошная стрелка показывает новое сопоставление k0 с s4, а пунктирные стрелки обозначают прежние связи. Диаграмма иллюстрирует диапазон кольца, который затрагивается при добавлении нового сервера.

Рисунок 14

Когда сервер (s1) удаляется, как показано на рисунке 15, затронутый диапазон начинается в s1 (удаленном узле) и движется против часовой стрелки по кольцу, пока не встретится сервер (s0). Следовательно, ключи, расположенные между s0 и s1, должны быть перераспределены на s2.

Изображение показывает кольцевую топологию с четырьмя серверами s0, s1, s2, s3 и четырьмя ключами k0, k1, k2, k3. Слева приведен список серверов, а на кольце показано, какой участок и какие ключи затрагиваются при удалении сервера s1 и последующем перераспределении данных.

Рисунок 15

Подведем итоги​

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

  • При добавлении или удалении серверов перераспределяется минимальное число ключей.

  • Оно упрощает горизонтальное масштабирование, потому что данные распределяются более равномерно.

  • Оно смягчает проблему горячих ключей (hotspot key). Чрезмерное число обращений к конкретному шарду может привести к перегрузке сервера. Представьте, что данные о Katy Perry, Justin Bieber и Lady Gaga попали в один и тот же шард. Консистентное хеширование помогает смягчить эту проблему, распределяя данные более равномерно.

Консистентное хеширование широко используется в реальных системах, включая несколько известных примеров:

  • Компонент разбиения данных в базе данных Amazon Dynamo [3]

  • Разбиение данных по кластеру в Apache Cassandra [4]

  • Чат-приложение Discord [5]

  • Сеть доставки контента Akamai [6]

  • Сетевой балансировщик нагрузки Maglev [7]

Поздравляем, вы добрались до этого места! Теперь можно похлопать себя по плечу. Отличная работа!

Справочные материалы​

[1] Consistent hashing:
https://en.wikipedia.org/wiki/Consistent_hashing

[2] Consistent Hashing:
https://tom-e-white.com/2007/11/consistent-hashing.html

[3] Dynamo: Amazon’s Highly Available Key-value Store:
https://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf

[4] Cassandra - A Decentralized Structured Storage System:
http://www.cs.cornell.edu/Projects/ladis2009/papers/Lakshman-ladis2009.PDF

[5] How Discord Scaled Elixir to 5,000,000 Concurrent Users:
https://discord.com/blog/how-discord-scaled-elixir-to-5-000-000-concurrent-users

[6] CS168: The Modern Algorithmic Toolbox Lecture #1: Introduction and Consistent Hashing:
http://theory.stanford.edu/~tim/s16/l/l1.pdf

[7] Maglev: A Fast and Reliable Software Network Load Balancer:
https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/44824.pdf