Tech Chapter V đọc bản tiếng việt →

The vocabulary of distributed systems

And the places it gets confused

◔ read time

10–15 min · one sitting

load

need first

some background in distributed systems will help

best when

freetime, or while reading a distributed design

Linearizability

is a strong consistency property. It guarantees that every operation on a single object appears to take effect instantaneously at some point between the call and the return. It respects real-time ordering.

Put more plainly: in a system with this property, if an operation at time $t_{1}$ has been acknowledged as successful, then an operation at any time $t_{2} (t_{2} > t_{1})$ must see the result of that earlier operation.

Properties

Single-object focus: the statement of the property talks about one object only.
Illusion of instantaneity: although real time passes between the call and the return, linearizability makes the operation look as though it happened at a single point in time, somewhere between the invocation and the response/return.
Respects real-time ordering.

Easy to get wrong when

It is used for properties that are not about a single object — several objects, or a transaction. For instance: Serializability.

Serializability

guarantees that concurrent transactions running across several processes produce a final result identical to running them on one machine in some serial order. It does not respect real-time ordering.

For example: two concurrent transactions $T_{1}$ , $T_{2}$ . The system guarantees the final result follows a serial order, either $T_{1} \to T_{2}$ or $T_{2} \to T_{1}$ . With an account $A$ starting at $1$ :

$T_{1}$ : ADD A 5
$T_{2}$ : MUL A 2

The valid results are $12 = (1 + 5) \times 2$ or $7 = (1 \times 2) + 5$ . What it rules out is the interleaved case, the lost write that leaves $6$ or $2$ .

Easy to get wrong when

It is confused with linearizability.

Strict Serializability

is serializability plus respect for real time.

Easy to get wrong when

It is confused with plain serializability.

Eventual Consistency

says that if no further changes are made to the data, every copy (replica) of it will synchronise and converge to the same final state.

Properties

Eventual convergence: every copy of the data will, in the end, converge to the same state.
No commitment about time: the property makes no promise about how long convergence takes. Every system has its own commitment there, and that commitment has to be checked — do not assume a few milliseconds, or a few seconds.

Easy to get wrong when

It is used without knowing the system’s actual commitment about synchronisation time.

Monotonic Reads / Monotonic Writes

guarantees that once a client/session/process has read a particular value or a particular version of the data, it will never read an older value of that data again.

Likewise, guarantees that a client/session/process cannot write an older version of the data over the current one.

Read-your-writes

guarantees that if a client/session/process has made a change to an object, it sees that change immediately.

Most of the cases (90%) that arrive asking for “strong consistency” can be settled with this property, without paying the price of going all the way to linearizability.

Easy to get wrong when

Jumping straight to linearizability.

Causal Consistency

guarantees that operations with a cause-and-effect relationship are observed in the same order at every node in the system, while other operations — the unrelated ones — may be observed in any order.

For example, commenting on a post: A writes a post, B comments on it. A writing the post must happen before B commenting on A’s post, so every node sees the sequence A writes $\to$ B comments. Other actions — B liking a post of C’s, or D publishing an unrelated post — may come in any order.

For most social networks, this property is enough.

Happens-before

is a partial, local order produced by causality. It is not a global order.

Happens-before expresses a causal relation $A \to B$ , and that relation holds only when $A$ , $B$ fall into one of three cases:

Within the same process: event $A$ occurs before event $B$ in the same process.
A send-receive pair: $A$ is the sending of a message from process 1, and $B$ is the receiving of that same message at process 2.
Transitivity: if $A \to B$ and $B \to C$ then $A \to C$ .

Telling the consistency models apart, and ranking them

The consistency models in distributed systems can be ordered from strong $\to$ weak as follows:

Rank	Model	Ordering constraint	Achieved by
1	Strict consistency	Absolute real time, a global clock	Not implementable; a theoretical ceiling only
2	Linearizability (strong)	Real time + one single global order	Raft/Paxos + , TrueTime (Spanner accepts an uncertainty window)
3		One global order, matching program order, need not match real time	Rarely used on its own in real databases; shows up in shared-memory models
4	Causal consistency	Only causally related operations are forced into an order; concurrent operations may be seen differently at different replicas	Vector clocks, COPS, CRDTs with causal delivery
5	PRAM / FIFO consistency	Per-writer FIFO only, no transitivity across other processes	Per-process logs; no need for full vector clocks
5.5	Session guarantees (read-your-writes, monotonic reads, monotonic writes, writes-follow-reads)	Individual local constraints, granted independently per session/client	Sticky sessions, per-client version vectors, read-your-writes tokens
6	Eventual consistency	Commits only to eventual convergence once writes stop; no ordering in the meantime, and nothing about when convergence happens	Anti-entropy, gossip, CRDTs (the semilattice guarantees correct convergence, but not when you see what)

