Glossary

A background process that compares replicas and reconciles differences, repairing data that read repair never touches because nobody reads it. Usually implemented with Merkle trees.

Advertising the same IP address from many locations and letting internet routing deliver each packet to the topologically nearest one. How CDNs and public DNS resolvers route users without DNS tricks, and it fails over faster than DNS because the network does the work.

Retry until acknowledged. Never loses messages, sometimes duplicates them. The correct default for anything that matters, paired with idempotent processing.

Send without retrying. Never duplicates, sometimes loses. Acceptable for metrics, telemetry, and logs where one missing sample is invisible.

The proportion of time a system can serve requests. Distinct from durability: eleven nines of durability with four nines of availability means your data is safe but occasionally unreachable.

A balanced tree of fixed-size pages kept sorted by key, updated in place. High fanout makes it shallow — any row in a billion-row table is three or four page reads away — which is why it has dominated transactional databases for decades.

Deriving QPS, storage, and bandwidth from user counts and payload sizes, rounded aggressively. Its purpose is to change the design — an estimate that only confirms your plan was probably not worth doing.

The mechanism by which a slow consumer signals a fast producer to slow down. Without it a queue grows unboundedly and converts a throughput mismatch into a latency problem that looks fine on every dashboard until memory runs out.

How much of a system a single fault can damage. Cell-based architecture exists to bound it: partitioning the whole stack into independent cells means a bad deploy or a poison request harms one cell rather than everything.

A compact probabilistic structure answering "definitely not present" or "possibly present". LSM-trees keep one per SSTable so a read can skip most files, which is what makes lookups for non-existent keys cheap.

Block Range INdex — stores only min/max values per range of physical blocks. Tiny and effective when the column correlates with physical order, such as an append-only timestamp column; useless on randomly ordered data.

Isolating resources (separate thread pools and connection pools per dependency) so one saturated downstream cannot exhaust everything else. Named after ship compartments.

How fast an incident is consuming the error budget. Alerting on burn rate rather than a fixed threshold means a fast burn pages immediately while a slow one opens a ticket, which is what keeps alerts actionable.

Many keys expiring simultaneously — typically because they were populated together with an identical TTL — sending a wall of misses to the origin. Fixed by jittering TTLs.

Repeated requests for keys that do not exist, which find nothing cached and hit the database every time. Fixed by caching the negative result briefly, or with a Bloom filter.

Also called thundering herd. A hot key expires and every concurrent request misses at once, all hitting the origin together. Fixed by single-flight locking, probabilistic early expiry, or stale-while-revalidate.

The application checks the cache, and on a miss reads the database and populates it. The default caching pattern: only requested data is cached, and a cache failure degrades to slow rather than broken.

During a network partition you must choose between consistency (specifically linearizability) and availability. You never choose partition tolerance — partitions are a property of networks. Outside a partition, CAP constrains nothing.

Causally related operations are observed in the same order by everyone; concurrent operations may be seen in any order. Notable because it is the strongest model achievable while remaining available during a partition.

Partitioning the entire stack — not just the data — into independent cells, each serving a subset of customers with no shared state. Bounds blast radius and lets you deploy to a fraction of traffic at a time. The router in front is the one shared component, so it must be boring.

Reading a database's replication log and projecting the changes into other systems. Makes the database's log the single ordered source of truth, avoiding the drift that dual writes cause.

Services react to each other's events with no central coordinator. Loosely coupled and easy to extend, at the cost that no single place describes the whole flow, which makes debugging an exercise in archaeology. Contrast with orchestration.

After repeated failures, stop calling a dependency and fail fast, giving it room to recover and freeing your own resources. Periodically probes to decide when to close again.

After an error rate crosses a threshold, stop calling a dependency and fail fast, giving it room to recover. Three states — closed, open, half-open — with a probe deciding when to close. Trip on error rate over a window, not a raw count, or it fires falsely at low volume.

An index whose leaf level is the table — rows are physically stored in index order. There can only be one. In InnoDB it is the primary key, which is why secondary lookups cost two traversals and why keeping the primary key small matters.

The period after a cache restarts or scales out when hit rate is zero and the origin receives full traffic. At a 95% steady-state hit rate that is twenty times normal load, which is why caches are warmed and nodes restarted gradually rather than together.

The background process in an LSM-tree that merges immutable SSTables, discarding overwritten values and tombstones. It is what makes reads tolerable, and its IO cost is what makes LSM tail latency spiky.

Letting in-flight requests finish on an instance being removed, after it stops receiving new ones. Skipping the wait between deregistering and exiting is the classic cause of 502s during deploys.

Getting a group of unreliable machines to agree on a value, or more usefully on an ordered log, and never change their minds. Feeding an identical log into identical state machines gives linearizable replication.

