Хеш-слоты

Хеш-слоты (англ. hash slots) — это фиксированное количество логических разделов (слотов), на которые равномерно распределяется всё ключевое пространство хэш-функции в распределённых системах, использующих алгоритм согласованного хэширования. Каждый хеш-слот однозначно сопоставляется с определённым диапазоном значений хэш-функции и закрепляется за конкретным узлом кластера. Такая схема применяется для обеспечения масштабируемости, балансировки нагрузки и минимизации перемещения данных при добавлении или удалении узлов.

История и происхождение

Концепция хеш-слотов получила широкое распространение в середине 2000-х годов в связи с развитием распределённых баз данных и систем кэширования. Ключевым импульсом стало появление алгоритма согласованного хэширования (consistent hashing), предложенного Дэвидом Каргером и его коллегами в 1997 году. В первоначальной версии согласованного хэширования использовалось кольцо хэш-значений, где каждый узел отвечал за определённый диапазон. Однако на практике такая схема приводила к неравномерному распределению данных и сложностям при репликации.

В 2007 году компания Amazon представила распределённое хранилище Dynamo, где для балансировки нагрузки применялась виртуализация узлов (vNodes). В 2013 году компания Redis представила кластерную архитектуру Redis Cluster, которая ввела чёткое понятие хеш-слотов как фиксированного набора из 16384 логических разделов. Эта реализация стала стандартом де-факто для многих современных распределённых систем.

Принцип работы

Хэш-функция и слоты

В системах, использующих хеш-слоты, для каждого ключа данных вычисляется хэш-значение. Затем это значение отображается на один из фиксированного количества слотов (например, 16384 в Redis Cluster). Формула отображения обычно выглядит как:

`` slot = CRC16(key) mod 16384 ``

где CRC16 — циклический избыточный код (16-битная версия), а 16384 — количество слотов. Полученный номер слота определяет, на каком узле кластера будет храниться данный ключ.

Распределение слотов по узлам

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

Репликация

Для обеспечения отказоустойчивости каждый хеш-слот может иметь несколько реплик (копий), расположенных на разных узлах. В Redis Cluster, например, каждый слот имеет одну основную (master) реплику и одну или несколько резервных (slave) реплик. Если основной узел выходит из строя, одна из резервных реплик автоматически становится основной.

Классификация систем, использующих хеш-слоты

Хеш-слоты применяются в различных типах распределённых систем:

1. Системы управления базами данных (СУБД)

• Redis Cluster — использует 16384 хеш-слота. Каждый ключ отображается на слот, а слоты распределяются между узлами кластера. Поддерживает автоматическое перераспределение слотов при добавлении/удалении узлов.
• Apache Cassandra — использует виртуальные узлы (vNodes), которые по сути являются аналогом хеш-слотов. Количество vNodes настраивается администратором.
• Amazon DynamoDB — использует внутреннюю реализацию хеш-слотов для распределения данных по партициям.

2. Системы кэширования

• Memcached — в кластерных конфигурациях может использовать согласованное хэширование с хеш-слотами для распределения ключей.
• Varnish — HTTP-акселератор, использующий хеш-слоты для распределения запросов между серверами.

3. Распределённые файловые системы

• Ceph — использует CRUSH-алгоритм, который отображает объекты на хеш-слоты (PG — placement groups), а затем на OSD (объектные устройства хранения).

Характеристики и параметры

Количество слотов

В большинстве реализаций количество хеш-слотов фиксировано и не зависит от числа узлов. В Redis Cluster это 16384 (2^14), что обеспечивает хороший баланс между точностью распределения и накладными расходами на хранение метаданных. В Apache Cassandra количество vNodes может варьироваться от 256 до 4096 на узел.

Распределение слотов

Распределение может быть:

• Равномерным — каждый узел получает примерно одинаковое количество слотов.
• Взвешенным — узлы с большей производительностью получают больше слотов.
• Динамическим — система автоматически перераспределяет слоты в зависимости от нагрузки.

Перемещение данных

При изменении состава кластера (добавление/удаление узла) перемещаются только данные, относящиеся к перераспределяемым слотам. В Redis Cluster, например, при добавлении нового узла перемещается примерно 1/N часть данных (где N — количество узлов), что значительно меньше, чем при полном рехэшировании.

Применение

Балансировка нагрузки

Хеш-слоты позволяют равномерно распределять запросы между узлами кластера, так как ключи равномерно распределяются по слотам, а слоты — по узлам.

Масштабирование

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

Отказоустойчивость

Благодаря репликации слотов, выход из строя одного узла не приводит к потере данных — его слоты обслуживаются репликами на других узлах.

Шардирование

Хеш-слоты являются основой для шардирования (сегментирования) баз данных, позволяя распределять данные по нескольким серверам без необходимости в единой точке отказа.

Примеры реализации

Redis Cluster

В Redis Cluster каждый ключ отображается на один из 16384 хеш-слотов. Кластер может содержать до 1000 узлов. Распределение слотов хранится в метаданных кластера и обновляется при изменении топологии. Клиентские библиотеки (например, redis-py-cluster) автоматически определяют, на каком узле находится нужный слот, и направляют запрос напрямую.

Apache Cassandra

Cassandra использует виртуальные узлы (vNodes), каждый из которых соответствует хеш-слоту. Количество vNodes на узел настраивается параметром num_tokens. При добавлении нового узла система автоматически перераспределяет vNodes между всеми узлами, минимизируя перемещение данных.

Критика и ограничения

Неравномерное распределение

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

Сложность перераспределения

Хотя перемещение данных при изменении состава кластера меньше, чем при полном рехэшировании, оно всё равно требует значительных вычислительных и сетевых ресурсов, особенно при большом количестве данных.

Фиксированное количество слотов

В системах с фиксированным количеством слотов (например, 16384) невозможно изменить это число без полной остановки кластера и перераспределения всех данных. Это ограничивает гибкость при очень больших кластерах.

Зависимость от хэш-функции

Выбор хэш-функции влияет на равномерность распределения. Слабые хэш-функции могут приводить к коллизиям и неравномерному заполнению слотов.

Интересные факты

• Число 16384 (2^14) в Redis Cluster выбрано не случайно: оно достаточно велико для равномерного распределения, но при этом укладывается в 2 байта (16 бит), что упрощает хранение метаданных.
• В некоторых реализациях (например, в Amazon DynamoDB) хеш-слоты называются «партициями» (partitions), а их количество может автоматически увеличиваться при росте объёма данных.
• Алгоритм CRC16, используемый в Redis Cluster, не является криптостойким, но обеспечивает хорошее распределение для большинства практических случаев.

Источники

• Redis Cluster Specification (Redis Documentation)
• David Karger et al. "Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web" (1997)
• Giuseppe DeCandia et al. "Dynamo: Amazon's Highly Available Key-value Store" (2007)
• Apache Cassandra Documentation (vNodes)
• "Redis in Action" by Josiah L. Carlson (2013)