Holds for any arrival pattern and service distribution in a stable system. Forwards it turns a throughput target into a concurrency requirement (2 000 QPS at 50 ms needs 100 in-flight slots); backwards it distinguishes 'requests are queueing' from 'concurrency is capped', which look identical on a latency graph.

The variable that governs queueing. M/M/1 time in system is W = E[S]/(1−ρ), so latency rises hyperbolically rather than linearly — the same 5% of extra traffic costs 3 ms at 50% utilisation and 100 ms at 90%. Provision against utilisation, never against throughput.

Requests do not arrive evenly spaced, so they cluster and queue even when a server is idle on average. This is why latency degrades long before 100% utilisation and why systems fail suddenly rather than gradually.

Latency has a floor and no ceiling, so the mean is dragged by a few slow requests and describes an experience nobody had. The tail disproportionately affects the heaviest users, since more data means slower requests.

p99 = 250 ms means 99% of requests finished within 250 ms. Percentiles do not average across servers and do not add along a call chain — both are common monitoring errors. A usable p_q needs roughly 10/(1−q) samples.

Sent only when the first attempt exceeds, say, the p95, so extra load is ~5% while the tail collapses — the request is only still slow if the duplicate is slow too. A tied request sends both immediately and cancels the loser.

P(slow) = 1 − (1−p_slow)^n. With each of 100 backends slow just 1% of the time, the request is slow 63% of the time — so the required component percentile is set by the fan-out, not by taste.

G(N) = 1/((1−p_parallel) + p_parallel/N), with a ceiling of 1/(1−p_parallel). At 95% parallel, 100 machines give 17× and no number ever exceeds 20×. The serial fraction is usually a shared resource — one database, one lock, one coordinator.

C(N) = N / (1 + σ(N−1) + κN(N−1)). The κN² term makes the curve peak at N* = √((1−σ)/κ) and fall beyond it, which is why adding nodes to a struggling cluster can reduce throughput. The fix is less coordination, not more hardware.

Gives O(log n) expected search and insert like a balanced tree, but an insert splices a node into a few linked lists rather than rotating subtrees — which makes lock-free and fine-grained-locking implementations practical. That matters because the memtable is the hottest shared structure in an LSM engine.

The simplest workable storage engine: one hash lookup plus one seek per read. Bounded by distinct key count rather than data size (~68 bytes per key), and structurally incapable of range queries — which is what motivates sorting the data instead.

The query is answered from the index alone, removing one random read per result row. The trade is a wider index: more pages, fewer entries per page, and more write amplification — read amplification traded for write amplification at the query level.

The table's data lives inside the index, so rows with nearby keys sit on the same or adjacent pages. Rows can have only one physical order, so a table has at most one clustered index. Primary-key reads and ranges are cheap, but the key choice becomes a physical-layout decision. InnoDB tables are always clustered, normally on the primary key.

Leaf entries hold the indexed values plus a row locator: a physical row address on a heap, or the clustered key on a clustered table. Reaching the full row takes a second lookup unless the index covers the query. A table can have many. SQL Server uses the term for every secondary index.

A row is placed wherever there is free space, and every index on the table is secondary, pointing at the row's physical location. PostgreSQL tables are heaps; its CLUSTER command reorders a table once but does not maintain that order for later writes.

The organising constraint of storage engine design. Tiering optimises update cost and pays in read amplification; leveling optimises read and space and pays in write amplification; Bloom filters buy read performance with memory.

Extends CAP with the normal case CAP ignores. The E half dominates because partitions are rare while replication latency is charged on every request — ~150 ms against ~1 ms across continents. Real systems expose the choice per query rather than per system.

Read-your-writes, monotonic reads, monotonic writes and writes-follow-reads. Each rules out an anomaly users actually notice, and each is enforced by routing or a carried version token rather than by coordination — so latency and availability are preserved.

Nearly free, because the read already holds several versions and knows which replicas are behind. It only ever fixes keys that are read, so the cold majority of the keyspace stays stale — which is why background anti-entropy is required as well.

φ = −log₁₀ P(a heartbeat is later than the current gap), computed from the observed arrival distribution. Each consumer picks its own threshold according to what a mistake costs it, and the detector adapts to a slow network without a hand-tuned constant.

Those three properties make replicas converge regardless of the order, grouping or repetition of updates — exactly what an unreliable network does. A G-counter merges by elementwise max; an OR-set tags additions so a concurrent add survives a remove.

a → b if they are on the same node in that order, or a is a send and b its receipt, or transitively. Events with neither direction are concurrent — neither could have known of the other, which is the property conflict detection needs and a timestamp destroys.