Quorum

Quorum is the smallest/minimum number of machines/nodes that must agree on a read or a write operation.

Usually $R + W > N$ , where

$R$ (read quorum): the minimum number of nodes that must respond for a read operation
$W$ (write quorum): the minimum number of nodes that must acknowledge success for a write operation
$N$ : the total number of replicas

The formula holds because of the pigeonhole principle: when $R + W > N$ , the set of nodes serving the read ( $R$ ) and the set of nodes serving the write ( $W$ ) must intersect in at least one node. That intersecting node holds the newest version of the data, which is what keeps the system from ever returning a stale value.

Easy to get wrong when

It is confused with majority. A quorum is not, in essence, a statement about majority agreement.

Split-brain

is the failure mode where two or more nodes each believe they are the leader, which leads to conflicting writes being accepted.

It can happen for many reasons, most often a network partition or a garbage collection pause (GC pause).

Lease

A is a right/lock/token granted to a process, permitting it to operate on a data object, with a time limit: a time-to-live (TTL).

Once the TTL expires the lease expires automatically and the process is no longer permitted to operate on the object. The process may also release the lease early, or extend it if it needs to.

It is used to stop one process from blocking a data object forever and never letting anyone else use it.

Easy to get wrong when

Thinking the lease alone is enough. The lease is really only the first half of the story: afterwards, the holder may still not know its lease has expired, which leads to it writing in conflict with whoever actually holds the new lease.

Fencing token

A is a token granted in order to block a process that is holding a stale lease. It is usually a monotonically increasing number.

It is the other half of the pair with lease.

Idempotent

describes an operation that can be performed many times and still leave the same final result as performing it once.

For example: SET A 5 always leaves A equal to 5 no matter how many times it runs, but ADD A 5 does not.

This property is the foundation of every safe retry mechanism.

In HTTP, methods such as GET, PUT and DELETE are idempotent at the protocol level. Note that protocol-level idempotence does not automatically confer idempotence on the system as a whole.

Easy to get wrong when

It is confused with commutativity.
Or used to mean safe to call again in some vague, general sense.

Commutative

is the property that the order of operations does not affect the final result.

For example: ADD A 5 then ADD A 2, or ADD A 2 then ADD A 5 — the final result is A + 7 either way, independent of order. MUL A 2 and ADD A 3 are a different matter: there, order does affect the final result.

This is the foundational property of CRDTs (Conflict-free Replicated Data Types ).

Associative

is the property where a merge operation guarantees that how the data is split up and packaged for merging does not change the final result.

$Merge (Merge (A, B), C) = Merge (A, Merge (B, C))$

A system or structure satisfying $Associative + Commutative + Idempotent = Bounded Semi-lattice$ is a perfect foundation for distributed data synchronisation.

Monotonic

describes a value/state that only moves forward, in one direction — usually only increasing, or only getting newer — and never goes backwards or reuses a value/state from the past.

This is the foundational property behind CALM (Consistency As Logical Monotonicity), which says a program/system can achieve eventual consistency WITHOUT coordination between nodes if and only if the program’s logic is monotonic.

At-least-once / At-most-once / Exactly-once / Effectively-once

At-least-once: guarantees no message loss, and accepts that processing may be duplicated.
At-most-once: guarantees no duplicates, and accepts that messages may be lost.
Exactly-once: guarantees a message is processed effectively exactly once — nothing lost, nothing duplicated.

People always aim for exactly-once across the whole system, but it demands very high cost and complexity. In practice, what gets applied is : combining at-least-once with deduplication / idempotence so that the system’s state changes exactly once even when the message arrives twice. For side effects that reach outside — sending an email, calling a third-party API — those side effects need deduplication built into them as well, or they will be performed more than once.

Easy to get wrong when

Using Kafka and thinking exactly-once falls out of it for the whole system. This is a common and mistaken belief: Kafka’s Exactly-Once Semantics (EOS) really only covers its internal processing path (stream-to-stream processing between topics). A consumer remains perfectly capable of receiving and processing a message twice — after a crash before the offset is committed, for example. If the application layer has no deduplication/idempotence mechanism, the system will still process duplicates.
Confusing effectively-once with true exactly-once. Absolute end-to-end exactly-once across a distributed network is theoretically impossible. In practice, every system that works correctly does so because it achieves effectively-once (at-least-once + idempotence).

