Что такое consistent hashing? Где применяется?
Подробный ответ
Проблема обычного хеширования
Если распределять ключи по формуле hash(key) % N, то при изменении числа серверов N меняется результат почти для каждого ключа. Это приводит к массовому перемещению данных и cache miss.
Идея consistent hashing
Ключи и серверы размещаются на хеш-кольце. Для ключа вычисляют его позицию на кольце и назначают его ближайшему серверу по часовой стрелке. При добавлении или удалении одного сервера перераспределяются только ключи из соседнего диапазона.
Hash ring
0 ----- Node A ----- Node B ----- Node C ----- 2^32
^
|
key hash
Key goes to the first node clockwise from its position.Virtual nodes
Один физический сервер может быть представлен несколькими virtual nodes на кольце. Это делает распределение ключей более равномерным и позволяет учитывать разную мощность серверов: более производительному узлу можно назначить больше virtual nodes.
Где применяется
распределённый cache, например sharding ключей между cache nodes;
NoSQL и распределённые хранилища;
маршрутизация запросов по user ID, tenant ID или ключу объекта;
распределённый rate limiter;
балансировка с сохранением привязки ключа к конкретному backend.
Репликация
Для устойчивости ключ можно хранить не на одном, а на нескольких следующих узлах кольца. Тогда при падении одного узла чтение и восстановление можно выполнить через реплики.
Ограничения
Consistent hashing уменьшает объём перемещаемых ключей, но не решает hot key problem: один популярный ключ всё равно может перегрузить назначенный ему узел. Для hot keys нужны репликация, локальный cache, request coalescing или отдельная стратегия распределения.
Как ответить на собеседовании
Consistent hashing размещает ключи и узлы на хеш-кольце. При добавлении или удалении сервера переносится только часть ключей, в отличие от hash(key) % N. Его применяют для шардирования cache и распределённых хранилищ; virtual nodes улучшают равномерность распределения, а репликация повышает отказоустойчивость.
Оцени свой прогресс