Database Sharding

One-liner: Split one logical dataset across many nodes by a shard key so writes and storage scale horizontally; you pay with cross-shard queries and resharding.

Say this#

SAY THIS

Horizontal partitioning (sharding) — rows split across nodes; same schema everywhere.
Vertical partitioning — columns/tables split by domain (users DB vs orders DB).
Shard key / partition key — the column that decides placement; the most important decision.
Range sharding — contiguous key ranges per shard (HBase, Spanner, MongoDB ranged); good for range scans, risk of hot ranges.
Hash sharding — hash(key) → shard; even spread, no range scans (Cassandra, DynamoDB).
Directory / lookup-based sharding — a mapping service decides; flexible, extra hop, SPOF risk.
Geo sharding — by region for locality and data residency.
Hot partition / hot shard / celebrity problem — one key or range gets disproportionate load.
Scatter-gather — query every shard and merge; expensive.
Cross-shard join / transaction — avoid by colocating related data; else saga or 2PC.
Resharding / rebalancing — moving data when adding shards; consistent hashing or pre-split into many logical shards.
Logical vs physical shards — e.g. 4096 logical shards mapped onto 16 physical nodes; remap without rehashing.
Examples — Vitess (YouTube/MySQL), Citus (Postgres), MongoDB sharded clusters, CockroachDB/Spanner (auto range splits).

How it works#

TEXT

request(user_id=1234) -> router (app lib / proxy like Vitess, Citus coordinator)                           -> shard = hash(user_id) % 4096 (logical) -> node 7 (physical)request(user_id=1234) -> router (app lib / proxy like Vitess, Citus coordinator)
                           -> shard = hash(user_id) % 4096 (logical) -> node 7 (physical)

Pick a shard key that appears in nearly every query and spreads evenly (user_id, tenant_id).
Use many logical shards from day one; map logical → physical in config (Zookeeper/etcd).
Colocate everything for one entity on the same shard so transactions stay local.
Global/secondary indexes: either per-shard (scatter-gather) or a separate global index table (DynamoDB GSI, async).
Reshard by moving whole logical shards: double-write or snapshot + replay changelog, then flip the mapping.

Trade-offs#

Choice	Pro	Con
Hash sharding	Even distribution	Range queries become scatter-gather
Range sharding	Range scans, ordered	Hot spots on sequential keys (timestamps, auto-increment)
Directory sharding	Arbitrary placement, easy moves	Lookup hop; the directory must be HA and cached
Shard by tenant/user	Local transactions, simple	Big tenants become hot shards
Vertical partitioning first	Simple, no cross-shard joins within a domain	Each service DB still hits the single-node ceiling
Not sharding (scale up + replicas)	Simplest; often enough to tens of TB	Eventually a wall for writes

Numbers#

Rule of thumb: start thinking about sharding when a single primary passes roughly a few TB or ~10k+ sustained writes/s; prefer vertical scale, caching, and read replicas first.
Pre-split into 2^10 to 2^12 logical shards; physical node count can grow by moving whole logical shards.
Instagram-style ID: 41 bits time, 13 bits logical shard (8192 shards), 10 bits sequence.

Say this#

How it works#

Trade-offs#

Numbers#

In the interview#