Как мы эффективно реализуем согласованное хеширование

задняя часть сервер алгоритм Программа перевода самородков

Платформа Ably для работы в режиме реального времени распределена по более чем 14 физическим центрам обработки данных и более чем 100 узлам. Чтобы гарантировать, что нагрузка и данные могут быть равномерно и последовательно распределены по всем узлам, мы используем согласованный алгоритм хеширования.

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

Давайте снова поговорим о хешировании

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

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

location = hash(key) mod size

В таком случае, почему мы не можем обрабатывать сетевые запросы таким же образом?

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

Теперь давайте сделаем шаг назад. В традиционных методах хеширования мы всегда предполагаем:

  • количество ячеек памяти известно, и
  • Это количество никогда не меняется

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

перед изменением узла

После изменения узла

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

Консистентное хеширование — что это?

Непротиворечивое хеширование можно описать следующим образом:

  • Он использует виртуальную кольцевую структуру для представления запрашивающих ресурсы (для удобства описания позже он будет называться «запрос») и серверных узлов, это кольцо обычно называютhashring.
  • Количество мест хранения больше не является детерминированным, но мы предполагаем, что на этом кольце бесконечно много точек и что серверные узлы могут быть размещены в любом месте кольца. Конечно, мы по-прежнему можем использовать хеш-функцию для выбора этого случайного числа, но второй шаг, деление на количество мест хранения, опущен, потому что количество мест хранения больше не является конечным числом.
  • Запросы, такие как пользователи, компьютеры или бессерверные программы, которые эквивалентны ключам в традиционных методах хеширования, также размещаются в том же кольце с использованием той же хэш-функции.

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

Теоретически каждый сервер «владеет» диапазоном хеширования, и любой запрос, сопоставленный с этим диапазоном, будет обслуживаться одним и тем же сервером. Итак, что если один из серверов выйдет из строя, возьмем в качестве примера узел 3, на этот раз диапазон адресов следующего узла сервера в кольце будет расширен, и любые запросы, которые сопоставляются с этим диапазоном, будут отправлены на новый сервер. . Это все. Только хэши в диапазоне, соответствующем отказавшему узлу, должны быть перераспределены, в то время как остальная часть хэш-кольца и распределения сервера запросов остаются неизменными. Это полная противоположность традиционному хэшированию, когда изменения размера хеш-таблицы могут повлиять навсеотображение. потому что этоСогласованное хеширование, только часть (это связано с коэффициентом распределения кольца) запросов будут затронуты известными изменениями кольца хэширования. (Добавление или удаление узлов приведет к изменению кольца, что приведет к изменению некоторых сопоставлений сервера запросов.)

эффективная реализация

Теперь, когда мы знакомы с тем, что такое хэш-ринг...

Нам нужно реализовать следующее, чтобы заставить его работать:

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

карта

Чтобы завершить первую часть выше, нам нужно следующее:

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

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

  • Массив хэшей, которые однозначно соответствуют узлам кольца.
  • Граф (хеш-таблица), используемый для поиска серверных узлов, соответствующих известным запросам.

На самом деле это примитивное представление упорядоченного графа.

Чтобы иметь возможность найти узел в приведенной выше структуре данных, который может обслуживать известное значение хеш-функции, нам нужно:

  • Выполните модифицированный двоичный поиск, чтобы найти первый узел в массиве, который равен или больше (≥) запрашиваемого хеш-значения — хэш-карты.
  • Найдите найденный узел в графе — тот, который соответствует хеш-карте.

Добавить или удалить узлы

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

Как найти те запросы, на которые повлияла смена хеш-кольца?

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

Однако объем работы, необходимой для этого, увеличивается по мере увеличения количества запросов на узле. Что еще хуже, по мере увеличения количества узлов количество изменений в кольце также может увеличиваться. В худшем случае, поскольку изменения кольца часто связаны с локальными отказами, переходные нагрузки, связанные с изменением кольца, могут также увеличить вероятность отказа других затронутых узлов, что может привести к каскадным отказам во всей системе.

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

Эффективный поиск затронутых хэшей

Добавление или удаление узла из кластера изменит распределение некоторых запросов в кольце, которое мы называемПораженная область(affected range). Если мы знаем границы затронутого диапазона, мы можем перенаправить запрос в нужное место.

Чтобы найти границы затронутого диапазона, мы начинаем с хеш-значения H узла, который был добавлен или удален, и движемся назад по кольцу от H (против часовой стрелки на диаграмме), пока не будет найден другой узел. Определим хеш-значение этого узла как S (для начала). Запросы, идущие против часовой стрелки от этого узла, будут назначены ему (S), поэтому они не будут затронуты.

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

