Skip to content

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.

Shard 1: user_id 1 – 1,000,000
Shard 2: user_id 1,000,001 – 2,000,000
  • ✅ 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.

shard = hash(user_id) % num_shards
  • ✅ 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)
  • RF copies per partition spread across nodes
  • Choose partition key so partitions stay under ~100 MB

MongoDB

  • Sharding via mongos router + 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.

A tenant-aware router sends each key to one shard; every shard has its own replica

Edit this diagram in draw.io.

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

  1. Identify the source range, destination, routing epoch and rollback criteria.
  2. Copy a consistent snapshot while capturing subsequent changes.
  3. Catch up changes and verify counts/checksums at a comparable watermark.
  4. Fence stale writers and atomically switch ownership/routing metadata.
  5. 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

#

Question 1

Will doubling the shard count necessarily double throughput?

#

Question 2

Why are global unique constraints and pagination harder after sharding?

#

Question 3

What should you establish before proposing sharding?

Sources: MongoDB chunk partitioning, Spanner splits and replication.