Partitioning Strategies

Зачем

Один сервер не вмещает данные — либо по объёму, либо по нагрузке. Партицирование (sharding) разбивает датасет на куски по ключу, и каждый кусок живёт на отдельной ноде. Но выбор ключа — это не вкусовщина: ошибиться в стратегии = получить hot partition, scatter-gather на каждом запросе, или 6-месячный resharding-проект с downtime.

sharding как концепт объясняет «зачем». Этот урок — про детали: range vs hash vs composite vs directory vs geographic, как избегать hot tail и celebrity keys, как Pinterest и Discord перешивают кластер вживую без потери единого write.

Mental model

«Стратегия партицирования = выбор того, что чаще всего трогает запрос. Если запросы по user_id — партицируй по user_id. По времени — по time bucket. По геолокации — по region. Партиционный ключ должен совпадать с самым горячим access pattern, иначе каждый запрос превращается в scatter-gather.»

Три закона:

1. Hash распределяет равномерно по умолчанию, но плохо для range queries. Range — наоборот: дёшев для сканов «всё за июль», но провоцирует hot tail.
2. Hot keys всегда найдутся. @elonmusk_posts, tenant_id=enterprise_giant, region=us-east-1 — даже хеш не спасёт, если 80% нагрузки на один ключ.
3. Resharding неизбежен. Datasets растут. План на live cutover нужен до того, как припрёт, а не после.

Что показывает диаграмма

Канвас — упрощённый партиционированный кластер: Application → Router/Coordinator → 4 шарда. Координатор знает mapping key → partition и инкапсулирует стратегию. Реальные системы:

• DynamoDB — request router инкапсулирует hash partitioning, клиент видит «one table».
• Cassandra — клиент сам считает token и идёт прямо на coordinator-ноду (любая нода может быть coordinator).
• Vitess (YouTube/Slack) — vtgate как router перед MySQL шардами.
• MongoDB — mongos процесс роутит запросы к нужному mongod.

Диаграмма — образ. Mapping может быть встроен в клиент (Cassandra), вынесен в lookup-сервис (Pinterest директория), или жить в metadata cluster (Vitess + etcd). Важно — что где-то решение «какой шард» принимается перед первым диск-сиком.

Четыре сценария показывают ровно те ситуации, которые ломают наивные дизайны: идеальный hash, range hot tail, celebrity hot key и live resharding.

Сценарии

hash-even — идеальный hash

Writes на разных user_id → hash(id) % 4 равномерно раскладывает по 4 шардам. ~25% нагрузки на каждый, никаких hot spots. Это baseline: hash partitioning по высококардинальному ключу с равномерным распределением запросов. DynamoDB, Cassandra, MongoDB hashed sharding — все начинают здесь.

Почему работает: хорошая hash-функция (MurmurHash3, xxHash) даёт uniform output даже на skewed input. 64-битный hash space + modulo по N шардов = approximately N/total нагрузки на каждый шард.

Когда ломается: см. следующие два сценария.

range-hot-tail — классический антипаттерн

Партиция по месяцу: Jan→p1, Feb→p2, ..., May→p4 (текущий). Все today-writes идут в один partition. Остальные три простаивают. p4 уходит в throttling, 503 на клиента.

Это самая частая ошибка в системах с time-series данными (events, logs, metrics). Range partitioning сам по себе не плох — он идеален для «дай всё за июль». Но партицировать только по timestamp без compound — гарантированный hot tail.

Фикс: compound key (bucket, timestamp), где bucket = hash(user_id) % 16. Теперь writes размазаны по 16 buckets × time, при этом range query по конкретному user_id всё ещё работает (один bucket → один шард, range по времени внутри шарда). Cassandra-паттерн: ((user_id), message_ts) — partition key размазывает, clustering key сортирует внутри.

hot-celebrity — hash не панацея

@elonmusk_posts хешируется в один конкретный шард. Hash распределение «равномерное» в среднем — но один ключ, который генерирует 80% reads, утопит свой шард независимо от количества partitions. p3 на 100% CPU, p1/p2/p4 idle.

Mitigation hierarchy (от простого к сложному):

1. Кеширование hot key (Redis перед БД, edge-cache, CDN). Снижает RPS до origin.
2. Replicate hot key to all shards — отдельная политика для известных hot keys, request → random replica. Twitter делал это для timeline хвостов знаменитостей.
3. Compound key с random suffix — (elonmusk_posts, shard_id) для writes; reads scatter-gather (но scatter по фиксированному N — приемлемо).
4. Detect hot keys dynamically — sliding window counter на coordinator, автоматически escalate в режим repliction для top-K keys. DynamoDB adaptive capacity, ScyllaDB heat-weighted load balancing.

Ключевая мысль: hash защищает от skew в ключевом пространстве, но не от skew в access pattern.

live-resharding — Pinterest/Discord pattern

Когда все шарды в red zone (disk 95%+, CPU saturating), нужно расти. Из 4 шардов в 8 — без downtime, без потери write.

Канонический алгоритм:

1. Provision новые шарды, оставить старые в работе.
2. Virtual mapping key → {old_shard, new_shard} — слой абстракции в coordinator. Старая логика: hash(key) % 4, новая: hash(key) % 8.
3. Dual-write — каждый write идёт в обе локации (old + new). Чуть медленнее, но обе версии данных консистентны для новых ключей.
4. Backfill — фоновый процесс сканирует старые шарды, копирует данные в соответствующие new shards. Идёт часы или дни в зависимости от объёма.
5. Dual-read когда backfill завершён: «попробуй new, fallback на old». Сначала с fallback (страховка), потом без.
6. Cutover — отключить writes в old, mapping → new only. Old shards readonly, потом drop.