The shape real access patterns take. With s = 1 over 10⁶ items the top item takes ~7% of all traffic and the top ten ~20%, so skew is the expected case rather than an anomaly — and any design assuming uniform access is assuming something that has never been true.

Writes are distributed across k partitions; reads must query all k and merge. It trades a write hotspot for read fan-out, so it is applied selectively to identified hot keys rather than globally.

Each version is tagged with the transactions that created and superseded it, and a snapshot plus one visibility predicate yields snapshot isolation. It is the append-only insight applied to concurrency — and it owes the same debt, needing vacuum to reclaim versions that no open transaction can see.

The pessimistic route to serializability. The discipline guarantees an acyclic precedence graph, since a cycle would require acquiring after releasing. Costs waiting, unpredictable latency and deadlocks that the application must retry.

Uses the result that every cycle under snapshot isolation contains two consecutive rw-dependencies, so the engine tracks a constant amount of state per transaction rather than building a global graph. Readers never block writers; the cost is an abort rate that rises with contention.

An edge T1 → T2 whenever T1 must precede T2. A schedule is serializable exactly when the graph is acyclic — a cycle means no serial order exists. Every concurrency mechanism either prevents or detects such a cycle.

Because a crashed node and an arbitrarily slow one are indistinguishable. Real systems escape by keeping safety unconditional and sacrificing guaranteed termination — an unavailable consensus system is an inconvenience, an inconsistent one has two leaders.

Two sets each larger than N/2 cannot be disjoint, so a new decision always consults a node from the previous one. Hence ⌊N/2⌋+1 and N = 2f+1 to tolerate f failures — and why even-sized clusters add cost without adding tolerance.

Decomposes into leader election, log replication and safety. Terms act as a logical clock and a fencing token; randomised election timeouts avoid split votes; and the election restriction plus quorum intersection guarantee a new leader holds every committed entry.

Increment on every event; on receive take the max then increment. a → b implies C(a) < C(b), but not the converse — a smaller counter may be an unrelated event. With a node-id tie-break it gives a total order every node computes identically.

Stays within a bounded distance of wall-clock time so it is human-meaningful, while still guaranteeing that causally ordered events compare correctly. Used by CockroachDB and MongoDB where causally sound timestamps must also look like times.

Keeps the uncertainty NTP discards. Disjoint intervals order definitively; overlapping ones are explicitly unknown. Spanner waits out the interval before releasing locks, buying strong consistency by measuring uncertainty and paying it as latency.

Completeness is unknowable on a stream, so a window must be closed on an assumption. Allowed lateness trades latency against accuracy — there is no correct value, only a stated one, and late data is then dropped, used to update the result, or sent to a side output.

Collapses many records into one per mapper per key before they cross the network — the highest-value optimisation in a distributed job. Requires the reduce function to be associative and commutative, the same algebraic condition a CRDT merge needs.

How an append-only event log satisfies a right to erasure: encrypt personal data per subject and delete the key, rendering the events unreadable without mutating the log. It must be designed in from the start, as retrofitting is close to impossible.

The product of its label domains, and the cost driver for a metrics system. Endpoint × status × region × instance is manageable; adding a user id multiplies it by the user count and takes the metrics system down. High-cardinality identifiers belong in traces and logs.

User-facing by construction, which is why they wear well. Alerting on causes such as CPU produces pages for conditions nobody experiences, and every alert that fires without needing action trains responders to ignore alerts.

Alerting on burn rate — how fast the budget is being consumed — rather than on instantaneous thresholds. A brief blip consuming 1% of a monthly budget needs no one awake; a slow degradation that will exhaust it in a day does, and a threshold alert catches the wrong one.

Improves maximum load from Θ(log n / log log n) to Θ(log log n) — an exponential gain from one extra sample — and needs no shared state, so parallel balancers cannot all converge on the same 'least loaded' server and stampede it.

Admits a new item only if a compact frequency sketch suggests it is more valuable than the entry it would displace. This defeats LRU's central weakness — a single batch scan evicting the entire hot set — since a once-seen item loses that comparison and never enters.

Queries per second — the standard unit for sizing a system, used instead of "users" because one user generates many operations. Always derive QPS from a write-volume input and a read:write ratio (see 1.7).

The time a single operation takes from start to finish. Decoupled from throughput via parallelism — see 1.2. A redirect's latency budget is "tens of milliseconds" because it sits in front of a page load.

The rate of operations a system completes, independent of any single operation's latency. Raised by adding parallel workers/servers/partitions.

