Probably Up to Date — The Scholars' Coast

Where this book sits

Draws on

Epidemic Algorithms for Replicated Database MaintenanceDemers et al. 1987 · Spreading by Word of Mouth
- anti-entropyAnti-entropy: copies compare and exchange until all are current.
Probabilistic Quorum SystemsMalkhi, Reiter, Wool & Wright 2001
- probabilistic quorumsQuorums that overlap only with high probability.
On the Availability of Non-Strict Quorum SystemsAiyer, Alvisi & Bazzi 2005
- non-strict quorumsQuorums that need not overlap, and what they still guarantee.
Dynamo: Amazon’s Highly Available Key-Value StoreDeCandia et al. 2007
- partial quorumsPartial quorums: reads and writes that ask only some of the replicas.

This book retells

Probabilistically Bounded Staleness for Practical Partial QuorumsBailis et al. 2012

Each link is an idea one paper took from another. Point at one, or tap it, to read how.

a paper this book retells a paper retold in another book a paper outside the series

First, in machine terms

Write to some, read from some

A data item is kept at N replicas. A write is acknowledged once W of them have it, and a read returns the newest of the first R answers.

If R + W is more than N, every read meets the latest acknowledged write.
Operators often choose smaller numbers, for speed. A read may then return stale data.
Probabilistically Bounded Staleness (Bailis et al., 2012) works out how likely that is, how many versions behind, and for how long after the write. It gives a probability, never a promise.

We tell it with one work kept at three libraries, a writer, a reader, and couriers who take as long as they take.

Three replicas choose W and R

W: acknowledgments a write waits for

R: answers a read waits for

0reads0stale

Each read comes straight after a write. Which replicas answer first is drawn at random.

The coast from high above: libraries with red-tiled roofs scattered through olive groves and joined by pale footpaths, the long stoa near the shore and the sea at the island's edge

The scholars' coast

A work and its three home libraries

On the scholars' coast a library answers a reader from whatever copy it holds, and lives with copies that differ for a while.^* Some works are kept at more than one library.

Three home librariesOne work is kept at three libraries and no others.

CouriersA new edition goes to all three by courier, and each courier takes a different time.

The newest replyA reader asks all three and takes the newest copy among the first replies.

Who holds the work

A work and its home libraries

A work kept at three libraries has three home libraries, and every copy of it on the coast is held by one of them. Each copy is an edition with a tally, the day and hour it was written, and of two editions the larger tally is the newer.

A writer sends a courier to each home library with a new edition. A home library that receives it enters it and sends a courier back to say so. When enough home libraries have answered, the writer announces the edition and regards it as done. The couriers still on the road keep walking.

A reader writes to all three home libraries and takes the newest copy among the first few replies, without waiting for the rest.

So there are two numbers: how many home libraries a writer waits for, and how many replies a reader takes. Nothing in the replies says whether the home libraries heard from are ones the edition has reached.

One of a work's three home libraries seen from its porch road: a small plastered library on a base of dressed stone, with a porch of two plain columns, a pediment and a tiled roof, among olive trees and cypresses

Certainty, and its price

How many to wait for

Waiting for all three home libraries and asking all three makes the slowest courier decide how soon anything is done. One slow road or one stopped courier holds up everyone.

Waiting for fewer is quicker. The risk is that the home libraries the writer waited for and the home libraries the reader heard from share no library.

Three home libraries, one new edition choose the two numbers, then let a reader ask

The writer waits for

The reader takes the first

Gold home libraries hold the new edition. Ringed home libraries are the ones the reader hears from first.

The rule the Chamber has always used

When the two numbers add up to more than the home libraries, the two groups share a library

A decree passes in the Chamber when a majority hold it, and any two majorities share a member.^* The same holds for home libraries. With three, waiting for two and taking two is enough: the reader always hears from a home library that has the announced edition, and takes the newest copy heard.

Proof · that R + W > N forces every read quorum to meet every write quorum

Let there be N replicas, a write quorum Q_W of size W and a read quorum Q_R of size R, both subsets of the same N replicas. Claim. If R + W > N, the two quorums share a replica.

This is the standard property of strict quorums, which the paper recalls in §2. Let there be N replicas, a write quorum Q_W of size W and a read quorum Q_R of size R, both subsets of the same N replicas.
|Q_W ∪ Q_R| ≤ N, since both are subsets of a set of size N.
|Q_W ∩ Q_R| = |Q_W| + |Q_R| − |Q_W ∪ Q_R| ≥ W + R − N.
If R + W > N, the right side is at least 1, so the two quorums share a replica. That replica holds the committed write, and a read that returns the value with the greatest version among its responses returns that write or a later one.∎