Mapping both servers and keys onto a circular hash space, with each key owned by the first server clockwise. Adding or removing a server relocates only about K/N keys instead of nearly all of them.

A set of consumers sharing a subscription, where each partition is assigned to exactly one member. Adding consumers beyond the partition count buys nothing, and membership changes trigger a rebalance that briefly stops consumption.

How far behind the head of the log a consumer is. The single most important metric for a streaming pipeline: growing lag means consumption is slower than production, and the queue is hiding the mismatch rather than fixing it.

An index containing every column a query needs, so the query is answered from the index alone without touching the table — an index-only scan. Often the single largest query win available.

Command Query Responsibility Segregation — separating the write model from one or more read models. Justified when read and write shapes genuinely diverge, at the cost of eventual consistency between them. Independent of event sourcing, though the two are frequently conflated.

Conflict-free Replicated Data Type — a structure whose merge function is deterministic and order-independent, so concurrent updates converge without coordination. Well-known constructions exist for counters, sets, and collaborative text.

Paginating with a key from the last row seen rather than an offset. O(1) per page instead of O(offset), and stable when rows are inserted or deleted mid-traversal — both of which OFFSET/LIMIT gets wrong.

Where messages go after exhausting their retries, so one poison message cannot block a partition forever. A dead-letter queue nobody monitors is a data-loss mechanism with extra steps.

Passing a remaining time budget down a call chain rather than giving each hop its own independent timeout. Prevents an inner call from having a longer timeout than its caller's entire budget.

Whether data still exists later, as opposed to whether you can reach it now. Object stores advertise eleven nines of durability alongside far weaker availability.

The failure allowance implied by an SLO — 99.9% monthly permits about 43 minutes. Treated as a resource to spend on risky deploys and migrations, and a trigger to stop shipping features when exhausted.

Storing the sequence of events as the source of truth and deriving current state by replay. Buys a complete audit trail and new projections from history; costs schema evolution of old events, replay time, and genuine difficulty with deletion. Most systems should not do this.

When something actually happened, as opposed to processing time — when your system saw it. Computing on processing time makes results depend on infrastructure conditions, so a replay of the same data produces a different answer.

If writes stop, replicas eventually converge. That is the entire guarantee: nothing about when, and nothing about what you see meanwhile, including values appearing to move backwards.

Exactly-once delivery is impossible, being a direct consequence of the two generals problem. Exactly-once effect is achievable: at-least-once delivery plus deduplication or idempotent operations.

A monotonically increasing number issued with a lock and checked by the resource, which rejects any write carrying a lower token. The only thing that makes distributed locking safe against a paused client, since a lock service can revoke permission but not the ability to act.

In a fully asynchronous system where even one node may fail, no deterministic algorithm guarantees consensus. Real protocols sidestep it with timeouts and randomisation, giving safety always and liveness when the network cooperates.

A component that is degraded rather than down — slow, intermittently erroring, or returning corrupt data while passing health checks. More damaging than a crash, because it keeps receiving traffic and consumes callers' resources.

Lamport's causal ordering: A happens-before B if they are sequential in one process, or A is a send and B its receive, or via a chain of those. Events with no such relation are concurrent, meaning causally independent rather than simultaneous.

Deciding whether to keep a trace at ingress, before knowing how it turns out. Cheap and simple, and it discards the rare slow or failed traces you most wanted. Tail-based sampling decides after seeing the whole trace, at the cost of buffering.

A probe deciding whether a backend should receive traffic. Shallow checks test the process; deep checks test dependencies — and deep checks can eject an entire fleet at once when a shared dependency degrades.

Sending a request to more replicas than strictly needed and using the first responses to arrive. Trades extra load for a shorter tail, since you no longer wait on the slowest replica.

When a target replica is unreachable, another node accepts the write and holds a hint to deliver it later. Improves durability and availability, and is part of why sloppy quorums break the R+W>N guarantee.

A timestamp pairing a physical component (tracking wall time within the clock-skew bound) with a logical counter. Preserves causality, stays meaningful as approximate wall time, and is constant size. Used by CockroachDB, MongoDB, and YugabyteDB.

A client-generated identifier for a logical operation, sent unchanged across every retry. The server inserts it under a unique constraint, stores the response against it, and replays that stored response instead of re-executing.

A map from term to the list of documents containing it. The inverse of an ordinary index, and what makes 'find every document containing this word' fast where a scan cannot.

A single counter per process, advanced to max(local, received) + 1 on receive. Gives a total order consistent with causality, but cannot detect concurrency — for that you need vector clocks.

Resolving conflicts by keeping the highest timestamp. Always converges, which is why it is popular, but it silently discards data and, with wall clocks, lets the node with the fastest clock win every race.

Dynamo-style: clients write to and read from several replicas directly, with no leader and therefore no failover. Relies on quorums, read repair, and anti-entropy to converge.

