k randomly hashed keys all land on one shard with probability N¹⁻ᵏ, which collapses in k rather than in N: at two shards a two-key transaction already crosses half the time. Everything that crosses pays two-phase commit — two round trips and extra fsyncs — and the cost that belongs in a latency budget is that price multiplied by the crossing probability.
Core ideas
A counting question and a latency question, kept apart until the last step where one multiplies the other.
Fix the first key's shard; each of the remaining k − 1 keys joins it with probability 1/N, so all k agree with probability N¹⁻ᵏ. N appears once and k appears in the exponent, so adding a key is worth far more than adding shards: at N = 16, going from two keys to three takes the local fraction from 6.25% to 0.39%.
At N = 2 and k = 2 the probability of staying local is 1/2. One extra shard — the first one anybody adds — already sends half of all two-key transactions across a boundary. Nobody has to reach a large fleet before this matters, which is why “most of our transactions are local” is worth checking rather than assuming.
A crossing transaction pays two-phase commit: a prepare round and a commit round, plus an fsync on each. At 2.00 ms a round trip and 0.50 ms an fsync that is 5.00 ms. But 6.25% of transactions are local and pay none of it, so the figure that belongs in a mean latency budget is 0.9375 × 5.00 = 4.688 ms — and the figure that belongs in a tail budget is the full 5.00 ms.
The material
The counting argument, what it does as k and N move, the protocol that the crossing transactions run, and how to put the two together without double-counting.
A transaction is local when every key it touches lives on one shard, and cross-shard otherwise. A local transaction commits with the store's ordinary single-node path. A cross-shard one needs an atomic commitment protocol across the participants, and two-phase commit is the standard one: a prepare round in which every participant durably votes, then a commit round.
If k keys are hashed independently and uniformly over N shards, the probability that all of them land on the same shard is N¹⁻ᵏ.
Condition on the shard of the first key, whatever it is. Each of the remaining k − 1 keys is independently uniform over the N shards, so each lands on that same shard with probability 1/N.
By independence the probability that all k − 1 of them do is (1/N)ᵏ⁻¹ = N¹⁻ᵏ, and this does not depend on which shard the first key chose, so it is the unconditional probability as well.
At k = 1 this gives N⁰ = 1, which is the right answer: a single-key transaction is always local.
□
The first table's second column barely changes after the first few rows — 93.75% at sixteen shards and 98.44% at sixty-four — which is what “collapses in k, not in N” looks like from the other side. Once N is past a handful, essentially every multi-key transaction crosses, and the remaining question is only what crossing costs.
The expected number of shards a transaction touches is a different count and a useful one: it is N(1 − (1 − 1/N)ᵏ), which at k = 2 and N = 16 is 1.938. That is the number of participants the commit protocol coordinates, and it stays close to k for any N much larger than k. A two-key transaction on a large fleet is a two-participant commit almost always, which is why the protocol's cost does not grow with the fleet.
Two numbers, two purposes. 5.00 ms is what a crossing transaction pays and it belongs in a tail budget, because at 93.75% crossing the p99 transaction certainly crosses. 4.688 ms is the mean over all transactions and belongs in a throughput calculation. Quoting the mean where the tail is wanted understates the p99 by the 6.25% of transactions that got off free.
The round-trip term scales with distance and the fsync term does not. Move the participants into one rack and the 4.00 ms may fall by an order of magnitude while the 1.00 ms of durable votes stays exactly where it is; move them across regions and the round trips dominate everything. Itemising the two means the same model answers both questions, and “The Speed-of-Light Floor” gives the round trip a lower bound that no amount of engineering moves.
Every practical answer is a way of making k = 1 rather than a way of making two-phase commit cheap. Partition by the entity the transaction is about — orders by customer, posts by author — so that a transaction touching several rows touches one shard. Or deliberately co-locate related keys by giving them a shared partition key prefix, which is the same idea stated as a schema choice. Both are decisions about the partitioning function, and both are much harder to make after the data is placed.
Where the transaction genuinely spans entities, the remaining levers are to weaken what is being asked for — an eventually-consistent compensating action instead of an atomic commit — or to accept the 5.00 ms and make sure it is in the budget. What is not a lever is the shard count: N¹⁻ᵏ is already near zero at any N worth having, and the protocol's cost does not depend on N at all.
Interactive
N to the power 1 − k, and the two-phase cost the rest of them pay
Method
One probability, one protocol cost, and a multiplication — with the mean and the tail kept apart at the end.
k is the number of distinct partition keys, not the number of rows or statements. If the keys are deliberately co-located under a shared prefix then they are not independent, N¹⁻ᵏ does not apply, and the transaction is local by construction — which is the good case.
N¹⁻ᵏ is the local fraction and 1 − N¹⁻ᵏ is what crosses. Sanity-check at k = 1, where it must give 1. At k = 2, N = 16 the crossing fraction is 93.75%, so the interesting number is the complement rather than the probability itself.
Two round trips and two fsyncs for two-phase commit. Keep them apart: 4.00 ms of round trips responds to where the participants are, and 1.00 ms of fsyncs responds to what the storage does.
Mean added latency is (1 − N¹⁻ᵏ) × protocol cost, which is 4.688 ms at the lab's numbers. The p99 transaction crosses, so its added latency is the full 5.00 ms. Put the right one in the right budget.
The probability, the participants, the protocol cost, and the two latency figures that come out of them.
The last two lines are the ones to carry away. At the very first shard anybody adds, half of all two-key transactions are already crossing — the problem does not wait for a large fleet, and by sixteen shards the crossing fraction has only gone from a half to 93.75%.
For a faded rehearsal, keep N = 16 and take k to 3. The supplied first move is the local probability, 16⁻² = 1/256. Produce the crossing fraction, the expected number of participants, and the mean added latency; then say which of those three changed most between k = 2 and k = 3, and whether raising N to 64 would have changed any of them comparably.
You should be able to compute the local and crossing fractions for any k and N, state the expected number of participants, itemise two-phase commit into round trips and fsyncs, and produce a mean and a tail figure that are not the same number.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.