Алгоритмы и структуры данных

Консистентное хеширование

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


Что такое хеширование?

Хеширование — это отображение некоторого множества объектов в множество чисел. Данная техника используется в хэш таблице, которая использует хэш значение ключа для доступа к нужному бакету. Более того, хэширование позволяет унифицировать способ доступа к произвольным данным.

В Java все объекты имеют метод hashCode(), который возвращает хэш для объекта.

Рехеширование

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

Самый тривиальный способ это сделать — это взять остаток от деления на N, где N — размер хэш-таблицы.

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

Консистентное хеширование

Вот мы и подошли к главной теме статьи. Консистентное хеширование позволяет нам при изменении размера бакетов рехешировать только K/N ключей в среднем, где K — количество ключей, а N — количество бакетов. Консистентное хеширование не зависит напрямую от количества серверов.

Консистетное хеширование — это класс функций, обладающих вышеописанным свойством, но самый популярный алгоритм — это консистентное хеширование на основе Hash Ring.

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

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

File:Consistent hashing.pdf
Consistent Hashing

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

Вес серверов

Чтобы распределить нагрузку с учетом мощности серверов, мы можем задать вес серверов. Имплементируется это с помощью так называемых Virtual Nodes. Это сервера, которые существуют на Hash Ring только виртуально, и любой маппинг в них отображается в действительный сервер.

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

При удалении сервера, должны будут быть также удалены все виртуальные сервера.

Консистентное хеширование: 2 комментария

  1. After I initially commented I appear to have clicked the -Notify me when new comments are added- checkbox and from now on every time a comment is added I get four emails with the exact same comment. Is there a means you can remove me from that service? Thank you! Alis Elroy Lightman

Добавить комментарий

Ваш адрес email не будет опубликован.