Запросы, содержащие хэши между найденным узлом и диапазоном добавленных (или удаленных) узлов, необходимо переместить.

Эффективно находить запросы в затронутой области

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

Что-то вроде этого в JavaScript:

for (const request of requests) {
  if (contains(S, H, request.hash)) {
    /* 这个请求受环变化的影响 */
    request.relocate();
  }
}
function contains(lowerBound, upperBound, hash) {
   const wrapsOver = upperBound < lowerBound;
   const aboveLower = hash >= lowerBound;
   const belowUpper = upperBound >= hash;
   if (wrapsOver) {
     return aboveLower || belowUpper;
   } else {
     return aboveLower && belowUpper;
   }
}

Поскольку хеш-кольцо является циклическим, недостаточно найти запросы между S contains()может справиться с этой ситуацией.

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

Однако по мере увеличения количества запросов на узле увеличивается и объем требуемой работы, и, что еще хуже, смена кольца также может происходить чаще по мере увеличения узлов либо из-за автоматического масштабирования узла (запуск параллельной нагрузки в системе). для перебалансировки запросов на доступ в случае автоматического масштабирования) или отработки отказа.

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

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

Это позволяет нам настроить таргетинг на все запросы в затронутой области, выполнив следующие действия:

  • Найдите первый запрос, начинающийся с S.
  • Идите по часовой стрелке, пока не найдете значение хеш-функции за пределами этого диапазона.
  • Переместите запросы, попадающие в этот диапазон.

При обновлении хэша среднее количество запросов для прохождения равно R/N, R – количество запросов, находящихся в пределах диапазона этого узла, а N – количество значений хеша на кольце. Здесь мы предполагаем, что запросы распределяются равномерно.

Давайте применим приведенное выше объяснение на рабочем примере:

Предположим, у нас есть кластер с узлами A и B.

Давайте случайным образом сгенерируем «хэш-назначение» каждого узла: (при условии, что хэш 32-битный), поэтому мы получим

A:0x5e6058e5

B:0xa2d65c0

Здесь мы помещаем узлы в виртуальное кольцо, значение0x0,0x1и0x2...последовательно размещаются на кольце до тех пор, пока0xffffffff, так после оборачивания круга вокруг кольца0xffffffffс последующим0x0.

Поскольку хэш узла A0x5e6058e5, который отвечает за0xa2d65c0+1прибыть0xffffffff, и из0x0прибыть0x5e6058e5Любой запрос в области действия, как показано на следующем рисунке:

С другой стороны, B отвечает за0x5e6058e5+1прибыть0xa2d65c0диапазон. Таким образом, все хеш-пространство делится.

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

Например, нам нужно найти (или создать) новый запрос с идентификатором «bobs.blog@example.com».

  1. Вычисляем хеш H этого тождества, например, получаем0x89e04a0a
  2. Мы ищем первый узел на кольце с хэшем больше H. Здесь мы находим Б.

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

Этот пример слишком упрощен. В практических ситуациях предоставление только одного хэша на узел может привести к очень неравномерному распределению нагрузки. Вы могли заметить, что в этом примере B отвечает за(0xa2d656c0-0x5e6058e5)/232 = 26.7%, а за все остальное отвечает А. В идеале каждый узел мог бы отвечать за часть кольца одинакового размера.

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

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

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

A:0x5e6058e5

B:0xa2d65c0

C:0xe12f751c

в настоящее время,0xa2d65c0 + 1и0xe12f751cКольцевое пространство между (ранее часть A) выделяется для C. Все остальные запросы продолжают хэшироваться на тот же узел, что и раньше. Чтобы обработать изменение ответственности узла, все запросы в этой области, уже назначенные A, должны передать все свое состояние C.

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

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

Создавать распределенные системы сложно. Но мы любим это, и мы любим говорить об этом. Выберите Ably, если вам нужно полагаться на распределенную систему. Если вы хотите поговорить с нами, свяжитесь с нами!

Особая благодарность инженеру по распределенным системам Ably.John DiamondВклад в эту статью.

Сруштика этоAbly Realtimeконсультант по разработке программного обеспечения

благодарныйJohn DiamondиMatthew O'Riordan.

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

Программа перевода самородковэто сообщество, которое переводит высококачественные технические статьи из Интернета сНаггетсДелитесь статьями на английском языке на . Охват контентаAndroid,iOS,внешний интерфейс,задняя часть,блокчейн,продукт,дизайн,искусственный интеллектЕсли вы хотите видеть более качественные переводы, пожалуйста, продолжайте обращать вниманиеПрограмма перевода самородков,официальный Вейбо,Знай колонку.

Категории