A lock with an expiry, so a crashed holder does not block forever. Fixes liveness but not safety: the holder and the service judge expiry by different clocks, so a paused client can act after its lease has gone.

Every operation appears to take effect atomically at an instant between its invocation and its response, so a completed write is visible to every subsequent read. A single-object, real-time guarantee whose price floor is a network round trip.

Deliberately rejecting requests when overloaded, rather than queueing them all and degrading for everyone. A fast 503 is usually better for both parties than a 30-second wait.

Rejecting work when overloaded rather than queueing it. A queue converts overload into unbounded latency serving requests whose callers have already given up; shedding by priority keeps the requests that matter.

Log-Structured Merge tree: writes land in an in-memory memtable, flush to immutable sorted files, and are merged by background compaction. Very fast writes at the cost of read amplification and compaction-driven tail latency.

The in-memory sorted structure at the front of an LSM-tree that absorbs writes before they are flushed to disk as an SSTable. Backed by a write-ahead log so the write is durable immediately.

A tree of hashes where each node hashes its children. Two replicas compare root hashes first and descend only into differing subtrees, so finding a handful of differences among a billion keys costs a logarithmic number of comparisons.

A clock that only ever moves forward, whose absolute value is meaningless. The correct source for measuring elapsed time; wall-clock time can step backwards on NTP correction and produce negative durations.

A guarantee that a client never sees time run backwards — having read a value, it will not subsequently read an older one. Typically obtained by pinning a client to one replica.

Mean time to recovery. Since availability is MTBF / (MTBF + MTTR), halving MTTR is usually far cheaper than doubling MTBF, which is why fast rollback and detection beat chasing reliability.

Accepting writes at more than one leader — for multi-datacenter, offline clients, or collaborative editing. The cost is genuine write conflicts, since there is no global order to appeal to.

Multi-Version Concurrency Control — keeping several versions of each row so readers never block writers and vice versa. The cost is dead versions requiring vacuum, and long-running transactions that prevent reclamation and cause bloat.

One tenant consuming shared resources — CPU, IO, connection pool, a hot shard — and degrading everyone else. Contained with per-tenant quotas, bulkheads, and moving outlier tenants to dedicated infrastructure.

A coordinator explicitly drives the steps of a workflow. The flow is visible and testable, at the cost of a central component that must not fail. Contrast with choreography.

A regional parent cache that CDN edge nodes fetch through, so an uncached popular object produces one origin request rather than one per PoP. Also called tiered caching.

Writing an event row into an outbox table inside the same transaction as the business write, with a separate process publishing from it. Makes "update and publish" atomic without a distributed transaction.

If there is a Partition, choose Availability or Consistency; Else, choose Latency or Consistency. The "else" branch is the one that applies almost all the time, and it is what makes PACELC more useful than CAP alone.

The defining property of distributed systems: some components work and others do not, and you cannot reliably tell which. Contrast with a single process, where failure is total.

Splitting data across machines so each holds a subset — buying storage and write capacity. Orthogonal to replication, which puts the same data on several machines for availability.

A detector that outputs a continuous suspicion level derived from the observed distribution of heartbeat arrivals, rather than a binary alive/dead at a fixed threshold. Adapts to a network that is simply slower today.

Sample two backends at random and send to the less loaded. Needs no global state and avoids the herding that "always pick the least loaded" causes when many balancers act on the same stale information.

A subset of replicas that must respond for an operation to count. With R + W > N the read and write sets must overlap, bounding staleness — though not providing linearizability.

A consensus protocol designed for understandability: randomised election timeouts, majority commit, and an election restriction ensuring any node that can win an election already holds every committed entry.

Disk reads performed per logical read. High in LSM-trees, where a key may live in the memtable or any of several levels; low in B-trees, where it is roughly the tree depth.

Noticing during a read that a replica returned a stale version and writing the current one back. Free, since the read already happened, but it only ever repairs data someone reads.

A guarantee that a client always sees its own updates, even when reads are served from lagging replicas. Usually the cheapest correct fix for "I saved it and it did not change".

Rate, Errors, Duration — the three signals to monitor for a request-driven service. Its counterpart for resources is USE: Utilisation, Saturation, Errors.

The delay between a write being applied on the leader and on a follower. Usually milliseconds, occasionally minutes, and the cause of read-your-writes, monotonic read, and consistent prefix anomalies.

Tenant isolation enforced by the database rather than by application code, so a query missing its tenant filter returns nothing instead of returning another customer's data. It fails closed, which is why it beats relying on code review.

You can optimise for two of Read overhead, Update overhead, and Memory (space) overhead, but not all three. The reason storage engines differ rather than one being universally best.

A long-running transaction split into local transactions, each with a compensating action to undo it. Avoids distributed locks and a coordinator, at the price of no isolation — intermediate states are visible, so compensation must be a business-level concept.

