Введение в согласованное хеширование

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

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

Основные концепции

Хеширование

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

• MD5 выдает 128-битные хеш-значения.
• SHA-1 производит 160-битные хеш-значения.
• и т.п.

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

Должен здесь важен. Наихудший сценарий - это столкновение. Конфликт - это когда два разных фрагмента данных имеют одно и то же хеш-значение. Давайте возьмем реальный пример, определив следующую функцию хеширования: для данного человека она возвращает дату его рождения (день и месяц рождения). Парадокс дня рождения говорит нам, что если в комнате находится всего 23 человека, вероятность того, что у двух человек будет один и тот же день рождения (следовательно, столкновение), составляет более 50%. Следовательно, функция дня рождения, вероятно, не является хорошей функцией хеширования.

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

• MD5 распределяет значения по 128-битной области пространства
• Хэш-таблица (или хэш-карта), поддерживаемая массивом из 32 элементов, имеет внутреннюю хеш-функцию, которая распределяет значения по любому индексу (от 0 до 31).

Распределение нагрузки

Распределение нагрузки можно определить как процесс распределения нагрузки по узлам. Термин узел здесь взаимозаменяем с сервером или экземпляром. Это вычислительная единица.

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

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

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

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

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

Mod-n хеширование

Принцип хеширования mod-n следующий. Каждый ключ хешируется с использованием хеш-функции для преобразования входных данных в целое число. Затем мы выполняем по модулю количество узлов.

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

Преимущество такого подхода - отсутствие гражданства. Нам не нужно сохранять какое-либо состояние, чтобы напоминать нам, что foo был направлен на узел 2. Тем не менее, нам нужно знать, сколько узлов настроено для применения операции по модулю.

Тогда как этот механизм работает в случае увеличения или уменьшения масштаба (добавления или удаления узлов)? Если мы добавим еще один узел, операция по модулю теперь будет основана на 4 вместо 3:

Как мы видим, ключи foo и baz больше не связаны с одним и тем же узлом. При хешировании mod-n нет никакой гарантии сохранения согласованности в ассоциации ключ / узел. Это проблема? Может.

Что, если мы реализуем хранилище данных с использованием сегментирования и на основе стратегии mod-n для распространения данных? Если мы масштабируем количество узлов, нам нужно выполнить операцию перебалансировки. В предыдущем примере ребалансировка означает:

• Перемещение foo из узла 2 в узел 0.
• Перемещение baz из узла 2 в узел 3.

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

• Распределение остается как можно равномерным на основе нового количества узлов.
• Количество ключей, которые мы должны перенести, должно быть ограничено. В идеале это было бы только 1 / n процентов ключей, где n - количество узлов.

Это как раз цель алгоритмов согласованного хеширования.

Однако термин «последовательный» может несколько сбивать с толку. Я встречал инженеров, которые предполагали, что такие алгоритмы продолжают связывать данный ключ с одним и тем же узлом, даже несмотря на масштабируемость. Это не тот случай. Он должен быть последовательным до определенного момента, чтобы обеспечить равномерное распределение.

А теперь пора заняться некоторыми решениями.

Свидание

Рандеву был первым алгоритмом, предложенным для решения нашей проблемы. Хотя в оригинальном исследовании, опубликованном в 1996 году, не упоминается термин согласованное хеширование, оно дает решение описанных нами проблем. Давайте посмотрим на одну из возможных реализаций на Go:

Как это работает? Мы проходим каждый узел и вычисляем его хеш-значение. Хеш-значение возвращается функцией hash, которая производит целое число на основе ключа (нашего ввода) и идентификатора узла (самый простой подход - хешировать конкатенацию двух строк). Затем мы возвращаем узел с наивысшим значением хеш-функции. Это причина, по которой алгоритм также известен как хеширование с наивысшим случайным весом.

Основным недостатком рандеву является его временная сложность O (n), где n - количество узлов. Это очень эффективно, если нам нужно ограниченное количество узлов. Тем не менее, если мы начнем обслуживать тысячи узлов, это может вызвать проблемы с производительностью.

Последовательный хэш кольца

Следующий алгоритм был выпущен в 1997 году Karger et al. В этом документе". В этом исследовании впервые упоминается термин согласованное хеширование.

В его основе лежит кольцо (массив с непрерывным соединением). Хотя это самый популярный алгоритм последовательного хеширования (или, по крайней мере, самый известный), принцип не всегда хорошо понимается. Давайте погрузимся в это.

Первая операция - это создание кольца. Кольцо имеет фиксированную длину. В нашем примере мы разбиваем его на 12 частей:

Затем мы размещаем наши узлы. В нашем примере мы определим N0, N1 и N2.

Узлы пока распределяются равномерно. Мы вернемся к этому вопросу позже.

Затем пора посмотреть, как представлять ключи. Во-первых, нам нужна функция f, которая возвращает индекс кольца (от 0 до 11) на основе ключа. Для этого мы можем использовать хеширование mod-n. Поскольку длина кольца постоянна, это не доставит нам никаких проблем.

В нашем примере мы определим 3 ключа: a, b и c. Наносим f на каждую. Предположим, у нас есть следующие результаты:

• f(a) = 1
• f(a) = 5
• f(a) = 7

Поэтому мы можем расположить ключи на кольце следующим образом:

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

В этом примере мы связываем a с N1, b и c с N2.

