Knowledge graph
Notes
203 concepts, 31 systems and 451 flashcards so far. Each note is one idea, linked to the others. See them as a map โ
FieldsSystem Design
transactionstopic map
- ACID๐ฑA transaction groups reads and writes into one unit that commits or aborts as a whole. ACID names its four guarantees: atomicity (all or nothing on faults), consistency (your invariants), isolation (concurrent transactions don't interfere) and durability (committed data survives crashes).
- Actual Serial Execution๐ฑRun transactions literally one at a time, on one thread per partition, with all data in memory. With no concurrency there's nothing to lock, so every schedule is serial by construction.
- Deadlock๐ฑTwo or more transactions each hold a lock the other needs, so all of them wait forever. Databases find the cycle in a waits-for graph (or prevent it with timestamp priorities) and abort a victim, which the application must retry.
- Dirty Read๐ฑA dirty read is seeing another transaction's uncommitted write, which may still be rolled back. Its sibling, the dirty write, is overwriting another transaction's uncommitted write.
- Distributed Transaction๐ฑA transaction whose writes span several nodes (shards, databases or services) and must still be atomic: every participant commits or every participant aborts. It needs an atomic commit protocol, usually [[Two-Phase Commit]].
- Isolation Level๐ฑAn isolation level is a contract about which concurrency anomalies a database allows. Weaker levels admit more anomalies in exchange for less blocking and fewer aborts; only [[Serializability]] admits none.
- Lost Update๐ฑTwo transactions each read a value, modify it in application code and write it back; the second write silently erases the first. It's the classic read-modify-write race behind broken counters, balances and inventory.
- MVCC๐ฑThe database keeps several versions of each row, tagged with the transactions that created and replaced them, and each transaction reads the version its snapshot should see. Readers never wait for writers; the price is storing and garbage-collecting old versions.
- Optimistic Concurrency Control๐ฑRun transactions without locks, record what they read, and at commit validate that none of it has changed; if it has, abort and retry. It bets that conflicts are rare, and pays in wasted work when they aren't.
- Phantom Read๐ฑA phantom is a write in one transaction that changes the result of another transaction's search, typically an insert into a range someone else just queried. Row locks can't stop it, because the row didn't exist when the search ran.
- Read Committed๐ฑRead Committed guarantees no [[Dirty Read]]s and no dirty writes: you only read and overwrite committed data. Each statement sees the latest committed state, so two statements in one transaction can see different worlds.
- Saga Pattern๐ฑReplace one long distributed transaction with a sequence of local transactions, each committed immediately, plus a compensating transaction for each step. On failure, run the compensations in reverse. Atomic eventually; never isolated.
- Serializability๐ฑConcurrent transactions are serializable if the result equals running them one at a time in some order. It's the only isolation level with no anomalies to design around: a transaction that's correct alone stays correct, or fails to commit.
- Serializable Snapshot Isolation๐ฑSnapshot isolation plus a runtime check for the one pattern it misses: two consecutive read-write dependencies through one transaction. Reads still never block writes; instead, one transaction of a dangerous pair is aborted at commit.
- Snapshot Isolation๐ฑEach transaction reads from a consistent snapshot of everything committed when it started, and ignores later commits. Readers never block writers and writers never block readers, but [[Write Skew]] is still possible.
- Transactional Outbox๐ฑTo update a database and publish an event atomically, insert the event into an outbox table in the same local transaction as the change, and let a separate relay publish outbox rows to the broker. Delivery is at least once, so consumers must be idempotent.
- Two-Phase Commit๐ฑAn atomic commit protocol: a coordinator asks every participant to prepare (make the change durable and vote), then logs commit only if all voted yes and tells everyone. It is atomic but blocking: if the coordinator dies after prepare, participants wait, holding locks.
- Two-Phase Locking๐ฑReaders take shared locks, writers take exclusive locks, and every lock is held until the transaction commits or aborts. Readers block writers and writers block readers, which forbids the read-write conflicts behind write skew.
- Write Skew๐ฑTwo transactions read the same data, make a decision from it, and then write different rows, each invalidating the premise of the other. No row is written twice, so snapshot isolation sees no conflict, yet the result matches no serial order.
- XA Transactions๐ฑA 1991 X/Open standard for running [[Two-Phase Commit]] across different systems (two databases, or a database and a message broker), driven by an external transaction manager. It inherits 2PC's blocking and adds operational fragility.
encodingtopic map
- Apache Avro๐ฑAvro is a binary format with no field tags: values are written in schema order, so decoding requires the exact writer's schema. At read time Avro resolves the writer's schema into the reader's, matching fields by name and filling in defaults.
- API Versioning๐ฑAPI versioning lets a service make breaking changes without breaking clients it doesn't control, by letting each client keep the version it was built against. Additive changes need no version, as long as clients ignore unknown fields.
- Backward and Forward Compatibility๐ฑBackward compatibility means new code can read data written by old code; forward compatibility means old code can read data written by new code. Which one a change preserves decides who must upgrade first.
- Durable Execution๐ฑDurable execution runs ordinary code for a long-lived process so that it survives crashes: every step's result is recorded, and after a failure the code is replayed against that record to rebuild its state and continue where it stopped.
- Idempotency๐ฑAn operation is idempotent if doing it several times has the same effect as doing it once. Because a timeout leaves the outcome unknown, idempotency is what makes retries safe; idempotency keys make non-idempotent operations like "charge a card" behave that way.
- JSON vs Binary Encoding๐ฑTextual formats like JSON describe themselves, so they carry field names in every record and have no enforced schema. Schema-driven binary formats carry only values, which makes them several times smaller and lets compatibility be checked before deploy, at the cost of human readability.
- Message Passing๐ฑIn asynchronous message passing a sender hands a message to an intermediary, usually a message broker, and carries on without waiting. The broker buffers, redelivers and fans out messages, decoupling sender and recipient in time and address.
- Protocol Buffers๐ฑProtocol Buffers is a schema-driven binary format in which every field has a permanent number. On the wire each field is a tag (field number plus wire type) and a value, so parsers can skip fields they don't know, and the number, not the name, is the field's identity.
- REST๐ฑREST is an architectural style for networked APIs built on the web's own rules: resources named by URLs, a small uniform set of methods, stateless requests and cacheable responses. In practice it usually means JSON over HTTP with resource-shaped URLs.
- RPC๐ฑRPC makes a call to another process look like a local function call. The illusion is leaky: remote calls have unpredictable latency, no shared memory and partial failure, where a timeout leaves the outcome unknown.
- Schema Evolution๐ฑSchema evolution is changing a data format while old and new code, and old and new data, keep working together. The safe moves are additive: new optional fields, never a reused identifier, and old code that preserves what it doesn't understand.
- Schema Registry๐ฑA schema registry stores every version of every message schema, gives each one a compact ID that messages carry instead of the schema, and refuses new versions that break the configured compatibility mode.
- Serialization๐ฑSerialization turns in-memory data (objects, structs, pointers) into a self-contained byte sequence that can be stored or sent, and deserialization turns it back. The format you pick decides who can read the bytes, how big they are, and how safely the data can change.
- Workflow Orchestration๐ฑWorkflow orchestration puts one component in charge of a multi-service process: it calls each step, tracks state, retries and compensates. Its alternative, choreography, lets services react to each other's events with no central owner.
foundationstopic map
- Accidental Complexity๐ฑAccidental complexity is complexity that isn't inherent in the problem users need solved but comes from our tools, structure and choices. Removing it, mainly with good abstractions, is how systems stay understandable.
- Algorithmic Bias๐ฑAlgorithmic bias is systematically worse outcomes for some groups from an automated system, usually learned from biased historical labels, proxies for sensitive attributes, or a target that measures the wrong thing, and then applied consistently at scale.
- Backpressure๐ฑBackpressure is a consumer signalling its producer to slow down when it can't keep up, so work waits upstream instead of piling up in an unbounded buffer. It loses nothing, but only works if the producer can afford to wait.
- Blameless Postmortem๐ฑA blameless postmortem is a written review of an incident that looks for contributing causes in systems and processes rather than individuals, and produces tracked action items. It asks "how did the system allow this?", not "who did it?"
- Bulkhead๐ฑA bulkhead partitions resources (threads, connections, servers, whole cells) so that one overloaded dependency or tenant can exhaust only its own share, not everything. It limits blast radius rather than preventing the fault.
- Cache Eviction Policy๐ฑWhen a cache is full, its eviction policy decides what to throw out, betting on which keys won't be needed soon. Modern policies add admission control, so a key must prove it's reused before it can displace established ones.
- Cache Invalidation๐ฑInvalidation is how a cache learns its copy is out of date: expire it after a TTL, delete it when the source changes, or derive deletes from the source's change log. Races mean you need a TTL as the backstop.
- Cache Stampede๐ฑWhen a hot key expires or the cache empties, every concurrent reader misses at once and recomputes the same value, flooding the backend. If those recomputations time out, nobody refills the cache and the overload sustains itself.
- Cache-Aside๐ฑThe application owns the cache: on a read it checks the cache, falls back to the database on a miss and fills the cache. On a write it updates the database and deletes the cached key.
- Caching๐ฑA cache keeps a copy of a result somewhere cheaper to read than its source, so repeat reads skip the expensive work. Its value is set by the hit ratio, and its danger is that the system comes to depend on it.
- Canary Release๐ฑA canary release deploys a change to a small, time-limited slice of production and evaluates it against a control before rolling out further, so a bad change hurts a few users instead of all of them.
- Cascading Failure๐ฑA cascading failure is one where a failure in one component raises the load on, or starves, the components around it, so they fail too, and the failure spreads through the system faster than it can be contained.
- Chaos Engineering๐ฑDeliberately inject faults into production (kill instances, cut links) while the team is ready, so recovery paths are exercised continuously instead of failing for the first time in a real outage.
- Circuit Breaker๐ฑA circuit breaker wraps calls to a dependency and, once failures cross a threshold, trips open so later calls fail instantly without being sent. After a cool-down it lets a trial call through (half-open) and closes again if it succeeds.
- Cloud vs Self-Hosting๐ฑRunning infrastructure yourself trades a lower unit cost and more control for fixed capacity and owning the operations; renting it from a cloud provider trades a higher unit cost and less control for elasticity, speed and managed services. Load shape and operational skill decide which wins.
- Content Delivery Network๐ฑA CDN is a globally distributed HTTP cache whose edge servers near users answer repeat requests, so the origin and the long network path are skipped. HTTP headers control what it stores and for how long.
- Crypto-Shredding๐ฑCrypto-shredding erases data by destroying keys instead of data: each subject's records are encrypted with their own key, and deleting that key makes every copy (log, replicas, backups) unreadable without rewriting anything.
- Data Ethics๐ฑData ethics is the practice of deciding what data about people a system collects, keeps, infers and acts on, and who could be harmed by it. Most of those decisions are made by engineers in schemas, logs, retention settings and training sets, often without noticing they are decisions.
- Data Minimization๐ฑData minimization means collecting and keeping only the personal data a specific purpose needs, in the least identifying form that serves it. Data you never stored can't be breached, subpoenaed, repurposed or sold.
- Data Retention๐ฑData retention is deciding, per dataset, how long personal data is kept and enforcing deletion when that period ends. Data that has served its purpose isn't harmless; it is pure risk, and the retention limit caps what any breach can take.
- Evolvability๐ฑEvolvability is how easily a system can be adapted as requirements change. It comes from simplicity, small compatible steps and reversible decisions.
- Fan-Out on Write๐ฑFan-out on write does the work of assembling a feed when a post is written, copying it into every follower's precomputed timeline, so reads become a single lookup. It trades cheap reads for writes amplified by the follower count.
- Fault Tolerance๐ฑA fault is one component deviating from its spec. A failure is the whole system no longer serving users. Fault tolerance is designing so faults don't become failures.
- Hardware Fault๐ฑDisks, RAM, power supplies and cables fail. Each one is rare, but across a fleet they're a steady background rate. Hardware faults are mostly random and independent, which is why redundancy works against them.
- Health Check๐ฑA health check decides whether a backend should get traffic right now. Active checks probe an endpoint on a timer. Passive checks (outlier detection) watch real responses. Both need guardrails so a correlated failure doesn't empty the pool.
- Horizontal Scaling๐ฑHorizontal scaling adds capacity by spreading load across more machines, each with its own CPU, memory and disk, coordinating over the network (shared-nothing). It has no hard ceiling, but for stateful systems it requires splitting the data.
- Human Error๐ฑOperators are the leading cause of outages, mostly through configuration mistakes. You can't make humans perfect, but you can make the system forgiving: hard to get wrong, quick to undo, limited in blast radius.
- L4 vs L7 Load Balancing๐ฑAn L4 balancer routes connections using addresses and ports, without reading the payload. An L7 balancer is a proxy that reads each HTTP/gRPC request and routes each one separately. L4 is fast and generic; L7 is smart and costly.
- Latency Percentiles๐ฑResponse time is a distribution, so describe it with percentiles: p50 for the typical request, p95/p99/p99.9 for the tail. The mean is pulled up by outliers and describes no actual user.
- Little's Law๐ฑIn a stable system, the average number of requests in flight equals arrival rate times average time in the system: L = ฮปW. It turns throughput and latency into the concurrency (threads, connections, workers) you need.
- Load Balancer๐ฑA load balancer puts one stable address in front of a pool of interchangeable backends and decides, per request or per connection, which healthy backend gets it. It spreads load, routes around failures and hides changes to the pool.
- Load Balancing Algorithms๐ฑThe rule a load balancer uses to pick a backend: rotation, load-aware choice, randomness or hashing. Each one trades how even the load is against how much state and how fresh a load signal it needs.
- Load Parameters๐ฑLoad parameters are the few numbers that determine how much work a system does, such as requests per second, read/write ratio or followers per account. Which ones matter depends on the architecture, and often the one that matters is the shape of a distribution, not a total.
- Load Shedding๐ฑLoad shedding is a server deliberately rejecting excess work, early and cheaply, so it can spend its capacity on requests it can actually finish. It keeps goodput (useful, timely responses) near capacity instead of letting it collapse.
- Maintainability๐ฑMaintainability is how easy a system is to keep running, understand and change over its lifetime. Most of software's cost comes after launch, so it rests on three principles: [[Operability]], simplicity (removing [[Accidental Complexity]]) and [[Evolvability]].
- Metastable Failure๐ฑA metastable failure is a bad state that a temporary trigger pushes a system into and that persists after the trigger is gone, because a feedback loop in the system (the sustaining effect, usually retries) keeps load above capacity.
- Observability๐ฑObservability is the ability to understand what a system is doing, and answer questions you didn't anticipate, from its external outputs, without shipping new code. Monitoring answers known questions; observability handles unknown ones.
- Operability๐ฑOperability is how easy a system makes it for the people running it to keep it healthy: routine tasks are easy and automated, unusual ones are possible, and behaviour is visible and predictable.
- Power of Two Choices๐ฑPick two backends at random and send the request to the less loaded one. That one extra sample shrinks the worst server's load exponentially compared with a single random pick, and it doesn't herd when load data is stale.
- Privacy by Design๐ฑPrivacy by design means building data protection into a system's architecture from the first design rather than bolting it on later; privacy by default means the out-of-the-box setting processes only the data each purpose needs, with sharing opt-in.
- Rate Limiting๐ฑRate limiting caps how much any one caller (user, API key, tenant) may send per unit of time, rejecting the excess with `429 Too Many Requests`. It protects shared capacity from one client, where load shedding protects a server from total load.
- Redundancy๐ฑKeep spare copies of a component (a disk, a power supply, a whole machine) so that when one dies, another takes over. It works against independent faults only.
- Reliability๐ฑA system is reliable if it keeps working correctly (right results, acceptable performance, secure) even when things go wrong. Things will go wrong; reliability is about containing them.
- Retry with Backoff๐ฑRetrying hides transient faults, but every retry is extra load that arrives exactly when a dependency is struggling. Safe retries wait exponentially longer with random jitter, happen at one layer, and stay within a budget.
- Right to Erasure๐ฑThe right to erasure lets people have their personal data deleted without undue delay when it's no longer needed or they withdraw consent. For engineers it is a distributed-systems problem: the data has been copied into many stores, and every copy must go.
- Rolling Upgrade๐ฑA rolling upgrade replaces a fleet's nodes one (or a few) at a time, so the service never goes down. For its duration old and new versions run side by side, so they must be compatible in both directions.
- Scalability๐ฑScalability is a system's ability to cope with increased load. It isn't a yes/no property: it only means something once you say which load grows, by how much, and what performance you need to keep.
- Service Discovery๐ฑService discovery keeps a live registry of which instances of each service exist and where, so balancers and clients always have a current pool. In dynamic environments it becomes the dependency everything depends on.
- Single Point of Failure๐ฑA single point of failure is any component whose failure alone takes the whole system down. Removing them means [[Redundancy]] at every layer, including the layers that provide redundancy, like load balancers and discovery.
- Software Fault๐ฑSoftware faults are systematic: the same bug is in every copy of the code, so one trigger hits every replica at once. Correlated faults defeat redundancy, which makes them more dangerous than hardware faults.
- Tail Latency Amplification๐ฑWhen one user request fans out to many servers and waits for all of them, the slowest one sets the response time, so rare per-server slowness becomes common user-facing slowness. With 100 servers each slow 1% of the time, about 63% of requests are slow.
- Timeout๐ฑA timeout bounds how long a caller waits for a remote call before treating it as failed. A deadline is the same budget set once at the edge and propagated, so every hop gives up when the original caller does.
- Vertical Scaling๐ฑVertical scaling adds capacity by moving to a more powerful machine: more CPUs, RAM and faster disks under one operating system. It keeps everything in one address space, so there are no distributed-systems problems, until you hit the biggest machine you can buy.
- Write-Back Cache๐ฑThe cache acknowledges a write as soon as it holds it, marks it dirty, and flushes to the backing store later, often in batches. Fast writes, but acknowledged data is lost if the cache dies first.
- Write-Through Cache๐ฑEvery write goes to the cache and the backing store together, and is acknowledged only once the store has it. The cache is never behind, at the cost of write latency.
replicationtopic map
- Anti-Entropy๐ฑA background process that compares replicas and copies over whatever is missing. Merkle trees of hashes make the comparison cheap: descend only into subtrees whose hashes differ.
- Consistent Prefix Reads๐ฑIf writes happen in some order, readers see them in that order: a prefix of history, never history with gaps. It breaks when causally related writes live in different partitions.
- CRDT๐ฑA data type whose replicas can be updated independently and always merge to the same result, because its merge is commutative, associative and idempotent. Conflicts are resolved by construction, not by application code.
- Failover๐ฑPromoting a follower to leader when the leader fails, and pointing clients and other followers at it. Every step (detecting, choosing, reconfiguring) has a failure mode.
- Last Write Wins๐ฑResolve conflicting versions by keeping the one with the highest timestamp. It always converges, and it silently discards every other concurrent write.
- Leader-Based Replication๐ฑOne replica, the leader, accepts every write and streams its [[Replication Log]] to followers, which apply it in the same order. Reads can go anywhere; writes go only to the leader.
- Leaderless Replication๐ฑNo replica is special: writes and reads go to all n replicas of a key in parallel and succeed once w (or r) respond. Stale replicas are fixed later by read repair and anti-entropy, not by a log.
- Monotonic Reads๐ฑA session guarantee: once you've seen some state, you never later see an older one. Stale is allowed; going backwards isn't.
- Multi-Leader Replication๐ฑSeveral nodes, typically one per region or per device, each accept writes and asynchronously forward them to the others. Writes are local and survive outages, at the cost of [[Write Conflict]]s.
- Quorum๐ฑWith n replicas, require w acknowledgements per write and r responses per read. If w + r > n, every read set overlaps every write set in at least one replica, so some reply carries the latest successful write.
- Read Repair๐ฑWhen a read sees replicas disagree, write the newest version back to the stale ones. It repairs frequently read data for free, and never touches data nobody reads.
- Read-Your-Writes Consistency๐ฑA session guarantee: after you write something, your later reads always reflect it. It promises nothing about other users' writes.
- Replication Lag๐ฑHow far an asynchronous follower trails the leader's log. Usually milliseconds, unboundedly more under load, and the source of stale reads that look like bugs.
- Replication Log๐ฑThe ordered stream of changes a leader sends to its followers. What it records (SQL statements, storage-engine bytes, or row changes) decides how fragile replication is and whether replicas can run different versions.
- Sloppy Quorum๐ฑWhen a key's home replicas are unreachable, accept the write on other healthy nodes, which keep it with a hint naming the intended owner and hand it off later. Writes stay available; quorum overlap is gone until handoff.
- Split Brain๐ฑTwo nodes both acting as leader and accepting writes, so their histories diverge and can't be merged automatically. It happens when an old leader is cut off rather than dead.
- Synchronous vs Asynchronous Replication๐ฑWhether the leader waits for followers before telling the client a write succeeded. Synchronous buys durability with latency and availability; asynchronous buys speed with the risk of losing acknowledged writes.
- Version Vector๐ฑOne counter per replica attached to each key's value. Comparing two version vectors tells you whether one write overwrote the other or whether they were concurrent and both must be kept.
- Write Conflict๐ฑTwo replicas accept different writes to the same data without either seeing the other's. Every replica must then converge on one outcome, and someone has to decide which.
storagetopic map
- Approximate Nearest Neighbor๐ฑA vector index that returns most of the true nearest neighbours for a tiny fraction of the work of a full scan. Every design exposes a dial that trades recall for speed and memory.
- B-Tree๐ฑA balanced tree of fixed-size pages that keeps keys sorted and updates them in place: a lookup follows one page per level from root to leaf. High fanout keeps it shallow, and page splits keep every leaf at the same depth.
- Bloom Filter๐ฑA compact bit array plus k hash functions that answers "is this key in the set?" with definitely not or maybe. It has false positives but never false negatives, so a "no" safely skips work.
- Clustered Index๐ฑA table stored inside its primary-key [[B-Tree]], with full rows in the leaves, so the rows are physically ordered by key. Its alternative is a heap table, where rows sit unordered and every index, primary key included, points at a physical location.
- Column-Oriented Storage๐ฑStore each column of a table contiguously instead of each row, all in the same row order. Scans read only the columns a query needs, compress far better, and can skip blocks by their min/max statistics.
- Columnar Compression๐ฑLightweight encodings that exploit a column holding one type with few distinct values and long repeats: dictionary codes, bit-packing, run-length and delta encoding, often with LZ4 or Zstandard on top. Fewer bytes means faster scans, and engines can filter on the encoded form directly.
- Compaction๐ฑThe background process in an [[LSM-Tree]] that merge-sorts [[SSTable]]s into new ones, keeping only the newest version of each key and dropping tombstones. The strategy for which files to merge sets the balance between write, read and space amplification.
- Data Lakehouse๐ฑWarehouse features (ACID commits, snapshots, schema enforcement) on top of open columnar files in cheap object storage, via a table format such as Iceberg, Delta Lake or Hudi. One copy of the data, readable by many engines.
- Data Warehouse๐ฑA separate database holding read-mostly, historical copies of data from many operational systems, organised for analysis. Data arrives by ETL (transform, then load) or ELT (load raw, transform inside the warehouse).
- Full-Text Search๐ฑFinding documents that contain the words of a query, then ranking them by relevance. It is built on an [[Inverted Index]] plus a scoring function, BM25 by default in Lucene-based engines.
- Inverted Index๐ฑAn index from each term to the sorted list of documents containing it (its postings list). It turns "which documents contain these words?" into a few dictionary lookups and list intersections.
- LSM-Tree๐ฑA storage engine that never updates data in place: writes go to an in-memory [[Memtable]], which is flushed as sorted, immutable [[SSTable]]s that background [[Compaction]] merges. It trades extra background work and read effort for very cheap, sequential writes.
- Memtable๐ฑThe in-memory, sorted buffer at the top of an [[LSM-Tree]] where every write lands first. When it fills, it is frozen and flushed to disk as one sorted, immutable [[SSTable]].
- OLTP vs OLAP๐ฑOLTP serves many small, latency-sensitive requests that each touch a few whole rows by key. OLAP runs few, large queries that scan millions of rows but only a few columns, and the two want opposite physical layouts.
- Secondary Index๐ฑAn extra index, beyond the primary key, that finds rows by some other column or combination of columns. It is a sorted copy of those values with a reference back to each row, so it speeds the reads it matches and slows every write.
- SSTable๐ฑAn immutable file of key-value pairs sorted by key, split into blocks, with an index of where each block starts. It is the on-disk unit of an [[LSM-Tree]]: written once in one sequential pass, never modified, eventually merged away by [[Compaction]].
- Star Schema๐ฑA warehouse schema with one huge fact table of events at a fixed grain in the centre, holding foreign keys and numeric measures, surrounded by small, descriptive dimension tables. Normalising the dimensions further gives a snowflake schema.
- Vector Search๐ฑSearch by meaning: items and queries are mapped to [[Embedding]] vectors, and the answer is the k vectors nearest the query. Exact search is a full scan, so production systems use an [[Approximate Nearest Neighbor]] index.
- Write Amplification๐ฑThe ratio of bytes a storage engine writes to disk to bytes the application asked it to write. Together with read and space amplification it forms the triangle every storage engine trades along: improving one usually worsens another.
- Write-Ahead Log๐ฑAn append-only file where a storage engine records every change, forcing it to disk before the changed data reaches disk and before the commit is acknowledged. After a crash, replaying the log restores every acknowledged write.
distributed
- Byzantine Fault๐ฑA fault where a node behaves arbitrarily, including sending false or contradictory messages. Tolerating f such nodes needs at least 3f + 1 nodes, so most data-centre systems assume nodes are honest and only crash.
- CAP Theorem๐ฑWhen a network partition happens, a replicated system must give up either linearizability or availability (every request to a non-failing node gets a response). It says nothing about the system when there is no partition.
- Causal Consistency๐ฑIf one operation could have influenced another, every replica shows them in that order; concurrent operations may appear in different orders. It is about the strongest model that stays available during a partition.
- Clock Skew๐ฑDifferent machines' clocks disagree (skew) and wander (drift), and the time-of-day clock can jump, even backwards. A timestamp is a range, not a point, so wall-clock times are unsafe for ordering events across machines.
- Consensus๐ฑGetting a group of nodes to agree on one value (or one log, entry by entry) even though some may crash and the network may delay messages. Safety always holds; progress needs a majority up and a network that's usually timely.
- Consistency Model๐ฑThe contract that says which results a read may return while replicas disagree. It's a safety property over histories (who issued what, and what they got back), so it can be tested by recording a history and checking it.
- Coordination Service๐ฑA small, consensus-replicated store (usually 3 or 5 nodes) holding the little data a fleet must agree on: who leads, current configuration, membership, locks. Applications use it instead of implementing consensus themselves.
- Eventual Consistency๐ฑIf writes stop, all replicas eventually return the same value. A liveness promise only: it says nothing about what reads return before then, or how long "eventually" is.
- Failure Detection๐ฑDeciding that a remote node has failed from the absence of messages. Every detector trades detection speed against false suspicions, because over an asynchronous network a slow node and a dead one look identical.
- Fencing Token๐ฑA number that strictly increases with every grant of a lock or lease, sent with each write so the resource can reject writes from any holder older than the newest it has seen.
- FLP Impossibility๐ฑIn a fully asynchronous system, no deterministic algorithm can guarantee that consensus terminates if even one process may crash. Practical algorithms keep safety unconditionally and get liveness from timeouts or randomness.
- Gossip Protocol๐ฑEach node periodically shares what it knows with a few random peers, who pass it on, so information reaches all n nodes in O(log n) rounds at constant load per node. SWIM uses it to spread membership and failure news.
- Happens-Before๐ฑEvent a happens before b (a โ b) if a precedes b on the same process, a is the send of a message b receives, or a chain of those links them. If neither a โ b nor b โ a, the events are concurrent: neither could have influenced the other.
- Hybrid Logical Clock๐ฑA timestamp (l, c) where l is the largest physical time a node has seen and c is a counter for events sharing that l. It respects causality like a Lamport clock and stays within the clock skew of physical time.
- Lamport Clock๐ฑOne integer counter per process, incremented before each event and carried on every message; a receiver jumps to max(own, received) + 1. If a happened before b then L(a) < L(b), but not the reverse.
- Leader Election๐ฑChoosing exactly one node to lead, such that every node agrees and two leaders can never act in the same term. Done properly it is consensus: a majority vote per numbered term.
- Lease๐ฑA grant that expires after a fixed time unless renewed. It lets a leader act alone (serve reads locally, hold a lock) for a bounded window, and lets everyone else take over safely once the window has passed.
- Linearizability๐ฑThe system behaves as if there were one copy of the data, and every operation takes effect atomically at some instant between its request and its reply. If A completes before B starts, B sees A.
- Network Partition๐ฑA network fault that cuts some nodes off from others while all of them keep running. To each side, the other side looks crashed, so a system must ensure at most one side keeps making decisions.
- PACELC๐ฑIf there's a Partition, choose Availability or Consistency; Else, choose Latency or Consistency. It adds the trade-off CAP ignores, the one you pay on every request when nothing is broken.
- Partial Failure๐ฑIn a distributed system some parts can be broken while others work, unpredictably, and a node often can't tell which. One computer either works or crashes; many computers on a network fail partially and nondeterministically.
- Paxos๐ฑA consensus algorithm in which a proposer gets promises from a majority of acceptors (phase 1), then asks them to accept a value (phase 2), adopting any value already accepted. Multi-Paxos keeps a stable leader so phase 1 runs once for a whole log.
- Process Pause๐ฑA running thread can be stopped at any instruction for seconds or minutes without knowing it, while the rest of the system moves on. Any "check, then act" based on time is unsafe across such a pause.
- Raft๐ฑA leader-based consensus algorithm designed for understandability: elect one leader per term by majority vote, have it replicate a log, and commit entries once a majority stores them. Equivalent to Multi-Paxos in fault tolerance and performance.
- Sequential Consistency๐ฑThe result is as if all operations ran in one total order that every client agrees on, with each client's operations in the order it issued them. Unlike linearizability, that order may lag behind real time.
- Total Order Broadcast๐ฑA protocol that delivers every message to every node, in the same order on all of them. Feed deterministic replicas the same ordered log and they stay identical; keeping that order through leader failures is equivalent to consensus.
- TrueTime๐ฑA clock API that returns an interval [earliest, latest] guaranteed to contain true time. By waiting out the interval's width at commit, a database makes timestamp order match real-time order everywhere.
- Unique ID Generation๐ฑSchemes for issuing IDs that never collide, trading coordination against order. Time-first layouts (Snowflake, UUIDv7) give uncoordinated, roughly time-sorted IDs whose order is only as good as clock sync.
- Unreliable Network๐ฑData-centre and internet networks are asynchronous packet networks: a message may be lost, delayed without bound, duplicated or reordered, and the sender can't tell a lost request from a dead or slow receiver or a lost reply.
- Vector Clock๐ฑEach process keeps a vector of counters, one per process, merged element-wise on receipt. Comparing two vectors entry by entry tells you exactly whether one event happened before the other or they were concurrent.
stream
- Change Data Capture๐ฑRead a database's own replication log and publish every committed row change, in commit order, as a stream. Downstream stores then follow the database the way a replica does, with no dual writes.
- Consumer Group๐ฑConsumers sharing a group ID split a topic's partitions so that each partition has exactly one owner in the group. A rebalance reassigns partitions as members join, leave or die, and how it's done decides whether the whole group pauses.
- Consumer Offset๐ฑA log consumer's entire progress is one number per partition: the offset of the next record to read. The committed offset is the saved copy a restart resumes from, and where you commit it relative to your side effects decides the delivery guarantee.
- CQRS๐ฑUse one model to change data (commands) and a different model, or several, to read it (queries). The read models are derived asynchronously from the write side, each shaped for the screen or API that queries it.
- Dead Letter Queue๐ฑA side queue where messages go after a bounded number of failed attempts, so one message that can never succeed (a poison message) stops blocking or burning the stream. It only helps if someone is alerted and redrives the messages after a fix.
- Delivery Semantics๐ฑBecause any step can fail between "received" and "acknowledged", a message is delivered at-most-once (may be lost), at-least-once (may be duplicated) or effectively exactly-once (duplicates are made harmless). At-least-once with idempotent consumers is the industry default.
- Derived Data๐ฑData computed from a [[System of Record]] by some transformation: caches, indexes, materialized views, replicas, aggregates, models. It's redundant by design, and if it's lost you can rebuild it from the source.
- End-to-End Argument๐ฑA function like duplicate suppression or integrity checking can only be implemented completely by the application at the endpoints. Reliability in lower layers is a performance optimisation that makes failures rarer; it never replaces the end-to-end check.
- Event Sourcing๐ฑStore every change to application state as an immutable, past-tense event in an append-only log, and derive current state by replaying the events. The log is the system of record; tables are views of it.
- Event Time vs Processing Time๐ฑEvent time is when something happened; processing time is when the stream processor sees it. The gap between them (skew) is never zero and never constant, so results about the world must be computed in event time to be correct and reproducible.
- Exactly-Once Semantics๐ฑRecords may be delivered and processed more than once, but the effect on state and output is as if each were processed once. It needs the progress marker (offsets, checkpoint) and the effect to commit atomically, or the effect to be idempotent.
- Integrity vs Timeliness๐ฑ"Consistency" bundles two properties: timeliness (readers see up-to-date state; violations heal by themselves) and integrity (nothing lost, duplicated or contradictory; violations are permanent). Log-based systems can guarantee integrity while relaxing timeliness, without distributed transactions.
- Kappa Architecture๐ฑOne stream processing codebase over a log retained long enough to replay. To change the logic, run a second version of the job from the start of the log into a new table, switch readers when it catches up, then delete the old one.
- Lambda Architecture๐ฑKeep all raw events immutable and recompute views from scratch in a batch layer, while a separate speed layer processes recent events in real time; queries merge the two. It trades a second codebase for recoverability and low latency.
- Log Compaction๐ฑRetention by key instead of by age: the broker keeps at least the latest record for every key and discards older ones, so replaying the topic from offset 0 always rebuilds the current table. A null-valued tombstone deletes a key.
- Log-Based Message Broker๐ฑA broker that stores messages as an append-only, ordered, partitioned log and keeps them until retention removes them, whether or not anyone has read them. Consumers are just positions in the log, so reading is cheap, fan-out is free and history can be replayed.
- Materialized View๐ฑThe stored result of a query over a source, kept up to date as the source changes, so reads become lookups. The design question is how it's kept current: full recomputation or incremental maintenance from deltas.
- Message Broker๐ฑA server that durably stores messages between producers and consumers, so neither has to be up, fast or even known to the other. It trades a synchronous answer for decoupled availability, buffering and fan-out.
- Stateful Stream Processing๐ฑStream operators keep local, key-partitioned state (counts, windows, join buffers) and make it fault-tolerant by periodically snapshotting it together with the input offsets it corresponds to. Recovery restores both and replays from there, so each record affects state exactly once.
- Stream Join๐ฑA streaming join must remember one side until the matching record from the other side arrives, so its cost is state. Time bounds (an interval, a window, a versioned table) tell it when it may forget; without them, state grows forever.
- System of Record๐ฑThe store that holds the authoritative version of some data: new facts are written there first, and if any other copy disagrees, the system of record wins.
- Unbundling the Database๐ฑA database already derives tables, indexes, views, caches and replicas from its own log. Unbundling pulls that log out into a shared system and builds each derived structure as a separate, specialised store kept current by stream processors.
- Watermark๐ฑA watermark is a timestamp flowing through a streaming job that asserts "no more events older than this are expected". Windows fire when it passes their end. It's a heuristic: too eager produces late data, too cautious adds latency.
- Windowing๐ฑWindows slice an unbounded stream into finite, per-key groups by event time, so aggregates and joins can finish. The window shape (tumbling, hopping, session) decides how many results you get, how much state you hold, and when a result can be emitted.
partitioningtopic map
- Consistent Hashing๐ฑA way to map hashed keys to nodes so that adding or removing one of N nodes moves only about 1/N of the keys, instead of nearly all of them as with `hash mod N`.
- Hash Partitioning๐ฑPlace each record by a hash of its key rather than the key itself, so consecutive keys scatter evenly across shards. Writes spread out; range scans over the original key now hit every shard.
- Hot Spot๐ฑA shard that gets far more than its share of traffic, usually because one key (or one key range) is far more popular than the rest. Hashing spreads keys, not load, so it can't fix a single hot key.
- Local vs Global Secondary Index๐ฑIn a sharded database a [[Secondary Index]] is either local (each shard indexes its own rows, so queries ask every shard) or global (the index is partitioned by the indexed value, so reads hit one partition but writes touch several).
- Range Partitioning๐ฑSort the keys and give each shard a contiguous range of them, with boundaries chosen so each range holds a similar amount of data. Range scans stay on one shard; monotonic keys pile onto the last one.
- Rebalancing๐ฑMoving data between nodes as data, load or the node count changes, so that load ends up fair, the database keeps serving during the move, and no more data moves than necessary.
- Request Routing๐ฑHow a request finds the node that currently owns its key. The map from keys to nodes changes during rebalancing, so the hard part is keeping one authoritative copy and making stale copies harmless.
batch
- Data Skew๐ฑWhen one key (or a few) has far more rows than the rest, hash partitioning sends all of them to one task, and the whole stage waits for it. The batch-processing form of a [[Hot Spot]].
- Dataflow Engine๐ฑA batch engine that runs a whole multi-step pipeline as one graph of operators, fusing steps, keeping intermediates in memory or on local disk, and recovering lost data by recomputing it from its lineage instead of replicating it.
- DataFrame๐ฑA table of named, typed columns with relational operations (select, filter, join, group-by) as a library API. Eager DataFrames run each call immediately; lazy ones build a plan and optimise it like a SQL query before running anything.
- Join Strategies๐ฑWays to bring matching rows of two distributed datasets together: shuffle both sides by key (sort-merge or shuffle hash), copy the small side everywhere (broadcast hash), or pre-partition both identically (bucketing). The cost that matters is what crosses the network.
- MapReduce๐ฑA batch programming model where you write map (record โ key-value pairs) and reduce (key, all its values โ output), and the framework handles partitioning, the shuffle, scheduling and failures across thousands of machines.
- Shuffle๐ฑThe distributed sort between map and reduce: every mapper partitions its output by key into one bucket per reducer, and every reducer fetches its bucket from every mapper, so all values for a key meet on one machine.
- Unix Philosophy๐ฑBuild small programs that each do one thing well and communicate through one uniform interface (streams of text), so they can be composed into jobs nobody designed them for. Distributed batch systems inherited the design.
data models
- Declarative Query Language๐ฑA declarative query describes the result you want, not the steps to compute it, and the engine's optimizer chooses the plan. That indirection lets plans change with data, indexes and hardware while the query stays the same.
- Document Model๐ฑEach record is a self-contained tree (usually JSON) that holds its one-to-many children inline. You get locality and a close match to application objects, and pay for it whenever data is shared across documents.
- Graph Model๐ฑData is vertices joined by typed edges, and both can carry properties. It is the natural model when many-to-many relationships are the point of the data and queries follow paths of unknown length.
- Normalization๐ฑStore each fact in exactly one place and refer to it by a meaningless ID. Changes then touch one row and copies can't disagree; the price is joins on read.
- Object-Relational Mismatch๐ฑApplication code holds nested object graphs; relational databases hold flat rows. The translation layer between them, usually an ORM, saves boilerplate but leaks, most famously as the N+1 query problem.
- Relational Model๐ฑData lives in relations (tables of rows), and queries select rows by value, never by following stored pointers. Because the database, not the program, chooses access paths, layouts and indexes can change without rewriting a single query.
- Schema-on-Read๐ฑThere is always a schema; the question is when it's enforced. Schema-on-write checks every write against a declared schema, while schema-on-read accepts any structure and leaves interpreting it to the code that reads.
Systems
- Apache FlinkA distributed engine for stateful computation over unbounded streams, in event time. Its defining choice is local keyed state made fault-tolerant by asynchronous barrier snapshots, which gives exactly-once state and, with transactional sinks, exactly-once output.
- Apache KafkaA distributed, partitioned, replicated commit log, built at LinkedIn (2011). Records stay after they are read, and consumers are just offsets, which makes replay, fan-out and stream processing cheap.
- Apache ParquetAn open columnar file format, announced by Twitter and Cloudera in 2013, that nearly every analytics engine reads and writes. Its defining choice is a footer with the schema, chunk offsets and statistics, written after the data, so readers fetch only what a query needs.
- Apache SparkThe dominant open-source distributed batch engine, born at UC Berkeley's AMPLab. Its defining choice is the resilient distributed dataset: intermediate data kept in memory or local disk and rebuilt from lineage on failure, not replicated.
- CassandraA wide-column database descended from Dynamo's design: leaderless replication with per-query tunable consistency and last-write-wins per cell.
- Chaos MonkeyNetflix's tool that randomly terminates production instances during working hours, forcing every service to tolerate instance loss.
- ClickHouseAn open-source column-oriented OLAP database, built at Yandex for web analytics and open-sourced in 2016. Its defining choice is the MergeTree engine: sorted, immutable parts merged in the background, with a sparse index over granules of up to 8,192 rows.
- CockroachDBA distributed SQL database (Postgres wire protocol) that defaults to serializable transactions across ranges replicated with Raft, using MVCC with hybrid-logical-clock timestamps.
- DebeziumThe standard open-source change data capture platform: connectors that read database logs (WAL, binlog, oplog, redo log) and emit every row change as an ordered event, usually into Kafka. Its defining choice is log-based capture with a snapshot-then-stream bootstrap.
- DynamoAmazon's internal key-value store (2007), built to be "always writeable" for services like the shopping cart. Not the same system as the DynamoDB cloud service.
- DynamoDBAWS's managed key-value and document database (2012). Tables are hash-partitioned by a partition key into partitions with hard per-partition throughput limits, which the service splits and moves automatically. Despite the name, it shares little of [[Dynamo]]'s architecture.
- ElasticsearchA distributed search and analytics engine built on Apache Lucene. Its defining choice is Lucene's: an index is a set of immutable segments, each a complete [[Inverted Index]], made searchable by periodic refreshes and merged in the background.
- EnvoyA high-performance L4/L7 proxy, originally built at Lyft, used as an edge proxy, a sidecar and the data plane of many service meshes (Istio, Consul). Its defining choice is that everything (pool, routes, listeners) is configured dynamically by a control plane over the xDS APIs.
- HadoopThe open-source implementation of Google's GFS and MapReduce, split out of the Nutch search engine in 2006 and grown up at Yahoo. Its defining choice is moving computation to where the data lives, in a replicated distributed file system.
- JepsenKyle Kingsbury's framework and series of analyses (since 2013) that test distributed databases under injected faults and check the recorded histories against the consistency models they claim.
- MemcachedA deliberately simple, multithreaded, in-memory key-value cache with no persistence, no replication and no rich types, which leaves distribution to the clients. That simplicity is why it scales to the largest cache fleets in the world.
- MongoDBThe most widely used document database: collections of BSON documents, each read and written as a unit. Its defining choice is to make the self-contained document, not the row, the unit of storage, indexing and atomicity.
- MySQLThe open-source relational database behind much of the web. Its replication is a leader (source) streaming a row-based binary log to replicas, asynchronous by default.
- Neo4jA native property-graph database queried with Cypher. Its defining choice is index-free adjacency: each node's storage leads straight to its relationships, so a traversal hops without a global index lookup.
- PostgreSQLThe open-source relational database whose concurrency model is MVCC with versions stored in the table itself, offering Read Committed by default, snapshot isolation as Repeatable Read, and true serializability via SSI.
- RabbitMQThe classic queue broker. Producers publish to exchanges that route messages into queues, and the broker pushes each message to one consumer and deletes it on ack. It tracks every message, so per-message acks, routing, TTLs and dead-lettering are first-class.
- RedisAn in-memory data-structure server (strings, hashes, lists, sets, sorted sets, streams) that runs commands on a single main thread. It's the most common shared cache tier, and it's also used as a queue, rate limiter and lock service.
- RocksDBAn embeddable LSM key-value store from Facebook, forked from Google's LevelDB, that sits underneath many other databases. Its defining choice is to make every part of the [[LSM-Tree]] pluggable and tunable.
- SpannerGoogle's globally distributed SQL database. Its defining choice is TrueTime: clocks with an explicit, small error bound, waited out at commit so that transaction timestamps match real-time order across the planet.
- TemporalAn open-source durable-execution platform, founded in 2019 on a fork of Uber's Cadence. Its defining choice is event-history replay: workflow code is re-executed against a recorded history to recover from any crash.
- VitessA sharding layer for [[MySQL]], originally built at YouTube and now a CNCF project. Applications talk to it like one MySQL database; it routes each query to the shards that own its keys.
- VoltDBAn in-memory SQL database, from the H-Store research prototype, that executes transactions serially: one single-threaded engine per partition running deterministic stored procedures, with no locks or latches.
- ZooKeeperA replicated tree of small files (znodes) for coordination, from Yahoo (2010). Writes are linearizable and ordered by its Zab broadcast protocol; reads are served locally for speed.
- etcdA Raft-replicated key-value store for coordination data, best known as Kubernetes' backing store. Every change gets a global revision number.
- gRPCGoogle's open-source RPC framework (2015), the successor to its internal Stubby. Its defining choice is Protocol Buffers over HTTP/2: typed, generated interfaces with streaming and deadlines built into every call.
- pgvectorA Postgres extension that adds vector types, distance operators and ANN indexes. Its defining choice is to keep embeddings in the same database, rows and transactions as the data they describe.