Approximate Memory Cache Systems

Sketch-backed cache

Simple Fundamental Explanation

Imagine you are a security guard checking ID badges at a massive concert.

The Exact Way: You have a giant binder with the names of all 100,000 attendees. For every person, you flip through the pages to find their exact name. It takes 30 seconds per person. The line stops moving.
The Approximate Way: You scan a barcode on their ticket. The scanner flashes a green light if the barcode looks like the mathematical pattern of a valid ticket. It doesn’t actually check the central database. There is a 0.01% chance a clever counterfeiter gets in, but you process 5 people every second, and the line moves flawlessly.

In distributed computing, an Approximate Memory/Cache System intentionally drops perfect data retention or exact key-value mapping to compress the memory footprint by orders of magnitude. It answers queries probabilistically: “This item is probably in the cache,” or “This item has been accessed about 50 times.”

Deep Dive: How It Works Under the Hood

Modern infrastructure (like web caches, CDNs, and database buffers) cannot afford to keep all data in RAM. They must use caching. But tracking exactly what is in the cache (and what should be evicted) requires massive metadata.

Approximate systems use probabilistic data structures to compress this metadata.

1. Approximate Admission (TinyLFU)

As discussed in TINYLFU.md, instead of tracking the exact frequency of every database query ever made, systems like Caffeine Cache use a Count-Min Sketch. The cache doesn’t know exactly how many times a user logged in, it just knows an over-estimated approximation. This approximation is good enough to make highly optimal eviction decisions.

2. Approximate Membership (Bloom Filters in Storage)

Databases like Apache Cassandra and LevelDB use Log-Structured Merge (LSM) trees. Data is written to immutable files on disk (SSTables). To find a specific row, the database would normally have to read every single file on disk (extremely slow). Instead, every file has an attached Bloom Filter in RAM. The database asks the filter: “Is this row in this file?” The filter answers “Definitely No” (skip reading the disk entirely) or “Probably Yes” (perform a slow disk read).

Visual Diagram: Storage Engine Bloom Filter

Query: SELECT * FROM Users WHERE ID = 'User789'

RAM:
SSTable_1_Filter: "Definitely No"
SSTable_2_Filter: "Definitely No"
SSTable_3_Filter: "Probably Yes" (False Positive)
SSTable_4_Filter: "Probably Yes" (True Match)

Disk Reads:
Database skips files 1 and 2 completely! (Saved 50% of disk I/O)
Database reads file 3 -> Not found (Wasted 1 read due to false positive).
Database reads file 4 -> Found data!

Practical Example: CPU Hardware Caches

The concept of approximate caching goes all the way down to the physical silicon.

Modern CPU caches (L1, L2, L3) use Pseudo-LRU (PLRU) algorithms. Maintaining a perfect, strict “Least Recently Used” chronological list for a hardware cache requires updating pointers on every single clock cycle. This uses too much physical space on the silicon and generates too much heat.

Instead, CPUs use a binary tree of bits. When a cache line is accessed, it flips a bit pointing away from that line. When the CPU needs to evict data, it just follows the bits down the tree. It doesn’t find the exact least recently used item, but it probabilistically finds a “pretty old” item in just a few nanoseconds using a microscopic amount of silicon.

The Mathematics: Equations and In-Depth Analysis

The Cost of False Positives in Storage

In an LSM-tree database, how large should we make the Bloom filters to optimize performance?

Let $R_{d}$ be the cost (in latency) of reading from the hard disk (e.g., 10,000 microseconds). Let $R_{m}$ be the cost of reading the Bloom filter from RAM (e.g., 1 microsecond). Let $P$ be the false positive rate of the Bloom filter.

The expected cost of a query for a key that does not exist in the file is:

E [Cost] = R_{m} + P \cdot R_{d}

We know from Bloom Filter theory that $P \approx (0.6185)^{m / n}$ , where $m / n$ is the number of bits allocated per item.

If we allocate 10 bits per item, $P \approx 0.01$ (1%). The expected cost is: $1 μ s + (0.01 \cdot 10, 000 μ s) = 101 μ s$ .

By spending just 10 bits of RAM per item, we reduced the disk penalty for missing keys by 99%. Engineers mathematically optimize $m / n$ based on the ratio of RAM cost vs SSD latency to find the perfect probabilistic sweet spot for their infrastructure.

Lab

Approximate caches trade exact metadata for compact sketches. Tune Bloom bits per item (LSM absent-key probes: E[Cost] = R_m + P·R_d) and CMS ε (admission frequencies) — then compare oracle hit ratio vs sketch-backed admission on the cache-scan trace.

Bloom bits per item (m/n)10.0 bits/item

SSTables on disk8 files

CMS ε (frequency error)0.02

Cache capacity (admission)8 slots

LSM absent-key probe

SST 8Bloom: definitely no — skip disk1 µs

SST 7Bloom: definitely no — skip disk1 µs

SST 6Bloom: definitely no — skip disk1 µs

SST 5Bloom: definitely no — skip disk1 µs

SST 4Bloom: definitely no — skip disk1 µs

SST 3Bloom: definitely no — skip disk1 µs

SST 2Bloom: definitely no — skip disk1 µs

SST 1Bloom: definitely no — skip disk1 µs

Read every file80.0 ms

Bloom per file664 µs ~83 µs / table

Cache admission hit ratio

Exact freq

CMS sketch

LSM naive

LSM + Bloom

Green SST rows: Bloom says “no” — skip disk. Red rows: false positive wastes a read (~0.8% per table). Cache bars replay the cache-scan trace (32 accesses, capacity 8).

With 10.0 bits/item Bloom filters across 8 SSTables and CMS ε=0.02, will sketch-backed admission match the exact-frequency hit ratio on the cache-scan trace?

P ≈ (0.6185)^10 = 0.8%. Expected absent-key cost: 664 µs vs 80.0 ms naive. Cache: exact 50.0%, CMS 40.6%.