Formalized by Eric Brewer (2000), proven by Gilbert & Lynch (2002). Consistency = linearizability (every read sees the latest write). Availability = every request to a live node gets a response. Partition tolerance is not optional — the real choice is C vs A, and only during an active partition.

The strongest common consistency model: the system behaves as though there's a single, up-to-date copy of the data and every operation appears to take effect instantaneously at some point between its start and end. This is what "Consistency" means in the CAP theorem. It's expensive to guarantee across a network, which is exactly why weaker models (eventual, read-your-writes, monotonic reads, causal) exist as cheaper compromises.

A consistency guarantee weaker than linearizability but stronger than plain eventual consistency: after a user writes a value, that same user's subsequent reads are guaranteed to reflect it, typically implemented by routing that user's reads to the primary (or the replica that served their write) for a short window.

A consistency guarantee ensuring that once a user has seen a value, they never see an older value on a later read — even if that later read happens to hit a more-lagged replica. Without it, refreshing a page could show a comment disappearing and reappearing.

A consistency guarantee that preserves cause-and-effect ordering (e.g. a reply is never seen before the comment it replies to) without requiring the full ordering guarantees of linearizability. Sits between eventual consistency and linearizability on the consistency spectrum.

A system that chooses Consistency over Availability during a network partition — it will refuse requests rather than risk serving stale or conflicting data. Examples: ZooKeeper, etcd, HBase, MongoDB in its default configuration.

A system that chooses Availability over Consistency during a network partition — it keeps accepting reads/writes even if replicas may disagree temporarily. Examples: Cassandra, DynamoDB, Riak, CouchDB.

The consistency model that AP systems provide: given no new writes, all replicas eventually agree. There's no bound on how long convergence takes. Stronger variants: read-your-writes, monotonic reads, causal consistency.

The precise definition (not "doing it again does nothing"). GET/PUT/DELETE are naturally idempotent; POST is not. Fixed for non-idempotent operations via an idempotency key + stored result. See the crash-in-the-gap problem for why no implementation is perfectly safe.

A unique key (often client-generated, e.g. a UUID) sent with a request so the server can recognize a retry and return the previously stored result instead of redoing the side effect. Popularized by the Stripe API for payments.

Adding more CPU/RAM to a single machine. Operationally simple — no distributed-systems problems — but hits a hard, increasingly expensive ceiling.

Adding more machines rather than upgrading one. No hard ceiling, but introduces every distributed-systems tax: coordination, partial failure, consistency.

States a capability the system provides ("a user can shorten a URL"). Declarative, not interrogative — a clarifying question ("do links expire?") is not itself a requirement.

Describes the qualities the system must have rather than what it does. Often drives the architecture more than functional requirements — two systems with identical features diverge entirely based on their non-functional targets.

Sends the 1st request to server A, 2nd to B, 3rd to C, then back to A — blind to how busy each server actually is. Simple and fair when requests are roughly equal cost; poor when request cost varies a lot, since a server can get piled up with expensive requests purely by bad luck of the rotation.

Tracks in-flight requests per server and routes each new request to whichever server currently has the fewest, which adapts naturally to uneven request costs — unlike round robin, a server bogged down with slow requests simply stops receiving new ones until it catches up.

Sits between clients and app servers, using an algorithm (round robin, least connections) to pick a target, and health checks to eject unhealthy servers. Examples: NGINX, HAProxy, Envoy, AWS ALB/NLB.

Operates at the transport layer, routing based on IP address and port without inspecting the payload. Faster than Layer 7 but can't route on path or header.

Operates at the application layer, parsing HTTP to route by path, header, or cookie. More flexible than Layer 4 but adds parsing overhead.

A load-balancing mode that routes a given user's requests to the same server every time, usually via a cookie. Fragile: breaks if that server dies, and creates uneven load across the fleet.

A server design where session state lives externally (e.g. in Redis) instead of in the server's own memory, so any server in the pool can handle any request — the fix for the sticky-session trap.

Trades storage cost and staleness risk for speed. Exists at multiple layers: browser, CDN, application (Redis/Memcached), and database buffer pool.

Also called lazy loading. The most common read pattern because it survives cache death — the cache sits outside the critical write path.

Keeps the cache always fresh at the cost of slower writes, since every write pays the latency of both stores.

Also called write-behind. Fast writes, but risks data loss if the process crashes before the deferred flush completes.

Also called thundering herd. Fixed with a repopulation lock, early refresh before expiry, or TTL jitter so keys don't all expire together.

