1
Choose and re-choose a shard count
The count from load, capacity and target utilisation, the count from storage and replication factor, the binding one — and the fraction of keys that move when the count changes, under mod-N and under a ring.
Course · System Design
Partitioning and Load Balancing
Splitting data or traffic across N nodes is a balls-into-bins problem, and the course measures it: how uneven a hash actually is, what fraction of keys move when N changes, what one hot key does to the hottest shard regardless of N, why sampling two bins beats one so dramatically, and what a query that must visit every shard costs.
N = max(⌈λ_peak/(c·ρ)⌉, ⌈D·RF/per-node⌉) two constraints, take the max
mod N → mod N+1 moves N/(N+1); a ring moves 1/(N+1)
hottest = f·λ + (1 − f)λ/N a hot key does not care about N
two choices: ln n/ln ln n → ln ln n stated, not proved; measured here
P(k random keys on one shard) = N¹⁻ᵏ
What this course is about
- Subject
- System Design
- Lessons
- 12
- Format
- Interactive
Overview
What you will be able to do
By the end you can choose a shard count under two constraints, measure the imbalance a hash actually produces, price the three things that change it, and cost the two queries that sharding makes expensive.
2
Measure imbalance rather than assume it
Max-over-mean on a seeded hashed placement, the improvement from V virtual nodes, and the write share a monotonic key sends to one range.
3
Price a hot key and a straggler
The hottest shard's load before and after salting, and the expected and p99 completion of a job that ends with its slowest partition.
4
Cost the queries sharding makes expensive
A scatter-gather's shard requests and latency tail, a global against a local secondary index with the crossover ratio, the cross-shard fraction of a k-key transaction, and the hours a rebalance takes.
Lessons
12 lessons
How many shards first, then how evenly the keys actually land and what moves when the count changes, then the three sources of imbalance, and last the queries and operations that cross shards.
How Many ShardsCompute the shard count from load and the shard count from storage, and build the larger of the two.Not marked
Hash Partitioning and ImbalanceMeasure max over mean on a seeded hashed placement, then reseed and watch the maximum move.Not marked
Rehashing When N ChangesCount the keys that move when a shard is added, under mod-N assignment and on a ring, and check that the two counts are the whole key set.Not marked
Virtual NodesMeasure the ring's max over mean and relative spread at one, ten and a hundred tokens a node, and read the rate the spread falls at.Not marked
Range Partitioning and Hot RangesCompute the hottest range's share of the writes happening now, for a monotonic key and for a hashed one, and say what each costs a scan.Not marked
Hot Keys and SaltingCompute the hottest shard's load before and after salting, and the read amplification the salt costs.Not marked
StragglersCompute a job's mean and p99 from one partition's time distribution, and say what another partition buys.Not marked
The Power of Two ChoicesMeasure the maximum load under one random choice and under the lesser of two, from the same stream, and reseed.Not marked
Scatter-Gather CostCompute the shard requests a second and the query latency tail for a query that must ask every shard.Not marked
Local vs Global Secondary IndexesCompute the shard operations a second for both index designs and the read-to-write ratio at which they change places.Not marked
Cross-shard TransactionsCompute the fraction of k-key transactions that cross shards and the mean latency two-phase commit adds to every transaction.Not marked
Rebalancing CostCompute how long a rebalance takes at a given throttle and the utilisation the fleet runs at while it does.Not marked
Recommended background
Queues and utilisation and replication and consistency from this path, plus modular arithmetic, hashing and pseudorandom numbers, expected value, variance and combinations from discrete mathematics, and ratio, proportion and percent from algebra.
Practice suggestions
Reseed the placement labs several times. A single seeded run of balls into bins is one sample; the lesson is about the distribution of the maximum, and that only shows up across seeds.
Read the rehashing fractions as a pair. That N/(N+1) and 1/(N+1) sum to one is the whole argument for consistent hashing and takes one line.
Keep “shard” and “replica” apart. A shard is a piece of the data; a replica is a copy of a piece. “Replication and Consistency” replicated; this course splits.
What it does not cover
Shard-router internals and the mechanics of a resharding algorithm — the cost is computed in “Rebalancing Cost”; the algorithm is not.
Geo-partitioning and data-residency constraints.
Proofs of the maximum-load asymptotics. They are stated and measured; see the notes in “Hash Partitioning and Imbalance” and “The Power of Two Choices”.