Glossary

A unified glossary of terms used across all labs. Terms are grouped by domain.

Storage & I/O

Term	Definition
Page	The unit of I/O between disk and memory. Usually 4 KiB (matches OS page size) but databases often use 4–32 KiB.
Block	An SSTable's I/O unit (LevelDB default 4 KiB). Distinct from a B-tree "page" — both are I/O units but for different engines.
mmap	Map a file into process address space. Reads happen via page faults; writes via dirty pages flushed by the kernel.
pread/pwrite	Positional read/write syscalls. Explicit offset, no shared file pointer. Predictable cost, no page-fault stalls.
`O_DIRECT`	Open flag (Linux) that bypasses the page cache. Requires aligned buffers, aligned offsets, aligned sizes.
`fsync`	Force file data + metadata to stable storage. Blocks until disk acknowledges. Often the slowest syscall in a database.
`fdatasync`	Like `fsync` but skips non-essential metadata. Faster on most filesystems.
Write amplification (WA)	Bytes physically written / bytes logically written. SSDs have hardware WA; LSM-trees have algorithmic WA from compaction.
Read amplification (RA)	Bytes physically read / bytes logically read. LSM-trees suffer from RA due to checking multiple levels.
Space amplification	Bytes on disk / bytes of live data. LSMs have space amp from stale data awaiting compaction.
Endianness	Byte order. Little-endian (x86, ARM default): least-significant byte first. Big-endian: network byte order.
Alignment	Memory address being a multiple of N. Required for `O_DIRECT` (usually 512 B or 4 KiB) and SIMD ops.
`io_uring`	Linux async I/O API (≥ 5.1). Two ring buffers (SQ/CQ) shared between kernel and user space.
DMA	Direct Memory Access — disk controller writes directly to RAM without CPU involvement.

Hardware

Term	Definition
HDD seek time	~5–10 ms for random reads (head movement + rotational latency). ~150 MB/s sequential.
SATA SSD	~100 μs random read latency, ~500 MB/s sequential, ~80K IOPS.
NVMe SSD	~50–100 μs random read latency, ~3–7 GB/s sequential, ~500K–1M IOPS. Multiple hardware queues.
Cache line	CPU cache unit, almost always 64 bytes. Data-structure layout for cache locality matters.
NUMA	Non-Uniform Memory Access — CPU sockets have local RAM; cross-socket access is slower.
Wear leveling	SSD firmware spreads writes across blocks to even out flash wear. Causes hardware write amplification.

Data Structures

Term	Definition
Skip list	Probabilistic balanced structure with O(log n) ops and lock-free-friendly properties. Used in LevelDB MemTable.
B-Tree	Self-balancing m-ary tree. Internal nodes store keys + values + child pointers. Used for indexes.
B+-Tree	B-Tree variant where all values live in leaf nodes; internal nodes are pure routing. Used for tables in SQLite.
LSM-Tree	Log-Structured Merge-Tree. In-memory MemTable + on-disk sorted runs (SSTables), merged via compaction.
Bloom filter	Probabilistic set membership; no false negatives, tunable false positive rate. Used to skip SSTable lookups.
ART	Adaptive Radix Tree — modern in-memory index alternative to B-Trees, used by HyPer, DuckDB.

Consensus

Term	Definition
Quorum	Subset of nodes whose agreement is required. Typically ⌊N/2⌋ + 1 for majority quorum.
Term / Epoch	Monotonically increasing identifier for a leadership period (Raft term, ZAB epoch, Paxos ballot).
Log index	Position of an entry in the replicated log. Indices are monotonic and dense.
Commit index	The largest log index known to be safely replicated to a quorum.
Linearizability	Strongest consistency: operations appear to take effect atomically at some point between their invocation and response.
Sequential consistency	All processes agree on a single global order, but the order need not match real-time.
Eventual consistency	If updates stop, all replicas eventually agree. No real-time guarantees.
CAP theorem	Under a network partition, you must choose Consistency or Availability. Partition tolerance is non-negotiable.
FLP impossibility	No deterministic asynchronous consensus protocol can guarantee progress with even one crash failure.
Lamport timestamp	Scalar logical clock: `L(a) < L(b)` if `a` happened-before `b`. Cannot detect concurrency.
Vector clock	Per-node vector. `VC(a) < VC(b)` iff every component is ≤. Detects concurrent events.
HLC	Hybrid Logical Clock: combines physical time with a logical counter; bounded skew from real time.

