5 минут, чтобы понять последовательный алгоритм хеширования

предисловие

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

1 распределенный кеш

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

Простейшей стратегией оптимизации является сохранение часто используемых данных в Redis.Для достижения высокой доступности используется 3 Redis (кластер не настроен, требуется как минимум 6 кластеров). Каждый запрос Redis будет отправлен одному из них случайным образом, но эта стратегия вызовет следующие две проблемы:

• Одни и те же данные могут находиться в нескольких базах данных Redis, что приводит к избыточности данных.
• Определенный фрагмент данных уже существует в одной из баз данных Redis, но повторный доступ к базе данных Redis не затрагивает существующую базу данных. Нет гарантии, что все обращения к одному и тому же ключу отправляются в один и тот же Redis.

Для решения вышеуказанных проблем нам нужно немного изменить правила хранения ключей в Redis:Использовать хеш-алгоритмНапример, если есть три Redis, хеш-значение можно получить, вычислив хэш-значение для каждого доступа. Например, в формуле h=хэш(ключ)%3 мы устанавливаем номер Redis равным 0, 1, 2, чтобы сохранить значение, рассчитанное по соответствующему хешу, а значение h равно числу, соответствующему Redis. Однако алгоритм хеширования также сталкивается с проблемами отказоустойчивости и масштабируемости. Отказоустойчивость означает, что сбой службы в системе не может повлиять на другие системы. Масштабируемость означает, что при добавлении новых серверов вся система может работать правильно и эффективно.

Предположим теперь, что сервер Redis не работает, тогда, чтобы заполнить вакансию, неработающий сервер должен быть удален из нумерованного списка, а следующие серверы будут перемещены вперед на одну позицию по порядку, а их числовое значение будет уменьшено на единицу. В это время каждый ключ необходимо пересчитать согласно h = Hash(key) % 2.

Точно так же, если добавляется новый сервер, правила также необходимо пересчитать, h = Hash(key) % 4. Следовательно, если в системе произойдет смена сервера, это напрямую повлияет на значение хэша, и большое количество ключей будет перенаправлено на другие серверы, что приведет к более низкой частоте попаданий в кэш, что очень плохо в распределенной системе.

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

2. Последовательный алгоритм хеширования

Согласованное хеширование — это специальный алгоритм хеширования. После использования последовательного алгоритма хеширования изменение количества слотов (размера) хеш-таблицы требует в среднем только переназначения K/n ключей, где K — количество ключей, а n — количество слотов. Однако в традиционной хэш-таблице добавление или удаление слота требует переназначения почти всех ключей.

Проще говоря, согласованное хеширование организует все пространство хэш-значений в виртуальное кольцо, например, при условии, что пространство значений хеш-функции H равно 0-2^32-1 (хеш-значение представляет собой 32-битное целое число без знака). , все кольцо хеш-пространства выглядит следующим образом:

Все пространство организовано по часовой стрелке, а 0 и 2^32-1 совпадают в направлении нулевой точки.

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

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

Например, у нас есть четыре объекта данных A, B, C и D. После вычисления хеш-функции их положение на кольцевом пространстве выглядит следующим образом:

В соответствии с последовательным алгоритмом хеширования данные A будут назначены Серверу 1, данные B будут назначены Серверу 2, а C и D будут назначены Серверу 3.

3 Отказоустойчивость и масштабируемость

А как насчет отказоустойчивости и масштабируемости при использовании согласованного алгоритма хеширования?

3.1 Отказоустойчивость

Что делать, если RedisService2 выйдет из строя?

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

3.2 Расширяемость

Давайте рассмотрим другую ситуацию.Если вы добавляете сервер Redis4, конкретное расположение показано на следующем рисунке:

Исходные данные C были сохранены в Redis3, но из-за добавления Redis4 данные C были сохранены в Redis4. Нарушается только Redis3, остальные данные не затрагиваются.

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

4 виртуальных узла

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

Например, в нашей системе есть два Redis, и позиции распределенного кольца показаны на следующем рисунке:

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

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

Конкретный метод может быть реализован путем добавления числа после IP-адреса сервера или имени хоста.Например, в приведенном выше случае к каждому сервисному узлу можно добавить три виртуальных узла, поэтому их можно разделить на RedisService1#1, RedisService1#2 , RedisService1#3, RedisService2 #1, RedisService2#2, RedisService2#3, конкретные расположения показаны на следующем рисунке:

Хэш-алгоритм позиционирования данных остается без изменений, но добавляется отображение виртуальных узлов на реальные узлы. Например, данные C сохраняются в виртуальном узле Redis1#2, но фактически данные сохраняются в Redis1. Таким образом может быть решена проблема неравномерности данных при небольшом количестве сервисных узлов. В практических приложениях количество виртуальных узлов обычно устанавливается равным32 или больше, так что даже еслимало сервисных узловтакже может быть относительноРавномерное распределение данных.

Суммировать

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

---

Фан Цин

Группа разработчиков Java компании Guangzhou Reed Technology

Reed Technology-Guangzhou Professional Internet Software Service Company

Ухватитесь за каждую деталь и создайте каждую красоту

Подпишитесь на наш официальный аккаунт, чтобы узнать больше

Хотите сразиться с нами? лагу поиск"Рид Технология"Или отправьте свое резюме наserver@talkmoney.cnПрисоединяйтесь к нам

Следите за нами, ваши комментарии и лайки - наша самая большая поддержка