Smaller numbers are chosen for speed. The paper observes that real systems with three copies often wait for one and ask one, on purpose: the quicker answers matter more to them than an old copy now and then. On the coast that is the quick way.

The plainest case

When the groups miss each other

Suppose the home libraries that answer the writer, and the home libraries the reader hears from, fall as if by lot. With three home libraries and the quick way, the edition is at one home library and the reader's home library is one of the three. The reader misses it two times in three.

With more home libraries the odds improve quickly, if the two numbers grow with them. Two groups drawn from a large crowd are very unlikely to share no one.

The chance of an old copy about a third of the home libraries waited for, and a third asked

The page works these out from the count of the ways the reader's home libraries can all lie among those the edition has not reached.

Proof · that the probability of a read missing the last write is C(N − W, R) / C(N, R)

Let N be the number of replicas, W the write quorum size and R the read quorum size, the W replicas written and the R replicas read each chosen uniformly at random; C(n, r) is the number of subsets of size r of a set of size n. Claim. The probability p_s that the read quorum misses the write quorum is C(N − W, R) / C(N, R).

This is Equation 1 of §2.1, with the paper's assumption that the W replicas written and the R replicas read are each chosen uniformly at random.
The read quorum is one of the C(N, R) subsets of size R, each equally likely.
The read misses the write quorum exactly when every one of its R members lies among the N − W replicas not written to. There are C(N − W, R) such subsets.
So p_s = C(N − W, R) / C(N, R). For N = 3, R = W = 1 this is 2/3; for N = 100, R = W = 30 it is about 1.88 × 10⁻⁶, as the paper states.∎

The odds are excellent for a coast with a hundred home libraries of each work. A work on this coast has three, and the paper notes that real systems keep one to three copies. Nothing about the large case helps the small one. But a reader usually asks something narrower than is this the newest?

Leeway in editions

How many editions behind

A reader who will take any of the newest few editions is let down only if the home libraries heard from lack every one of them.

Each announced edition went to its own group of home libraries, and the reader's group has the same chance of missing each. So the chance of missing the newest two is the chance of missing one, multiplied by itself, and so on. The chance of an old copy falls away fast with every edition of leeway.

One of the newest few three home libraries, the reader takes one reply

The writer waits for

Worked out from the rule: one chance of a miss for each edition that will do, all multiplied together.

Proof · that PBS k-staleness is p_sk = p_s^k

Let p_s = C(N − W, R) / C(N, R) be the probability that a read quorum misses one write quorum, and let k be the number of versions a reader will accept. Claim. A read returns a value more than k versions old with probability p_sk = p_s^k.

This is §3.1 for quorums that do not expand. A read returns a value within k versions of the latest committed version exactly when its read quorum intersects at least one of the write quorums of the last k committed versions.
Treat the k write quorums as independent, each missed by the read quorum with probability p_s = C(N − W, R) / C(N, R).
The read quorum misses all k with probability p_s^k, so p_sk = p_s^k and the read is within k versions with probability 1 − p_s^k.
With N = 3, R = W = 1, p_s = 2/3, so 1 − (2/3)^k is 5/9 for k = 2, 0.704 for k = 3, 0.868 for k = 5 and 0.983 for k = 10. With W = 2, p_s = 1/3 and the values are 2/3, 8/9 and 0.996 for k = 1, 2 and 5, as the paper's examples give.
For expanding quorums the paper notes this is an upper bound on the probability of staleness, since writes only reach more replicas with time.∎

There is a second gain. A library that need not return the newest edition need not ask as many home libraries, so the busiest home library is asked less often, and the same libraries can serve more readers.

These odds ignore time. They would be the same a moment after the announcement or a week after, and yet the couriers still on the road are still arriving.

Leeway in time

How long until it shows

The edition was sent to all three home libraries at the start, so after the announcement it goes on reaching those that had not answered. A reader who comes a while later asks home libraries of which more have it.

The visibility of an edition after a while is the chance that a reader who comes that long after the announcement is handed the edition or a newer one.

What decides it is how many home libraries hold the edition at that moment. If all three do, no reader can miss it. If only the first to answer does, the odds are those of the quick way. In between, the chance of a miss is the chance that the reader's home libraries are all among those that lack it.

Two things to note

A newer edition ends the question

