SD7.5 · LESSON 5 OF 6

Sharding

Compare consistency contracts and distribute data while tracing stale reads, partitions and hot keys.

THE IDEA

Sharding

Sharding splits data across machines by a partition key and a routing rule. The goal is even load, but record counts do not show it. Four shards with 1,000 records each, where one tenant sends 700 of 1,000 requests per second, put 70% of the traffic on one shard: imbalance 2.8. Adding machines does not fix that; changing the key, or spreading the hot tenant across shards, does.

requests/s from the biggest tenant700

shard	records	requests/s	share of traffic
1	1,000	700	0.7
2	1,000	100	0.1
3	1,000	100	0.1
4	1,000	100	0.1

record counts are identical (1,000 each); request load is not imbalance = busiest / average = 2.8 (1.0 would be perfect)

A partition key and routing rule decide where data and traffic land. A skewed key or one huge tenant creates a hot shard however many machines you add. Spreading the hot key (for example with a salt) trades single-shard simplicity for even load.

Make the big tenant bigger, then spread it.

Predict first. Does an even record count guarantee even request load?

Chapter context

Replication copies data for resilience or read capacity; partitioning assigns different data to different owners. Both introduce coordination and failure behavior that an application must explicitly account for.

TRY IT YOURSELF

Part 1. Do it hands-on

Measure imbalance by hand, then write shard loads, hot-shard detection and a salted key.

requests/s from the biggest tenant700

shard	records	requests/s	share of traffic
1	1,000	700	0.7
2	1,000	100	0.1
3	1,000	100	0.1
4	1,000	100	0.1

record counts are identical (1,000 each); request load is not imbalance = busiest / average = 2.8 (1.0 would be perfect)

fraction of traffic on shard 1 (700 of 1000) imbalance imbalance after salting (275,275,275,175) even records mean even load? (yes/no)

To do: Four shards each hold 1,000 records, but one tenant sends 700 of the 1,000 requests per second and lives on shard 1; the rest send 100 each. Fraction of all traffic on shard 1?
To do: Imbalance = busiest shard load / average shard load (average = 250). Value?
To do: The tenant's traffic is spread over all four shards by adding a bucket to its key (700 / 4 = 175 each), and the other tenants stay where they are. Imbalance now (3 decimals)? shard loads are 275, 275, 275, 175
To do: Does an even record count guarantee even request load? Type yes or no

Part 2. Do it in code

shard_of(key, n): sum(ord(c) for c in key) % n.
shard_loads(requests, n): requests is a list of (key, weight); total weight per shard.
record_counts(keys, n): number of keys per shard.
imbalance(loads): max / mean (1.0 when the mean is 0).
salted_key(key, i, buckets): "key#b" where b = i % buckets (spread one hot key over several shards).
hot_shards(loads, factor=1.5): the indexes of shards whose load exceeds factor × the mean.

def shard_of(key, n):
    pass

def shard_loads(requests, n):
    pass

def record_counts(keys, n):
    pass

def imbalance(loads):
    pass

def salted_key(key, i, buckets):
    pass

def hot_shards(loads, factor=1.5):
    pass

Ctrl/⌘ + Enter runs it

Stuck, or something not working? You can come back to it any time.

CHECK YOUR UNDERSTANDING

Does an even record count guarantee even request load?

ANoBYes

Chapter reference: math, worked example & code

This section belongs to the whole chapter, so it is the same on every lesson in it and may cover a different lesson's topic. The code for the experiment you just ran is inside the experiment itself.

Math and notation

For fixed sets over N replicas, $|R\cap W|\ge |R|+|W|-N$ . Thus R=W=3 with N=5 forces at least one shared member. This is a set fact, not a complete consistency proof. Shard and replication counts describe different dimensions of the layout.

Worked example

Five replicas use read sets and write sets of size three. The lower bound on overlap is 3+3−5=1. Enumerating all three-member sets confirms every pair overlaps. A read still needs the right version-selection and concurrency rules; intersection alone does not tell which stored value is newest or committed.

Reference code

The following example uses the Python standard library and does not call a remote service.

from itertools import combinations
replicas=set(range(5))
sets=[set(x) for x in combinations(replicas,3)]
assert min(len(r&w) for r in sets for w in sets) == 1
assert 3+3-5 == 1
assert all(r&w for r in sets for w in sets)

Python examples are provided for study and local execution; this page does not execute Python.

Common mistakes

Quorum arithmetic does not establish a full consistency contract. Sharding is not replication. CAP availability is a precise failure-model property, not the same as an ordinary monthly uptime percentage.