Sharding

"Sharding optimizes writes and destroys reads unless you're careful."

What sharding costs you (forever)

The numbers below are what an L6 calibration looks like — quoted to fork architectural decisions, not to fill a slide.

Why shard?

Sharding is the answer when the problem is physical exhaustion, not slowness. Slowness has cheaper answers — indexing, caching, read replicas, a bigger box. Exhaustion means working set, write IOPS, or storage have exceeded what any single node sells. What you get: linear scale for writes and storage, smaller per-node working sets, fault isolation. What you pay is the whole next section.

When to shard — the constraint tree

Don't compare features. Compare which resource is exhausted. Sharding fixes exactly one bottleneck at a time, and the shape of the shard key has to match the resource being relieved.

flowchart LR
    Start["Is a single node insufficient?"] --> Bottleneck{"Which resource is exhausted?"}
    Bottleneck -- Memory --> RAM["Working set > node RAM?"]
    Bottleneck -- Compute --> CPU["Query load saturating cores?"]
    Bottleneck -- Storage --> Disk["Write volume > disk BW?"]
    RAM --> RAMFirst["Try first: bigger instance, hot/warm tiering, Redis/Memcached, column pruning"]
    CPU --> CPUFirst["Try first: read replicas, query optimization, connection pooling"]
    Disk --> DiskFirst["Try first: separate WAL disk, NVMe upgrade, batch writes"]
    RAMFirst -- Still stuck --> RAMShard["Shard by access pattern; hot data on fewer shards"]
    CPUFirst -- Still stuck --> CPUShard["Shard to distribute query load across cores"]
    DiskFirst -- Still stuck --> DiskShard["Shard to distribute write I/O across disks"]
    

The sharding tax — what you sign for, in writing

• Cross-shard queries. Scatter-gather adds (N−1) × network_RTT latency minimum, and tail-latency dominates the result.
• Distributed transactions. 2PC or eventual consistency. Pick your poison; both are expensive.
• Rebalancing operations. Moving data between shards is never zero-downtime. The shard that needs splitting is already on fire.
• Schema migrations. ALTER TABLE now runs on N shards, often sequentially.
• Operational complexity. N databases to monitor, backup, failover. Forever.
• JOIN limitations. Cross-shard JOINs are either impossible or prohibitively expensive.

Capacity planning — how many shards?

Don't guess. Take the per-shard ceiling, your target utilization, and your largest dimension. Take the max, round up to a power-of-two-friendly logical shard count, map to fewer physical nodes.

Sharding architectures

flowchart LR
    User([User]) --> Geo{Geo route}
    Geo -->|Americas| USE[US-East]
    Geo -->|Europe| EU[EU-Central]
    Geo -->|Asia| AP[AP-South]
    USE --> CellA[Cell A]
    USE --> CellB[Cell B]
    CellA --> Shard{Shard by tenant_id}
    Shard --> Data[(Tenant shards)]
    

Sharding for multi-tenancy

Beyond scale, sharding by tenant gives you four bonuses you'd otherwise build by hand: resource isolation (one tenant's expensive ops don't slow others), permission isolation (access lives at the shard boundary), per-tenant backup/restore (recover one customer without touching others), and regulatory compliance for free (GDPR, data residency, right to deletion all become single-shard operations).

The catches: every tenant must fit on a single node, small tenants make the per-shard overhead embarrassing, and growing tenants will eventually need to migrate between shards.

Shard key selection

Properties of a good shard key

Bad shard keys in the wild: country, status, created_at, anything with celebrity behavior. Good shard keys for SaaS: (tenant_id, user_id) compound — single-shard queries within a tenant, distribution across the population.

10 workloads, 10 keys

Grouped by access-pattern shape. The category is the lesson: most workloads cluster into one of four shapes, and knowing which shape yours resembles is half the answer to picking a key.

ID generation in a sharded world

The moment you shard, AUTO_INCREMENT dies. Each shard issues its own monotonic counter; collisions and ordering become your problem. The new question: where does an ID get assigned, and what does it encode?

Sharding algorithms

Five mainstream choices. Pick by access pattern, not familiarity.

Key → CRC16(key) % 16384 → Slot → Node
Slots 0–5460       → Node A
Slots 5461–10922   → Node B
Slots 10923–16383  → Node C

Request routing

Once a key has a shard, something has to find that shard. There are really only two routing architectures, with one hybrid.

Metadata management

Two architectures, two failure profiles. Pick the one whose failure mode you can afford.

How real systems route

Sharding compute, not data — Slicer

When candidates say "sharding," they almost always mean data sharding — partitioning rows across DB instances. But there's a parallel problem: partitioning a fleet of stateful workers across requests. Examples that come up constantly:

