A vocabulary,
in one place.

Atomicity, Consistency, Isolation, Durability — the database transaction guarantees.

Coined by Andreas Reuter and Theo Härder in 1983. Atomic = all-or-nothing; Consistent = invariants hold; Isolated = concurrent txns appear serial; Durable = once committed, survives crashes.

Encryption that integrates confidentiality and integrity in one operation.

AES-GCM and ChaCha20-Poly1305 are the canonical examples. Replaces the error-prone "encrypt-then-MAC" composition that gave us Lucky13, BEAST, and POODLE. Every TLS 1.3 cipher suite is AEAD.

TLS extension that picks h2 / h3 / http/1.1 inside the handshake.

Avoids a second round trip after TLS finishes. Also how WebRTC and gRPC tell the server what protocol to switch to.

Speedup = 1 / (s + p/N), where s is the serial fraction.

A 5% serial fraction caps speedup at 20× no matter how many cores you add. Why "make it parallel" doesn't scale forever.

Background process that reconciles divergent replicas.

Merkle-tree comparison or read-repair. Cassandra and Riak run anti-entropy continuously to converge eventually-consistent replicas.

One IP, advertised from many locations; routing picks the nearest one.

How DNS root servers work, how Cloudflare and AWS Global Accelerator route traffic, how DDoS mitigation absorbs traffic across regions.

A traffic entry point that routes, authenticates, and rate-limits.

AWS API Gateway, Kong, Tyk, Envoy. Sits in front of microservices to provide a single client-facing surface.

Balanced multi-way search tree; the shape of every relational index.

Bayer & McCreight, Boeing 1971. Wide fan-out keeps the tree shallow even at billions of records — 4 levels deep at fanout 200 vs 30 levels in a binary tree.

Wait longer between retries after each failure.

Exponential, jittered, decorrelated. Without jitter, all clients retry at exactly the same moment — the thundering herd that crashes a recovering service.

A signal from a slow consumer asking the producer to slow down.

Without it, queues grow until OOM. Reactive Streams and HTTP/2 flow control bake it in; most systems retrofit it badly.

P(A∣B) = P(B∣A)·P(A)/P(B). The rule for updating belief.

Counterintuitive when P(A) is small: a 99%-accurate test on a 1-in-1000 disease still gives ~9% true-positive rate.

Congestion control that models the path instead of reacting to loss.

Cardwell et al at Google, 2017. Replaces CUBIC's "halve cwnd on loss" with active probing of bandwidth and RTT. Default in Linux 4.9+ and Google's edge.

A per-client backend that aggregates and shapes services for one frontend.

A web BFF, a mobile BFF, a partner BFF. Keeps OAuth refresh tokens out of browsers (the Part 10 OAuth pattern). Adds a hop; saves a thousand frontend headaches.

How autonomous systems on the internet exchange routes.

Path-vector protocol with policy. Most internet outages that "took down half the internet" were BGP misconfigurations.

Hash collisions become likely at √(output space).

A 256-bit hash gives only ~128 bits of collision-resistance. Why MAC tags need to be at least 128 bits in modern protocols.

Probabilistic set: "definitely not" or "probably yes" in tiny space.

Burton Bloom, 1970. Cassandra row caches, every LSM-tree, Bitcoin SPV, Chrome safe-browsing. ~10 bits per element for 1% false-positive.

Fraction of reads served from cache.

95%+ is a healthy target for read-heavy services. Below 80% suggests cache key design is wrong.

When a popular cache key expires and many concurrent requests miss simultaneously.

Each miss does the expensive backend work; backend gets crushed. Mitigations: probabilistic early expiration, request coalescing, lock-on-miss.

App reads cache; on miss reads source and populates.

The most common caching pattern. Simple to reason about; staleness is the cost.

Under partition, choose Consistency or Availability.

Eric Brewer, 2000. Often misread — it's about behaviour during a partition, not a permanent trade-off. Most real systems are AP with bounded staleness.

Number of distinct values in a set.

High-cardinality columns make poor partition keys (uneven distribution); low-cardinality columns make poor indexes (each key matches many rows).

A global cache fabric with PoPs near users.

Cloudflare, Akamai, Fastly. Modern CDNs do more than caching — TLS termination, WAF, edge compute, image transforms.

Append-only public logs of every TLS certificate issued.

RFC 6962. Browsers refuse certs without a Signed Certificate Timestamp embedded. Tools like crt.sh let you spot rogue certs for your domain in minutes.

Linux mechanism that limits and accounts CPU, memory, IO for a process tree.

