Основы дизайна систем: последовательное хеширование

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

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

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

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

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

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

request#1 => hashes to 34
request#2 => hashes to 23
request#3 => hashes to 30
request#4 => hashes to 14

// У вас есть 5 серверов => [Server A, Server B ,Server C ,Server D ,Server E]

// таким образом modulo 5 для каждого запроса...

request#1 => hashes to 34 => 34 % 5 = 4 => send this request to servers[4] => Server E

request#2 => hashes to 23 => 23 % 5 = 3 => send this request to servers[3] => Server D

request#3 => hashes to 30 => 30 % 5 = 0 => send this request to  servers[0] => Server A

request#4 => hashes to 14 => 14 % 5 = 4 => send this request to servers[4] => Server E

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

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

Добавление серверов и обработка отказавших серверов

Итак - что произойдет, если один из серверов, на которые мы отправляем трафик, умрет? Функция хеширования по-прежнему считает, что существует 5 серверов, а оператор по модулю генерирует диапазон от 0 до 4. Но у нас сейчас только 4 сервера, один из которых вышел из строя, и мы все еще отправляем ему трафик. Ой.

И наоборот, мы могли бы добавить шестой сервер, но он никогда не получит никакого трафика, потому что наш оператор модификации - 5, и он никогда не выдаст число, которое будет включать вновь добавленный 6-й сервер. Двойной ой.

// Добавим 6-й сервер
servers => [Server A, Server B ,Server C ,Server D ,Server E, Server F]

// давайте изменим операнд по модулю на 6
request#1 => hashes to 34 => 34 % 6 = 4 => send this request to servers[4] => Server E

request#2 => hashes to 23 => 23 % 6 = 5 => send this request to servers[5] => Server F

request#3 => hashes to 30 => 30 % 6 = 0 => send this request to  servers[0] => Server A

request#4 => hashes to 14 => 14 % 6 = 2 => send this request to servers[2] => Server C

Мы отмечаем, что номер сервера после применения мода изменяется (хотя в этом примере не для запроса №1 и запроса №3 - но это просто потому, что в данном конкретном случае числа рассчитывались таким образом).

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

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

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

Итак, очевидно, что простая система хеширования для выделения памяти плохо масштабируется и не справляется с ошибками.

Популярное решение - последовательное хеширование

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

При изучении последовательного хеширования следует помнить о двух очень важных вещах:

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

---

Читайте также:

• Основы дизайна систем: кеширование
• Основы дизайна систем: прокси
• Основы дизайна систем: балансировка нагрузки