• Which chat server holds a user's WebSocket?
• Which game-server process is hosting a match?
• Which Flink task owns a keyed window's in-memory state?
• Which session-cache node has a logged-in user's session?

The "shard key" is the user / game / session ID; the "shard" is a worker process; the routing problem is "find the worker that currently owns this key." Whether the data store underneath is itself sharded is a separate question.

Slicer is Google's internal service for this exact problem (OSDI 2016 paper, still in production). It uses a two-tier pattern that has since become the canonical answer:

Clients hit the nearest Distributor, get the worker assignment, RPC the worker directly. When the Assigner rebalances or fails a worker over, the change propagates through Distributors to clients. Strong leasing guarantees exactly one worker owns each key at any moment.

How real systems reshard

This is where the architectural personality shows. Range-split systems do it continuously and transparently. Hash-ring systems never truly reshard — they rebalance. Proxy-sharded systems require operational ceremonies. Same problem, five different answers.

Handling skewed workloads & hot spots

Detect — per shard, not cluster-wide

Mitigate — three layers, in order

1. Cache in front of hot keys. 5-second TTL absorbs ~90% of read-hot cases. Cheapest and reversible.
2. Split the hot key. Append a random suffix (bieber_0…bieber_7) to scatter writes across N shards. Reads now fan out and merge. Trade: write hotspot becomes read fan-out and tail-latency exposure.
3. Dedicated shard. Last resort. Operationally expensive snowflake.

Salt-factor lifecycle

Changing N from 10 to 50 is a migration in disguise. Old data is salted with old N, new data with new N. Reads must fan out to max(old_N, new_N) during transition. For the handful of entities that need re-salting, prefer eager migration with a brief read-from-both window over a permanent lazy dual-path.

Sharding × replication

In production, each shard is also replicated. That means every shard has leader election, replica lag, and failover behavior — and the failure modes multiply combinatorially.

Your design must specify, per shard: routing (shard → replica → leader), read consistency (leader-only, allow stale, bounded staleness), and failover semantics.

Secondary indexes in a sharded world

This is the most-asked follow-up after "tell me about sharding." There are two shapes, and the trade-off between them is exactly the trade-off between write amplification and read scalability.

Rebalancing — the mechanics that determine downtime

The interview trap is saying "we move the data to the new node." That's a goal, not a mechanism. L6 reality: moving data while serving writes requires a five-phase state machine. Describe it.

Real numbers

Moving a 100GB shard at a throttled 50MB/s: ~25 minutes cold copy, 3–5 minutes catch-up, 50–200ms cutover window. The 7-day zombie window is your rollback insurance — if the destination misbehaves post-migration, flip routing back; the source still has the data.

Why rebalancing kills production

• Competes with live traffic for I/O and network.
• Overloads the destination (cold cache, compaction spike).
• Triggers cascading hot spots when the LB sees inflated latency.
• Migration mid-way + node failure = data in limbo.

Always: throttle (cap to e.g. 50MB/s); rebalance during low-traffic windows; monitor bytes_in_flight, not just shard count; rate-limit on destination health; cap concurrent migrations to one or two.

Backups & snapshots across shards

The L6 framing: ask what the restore looks like before you design the backup. Per-shard async restore = "rebuild from these N independent snapshots; expect orphaned references across shards; have a reconciliation job ready." Coordinated restore = "restore is atomic but the backup is slower and more fragile." Pick the failure mode you can afford.

Cross-shard operations

Cross-shard reads — the scatter-gather math

Single-shard query: 1 × (RTT + query_time) ≈ 5ms.
16-shard scatter: 16 × query_time + max(RTT) + merge ≈ 51ms.

The honest cost isn't the mean — it's the tail. The p99 of N independent shards is approximately the (1 − 1/(N×100))-th quantile of any one shard's distribution. With N = 256, you're asking each shard to be in its 99.996th percentile or better — which it isn't.

Mitigation — three real moves

Cross-shard writes — pick your poison

Distributed joins

The problem: SELECT * FROM orders JOIN users when tables are sharded by different keys. Three strategies, ranked by preference:

1. Co-locate. Shard both tables by the same key. Join is shard-local.
2. Broadcast. If one table is small (<1GB), replicate to all shards.
3. Application-level decomposition. Query one, gather IDs, query the other with WHERE id IN (...), merge in app.

The spectrum across systems goes from "the database handles it" (Spanner with interleaved tables, distributed SQL push-down + shuffle) to "you handle it" (Cassandra and DynamoDB have no joins — denormalize at write time). The more the database does, the more latency floor those operations pay.

Operational realities — battle stories

Five lessons paid for at scale. Each one is a free piece of context you can quote in an interview.

Failure modes

Five canonical failure modes. Each gets a name, an impact, a fix, and a sentence you can say out loud.

Interview traps

The final mental model

Followups they'll ask

Revision — flip before the interview