Byzantine

is the failure mode where nodes send wrong, malicious, or mutually contradictory information to different parts of the network.

The related concept is Byzantine Fault Tolerance (BFT), a system’s ability to tolerate Byzantine faults, usually following $N \geq 3 f + 1$ . That is: to tolerate $1$ Byzantine node, the system needs $3 (1) + 1 = 4$ nodes.

Where $f$ is the number of Byzantine nodes and $N$ is the total number of nodes required.

Easy to get wrong when

It is used for ordinary faults, which are normally crash-stop.

Safety / Liveness

Safety

is the property standing for “nothing bad ever happens”. It guarantees the system never enters an incorrect or invalid state.

Liveness

is the property standing for “something good eventually happens”. It guarantees the system keeps operating and making progress, rather than dying or stalling forever.

These two are a pair for analysing a system, not a trade-off to make. A good system has to satisfy both.

Grey failure

is the failure mode where a node degrades in performance, or returns errors, but still passes its health checks.

Static Stability

is the property guaranteeing that the system serving users keeps running during an incident, without needing active intervention from the control or configuration plane.

It is usually produced by preparing in advance, and by designing the control plane and the data plane to be independent.

If you remember one sentence from The vocabulary of distributed systems

Linearizability is a promise about one object in real time; serializability is a promise about many objects in some order. Most designs pay for the first while needing neither.

Words

marked in this piece

associative adjective · distributed systems: A merge where the grouping does not matter: merging A with B then C equals merging A with the merge of B and C.
Byzantine fault noun · distributed systems: A node that does not merely stop but lies — and may tell different lies to different neighbours.
causal consistency noun · distributed systems: Operations that are causally related are seen in the same order everywhere; unrelated ones may be seen in any order, differently at different replicas.
commutative adjective · distributed systems: An operation where the order of application does not change the final result.
effectively-once noun · distributed systems: At-least-once delivery plus idempotence at the receiver: the message may arrive twice, but the state changes once.
eventual consistency noun · distributed systems: The promise that if writing stops, every replica converges on the same state — and no promise about anything else.
fencing token noun · distributed systems: A monotonically increasing number handed out with a lease, which the storage layer uses to reject anyone holding an older one.
grey failure noun · distributed systems: A node that has degraded or is returning errors, but still passes its own health checks.
happens-before noun · distributed systems: The partial order causality gives you: within a process, from a send to its receive, and transitively through both.
idempotent adjective · distributed systems: An operation whose result after many applications is the same as after one.
lease noun · distributed systems: A permission to act on something, granted with an expiry — a lock with a TTL rather than a lock held until released.
linearizability noun · distributed systems: The guarantee that every operation on one object appears to take effect at a single instant between its call and its return, in real-time order.
liveness noun · distributed systems: The class of property saying something good eventually happens — the system keeps making progress rather than stalling.
monotonic adjective · distributed systems: A value or state that only ever moves one way — forward, newer, larger — and never revisits or reuses what it has passed.
monotonic reads noun · distributed systems: A session guarantee: once you have read a version of the data, you never read an older one.
monotonic writes noun · distributed systems: A session guarantee: your own writes are applied in the order you issued them, never out of order.
quorum noun · distributed systems: The minimum number of nodes that must take part in an operation for it to count — usually sized so reads and writes must overlap.
read-your-writes noun · distributed systems: A session guarantee: a client that has written something sees its own change on the next read.
safety noun · distributed systems: The class of property saying nothing bad ever happens — the system never enters an incorrect or invalid state.
sequential consistency noun · distributed systems: One global order that every node agrees on and that matches each process’s own program order — but need not match real time.
serializability noun · distributed systems: The guarantee that concurrent transactions end with the same result as running them one at a time in some serial order — any serial order.
split-brain noun · distributed systems: The failure where two or more nodes each believe they are the leader, and each accepts writes.
static stability noun · distributed systems: The property that the serving path keeps working through an incident without needing the control plane to act.
strict serializability noun · distributed systems: Serializability plus real time: the serial order the system picks must also agree with the order things actually happened in.

The whole dictionary lives here

Sources

cited in this piece

01
Linearizability: A Correctness Condition for Concurrent Objects Paper

Herlihy, Maurice P.; Wing, Jeannette M. · 1990

The paper that defined the word, and the reason the definition is about a single object. Correctness here is a property of one object's history: every operation looks as though it took effect at an instant between its call and its return, and those instants respect real time. Read it once and the confusion with serializability stops being possible — that one is about many objects and no clock.
02
Conflict-free Replicated Data Types Paper

