Glossary

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

Absolute deadline: A point in time by which a request must finish, carried with the request so each hop computes its remaining budget.
Active-active: A geo-replication setup where several regions accept writes at once, which needs conflict resolution.
Aggregation tree: Gathering results through intermediate nodes. It reduces fan-in and root CPU but does not improve the tail.
Attempt-local slowness: Slowness caused by one attempt (pause, busy disk), so a second attempt is independent. Hedging helps only here.
Barrier: A point where all workers must arrive before any may continue.1 other meaning →
Byzantine fault: A node that behaves arbitrarily or maliciously, for example by lying; tolerating it needs N >= 3f + 1.
Cache: A deliberately kept second copy of data that no protocol forces to stay correct.1 other meaning →A cache is a small, fast place that holds copies of data kept somewhere bigger and slower. When a request finds its data in the cache, that is a hit. When it does not, it is a miss, and the system must go to the slower place (the backing store or origin). The hit rate h is the fraction of requests that hit. The miss penalty is the extra time a miss costs.
CALM: Theorem: a program has a coordination-free consistent implementation if and only if it is monotone.
Clock: A source of time. A wall clock shows date and time and can jump, even backwards, when it is corrected; a monotonic clock only counts forward and is the one to use for measuring durations on one machine.1 other meaning →A wall clock shows the date and time. It is corrected from time to time by a time-sync service (such as NTP) and can therefore jump, even backwards. A monotonic clock only counts forward; it is good for measuring "how long since X" on one machine but means nothing across machines.
Closed timestamp: A timestamp below which a replica promises no new writes, so a follower can serve reads at it.
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.
Consistent cut: A snapshot in which state reflects exactly a prefix of the input, with matching source offsets.
Consistent hashing: Mapping keys and nodes onto a ring so a membership change moves only about K/N keys.Consistent hashing is a way to map keys onto nodes so that adding or removing a node moves only a small part of the keys. A CRDT (conflict-free replicated data type) is a data structure designed so that copies edited independently can always be merged to the same result. Last-write-wins resolves two conflicting versions by keeping the one with the later timestamp and discarding the other.
Control plane: The layer that sends commands and receives status; it moves no data.The data plane is where the real data moves (storage, Spark, the warehouse). The control plane is the layer that only sends commands and receives status. The orchestrator is a control plane.
Copyset: A fixed group of nodes that together hold all replicas of some partition; limiting their number reduces the chance of total loss.
Crash: Any sudden stop: a process killed, the operating system (OS) failing (a kernel panic), a power cut. A crash gives no warning and can happen between any two instructions.
Currencies (three): Waiting, wasted work and weakened semantics: the only ways to pay for resolving a conflict, delay or missing input.
Data plane: Where the real data is stored and moved.The data plane is where the real data moves (storage, Spark, the warehouse). The control plane is the layer that only sends commands and receives status. The orchestrator is a control plane.
Dedup window: The time for which deduplication state is kept; duplicates after it are undetectable.
Definition substitutes for observation: Candidate idea: replace an unobservable property with a checkable definition (for example, leader means holder of the votes in a term).
Durable: An fsync is the system call that forces data from memory onto the disk. Data is durable once it survives a power loss. An fsync takes roughly 0.1 to several ms, so "write to disk before answering" is a real cost.
E[max of N]: Expected maximum of N latency draws; the cost of waiting for all N shards.
Epoch: A number that increases at every leadership change and lets others reject stale leaders.2 other meanings →A whole number that increases each time leadership changes. "Epoch 7" means "the seventh leadership period". Every action is stamped with the epoch, so old leaders can be recognized and ignored.
Escrow: Pre-allocating shares of a global budget to nodes so that only transfers between nodes need coordination.
Eventual synchrony: The assumption that the network is sometimes slow but eventually behaves; it is what makes consensus liveness possible.
Fail-static: The data plane keeps running on the last known configuration when the control plane is unreachable.
Failure detector: A mechanism that decides whether a component has failed, usually from timeouts; it cannot be perfectly correct in an asynchronous system.Any piece of software that decides "that machine is dead". Since a machine cannot announce its own death, every detector works by waiting for a heartbeat or reply that does not come. So every detector is a timeout in disguise.
Failure domain: A set of components that can fail together.A set of components that fail together: machines in one rack share a switch and a power feed; machines in one AZ share a building; every machine running the same buggy deployment shares that bug. When we say two replicas fail "independently", we mean they are in different failure domains.
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.
FLP result: No deterministic consensus algorithm is guaranteed to finish in an asynchronous system with one possible crash.
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.
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.
Gossip: A protocol where nodes periodically exchange state with random peers to spread information cheaply.
Heartbeat: A periodic message used to detect whether the other side is alive and working.A timeout is a rule: "if no answer comes within T, assume something is wrong." A heartbeat is a small message a node sends every few hundred milliseconds to say "I am alive". Another node that stops receiving heartbeats starts to suspect the sender.
Hedge rate: Fraction of requests that were hedged; above the configured percentile it signals request-local slowness.
Hedging: Sending a second copy of a request after a delay (such as p95) and using the first answer.
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.
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 one sentence each: Consistent hashing is a way to map keys onto nodes so that adding or removing a node moves only a small part of the keys. A CRDT (conflict-free replicated data type) is a data structure designed so that copies edited independently can always be merged to the same result. Last-write-wins resolves two conflicting versions by keeping the one with the later timestamp and discarding the other.
In-band coordination: Sharing facts by attaching them to requests that already travel, at zero extra round trips.
Intersection: The overlap between two quorums. Any two majorities of the same set of nodes share at least one member, which is why a majority can carry a decision from one round to the next.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.
Joint consensus: A membership change that requires majorities of both the old and the new configuration during the transition.
Lamport clock: A logical counter where a causal order a to b implies L(a) < L(b).
Last-write-wins (LWW): Merge rule that keeps the version with the latest timestamp; silently discards concurrent writes.Consistent hashing is a way to map keys onto nodes so that adding or removing a node moves only a small part of the keys. A CRDT (conflict-free replicated data type) is a data structure designed so that copies edited independently can always be merged to the same result. Last-write-wins resolves two conflicting versions by keeping the one with the later timestamp and discarding the other.
Leader: 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.
Lease: A lock that expires after a time limit unless renewed.
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.
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.
Majority: More than half of a set of nodes, the usual quorum: any 3 of 5. Any two majorities share at least one member, so a decision made by one is seen by the next, without relying on clocks.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.
Max-connection-age: A setting that forces long-lived connections to close, acting as a forced cache expiry for discovery.
Message: 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:
Node: One machine, or one process, in a cluster. Data is split into partitions (shards), and each partition is kept as several replicas on different nodes.A node is one machine (or one process) in the cluster. A replica is one copy of a piece of data. A partition (also called a shard) is one piece of the data set; each key belongs to exactly one partition. If you have 64 partitions and 3 replicas of each, the cluster holds 64 × 3 = 192 partition-replicas.
Order statistic: If you collect N response times and sort them, the k-th smallest is an order statistic. The 1st is the fastest, the N-th is the slowest, the middle one is the median. Waiting for the k-th response out of N is "k-of-N waiting".
Partial result: Answering after most shards reply and marking the answer as degraded; valid only if the aggregation tolerates a missing input.
Partition: One piece of a data set; each key belongs to exactly one. Partitions are the unit of parallel work and of placement, each kept as several replicas on different nodes.3 other meanings →A node is one machine (or one process) in the cluster. A replica is one copy of a piece of data. A partition (also called a shard) is one piece of the data set; each key belongs to exactly one partition. If you have 64 partitions and 3 replicas of each, the cluster holds 64 × 3 = 192 partition-replicas.
Pause: A process that keeps its state but does nothing for a while, for example during a garbage-collection pause. From outside, a long pause looks the same as a crash, until the process resumes.A crash means the process stops. A pause means it keeps its state but does nothing for a while, for example during a garbage-collection (GC) pause, when a runtime such as the JVM stops all program threads for seconds to clean memory. From outside, a long pause looks the same as a crash.
Percentile (p50, p99, p99.9): The value below which that fraction of observations fall.p50 is the median latency, p99 is the latency that 99% of requests beat. The slowest requests are the tail. When one request needs answers from many servers (a fan-out) it must wait for the slowest one. With 100 servers that each have a 1% chance of being slow, the chance that at least one is slow is 1 − 0.99¹⁰⁰ = 63%. So the user-facing tail is much worse than any single server's tail.
Power-of-two-choices: Pick two servers at random and send to the less loaded; avoids herding.
Pre-vote: A conservative check before an election to avoid disrupting a healthy leader.
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.
Rebalancing: Moving partitions between nodes to even out load or capacity.
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.
Request ID (idempotency key): A client-generated identifier that lets the server detect and ignore repeated requests.
Request-local slowness: Slowness caused by the request itself (large key, pathological query); hedging gives no benefit.
Resharding: Changing the number of partitions or the key-to-partition mapping.
Retry budget: A limit that allows retries only up to a fraction of recent successful requests.
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:
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.
Scatter-gather: Fanning a request out to N shards and waiting for their answers.To query a dataset split over many machines (shards), a coordinator sends the query to the shards (scatter) and merges the answers (gather). The query is finished only when the slowest shard answers, so the latency of the whole is the maximum over shards. Slow outliers (the "tail", measured by percentiles such as p99, the time that 99% of requests beat) therefore hurt more as you add shards.
Semilattice join: A merge operation that gives the same result in any order and when repeated; required for gossip payloads.
Speculative execution: Launching a duplicate of a slow-looking task and taking whichever attempt finishes first.
Split brain: A state where two parts of a system each believe they are in charge.
Subsetting: Each client connects to only k of N servers, bounding connection count.
Tail (a log): The slowest requests, such as those above p99.p50 is the median latency, p99 is the latency that 99% of requests beat. The slowest requests are the tail. When one request needs answers from many servers (a fan-out) it must wait for the slowest one. With 100 servers that each have a 1% chance of being slow, the chance that at least one is slow is 1 − 0.99¹⁰⁰ = 63%. So the user-facing tail is much worse than any single server's tail.
The locality tiers: 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:
Tied request: Requests enqueued at two replicas, each cancelling the other when it starts.
Timeout: The maximum time a caller waits before giving up.A timeout is the longest a caller waits for a reply before giving up. A retry is sending the same request again after a failure or timeout. Retries help when the failure was a rare accident. They add load when the failure is caused by overload.
Token bucket: A limiter that adds tokens at rate R up to capacity C; allows bursts up to C.
TTL: Time to live: how long an entry may be served before it expires.A lifetime attached to a cache entry. After the TTL expires, the entry is dropped or treated as missing.
Unknown outcome: Third commit result besides committed and aborted.
Witness: A voting member that stores no data, placed in a third failure domain to supply a tie-breaking vote.
xDS: A family of APIs by which a control plane pushes endpoint lists to proxies and clients.
δ-CRDT: A state-based CRDT that ships only the recent change instead of the whole state.