Glossary

138 terms, in the sense this mechanism uses them. The platform glossary has every term across all mechanisms.

ABD: The classic quorum algorithm for a linearizable register: a read collects values from a majority, then writes the winning value back to a majority before returning.
Abort / rollback: Cancel a transaction and undo its changes.
Add-wins: The OR-Set rule: an add that a concurrent remove has not observed survives.
Anomaly: A result that no serial execution could produce but a concurrent one did.A result that no serial (one-after-another) execution could ever produce, but that a concurrent execution did. Example: two withdrawals each check "there is enough money" and both succeed, although only one could have succeeded if run one after the other.
ANSI SQL isolation levels: The standard's four levels (Read Uncommitted, Read Committed, Repeatable Read, Serializable), defined by prohibited anomalies; ambiguous and incomplete.
Anti-dependency (rw edge): Tᵢ reads a version that Tⱼ then overwrites, so Tᵢ must come before Tⱼ.
Anti-entropy: A background process that compares replicas and repairs differences; the only repair method that guarantees convergence.
Approximation rule: When an exact test is intractable, systems and verifiers use a conservative approximation and pay in false positives.
Arbitrate: To make replicas converge by choosing one winning write and discarding the others (for example last-write-wins).
Availability: Total availability: every request to every non-failing node gets a non-error response.1 other meaning →
Bound rule: A liveness claim such as "eventually" is useful only when someone states a bound.
Bounded counter (escrow CRDT): A counter that pre-allocates quota to each replica and coordinates only when a replica uses up its quota.
Bounded staleness: A guarantee that a read is never more than a stated amount of time (or number of versions) behind.
BSP barrier: A "wait for everyone" step in bulk-synchronous parallel computation.
CALM: Theorem: a program has a coordination-free consistent implementation if and only if it is monotone.
CAP theorem: During a network partition, a system cannot provide both linearizability and total availability.
Causal consistency: All replicas see causally related operations in the same order; concurrent operations may be seen in any order.
Causal stability: The state in which every replica is known to have seen an operation, so metadata about it can be discarded.
Causal+: Causal consistency plus a convergence rule for concurrent conflicting writes (from COPS).
Commit: Finish a transaction successfully and make its changes permanent.
Commutative: Two operations give the same result in either order (for example two decrements).A combining operation is associative if grouping does not matter: (a + b) + c = a + (b + c). It is commutative if order does not matter: a + b = b + a. It is invertible if you can undo it: subtract to undo an addition. Sum and count have all three properties. Maximum is associative and commutative but not invertible. Median has none of the three in a useful form. These properties decide how cheaply an aggregate can be computed piece by piece.
Compare-and-swap (CAS): An atomic instruction that updates a variable only if it still has the expected old value.A lock or latch lets only one thread enter a piece of code or data at a time (a latch is a short lock inside a database). CAS (compare-and-swap) is one CPU instruction: "set this variable to new only if it still equals old". It either succeeds or fails and never blocks. Lock-free algorithms are built from it.
Concurrency: Several transactions or tasks in progress at the same time, their steps interleaved. The database decides which interleavings of their reads and writes are allowed.Two transactions are concurrent when their lifetimes overlap. An interleaving (or schedule) is the exact order in which their individual reads and writes are mixed. If T1 reads, then T2 reads, then T1 writes, then T2 writes, that is one interleaving. There are many possible ones, and the database decides which are allowed.
Conserved-cost rule: A design that seems to remove a cost has moved it to another party or time.
Consistent prefix: A reader only sees states that are prefixes of the write order.
Convergence: Any two replicas that have delivered the same set of updates are in the same state.
Cursor stability: A level between Read Committed and Repeatable Read where a row being worked on is locked, as with SELECT ... FOR UPDATE.
CvRDT / CmRDT: State-based CRDT (ships whole states, merge is a least upper bound) / operation-based CRDT (ships commuting operations, needs reliable causal broadcast).
Dangerous structure: Two consecutive rw edges in a dependency graph; every SI anomaly cycle contains one.
Dekker pattern: A two-variable test (each client writes one variable then reads the other) used to show that local reads and writes cannot be sequentially consistent.
Dependency graph: Graph of committed transactions with ww, wr and rw edges; serializable if and only if acyclic.
Dependency list: An explicit list of the writes that a write depends on, used to track causality.
Dirty read: Reading a value written by a transaction that has not committed.
Dirty write: Two uncommitted transactions overwrite the same row in an incoherent order.
Distributed consistency model: A promise about recency and order for one object with many copies.
Elle: A checker (used with Jepsen) that infers a dependency graph from a recorded history and looks for cycles.
Eventual consistency: A liveness property: if no new updates arrive, replicas eventually converge.
External consistency: Strict serializability: serializability plus real-time order across transactions.
False dependency: An ordering constraint created by coarse tracking, which makes a write wait for something it never depended on.
False independence (false concurrency): Two causally ordered writes that look concurrent because metadata was truncated.
Fencing token: A growing number issued with a lock or lease; the resource rejects requests with an older number.An epoch is a number that only goes up, for example "this is leadership term 7". A fencing token is such a number attached to every request, so that a storage system can refuse a request carrying an older number than one it has already seen.
First-committer-wins / first-updater-wins: SI conflict rules: the first writer to commit (or to touch the row) wins; the other aborts.
Follower: In many systems one replica of each partition is the leader: it accepts all writes and sends them to the other replicas, the followers. A follower copies what the leader tells it.
FOR UPDATE: A SQL clause that locks the selected rows until the transaction ends.
G-counter: A grow-only counter CRDT: a vector of per-replica counts, merged by pointwise max, valued by the sum.
G0, G1a, G1b, G1c, G-single, G2-item, G2: Adya's names for cycle shapes (dirty write, aborted read, intermediate read, circular flow, single-rw cycle, item write skew, any rw cycle).
Granularity mismatch (mismatch rule): The unit the system tracks differs from the unit the invariant needs, causing waste or missed conflicts.
GTID: Global transaction identifier (MySQL); a token naming a point in the replication history.
Happens-before: The partial order of operations that could have influenced one another.
HAT (Highly Available Transactions): The set of transactional guarantees achievable with total availability.
Hi/Lo allocation: Handing out identifiers from blocks that a service reserves in advance.
Hinted handoff: Storing a write on another node as a hint while the owner is down; yields a sloppy quorum.
History: The sequence of reads and writes a system performed, as observers saw them.An object is one thing the database stores and names (a row, a key, a file). Each write to it creates a new version. A history is the list of all reads and writes the system performed, in the order each observer saw them. This mechanism is about which histories are allowed.
I-confluence: An invariant is I-confluent if merging two valid states that diverged from a common ancestor always yields a valid state.
Interleaving: The order in which the operations of concurrent transactions are mixed.1 other meaning →Two transactions are concurrent when their lifetimes overlap. An interleaving (or schedule) is the exact order in which their individual reads and writes are mixed. If T1 reads, then T2 reads, then T1 writes, then T2 writes, that is one interleaving. There are many possible ones, and the database decides which are allowed.
Invariant: A rule about the data that must always hold.
Isolation level: A set of forbidden dependency-graph shapes.
Join-semilattice: A set with a "least upper bound" operation; the algebraic structure behind state-based CRDTs.
Lease: A lock that expires after a time limit unless renewed.
Linearizability: Every operation appears to take effect atomically at one instant between its invocation and response, in real-time order.
Little's Law: L = λW: average items in a system = arrival rate × average time in the system.Throughput is work finished per second. Latency is how long one operation takes. Little's Law links them to the number of operations in progress: L = λ × W, where λ is the arrival rate (per second), W is the average time one operation spends in the system, and L is how many are inside the system at the same time. Example: 1,000 requests per second, each taking 20 ms (0.02 s), means 1,000 × 0.02 = 20 requests in flight at any moment. This is an identity, not a design choice.
Liveness: The property that something good eventually happens, such as a leader being elected.1 other meaning →A safety property says "this bad thing never happens" (you can find a counterexample in a finite amount of time). A liveness property says "this good thing happens eventually" (no finite observation can prove it wrong). Part 3 explains why this difference is essential. For now remember: "never" can be tested, "eventually" cannot.
LOCAL_QUORUM: A Cassandra level that applies the quorum rule within one datacenter only.
Lock (mutex): A flag that only one thread can hold at a time.A lock or latch lets only one thread enter a piece of code or data at a time (a latch is a short lock inside a database). CAS (compare-and-swap) is one CPU instruction: "set this variable to new only if it still equals old". It either succeeds or fails and never blocks. Lock-free algorithms are built from it.
Lost update: Two read-modify-write cycles on one row, where one overwrites the other.
LSN: Log Sequence Number: the position of a record in the log.
LWW (last-write-wins): A merge rule that keeps the write with the highest timestamp.
Materialize the conflict: Make transactions write one shared row so the engine can detect their conflict.
Monotone (CALM): A computation in which adding facts never retracts a conclusion.
Monotonic atomic view: Once a transaction has seen one effect of another transaction, it sees all of that transaction's effects.
Monotonic reads: Once a client has seen a value, it never sees an older one.
Monotonic writes: A client's writes are applied in the order issued.
MVCC: Keeping old versions so readers do not block writers and writers do not block readers.A technique where an update does not overwrite a row but creates a new version, so that readers who started earlier can still see the old one. Each reader works on a consistent snapshot. Old versions are removed later by a cleanup job (called vacuum in Postgres).
N, R, W: Number of copies, number of copies asked on a read, number of copies that must acknowledge a write.
Next-key lock: An InnoDB lock on a row plus the gap before it in an index.
Non-repeatable read: Reading the same row twice in a transaction and getting different values.
NP-complete: A class of problems with no known fast general solution.
Object: One thing a database stores and names: a row, a key, a file. Each write creates a new version of it, and consistency models say which orders of reads and writes of objects are allowed.An object is one thing the database stores and names (a row, a key, a file). Each write to it creates a new version. A history is the list of all reads and writes the system performed, in the order each observer saw them. This mechanism is about which histories are allowed.
Observer-count rule: Consistency cost depends on the number of observers and their distance, not on data volume.
One-way delay: The time one message takes to reach another machine, half a round trip. It is set by distance and the speed of light in fibre, about 80 ms from Frankfurt to Singapore, and no software can reduce it.A message that goes to another machine and back costs a round trip. The one-way delay (written d here) is the time one message needs. Frankfurt to Singapore is about 80 ms one way, 160 ms round trip, and no software can reduce it, because it is set by the speed of light in cable and by the route.
OR-Set: Observed-remove set: a set CRDT in which each add has a unique tag and a remove deletes only observed tags.
Out-of-band channel: A path for information (a person, a queue, another service) that bypasses the system's own replication.
Overlap: The property that any read set and any write set share at least one replica when R + W > N.
PACELC: If Partition then Availability or Consistency; Else Latency or Consistency.
Partition: A network partition is a failure where two groups of machines cannot talk to each other, though each group still works. A quorum is a majority (for 3 copies, any 2). Quorums matter because any two majorities share at least one member.3 other meanings →
Partition the slack: Splitting a global budget among replicas so each acts locally until its share is spent.
Phantom: A repeated predicate query returns rows that another transaction inserted.
Pivot: A transaction with both an incoming and an outgoing rw edge.
PN-counter: A counter CRDT made of two G-counters, one for increments and one for decrements.
Predicate: The condition in a query that decides which records qualify.The condition in a query that decides which records qualify. In WHERE price < 500 AND city = 'Pune', the predicate is price < 500 AND city = 'Pune'.
Predicate over histories: A rule that says yes or no to a sequence of observed reads and writes; what a consistency model is.
Primary (leader): The replica that accepts writes and sends them to the followers. Followers apply them a little later (replication lag), so a read from a follower can return older data.A replica is another copy of the same data on another machine. The primary (also leader) accepts writes and sends them to the followers. Followers apply the writes a little later. The delay is replication lag. A read from a follower can therefore return older data than a read from the primary.
Primary / leader: The copy that accepts writes.
Quorum: A majority of replicas.A quorum is a group of nodes big enough that its answer counts. The usual quorum is a majority: more than half. With 5 nodes, any 3 form a majority. The key fact: any two majorities of the same set share at least one member. Why? If two groups of 3 from 5 nodes had no member in common, they would need 6 different nodes, but there are only 5. This is the pigeonhole principle. It is arithmetic; it uses no clock and holds however slow the network is. We use it again and again.
Read atomicity: A reader sees all or none of another transaction's writes.
Read repair: Fixing stale replicas when a read notices a difference; never fixes cold data.
Read set / write set: The rows a transaction read / changed.
Read skew: Reading two related items at two different moments and seeing an inconsistent pair.
Read Uncommitted (RU): The lowest level; forbids only dirty write.
read_committed: Kafka consumer setting that hides records of aborted or open transactions.
Read-index read: A read in which a follower asks the leader for its current log position and waits until it has applied that position.
Read-your-writes: Guarantee that a client sees its own earlier writes; achieved with a version token in the key.
Reliable causal broadcast: A delivery service that gets every message to every replica, in causal order.
Repeatable Read (RR): A level whose meaning differs per engine (ANSI, PostgreSQL = SI, InnoDB hybrid).
Replica: A copy of the same data on another machine. The primary takes writes and the followers apply them a little later, so a follower can lag behind.A replica is another copy of the same data on another machine. The primary (also leader) accepts writes and sends them to the followers. Followers apply the writes a little later. The delay is replication lag. A read from a follower can therefore return older data than a read from the primary.
Replica / follower: A copy of the data that applies the primary's writes after a delay.
Replication lag: The delay between a write on the primary and its appearance on a replica.
Right-algebra rule: If an operation is restated so order does not matter, coordination becomes optional.
Round trip (RTT): The time for a message to reach the other side and the answer to come back: about 0.2–1 ms inside a datacenter, 70–250 ms between continents, against about 100 ns for a memory read.Latency is how long one operation takes. Throughput is how much work finishes per second. A round trip (RTT, round-trip time) is the time for a message to reach the other side and for the answer to come back. Inside one datacenter an RTT is about 0.2–1 ms. Between continents it is 70–250 ms. A memory read takes about 100 ns, so a network round trip inside a datacenter is roughly 10,000 times slower.
Safety: The property that nothing bad ever happens, such as two leaders acting at the same time.A safety property says "this bad thing never happens" (you can find a counterexample in a finite amount of time). A liveness property says "this good thing happens eventually" (no finite observation can prove it wrong). Part 3 explains why this difference is essential. For now remember: "never" can be tested, "eventually" cannot.
Safety property: A "bad thing never happens" property, violated by a finite prefix of a history.
Sequential consistency: One total order that all clients agree on, respecting each client's program order, with no real-time requirement.
Serial execution: Transactions run strictly one after another.Running transactions strictly one after another. It is always correct and always slow. Most of this mechanism is about how close a faster system can come to "as if serial".
Serializable: Equivalent to some serial order; the dependency graph is acyclic.
Session guarantees: Read your writes, monotonic reads, monotonic writes, writes follow reads.
Sloppy quorum: A write acknowledged by nodes that are not the owners; does not guarantee read overlap.
Snapshot: A frozen consistent view of the database at one moment.1 other meaning →A lock makes other transactions wait while you use a row. A snapshot is a frozen, consistent view of the database as it was at one moment; with it, readers do not need locks, because they read old versions while writers create new ones. This second idea is called MVCC (multi-version concurrency control): the database keeps several versions of each row. Both are mechanisms. This mechanism is about the promises they are used to keep.
Snapshot isolation (SI): Reads from a snapshot at start plus a commit-time check of write sets; permits write skew.
SSI: Snapshot isolation plus detection of dangerous rw structures; aborts pivots.
Sticky routing: Always sending a client to the same replica.
Stranded slack: Reserved quota at a replica where nobody consumes it.
Strict serializability (external consistency): Serializability plus real-time order.
Strong eventual consistency: Eventual delivery plus convergence: same set of updates means same state.
Thomas write rule: In timestamp ordering, discard an obsolete write instead of aborting.
Token rule: A guarantee spanning several operations is moved to the client as a monotone handle.
Tombstone: A marker record that says a key was deleted; must outlive every older copy.
Transaction: A group of operations executed as one all-or-nothing unit.A group of reads and writes that the database treats as one unit: either all of it takes effect, or none of it does. In SQL you mark it with BEGIN ... COMMIT (make it permanent) or ROLLBACK (throw it away). Example: moving 30 from Anna's wallet to Ben's wallet.
Transactional causal consistency: Causal consistency for transactions; the strongest transactional guarantee compatible with total availability.
u/(1-u): Cleaning cost per byte reclaimed when a fraction u of a unit is live.
Vantage point (observer): A place from which someone can read the data, such as a replica, a cache or a region.
Version: The state of an object after one write. Multi-version systems keep several versions so that readers can see a consistent past state while writers create new ones.An object is one thing the database stores and names (a row, a key, a file). Each write to it creates a new version. A history is the list of all reads and writes the system performed, in the order each observer saw them. This mechanism is about which histories are allowed.
Version vector: A table of "writer to latest counter" used to compare replica histories.
Watermark: Declared non-decreasing lower bound on the event times of future arrivals.1 other meaning →Every event carries a timestamp of when it happened (event time), which differs from when the job sees it (processing time). Events arrive late and out of order: a phone with no signal sends its events 5 minutes after they happened. A watermark is a marker flowing through the stream that says "no event with a timestamp earlier than T should arrive any more." It is the job's best guess of how complete the input is. When the watermark passes the end of a time period, the job may treat that period as complete. Watermarks are a guess, and late events can still violate them. The rules of when it is correct to emit a result (event time versus processing time, how late is too late) are a topic of their own. In this mechanism we need only the idea above. We study the machinery that holds data until the watermark allows an answer.
Window: The time during which two operations can conflict (lag, snapshot age, TTL, read-to-write gap).2 other meanings →
wr edge / ww edge: Tᵢ writes a version that Tⱼ reads / Tⱼ overwrites.
Write skew: Two transactions read overlapping data and write different rows, jointly breaking a rule either alone would keep.
Writes follow reads: A write made after reading a value is ordered after the write that produced it.
δ-CRDT: A state-based CRDT that ships only the recent change instead of the whole state.