Sharding Databases

The Topology

 logical shards map onto PHYSICAL nodes (with replicas):

 shard 0 (users hash 0-25%)   → primary A + replicas A1,A2
 shard 1 (25-50%)             → primary B + replicas B1,B2
 shard 2 (50-75%)             → primary C + replicas C1,C2
 shard 3 (75-100%)            → primary D + replicas D1,D2

 every shard = an independent database instance with its own
 replication. the SHARDING LAYER routes by key.

 [app] ──route(uid)──► correct shard's primary/replica

The Three-Layer Question

 WHERE does routing live?

 APP-MANAGED:
   app library computes shard, connects directly.
   + fastest   − logic in every service; migrations coordinated

 PROXY TIER (Vitess/Citus/pgbouncer-forks):
   transparent SQL interception; app sees one database.
   + app stays simple   − extra hop; new critical component

 NATIVE DISTRIBUTED (CockroachDB/Spanner/Yugabyte):
   the database shards itself; SQL just works.
   + least code   − opinionated consistency/cost tradeoffs

 all three implement identical CONCEPTS below —
 learn concepts once, recognize them in any layer.

Key Selection Rules (recap + sharpen)

 the key decides EVERYTHING:

 CARDINALITY    enough distinct values to spread
 SKEW           no natural celebrity keys (city=nyc ✗)
 ALIGNMENT      dominant queries filter BY this key
 
 RideShare analysis:
 rider_id ✓ (trips/orders/profiles all per-rider)
 driver_id ✓ symmetric case — co-locate trips BOTH ways?
   → answer: pick read-heavier principal; denormalize
     the other direction via lookup table/GSI-style index.

 DOCUMENT the query→shard mapping for top 10 queries;
 if >2 of them scatter-gather, reconsider the key.

What Production Sharding Actually Involves

 □ ID GENERATION:      globally unique without coordination
                       (UUIDv7 / snowflake-style time-ordered)
 □ MIGRATION TOOLING:  dual-write backfill machinery (own lessons)
 □ CROSS-SHARD QUERIES: routed to warehouse or denormalized
 □ PER-SHARD OPS:      N× backups, monitoring, upgrades — automate!
 □ REBALANCING PLAN:   consistent-hash/virtual-shards from day one
 □ HOTSPOT PLAYBOOK:   salting/bucketing ready before celebrities

 teams underestimate the OPS multiplication most;
 automation investment is non-optional at 8+ shards.

The Virtual Shard Trick (plan it early)

 create MANY logical shards (e.g., 1024) mapped onto few nodes:

 virtual shard v0-v255 → node A
 virtual shard v256-v511 → node B ...

 growing: move HALF the virtual shards to new node C —
 fine-grained, incremental, online.
 vs modulo-N where resize remaps nearly everything.

 decide virtualization BEFORE launch; retrofitting is brutal.

Interview Framing

Sharding answers score on completeness signals: routing-layer choice named with tradeoff, key justified against top queries, virtual-shard planning mentioned unprompted, ops-multiplication acknowledged, and cross-shard strategy for the two inevitable questions (“top users?”→warehouse, “user X after re-shard?”→directory/routing table). Completeness here reads as scar tissue.