If a second edition is announced before the first has finished arriving, the first no longer matters: a reader handed the second is handed something newer.

Two things to note

Not yet announced is not stale

A reader handed an edition that is written but not yet announced is handed something newer than the announced one, not older.

Proof · that the probability of a stale read t after commit is a sum over how many replicas hold the write

Let q_c(t) be the probability that exactly c replicas hold version v at time t after v commits, for c from W to N. Claim. The probability of a stale read at time t is p_st = Σ_c=W^N q_c(t) · C(N − c, R) / C(N, R).

This is §3.4. Let q_c(t) be the probability that exactly c replicas hold version v at time t after v commits, for c in [W, N]; at commit exactly W do with certainty, so q_W(0) = 1.
Conditional on exactly c replicas holding v, a read quorum chosen uniformly misses all of them with probability C(N − c, R) / C(N, R), by the argument of Equation 1.
Summing over the possible c: p_st = Σ_c=W^N q_c(t) · C(N − c, R) / C(N, R). The paper writes this with its distribution P_w(c, t) of the number of replicas reached; its printed Equations 4 and 5 differ from one another in the range of the sum and the sign of the difference, and the sum above is the quantity both mean.
The paper notes that this assumes instant reads and instant commitment after the Wth copy arrives, so it is a conservative upper bound on the true probability of staleness. When the last k writes all happened at the same time the same argument gives the chance of missing all k as the kth power, the paper's ⟨k, t⟩-staleness.∎

For one of the newest few editions, a while after the announcement, a cautious rule of thumb is one such answer for each edition, all multiplied together. A reader may trade one kind of leeway for the other. What is left to understand is how many home libraries hold the edition at a given moment.

A library on a headland seen from the side: a porch of two plain columns and a tiled roof above walls of pale plaster with small barred windows, an olive tree close at the right and the sea beyond

The couriers' journeys

The four legs

Four journeys are in every writing and reading, and each takes a time that varies from courier to courier.

The edition's way out from the writer to a home library. The acknowledgment's way back. The request's way out from a reader to a home library. The copy's way back to the reader.

A home library's reply is stale when the reader's request reaches the home library before the edition does. The home library then has only the old edition to give. The reader is handed an old copy only if that is so for every one of the first replies taken.

A request that outruns the edition the writer, one home library and the reader

W the writer · K one home library · R the reader
1 The writer sends the edition. Its way out to this home library is slow.
2 Enough other home libraries answer, and the writer announces it.
3 A while later the reader sends a request. Its way out is quick.
4 The request arrives first. The home library sends back the old copy.
5 The edition arrives, too late for this reader.

The chance cannot be written down in one line, as the chance for editions was, and the paper says so. The moment of announcement depends on the first few journeys out and back, the reader's replies on the first few requests and copies, and the two overlap. So the odds are found by playing the situation over many times, drawing each journey's time from the couriers' logbook, and counting how often the reader is behind.

Play it over ten thousand times three home libraries; every journey's time is drawn afresh

The writer waits for

The reader takes the first

The edition's way out, against the other three legs

Choose, then play.

Proof · that under WARS no read is stale when R + W > N

WARS names the four delays: W, from the coordinator to a replica for a write; A, the acknowledgment back; R, a read request to a replica; S, the response back. Let the write be sent at time 0, reach replica i at w_i and be acknowledged at w_i + a_i; it commits at w_t, the Wth smallest acknowledgment time. Claim. If R + W > N, a read begun at any t ≥ 0 after commit is not stale.

This is the remark of §4.1. Let the write be sent at time 0, reach replica i at w_i (a draw from W) and be acknowledged at w_i + a_i (a draw from A). The write commits at w_t, the Wth smallest of these acknowledgment times.
The W replicas whose acknowledgments came first each received the write at w_i ≤ w_t.
A read begins t ≥ 0 after commit, so its request to replica i arrives at w_t + t + r_i (a draw from R), which is at least w_i for each of those W replicas. Such a replica returns the write.
The read takes the first R responses, which are R distinct replicas. If R + W > N they cannot all lie among the N − W other replicas, so at least one is among the W that hold the write, and the read is not stale.∎

The method of §5.1 for the general case: draw N samples from each of W, A, R and S; compute w_t, the Wth smallest of the sums W[i] + A[i]; order the replicas by R[i] + S[i]; and count the read stale when each of the first R satisfies w_t + R[i] + t ≤ W[i]. Repeating this many times gives the probability for each t.

