Glossary

Definitions describe the meaning used in this course. Product documentation can use a term more narrowly; the relevant lesson identifies that scope. A guarantee belongs to an operation, configuration, and failure model rather than to a product name alone.

Workloads, resources, and measurement

Access pattern. The keys, ranges, relationships, and order in which an operation reads or changes data. Two requests with identical SQL structure can have different costs because parameter values select different amounts of data. See Lessons 1, 16, and 37.

Admission control. Deciding whether work may enter a bounded execution system. Rejection before execution is different from a timeout after a possible commit. Admission protects useful progress and retained resources during overload. See Lesson 34.

Amdahl’s Law. A model bounding speedup when only part of a fixed computation can be accelerated. Its idealized assumptions exclude additional parallelization overhead. It is a reasoning tool, not a promise that adding a certain number of cores yields a particular result. See Lesson 6.

Backpressure. A signal or control that stops a producer from indefinitely outrunning a consumer. It must reach the correct ownership boundary; blocking one subscriber should not accidentally block every transaction. See Lessons 17 and 33.

Bandwidth. A rate of data movement, usually bytes or bits per second. It differs from propagation latency and from operations per second. A high-bandwidth distant path can still be slow for several dependent exchanges. See Lesson 4.

Bandwidth-delay product. A path rate multiplied by round-trip time, giving an estimate of bytes in flight needed to fill the path under the stated model. It does not predict an application’s full throughput by itself. See Lesson 4.

Capacity. Sustainable work under a stated workload and contract. Capacity is constrained by CPU, memory, I/O, network, synchronization, and maintenance, often unevenly across partitions. See Lesson 35.

Closed-loop load. A generator whose next request depends on earlier completion or a fixed outstanding-work limit. Useful for concurrency experiments, but it changes offered rate when the service slows. See Lessons 6 and 42.

Coordinated omission. Missing relevant waiting observations because the load generator or measurement process stops scheduling work during service stalls. The remedy depends on the intended arrival model. See Lesson 6.

CPU demand. Execution time consumed on a CPU resource, often expressed as CPU-seconds per operation or per second. It is not the same as end-to-end elapsed time. See Lessons 2 and 35.

Critical path. The dependency chain that determines completion time. Work outside the chain can consume resources without directly extending that operation’s current elapsed time. See Lessons 1 and 31.

Headroom. Capacity reserved for variation, bursts, maintenance, transition work, or failures. A system can need headroom even when average demand is below its theoretical maximum. See Lessons 34–36.

Hot key. A key receiving disproportionately high traffic or conflict. Hashing many keys across machines does not automatically divide one key’s exclusive state transition. See Lessons 1 and 29.

Jitter. Variation in delay. In games and streaming systems, uneven updates can harm presentation even when average delay is acceptable. See Lessons 4, 33, and 47.

Latency. Elapsed time between specified events. Always identify the measurement boundary and completion guarantee. Engine execution latency, durable-commit latency, and player-visible latency are different measurements. See Lessons 1 and 6.

Little’s Law. The stable-system relation L = λW between average in-flight work, rate, and mean residence time within one consistent boundary. It does not say that additional concurrency creates additional capacity. See Lessons 3 and 6.

Load shedding. Explicitly rejecting or reducing work to preserve service under excess demand. A definitive pre-execution rejection and an uncertain post-execution timeout need different client behavior. See Lesson 34.

Open-loop load. A generator scheduling arrivals independently of response completion. The generator must record scheduling lag and have enough capacity to produce the intended workload. See Lesson 6.

Percentile. A position in an observed distribution. A p99 is not a maximum, and averaging machine-level p99 values does not generally produce a correct global p99. See Lessons 6 and 42.

Service demand. The amount of a particular resource needed by an operation. A resource vector makes CPU, I/O, memory, and network requirements explicit instead of collapsing them into one throughput number. See Lesson 35.

Skew. Uneven distribution of values, requests, or work. Data skew and request skew can differ, and a small range can be hotter than a much larger range. See Lessons 1, 16, and 29.

SLO. Service-level objective: a target for a defined service indicator over a defined window. Request-based and time-based objectives use different denominators. See Lesson 42.

Tail latency. The slower end of a response-time distribution. Queueing, pauses, misses, and fan-out can make tail behavior different from typical behavior. See Lessons 6 and 34.

Throughput. Completed work per unit time. State whether the count represents attempts, successful commits, business outcomes, or delivered messages. See Lessons 1 and 6.

Representation, access, and query execution