Shapiro, Marc; Preguiça, Nuno; Baquero, Carlos; Zawirski, Marek · 2011

Where associativity, commutativity and idempotence stop being three separate algebra words and become one engineering result. Make the merge a join on a semilattice and replicas converge without coordination — no leader, no quorum, no rollback. The essay says the semilattice guarantees convergence but not when; this is the paper that proves the first half and is honest about the second.
03
The serializability of concurrent database updates Paper

Papadimitriou, Christos H. · 1979

The other half of the pair, from the database side and eleven years earlier. Serializability asks only that the outcome match *some* serial order of the transactions — which order is not specified and does not have to be the real-time one. That "some" is the whole difference, and it is why strict serializability needs a separate name.
04
Time, Clocks, and the Ordering of Events in a Distributed System Paper

Lamport, Leslie · 1978

Where happens-before comes from. The argument is that a distributed system has no global clock to appeal to, so the only ordering you can actually establish is the partial one causality gives you: within a process, across a send and its receive, and transitively. Everything in the causal-consistency row of the table is downstream of this eight-page paper.
05
Session guarantees for weakly consistent replicated data Paper

Terry, Douglas B.; Demers, Alan J.; Petersen, Karin; Spreitzer, Mike J.; Theimer, Marvin M.; Welch, Brent B. · 1994

The four session guarantees, named and separated: read-your-writes, monotonic reads, monotonic writes, writes-follow-reads. This is the paper behind rank 5.5 and behind the claim that most requests for "strong consistency" are really requests for one of these. They are granted per session, which is why they cost a version vector and a sticky route rather than a consensus round.
06
Keeping CALM: When Distributed Consistency is Easy Paper

Hellerstein, Joseph M.; Alvaro, Peter · 2020

The CALM theorem, stated as an if-and-only-if: a program has a coordination-free distributed implementation exactly when its logic is monotonic. What makes it worth reading rather than quoting is the direction people skip — non-monotonicity is not a hint that coordination might help, it is a proof that you cannot avoid it.
07
The Byzantine Generals Problem Paper

Lamport, Leslie; Shostak, Robert; Pease, Marshall · 1982

Where the 3f + 1 bound comes from, and why it has that shape. The fault being modelled is not a node that stops but a node that lies, differently, to different neighbours — which is why three nodes cannot survive one traitor: the two honest ones cannot tell which of the other two is lying. Reach for this only when the failure really is malicious; ordinary crashes are a cheaper problem.
08
Spanner: Google’s Globally Distributed Database Paper

Corbett, James C.; Dean, Jeffrey; Epstein, Michael; et al. · 2013

The TrueTime entry in the table, in its own words. Spanner does not defeat the clock problem, it bounds and then publishes it: TrueTime returns an interval rather than an instant, and a commit waits out the uncertainty window. That is the honest price of real-time ordering at global scale, and it is paid in latency.
09
How to do distributed locking Article

Martin Kleppmann · 2016

The clearest statement of why a lease is only half the story. The diagram to remember: a client pauses for GC, its lease expires, it wakes up believing it still holds the lock, and writes. No lock service can prevent this from its own side — only a monotonically increasing fencing token checked at the storage layer can.
10
Gray Failure: The Achilles’ Heel of Cloud-Scale Systems Paper

Huang, Peng; Guo, Chuanxiong; Zhou, Lidong; Lorch, Jacob R.; Dang, Yingnong; Chintalapati, Murali; Yao, Randolph · 2017

Names the gap this failure mode lives in: the system observes its own health differently from the way its clients experience it, and gray failure is exactly the region where those two disagree. The useful consequence is that a health check answering for the node rather than for the request is not a detector, and adding more of them does not become one.
11
Static stability using Availability Zones Documentation

Amazon Builders’ Library

Static stability written up by the people who had to operate it. The rule it argues for is that the data plane must keep serving on whatever it already knows when the control plane is unavailable — which means pre-provisioning capacity you are not using, and refusing to make recovery depend on anything that has to succeed during the incident.
12
Designing Data-Intensive Applications Book

Martin Kleppmann · 2017

The one book to read beside this vocabulary. Chapters 5 and 9 are the long version of the consistency table, and they do the thing a glossary cannot: carry each guarantee through to what it costs in replication, in latency and in what a client is allowed to assume. Where this piece names the confusions, the book works out their consequences.

The full list lives here

a quiet word to the author not published · never shown to other readers

Did anything here change how you think about the problem?