Plus namespaces = container. cgroupv2 unified the interface in 2016; required for systemd and modern container runtimes.

Replicas in a linear chain; writes flow head→tail, reads from tail.

van Renesse & Schneider, 2004. Strong consistency with simpler failure handling than Paxos. Used in Microsoft's Azure storage and FoundationDB.

In a saga: services react to each other's events vs a central coordinator drives steps.

Choreography is decentralised, harder to debug. Orchestration centralises the workflow; easier to reason about, single point of failure.

IP address + prefix length notation (e.g. 10.0.0.0/24).

Replaced the rigid Class A/B/C system in 1993. The /N tells you how many high bits identify the network.

A state machine that fails fast after a downstream is unhealthy.

Closed → Open → Half-open. Stops you from beating up an already-broken service. Hystrix popularised it; Resilience4j is the modern Java incarnation.

Approximate-LRU cache eviction with a circular reference bit.

Each entry has a referenced bit. Eviction sweeps a clock hand; sets the bit to 0; evicts when it sees a 0. Used by Redis (allkeys-lru), Postgres buffer pool.

Merging LSM SSTables to bound read amplification.

Tiered (size-tiered): merge files of similar size. Levelled (RocksDB default): each level is K× the size of the previous, single sorted run per level.

Reuse a fixed pool of long-lived connections instead of opening one per request.

Database connections are expensive; PgBouncer, HikariCP, and the like multiplex thousands of short requests over hundreds of long connections.

Hash both keys and nodes onto a ring; nodes own arcs.

Karger et al, MIT 1997. Adding/removing a node only moves K/N keys, not the whole keyspace. Powers every distributed cache and CDN.

Separate read and write models, often backed by different stores.

Pairs naturally with event sourcing. Read side can be denormalised, indexed, or materialised differently from the write side.

A data type whose merges are commutative, associative, idempotent.

Strongly eventual consistency without coordination. The math behind every collaborative editor (Yjs, Automerge).

HTTP header that whitelists which origins can load scripts, styles, frames.

The single most effective XSS mitigation when configured strictly. nonce or hash-based for inline scripts.

Attack: a third-party site causes the browser to send authenticated requests to your origin.

Defenses: SameSite cookies, anti-CSRF tokens, double-submit cookies. Largely solved by SameSite=Lax becoming the browser default.

Edges have direction; no cycles.

The natural shape for build systems, version control, schedulers, dataflow engines. Topological sort produces a valid execution order in O(V+E).

AWS DynamoDB Accelerator — an in-memory cache in front of DynamoDB.

Sub-millisecond reads. Pattern transferable: every fast KV store benefits from a memory tier.

Coordinated traffic flood from many sources.

L3/L4 (volumetric, SYN floods) vs L7 (HTTP slow-loris, regex). Anycast + scrubbing centers (Cloudflare, AWS Shield) absorb the volumetric kind.

Two or more transactions wait on each other forever.

Detected by cycle-finding in a wait-for graph; resolved by aborting the youngest transaction. Postgres detects deadlocks every 1 second by default.

A request's path across services, captured as a tree of spans.

OpenTelemetry standardised the wire format. Sampling is the open problem at scale — head-based vs tail-based.

Data Plane Development Kit — userspace networking that bypasses the kernel.

Polled-mode drivers. Hundreds of millions of packets per second on commodity hardware. Used by load balancers, telecom NFV, high-frequency trading.

Bind an OAuth token to a client-side public key.

RFC 9449. Theft of just the access token is useless without the matching private key. Replacing bearer tokens for high-value APIs.

Run sandboxed programs in the Linux kernel without loading modules.

Originally for packet filtering (Berkeley Packet Filter); now used for tracing, networking (Cilium), security (Tetragon), observability.

Run code at the CDN edge, milliseconds from the user.

Cloudflare Workers, AWS Lambda@Edge, Vercel Edge Functions. V8 isolates rather than full processes — cold start measured in microseconds.

Linux IO multiplexing — register fds, get notifications on readiness.

Replaces select/poll which were O(N) per call. epoll_wait is O(1). The foundation of every async Linux network server.

Store k data shards + m parity shards; tolerate any m losses.

Reed-Solomon for cold storage. ~1.5× space overhead vs 3× for replication, at the cost of more compute on read with failures.

Persist state as an append-only log of events; current state is a fold.

Audit, replay, and time-travel debugging come for free. The cost is querying — you usually pair with CQRS read models.

All replicas eventually agree if writes stop.

