Consistent Hashing

Consistent Hashing (Согласованное хеширование) позволяет сократить негативное влияние (impact) на распределенную систему от добавления или удаления(отказ) серверов и более равномерно распределять данные или нагрузку в системе. Consistent hashing, например, используется в распределенных системах для партиционирования данных, а также в балансировщиках нагрузки. Например, Apache Cassadra, AWS Dynamo DB, Couchbase используют consistent hashing для партиционирования данных.

Рассмотрим работу hashing на примере балансировщиков нагрузки (Load Balancers). Допустим у нас есть три клиента: client 1, client 2, client 3 и четыре сервера: Server 1, Server 2, Server 3, Server 4. При помощи LB мы распределяем запросы от клиентов на сервера. Как это можно сделать? Простой алгоритм - round-robin. Мы, просто, первый запрос от любого клиента отправим на Server 1, второй запрос на Server 2, третий на сервер 3, четвертый снова на Server 1 и т.д. В чем недостатки такого подхода? Очень часто сервера выполняют запрос от клиента и кэшируют результат локально. Если придет такой же запрос, это позволит не выполнять его обработку снова, а просто вернуть значение из кэша. Round-robin однотипные запросы не будет отправлять на один и тот же сервер, он их будет поочередно отправлять на разные сервера. Т.е. если Server 1 выполнил запрос и закэшировал результаты и снова пришел такой же запрос, он будет отправлен на Server 2, который снова произведет обработку такого же запроса, вместо того, чтобы вернуть уже обработанное значение из кэша.

Т.е. хотелось бы отправлять одинаковые запросы на один и тот же сервер. Как это можно сделать? Можно использовать хеширование. Мы возьмем запрос, вычисли его hash(request) и на основе вычисленного хеша вычисли какой сервер должен его обработать. Это можно сделать, например, взяв остаток от деления на число серверов:

serverToHandleRequest = hash(request) % numberOfServers.

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

Но что делать, если сервер упал или мы хотим добавить новых серверов (если, например, выросла нагрузка на систему)? В таком случае numberOfServer изменится и все значения хешей "поплывут", запросы начнут отправляется на другие сервера, и кеши на всех серверах перестанут быть полезными.

Как можно уменьшить влияние на систему от добавления или удаления серверов? Ответ - consistent hashing.

Для этого мы вычисли hash для каждого сервера (например от его имени или ip-address): hash(Server1), hash(Server2), hash(Server3), hash(Server4). Расположим значения вычисленных хешей на окружности со значениями от 0 до максимального значения нашей хэш функции.

После этого проделаем такую же процедуру с клиентами, вычислим hash для клиентов и также их расположим на нашей окружности. Далее для каждого клиента найдем ближайший сервер на нашей окружности если смотреть по часовой стрелке. Будем отправлять запросы от клиента на сервер, который является ближайшим к нашему клиенту на данной окружности по часовой стрелке. Это позволит заасайнить каждого слиента на один и тот же сервер. Если же мы хотим асайнить не клиента на определенный сервер, а опредеденного типа запрос, то можно вместо hash клиента, вычислять hash запроса(hash(request)) и также расположить его на этой окружности. Логика будет абсолютно такая же.

Отлично. Давайте теперь посмотрим, что произойдет если мы захотели добавить новый сервер: Server 5. Мы вычислим hash(Server5) и также расположим его на нашей окружности. Теперь часть запросов будут приходить на этот сервер, для которых он ближайший на нашей окружности. При этом влияние на другие сервера будет минимальным.

Тоже самое произойдет если мы удалили сервер: Server 2 (или он отказал). При этом запросы просто пойдут на следующий доступный ближайший сервер по часовой стрелке.

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