Glossary

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

2PL (two-phase locking): Protocol with a growing phase (acquire locks) then a shrinking phase (release only); serialization order is lock-point order.
A schedule: The actual order in which the reads and writes of overlapping transactions were carried out. Concurrency control aims for a schedule equivalent to running the transactions one after another.Two transactions are concurrent if their lifetimes overlap. A schedule (also called a history or an interleaving) is the actual order in which the individual reads and writes of several transactions were carried out. A serial schedule runs one transaction completely, then the next. A serial schedule is always correct, because no two transactions ever overlap. The goal of concurrency control is a schedule that is equivalent to some serial one while still letting transactions overlap.
Abort: Cancel a transaction and undo all its changes.
Abort asymmetry: Commit is one log record; abort must undo all work in place, but is free when writes are out of place.
Acceptor: A replica that votes in a consensus round.
ACID: Atomicity, Consistency, Isolation, Durability: four properties from different mechanisms.
Antidependency (rw edge): T₁ reads an item that T₂ later overwrites, so T₁ must be ordered before T₂.
Asynchronous commit: Acknowledging a commit before its log record is flushed; durability is not guaranteed for a bounded window.
Asynchronous system: A system where message delays are unbounded, so a slow node cannot be told from a dead one.
Atomic commit: Getting all participants to commit or all to abort; needs unanimity.
Autonomous transaction: A child transaction that commits independently of its parent (Oracle).
Availability: Availability is the fraction of time a service works. 99.9% is "three nines", 99.99% is "four nines". Over a year of 8,760 hours, 99.9% allows about 8.76 hours of downtime and 99.99% allows about 52.6 minutes.1 other meaning →
Backoff with jitter: Waiting a growing random time between retries to avoid synchronized retries.
Backward validation: OCC check of my read set against write sets of transactions that committed since I started.
Blocking window: Time during which a 2PC participant that voted yes cannot decide without the coordinator.
Calvin: Deterministic distributed database that agrees the global order first, so there is no vote.
Cascading abort: Aborting a transaction forces others to abort because they read its uncommitted data.
Catalog: The service that knows which tables exist, where they are and their definitions.A catalog is the service that knows which tables exist and where they are. A metastore is the database inside (or behind) a catalog that stores table definitions, partitions and file lists. Compare it with a library card index: it tells you where each book sits and which books exist, without opening any book.
Change data capture (CDC): Turning a database's changes into a stream of records.A feed of every change (insert, update, delete) made to a database table, delivered as a stream of events.
Checkpoint: A summary of table state that bounds the number of commits a reader must replay.1 other meaning →
Closed nesting: Subtransaction whose commit means nothing until the top-level transaction commits.
Coffman conditions: The four conditions for deadlock: mutual exclusion, hold-and-wait, no preemption, circular wait.
Commit: Finish a transaction successfully and make its changes permanent.
Commit point: The moment the commit record becomes durable.
Commit record: The log record that marks a transaction as committed. The transaction counts as committed once this record is safely on stable storage (forced with fsync).A database writes every change into an append-only file called the write-ahead log (WAL) before it changes the data. fsync is the system call that forces written bytes onto stable storage so that they survive a power failure. A transaction counts as committed when its commit record is safely in the log. One fsync on a good SSD costs roughly 20–100 µs.
Commit wait: Waiting out clock uncertainty before acknowledging a commit (TrueTime).
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.
Compensator: An action that semantically undoes a saga step.
Concurrent transactions: Transactions whose lifetimes overlap. Their reads and writes interleave, and concurrency control must make the result equivalent to running them one after another.Two transactions are concurrent if their lifetimes overlap. A schedule (also called a history or an interleaving) is the actual order in which the individual reads and writes of several transactions were carried out. A serial schedule runs one transaction completely, then the next. A serial schedule is always correct, because no two transactions ever overlap. The goal of concurrency control is a schedule that is equivalent to some serial one while still letting transactions overlap.
Conflict: Two operations from different transactions on the same item where at least one writes.Two operations conflict if they come from different transactions, touch the same item, and at least one of them is a write. Three shapes exist: write after write, read after write, and write after read. Operations that do not conflict (two reads of the same row) can be reordered freely.
Conflict serializability: A schedule whose serialization graph has no cycle.
Consensus: Agreement of several machines on one value; needs a majority.The problem of getting several nodes to agree on a value (or, more usefully, on a sequence of values) even though nodes can crash and messages can be lost. Algorithms for it are Paxos, Raft, ZAB and Viewstamped Replication. Part 3 explains them.
Conservative approximation: A cheap test that never misses a real problem but sometimes reports a false one.
Cooperative termination: Participants ask each other for the decision when the coordinator is gone.
Coordinator: The node that drives a distributed transaction.
Dedup store: Table of processed identifiers used to drop duplicates; has a retention window.
DEFERRABLE: Postgres option for a read-only transaction to wait for a safe snapshot.
Dirty read: Reading a value written by a transaction that has not committed.
Dual-write problem: Updating a database and publishing a message atomically with no shared atomic event.
Durable execution: An architecture that logs every external effect of a program and replays the program after a crash.
Effective N: The size of the key space that traffic really uses, usually much smaller than the row count because of skew.
Escalation (lock): Replacing many fine locks by one coarse lock to save lock-manager memory.
Escrow transaction: Reserving a quantity from a balance so that commutative updates need no ordering.
Exactly-once processing: Effects applied once, via at-least-once delivery plus idempotence, or one atomic event.
External consistency: Strict serializability: serializability plus real-time order across transactions.
Force-at-commit: Rule: flush the log before acknowledging a commit.
Forward validation: OCC check of my write set against read sets of still-running transactions.
fsync: System call that pushes a file's data and the device cache to durable media.A system call that asks the OS: "push my file's cached data all the way to the device, and ask the device to empty its own cache too." It is the main tool to make data durable. It is also slow, because it waits for the physical device.
Gap lock / next-key lock: A lock on a range of index keys, including the gaps between them, used to prevent phantoms.
Goodput: Completed work whose result is still wanted.Throughput is work completed per second. Goodput is work completed per second whose result is still wanted. If a client has already given up (timed out), finishing its request adds throughput but no goodput.
Group commit: Many transactions share one log flush.
Heavy tail: A distribution in which a small fraction of items carry most of the total size.A distribution with a few extremely large values (a phone offline for a week) far above the typical ones.
Heuristic decision: Operator's manual resolution of an in-doubt XA transaction, risking atomicity.
HLC (Hybrid Logical Clock): Timestamp combining physical time and a logical counter.
HOT (heap-only tuple): Postgres optimization that avoids index writes when an update changes no indexed column.
Hot key: A key with far more rows than average.One key that receives far more traffic than others (a famous artist's tickets, one celebrity's profile). Traffic to keys is often Zipf-distributed: a few keys take most of the load.
Idempotency key: Unique identifier of an intent, used to make retries safe.
Idempotent: Doing it twice has the same effect as doing it once.An operation is idempotent if doing it twice has the same effect as doing it once. "Set the order status to SHIPPED" is idempotent. "Add 1 to the stock counter" is not. Idempotence is the main tool for living with duplicates.
In-doubt window: Time between issuing a durable commit and learning its outcome.
Intention lock (IS, IX, SIX): Mark on a parent node saying that locks are held or intended below it.
Item: An item is the unit the database protects: a row, a page, a file. The key space is the set of all items. In this mechanism N is the number of items that transactions could choose from, and k is how many items one transaction touches.
Key space: The set of all items that transactions could touch.An item is the unit the database protects: a row, a page, a file. The key space is the set of all items. In this mechanism N is the number of items that transactions could choose from, and k is how many items one transaction touches.
Latch: A short lock inside a database protecting a page or structure.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.
Latch coupling (crabbing): Taking a child's latch before releasing the parent's while descending an index.
Latency: Time one operation takes from request to response.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.
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.
Livelock: Threads constantly change state in response to each other and make no progress.
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.
Lock manager: Component that records which transaction holds which lock and who waits.
Lock point: The instant at which a 2PL transaction holds all of the locks it will ever hold.
Log (append-only log): A stored ordered sequence of records; consumers track their own offset.An event is a small record: "order 77 placed by user 12 at 12:03:04". A log is an append-only file or service: new events are added at the end, and old events are never changed. A topic is a named log (the word comes from systems like Apache Kafka). Every event has an offset, its position in the log (0, 1, 2, …). A reader remembers "I have read up to offset 5,000", and can go back to offset 3,000 and read again. This ability to replay is the foundation of this whole mechanism. A log keeps events for a configured time (retention), for example 7 days, then deletes the oldest ones.
Lost update: Two read-modify-write cycles on one row, where one overwrites the other.
Metastable failure: A failure that persists after its trigger is gone because retries keep the system overloaded.
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\* (USL peak): The worker count √((1−α)/β) at which throughput is highest; beyond it throughput falls.
OCC (optimistic concurrency control): Run without locks, validate at commit, abort if something you read has changed.
Orchestration / choreography: Saga control by a central state machine / by event reactions in each service.
Outbox (transactional): Table written in the same transaction as the state change, relayed to a broker later.
Paxos-commit: Atomic commit where every vote and decision is replicated with consensus.
Percolator: Google system for cross-row transactions on Bigtable, storing the decision in a primary row.
Phantom: A repeated predicate query returns rows that another transaction inserted.
Pivot: A transaction with both an incoming and an outgoing rw edge.
Predicate lock: Lock on a condition (for example price > 100) instead of on rows; intractable in general.
Presumed abort: Default rule: no record of a transaction means it aborted.
Prewrite: Percolator's prepare step: check conflicts, write value and lock.
Probability of a collision: If you throw a balls at random into N boxes, the chance that two particular balls land in the same box is about 1/N. The number of pairs among m things is m(m−1)/2, about m²/2. These two facts give most of the arithmetic here.
Rebase: Re-applying a change on top of a newer table version.
Recoverable schedule: A schedule in which no transaction commits after reading data from one that later aborts.
Relay (outbox): Process that reads the outbox and publishes to the broker.
Rigorous 2PL: 2PL that holds all locks until commit; serialization order equals commit order.
RTT (round-trip time): Round-trip time.Machines talk by sending messages over a network. A message may be late, may arrive twice, may arrive out of order, or may never arrive. The round-trip time (RTT) is the time from sending a request until the reply returns. RTT depends strongly on distance:
Safe snapshot: A snapshot at which a read-only transaction cannot be part of an anomaly.
Saga: Sequence of local transactions with compensators; no atomicity, no isolation.
Savepoint: A bookmark in the undo chain that allows partial rollback.1 other meaning →
Schedule (history): The actual order in which operations of concurrent transactions were executed.
Semantic lock: A "pending" status that tells others not to trust a record.
Sequencer: Component that puts transactions into one agreed global order.
Serial schedule: One transaction runs completely before the next starts.
Serialization graph: Graph with an edge Tᵢ → Tⱼ when an operation of Tᵢ precedes and conflicts with one of Tⱼ.
SI (snapshot isolation): Each transaction reads a consistent snapshot; allows write skew.
Silo: In-memory database design that replaces OCC's global validation with per-record IDs and epoch commit.
SIREAD lock: Postgres's read-tracking entry for SSI; blocks nothing but uses lock-manager space.
Skeen's result: No atomic commit protocol is both safe and non-blocking in an asynchronous system with failures.
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.
SSI: Snapshot isolation plus detection of dangerous rw structures; aborts pivots.
Strict 2PL: 2PL that holds exclusive locks until commit; prevents cascading aborts.
synchronous_commit: Postgres setting that decides whether commit waits for the log flush.
Thomas write rule: In timestamp ordering, discard an obsolete write instead of aborting.
Thrashing: Throughput falling as load rises, because conflict and blocking feed on each other.
Three-Phase Commit (3PC): 2PC plus a pre-commit phase; non-blocking only without partitions.
Throughput: Work completed per unit of time.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.
Timestamp oracle: Service issuing monotonic timestamps.
Timestamp ordering: Giving each transaction a timestamp and aborting operations that would violate timestamp order.
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.
TrueTime: Clock API returning an interval guaranteed to contain true time.
Two Generals problem: The proof that two parties cannot be certain they agree over an unreliable channel.
Two-phase commit (2PC): Prepare then decide; participants give up the right to abort after voting yes.A way to make a change appear in two places atomically (all or nothing). Phase 1: every participant prepares and promises it can commit. Phase 2: when all have promised, everyone commits. If any participant says no, everyone aborts. Until phase 2, the change stays invisible.
Uncertainty interval: Window in which a read cannot tell whether a value happened before it.
Unknown outcome: Third commit result besides committed and aborted.
Vacuum / purge: Background collection of row versions that no snapshot can see.
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 chain: The linked set of versions of one record.
View serializability: A weaker, more faithful correctness criterion than conflict serializability; testing it is NP-complete.
Wait-die / wound-wait: Timestamp-based deadlock prevention schemes (younger dies; older wounds the younger).
Waits-for graph: Graph with an edge T₁ → T₂ when T₁ waits for a lock held by T₂; a cycle is a deadlock.
Write skew: Two transactions read overlapping data and write different rows, jointly breaking a rule either alone would keep.
Write-ahead rule: Log first: redo before commit, undo before the page write.
XA: Industry standard interface for 2PC between transaction manager and resource managers.
Zipf distribution: A distribution where the r-th most common value has frequency about 1/r of the top one.In many workloads a few items are requested very often and most items are requested rarely. Zipf's law says the item of popularity rank i (rank 1 is the most popular) is requested with frequency proportional to i^(−α). The number α (alpha) is the popularity exponent. A larger α means a steeper concentration on the top items.