Шардирование, партиционирование и согласованное хеширование

Когда данные не влезают на одну машину, их режут на части и раскладывают по узлам.

Шардирование (sharding) — разбиение данных на части (шарды) и распределение их по разным серверам, чтобы каждый хранил и обслуживал только свою долю.

Зачем это нужно

Один сервер ограничен по диску, памяти и пропускной способности. Когда данных терабайты, а запросов тысячи в секунду, их делят между узлами. Каждый шард — это самостоятельная база со своей долей данных. Запрос идёт только на нужный шард, а не на все.

Стратегии разбиения

Стратегия	Как делим	Минус
По диапазону (range)	id 1–1М → шард A, 1М–2М → B	перекос: новые записи бьют в один шард
По хешу ключа	shard = hash(key) % N	при смене N переезжает почти всё
По справочнику (directory)	таблица «ключ → шард»	справочник — новая точка отказа

Выбор ключа шардирования

Ключ должен равномерно распределять нагрузку и совпадать с тем, по чему вы чаще всего ищете. Шардирование ленты по user_id хорошо, если запросы всегда «дай данные пользователя X». Плохой ключ порождает «горячий» шард — узел, на который приходится непропорционально много трафика (например, шард со знаменитостью-миллионником).

Проблема наивного хеша

Формула shard = hash(key) % N кажется удобной, но у неё фатальный изъян: при изменении числа узлов N (добавили или убрали сервер) меняется почти у всех ключей. Это значит массовый переезд данных и обвал кэша.

Было 4 узла:  hash(key) % 4
Стало 5 узлов: hash(key) % 5
→ ~80% ключей сменили узел = катастрофа

Согласованное хеширование (consistent hashing)

Решение — представить пространство хешей как кольцо (например, 0 … 2³²−1). И ключи, и узлы хешируются в точки на кольце. Ключ принадлежит первому узлу по часовой стрелке от своей точки.

Кольцо хешей (по часовой стрелке):

   [Node A]----key1----[Node B]----key2----[Node C]----key3----(назад к A)

key1 → ближайший по часовой = Node B
key3 → ближайший по часовой = Node A (через замыкание кольца)

Магия в том, что при добавлении узла переезжает только часть ключей между новым узлом и его соседом, а не все. При удалении — аналогично: ключи ушедшего узла достаются соседу, остальные не трогаются.

Событие	hash % N	Consistent hashing
Добавили узел	переезжает ~все ключи	переезжает ~1/N ключей
Убрали узел	переезжает ~все ключи	переезжают только ключи этого узла

Виртуальные узлы

Если каждый узел — одна точка на кольце, распределение получается неравномерным. Поэтому каждый физический узел представляют сотнями виртуальных точек на кольце. Тогда нагрузка размазывается ровно, а при падении узла его ключи расходятся по многим соседям, а не падают на одного. Этот приём используют Cassandra, DynamoDB, многие распределённые кэши.

Итог

Шардирование делит данные по узлам; ключ должен распределять нагрузку равномерно.
Наивный hash % N при смене числа узлов переселяет почти все ключи.
Consistent hashing переселяет лишь ~1/N ключей; виртуальные узлы выравнивают нагрузку.