The safety net for staleness — even if invalidation is missed on a write, the entry self-heals once its TTL elapses.

Every relational database keeps a region of RAM (Postgres's shared_buffers, MySQL's InnoDB buffer pool) holding recently accessed disk pages, so repeat reads of hot rows avoid disk I/O entirely. It's the reason RDS memory-optimized (R-family) instances are the default choice for databases: a bigger buffer pool means a bigger fraction of the working set never touches disk.

The empirical observation that access patterns are rarely uniform — roughly 20% of keys (the "hot set") tend to account for roughly 80% of requests. This is what makes caching a cheap, high-leverage win: a cache sized for only the hot set, not the whole dataset, still absorbs most traffic. It's why the URL shortener's ~1-2GB cache handles ~4,000 QPS against an 18TB dataset.

LRU (least recently used) evicts the entry untouched for longest — the default, works well since access is temporally clustered. LFU (least frequently used) evicts by access count — better when popularity is stable over time.

Solves availability and read throughput, not write throughput or storage (that's sharding). Dominant topology: leader-follower, where a single leader establishes write order and followers replay its log.

Also called primary-replica. The leader gives writes an authoritative order; followers replay that order to converge. Examples: Postgres streaming replication, MySQL binlog replication, MongoDB replica sets.

Durable (a follower is guaranteed to have the data before the write is acked) but slower, since every write pays the round-trip to the follower.

Fast, but introduces replication lag and can lose acked writes if the leader crashes before the follower catches up.

A middle ground between full synchronous (wait for all followers) and asynchronous (wait for none) replication: the write is guaranteed to survive on at least one other node before being acked, without paying the latency cost of waiting on every replica.

The mechanism underlying most durable databases and replication systems: every change is first appended to a sequential log on durable storage, and only then applied to the in-memory/on-disk data structures. Because the log is the single source of truth for "what happened and in what order," followers can replay it to reconstruct the same state — it's usually the actual unit of replication, not the final table data.

Causes "read-your-writes" bugs — a user writes, then immediately reads a stale replica and doesn't see their own change. Route to the primary for the simple fix, or carry a commit position/session token and choose a replica that has reached it.

A failover hazard. Majority agreement and a new epoch or term choose the current owner, while fencing at the protected resource rejects delayed work from an old leader.

In leaderless replication, requiring the write set (W_write) plus read set (R_read) to exceed the total replica count (N_replicas) makes the sets overlap under the model. It does not alone guarantee linearizability: concurrent writes, sloppy quorums, conflict resolution, and repair behavior still matter.

Consensus establishes an irrevocable decision under an explicit failure model. Terms or epochs reject stale leaders, and a majority makes progress possible when enough nodes can communicate. Consensus chooses authority; fencing prevents delayed old authority from acting.

Useful for multi-region writes but introduces conflict resolution when two leaders accept conflicting writes to the same record.

No single leader orders writes. Correctness relies on the W_write + R_read > N_replicas quorum rule. Used by Cassandra and DynamoDB.

Solves write throughput and storage limits, which replication does not (replication only scales reads). Real systems layer both: each shard is itself a replicated cluster.

The hardest, most-tested sharding decision: it must distribute load evenly AND align with the dominant query pattern, or queries without it become expensive scatter-gathers.

Caused by a partition key that concentrates traffic — e.g. shard-by-userID plus a celebrity user, or shard-by-timestamp with everyone writing to "now."

Happens when a query doesn't include the partition key. Expensive — avoided by choosing a partition key that matches the dominant query pattern.

Good for range queries (e.g. "all orders from March") but hotspot-prone when writes cluster at one end of the range (e.g. always-increasing timestamps).

Distributes load evenly but naive hash(key) % N reshuffles nearly every key when N changes, since N is the divisor. See Consistent Hashing for the fix.

Introduced by Karger et al. (1997). Places nodes and keys on a ring; each key belongs to the next node clockwise. Because node positions are independent of N, adding/removing a node disturbs only one arc of the ring. Used by Cassandra, DynamoDB, and memcached client-side sharding.

Plain consistent hashing does not distribute evenly on its own; virtual nodes fix this by giving each physical node many points on the ring, so a removed node's load spreads across many neighbors instead of dumping onto one.

A standardized, broker-based messaging protocol (as opposed to Kafka's custom protocol over a partitioned log). RabbitMQ is the canonical AMQP implementation, offering flexible routing (exchanges, bindings, per-message routing keys) that lean it toward the work-queue / point-to-point model, though it can do pub-sub too via fanout exchanges.

Lets a producer hand off work and move on; a consumer processes whenever it can. Buys fast producer responses, spike buffering, and consumer fail/restart safety.

The "done once by someone" model. Examples: Celery, AWS SQS.

The "everyone notified" model. Examples: Kafka, AWS SNS.

What real messaging systems provide. Requires consumers to be idempotent, since a message may be redelivered after a crash-in-the-gap between processing and acking.

Some brokers and stream processors can provide exactly-once effects inside a transaction boundary. A worker can still crash between an external side effect and its acknowledgement, so arbitrary side effects need idempotency keys, an outbox, or reconciliation.

Prevents a poison message from blocking the main queue by routing it aside after a bounded number of failed processing attempts.

The redelivery window: if a consumer doesn't ack within this window, the message becomes visible again and another consumer may pick it up.

An unbounded queue is not a fix for structural overload — it delays failure rather than preventing it. If the consumer is structurally slower than the producer, the real fix is adding consumers.

Implemented via token bucket, leaky bucket, or sliding window algorithms. Redis is the canonical store, using atomic INCR+TTL or a sorted-set sliding window.

Tokens refill into a bucket at a fixed rate (e.g. 10/sec); each request consumes one token, and requests are rejected once the bucket is empty. Unlike a strict fixed rate, unused tokens accumulate up to the bucket's capacity, so a client can burst above the average rate briefly if it hasn't been using its full allowance. The most commonly used rate-limiting algorithm because it naturally tolerates bursty, real-world traffic.

Incoming requests fill a fixed-size queue ("bucket"); the bucket "leaks" (processes) requests at a constant rate regardless of how bursty the input was, and new requests are dropped once the bucket is full. Unlike token bucket, it smooths bursts out into a steady rate rather than allowing them through — useful when the downstream system genuinely can't handle spikes at all.

A fixed window (e.g. "100 requests per minute, reset on the minute") allows a client to send 100 requests at 0:59 and another 100 at 1:00 — 200 in two seconds. A sliding window instead counts requests in the trailing N seconds at all times, closing that loophole. Commonly implemented in Redis with a sorted set keyed by timestamp.

Content Delivery Network. Answers the ~150ms transcontinental latency problem by serving static (and sometimes dynamic) content from a node physically close to the requester. Examples: Cloudflare, Akamai, CloudFront, Fastly.

A superset of a reverse proxy/load balancer's role, centralizing authentication, rate limiting, SSL termination, and routing for all backend services. Examples: Kong, AWS API Gateway, Envoy.

Answers "is this key definitely absent?" cheaply, at the cost of occasional false positives (never false negatives). Cassandra uses one per SSTable to skip disk reads for keys that certainly aren't present.

Needed whenever exactly one node must own a piece of work. Implementations: Redlock (Redis-based), ZooKeeper (ephemeral znodes), etcd (lease-based).

ZooKeeper's primitive for leader election and distributed locking: a client creates an ephemeral znode, which ZooKeeper automatically removes if that client disconnects or crashes (its session expires). Other nodes watch for that deletion to detect failure and trigger a new election — turning "is the leader still alive?" into a problem ZooKeeper's session mechanism answers for you, rather than something each service has to implement with heartbeats and timeouts itself.

Short for "Sorted String Table." Cassandra (and other LSM-tree-based stores) write incoming data to an in-memory structure first, then periodically flush it to disk as an immutable, sorted SSTable file. Because SSTables are immutable and sorted, lookups can binary-search them and a per-file Bloom filter can cheaply rule out files that definitely don't contain a given key, avoiding needless disk reads across old files.

Used to turn an incrementing counter or hash into a short, URL-safe string. A 7-character base62 code covers 62⁷ ≈ 3.5 trillion values.

One approach to the URL shortener's uniqueness problem: generate a large pool of unused codes ahead of time and dispense them on demand, avoiding collision retries at write time.

A URL shortener normally handles GET /{short_code} and returns a 301 or 302 response with the destination in the Location header. 301 allows browsers and intermediaries to cache the redirect; 302 keeps more clicks flowing through the service for analytics and control.

A vector clock stores a counter per participating replica. If every counter in version B is at least version A's counters, A is an ancestor of B. If neither dominates, the versions are concurrent siblings and require conflict resolution.

Nodes periodically send their membership view and heartbeat counters to random peers. Missing heartbeats eventually mark a node suspect or failed, while updates spread through the cluster without a single monitoring coordinator.

When an intended replica is unavailable, the system preserves availability by using another healthy node. The temporary holder records a hint so the value can be handed back when the original replica recovers.

A temporary replica stores a hint identifying the unavailable destination. Once that node is healthy, the hint is replayed and the temporary copy can be discarded or reconciled.

Replicas periodically compare their contents and copy newer or missing values. Merkle trees make this practical by narrowing comparison to ranges whose hashes differ.

Leaf hashes summarize data ranges; parent hashes summarize child hashes; the root summarizes the replica. Matching roots mean the compared ranges match, while differing branches guide a small repair instead of a full dataset copy.

A common layout uses timestamp bits, datacenter and machine or worker bits, and sequence bits for multiple IDs generated in one millisecond. It is roughly time-sortable, but requires unique worker assignment and clock rollback handling.

A frontier separates waiting URLs from visited URLs and combines priority, freshness, host routing, and politeness. It is usually durable enough to resume after a worker or process failure.

Route URLs for the same host to controlled queues and add delays or concurrency limits between downloads. Politeness is both an operational requirement and a way to avoid looking like a denial-of-service attack.

Before crawling a host, fetch and cache its robots.txt rules, then apply the relevant user-agent and allow/disallow directives. It is a cooperation protocol, not a security boundary.

A publish event is copied into each follower's feed cache before they read. This gives fast reads but creates high write amplification and hot-key problems for accounts with enormous audiences.

The system stores posts once and assembles a user's stream at read time. It avoids work for inactive users and celebrities, but increases read latency and query complexity.

After an HTTP upgrade, either side can send messages over the live connection. WebSockets suit chat and presence, but live connection state must be routed to the correct server and durable messages must live elsewhere.

Presence services use connection state and heartbeats. A user is online while heartbeats arrive within a lease window; after the timeout, the status expires rather than relying on a clean disconnect event.

Each edge represents a character and each node represents a prefix. Store the top k completions at each node to answer common autocomplete queries without traversing the entire subtree.

The API authorizes an upload and returns a URL with a short expiry and constrained object key or method. The client sends the large payload to storage instead of consuming API-server bandwidth.

A video pipeline can split, decode, encode, package, and publish artifacts as separate tasks. The DAG scheduler runs independent tasks in parallel, retries failed work, and tracks dependencies so one failure does not restart everything.

The server creates an upload session and records confirmed byte ranges or blocks. A client reconnects, asks for the current state, and sends only the missing portion instead of restarting a large file.

Split a file into content-addressed blocks and compare hashes between versions. Upload only changed blocks, then write new metadata that references the complete block set.

Start with transactions, query shapes, relationships, consistency, size, and latency. Relational databases fit constraints and joins; key-value or document stores fit known-key access and flexible large-scale records; object storage fits large immutable blobs.

Cross-region copies improve availability and user latency, but add replication lag, failover routing, conflict resolution, data residency, and recovery-point decisions. State whether writes are active-active or routed to one primary region.

Atomicity makes a transaction all-or-nothing; consistency preserves declared invariants; isolation controls concurrent visibility; durability keeps committed data after failure. These guarantees are valuable for metadata and permission changes but may cost scale or latency.

Move old versions, backups, or infrequently watched media to an archival tier. Cost savings come with higher retrieval latency and sometimes additional restore fees, so lifecycle rules should match retention and recovery requirements.

A data model built around relations and sets of rows. It is a strong fit when relationships, joins, constraints, and multi-object transactions are central. The model is independent of one particular relational database product.

Stores related values together as a document. It can simplify reads and schema changes when the aggregate is read as one unit, but duplicated or cross-document relationships need explicit update and consistency handling.

Represents entities and their relationships directly. It is useful when the important queries follow paths through a connected graph rather than filtering independent records.

The storage accepts flexible records and readers apply the expected shape later. It improves ingestion flexibility but moves malformed-data handling and compatibility work into readers and transformations.

The writer must satisfy the declared structure before data is accepted. This protects downstream readers and invariants, but schema changes need a rollout plan.

SQL is the common example: the query states what rows or result set are wanted, while the optimizer chooses indexes, joins, scans, and parallelism. This differs from procedural code that specifies each transformation step.

A materialized view precomputes a query, join, or aggregate for faster reads. It is a deliberate copy, so refresh lag, invalidation, backfill, and rebuild behavior are part of the design.

User-facing workloads typically read or update a small number of records and need predictable latency, indexes, concurrency control, and transactional integrity.

Analytical workloads issue fewer but heavier queries over many records. Column storage, compression, parallel scans, and precomputed aggregates often fit better than point-lookup indexes.

Efficient for equality lookups when the key is known, but it does not naturally support ordered range scans. Hashing also needs collision handling and durability rules.

B-trees keep keys ordered and bounded in height, making point lookups and range scans predictable. Updates modify or split pages in place, which trades read simplicity for random-write work and page contention.

Writes land in a memory table and later flush to immutable SSTables. Background compaction merges files and removes obsolete versions. It can make writes efficient while increasing read and compaction work.

Compaction rewrites storage to reduce duplicate versions, improve locality, and reclaim space. It consumes I/O and CPU, so compaction scheduling is part of tail-latency and capacity planning.

An in-memory sorted structure (commonly a skip list or red-black tree) holding the most recent writes. Sorting in RAM costs no I/O, which is what lets an LSM engine write only sequentially and still flush a file that is already in key order. It is flushed to an immutable SSTable when it reaches a size threshold, and it is backed by the write-ahead log so a crash does not lose it (see 3.3).

In an append-only engine there is no way to erase a record, so a delete appends a marker that shadows every older value for the key. A tombstone may only be discarded once compaction covers every file that could still hold an older value; dropping it early makes a deleted row reappear. Delete-heavy workloads therefore grow before they shrink (see 3.3).

A run behaves like a single sorted file for lookup purposes. Leveling keeps one run per level; tiering allows up to T runs per level. The number of runs a query must consult is what read amplification counts (see 3.3).

Merging into level i rewrites the overlapping part of that level, so an entry is rewritten about T times per level, giving write amplification of order T·L and point-lookup cost of order L. It also keeps space amplification low. This is the RocksDB and LevelDB default (see 3.3).

Runs pile up at a level and are merged only when the level is full, so an entry is written about once per level — write amplification of order L — at the cost of checking up to T·L runs per lookup and holding up to T copies per level. This is the Cassandra default (see 3.3).

With data size N and memtable size M, the level count is L = ceil(log_T(N/M)). T appears in every amplification term: raising it makes leveling write more and read less, lowering it does the reverse. There is no value that makes both cheap (see 3.3).

The third amplification alongside read and write. LSM engines pay it in obsolete versions and uncollected tombstones until compaction runs; B-trees pay it in page fragmentation from splits. Leveling keeps it low, tiering allows up to T copies per level (see 3.3).

Because an SSTable is sorted, an index does not need an entry per key: a sparse set of offsets narrows a lookup to one small block that is then scanned. This is what keeps the in-memory index small enough to hold for a large file — sorting is what makes the index cheap (see 3.3).

Fanout B is roughly page size divided by (key size + pointer size), so a 4 KB page with 32-byte entries gives B of about 128. Lookup cost is the tree height, about log_B(N), so a large fanout is the whole point: a billion rows sit about 5 levels deep instead of the ~30 a binary tree would need (see 3.3).

LSM engines may check memory and several SSTables; indexes may require multiple page reads. Bloom filters, caches, and compaction reduce the number of structures visited.

Page splits, WAL records, replication, compaction, and index maintenance can all multiply physical work. Measure it when sizing storage bandwidth and SSD endurance.

Column storage improves compression and lets an analytical query read only the columns it needs. It is usually a complement to an OLTP store, not a universal replacement.

Required during rolling upgrades and long-lived data retention. New readers should understand old fields and preserve old meanings while the fleet migrates.

Usually requires old readers to ignore unknown fields and new writers to avoid changing the meaning of existing fields until all readers are upgraded.

Safe evolution requires compatibility rules, rollout order, ownership, and a deprecation window. The same concern applies to database rows, RPC messages, queue events, and client payloads.

Rolling upgrades reduce downtime and blast radius, but require mixed-version compatibility. Deploy readers before writers when introducing new fields or event shapes.

Dataflow makes the producer, encoding, transformation, destination, lag, and retry behavior explicit. It is the common shape connecting databases, queues, streams, indexes, and analytics.

A system of record owns the durable truth for a fact. Caches, search indexes, analytics tables, and notifications should have a defined relationship to that source and a way to recover from drift.

Derived data includes caches, indexes, materialized views, aggregates, and machine-learning features. Retain enough input history or snapshots to rebuild it when code or requirements change.

CDC commonly reads a database log so inserts, updates, and deletes can feed search, caches, warehouses, or services. Consumers still need schema evolution, duplicate handling, transaction ordering, and replay rules.

Current state is reconstructed by replaying events. Event sourcing improves auditability and replay, but event schemas, snapshots, privacy, corrections, and projection rebuilds become long-lived design obligations.

Compaction removes obsolete records while keeping the newest state for each key. It supports rebuilding a key-value view without retaining every historical update forever.

Isolation is a spectrum. Weaker levels permit more anomalies but usually allow more concurrency; stronger levels prevent more anomalies but may block or abort transactions.

Two statements in one transaction may see different committed states. It prevents dirty reads but does not by itself prevent lost updates, read skew, or predicate anomalies.

Readers see a consistent version while writers continue. It prevents many read anomalies, but write skew and some lost-update patterns still require stronger protection or explicit coordination.

Serializable execution preserves the strongest general concurrency contract, often through locking or conflict detection. Applications must expect blocking or serialization failures and retry safely.

Two actors read the same old value, compute independent updates, and the later write erases the earlier one. Use atomic updates, compare-and-set, locks, or a transaction that detects the conflict.

Each transaction observes a valid state and changes a different row, but both commits make the combined state invalid. Serializable isolation or explicit locking of the invariant is required.

Another transaction inserts, deletes, or changes a row so it enters or leaves the predicate result. Range locking or serializable conflict detection protects the predicate when needed.

2PC provides distributed atomic commit when participants support the protocol, but adds coordinator state, blocking paths, timeouts, and operational coupling. It is not a universal substitute for local transactions and asynchronous workflows.

Each step commits locally and emits the next action. If a later step fails, compensating work attempts to restore the business outcome. Sagas need idempotency, durable progress, and explicit intermediate states.

The transaction writes business state and an outbox row atomically. A separate publisher retries unsent rows, preventing the dual-write gap between committing a database change and publishing a message.

A request may be delayed, duplicated, accepted without its response, or processed by a node that another node considers dead. Robust designs make retries, ownership, and recovery explicit.

In an asynchronous network, a timeout cannot prove that a node crashed; it may only be slow or partitioned. Failure detectors therefore produce suspicions that need quorum, epochs, or fencing before authority changes.

A timeout bounds caller patience; it does not cancel remote work or prove the outcome. Pair it with request identity, idempotency, cancellation where supported, and reconciliation.

NTP reduces skew but does not create a perfectly shared clock. Do not use wall-clock timestamps as sole proof of causality or ownership without an error bound and a safer protocol.

Monotonic clocks are appropriate for timeouts, durations, and retry backoff because wall-clock adjustments should not make elapsed time negative or unexpectedly long.

A lease lets a system act on temporary ownership, but a paused owner may resume after expiry. The protected resource should validate a fencing token or epoch rather than trusting the lease holder alone.

When ownership changes, the new owner receives a higher token. Storage or the external resource rejects operations carrying an older token, preventing delayed work from acting after a lease expires.

Garbage collection, scheduler stalls, resource pressure, or a debugger can pause a process long enough for another node to take ownership. Fencing protects against its late return.

A new leader or configuration receives a higher term. Messages from an older term are rejected, which prevents a delayed former leader from being treated as current authority.

Byzantine tolerance matters when nodes or communication may be adversarial or independently operated. Ordinary service architectures usually assume crash and omission faults instead, but should state that assumption.

Batch jobs partition input, move related records together, perform joins or aggregations, and emit derived output. Deterministic operators and materialized checkpoints make failed work recomputable.

Map stages are naturally parallel because each input can be processed independently. They commonly emit intermediate key-value pairs for a later grouping stage.

Shuffle is the network-heavy boundary between independent transformation and grouped processing. It determines parallelism, skew, ordering, and often the dominant batch cost.

Reduce consumes all or many values for a key and produces a smaller result. It must handle skew, retries, memory pressure, and the desired ordering of grouped input.

Partitions provide parallelism and define the normal ordering boundary. Events with the same key can be routed together; consumers track progress independently by offset.

Each partition is assigned to one active consumer in a group at a time, while different groups can independently replay the same events for different purposes.

Consumers checkpoint offsets so they can resume after failure. The checkpoint must be coordinated with processing state or duplicate processing remains possible.

Event time supports historically correct windows when events arrive late or out of order. It requires a policy for watermarks, late data, corrections, and result revisions.

Processing time is simple and low-latency but can produce different answers when network delay or replay changes arrival order. It is appropriate when approximate real-time behavior is acceptable.

Stream joins keep state for matching records and must define retention, out-of-order behavior, late data, and what happens when one side is absent.

Aggregations, windows, joins, and sessions are stateful. Recovery uses checkpoints, changelog replication, or replay from the input stream.

A checkpoint lets a processor resume from a consistent point instead of starting over. Correctness depends on coordinating the checkpoint with input offsets and output effects.