Glossary

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

Admission filter: A gate that decides whether a new key may enter the cache at all, based on estimated frequency.
Amortization: Spreading a fixed cost over many units so the cost per unit falls.Paying a fixed cost once and spreading it over many units. One delivery truck for 1,000 parcels costs less per parcel than 1,000 bicycles.
Amortization inequality: The rule λ/w > P/S: a derived cache entry pays only if reads per version exceed production cost divided by saving per read.
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 loads (consistent hashing): Capping each node at (1+ε) times the mean load and walking the ring on overflow.
Bypass path: The route that reads the first copy directly, without using the cache, which makes the cache stale by construction.A way to change the data without going through the cache. If every write goes through the cache, the cache cannot disagree with the data. If anyone can write to the database directly, the cache can be left holding an old value. The word stale means "an old value that the truth has since replaced".
Cache: A deliberately kept second copy of data that no protocol forces to stay correct.1 other meaning →A cache is a small, fast place that holds copies of data kept somewhere bigger and slower. When a request finds its data in the cache, that is a hit. When it does not, it is a miss, and the system must go to the slower place (the backing store or origin). The hit rate h is the fraction of requests that hit. The miss penalty is the extra time a miss costs.
Cache-aside: Pattern where the application reads the cache first and on a miss reads the store and fills the cache.
Churn (w): The rate of writes that make a cached object wrong.
Client near-cache: A tiny cache inside each client holding the hottest keys; cannot be invalidated directly.
Coalescing: Letting one requester recompute an expired key while the others wait for its result.1 other meaning →
Competitive ratio (k-competitive): The worst-case ratio between an online policy's misses and the optimal offline policy's misses.
Conditional GET / revalidation: Asking the origin "has this changed?" with a version tag; an "unchanged" answer costs a round trip and no payload.
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.
Content-addressed key: A cache key built from a hash of the content, so the same key always means the same bytes.
Correlated expiry: Many entries expiring at the same moment because they were filled together with the same TTL.
Cost-aware eviction (GDSF): Eviction by value density (frequency x miss cost / size) instead of recency only.
Derivation distance: How many transformation steps separate a cached object from the base data.
Designated version cell: One small value (pointer, snapshot id, timestamp) that all cached entries are keyed to, giving cross-entry consistency.
Doorkeeper: A small filter that stops one-time keys from reaching the frequency sketch.
Early probabilistic expiry: Recomputing an entry with rising probability before its expiry so refresh happens without coordination.
Explicit invalidation: Removing or marking cache entries by message when data changes.
Fan-in: The number of upstream pieces a single output depends on.1 other meaning →A DAG (directed acyclic graph) is a diagram of steps where each step depends on earlier steps and there are no loops. A batch job is often a DAG. Fan-in is the number of earlier pieces one step depends on.
FIFO eviction: Evicting the oldest inserted entry; needs no metadata and no write on a hit.
Hit: A request answered from the cache. A miss must go to the slower backing store; the hit rate h is the share of requests that hit.A cache is a small, fast place that holds copies of data kept somewhere bigger and slower. When a request finds its data in the cache, that is a hit. When it does not, it is a miss, and the system must go to the slower place (the backing store or origin). The hit rate h is the fraction of requests that hit. The miss penalty is the extra time a miss costs.
Hit rate (h): The share of requests answered from the cache.
Hot key: A key with far more rows than average.One key that receives far more traffic than others (a famous artist's tickets, one celebrity's profile). Traffic to keys is often Zipf-distributed: a few keys take most of the load.
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.
Jitter: Randomness added to waiting times to avoid synchronized clients.
Knee: A point on the miss-ratio curve where a small extra size gives a large gain.1 other meaning →
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.
Lease: A lock that expires after a time limit unless renewed.
Leverage: 1/(1 − h): how many requests the cache absorbs for each one that reaches the layer below.
Logarithms: ln x, the natural logarithm. Its key property, ln(a·b) = ln a + ln b, is why a constant step in one quantity can mean multiplying another, as in each point of cache hit rate costing a constant factor in cache size.Ln x is the natural logarithm. You only need two facts: ln(a·b) = ln a + ln b, and "adding a constant to ln C" means "multiplying C by a constant". When this mechanism says "each point of hit rate costs a constant multiplicative factor in cache size", that is a logarithm talking.
LRU: Least Recently Used: evict the entry that was unused for the longest time.
Manifest: A small file that lists other files, with sizes, checksums and totals; it defines the set.A small file that lists other files (names, sizes, checksums). It says "this set of files is the dataset".
Marking algorithm: A randomized paging algorithm that is Θ(log k)-competitive.
Materialized view: A stored query result that the system refreshes, with its admission declared.A query result that is saved as a table and kept up to date, instead of being recomputed each time it is read.
Miss: A request the cache cannot answer, so it goes to the slower backing store. The miss penalty is the extra time that costs.A cache is a small, fast place that holds copies of data kept somewhere bigger and slower. When a request finds its data in the cache, that is a hit. When it does not, it is a miss, and the system must go to the slower place (the backing store or origin). The hit rate h is the fraction of requests that hit. The miss penalty is the extra time a miss costs.
Miss penalty: The extra time a request pays when the cache does not hold the answer.
Miss-ratio curve (MRC): The miss ratio as a function of cache size.
Monoid / inverse: An aggregate with an associative combine and identity (monoid); an inverse lets you remove a value, which makes incremental maintenance under deletes possible.
Negative cache: A cache of "this key does not exist" answers.
Object storage: A cloud service holding named objects fetched by HTTP, replaced whole, never edited.A cloud service where each file ("object") has a name and is fetched with an HTTP request. A request costs 20-100 ms before the first byte arrives, and the provider charges a small fee per request. You cannot change a few bytes inside an object. You replace the whole object.
Parquet: Column-oriented file format with row groups, pages and a footer.Object storage (like Amazon S3) stores whole files called objects behind HTTP requests. Parquet is a file format that stores data column by column. A table format (such as Iceberg or Delta) records, in small metadata files called manifests, which data files make up a table. A snapshot is one exact version of the table, identified by a snapshot id. A catalog is the service that tells you the current snapshot of a table.
Percentile (p50, p99, p99.9): The value below which that fraction of observations fall.p50 is the median latency, p99 is the latency that 99% of requests beat. The slowest requests are the tail. When one request needs answers from many servers (a fan-out) it must wait for the slowest one. With 100 servers that each have a 1% chance of being slow, the chance that at least one is slow is 1 − 0.99¹⁰⁰ = 63%. So the user-facing tail is much worse than any single server's tail.
Plateau: A flat region of the miss-ratio curve where more memory does not change the hit rate.
Populate-after-invalidate race: A reader fetches an old value, the writer deletes the entry, then the reader fills the cache with the old value.
Prefetch: Speculatively loading data on the read path before it is requested.
Principal: The identity (user or role) on whose behalf a query runs.A principal is anyone or anything that can make a request: a person, a program, a scheduled job. An object is the thing they want to touch: a table, a file, a column. An action is what they want to do: read, write, delete. Almost all access control answers one question: may this principal perform this action on this object, right now?.
Read-your-writes: Guarantee that a client sees its own earlier writes; achieved with a version token in the key.
Resharding: Changing the number of partitions or the key-to-partition mapping.
Reuse distance (stack distance): The number of distinct items accessed since the previous access to the same item.
Row-level security: A database feature that filters rows according to the user, so cached results must be keyed per user or policy.
Scan resistance: Property that a long one-time scan cannot evict the useful working set.
Semantic cache: A cache that matches requests by meaning or similarity rather than exact key.
Serve-stale-while-revalidate: Serving the expired value while one requester refreshes it in the background.
Shard: A method that samples keys by hash to compute an approximate miss-ratio curve at very low cost.1 other meaning →
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.
Snapshot: A frozen consistent view of the database at one moment.1 other meaning →A lock makes other transactions wait while you use a row. A snapshot is a frozen, consistent view of the database as it was at one moment; with it, readers do not need locks, because they read old versions while writers create new ones. This second idea is called MVCC (multi-version concurrency control): the database keeps several versions of each row. Both are mechanisms. This mechanism is about the promises they are used to keep.
Snapshot id: An identifier for one committed version of a table.
Stack algorithm: Replacement policy whose contents at size c are a subset of the contents at size c+1 (LRU).
Stale: Out of date compared with the first copy.
Stampede (thundering herd): Many simultaneous recomputations of one key after it expires; duplicates = λ_k · W.
Table format: A specified metadata protocol that defines a table as a set of files plus commits.Object storage (like Amazon S3) stores whole files called objects behind HTTP requests. Parquet is a file format that stores data column by column. A table format (such as Iceberg or Delta) records, in small metadata files called manifests, which data files make up a table. A snapshot is one exact version of the table, identified by a snapshot id. A catalog is the service that tells you the current snapshot of a table.
Three currencies of freshness: Coordination, staleness and verification, the only ways to close the gap between cache and truth.
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.
TinyLFU / W-TinyLFU: Admission policy using an aged count-min sketch, plus a small LRU window for bursts.
TTL: Time to live: how long an entry may be served before it expires.A lifetime attached to a cache entry. After the TTL expires, the entry is dropped or treated as missing.
Value density: Expected future hits times miss cost divided by size; the right quantity to keep.
Virtual node (vnode): Many ring points per physical node so load evens out as 1/√V.
Volatility (IMMUTABLE/STABLE/VOLATILE): A function's declared stability, which decides whether a query using it may be cached.
Warming: Bulk-populating a cache with no request in flight, to survive a cold start.
Working set: The set of pages a workload keeps coming back to.
Write-around: Writing only the store and dropping the cache entry; admission follows read locality.
Write-back: Writing only the cache and flushing later; moves the source of truth into the cache.
Write-invalidate / write-update: On write, delete the cache entry (safe) or overwrite it (race-prone).
Write-through: Writing cache and store synchronously before acknowledging.
Zipf / alpha: A popularity distribution where frequency falls as rank^(−α); α decides how fast cache size must grow with corpus size.
Zipf distribution: A distribution where the r-th most common value has frequency about 1/r of the top one.In many workloads a few items are requested very often and most items are requested rarely. Zipf's law says the item of popularity rank i (rank 1 is the most popular) is requested with frequency proportional to i^(−α). The number α (alpha) is the popularity exponent. A larger α means a steeper concentration on the top items.