B+ tree. An ordered multiway search structure whose internal nodes route searches and whose leaves hold entries. Range scans can traverse leaf order. Split, visibility, and reclamation protocols are essential parts of a concurrent durable implementation. See Lesson 10.

Bloom filter. A probabilistic membership structure intended to reject absent candidates without false negatives under its construction assumptions. False positives spend extra lookup work; the filter does not prove that a returned value is transactionally visible. See Lesson 11.

Buffer frame. A reusable memory region holding a database page. A frame identity differs from the persistent page identity currently mapped into it. See Lesson 9.

Buffer pool. Engine-managed memory for pages or blocks. It includes mapping, pinning, loading, replacement, and writeback responsibilities, not merely an eviction list. See Lesson 9.

Cardinality. Number of rows in a relation or intermediate result. Estimate errors can alter join choice, memory fit, and distributed data movement. See Lesson 16.

Catalog. Database metadata describing objects such as schemas, types, constraints, functions, indexes, and statistics. Planning needs a coherent interpretation of catalog state during evolution. See Lessons 13 and 41.

Columnar layout. A representation grouping values by attribute across records. It can reduce scan bytes and enable compression while changing update and reconstruction costs. See Lessons 8, 12, and 47.

Compaction. Rewriting or merging stored representations to improve access, reclaim obsolete state, or maintain layout. In an LSM engine, it must preserve snapshots and safe deletion rules. See Lesson 11.

Compaction debt. Maintenance required to reach the intended storage organization that has not yet been completed. Debt growth can make a short-lived ingestion rate unsustainable. See Lessons 11 and 35.

Covering index. An index carrying enough values for selected queries to avoid some base-record fetches, subject to visibility and engine rules. Additional payload increases maintenance and storage. See Lesson 10.

Denormalization. Intentional redundant representation of facts for selected access paths. It needs explicit authority, freshness, and maintenance rules. Historical snapshots are also intentional copies but may preserve a different fact. See Lesson 7.

Dirty page. A memory page whose changes are not yet represented in the corresponding persistent data-file state. Its writeback must obey recovery ordering. See Lessons 9 and 19.

External algorithm. An algorithm designed to operate when state exceeds available memory, using storage for runs, partitions, or other intermediates. It needs bounded resources and failure cleanup. See Lesson 15.

Fanout. Depending on context, the number of tree children, downstream subrequests, or recipients of a change. The lesson states which meaning is intended. See Lessons 10, 31, and 33.

Fragmentation. Space inefficiency caused by unused allocation portions or scattered free regions. Total free bytes may not be usable as one contiguous record allocation. See Lesson 8.

Heap. A primary record organization without global key order in placement. This storage meaning differs from a programming-language heap or a priority-queue data structure. See Lesson 8.

Index. A maintained access representation supporting selected predicates or orderings. Its benefit must be weighed against memory, write work, visibility handling, and recovery. See Lessons 10–12.

Inverted index. A mapping from terms to matching documents, often with positions or frequencies. Query meaning depends on tokenization, ranking, and visibility. See Lesson 12.

Late materialization. Delaying reconstruction or copying of complete rows until required, often while processing selected columns and position vectors. See Lessons 12 and 17.

Logical plan. A representation of query meaning through operations such as selection, join, and aggregation before selecting concrete algorithms. See Lessons 13 and 14.

LSM. Log-structured merge organization, typically combining memory structures and immutable sorted runs with later compaction. It shifts work between foreground mutation, reads, and background maintenance. See Lesson 11.

Materialized view. A stored query result or maintained representation supporting it. Its refresh and maintenance contract determine freshness and write cost. See Lesson 32.

Memtable. An in-memory mutation structure in an LSM-oriented engine. A full instance may become immutable and be flushed while new writes enter another instance. See Lesson 11.

Normalization. Organizing facts according to dependencies to avoid unnecessary duplicated maintenance and anomalies. It does not require splitting every field into a separate table. See Lesson 7.

Page. An engine-defined storage unit containing records, index nodes, or metadata. It differs from an operating-system virtual-memory page. See Lessons 2 and 8.

Physical plan. Concrete operators and properties chosen to execute a query: access paths, join algorithms, order, partitioning, and exchanges. See Lessons 15–17.

Pin. A claim preventing a buffer frame from being reused while a caller depends on it. Pinning alone does not provide safe concurrent mutation or logical transaction isolation. See Lesson 9.

Projection. Selecting attributes from rows. Pushing it earlier can reduce intermediate width, provided required keys and semantic information remain available. See Lesson 14.

Read amplification. Extra accesses or bytes needed to answer logical reads, measured at a stated boundary. Cache and filter behavior can change it. See Lesson 11.

