Всем привет, я Сяофу~
Личный общедоступный номер:Внутри программатора, добро пожаловать на обучение и обмен
В последние два дня я видел, как маленький партнер в технической группе обсуждал вопрос алгоритма последовательного хеширования, и я просто придумал тему, о которой мне было нечего писать, поэтому я кратко представлю ее принцип. Ниже мы берем в качестве примера классические сценарии распределенного кэширования, а некоторые темы часто упоминаются в интервью, чтобы увидеть, что такое согласованный алгоритм хеширования и что он может предложить.
Создайте сцену
Предположим, у нас есть три номера кэш-сервераnode0,node1,node2, сейчас 30 миллионовkey, я надеюсь, что эти ключи можно будет равномерно закешировать на трех машинах, как вы думаете?
Первое решение, которое мы можем придумать, это алгоритм по модулюhash（key）% N, возьмите модуль после хеширования ключа, а N — количество машин. Результат после хэширования ключа по модулю 3, а результат должен быть 0, 1 или 2, что соответствует серверу.node0,node1,node2, вы можете напрямую найти соответствующий сервер для доступа к данным, что является простым и грубым и может полностью решить вышеуказанные проблемы.
хэш-проблема
Хотя алгоритм по модулю прост в использовании, использование по модулю числа машин имеет определенные ограничения при расширении и сужении кластера, поскольку обычно количество серверов корректируется в соответствии с размером бизнес-объема в производственной среде; и количество серверов После N измененийhash（key）% NСоответственно изменится и результат расчета.
Например: серверный узел не работает, формула расчета взята изhash（key）% 3сталhash（key）% 2, результат изменится.В это время, если вы хотите получить доступ к ключу, расположение ключа в кэше, скорее всего, изменится, и данные ранее кэшированного ключа также потеряют свою функцию и значение.
Одновременно выходит из строя большое количество кэшей, что приводит к лавинам кэша, что в свою очередь приводит к недоступности всей системы кэширования, что в принципе неприемлемо. в существование ~
Итак, как последовательный алгоритм хеширования решает вышеуказанные проблемы?
Согласованный хэш
Алгоритм согласованного хеширования также является алгоритмом по модулю, однако, в отличие от приведенного выше, который берет модуль по числу серверов, согласованный хеш принимает по модулю фиксированное значение 2 ^ 32.
Адреса IPv4 состоят из 4 групп 8-битных двоичных чисел, поэтому использование 2^32 может гарантировать, что каждый IP-адрес будет иметь уникальное сопоставление.
хэш кольцо
Мы можем абстрагировать эти 2^32 значения в кольцо⭕️(Если вы не хотите быть круглым, вы можете придумать форму и хорошо ее понять.), точка прямо над кольцом представляет 0, расположенный по часовой стрелке, и так далее, 1, 2, 3, 4, 5, 6... до 2^32-1, и это 2 точки в 32-й степени Кольца образовавшиеся вместе называютсяhash环.
Итак, какое отношение это кольцо хеширования имеет к согласованному алгоритму хеширования? Возьмем приведенный выше сценарий в качестве примера, три номера кэш-сервераnode0,node1,node2, 30 миллионовkey.
Карты серверов для хеш-кольца
В настоящее время формула расчета взята изхэш(ключ)%Nсталхэш(ip-адрес сервера)% 2^32, используйте IP-адрес сервера для вычисления хэша и используйте результат хеширования по модулю 2 ^ 32. Результат должен быть целым числом от 0 до 2 ^ 32-1, а позиция этого целого числа, отображаемого в хеш-кольце, представляет сервер , что в свою очередь будетnode0,node1,node2Три кэш-сервера сопоставлены с хэш-кольцом.
Ключи объекта сопоставляются с хэш-кольцами
Затем сопоставьте ключевой объект, который необходимо кэшировать, с хэш-кольцом,хэш(ключ)% 2^32, и серверный узел, и ключевой объект, подлежащий кэшированию, сопоставляются с хэш-кольцом. На каком сервере следует кэшировать объектный ключ?
Ключи объектов сопоставляются с серверами
Начиная с позиции ключа кэшированного объекта, первый сервер, обнаруженный в направлении по часовой стрелке, является сервером, на котором будет кэшироваться текущий объект..
Поскольку хэшированное значение кэшированного объекта и сервера является фиксированным, ключ объекта должен кэшироваться на фиксированном сервере при условии, что сервер остается неизменным. В соответствии с приведенными выше правилами отношение отображения на следующем рисунке:
key-1 -> node-1key-3 -> node-2key-4 -> node-2key-5 -> node-2key-2 -> node-0
Если вы хотите получить доступ к ключу, вам просто нужно использовать тот же метод расчета, чтобы узнать, на каком сервере кэширован ключ.
Преимущества согласованного хэша
У нас есть простое понимание принципа согласованного хеширования, так как же он оптимизирует добавление и уменьшение узлов в кластере, службу кеша, вызванную общим алгоритмом по модулю, и проблему масштабной недоступности?
Сначала рассмотрим сценарий расширения: если бизнес-объем резко возрастет, систему необходимо расширить, чтобы добавить сервер.node-4,только чтоnode-4сопоставляется сnode-1а такжеnode-2В промежутке узел сопоставления объектов в направлении по часовой стрелке обнаруживает, что исходный кэшnode-2объект наkey-4,key-5был переназначен наnode-4, и весь процесс расширения затрагивается толькоnode-4а такжеnode-1Небольшой фрагмент данных между узлами.
И наоборот, еслиnode-1Узел не работает, объект сопоставляется с узлом по часовой стрелке, а кэшnode-1объект наkey-1был переназначен наnode-4, данные, затронутые в это время, толькоnode-0а такжеnode-1часть данных между ними.
Из приведенных выше двух ситуаций можно сделать вывод, что при изменении количества серверов в кластере согласованный расчет хэша затронет только небольшую часть данных, гарантируя, что система кэширования в целом все еще может предоставлять услуги внешнему миру. .
проблема искажения данных
Для облегчения понимания принципа узлы на чертеже идеально и относительно равномерно распределены, но идеальные и реальные сцены часто сильно отличаются.Например, у меня есть фитнес-карта года, и я был только тренажерный зал дважды, и я только что принял душ.
ты хочешь тренироваться
Когда количество серверных узлов слишком мало, легко вызвать неравномерное распределение узлов.перекос данныхПроблема, как показано на рисунке ниже, большая часть кэшированных объектов кэшируется вnode-4На сервере ресурсы других узлов тратятся впустую, и большая часть системного давления сосредоточена наnode-4На узле такой кластер очень неработоспособен.
Решение проблемы перекоса данных также простое: нам нужно найти способ, чтобы узлы отображались в кольце хэшей относительно равномерно.
Алгоритм согласованного хеширования вводитвиртуальный узелМеханизм, то есть для вычисления нескольких хэш-значений для каждого узла сервера, они будут сопоставлены с хэш-кольцом, а ключи объектов, сопоставленные с этими виртуальными узлами, в конечном итоге будут кэшированы на реальном узле.
Обычно можно использовать хэш-вычисление виртуальных узлов, а IP-адрес соответствующего узла дополняется числовым числом.хэш (10.24.23.227#1)кстати, например, IP узла node-1 10.24.23.227, обычный расчетnode-1хэш-значение.
hash（10.24.23.227#1）% 2^32
Предположим, мы настроили три виртуальных узла для узла-1,node-1#1,node-1#2,node-1#3, хешируйте их по модулю.
hash（10.24.23.227#1）% 2^32hash（10.24.23.227#2）% 2^32hash（10.24.23.227#3）% 2^32
После того, как на следующем рисунке добавлены виртуальные узлы, исходные узлы относительно равномерно распределяются по хеш-кольцу, а нагрузка на оставшиеся узлы распределяется.
Но следует отметить, что чем больше виртуальных узлов выделено, тем более равномерным будет отображение на кольце хеширования, если узлов слишком мало, эффект увидеть сложно.
Введение виртуальных узлов также добавляет новые проблемы.Чтобы сделать сопоставление между виртуальными узлами и реальными узлами,对象key->虚拟节点->实际节点преобразование между.
Сценарии применения последовательного хеширования
Согласованное хеширование должно быть предпочтительным алгоритмом для балансировки нагрузки в распределенных системах.Его реализация является гибкой и может быть реализована либо на стороне клиента, либо в промежуточном программном обеспечении, таком как промежуточное программное обеспечение кэширования, которое часто используется ежедневно.memcachedа такжеredisКластеры используют его.
Кластер memcached особенный, строго говоря, его можно рассматривать только какпсевдокластер, поскольку его серверы не могут взаимодействовать друг с другом, маршрут распространения запроса полностью зависит от клиента, чтобы вычислить, на какой сервер должен попасть кэшированный объект, а его алгоритм маршрутизации использует согласованное хеширование.
Существует также концепция хеш-слотов в кластерах Redis.Хотя реализации разные, идеи остаются прежними.После прочтения согласованного хэша в этой статье вам будет намного легче понять Redis-слоты.
Есть много других сценариев применения:
-
RPCРамкаDubboИспользуется для выбора поставщиков услуг - Подтаблица подтаблицы распределенной реляционной базы данных: сопоставление отношений между данными и узлами
-
LVSпланировщик балансировки нагрузки - .....................
Суммировать
Хеш согласованности кратко объясняется. Если что-то не так, вы можете оставить сообщение, чтобы исправить это. Нет идеальных технологий. Алгоритм согласованного хеширования также имеет некоторые потенциальные скрытые опасности. Если количество узлов в кольце хеширования очень велико или часто обновляться, производительность поиска будет относительно низкой, а весь распределенный кеш нуждается в службе маршрутизации для балансировки нагрузки. После зависания службы маршрутизации весь кеш будет недоступен, и следует также учитывать высокую доступность.
Но, сказав это, пока это может решить проблему, это хорошая технология, и небольшой побочный эффект все еще терпим.