The replay can be trusted as far as it was tested. The authors checked it against a working system they set up, with chosen journey times for each leg. Across fifty thousand writings, the predicted chance of seeing the edition after each moment differed from the measured by well under one part in a hundred on average.

The replay, run on real roads

What the logbooks say

The first finding is which journey matters: the edition's way out. The slower and more uneven it is, the longer a reader must wait for near certainty, and its unevenness matters more than its average.

With three home libraries and the quick way, when the way out was very quick and even, a reader was handed the edition nine times in ten at the moment of the announcement. When it was ten times slower than the other legs, only four times in ten.

The paper then turned to the logbooks of two large systems, and took four coasts from them.

Four coasts, the same three home libraries, the quick way the chance of the new edition at the moment it is announced

These are the paper's measures. The page does not work them out.

What the logbooks show

A long tail delays certainty

On the coast where the way out now and then takes very long, the odds at once are good, and the climb to near certainty takes the longest of the four.

What the logbooks show

More home libraries hurt the first moment, not the end

On the slow-copying coast the chance at once falls from about 58 in a hundred with two home libraries to about 21 with ten. The time to near certainty rises by only about a fifth.

What the logbooks show

The quick way costs little

On the long-tailed coast, taking a second reply cut the wait for near certainty to about a seventh, and writer and reader together were still about four-fifths faster than the fastest way with no chance of a miss.

A reader who returns

Never going backwards

A reader who comes back to a work may not mind a copy that is not the newest. Finding a copy older than the one read last time is another matter.

The editions that will do are the one seen last time and every edition announced since. So this is leeway in editions again: one, plus the number announced between visits. A reader who visits seldom has the widest range and the best odds. A reader who visits all the time has the narrowest.

How likely is a step backwards? three home libraries, the quick way

Editions announced between two visits, on average

1editions will dochance of going backwards

One sure way

Keep to the same home library

A home library's copy only ever moves forward, so a reader who always asks the same home library is never handed anything older than before, unless that home library is lost. A library may also limit how often a reader comes, to bring the odds where it wants them.

Proof · that PBS monotonic reads is k-staleness with k = 1 + γ_gw / γ_cr

Let a client read a data item at rate γ_cr and let the item be written, by all clients, at rate γ_gw. Claim. The probability of violating monotonic reads is p_sMR = (C(N − W, R) / C(N, R))^{1 + γ_gw / γ_cr}.

This is §3.2. Let a client read a data item at rate γ_cr and let the item be written, by all clients, at rate γ_gw. Between two successive reads by this client the expected number of versions committed is γ_gw / γ_cr.
A read satisfies monotonic reads if it returns the version the client last read, or any newer one. If the last read returned version v_i−k and the latest committed is v_i, with γ_gw / γ_cr versions in between, the acceptable versions are the newest 1 + γ_gw / γ_cr.
That is PBS k-staleness with k = 1 + γ_gw / γ_cr, so the probability of violating monotonic reads is p_sMR = (C(N − W, R) / C(N, R))^{1 + γ_gw / γ_cr}, Equation 3.
For strict monotonic reads, where the client must read strictly newer data if any exists, the exponent is γ_gw / γ_cr. The paper uses expected values of the rates, which in practice are measured as distributions.∎

The limits

What it does not say

A library can tell a reader the odds. Four things it cannot say.

A library seen from behind and to one side among trees: its tiled gable, the small pediment of its porch and a barred window in a wall of pale plaster

Is the reader's copy current?

The library cannot say. It can say nine times in ten you are handed the newest, and nearly always one of the newest few. With the quick way a reader can be handed an old copy of any age: nothing in the numbers bounds how old, and the paper says so.

What do the odds assume?

That home libraries answer as if by lot; that the couriers' journeys are alike and drawn afresh each time, as the logbook records them; that no library is closed and no courier stopped. They also count no festival, no word of mouth and no reader who puts a lagging home library right, so the real odds are better.

Can a reader tell that a copy is stale?

Not when it is handed over. Afterwards, a late reply with a newer tally shows the copy was behind. Even that can mislead harmlessly: the later reply may carry an edition written after the request, or one not yet announced.

What of readers who need more than a recent copy?

A reader who must see a letter before its reply needs another kind of promise, which the paper leaves aside. It also leaves as a suggestion that a coast could set its two numbers by what it measures, and offer the quickest way that still meets stated odds.

Back to machines

The home libraries were replicas

Every home library is a replica, and the two numbers are the write and read quorums. Hover or tap to see who is who.

On the coast

In the machine room

With small quorums a read may be stale, and the chance falls fast with every version of leeway and with every moment since the write was acknowledged.

