09 · Sharding & Partitioning — Split Data Across Multiple Machines¶
Scaling Writes · Topic 9 of 10
The Problem¶
A single node has finite storage and write throughput. Sharding (horizontal partitioning) splits data across multiple nodes so each node owns a subset.
Partitioning Strategies¶
Range Partitioning¶
Data divided by key ranges. Supports range queries efficiently.
- ✅ Range queries efficient
- ❌ Hotspots if data is skewed (e.g., sequential IDs all land on one shard)
Hash Partitioning¶
Key is hashed and mapped to a shard. Uniform distribution.
- ✅ Even distribution
- ❌ Range queries require scatter-gather across all shards
Directory-Based Partitioning¶
A lookup table maps keys to shards.
- ✅ Flexible — can move data without rehashing
- ❌ Lookup table is a single point of failure / bottleneck
Consistent Hashing¶
See Consistent Hashing for one way to reduce key movement. Managed databases may instead move key ranges or fixed hash slots; no placement strategy is universally preferred.
Cloud Implementations¶
PostgreSQL¶
- Native declarative partitioning:
PARTITION BY RANGE/LIST/HASH - Logical sharding: Citus extension for distributed PostgreSQL
- Each partition is a separate table internally
CREATE TABLE orders (
order_id BIGINT,
created_at DATE
) PARTITION BY RANGE (created_at);
CREATE TABLE orders_2024 PARTITION OF orders
FOR VALUES FROM ('2024-01-01') TO ('2025-01-01');
Google Spanner¶
- Auto-sharding (splits) based on load and data size
- Key-range based; interleaving improves parent/child locality, but large hierarchies can span splits
- Choose keys to avoid hotspots: avoid monotonically increasing PKs
DynamoDB¶
- Partition key determines the shard
- Each partition: up to 10 GB, 3,000 RCU, 1,000 WCU
- Hot partition problem: use random suffix or write sharding for high-throughput keys
Cassandra¶
- Partition key hashed onto the ring (consistent hashing)
RFcopies per partition spread across nodes- Choose partition key so partitions stay under ~100 MB
MongoDB¶
- Sharding via
mongosrouter + config servers - Shard key:
{user_id: 1}or{user_id: "hashed"} - Range-based chunks; the documented default range size is 128 MB, configurable by deployment/version
Cross-Shard Queries¶
Scatter-gather
Queries without the shard key broadcast to all shards and merge results — expensive. Design query patterns to always include the shard key.
Partitioning Is Not Necessarily Sharding¶
PostgreSQL declarative partitions are separate tables within one database deployment; they do not automatically distribute writes across independent servers. Replication copies the same data; sharding divides ownership of different data. Most distributed databases do both.
Choose a Key from Access Patterns and Skew¶
| Candidate | Benefit | Failure mode |
|---|---|---|
tenant_id |
Tenant-local queries and joins | A very large tenant becomes a hot shard |
order_id hash |
Distributes many independent orders | Customer order history needs an index or fan-out |
| Time range | Efficient retention and bounded scans | The newest range absorbs all current writes |
(tenant_id, bucket) |
Splits a heavy tenant across buckets | Tenant-wide reads merge multiple results |
A hash distributes distinct keys, not the load on one key. Ten thousand writes per second to one tenant still hit one logical partition unless the data model explicitly splits that tenant. Random salting improves writes at the cost of read fan-out and aggregation. Pick bucket counts from measured peak traffic and leave headroom for rebalancing.
Resharding Without Losing Ownership¶
- Identify the source range, destination, routing epoch and rollback criteria.
- Copy a consistent snapshot while capturing subsequent changes.
- Catch up changes and verify counts/checksums at a comparable watermark.
- Fence stale writers and atomically switch ownership/routing metadata.
- Drain in-flight requests and retain a recovery window before retiring the old copy.
Naive dual writes can succeed on one shard and fail on the other. Migration needs a protocol for retries, ordering and duplicate suppression; it is not just INSERT ... SELECT plus a DNS change. During migration, monitor per-shard p99 latency, queue depth, bytes moved, replication lag and error rate—not only total cluster CPU.
Check Your Understanding¶
Sources: MongoDB chunk partitioning, Spanner splits and replication.