Glossary

Keys are held in sorted order across pages of a few kilobytes. A branching factor in the hundreds keeps the tree three or four levels deep for almost any dataset, and the upper levels stay cached, so a lookup costs roughly one disk read.

Inserting into a full page splits it, which touches several pages at once — the reason B-trees keep a write-ahead log despite updating in place. The default index in PostgreSQL, MySQL, SQLite and most transactional databases.

Both are required at once during a rolling deploy, because you do not control which instance handles which request.

Backward is the easy direction — the new version knows what the old one looked like. Forward is harder, because the old version must tolerate something that did not exist when it was written. The trick for remembering which is which: the adjective describes what the new code can cope with.

Each SSTable carries one. A read consults it first and skips any table that provably cannot hold the key, so a lookup for a missing key usually touches no disk at all.

False positives cost an unnecessary read. False negatives cannot happen, which is the property that makes it safe to skip on. Without them a read for an absent key must check every level before reporting absence — which is why they are not an optimisation but the thing that makes LSM point lookups viable.

Killing a random production node during working hours, on purpose. The point is not to prove the system survives — it is to be watching, with everyone awake, when it doesn’t.

The underlying claim is simple: a fault-tolerance mechanism that is never exercised does not exist. It is untested code that you believe works, which is the most expensive kind.

A query touching 3 of 40 columns reads 3 files instead of pulling whole rows through memory. Values in a column share a type and a domain, so they compress far better than a row’s mixture of types.

Sorting the table by a low-cardinality column turns bitmap encodings into long runs that collapse to almost nothing — which is why the choice of sort key is the highest-leverage decision in an analytical schema, and why column stores are mostly append-only.

The work is never avoided, only deferred to a moment the engine chooses — which is why a database can be fast for hours and then develop latency spikes when a large compaction starts competing for I/O.

The characteristic failure is sustained writes outrunning compaction: levels accumulate, reads slow, disk fills, and eventually the engine stalls writes to let it catch up. Watch pending compaction bytes rather than write latency; the second is the late warning.

A naive load generator sends a request, waits for the response, then sends the next. When the system stalls for two seconds, the generator also pauses — so the requests that would have been issued during the stall, and would have recorded terrible times, are never issued at all.

The result is a tail that can look an order of magnitude better than reality. The fix is to send on a fixed schedule regardless of outstanding responses, and to count the time a request should have been sent as part of its latency.

A 99.9% availability target permits 0.1% of requests to fail. That 0.1% is the budget. Spend it on a bad deploy and there is less left for the rest of the window.

Its usefulness is organisational as much as technical: it converts “should we ship this risky change?” from an argument about temperament into an arithmetic question about how much budget remains.

A target of 100% has no budget, which means every incident is a breach, which means the objective gets quietly ignored within a month.

A disk returning corrupt bytes is a fault. A user unable to load their invoice is a failure. Fault tolerance is the practice of breaking the causal chain between the two.

The distinction matters because it sets a reachable goal. You cannot prevent faults — hardware ages, networks partition, people are tired at 4pm on a Friday. You can prevent most faults from becoming failures.

In Protobuf and Thrift a field is encoded as its tag, its wire type, and its value. The name exists only in the schema file, for humans — so renaming a field is free, and reusing a retired tag number is catastrophic, because old records still carry the old field under that number.

The length prefix accompanying the tag is what makes forward compatibility mechanical: a reader that has never heard of tag 7 knows exactly how many bytes to skip.

Requests per second, reads per write, followers per account, rows per tenant. Which one matters is specific to the system, and picking the wrong one sends a team optimising something that was never the constraint.

The test is the doubling question: if this number doubled and nothing else changed, would the design have to change? If the answer is “no, we would add a machine,” it is not your load parameter.

State it as a distribution rather than an average. Systems fail at their peaks.

Writes go to a memtable and a write-ahead log, then out to disk in bulk as an SSTable. Reads check the memtable, then each level of SSTables, usually skipping most of them via Bloom filters.