It is a probability and a way to tune it. The worst case stays unbounded.

The scholars' coast, in detail All the papers

Setting The Scholars' Coast

The paper behind this book

Peter Bailis, Shivaram Venkataraman, Michael J. Franklin, Joseph M. Hellerstein and Ion Stoica, Probabilistically Bounded Staleness for Practical Partial Quorums. Proceedings of the VLDB Endowment, Vol. 5, No. 8 (38th International Conference on Very Large Data Bases, Istanbul, August 2012), 776–787. — Partial quorums, PBS k-staleness, t-visibility and monotonic reads, the WARS model, and a Monte Carlo evaluation on production latency data.

The ideas, plainly.

Bailis and co-authors study data kept on several machines, where a write is acknowledged after W of N machines have it and a read returns after R machines have answered. If R + W exceeds N, a read always meets the latest write. Operators often choose smaller numbers, for speed, so that a read may miss it. The paper asks how often, and shows that a read within k versions of the latest has probability 1 minus p to the k, where p is the chance of a plain miss: the chance of being stale falls exponentially with the leeway allowed. Monotonic reads is the same idea with k set by how often a reader returns compared with how often the data is written.

Staleness in time is harder, because writes keep reaching more machines after they are acknowledged. The paper models the four message delays of a write and a read, W, A, R and S, shows that a read is stale when its request reaches a replica before the write does, and works out the odds by simulation using measured delays. The results are that the delay of the write message, and above all its variance, matters most, and that typically the chance of reading the latest write is high within a short time of its commit, at a latency far below that of a strict quorum.

What the paper offers is therefore a probability and a way to tune it, not a guarantee: the worst case stays unbounded, and the odds rest on assumptions about independence and about the delays staying as they were measured.

The paper has five authors: Peter Bailis, Shivaram Venkataraman, Michael J. Franklin, Joseph M. Hellerstein and Ion Stoica, and all are credited here. Nobody in this telling is named; the writer, the home libraries and the reader are told apart by what they do.

In the paper, term by term

a work's home libraries: the same few libraries hold every copy of it	The replication factor N; one quorum system per data item. §2.1, §2.2.
an edition with its tally, the day and hour by the sun	A version with a timestamp giving a total order. §2.1.
the writer sends the edition to all the home libraries	The coordinator sends the write to all N replicas. §2.2.
announced when enough home libraries have answered	The write quorum W: the write commits after W acknowledgments. §2.2.
a reader asks all home libraries and takes the first few replies	The read quorum R: the read returns after R responses. §2.2.
the edition still on its way to the other home libraries after it is announced	Expanding quorums: the write quorum grows by anti-entropy after the write returns. §2.2.
groups sharing a home library when the numbers add to more than the home libraries	A strict quorum system: R + W > N. §2.1.
the quick way: wait for one, ask one	A partial quorum, R + W ≤ N, as deployed by operators. §1.1, §2.3.
the chance the groups miss each other; excellent for a crowd of home libraries	Probabilistic quorums: p_s = C(N − W, R) / C(N, R). §2.1.
one of the newest few editions; the chance falls by the same fraction each	PBS k-staleness: p_sk = p_s^k. §3.1.
a busy home library asked less often	Lower quorum load under staleness tolerance. §3.3.
the odds a while after the announcement	PBS t-visibility; the window of inconsistency. §3.4.
one of the newest few, a while after	PBS ⟨k, t⟩-staleness. §3.5.
the four legs: the edition out, the acknowledgment back, the request out, the copy back	The WARS model: the delay distributions W, A, R, S. §4.1.
stale when the request outruns the edition	A read is stale when the first R responses reached their replicas before the write. §4.1.
the couriers' logbook; replaying it by lot	Latency distributions; Monte Carlo simulation, validated against Cassandra. §5.1, §5.2.
the four coasts	LNKD-SSD, LNKD-DISK, YMMR and WAN latency fits. §5.4, §5.5.
a reader who never goes backwards	PBS monotonic reads: k = 1 + γ_gw / γ_cr. §3.2.
keeping to one home library	A sticky replica. §3.2.
learning afterwards from the late replies	Asynchronous staleness detection, with false positives. §4.3.
no festival and no word of mouth counted	The conservative assumption: read repair and Merkle-tree exchange never occur. §4.2.
a promise with odds: nine in ten, and nearly always one of the newest few	PBS consistency: an expected bound, not a guarantee; latency/staleness SLAs. §1.2, §6.