Sharding & Partitioning | System Design Interview Handbook

✂️

Vertical vs Horizontal Partitioning

split by column, or split by row

Vertical partitioning splits by column or table — put rarely-read columns or whole tables on a different store. Horizontal partitioning splits by row — the same table's rows spread across nodes by some key. Sharding is horizontal partitioning across separate machines, and it's the one that lets you grow past a single node's storage and write capacity.

  VERTICAL (by column/table)            HORIZONTAL / SHARDING (by row)
  ┌─────────────────────┐               ┌──────────┐ ┌──────────┐ ┌──────────┐
  │ id │ name │ big_blob │              │ shard A  │ │ shard B  │ │ shard C  │
  ├────┼──────┼──────────┤              │ users    │ │ users    │ │ users    │
  │ hot cols │ cold cols │  →           │ 0–333    │ │ 334–666  │ │ 667–999  │
  │ on DB-1  │ on DB-2   │              └──────────┘ └──────────┘ └──────────┘
  └─────────────────────┘               each node holds a SUBSET of the rows,
   relieves one table's width           on its own machine

ℹ️

Sharding is a last resort, not a first move. It's the final step in the scaling sequence because it complicates everything above it — queries, transactions, joins. Exhaust vertical scaling, read replicas, and caching first, then shard when a single node genuinely can't hold the data or take the writes (Scaling Patterns).

🔑

Choosing a Shard Key

the single most important decision

The shard key decides which node each row lives on, and it's the choice you can't easily undo. A good key does two things at once: it distributes evenly so no node is overloaded, and it aligns with the dominant query so most reads hit a single shard.

Get it wrong and you pay the cross-shard query tax: a query that can't be answered from one shard has to fan out to all of them, wait for the slowest, and merge — turning one lookup into N. Shard a chat app by message ID and "give me this conversation" scatters across every node; shard by conversation ID and it's one node.

⚠️

There's rarely a shard key that's perfect for every query — optimizing for one access pattern usually taxes another. Pick the key for your dominant pattern and accept that secondary queries fan out or need a separate index. Naming that tradeoff, rather than pretending one key serves all, is the senior answer (Tradeoffs).

#️⃣

Hash vs Range Sharding

even spread, or range queries — pick one

Two ways to map a key to a shard, and they trade the exact same thing against each other.

Hash sharding even, but scattered

Hash the key and assign by the result. Spreads load beautifully — even sequential keys land on random shards. The cost: range queries are dead. "All records from last week" is scattered across every shard because adjacent keys hash apart.

Range sharding local, but lumpy

Assign contiguous key ranges to shards. Range scans and "give me a window" queries stay on one or two shards. The cost: hot spots on sequential keys — timestamps or auto-increment IDs pile every new write onto the newest shard.

💡

The tell: does the workload need range queries? Time-series and "recent items" want range sharding and accept the hot-newest-shard problem. Key-value lookups with no range needs want hash sharding for the even spread. Say which one the question demands and why.

🔁

Consistent Hashing

adding a node without reshuffling everything

Naive hashing — shard = hash(key) % N — has a fatal flaw: change N (add or lose a node) and the modulo shifts for almost every key, so nearly all the data has to move. On a live cluster that's catastrophic. Consistent hashing fixes it so a membership change moves only about 1/N of the keys.

  Place nodes AND keys on a ring (hash space wrapped into a circle).
  Each key belongs to the first node CLOCKWISE from it.

              [Node A]
           k1 ·      · k2
        ·                 ·
   [Node C]                [Node B]
        ·                 ·
           k4 ·      · k3
              (ring)

  Add Node D between B and C:
     only the keys that fall in the B→D arc move (from C to D).
     Everything else stays put.  →  ~1/N of keys relocate, not all of them.

  Problem: with few nodes the ring is lumpy — some own huge arcs.
  Fix: VIRTUAL NODES. Each physical node gets many points on the ring,
  so load evens out and a lost node's share spreads across all the others.

Virtual nodes are the practical piece: giving each physical machine many points on the ring smooths the distribution and means when a node dies, its load spreads across all remaining nodes rather than dumping onto its single clockwise neighbor. This is how Cassandra, DynamoDB, and consistent-hash load balancers keep rebalancing cheap (Discovery).

🔥

Hot Spots & Rebalancing

when one shard gets all the traffic

Even spread of keys doesn't guarantee even spread of traffic. A celebrity's user ID, a viral post, a single hot product — one key can draw more load than a whole shard can serve. Even distribution assumed uniform access; reality is power-law.

Problem	Mitigation
Celebrity / hot key	Cache it in front so most reads never reach the shard (Caching)
Hot key still too heavy	Key salting — split it into `key#1…key#n` across shards, merge on read
Whole shard overloaded	Split the hot shard, or give the known-hot key dedicated capacity
Uneven growth over time	Rebalance: move partitions to new nodes without downtime

For rebalancing, a fixed number of partitions (many more than nodes) is easier to manage than resharding by hashing: to add a node, you move whole partitions to it, never rehashing individual keys. The data moves in the background while both copies serve, then traffic cuts over — no downtime.

🆔

Unique ID Generation

auto-increment breaks under sharding

A single-node auto-increment counter can't span shards — you'd need every shard to coordinate on the next number, which is exactly the bottleneck sharding was meant to remove. So distributed systems generate IDs differently, and the schemes trade sortability, coordination, and size.

Scheme	Sortable?	Coordination?	Gotcha
Auto-increment	Yes	Single node	Doesn't scale across shards
UUID v4	No	None	Random — kills B-tree insert locality
UUID v7	Yes (time-prefixed)	None	Fixes v4's locality problem
Snowflake	Yes	Machine ID only	Needs clock sync; 64-bit
Ticket server	Yes	Central service	That service is a bottleneck / SPOF

💡

Snowflake is the interview favorite: timestamp | machine ID | per-machine sequence packed into 64 bits. Time-sortable, generated independently on each node with no central coordination, and no collisions as long as machine IDs are unique. When a question needs decentralized, roughly-ordered IDs — the URL Shortener is the classic — Snowflake or UUID v7 is the answer (URL Shortener).

⚠️

UUID v4's randomness isn't just a size cost — random keys scatter B-tree inserts across the whole index, destroying the sequential-insert locality databases love and hammering write performance (Indexing). If you need a UUID, reach for v7, whose time prefix keeps inserts local.

📋

Quick Reference

sharding and IDs on one card

	Hash sharding	Range sharding
Distribution	Even	Can be lumpy
Range queries	No — scattered	Yes — local
Hot-spot risk	Low	High on sequential keys
Best for	Key-value lookups	Time series, ranges

ID scheme	Sortable?	Coordination?	Note
UUID v4	No	None	Kills insert locality
UUID v7	Yes	None	Time-prefixed, the safe default
Snowflake	Yes	Machine ID	Decentralized, needs clock sync
Ticket server	Yes	Central	Simple but a bottleneck

ℹ️

The one-liners to keep ready. Shard last, after replicas and caching. The shard key is the load-bearing choice: even spread plus alignment with the dominant query, and cross-shard queries are the tax for missing. Hash for even spread, range for range queries. Consistent hashing with virtual nodes keeps rebalancing to ~1/N. Auto-increment dies under sharding — reach for Snowflake or UUID v7.