Всем привет в этом “чате”. Решил немного разбавить материал новой рубрикой: “а как оно работает на самом деле” с отсылками к теоретической части различных технологий. И сегодня мы поговорим про кольцо хеширования (Consistent Hashing) и почему оно нам интересно. Также я навайбкодил симулятор и выложил его в конце статьи.

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