Теперь давайте посмотрим, как осуществляется ребалансировка. Мы определяем еще один узел N3. Где мы должны его разместить? Больше нет места для того, чтобы общее распределение было однородным. Стоит ли реорганизовать узлы? Нет, иначе мы бы перестали быть последовательными, не так ли? Чтобы позиционировать узел, мы повторно используем ту же хеш-функцию, которую мы представили f. Вместо вызова с помощью ключа его можно вызвать с помощью идентификатора узла. Таким образом, положение нового узла определяется случайным образом.

Тогда возникает один вопрос: что нам делать с a, поскольку следующий узел больше не N1:

Решение следующее: мы должны изменить его ассоциацию и получить a, связанный с N3:

Как мы обсуждали ранее, идеальный алгоритм должен перебалансировать в среднем 1 / n процентов ключей. В нашем примере, когда мы добавляем четвертый узел, у нас должно быть 25% возможных ключей, повторно связанных с N3. Так ли это?

• N0 из индексов с 8 по 12: 33,3% от общего количества ключей
• N1 из индексов со 2 по 4: 16,6% от общего числа ключей
• N2 из индексов с 4 по 8: 33,3% от общего числа ключей
• N3 от индексов 0 до 2: 16,6% от общего числа ключей

Распределение не равномерное. Как мы можем это улучшить? Решение - использовать виртуальные узлы.

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

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

В этом самом примере распределение теперь будет следующим:

• N0: 33.3%
• N1: 25%
• N2: 41.6%

Чем больше виртуальных узлов мы определяем для каждого узла, тем более равномерным должно быть распределение. В среднем, при 100 виртуальных узлах на сервер стандартное распределение составляет около 10%. При 1000 это около 3,2%.

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

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

Прежде чем двигаться дальше, интересно отметить, что иногда алгоритм можно существенно улучшить, изменив небольшую часть. Так обстоит дело, например, с алгоритмом, опубликованным Google в 2017 году, который называется согласованное хеширование с ограниченными нагрузками. Эта версия основана на той же идее кольца, которую мы описали. Тем не менее, их подход заключается в выполнении небольшой перебалансировки при любом обновлении (добавлении / удалении нового ключа или узла). Эта версия превосходит исходную с точки зрения стандартного отклонения за счет наихудшей временной сложности.

Перейти к согласованному хешу

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

Вот алгоритм на C ++ (7 строк кода 🤯):

В кольцевом хеш-коде с 1000 виртуальными узлами стандартное отклонение составляет около 3,2%. В хэше с согласованным переходом нам больше не нужна концепция виртуальных узлов. Тем не менее, стандартное отклонение остается менее 0,0000001%.

Однако есть одно ограничение. Узлы должны быть пронумерованы последовательно. Если у нас есть список серверов foo, bar и baz, мы не можем удалить, например, bar. Тем не менее, если мы настроим хранилище данных, мы можем применить алгоритм для получения индекса сегментов на основе общего количества сегментов. Следовательно, согласованный хэш-код может быть полезен в контексте сегментирования, но не для балансировки нагрузки.

Что такое идеальный алгоритм согласованного хеширования?

Поскольку теперь у нас есть некоторый опыт работы с последовательным хешированием, давайте сделаем шаг назад и посмотрим, какой алгоритм будет идеальным:

• В среднем будет переназначено только 1 / n процентов ключей, где n - количество узлов.
• Сложность пространства O (n), где n - количество узлов.
• Сложность времени O (1) на вставку / удаление узла и на поиск ключа.
• Минимальное стандартное отклонение, чтобы гарантировать, что узел не перегружен по сравнению с другим.
• Это позволило бы связать вес с узлом, чтобы справиться с разным размером узла.
• Это позволит произвольным именам узлов (не пронумерованным последовательно) поддерживать как балансировку нагрузки, так и сегментирование.

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

• Рандеву имеет линейную временную сложность на поиск.
• Кольцевой согласованный хэш имеет плохое минимальное стандартное отклонение без концепции виртуальных узлов. С виртуальными узлами сложность пространства равна O (n * v) с n количеством узлов и v количеством виртуальных узлов на узел. .
• Согласованный хэш перехода не имеет постоянной временной сложности и не поддерживает произвольные имена узлов.

Тема все еще открыта, и есть недавние исследования, на которые стоит обратить внимание. Например, многозондовый согласованный хеш, выпущенный в 2005 году. Он поддерживает сложность пространства O (1). Тем не менее, для достижения стандартного отклонения ε требуется время O (1 / ε) на поиск. Например, если мы хотим достичь стандартного отклонения менее 0,5%, потребуется хеширование ключа примерно 20 раз. Следовательно, мы можем получить минимальное стандартное отклонение, но с более высокой временной сложностью поиска.

Как мы уже говорили во введении, последовательные алгоритмы хеширования стали мейнстримом. Сейчас он используется в бесчисленных системах, таких как MongoDB, Cassandra, Riak, Akka и т. Д., Будь то в контексте балансировки нагрузки или распределения данных. Тем не менее, как это часто бывает в информатике, у каждого решения есть компромиссы.

Говоря о компромиссах, если вам нужно продолжение, вы можете взглянуть на отличный пост, написанный Дамианом Грыски:

Некоторые другие ресурсы, на которые стоит обратить внимание: