Sharding Connections

Discord обслуживает 19 миллионов одновременных соединений. Один сервер физически не вместит их все - но как разбить миллионы WebSocket-соединений так, чтобы сообщения внутри guild'а не прыгали между серверами?

• Discord guild sharding: shard_id = guild_id % total_shards. Все участники одного guild'а подключаются к одному шарду, fan-out сообщений - локальный, без межсерверного трафика.
• Slack workspace routing: при подключении клиента API gateway читает из Redis, на каком шарде живёт workspace, и проксирует WebSocket-соединение через internal load balancer на нужный шард.
• Consistent hashing в WebSocket-кластерах: при добавлении нового шарда перераспределяется только 1/N соединений вместо полного reshuffling - graceful rebalancing без массовых дисконнектов.
• Hot shard problem у Discord: guild с 500 000 участниками перегружает один шард. Решение - large guild exception: такие guild'ы выносятся на выделенные шарды с увеличенными ресурсами.

Consistent Hashing

Consistent hashing - это алгоритм распределения нагрузки, при котором и ключи, и серверы размещаются на одном кольце хешей (hash ring). Для нахождения сервера к которому принадлежит ключ, движение идёт по кольцу до ближайшего сервера по часовой стрелке. Ключевое свойство: при добавлении или удалении одного сервера перераспределяется только 1/N ключей, а не все.

Обычный модульный хеш (userId % N) при изменении N перераспределяет почти все ключи. Consistent hashing решает именно эту проблему - при добавлении сервера перемещается в среднем K/N ключей (K - число ключей, N - число серверов).

• Virtual nodes (vnodes): каждый физический сервер занимает несколько позиций на кольце - выравнивает нагрузку при неравномерном распределении
• Replica factor: каждый ключ может реплицироваться на следующие N серверов по кольцу для отказоустойчивости
• Lookup complexity: O(log N) при бинарном поиске по отсортированному массиву позиций серверов

Connection Sharding

Connection sharding - распределение WebSocket-соединений по нескольким серверам (шардам) таким образом, чтобы соединения одной логической единицы (guild, workspace, chat room) оказались на одном шарде. Это позволяет доставлять события внутри одной единицы без межсерверной рассылки.

Discord применяет guild sharding: каждый guild получает shard_id = guild_id % num_shards. Все участники guild'а при подключении направляются на один и тот же шард. Когда участник A отправляет сообщение в guild, сервер-шард уже имеет соединения со всеми участниками этого guild'а и рассылает событие без обращения к другим шардам.

Slack использует иной подход: workspace-based sharding. Каждый workspace (team) закреплён за шардом через lookup-таблицу в Redis. При подключении клиента API gateway читает Redis, находит нужный шард и проксирует WebSocket-соединение через internal load balancer.

• User-ID sharding: userId % N - простейший вариант, но соединения одного канала разлетаются по разным шардам
• Room/guild sharding: shardId = hash(roomId) % N - все участники одной комнаты на одном шарде, fan-out локальный
• Hybrid: user подключается к ближайшему шарду, а события между шардами маршрутизируются через pub/sub (Redis Streams)

Rebalancing

Rebalancing - перераспределение соединений между шардами при изменении их числа или при возникновении hot shard (один шард перегружен, остальные простаивают). WebSocket соединения - это stateful, long-lived connections, поэтому rebalancing значительно сложнее, чем для stateless HTTP.

Hot shard возникает, когда один объект (guild, workspace) несоразмерно велик. У Discord guild'ы-миллионники создают один перегруженный шард, тогда как тысячи маленьких guild'ов делят другой. Решение - large guild exception: guild с участниками свыше порога (например, 250 000) получает выделенный шард или несколько шардов.

1. Coordinator вычисляет новое распределение (consistent hashing минимизирует число переездов)
2. Старый шард дрейнирует соединения: перестаёт принимать новые, отправляет close code 4000 мигрирующим клиентам
3. Клиенты переподключаются, gateway направляет их уже на новый шард
4. Клиент восстанавливает сессию через resume (sequence number позволяет сервер-подхватить с нужного события)

Shard Routing

Shard routing - механизм направления входящего WebSocket-соединения или события на правильный шард. Различают два уровня: connection routing (при handshake) и message routing (для событий между шардами, когда участники разных guild'ов взаимодействуют).

Gateway service - точка входа, которая знает топологию шардов. При WebSocket handshake клиент подключается к gateway, тот вычисляет целевой шард (по guild_id, user_id или другому ключу) и либо проксирует соединение, либо отвечает redirect с адресом нужного шарда. Slack и Discord используют redirect-подход: клиент сам подключается к конечному шарду после redirect.

Межшардный routing через pub/sub (Redis, NATS, Kafka) используется когда событие нужно доставить участникам, соединения которых разбросаны по шардам. Это происходит при cross-guild взаимодействиях или когда пользователь состоит в нескольких guild'ах на разных шардах.

Итоги

• Consistent hashing размещает серверы и ключи на одном кольце - при добавлении/удалении шарда перемещается только 1/N соединений, а не все
• Guild/room sharding обеспечивает co-location: все участники одного контекста на одном шарде, fan-out становится локальной операцией в памяти
• Rebalancing WebSocket-соединений требует graceful drain: шард отправляет клиентам close code 4000, клиенты переподключаются и resume-механизм восстанавливает сессию без потери событий
• Gateway как точка входа знает топологию шардов и направляет новые соединения через redirect или проксирование - клиент подключается к конечному шарду напрямую

Связанные темы

Sharding connections строится на фундаментальных паттернах распределённых систем и определяет архитектуру pub/sub и session management:

• Consistent Hashing в распределённых системах — Алгоритм, на котором строится распределение соединений по шардам
• WebSocket Pub/Sub и fan-out — Межшардная доставка событий когда участники распределены по разным шардам
• Session Management и Resume — Механизм восстановления соединения после rebalancing без потери событий

Вопросы для размышления

• У вас чат с 10 000 комнатами по 2-3 участника и 5 комнатами по 50 000 участников. Как организовать sharding чтобы избежать hot shard?
• Клиент переподключается после rebalancing и запрашивает resume с sequence number 1500, но новый шард не имел этой сессии. Как восстановить состояние?
• Участник состоит в 20 guild'ах, каждый на своём шарде. Сколько WebSocket-соединений держит клиент и как уменьшить это число?

Связанные уроки

• db-23-sharding