Recall. In approximate retrieval, the fraction of reference matches recovered under a defined query and ground truth. It must be evaluated alongside latency, memory, filtering, and update cost. See Lesson 12.

Residual predicate. A condition checked after an access path produces candidates. An index can narrow the search without proving the entire predicate. See Lessons 10 and 12.

Selectivity. The fraction of input rows matching a predicate. Combining individual selectivities requires assumptions about joint distribution. See Lesson 16.

Slotted page. A page containing stable slot entries that point to record locations, allowing some physical movement without changing the slot reference. Slot reuse still needs lifetime rules. See Lesson 8.

Space amplification. Physical retained space relative to a defined logical live-data baseline. State whether versions, replicas, logs, and temporary storage are included. See Lesson 11.

SSTable. An immutable sorted-table file used in LSM-oriented designs. File creation and authoritative metadata publication are separate steps. See Lesson 11.

Tombstone. A marker representing deletion so older surviving versions do not reappear. Safe removal depends on snapshots and, in distributed systems, replication and repair assumptions. See Lessons 11 and 44.

Vectorized execution. Processing batches of values to amortize dispatch and exploit compact data. It differs from hardware SIMD, although the techniques can cooperate. See Lesson 17.

Write amplification. Physical writes divided by logical mutation bytes or operations under an explicit boundary. Host, replica, and device-internal amplification are different quantities. See Lessons 11 and 44.

Transactions, memory concurrency, and recovery

ACID. Atomicity, consistency, isolation, and durability. Each property needs a scope and implementation contract; the acronym does not establish every business invariant or distributed observation rule. See Lesson 7 and Part IV.

Atomicity. A logical operation’s related changes are accepted together or do not remain as a partial accepted result. Physical pages can still be written at different times under a recovery protocol. See Lesson 19.

Checkpoint. Recoverable metadata or state used to organize and limit recovery. A fuzzy checkpoint is not necessarily a fully flushed database image at one instant. See Lesson 24.

Critical section. Work performed while holding exclusive protection over a shared resource. Its duration controls contention; remote waiting inside it can be especially expensive. See Lessons 3 and 20.

Deadlock. A cycle of waits preventing participants from progressing under the modeled resources. Detection, prevention, and timeout policies have different costs and failure behavior. See Lesson 20.

Durability. Survival of an accepted result under specified failures. In-memory commit, local disk durability, replicated durability, and recoverable backups cover different boundaries. See Lessons 9, 24, and 39.

Epoch. A generation used to distinguish authority or safe memory lifetimes, depending on context. A leadership epoch and a reclamation epoch are different applications of the generation idea. See Lessons 23 and 25.

False sharing. Independent mutable objects occupying one coherence unit, causing traffic between cores despite logical independence. Padding can reduce it but cannot eliminate true contention over one invariant. See Lesson 23.

Group commit. Sharing a durability operation across several commits. It amortizes work but can add batch waiting; amortized flush cost is not per-request response latency. See Lessons 19 and 24.

Hazard pointer. A reader-published claim used in some concurrent reclamation schemes to prevent freeing an object still subject to valid dereference. It requires careful publication and validation. See Lesson 23.

Isolation. Restrictions on how transactions observe and interact with concurrent activity. The exact isolation level determines permitted histories and anomalies. See Lessons 20–22 and 26.

Latch. Short-lived physical synchronization protecting engine structures. Its lifetime and purpose differ from a transaction lock retained for logical isolation. See Lesson 23.

Lock-free. A progress property for a concurrent algorithm under its model, not a claim of no contention, no allocation cost, or universally better latency. See Lesson 23.

MVCC. Multiversion concurrency control: retaining versions and selecting visibility under snapshots or transaction rules. MVCC alone does not name one isolation level. See Lesson 21.

OCC. Optimistic concurrency control: executing tentative work and validating that its observations remain acceptable before publication. Validation and atomic publication must themselves be coordinated. See Lesson 22.

Predicate protection. Preventing or detecting conflicts involving a logical set, including rows not yet present. Protecting only returned records can miss phantoms. See Lesson 20.

Redo. Reconstructing changes required by the recovery protocol that are not yet reflected in persistent data pages. It is not replaying a business request as a new action. See Lesson 24.

Snapshot isolation. A transaction model with a consistent snapshot and a defined write-conflict rule, which can still permit write skew. It is not a synonym for serializability. See Lesson 21.

Steal/no-force. Buffer-policy terms: steal permits some uncommitted dirty data to reach persistent pages; no-force permits commit without flushing every changed data page. Recovery requirements depend on the full engine model. See Lesson 19.