The default for AP systems under CAP. "Eventually" can be milliseconds (gossip in a healthy cluster) or hours (cross-region replication during a partition).

Phishing-resistant authentication using public-key cryptography.

The browser API + the device protocol. Passkeys are FIDO2 credentials synced via cloud. The end of the password.

Past sessions stay secret even if the long-term key leaks.

Achieved with ephemeral key exchange (ECDHE). Mandatory in TLS 1.3 — RSA key transport is gone for this reason.

Automatic reclamation of unreachable memory.

Mark-sweep, generational, tri-color, concurrent. Java's G1, ZGC, Shenandoah; Go's tri-color concurrent collector; .NET's server GC.

The 2003 paper that founded scale-out storage.

Blueprint for HDFS, Colossus, every modern object store. Master + chunk servers; chunks are 64MB.

Each node periodically tells a random peer what it knows.

Information spreads in O(log N) rounds. Cassandra, Consul, Riak. No single coordinator to fail.

HTTP/2 + Protobuf RPC framework.

Bi-directional streaming, codegen in 12+ languages, schema-first. Default for internal microservice meshes.

O(1) average lookup via key → bucket index.

Hans Peter Luhn, IBM 1953. Collision strategies: chaining and open addressing. Every dictionary in every language.

Send a duplicate request to a second server if the first is slow; take whichever returns first.

Dean & Barroso 2013. Cuts tail latency at modest cost. Tied requests cancel the loser.

Highest offset acknowledged by all in-sync replicas.

Kafka concept. Consumers can only read up to the HW; this is what makes the log durable. HW lags the leader by one round-trip.

When a replica is down, a temporary node holds its writes and replays them later.

Dynamo-style availability technique. Handoffs are time-bounded; if the replica stays down too long, anti-entropy takes over.

Cardinality estimator in 12 KB with ~1% error.

Flajolet et al, INRIA 2007. Mergeable across shards. Powers every "unique users" dashboard at internet scale.

Multi-layer graph index for approximate nearest-neighbour search.

Malkov & Yashunin, 2016. Default ANN index in pgvector, Qdrant, Weaviate, Milvus. State-of-the-art recall; high memory cost.

Header compression for HTTP/2.

RFC 7541. Static + dynamic Huffman tables. A repeated 200-byte User-Agent header collapses to one byte after the first send.

Tells the browser: "no plaintext, ever again, for this domain".

Stops downgrade attacks once cached. The HSTS preload list ships in browsers and closes the first-visit gap.

A request can be retried without changing the result.

GET, PUT, DELETE are idempotent in HTTP. POST is not — which is why payment APIs use idempotency keys to deduplicate retries.

A client-supplied UUID that lets the server deduplicate retried POST requests.

Stripe popularised the pattern. Server stores (idempotency_key → response) for ~24h; second request with same key returns the same response.

Replicas caught up to the leader within a time bound.

Kafka. Falling behind for >30s evicts you; catching back up readmits. Producer durability scales with ISR size.

H(X) = −Σ p log p. Expected bits per sample.

Shannon, 1948. The compression ceiling for any source. Higher entropy = more uncertainty.

128-bit IP addresses; 2^96× more space than IPv4.

No more NAT (mostly). 30+ years of slow rollout; finally hit ~50% of US traffic in 2023.

How much concurrent transactions can see of each other.

Read uncommitted < read committed < repeatable read < snapshot < serializable. Each blocks one anomaly the previous allowed.

Variance in latency or arrival rate.

A constant 100ms is fine; latency that swings 5–500ms is debilitating. Sources: GC pauses, network microbursts, scheduling delays.

Self-contained signed (or encrypted) token: header.payload.signature.

Ubiquitous in OAuth and OIDC. Verify offline; revoke through context (short TTL + refresh rotation).

D_KL(P‖Q) = Σ p log(p/q). Extra bits to encode P with Q.

Asymmetric: D_KL(P‖Q) ≠ D_KL(Q‖P). Cross-entropy loss = entropy + KL.

Logical counter per process; causal ordering of events.

Lamport 1978. Each event's timestamp is max(local, received) + 1. Two events with timestamps in different order may have any real-time ordering — but causally-ordered events keep their order.

Picking exactly one node as the coordinator.

Paxos, Raft, ZooKeeper, etcd. Must tolerate failures and partitions without electing two leaders.

Monotonically-increasing term number for each elected leader.

Kafka KIP-101. New leader's first action is to fence out the old leader by epoch. Closes the "ghost record" data-loss window.