The trade: excellent write throughput, because every disk write is sequential, paid for with read amplification and background compaction competing with live traffic. Underneath RocksDB, LevelDB, Cassandra and most time-series databases.

Derived data, with the usual consequences: every write must eventually update it, and it is stale between refreshes.

A data cube extends the idea to every combination of a few dimensions. Both make the queries they anticipated fast and do nothing for the ones they did not, which is why warehouses keep the raw data and treat cubes as a cache rather than a source of truth.

Characteristically invisible: every individual query is fast, so the slow-query log shows nothing, and the loop looks like ordinary iteration in review.

The diagnostic is queries-per-request rather than query duration. The fix is to express the whole request as one statement — a join, or an IN over collected ids — so the planner can see the shape of what you want. Adding indexes does not help; the queries were already fast, there are simply hundreds of them.

The distinction is the access pattern, not the size. A 50TB transactional database is ordinary; a 2GB query scanning every row and grouping by three dimensions is analytical.

Running both on one database works until the analytical scans start evicting the transactional working set from cache, and the checkout page gets slow whenever someone opens a dashboard. That is the moment most companies grow a second, column-oriented system.

Sort your measurements and read off the value at a position. p50 is the median, the typical request. p99 is what your unluckiest one-in-a-hundred experienced.

Percentiles are reported instead of means because response-time distributions are right-skewed: a handful of very slow requests move the mean a long way while changing nothing about what most users saw.

They do not add up. The p95 of a request that calls two services is not the sum of each service’s p95, because those are usually different requests. To get a percentile for a composite, measure the composite.

Because edges are stored adjacent to their vertices, following one is a pointer hop rather than an index lookup — so traversal cost depends on how many edges a vertex has, not on how large the graph is.

Reach for it when the number of steps is part of the answer: transitive dependency analysis, fraud rings, permissions flowing through nested groups. Having relationships is not the trigger, since every model has those. Variable traversal depth is.

It re-decides on every execution using current statistics, which is why adding an index makes existing queries faster with no code change — and why a query unchanged for a year can suddenly become 40× slower when the data distribution shifts enough to flip the chosen plan.

That is the price of declarative execution. You gave up direct control in exchange for the system improving underneath you, and occasionally it changes its mind in a direction you did not want.

The safe changes are adding an optional field and removing an optional one. Everything else — adding a required field, removing a required one, renaming, changing a type — breaks at least one direction and needs a three-step rollout: ship code that tolerates both shapes, migrate the data, then ship code that assumes the new shape.

The middle step is the one people skip, and skipping it is the most common broken deploy in the industry.

A usable SLO names four things: the percentile, the threshold, where the measurement is taken, and over what window.

99% of GET /orders responses complete within 800ms, measured at the edge load balancer, over a rolling 28-day window.

Drop any clause and it stops being checkable. “Fast page loads” is a sentiment; this is a claim someone can be wrong about.

Sorting buys three things at once: the index can hold one entry every few kilobytes instead of one per key, range scans become a seek followed by sequential reading, and merging several tables is the merge step of merge sort — streaming, with no need to hold a file in memory.

Immutability is what makes background compaction safe. Nothing rewrites a table; a new one is produced beside it and swapped in.

Reads that hit a tombstone report the key as absent. Compaction eventually discards the tombstone along with every older record for that key.

The dangerous part is when. Drop a tombstone while an older segment still holds a value, and the next read finds that value — the deleted record comes back to life. “Deleted data reappears” is a real and famous class of bug in log-structured stores.

A B-tree writes the page plus a write-ahead log entry, plus occasional splits — roughly 2-3×, and it does not grow with data size. An LSM-tree rewrites each record once per compaction level it passes through, so its amplification grows with the number of levels.

One of three amplifications that decide between storage engines, alongside read amplification (disk reads per lookup) and space amplification (bytes stored per byte of live data). No engine minimises all three.