Glossary

209 terms, in the sense this mechanism uses them. The platform glossary has every term across all mechanisms.

Adaptive node types (ART): Trie nodes that use 4, 16, 48 or 256 child slots depending on how many children actually exist.
Amplification: Extra bytes read, written or stored compared with what was logically needed.If you ask for 200 bytes and the system must move 4,096 bytes, the amplification is about 20. Read amplification means extra bytes read. Write amplification means extra bytes written. Space amplification means extra bytes stored. It is the hidden cost behind most slow systems.
AMS sketch: A small sketch that estimates the second frequency moment F₂ = Σf², a measure of skew.
Approximation law: Error of an estimate from m independent observations falls as 1/√m: halving the error needs 4 times the memory.
ART (Adaptive Radix Tree): A trie with adaptive node sizes and path compression; a common in-memory index.
Atomic operation: An operation the hardware performs as one indivisible step; other threads see it either not done or fully done.
AVL tree: A balanced binary tree with a strict height bound (about 1.44 log n); reads fast, rebalances often.
B-link tree: A B-tree where each node has a pointer to its right sibling, so readers can pass a split in progress.
Backpressure: A signal from a consumer, based on its actual state, that makes the producer slow down.If a slow step cannot keep up, it tells the step before it to slow down, and that step tells the one before it, until the source stops reading. We study this in Part 8.
Big-O: A way to describe how work grows with input size.
Big-O notation: O(files) means "the work grows in proportion to the number of files." O(1) means "the work is the same however many files exist."
Birthday bound: Collisions among m slots begin after about √m random insertions.
Bit-packing: Storing every value of a block with the same fixed number of bits.
Bit-sliced index: A column stored as one bitmap per bit position, allowing range predicates and sums on bitmaps.
Bitmap index: For each distinct value, a bit vector with one bit per row; predicates become boolean operations on words.
Blocked Bloom filter: A Bloom filter that confines all k bits to one cache-line-sized block, for one cache miss per lookup.
Blocking operator (pipeline breaker): An operator that must read all input before it can output the first row, such as a sort.
Bloom filter: A bit array and k hash functions answering "definitely not present" or "probably present"A tiny structure that answers "is this key in the set?" with either "definitely not" or "probably yes". It never misses a real member, but sometimes says "probably yes" for a key that is not there (a false positive). It needs about 10 bits per key.
Bounded heap: A heap capped at k items, used to compute top-k in O(k) memory.
Branching factor / fanout: The number of children of a tree node.
BRIN: PostgreSQL's block-range index: a tiny min/max summary per range of pages.
Bucketed and sorted table: A table physically divided and sorted at write time so later queries can reuse the order.
Buffer-runs-merge: The write path of mutable in-memory buffer, immutable sorted runs and background merge, with a manifest and a collector.
Bε-tree (fractal tree): A B-tree whose nodes reserve space for buffered updates; a continuum between B-tree and LSM.
Cache coherence: The hardware rule that keeps copies of one memory location in different cores' caches consistent; works per cache line.
Cache line: The 64-byte block the CPU moves between RAM and cache.Memory (RAM) is fast but small and loses its content when power is off. Storage (SSD, disk) is slower but large and permanent. Hardware never moves single bytes. It moves fixed-size blocks:
Catalan number: The count of distinct ordinal trees on n nodes; its logarithm gives the 2-bits-per-node floor.
Chaining: Hash collision strategy that keeps a linked list of keys per slot.
Coarse locking: Using one lock for a large structure; simple, does not scale, and is often right for structures that are not hot.
Collector: A background job that frees or reorganizes old versions of data.1 other meaning →
Columnar stack: The ordering dictionary, bit-packing or run-length encoding, per-block statistics, then an optional byte codec.
Compact (class): A structure using O(Z) space, where Z is the information-theoretic minimum.
Compaction: Rewriting many small files into fewer larger ones.An LSM-tree (Log-Structured Merge tree) is a storage structure that never changes files in place. It collects writes in memory, writes them as sorted, immutable files, and later compacts (merges and rewrites) the files in the background to remove old versions and deleted entries. A tombstone is a marker that says "this key was deleted"; compaction removes the key and the marker. Compaction costs disk and CPU. Write amplification is the ratio of bytes the storage actually writes to bytes the application asked to write. A Bloom filter is a small structure that answers "definitely not in this file" or "maybe in this file", so reads can skip most files.
Compactor (KLL): A buffer that, when full, sorts and keeps every other element at double weight.
Compare-and-swap (CAS): An atomic instruction that updates a variable only if it still has the expected old value.A lock or latch lets only one thread enter a piece of code or data at a time (a latch is a short lock inside a database). CAS (compare-and-swap) is one CPU instruction: "set this variable to new only if it still equals old". It either succeeds or fails and never blocks. Lock-free algorithms are built from it.
Concurrent hash map: A hash table that many threads read and write at once; its hard operation is resize.
Conservation of cost: The principle that costs are never removed, only moved.
Consistent hashing: Mapping keys and nodes onto a ring so a membership change moves only about K/N keys.Consistent hashing is a way to map keys onto nodes so that adding or removing a node moves only a small part of the keys. A CRDT (conflict-free replicated data type) is a data structure designed so that copies edited independently can always be merged to the same result. Last-write-wins resolves two conflicting versions by keeping the one with the later timestamp and discarding the other.
Contention: Several threads wanting the same resource at the same time.
Coordinated sample: Samples built with the same hash function so that set operations can be done on the samples.
Coordination (as a currency): The cost of many actors agreeing who may touch what; superlinear in the number of participants.
Copy-on-write B-tree: A B-tree that writes a new path from leaf to root for each update instead of modifying pages.
Count-Min Sketch: A d × w table of counters that estimates item frequencies with overestimation proportional to total stream size.
Count-Sketch: A signed variant of Count-Min that supports deletions and L2 estimation.
Cuckoo filter: A membership filter storing fingerprints in a cuckoo hash table; supports deletion.
Cuckoo hashing: Hashing with two candidate slots per key; at most two probes per lookup, but inserts may cascade.
Dangling pointer: A pointer to memory that has already been freed; using it is a use-after-free bug.
Deletion vector: A compact bitmap of dead row positions, stored beside an immutable file.
Delta encoding: Storing differences between consecutive values instead of the values.
Delta store plus rebuild: The mutation story for read-only structures: changes go to a small side structure merged by periodic rebuild.
Dependent fetch: A read whose address depends on the result of the previous read, so it cannot overlap.A pointer is an address stored inside a data item that says where the next item is. A dependent fetch (or dependent miss) is a memory or disk read whose address you only learn from the previous read. Following a linked list is the typical example: you cannot read item 5 until you have read item 4. Dependent fetches cannot overlap, so each one pays the full latency. A cache miss to RAM costs about 80 ns. An NVMe SSD read costs about 100 µs (1 µs = 1/1,000,000 s; 1 ns = 1/1,000,000,000 s). A read from cloud object storage costs 20 to 100 ms.
Dictionary encoding: Replacing each value by a small integer index into a table of distinct values.
Disorder-tolerance knob: The parameter of any structure that says how much invariant violation is allowed before repair.
Dynamic hashing: Hashing methods (extendible, linear) that grow one bucket at a time.
Elias-Fano: An encoding of sorted integers with low bits packed and high bits in unary; about n(2 + log₂(u/n)) bits with random access.
Encoding (versus compression): A structure-aware, queryable representation; a codec is opaque and needs decompression.Compression makes data smaller. Generic compressors (gzip, LZ4) look for repeated byte patterns. Encodings are simpler, type-aware tricks, for example dictionary encoding (store each distinct value once, then store small numbers that point into the dictionary), run-length encoding (RLE) (store "India x 5,000" instead of five thousand copies), delta encoding (store the difference from the previous value) and bit-packing (use only as many bits per value as the largest value needs).
Entropy: The minimum average bits per symbol needed given only symbol frequencies.1 other meaning →In information theory, the entropy of a source is the minimum average number of bits per symbol needed to describe it, if you only know how often each symbol occurs. We will meet the formula in Part 3.
Epoch: A global counter that increases over time; used to decide when retired memory is safe to free.2 other meanings →
Epoch-based reclamation (EBR): Freeing a retired node only after every thread has advanced past the epoch in which it was retired; cheap readers, unbounded memory if a thread stalls.
Extendible hashing: A hash scheme with a directory that doubles while individual buckets split.
External sort: A sort of data larger than memory: write sorted runs to disk, then merge them.
False sharing: Two cores writing different variables in the same cache line, so the line bounces between caches.
Fan-in: The number of runs or partitions handled at once; F = M/B.1 other meaning →
Fetch-and-add (FAA): An atomic instruction that adds to a memory word and returns the old value; it never fails.
Fingerprint: A short hash of a key stored instead of the key.
ForwardingNode: A marker left in a migrated bin of Java's ConcurrentHashMap that sends readers to the new table.
Frame-of-reference: Storing values as small differences from a block minimum.
Free-rider pattern: Rebuild-only structures that cost nothing extra inside a system that already rebuilds its files periodically.
FST (finite-state transducer): A trie minimized into a graph with shared paths; used for compact term dictionaries.
FTL (flash translation layer): An SSD's mapping from logical to physical addresses.An SSD cannot overwrite a small piece of data in place. Its internal software, the FTL (flash translation layer), writes new data to a fresh place, keeps a lookup table, and later cleans old data, which means one logical write can cause several physical writes (typically 2 to 3 times, sometimes more).
GF(2): Arithmetic on bits where addition is XOR.
Grace period: The time a writer waits until every reader has finished with old data (in RCU, EBR, vacuum, snapshot expiry)
Gustafson / Amdahl: (Not used in this article.)
HAMT: Hash Array Mapped Trie; a wide (often 32-way) trie used for persistent maps and vectors.
Hash function: A function that turns a value into a large, evenly spread number; the same input gives the same output.A function that turns any key (a string, a number) into a number that looks random. The same key always gives the same number. Two different keys can give the same number; this is a collision.
Hazard pointer: A per-thread published pointer that tells reclaimers "do not free this"; bounded memory, expensive readers.
Heap: A tree-shaped structure that keeps only the minimum (or maximum) in place.2 other meanings →
Heavy hitter: The most frequent keys; structures such as Space-Saving track only the top k.
Hierarchical timing wheel: A structure that bins timers into time slots and advances a cursor; O(1) amortized.
HLL++: A production HLL with sparse mode, linear counting and bias correction.
Holistic aggregate: An aggregate (MEDIAN, exact COUNT DISTINCT) with no bounded intermediate state.
Homomorphism law: Only summaries that merge from partial results distribute (merge of summaries equals summary of merged data)
HyperLogLog: A distinct-count sketch that keeps the longest leading-zero run per bucket; error 1.04/√m.
IBLT: Invertible Bloom lookup table; lists the difference between two sets in space proportional to the difference.
Idempotent sketch: A sketch where inserting the same item twice changes nothing.
Immutability law: Layouts that cannot update in place grow an indirection layer and a collector.
Immutable: Never changed after it is written; it can be cached without invalidation.Something that is never changed after it is created. A new version is a new object with a new name. Parquet files in a data lake are usually immutable: you add files, you do not edit them.
Implicit / succinct / entropy-compressed: Classes of structure by space overhead above the information-theoretic minimum Z.
In two sentences: An SSD cannot overwrite a small piece of data in place. Its internal software, the FTL (flash translation layer), writes new data to a fresh place, keeps a lookup table, and later cleans old data, which means one logical write can cause several physical writes (typically 2 to 3 times, sometimes more).
Independence law: Independence is assumed everywhere and true almost nowhere.
Information-theoretic minimum (Z): The fewest bits that can represent the data.
Interesting order: An ordering supplied by an index that lets the plan skip a sort.
Interpolation search: Search that jumps to an estimated position using a model of the key distribution.
Interval tree: A tree augmented with subtree maximum end points to answer stabbing and overlap queries.
Jaccard similarity: Size of the intersection divided by size of the union of two sets.
Join-semilattice: A set with a "least upper bound" operation; the algebraic structure behind state-based CRDTs.
Key-value separation: Storing large values outside an LSM-tree so compaction rewrites only keys.
KLL: A mergeable quantile sketch with proven rank error.
KMV: "k minimum values": keep the k smallest hashes to estimate distinct count.
Latch: A short lock inside a database protecting a page or structure.A lock or latch lets only one thread enter a piece of code or data at a time (a latch is a short lock inside a database). CAS (compare-and-swap) is one CPU instruction: "set this variable to new only if it still equals old". It either succeeds or fails and never blocks. Lock-free algorithms are built from it.
Late materialization: Building full rows or decoding values only after filtering.
Latency: Time one operation takes from request to response.Throughput is work finished per second. Latency is how long one operation takes. Little's Law links them to the number of operations in progress: L = λ × W, where λ is the arrival rate (per second), W is the average time one operation spends in the system, and L is how many are inside the system at the same time. Example: 1,000 requests per second, each taking 20 ms (0.02 s), means 1,000 × 0.02 = 20 requests in flight at any moment. This is an identity, not a design choice.
Learned index: An index that replaces a search structure with a model of the data distribution.
Leveled compaction: One run per level; low read and space cost, high write cost.
Linear counting: Estimating a count from the fraction of empty buckets; used for small cardinalities.
Linear hashing: A hash scheme that splits one bucket per insert in a fixed rotation.
Linear probing: Open addressing in which a collision tries the next slot.
Linear sketch: A sketch that is a linear projection of the frequency vector, so sketches add.
Little's Law: L = λW: average items in a system = arrival rate × average time in the system.Throughput is work finished per second. Latency is how long one operation takes. Little's Law links them to the number of operations in progress: L = λ × W, where λ is the arrival rate (per second), W is the average time one operation spends in the system, and L is how many are inside the system at the same time. Example: 1,000 requests per second, each taking 20 ms (0.02 s), means 1,000 × 0.02 = 20 requests in flight at any moment. This is an identity, not a design choice.
LMAX Disruptor: A high-speed ring-buffer queue library from a trading firm; showed that cache-line layout dominates queue speed.
Load factor (α): The fraction of hash table slots in use.
Local density adaptivity: Choosing a container or representation per chunk by its observed density (ART, HLL++, Roaring)
Lock (mutex): A flag that only one thread can hold at a time.A lock or latch lets only one thread enter a piece of code or data at a time (a latch is a short lock inside a database). CAS (compare-and-swap) is one CPU instruction: "set this variable to new only if it still equals old". It either succeeds or fails and never blocks. Lock-free algorithms are built from it.
Lock striping: Dividing a table into several parts, each with its own lock, to reduce the serial fraction.
Lock-free: A guarantee that some thread always makes progress, though an individual thread may starve.
Loser tree (tournament tree): A merge structure needing one comparison per level when the winner is replaced.
LOUDS: A succinct tree encoding using about 2 bits per node, navigated with rank/select.
LSH (locality-sensitive hashing): Hashing designed so that similar items collide on purpose.
LSM-tree: Log-structured merge tree: buffer writes in memory, flush sorted runs, merge in the background.An LSM-tree (Log-Structured Merge tree) is a storage structure that never changes files in place. It collects writes in memory, writes them as sorted, immutable files, and later compacts (merges and rewrites) the files in the background to remove old versions and deleted entries. A tombstone is a marker that says "this key was deleted"; compaction removes the key and the marker. Compaction costs disk and CPU. Write amplification is the ratio of bytes the storage actually writes to bytes the application asked to write. A Bloom filter is a small structure that answers "definitely not in this file" or "maybe in this file", so reads can skip most files.
Memory: Memory (RAM) is fast but small and loses its content when power is off. Storage (SSD, disk) is slower but large and permanent. Hardware never moves single bytes. It moves fixed-size blocks:
Memory ordering (release/acquire): Rules that make writes before a release store visible to a thread that sees that store with an acquire load.
Memtable: The in-memory write buffer of an LSM-tree.
Merge join: A join of two sorted inputs in O(n + m) time and O(1) memory.
Mergeability law: Only operations that can be combined from partial results distribute.
MESI: A common cache-coherence protocol; a write by one core invalidates other cores' copies of the line.
Metadata escalation ladder: The sequence of per-block statistics: min/max, null counts, distinct list, Bloom filter, histogram.
MinHash: A signature whose match fraction estimates Jaccard similarity.
Minimal perfect hash function (MPHF): A collision-free function mapping n known keys to n slots using about 2 to 3 bits per key.
Mismatch law: Granularity mismatch generates amplification, and layers multiply it.
Misra-Gries: A deterministic heavy-hitter algorithm using k counters and global decrements.
Monkey: The result that Bloom filter false-positive rates should be proportional to level size in an LSM-tree.
Monotonic deque: A double-ended queue that keeps only non-dominated candidates for a sliding maximum.
MPSC: Multiple producers, single consumer; a queue type that needs arbitration between producers.
MVCC: Keeping old versions so readers do not block writers and writers do not block readers.A technique where an update does not overwrite a row but creates a new version, so that readers who started earlier can still see the old one. Each reader works on a consistent snapshot. Old versions are removed later by a cleanup job (called vacuum in Postgres).
N\* (USL peak): The worker count √((1−α)/β) at which throughput is highest; beyond it throughput falls.
Normalized key: A byte-string encoding of a sort key whose memcmp order equals the semantic order.
One-sided error: An error in only one direction (only false positives, or only overestimates)
Open addressing: A hash table that stores all keys in the array itself and probes on collision.
p99: The latency that 99% of requests beat; shows the slow tail.Time 1,000 requests and sort them from fastest to slowest. The p50 (median) is the 500th: half were faster. The p99 is the 990th: only 1% were slower. The p99.9 is the 999th. The slowest requests are called the tail. The mean (average) adds all the times and divides by the count.
Page: The fixed-size unit (commonly 4-16 KiB) read and written by storage and databases.3 other meanings →Storage hardware and databases do not read single bytes. They read fixed-size chunks called pages (or blocks), typically 4 KiB to 16 KiB on a local disk. To read one 200-byte row you must read its whole page.
Pane: A small time slice (one slide long) holding a partial aggregate for a sliding window.
Partition, localize, merge: Split the key space by range, run a local structure in each article, merge results; fails under skew.
Path compression: Collapsing a chain of single-child trie nodes into one edge.
Peeling: Constructing an XOR filter by repeatedly assigning a slot touched by exactly one key.
Persistent data structure: A structure whose updates return a new version and keep the old one intact, using structural sharing.
Physical-contention law: Contention is set by which cache lines are written, not by which operations conflict in meaning.
Pointer: A pointer is an address stored inside a data item that says where the next item is. A dependent fetch (or dependent miss) is a memory or disk read whose address you only learn from the previous read. Following a linked list is the typical example: you cannot read item 5 until you have read item 4. Dependent fetches cannot overlap, so each one pays the full latency. A cache miss to RAM costs about 80 ns. An NVMe SSD read costs about 100 µs (1 µs = 1/1,000,000 s; 1 ns = 1/1,000,000,000 s). A read from cloud object storage costs 20 to 100 ms.
popcount / POPCNT: An instruction that counts the set bits in a word.
Posting list: The sorted list of document ids for one term in an inverted index.
Power-of-two-choices: Pick two servers at random and send to the less loaded; avoids herding.
Pruning cascade: The ordered chain zone map, Bloom filter, sparse index, block scan; each stage has one-sided error and is cheaper than the next.
q-digest: A quantile sketch on a fixed binary partition of a bounded integer domain.
Queue: A line of work waiting for its turn, like people waiting at a bank counter. A scheduler is the part of a system that decides who is served next.1 other meaning →
Queueing law: Contention-allocated resources cost 1/(1 − ρ)
Quiescent state: A point where a CPU provably holds no reference to old shared data (used by RCU)
Quotient filter: A mergeable, resizable membership filter that is more cache-friendly than Bloom.
Randomization law: Randomness can replace coordination, paid for in worst-case guarantees.
Range partitioning: Sending each record to the node that owns its key range; makes a global merge a concatenation.
Rank / select: Rank(i) = number of 1s before position i; select(k) = position of the k-th 1.
RCU (read-copy-update): A scheme where readers do nothing and writers wait for a grace period before freeing old data.
Read amplification: Bytes or probes fetched per byte of answer.
Recurring mechanisms: Techniques seen in many places: match granularity, local density adaptivity, binning, discard the dominated, growth without relocation, power of two choices, free-rider pattern.
Replacement selection: A heap-based run generation method giving runs of average length 2M; now mostly obsolete.
Reservoir sampling: A one-pass uniform random sample of k items from a stream of unknown length.
Ribbon filter: A near-optimal immutable filter built by solving a banded linear system.
Ring buffer: A fixed-size array used as a queue with head and tail indexes that wrap around.1 other meaning →
Roaring bitmap: A bitmap index that stores each 65,536-row chunk as an array, a bitmap or runs, whichever is smallest.
Robin Hood hashing: Open addressing that evens out probe lengths by moving slots from near-home keys to far-from-home keys.
RUM conjecture: The claim that Read, Update and Memory cost cannot all be optimized together; unproven.
Safe memory reclamation: Deciding when an unlinked node can be freed because no reader still holds a pointer to it.
Secondary index: Any index other than the primary key's.The primary key (PK) uniquely identifies a row. A secondary index is any additional index on other columns.
Selection vector: A list of the positions in a batch that passed a filter.
Seqlock: A version-number scheme where readers check the number before and after reading and retry if it changed.
SimHash: A signature from the sign bits of random projections; Hamming distance approximates angle.
Single-writer principle: Giving each memory location exactly one writer, so only ordering is needed and no exclusion.
Sketch (HyperLogLog): A small summary of a data set that answers one kind of question approximately.A quantile is a percentile: the value below which a given fraction of data falls (the median is the 50% quantile). A sketch is a small, fixed-size summary of a huge dataset that answers one kind of question approximately: for example a t-digest or KLL sketch answers quantile questions, HyperLogLog counts distinct values, and Space-Saving finds the most frequent values. A sketch is built in a single pass and uses bounded memory.
Skip list: A sorted linked list with random-height express pointers; lock-free inserts need no rebalancing.
Sorted run (SSTable): An immutable sorted file.
Space amplification: Bytes stored per byte of live data.
Space-Saving: A heavy-hitter algorithm that evicts the minimum counter and adopts its count plus one.
Sparse index: An index with one entry per group of rows (granule) instead of per row.
Spill: Writing operator state to disk and continuing with a different algorithm, instead of failing.A hash join matches rows of two tables by building an in-memory hash table from the smaller side (the build side) and looking up each row of the other side. A sort orders rows. Both need memory proportional to their input. When there is not enough memory, a good engine writes some of its working data to temporary files on disk and reads it back later. This is called spilling. Part 5 explains it fully; Part 1 only names it.
Split-ordered list: A lock-free hash table design that keeps all items in one recursively ordered list so resize moves no data.
SPSC: Single producer, single consumer; a queue that needs no atomic read-modify-write instruction.
SSD: Flash storage. It cannot overwrite data in place, so its flash translation layer writes new data elsewhere and cleans old blocks later, which turns one logical write into several physical ones.An SSD cannot overwrite a small piece of data in place. Its internal software, the FTL (flash translation layer), writes new data to a fresh place, keeps a lookup table, and later cleans old data, which means one logical write can cause several physical writes (typically 2 to 3 times, sometimes more).
Stabbing query: A query asking which stored intervals contain a given point.
Stable sort: A sort that keeps equal keys in their original order.
Structural sharing: Copying only the path from root to a changed node and sharing all other subtrees between versions.
Succinct structure: A structure using Z + o(Z) bits while still supporting queries.
SuRF: A succinct-trie range filter.
t-digest: A quantile sketch with small clusters near the extremes, giving good tail accuracy without proofs.
Theta sketch: A KMV-style sketch that supports union, intersection and difference.
Throughput: Work completed per unit of time.Throughput is work finished per second. Latency is how long one operation takes. Little's Law links them to the number of operations in progress: L = λ × W, where λ is the arrival rate (per second), W is the average time one operation spends in the system, and L is how many are inside the system at the same time. Example: 1,000 requests per second, each taking 20 ms (0.02 s), means 1,000 × 0.02 = 20 requests in flight at any moment. This is an identity, not a design choice.
Tier-boundary law: Compactness pays discontinuously, at the boundaries between memory tiers (a candidate law)
Tiered compaction: Several runs per level merged together; low write cost, high read and space cost.
Timsort: A sort that detects natural runs, so nearly sorted input is close to linear.
Trie: A tree that follows a key one character or byte at a time.
Universal Scalability Law (USL): C(N) = N / (1 + α(N−1) + βN(N−1)); a model of throughput with a contention term α and a coherency term β.
Use-after-free: A bug where code uses memory after it was freed.
Utilization (ρ): The fraction of time a resource is busy.Utilization (ρ, "rho") is the fraction of time a server is busy. For random arrivals, average response time grows like S ÷ (1 − ρ), where S is the service time: 2×S at 50%, 5×S at 80%, 10×S at 90%, 100×S at 99%. Queues are caused by variability meeting load, and the curve has a wall at 100%. The last few percent of utilization cost more than the first eighty.
UUIDv7 / ULID: Identifiers that start with a timestamp, so they sort in creation order.
Variance law: Variance costs more than volume.
Wait-free: A guarantee that every thread finishes in a bounded number of steps; the only one that bounds tail latency.
Watermark: Declared non-decreasing lower bound on the event times of future arrivals.1 other meaning →Every event carries a timestamp of when it happened (event time), which differs from when the job sees it (processing time). Events arrive late and out of order: a phone with no signal sends its events 5 minutes after they happened. A watermark is a marker flowing through the stream that says "no event with a timestamp earlier than T should arrive any more." It is the job's best guess of how complete the input is. When the watermark passes the end of a time period, the job may treat that period as complete. Watermarks are a guess, and late events can still violate them. The rules of when it is correct to emit a result (event time versus processing time, how late is too late) are a topic of their own. In this mechanism we need only the idea above. We study the machinery that holds data until the watermark allows an answer.
Write amplification: Bytes written per byte of user data.If you write 1 MB of data and the system physically writes 10 MB (because of rewriting and merging), the write amplification is 10.
Write-ahead log (WAL): Write-ahead log: ordered, append-only description of changes, forced before commit.Before a database changes its data pages, it first appends a description of the change to a sequential file called the log. If the machine crashes, the database replays the log to recover. Every serious database has one (it may be called WAL, redo log or binlog). Each position in the log has an increasing number, called an LSN (log sequence number; other systems call it SCN or GTID). In this mechanism the key fact is: the log is a complete, ordered record of every change, and it already exists..
XOR filter: An immutable membership filter built by solving a GF(2) system; 1.23 times the minimum.
Z-ordering: Interleaving bits of several columns to sort by several dimensions at once, with weaker clustering in each.
Zone map: Per-file min and max values of a column, used to skip files.A zone map stores the minimum and maximum of a column for each block of rows. If your range does not overlap a block's min/max, you skip the block without reading it. Partition pruning is the same idea at table level: a table is split into partitions by a key (for example by date), and the engine skips partitions that cannot match. Both rely on values being comparable, so that "min" and "max" mean something.