arrow_backBack to Phase 3
pie_chart

Partitioning
(Sharding)

When your dataset is too big for one disk, you split it up. But how do you split it so you can still find things quickly?

Vertical vs Horizontal Scaling

Vertical (Scale Up)

1 Big Server
  • ✓ Simple (No code changes).
  • ✗ Expensive (Specialized hardware).
  • ✗ Hard Limit (Max RAM/CPU).

Horizontal (Scale Out)

Node
Node
Node
  • ✓ Cheap (Commodity hardware).
  • ✓ Infinite scale.
  • ✗ Complex (Distributed transactions, joins).

Partitioning Strategies

Key Range Partitioning

Sort keys and split by range. Like an encyclopedia (A-C, D-F, etc.).

Shard 1: User IDs [1 - 1000]
Shard 2: User IDs [1001 - 2000]
  • ✓ Range scans are efficient.
  • ✗ Uneven load if keys are sequential (e.g., timestamps).

Hash Partitioning

Hash the key to pick a shard. hash(id) % N.

Shard 1: hash(id) ends in 0
Shard 2: hash(id) ends in 1
  • ✓ Even distribution (load balancing).
  • ✗ Range scans are impossible (keys are scattered).

The Hotspot Problem

local_fire_department

Celebrity Problem

What if one key is extremely popular? (e.g., Justin Bieber's Twitter handle).
Even with perfect hashing, ALL his tweets and replies hit ONE shard.

The Fix: Salting

Append a random number to the key to split it across shards.

Key: "justinbieber" → "justinbieber_1", "justinbieber_2"...

(Trade-off: Reads must now query all split keys and merge results).

Rebalancing (Consistent Hashing)

When you add a new node, you don't want to move all data. You only want to move some data.

Consistent Hashing Ring

Imagine a circle (0-360°). Nodes are placed on the circle. Keys are placed on the circle. A key belongs to the first node it encounters moving clockwise.

Virtual Nodes

To balance load, each physical node appears at multiple random positions on the ring ("Virtual Nodes"). This prevents one node from getting a huge slice of the pie by luck.

Secondary Indexes

You sharded by User ID, but now you want to search by Email. The data is scattered everywhere.

Local Index (Scatter-Gather)

Each shard maintains its own index for its own data.

Query: Send to ALL shards.
Merge results.
  • ✓ Fast writes (only touch one shard).
  • ✗ Expensive reads (query amplification).

Global Index

A separate database/shard just for the index (Email → UserID).

Query: Check Global Index.
Go to specific User shard.
  • ✓ Fast reads (direct lookup).
  • ✗ Slow writes (distributed transaction to update data + index).