L = λW. Items in system = arrival rate × average wait.

Holds for any stable queue regardless of distribution. The most-used theorem in operations research.

Append-only writes flushed and merged in the background.

O'Neil et al, 1996. RocksDB, LevelDB, Cassandra, BigTable. Trades write amp for sequential I/O — SSDs love it.

Cache function results by argument tuple.

Bottom of dynamic programming. Trivially turns exponential recursion into polynomial time, at the cost of memory.

Instruction that prevents reordering of memory operations across it.

CPUs and compilers reorder for performance. Concurrent code uses barriers to ensure visibility ordering. acquire / release / sequentially-consistent.

L1 ~1ns, L2 ~4ns, L3 ~12ns, RAM ~100ns, SSD ~100µs, network ~1ms.

Each level is ~10× slower than the last. Cache locality dominates algorithmic complexity for small n.

Tree of hashes; root commits to all leaves.

Ralph Merkle, 1979. Bitcoin, Git, ZFS, Certificate Transparency, IPFS. Inclusion proofs are O(log n) hashes.

Set similarity estimation via minimum hash matching.

Andrei Broder at AltaVista, 1997. Compute Jaccard similarity in O(k) instead of O(|A∪B|). Used in web deduplication.

Mutual TLS — both client and server present certificates.

Service mesh default for cross-service auth. Token-binding alternative is DPoP.

Each row keeps versions; readers don't block writers.

Postgres, MySQL InnoDB, Oracle, CockroachDB. Vacuum/cleanup reclaims old versions.

Synchronises clocks within milliseconds across the internet.

RFC 5905. Stratum 0 = atomic clocks/GPS, stratum 1 = directly attached, etc. PTP (Precision Time Protocol) for sub-microsecond datacenter sync.

The modern auth-delegation flow: code + PKCE for everyone.

Removes implicit and password grants. Adds mandatory PKCE, exact-match redirect URIs, refresh token rotation.

Server pre-fetches a signed revocation response and attaches it to the handshake.

Faster than client-side OCSP and doesn't leak browsing history to the CA.

Identity layer on top of OAuth 2.0 — adds an ID token (JWT).

Standardises "who is the user". Issued alongside the access token after auth code exchange.

Read freely; check for conflicts at commit; retry if conflict.

Postgres serializable level uses it (SSI). Better than locks under low contention; degrades to busy-waiting at high contention.

To atomically write to DB + publish a message: write to an outbox table in the same DB transaction.

A separate process polls the outbox and publishes. Solves "double-write" — without it, message+DB updates can't be atomic.

99th percentile response time.

For fan-out queries, system latency is dominated by the slowest. p99 of one becomes p50 of 100. Hedged requests cut the tail at modest cost.

Family of protocols for distributed consensus.

Lamport, 1989. Notoriously dense; "Paxos Made Simple" is the path in. Variant Multi-Paxos powers Spanner, Chubby.

Cryptographic binding between authorisation request and token exchange.

RFC 7636. Stops authorization-code interception. Required for every OAuth 2.1 client (public and confidential).

A CDN edge location.

Cloudflare has 300+. Closest to the user wins; anycast routing handles the picking.

UDP-based multiplexed and secure transport — the substrate of HTTP/3.

Per-stream loss recovery (no TCP HOL), 0-RTT resumption, integrated TLS 1.3, connection migration via connection ID.

A majority needed for a write or read to count.

In a 5-node system, quorum is 3. Quorum reads + quorum writes = strong consistency. R+W>N is the math.

Consensus algorithm explicitly designed to be teachable.

Ongaro & Ousterhout, 2014. Powers etcd, Consul, CockroachDB, TiKV. Easier to reason about than Paxos.

Caps request rate per key.

Token bucket, leaky bucket, fixed window, sliding window. Each has different burst tolerance.

Long-lived OAuth credential to mint new access tokens.

Modern: rotate on every use, revoke the chain on reuse detection. Storage matters — httpOnly cookie or OS keychain, never localStorage.

Alternative to consistent hashing — pick the node that scores highest for the key.

For each (key, node) pair compute hash; key goes to node with max hash. No virtual nodes needed; balanced by construction.

Server-side proxy that fronts your backend.

NGINX, Envoy, Caddy, HAProxy. TLS termination, load balancing, caching, header rewriting.

Recovery Point / Recovery Time Objective.

RPO = how much data you can lose (e.g. 5 min). RTO = how long the recovery takes (e.g. 1 hour). Drives backup frequency and replication topology.

