Sharding

The Definition

 SHARDING = horizontal partitioning of one logical dataset
 across independent database nodes, each owning a key range
 or hash slice:

 shard-0: hash(uid) % 4 == 0     [ Postgres instance ]
 shard-1: hash(uid) % 4 == 1     [ Postgres instance ]
 shard-2: hash(uid) % 4 == 2     [ Postgres instance ]
 shard-3: hash(uid) % 4 == 3     [ Postgres instance ]

 each shard is a FULL database (schema + rows for its keys).
 no single node sees everything.

Choosing the Shard Key — THE Decision

 requirements for a good key:
 - HIGH CARDINALITY      enough distinct values to spread load
 - EVEN DISTRIBUTION     no natural skew baked in
 - QUERY ALIGNMENT       dominant queries filter BY the key

 candidates for RideShare:
 user_id   ✓ every trip/order/profile query starts from a user
 driver_id ✓ symmetric case; but trips involve BOTH → pick the
             read-heavier principal, co-locate its data
 city      ✗ low cardinality + skew (NYC vs rural) = hot shards
 timestamp ✓ great for time-series, terrible for entity lookups
 
 rule: shard by what you LOOK UP by, not by what grows fast

Query Patterns After Sharding

Query	Path	Cost
Get user’s trips	hash(uid) → 1 shard	cheap ✓
Trip by id (uid known)	same shard via uid	cheap ✓
Trip by id (uid unknown)	scatter-gather all shards	expensive ✗
Global top-N / counts	aggregate across shards	expensive ✗

 mitigating the expensive paths:
 - embed shard hint in ids: trip_id = shard# + uuid
   → direct routing even for by-id lookups
 - global secondary indexes in a separate service/search engine
 - precomputed aggregates (analytics pipeline) instead of live scans

Topology Choices

 app-managed:    app knows shard map; connects directly
                 fastest, most code
 proxy tier:     Vitess/Citus intercepts SQL; app stays naive
                 transparent, extra hop + operational component
 native:         distributed DB (CockroachDB, Spanner, Mongo)
                 sharding built-in; less control, vendor model
 
 all three implement the same concepts; interviews usually
 mean app-managed or proxy

What You Give Up

 ✗ simple cross-entity transactions (two-phase commit or sagas)
 ✗ global unique constraints (enforce via id design instead)
 ✗ trivial joins across shards (denormalize or application-join)
 ✗ easy resharding (own lesson — plan virtual shards early)
 
 this is why sharding is LAST on the scaling ladder:
 it converts hard-but-familiar problems into
 distributed-but-novel ones

Interview Framing

“Database can’t keep up” → after replicas/caching fail: shard. Scored sequence: justify with write-volume math, choose key with reasoning tied to dominant queries (“shard by rider_id — 90% of reads are per-rider”), handle the by-id lookup with embedded-shard ids, acknowledge cross-shard analytics moving offline. That arc demonstrates sharding as a designed decision, not a buzzword.