An immutable chunk of an index, written once and merged in the background — structurally the same design as an LSM-tree. Why search is near-real-time rather than real-time: documents become visible only on refresh.

The fraction of rows a predicate matches. Indexes pay off when selectivity is low (a few percent); when a predicate matches most of the table, a sequential scan is genuinely cheaper and the planner is right to choose it.

Transactions produce a result equivalent to some serial order — not necessarily the real-time one, so a serializable database may still return stale data. Adding the real-time requirement gives strict serializability.

Client-centric promises — read-your-own-writes, monotonic reads, monotonic writes, consistent prefix — that fix specific user-visible anomalies cheaply, without paying for system-wide linearizability.

A window whose boundaries are defined by a gap in activity rather than a fixed clock interval. The one that models actual user behaviour, and the one whose state is hardest to bound.

Accepting writes on whatever nodes are reachable rather than the key's designated home replicas, keeping the system writable during a partition. Improves availability and durability and voids the R+W>N overlap guarantee.

Each transaction reads from a consistent snapshot taken at its start. Prevents dirty and non-repeatable reads and, in practice, phantoms — but permits write skew, which is what separates it from serializable.

Two nodes simultaneously believing they are the leader, typically after a partition or a failover where the old leader returns. Accepting writes on both sides produces conflicts; fencing tokens are the standard defense.

Sorted String Table — an immutable file of key-value pairs written in sorted order when a memtable is flushed. Immutability is what allows compaction to run safely in the background.

A cache directive permitting a stale response to be served while a fresh one is fetched in the background. Its companion stale-if-error turns an origin outage into stale-but-working content.

Feeding an identical, consensus-ordered log of commands into identical deterministic state machines so every replica reaches the same state. The bridge from "agree on a log" to "a replicated database".

Pinning a client to one backend, usually by cookie. Simple, and it prevents clean draining, keeps load uneven, and blunts autoscaling — which is why stateless servers with shared session storage are preferred.

A tag attached to cached responses (product-1234) allowing purge by tag rather than by URL. What makes CDN-caching dynamic HTML practical, since one product update can invalidate every page showing it.

Deciding whether to keep a trace after the whole trace is available, so slow and failed traces can be retained preferentially. More useful than head-based sampling and more expensive, because every trace must be buffered until it completes.

Many clients simultaneously performing the same expensive operation — a cache stampede, a herd of lock waiters woken at once, or every CDN PoP fetching an object together. The general fix is to collapse the work (single-flight) or decorrelate the timing (jitter).

A marker recording that a key was deleted, written because LSM files are immutable. Only truly removed once compaction has carried it through every level, which is why heavy deletes can make reads slower.

Spanner's clock API, which returns a bounded uncertainty interval rather than a single timestamp. Commit-wait deliberately pauses for that interval before making a write visible, buying global ordering with latency and specialised hardware.

Two parties over a lossy channel can never be certain they agree, because the final message's delivery is always unconfirmed. The reason exactly-once delivery is impossible and timeouts can only ever be guesses.

A coordinator asks all participants to prepare, then to commit. Provides atomicity across nodes, and is a blocking protocol — a coordinator crash after prepare leaves participants holding locks with no way to resolve.

The fraction of capacity in use. Mean latency scales roughly as 1/(1-ρ), so 90% utilisation means about ten times the service time — which is why capacity plans target 60–70% at peak.

One counter per node, merged element-wise on receive. Unlike a Lamport timestamp it detects concurrency: if neither vector dominates the other, the events are causally independent and you have a genuine conflict.

Giving each physical server many positions on the consistent-hashing ring. Evens out the otherwise poor balance of random placement, makes capacity weighting trivial, and spreads a failed node's load across all survivors rather than one neighbour.

An assertion that no more events earlier than time T are expected, which is what lets an unbounded stream emit finite results. It is a heuristic, not a fact: aggressive watermarks cut latency and drop more late data, conservative ones hold state longer.

Bytes written to disk divided by bytes written by the application. A B-tree may write a full 8 KB page plus a WAL record for a 100-byte update; LSM write amplification is comparable in volume but sequential and off the request path.

Two transactions read an overlapping set of rows, each decides based on what it read, and each writes to a different row — so nothing conflicts, yet the combined result breaks an invariant. Permitted by snapshot isolation; prevented only by serializable.

An append-only log of intended changes, fsynced before the data structure itself is modified, so a crash can be recovered by replay. The reason writes are durable and part of why they are written more than once.

Deliberately spreading one logically hot key across several physical keys by appending a suffix, then fanning out reads. The standard remedy for a hot partition, and it trades read complexity for write distribution.

A heavily skewed access pattern where a small fraction of keys serves most requests. The reason caches work at all, and the reason hit rate is roughly logarithmic in cache size.