Кольцо хеширования - это алгоритм распределения ключей между множеством узлов (например, серверов, кешей, шардов БД) таким образом, чтобы минимизировать количество перестановок при добавлении или удалении узлов. А интересен он тем, что этот принцип широко используется в системах с распределённым хранением данных, например, в DynamoDB, Cassandra, Riak, а также в Memcached.
# Основные термины
- Хеш-пространство. Все возможные значения хеша (например, от 0 до 2³²−1 при использовании 32-битного хеш-функции) образуют кольцо - замкнутое пространство.
- Хеширование узлов. Каждый узел (сервер) получает одно или несколько значений в этом пространстве - они определяются с помощью хеш-функции от имени узла (например, hash("cache1")).
- Хеширование ключей. Каждый ключ (например, ID объекта) также хешируется и отображается на кольцо.
- Поиск узла для ключа. Ищется ближайший по часовой стрелке узел на кольце - он и будет ответственным за хранение данного ключа. Если не нашлось подходящего узла “вправо” - кольцо замыкается, и мы просто берём первый по кругу. Вот такая красивая логика.
# Как рассчитывается позиция узла
При добавлении нового узла, он перехватывает часть ключей у ближайших по кольцу узлов. Остальные остаются на месте. Таким образом изменения затрагивают только часть данных, а не все. Это повышает масштабируемость системы. При удалении узла аналогично - его ключи перераспределяются между оставшимися узлами, что также затрагивает только часть данных.
## Разберем на примере
Базовая реализация расчета позиции узла в кольце будет выглядеть так:
position = hash(node_id)
Где:
- node_id - уникальный идентификатор узла (например, `"node-1"`).
- hash() - детерминированная хеш-функция (например, **SHA1**).
Хеш-функция преобразует node_id в число из диапазона 0 до 2³²−1, где N количество бит хеша (например, 32 или 64). Это число и определяет позицию узла на кольце.
# считаем позиции
hash("node-A") = 132
hash("node-B") = 278
hash("node-C") = 75
Если добавляется "node-D" он встанет между A и B на кольце и запустится перераспределение части ключей.
hash("node-D") = 200
Чтобы избежать неравномерного распределения, часто применяют виртуальные узлы (virtual nodes):
hash("node-D#1")
hash("node-D#2")
hash("node-D#3")
Каждый виртуальный узел это просто хеш от строки с суффиксом. Это приводит к тому, что один физический узел будет представлен в нескольких местах на кольце - и получит ключи с разных участков, выравнивая нагрузку. Конечно, под капотом у реальных систем все гораздо сложнее, но у нас и нет цели тут построить DynamoDB.
Поиграться с симулятором consistent hashing можно тут https://consistent-hashing.simulators.devopsbrain.ru. В симуляторе вы можете добавить/удалить узлы, увидеть, как перераспределяются ключи.
UPD: оказывается версия на мобилках работала криво - поправил.
#simulators