Кольцо хеширования - это алгоритм распределения ключей между множеством узлов (например, серверов, кешей, шардов БД) таким образом, чтобы минимизировать количество перестановок при добавлении или удалении узлов. А интересен он тем, что этот принцип широко используется в системах с распределённым хранением данных, например, в 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. В симуляторе вы можете добавить/удалить узлы, увидеть, как перераспределяются ключи.