Discord так перешивал свои Cassandra/ScyllaDB кластера для триллионов сообщений. Pinterest — для MySQL шардов с фотографиями. Vitess умеет это автоматически (workflow MoveTables / Reshard).

Trade-offs (ADR)

ADR-001: Hash partitioning by default; composite (partition_key, clustering_key) для range-внутри-сущности; никогда не голый timestamp.

• Context: Stack новой OLTP-системы должен выдержать 100K RPS writes с ростом до 1M в 18 месяцев. Большинство запросов — point lookups по user_id, ~15% — «последние N событий юзера», ~5% — аналитика по time range.
• Decision: Hash partitioning по user_id (point lookups покрыты). Для «последние N событий» — composite key (user_id, event_ts): partition key даёт шард, clustering key сортирует. Аналитика по time range — отдельный OLAP store (ClickHouse / BigQuery), куда CDC льёт events; OLTP не партицируется по времени никогда.
• Consequences: Аналитика теряет real-time (минуты CDC lag), но OLTP остаётся write-scalable. Если новый use case потребует cross-user range scan — это scatter-gather по всем шардам, медленно. Решение: либо денормализация (отдельная таблица под query), либо OLAP slice.
• Альтернативы отклонены: (a) Range partitioning по created_at — hot tail, отброшено сразу. (b) Directory-based (Pinterest стиль) — lookup сервис как SPOF, операционная сложность не оправдана для greenfield. (c) Geographic-only — нужен мульти-региональный продукт, у нас single-region MVP.

ADR-002: Resharding только live (dual-write/backfill/cutover), никогда STOP-THE-WORLD.

• Context: Команды без опыта часто планируют resharding как «maintenance window, 4 часа, всё ляжет, выкатим». Для b2c с 24/7 трафиком это нереально.
• Decision: Resharding с первого дня проектируется через virtual mapping слой. Coordinator/router знает «текущая стратегия» и может перейти на dual-write без code deploy.
• Consequences: Чуть больше сложности в coordinator (mapping table, dual-write logic). Зато ресайз 4→8→16 шардов не вызывает downtime, можно делать без выходных. Если live resharding не нужен ещё год — over-engineering; если нужен через 6 месяцев — спас пол-года инженерных нервов.

Реальные системы

Anti-patterns

• Партиция по голому timestamp. Hot tail гарантирован — все writes в последний bucket. Compound (bucket_hash, ts) — обязательно.
• LSI (Local Secondary Index) для high-traffic queries. Каждый query по non-PK = scatter-gather по всем шардам. Используй GSI (отдельная партиционированная таблица «индекс-поле → PK»).
• Hash partition key с low cardinality. Партицирование по country_code при N=4 шардах — большинство трафика «US» утопит один шард, остальные три почти пусты. Высококардинальный ключ обязателен (user_id, request_id, заведомо много значений).
• Resharding скриптом «STOP THE WORLD». Read-only mode + миграция + переключение = downtime измеряется часами на терабайтах. Live cutover (dual-write/backfill/dual-read) тот же объём данных тащит без отказа сервиса.
• Игнорирование hot keys в дизайне. «Hash распределит» — пока не появится celebrity. План mitigation (кеш, replicate-to-all, dynamic detection) должен быть до первого incident, не после.
• Путать partition (логика шардирования) и tablespace (физическое размещение в Postgres). Tablespace — про диски, partition — про распределение строк. Можно иметь 1 partition на 4 tablespaces или 4 partitions на 1 tablespace.
• Async indexing без понимания consistency. CDC + индексер = eventually consistent индекс. Read-after-write по индексу может промахнуться на seconds-minutes. Для критичных flows — sync (dual-write с компенсацией), либо session token + read-from-primary fallback.
• Partitioning без замера access patterns. «Партицируй по user_id, всегда» — без проверки. Если 90% запросов — аналитика по region, hash по user_id заставляет каждый аналитический запрос быть scatter-gather. Сначала замерь access pattern, потом выбирай ключ.

Когда НЕ использовать

• Датасет <100GB и <10K RPS. Один Postgres / MySQL сервер с правильными индексами и репликой для чтения. Партицирование — операционная сложность, окупается только когда вертикальное масштабирование исчерпано.
• Сильные cross-entity транзакции в продукте. Если 50% бизнес-логики — это «atomic update А и Б, которые на разных шардах», то либо живёшь с distributed transactions (медленно, сложно), либо meta-проблема в дизайне домена. Spanner / CockroachDB решают это через TrueTime / hybrid logical clocks, но платишь latency.
• Нет понимания access patterns. Партиция «впрок» — гарантированно неправильный ключ. Сначала продакшен с одним сервером и метриками, потом — партиционирование под фактический workload.
• Когда decompose-the-monolith решает проблему. Иногда «БД не справляется» = «один сервис делает работу 10 сервисов». Микросервисная декомпозиция с отдельными БД на сервис может убрать необходимость шардирования вовсе.

Дальше читать

• [CONCEPT]sharding — общая концепция, контекст этого урока
• [CONCEPT]consistent-hashing — как добавлять/убирать шарды с минимальным rebalancing (Cassandra, DynamoDB vnodes)
• [CONCEPT]hot-key-mitigation — отдельный deep dive по celebrity keys
• [CONCEPT]cap-theorem и [CONCEPT]pacelc-theorem — какие гарантии теряются при кросс-шардовых операциях
• [CASE]twitter-system-design — partitioning timeline data
• DDIA Ch.6 «Partitioning» — каноничный текст, обязательно
• Discord: How Discord Stores Trillions of Messages — live migration Cassandra → ScyllaDB
• Pinterest: Sharding Pinterest — directory pattern и online resharding
• Vitess docs: workflow MoveTables / Reshard — production-grade live resharding в open source