Transactions

Term	Definition
ACID	Atomicity, Consistency, Isolation, Durability — properties a transaction must satisfy.
Isolation level	READ UNCOMMITTED → READ COMMITTED → REPEATABLE READ → SERIALIZABLE. Each rules out more anomalies.
Dirty read	Reading data written by an uncommitted transaction.
Non-repeatable read	Reading the same row twice in one tx and getting different values.
Phantom read	A range query returns different rows when re-run within one tx.
MVCC	Multi-Version Concurrency Control — writes create new versions; readers see a snapshot.
2PL	Two-Phase Locking — acquire locks in a growing phase, release in a shrinking phase. Guarantees serializability.
2PC	Two-Phase Commit — distributed transaction protocol: prepare phase, then commit/abort. Blocking on coordinator failure.

SQL Engine

Term	Definition
VDBE	Virtual Database Engine — SQLite's bytecode VM that executes compiled SQL.
Prepared statement	A parsed and compiled SQL statement, reusable with different parameters.
Cardinality estimation	Predicting how many rows a query operator will produce. Core to the query planner.
Selectivity	Fraction of rows that satisfy a predicate. Low selectivity ⇒ index scan preferred.
Covering index	An index that contains all columns needed by a query, so the table doesn't need to be touched.

Operational

Term	Definition
Snapshot	A consistent point-in-time view of data. Used for backups, MVCC reads, Raft log compaction.
Checkpoint	Operation that flushes in-memory state to disk so recovery has less log to replay.
Compaction	Background process that merges sorted files (LSM) or reclaims fragmented space (B-tree).
YCSB	Yahoo Cloud Serving Benchmark — standard KV workload suite (A–F). Used in `db-22`.
Jepsen	Test framework for distributed systems correctness; injects partitions/clock skew. Inspires our consensus tests.

Cloud Gateway & Application Networking (Phase 6)