Two-phase locking. A locking discipline separating acquisition and release phases. Strict variants retain write protection until transaction completion. It differs entirely from two-phase commit. See Lesson 20.

Undo. Reversing or eliminating the effects of incomplete work under the engine’s recovery and visibility design. Physical byte reversal is not the only possible implementation. See Lessons 19 and 24.

WAL. Write-ahead logging: recovery information must be durable before dependent data-page persistence under the protocol. A durable log can allow later page writeback. See Lessons 19 and 24.

Watermark. A position through which a specific kind of progress is known: appended, durable, committed, applied, or delivered. Different watermarks must not be conflated. See Lessons 19, 27, and 33.

Write skew. An anomaly in which transactions read a shared condition and make nonconflicting writes whose combined result violates it. The on-call-doctor history demonstrates the dependency cycle. See Lesson 21.

Distribution, delivery, and operations

CAP. A formal result concerning atomic, or linearizable, read/write storage and availability during network partitions under the original Gilbert–Lynch model. Its availability requirement concerns responses by nonfailed nodes; it is not an ordinary uptime percentage. The C property is not interchangeable with transaction serializability that omits real-time order. See Lesson 26.

Causal consistency. A guarantee preserving causally related observations while permitting different orders for independent concurrent operations. Scope and dependency tracking matter. See Lesson 26.

CDC. Change-data capture: exposing committed changes for downstream processing. Snapshot alignment, offsets, duplicate handling, and retention remain part of the consumer design. See Lesson 32.

Consensus. Agreement on decisions among participants under a failure model. It can support replicated logs; it does not independently define every multi-partition transaction guarantee. See Lessons 28 and 30.

CQRS. Separating command-side decisions from query-side representations. It can improve read specialization while introducing propagation, replay, and evolution responsibilities. See Lesson 32.

Eventual consistency. A convergence contract under stated communication and update assumptions. It does not by itself bound staleness or preserve an arbitrary cross-record invariant. See Lesson 26.

Fencing. Rejecting obsolete authority at the resource it could damage, commonly using a generation token. A new leader’s local belief is insufficient if old writers can still reach the resource. See Lesson 25.

Idempotency. Repeating a logical operation has no additional intended effect under its contract. Practical implementations often need durable operation identity, payload checks, and retention. See Lessons 5 and 37.

Linearizability. Operations on a specified object appear to take effect between invocation and response while respecting real-time order of nonoverlapping operations. Per-key linearizability does not automatically create multi-key atomic transactions. See Lesson 26.

Outbox. A durable publication obligation recorded atomically with business state, then delivered asynchronously. Consumers still need safe replay and external-side-effect handling. See Lesson 37.

PACELC. A reasoning framework highlighting partition-time availability/consistency choices and normal-operation latency/consistency tradeoffs. Different operations can make different choices. See Lesson 26.

Partition. Either a division of data ownership or a communication failure separating participants. The course explicitly distinguishes data partitions from network partitions. See Lessons 25 and 29.

Quorum. A set of participants sufficient for a protocol decision. Set intersection alone is not a complete consistency proof without version, durability, and reconfiguration rules. See Lessons 27 and 28.

RPO. Recovery point objective: tolerated data loss under a stated failure. It must agree with acknowledgment, replication, and recoverable history. See Lesson 39.

RTO. Recovery time objective: permitted time to restore the specified useful service boundary. Provisioning, restore, replay, validation, routing, and warming may all contribute. See Lesson 39.

Saga. A workflow of locally committed steps with compensating actions. Compensation is a new business action and does not generally erase all observations or external effects. See Lesson 30.

Serializability. A transaction-history guarantee equivalent to some valid sequential transaction execution. It does not alone impose every real-time order. See Lessons 8, 21, and 26.

Shard. A data-ownership or execution partition. Its identity can remain stable while physical placement changes. Cross-shard work needs an explicit coordination and routing model. See Lesson 29.

Strict serializability. Serializable transactions with real-time ordering for relevant nonoverlapping transactions. It is stronger than merely giving each transaction a stable snapshot. See Lesson 26.

Two-phase commit. An atomic-commit protocol involving preparation and a durable final decision. It differs from two-phase locking and from consensus, although a distributed database can combine them. See Lesson 30.

Uncertain outcome. The caller cannot determine whether an operation committed. A timeout after possible execution is not proof of abort. Safe resolution uses identity, status, or another explicit protocol. See Lessons 5 and 25.

Course index · Notation guide