Database Sharding and Partitioning: Keys, Indexes and Rebalancing

Sharding (horizontal partitioning) splits one large dataset across several databases, called shards, each holding a subset of the rows. It is how a system scales writes and storage beyond one machine, after caching and read replicas have run out. It is also the most invasive scaling step, so it's worth understanding the choices well.

Partitioning vs sharding: one idea, many names

Partitioning and sharding mean the same thing: breaking data into smaller pieces. Every database names the piece differently, which helps when reading documentation:

Why partition? Performance and scalability: reads and writes spread across many nodes instead of one. Fault tolerance: if one server or partition goes down, the others keep operating. Each partition is like a mini-database with its own rows and indexes, responsible for a subset of the data; queries and updates are routed to the right partition by the value of the partition key.

Cloud databases often partition automatically: DynamoDB splits partitions by partition key as data or traffic grows (each partition holds up to about 10 GB); Cloud Spanner splits and moves data by primary key based on size and load; Cosmos DB splits a physical partition as it approaches its limits (about 20 GB in the notes' example, larger in current versions). You rarely manage this by hand there, but the same rules about choosing keys apply.

Partitioning vs replication

Replication copies all the data to several machines (more read capacity, same write capacity). Sharding splits the data so each machine has some of it (more write capacity and storage). Real systems do both: each shard is itself replicated. See replication.

Partitioning strategies

Many systems split into many more logical shards than physical machines (Instagram used thousands of logical shards on far fewer servers). Rebalancing then means moving whole logical shards between machines, which is much easier than splitting data.

Range partitioning and hot spots

Range partitioning is like a dictionary split by first letter: A–B, C–D and so on. Most databases support it, adjacent keys stay together and range queries are easy. The catch is uneven load: English words aren't spread evenly over letters, so the partition holding the busy letters gets far more data and traffic.

Access patterns cause hot spots too: partition comments by year, and if 2019 had an unusual number of comments, that partition is busy while others sit idle; partition by date, and today's partition takes every write. That's why many systems prefer hash partitioning.

Hash partitioning in practice

A good hash function turns skewed input into uniformly spread output: even nearly identical keys hash far apart. Each node owns a range of hash values. Take the first 5 hex characters of an MD5 hash and three partitions: A = 00000–55555, B = 55556–aaaa9, C = aaaaa–fffff. Timestamps one second apart land evenly:

import hashlib

def partition_for(key: str) -> str:
    prefix = hashlib.md5(key.encode()).hexdigest()[:5]
    return "A" if prefix <= "55555" else "B" if prefix <= "aaaa9" else "C"

for s in range(54, 60):
    ts = f"2023-04-21 12:34:{s}"
    print(ts, partition_for(ts))      # B A A C C B: two per partition

Hash partitioning is available in most databases; the price is that adjacent keys scatter, so range queries must ask every partition.

The mixed approach: composite primary keys

A composite key hashes the first column to pick the partition and uses the remaining columns to sort rows inside it. Cassandra, DynamoDB and Spanner work this way. For a social app's posts, (user_id, timestamp): user_id is the hash (partition) key and timestamp the range (sort) key, so all of one user's posts sit in one partition, in time order: "Alice's latest 20 posts" is a single sorted read. In DynamoDB, creating a table asks for a partition key and optionally a sort key; supplying both makes a composite primary key.

Choosing the shard key

A favorite interview question. Design for the access patterns, and weigh:

• Access patterns: how the app reads data. A ticketing system looks up events by location, date or type, and the key should make those queries efficient.
• Write distribution: writes should spread evenly so no shard is overloaded while others idle.
• Query isolation: most queries should be answerable from one shard; cross-shard queries are complex and slow.
• Data growth: data should stay balanced as it grows over time.
• Prefer high-cardinality columns (user_id, order_id), use composite keys that match the access pattern (comments loaded per video in time order → (video_id, timestamp)), and add a random suffix only for genuinely write-heavy keys.

The shard key decides almost everything. A good one:

• Has high cardinality and spreads load evenly. country is a terrible key; user_id is usually fine.
• Matches the main access pattern, so most queries hit one shard: shard a chat app by conversation_id, a SaaS app by tenant_id.
• Keeps data that is used together on the same shard, so transactions and joins stay local: a user's orders live with the user.
• Avoids monotonic values with range partitioning: sharding by timestamp sends every new write to one shard.

Hot spots and celebrity keys

Even with a good key, one key can be far hotter than others: a celebrity's account, a viral post, a huge tenant. Mitigations:

• Cache hot reads aggressively in front of the shard.
• Split hot keys: append a suffix (post_123#0 … post_123#9) to spread writes like counters across 10 rows, and sum them on read.
• Isolate big tenants on dedicated shards (directory-based sharding makes this easy).

Skewed loads and key salting. A celebrity with millions of followers generates a disproportionate share of comments and likes. Appending a random number to the key spreads one hot key over several partitions (AWS's DynamoDB guide uses invoice data as its example); the cost is that reading the item now means querying every suffix and merging. For most keys that's unnecessary overhead; know it for the hot ones.

import random

SUFFIXES = 10                                     # spread one hot key over 10 partitions

def write_key(post_id):                           # writes pick a random suffix
    return f"likes#{post_id}#{random.randrange(SUFFIXES)}"

def read_keys(post_id):                           # reads must gather every suffix
    return [f"likes#{post_id}#{i}" for i in range(SUFFIXES)]

# total_likes = sum(db.get(k) or 0 for k in read_keys("celebrity_post"))

Secondary indexes on a partitioned database

The partition key finds a row by its primary key. To look rows up by another field (books partitioned by book_id, but queried by genre) you need a secondary index, and the data doesn't map neatly to partitions. There are two ways to store it:

Rebalancing partitions

Data grows and nodes fail, so partitions must move: new nodes take some load, and a dead node's partitions are taken over by others. Managed cloud databases do this for you, but three strategies sit underneath:

• Fixed number of partitions: create several times more partitions than nodes up front (say 20 partitions on 4 nodes, 5 each). A new node steals a few partitions from each existing node; a failed node's partitions are spread over the rest. Partitions never split, only move, which is simple, but the count is permanent and hard to pick when data size varies wildly. Moving a partition takes time because data crosses the network.
• Dynamic partitioning: the system watches size and load and splits partitions that grow too big or hot and merges small ones, so the count follows the data (HBase, MongoDB, DynamoDB, Spanner).
• Consistent hashing: nodes and keys sit on a hash ring, and adding or removing a node moves only the keys next to it. See consistent hashing.

Partitioning isn't only for databases: message queues (Kafka partitions), caches (Redis Cluster hash slots), search indexes and blob stores are partitioned with the same ideas. Azure's data partitioning guide covers strategies for each.

Try it: range partitioning in MySQL

A comments table partitioned by the year a comment was created (MySQL or MariaDB):

CREATE TABLE comments (
  comment_id   INT NOT NULL,
  page_id      INT NOT NULL,
  user_id      INT NOT NULL,
  content      TEXT NOT NULL,
  created_time DATETIME NOT NULL
)
PARTITION BY RANGE (YEAR(created_time)) (
  PARTITION pold VALUES LESS THAN (2019),
  PARTITION p19  VALUES LESS THAN (2020),
  PARTITION p20  VALUES LESS THAN (2021),
  PARTITION p21  VALUES LESS THAN (2022),
  PARTITION p22  VALUES LESS THAN (2023),
  PARTITION pmax VALUES LESS THAN MAXVALUE      -- catch-all so newer rows don't fail
);

INSERT INTO comments (comment_id, page_id, user_id, content, created_time) VALUES
  (1, 1, 1, 'The Times 03/Jan/2009 Chancellor on brink of second bailout for banks', '2009-01-03 18:15:05'),
  (2, 2, 2, 'Hello from 2021', '2021-10-11 18:45:02');

SELECT * FROM comments;                    -- both rows (all partitions)
SELECT * FROM comments PARTITION (pold);   -- only the 2009 comment
SELECT * FROM comments PARTITION (p21);    -- only the 2021 comment

This is partitioning within one server (it helps pruning and dropping old data); sharding applies the same idea across servers.

What sharding makes hard

• Cross-shard queries: "top 10 products across all users" becomes a scatter-gather over every shard, slow and fragile. Maintain a separate aggregated view, or use an analytics store.
• Cross-shard transactions: need two-phase commit or a saga. Design keys so they're rare.
• Global uniqueness: unique constraints and auto-increment ids no longer work across shards. Use distributed ID generation.
• Rebalancing: adding shards means moving data while serving traffic: copy, catch up with changes, then switch routing.
• Operations: backups, schema migrations and monitoring are multiplied by the number of shards.

Shard late. A single well-tuned primary with replicas and caching carries most products a long way, and many databases (Vitess for MySQL, Citus for Postgres, DynamoDB, Cassandra, CockroachDB) now handle sharding for you.