Long-running distributed transaction as a sequence of compensable steps.

Each step has a corresponding compensation. Replaces 2PC for cross-service transactions where atomicity isn't feasible.

Splitting data across machines by key.

Range, hash, directory. The harder problems are rebalancing, cross-shard queries, hot keys.

Probabilistic balanced search structure.

William Pugh, 1989. Tall nodes form an "express lane". Lock-free skip lists are easier to write than lock-free balanced trees — why Redis ZSET uses them.

A target for an SLI (latency, availability).

Internal commitment, looser than SLA. Tied to error budget — burn it slowly or roll back.

Each transaction sees a consistent snapshot taken at start.

Postgres, Oracle default. Prevents dirty reads, non-repeatable reads, phantoms — but allows write-skew anomalies.

TLS extension that tells the server which hostname is being requested.

Lets one IP host many TLS sites. Travels in the clear; ECH (Encrypted Client Hello) hides it.

~3×10⁸ m/s vacuum, ~2×10⁸ m/s in fibre.

New York → London round-trip: ~56ms minimum. The floor under every cross-region replication.

A lock implemented with a busy-wait loop instead of going to sleep.

Right when contention is rare and critical sections are short (microseconds). Wrong almost everywhere else — burns CPU.

A logical flow of frames over a single connection.

HTTP/2 introduced streams to multiplex requests. HTTP/3 made each stream independent at the transport layer (no TCP HOL).

The slow end of the distribution — p95, p99, p99.9.

Dean & Barroso, 2013. For fan-out systems, the tail dominates. Hedged requests, redundant requests, soft timeouts mitigate.

Begin with a small congestion window; double per RTT until loss.

Van Jacobson, 1988. The reason new connections are slow until they're warmed up; why HTTP keep-alive matters.

A counter that limits how long something stays valid.

IP packets (hop count, used by traceroute), DNS records (cache duration), cache entries (eviction).

2018 redesign of Transport Layer Security.

1-RTT handshake, AEAD-only ciphers, mandatory ECDHE, PSK resumption. The standard.

Rate limiter that accumulates tokens at a fixed rate.

Allows bursts up to bucket size, smooth rate at long term. Default for most rate limits in cloud APIs.

Append-only record of every change for crash recovery.

Same idea as WAL. Postgres pg_wal, MySQL redo log, SQL Server transaction log. Replay on crash to recover committed transactions.

Google's globally-synchronised clock with a known uncertainty bound.

Hardware GPS + atomic clocks. Lets Spanner do externally-consistent transactions globally — wait out the uncertainty before committing.

Coordinator-driven atomic commit across N participants.

Prepare → commit. Blocking: if the coordinator dies after prepare, participants are stuck. Saga and Calvin are alternatives.

Track connected components in O(α(n)) ≈ O(1).

Galler & Fischer, 1964; Tarjan's analysis 1975. Path compression + union-by-rank. Powers Kruskal MST and equivalence-class problems.

C(N) = N / (1 + α(N−1) + βN(N−1)). Throughput vs concurrency.

Above a critical N, adding workers slows throughput. β captures coordination cost (O(N²)). The crisper version of "Amdahl plus contention plus coherence".

Per-node logical counter; comparing two clocks tells you happens-before vs concurrent.

Generalises Lamport timestamps. Dynamo used vector clocks for conflict detection; modern systems often prefer dotted version vectors or hybrid logical clocks.

Append every change to a log before applying it to data files.

Crash recovery: replay the log. The basis for every modern database's durability story.

Persistent bi-directional connection over a single TCP socket.

Upgrades from HTTP via 101 Switching Protocols. The default for browser-side real-time before HTTP/3 streams.

Schema is dynamic per row; many sparse columns.

Bigtable, HBase, Cassandra, ScyllaDB. Optimised for time-series and event data where most rows have most columns null.

Idle workers steal pending tasks from busy workers' queues.

Each worker has a deque; thieves take from the back, owner from the front. Java ForkJoinPool, Go scheduler, Rust Rayon, .NET TPL.

Injecting attacker-controlled JS into a page that the browser then trusts.

Stored, reflected, DOM-based. Defenses: contextual escaping, CSP, framework-level auto-escape (React, Svelte).

Place in code where the scheduler may preempt.

In cooperative schedulers, only at explicit yield points. Pre-1.14 Go could only preempt at function calls — a tight loop blocked the P forever.

Move data without ever copying it to userspace.

sendfile(), splice(), io_uring. Kafka brokers stream from page cache directly to socket — bytes never enter the JVM heap.