Обзор
Здесь есть сценарий.Когда сервис предоставляется совместно несколькими группами серверов, на какой сервис должен быть перенаправлен ключ.Если здесь используется наиболее распространенный метод key%N (N — количество серверов), проблем нет на первый взгляд. Однако, когда количество отправленных серверов увеличивается или уменьшается, метод распределения становится ключевым% (N + 1) или ключевым% (N-1). Здесь будет большое количество миграций сбоя ключа, если backend key соответствует stateful Несомненно, такой подход приведет к большому объему миграции данных между серверами, что приведет к нестабильности сервиса.Для решения проблемы класса появился алгоритм консистентного хеширования.
1. Особенности алгоритма последовательного хеширования
В распределенном кэше хороший алгоритм хеширования должен соответствовать следующим условиям:
-
Остаток средств
Баланс в основном означает, что благодаря распределению алгоритмов каждый узел в кластере должен быть максимально сбалансированным. -
монотонность
Монотонность в основном относится к ключу, который был выделен старому узлу при изменении кластера, и по-прежнему выделяется предыдущему узлу, насколько это возможно, чтобы предотвратить миграцию большого объема данных.Общий хеш-модуль здесь трудно удовлетворить этому точка и согласованность. Алгоритм хеширования может управлять количеством ключей, которые необходимо перенести на низкий уровень. -
Распространение
Децентрализация в основном для одного и того же ключа.При работе на разных клиентах количество кластеров кеша, полученных клиентом, может быть несогласованным, что приводит к проблеме сопоставления ключей с разными узлами, что вызовет несогласованность данных.Алгоритмы хеширования должны избегать децентрализации как можно больше. -
Нагрузка
Нагрузка в основном связана с кешем, один и тот же кеш может быть сопоставлен пользователем с разными ключами, что приводит к несогласованному состоянию кеша.
С принципиальной точки зрения алгоритм согласованного хеширования имеет разумное решение вышеуказанных проблем.
2. Хеш согласованности Подробно
Основная идея последовательного хеширования состоит в том, чтобы выполнить хеш-операцию над ключом и округлить его по определенному правилу, чтобы получить значение между 0-2^32-1, размер кольца 2^32, и целочисленное значение, вычисленное с помощью ключа, является ключом. Позиция в хеш-кольце, как сопоставить ключ с узлом, здесь разделена на два этапа. Первым шагом является вычисление ключа службы в соответствии с алгоритмом хеширования, чтобы получить позицию службы в согласованном кольце хеширования. Второй шаг заключается в использовании того же метода для вычисления положения кэшированного ключа в хэш-кольце и по часовой стрелке для поиска первого служебного ключа, который больше или равен положению хэш-кольца, чтобы получить сервер которому необходимо назначить ключ.
Как показано на рисунке, каждый ключ назначается каждому узлу в соответствии с алгоритмом хеширования.При сбое узла, например, УЗЛА 2, ключ на УЗЛЕ 2 будет выделен соседнему узлу в кольце хеширования, в то время как позиции остальные ключи остаются без изменений.
Виртуальные узлы улучшают баланс
Как видно из приведенного выше рисунка, так как узлов всего 3, вокруг расположения некоторых узлов имеется большое количество хеш-поинтов, так что этим узлам назначается больше ключей, чем другим узлам, что вызовет нагрузку на каждый узел в кластере должен быть несбалансированным., для решения этой проблемы вводится виртуальный узел, то есть реальный узел соответствует нескольким виртуальным узлам. При сопоставлении кэшированного ключа сначала найдите соответствующий виртуальный узел, а затем сопоставьте его с реальным узлом. Как показано на рисунке ниже, каждый узел виртуализирует два виртуальных узла для улучшения баланса.
3. Сравнение алгоритмов последовательного хеширования и других алгоритмов
Для проблемы распределения узлов кэшированных ключей данных в кластере существует несколько решений, таких как простое хэширование по модулю, сопоставление слотов и согласованное хеширование.
-
хэш по модулю
Для хеш-модуля проблем с балансом нет, но если в кластер добавить новый узел, доступность данных будет N/(N+1) Чем больше значение N, тем выше частота отказов. Это явно неприемлемо. -
карта слотов
Этот алгоритм используется Redis, Идея состоит в том, чтобы выполнить определенную операцию над значением ключа (например, crc16, crc32, hash), получить целочисленное значение, а затем взять значение и фиксированное количество слотов по модулю (слотов), и каждый узел обрабатывает фиксированные слоты. При получении узла, где находится ключ, сначала вычислить соответствующую связь между ключом и слотом, а затем найти узел через соответствующую связь между слотом и узлом, Здесь каждый раз, когда добавляется узел, только ключ соответствующий определенному слоту, необходимо перенести, а значение ключа перенесенного слота не будет эффективным, что снижает эффективную эффективность до 1/(N+1). Однако недостатком этого метода является то, что все узлы должны знать соответствие между слотами и узлами, и если клиент не сохраняет соответствие между слотами и узлами, ему необходимо реализовать логику перенаправления. -
Согласованный хэш
Непротиворечивое хэширование Как уже упоминалось выше, вероятность отказа при добавлении нового узла составляет всего 1/(N+1), что в наибольшей степени снижает фактическую эффективность за счет согласованного хеширования. При этом, по сравнению с методом отображения слотов, нет необходимости вводить слоты для промежуточного соответствия, что в наибольшей степени упрощает реализацию.
4. Реализация согласованного алгоритма хеширования на основе golang
Здесь используется golang для достижения согласованного хэширования, учитывая, что в сценариях реального использования конфигурация машин между сервисными узлами может быть разной, поэтому предусмотрена логика перераспределения виртуальных узлов на основе веса узла, чтобы максимизировать количество узлов с большой вес.Несут некоторые ключи, в то время как узлы с малым весом несут меньше ключей.Конечно, вычисление весов также включает в себя много вещей.Смотрите код:hashring
5. Резюме
В этой статье анализируется принцип согласованного хеширования и сравнивается его с другими алгоритмами распределения распределенного кластера.С точки зрения распределенного кэширования, две хорошо известные системы распределенного хранения redis и memcached используют сопоставление слотов, и из-за различных используемых алгоритмов, ряд действий, инициируемых при изменении узлов в кластере, также отличается, и у каждого есть свои особенности.