Term	Definition
L4 / L7	Transport (TCP/UDP, opaque bytes) vs application (HTTP/gRPC/WebSocket, per-request) proxying.
Data plane	The proxies on the request path; optimized for p99 latency and throughput.
Control plane	The source of truth that computes + pushes config to the data plane; off the request path.
Event loop	A thread multiplexing many connections via `epoll`/`kqueue`; must never block (Zuul 2 / Netty).
C10K	The problem of serving 10k+ concurrent connections; solved by event loops, not threads.
Backpressure	Slowing a producer when the consumer can't keep up; for a proxy, stop reading one side when the other can't be written.
PROXY protocol	A header prepended to an L4 stream to convey the original client/destination addresses.
Nagle's algorithm	Coalesces small TCP writes; disabled with `TCP_NODELAY` for latency-sensitive traffic.
conntrack	The kernel connection-tracking table; a finite resource a busy gateway can exhaust.
HTTP/2 stream	One independent request/response multiplexed over a single TCP connection.
HPACK / QPACK	Header compression for HTTP/2 / HTTP/3 (QPACK is HOL-blocking-safe).
Flow control (h2)	Per-stream/connection credit windows; application-level backpressure via `WINDOW_UPDATE`.
GOAWAY	HTTP/2 frame to stop opening new streams; the graceful-drain signal.
Head-of-line blocking	A stalled item blocking those behind it: at L4 (TCP), h1 (pipelining), h2 (TCP under mux); fixed at h3.
QUIC / HTTP/3	Reliable multiplexed streams over UDP; no TCP HOL, 0-RTT, connection migration.
Filter chain	Zuul's inbound → endpoint → outbound phases; the programmable request lifecycle.
Connection churn	The rate of opening/closing connections to backends; the thing to minimize.
Connection pool / keep-alive	Reusing warm connections to avoid per-request TCP+TLS handshakes.
Subsetting	Each gateway connects to a subset of origins so total conns = `gateways × subset`, not `× origins`.
Van der Corput sequence	Binary low-discrepancy sequence (bit-reverse `i`); evenly-spread, stable subset selection.
WebSocket (RFC 6455)	HTTP-upgraded, full-duplex, framed channel; server can push at any time.
Push registry	`deviceId → owning node` map for routing a message to a connection (Pushy / KeyValue).
Reconnect storm	Many clients reconnecting at once; tamed with exponential backoff + full jitter.
P2C	Power of Two Choices: pick 2 random endpoints, send to the less-loaded; near-optimal, no coordination.
Outlier ejection	Removing a bad endpoint from rotation based on live error/latency.
Retry budget	Cap on retries as a fraction of total traffic; the anti-amplification rule.
Circuit breaker	CLOSED/OPEN/HALF-OPEN state machine that fails fast on a sick dependency.
Adaptive concurrency	Inferring the right in-flight limit from latency (Little's Law); shed at admission past the knee.
Metastable failure	A self-sustaining overload that persists after the trigger clears (e.g. a retry storm).
mTLS	Mutual TLS — both peers present certificates; cryptographic two-way authentication.
SPIFFE / SVID	A workload-identity URI / the short-lived X.509 cert carrying it (issued by SPIRE / Netflix Metatron).
SNI / ALPN	TLS extensions selecting the server cert by hostname / negotiating the protocol (h2/h3).
Zero-trust	Never trust the network; authenticate every connection, authorize every request.
Envoy	The canonical C++ L4/L7 data plane: listeners → filter chains → clusters → endpoints.
xDS	Envoy's discovery protocol (LDS/RDS/CDS/EDS/SDS) for dynamic config from a control plane.
ADS / Delta xDS	Aggregated (single ordered stream) / incremental variants of xDS.
ACK / NACK (xDS)	Envoy confirming or rejecting an applied config version; the rollout/correctness signal.
CNI	Container Network Interface — the spec + plugins that wire pod networking (veth, IPAM, overlay).
kube-proxy	Programs nodes to map ServiceIP → pod IP (iptables / IPVS / eBPF).
EndpointSlice	Sharded list of ready pod IPs behind a Service; the membership source for LB/EDS.
Readiness probe	Health check gating Service membership; the hook that makes graceful drain work.
CRD / Operator	A custom Kubernetes type / a controller that reconciles it to desired state.
Reconcile loop	Level-triggered, idempotent convergence of actual → desired state (self-healing).
Gateway API	Standard role-oriented K8s CRDs for L7 routing (GatewayClass/Gateway/HTTPRoute); successor to Ingress.
Finalizer	A marker blocking deletion until a controller cleans up external state.
RED / USE	Rate-Errors-Duration (request services) / Utilization-Saturation-Errors (resources).
Golden signals	Latency, traffic, errors, saturation — the four to dashboard and alert on.
SLI / SLO / error budget	Indicator / target / allowed failure that governs release velocity.
Trace context	Propagated identifiers (W3C `traceparent`, `b3`) that stitch spans into one trace across a proxy.
Shadow / mirror traffic	Copying prod traffic to a new path without serving its responses; zero-risk validation.
Canary / sticky canary	A small (consistent-cohort) slice of real traffic on the new path, compared to a control group.
NRI / OCI hooks	Container-runtime extension points to customize per-workload networking/storage (Netflix Titus→K8s).

Platform & Distributed Systems Architecture (Phase 7)

Term	Definition
Bounded context	A cohesive business capability with its own model + boundary (DDD); the basis for a service boundary.
Service contract	The explicit, versioned interface (API + events + guarantees) a service exposes.
Distributed monolith	Services that must deploy together / share a DB / call synchronously per request — a monolith with added latency.
Cohesion / coupling	How related a service's responsibilities are / how dependent services are on each other.
Fan-in / fan-out	Number of services depending on X / number X depends on.
Blast radius	The set of services affected if a given service fails (transitive dependents).
Strangler fig	Incrementally replacing a system by routing slices to the new one.
Conway's Law	System structure mirrors org communication structure.
Backward / forward compatibility	New code reads old data / old code reads new data.
Tag number (protobuf)	A field's stable id; the basis of safe schema evolution (never reuse/retype).
Idempotency key	Client-supplied key letting a server dedupe retries of a non-idempotent op.
Opaque cursor	A tamper-evident pagination token that hides the storage scheme from the contract.
Event	An immutable fact that something happened ("OrderPlaced").
At-least-once / exactly-once	Delivery that may duplicate (the practical default) / a myth; use at-least-once + idempotency.
Dead-letter queue (DLQ)	Where un-processable messages go after exhausting retries.
Choreography / orchestration	Services reacting to events / a central coordinator (a saga).
Commit log	Append-only, ordered sequence of records addressed by offset (the streaming substrate).
Partition	One shard of a topic; the unit of ordering and parallelism.
Offset	A record's monotonic, stable position within its partition.
Consumer group	Consumers sharing a topic's partitions (≤1 consumer per partition).
Rebalancing	Reassigning partitions to consumers on membership change (minimize movement).
Dual-write problem	Updating a DB and publishing an event non-atomically; a crash desyncs them.
Transactional outbox	Writing the event into the DB in the same transaction as the state change; a relay publishes it.
Change-data-capture (CDC)	Publishing events by tailing the DB's write-ahead log (the outbox alternative).
Saga	A sequence of local transactions with per-step compensating actions (vs distributed 2PC).
Compensation	A semantic undo of a completed saga step (refund, recall — not rollback).
Consistent hashing	Hash-ring key placement; a membership change moves ~1/N keys (vs mod-N's reshuffle).
Virtual nodes	Multiple ring positions per physical node; even load + smooth movement.
Quorum (N/W/R)	Replica count / write-acks / read-replicas.
R+W>N	The read/write-quorum overlap condition for strong (read-your-writes) consistency.
Linearizable / causal / eventual	Strongest → weakest consistency models.
CAP / PACELC	Consistency vs availability (under partition) / vs latency (else).
Infrastructure as Code (IaC)	Declarative infra + a diff-and-converge engine (Terraform/Pulumi).
Plan / apply / state / drift	The diff / converge / last-applied snapshot / world-diverged-from-state.
GitOps	Git as the single source of truth + a reconciler that continuously converges live state.
Sync / prune / self-heal	Apply git changes / delete what git dropped / revert manual drift.
Reconcile loop	Level-triggered, idempotent convergence to desired state (IaC/GitOps/operators/xDS).
SLI / SLO / error budget	Indicator / target / allowed-failure currency that governs release velocity.
Burn rate	errorRate / errorBudget; >1 = consuming the budget too fast.
Multi-window burn-rate alerting	Page only when long (sustained) AND short (ongoing) windows both burn fast.
Bulkhead	Per-dependency concurrency isolation so one saturated dependency can't starve others.
Cascading failure	One failure exhausting shared resources, toppling others.
Graceful degradation	Reduced-but-available service under stress.
ADR	Architecture Decision Record: context, decision, alternatives, consequences.
Fitness function	An automated test of an architectural property (cycles, layering, coupling) in CI.
Evolutionary architecture	Architecture as a continuously-tested, changeable property.
Paved road / golden path	The supported, easy default that makes the right thing the easy thing.

Distributed Systems Engineer — Build Databases & Consensus From Scratch