Cache invalidation is the problem of knowing when a cached query result has gone
stale and needs replacing. A write changes one row in the database, and every
cached answer derived from that row is now wrong. The work is finding those
answers and dropping or refreshing them before the next read.
Say you have a read-heavy application and you've been asked to make reads faster.
You put a cache in front of the database, the read path gets fast, and that
invalidation work lands in your write path as a short list of rules. Here are the
rules:
- If a vote arrives, drop that story's key.
- If a title changes, drop that story's key.
- If an account is renamed, drop that user's key.
One rule per table. It reviews cleanly and it ships.
One of those three rules is wrong. The page it breaks keeps serving stale data
until something unrelated evicts the entry.
We wanted to know what that mistake actually costs, and how the alternatives
compare when they see identical writes. So we built a lab and measured six read
paths against one workload.
Writing one of those rules wrong is easy. Here is the mistake in full, with the
schema on the page. Three tables, quoted from Figure 2 of the
Noria paper:
CREATE TABLE stories (id int, author int, title text, url text);
CREATE TABLE votes (user int, story_id int);
CREATE TABLE users (id int, username text);
The lab adds a primary key to each of the three tables.
A story page reads across all three. It needs a title from stories, a display
name from users, and a count from votes, and all three collapse into a single
cache key. So a cached result is not a copy of a row. It is an answer derived
from rows in several tables, and no one of those tables can say which cached
answers depend on it.
The code that writes knows which row it changed. The cache knows which key it
holds. The mapping between the two lives in exactly one place, the text of the
read query, and the read query sits nowhere near the write path:
SELECT s.id, s.title, u.username
FROM stories s JOIN users u ON u.id = s.author
WHERE s.id = ?;
The edge that matters is u.id = s.author. It says that changing a user dirties
story pages. Nothing in the users table mentions a story, so the rename rule has
no way to find the keys it just falsified. It drops a user key that this page never reads,
and every story by that author keeps serving the old name.
Nothing catches this. A cache entry that should have been dropped and was not
raises no error. It returns a plausible name, on the instances that happen to hold
it, only for entries populated before that particular write. It will not reproduce
on a laptop where the cache is empty, which is why this class of bug tends to be found by a user rather than by a test.
A 2023 survey by Ji, Zhou, Zhou and Wang
analysed 20 Spring-cache web applications and surveyed more than 50 engineers. Of
the cached methods they counted, 80.6% used a time to live or coarse-grained
invalidation (dropping every cache entry associated with a table or namespace,
rather than working out which specific entries a write affected), and only 10.4%
attempted fine-grained invalidation.
Four out of five cached results in real projects do not attempt the mapping. They
accept staleness instead. The authors' explanation of why:
All the aforementioned cases converge on a single fundamental challenge: the
absence of a link between database updates and cache entries at the application
level, making precise cache invalidation difficult to achieve.
Their examples are ordinary. One delete method issues 11 SQL statements across 9
tables, so no application-level rule can say what it dirtied. Another caches a
query with range predicates, where deciding whether an update changes the result
means evaluating the predicate.
Even teams who do this well find it hard.
Meta's Polaris service
exists to detect cache inconsistencies that reach production, and it moved TAO, the
store behind Facebook's social graph, from 99.9999% to 99.99999999%
consistency. Before Polaris, roughly one write in a million was silently wrong,
and it took a purpose-built service to find out.
Four strategies are in common use:
Time to live. Do not track dependencies at all. Put an expiry on each cached
result and re-read the query when it lapses. This is the most widely used strategy
because it is the only one with no invalidation code, and the trade is that the
cache is correct within N seconds, and you chose N. A TTL cache
also never learns that anything changed, so it re-reads on a schedule whether the
underlying rows moved or not.
Manual cache keys, the Redis model. Store each result under a key the
application chooses and delete those keys from the write path. Precise in
principle. The cost is that the write path has to invert the read query by hand,
and a missed edge is silent.
Event-driven invalidation. Read the database change stream, the MySQL binlog or
the Postgres write-ahead log, and invalidate from it. Moving the trigger out of the
application removes the race between a write and its invalidation, which is a real
gain. The mapping stays. The team still writes and maintains the code that turns a
changed row into the cache keys it affects, now in a stream processor rather than
in a write path.
Incremental view maintenance. Apply each change to the stored result instead of
discarding it. There is no invalidation step to write, because nothing is deleted.
| Strategy | Who writes the invalidation | When the cached result is wrong | Cost of a write |
|---|
| Time to live | Nobody | Up to the length of the window, after every write | None, but refreshes run on a clock whether or not anything changed |
| Manual cache keys | The application, per query | Until eviction, whenever the mapping misses an edge | The invalidation, plus a burst of misses behind it |
| Event-driven invalidation | The application, in a stream processor | Until the mapping is corrected | Stream processing, plus the burst of misses |
| Incremental view maintenance | Nobody | Only while the change propagates | Maintenance work inside the dataflow graph |
The rest of this post measures the first, the second and the fourth against each
other on one schema. One write workload.
The lab runs on the three tables declared above, stories, users and votes,
seeded at the scale the
Noria paper reports for
production Lobsters: 10,000 users, 40,000 stories and 500,000 votes. Six read
paths served the same story page under one write workload, and saw exactly the
same writes. Readyset runs with its query sampler off throughout.
The six paths:
- MySQL directly, no cache, as a control
- Redis look-aside with the three-rule invalidator, whose rename rule drops a
user key and leaves every story page by that author wrong
- Redis look-aside with a corrected invalidator
- Readyset shallow cache, fixed 10 s TTL with a 5 s refresh
- Readyset shallow cache with adaptive refresh
- Readyset deep cache, which maintains the result incrementally, a technique
called incremental view maintenance and abbreviated IVM in the tables that
follow
Reads have to be continuous, or the number measures the cache miss instead of the
cache: burst-reading a TTL cache reports 12 ms staleness where continuous reading
of the same cache reports seconds. The write interval also has to be jittered.
With a fixed interval, two runs of an identical configuration produced 4,783 ms
and 177 ms, both arithmetically correct and both meaningless, because the answer
was set by the phase relationship between the write clock and the cache's refresh
clock.
The control path has no cache, so it cannot be stale. It is there to measure the
instrument.
The clock starts when the write commits and stops when a reader first sees the new
value, so the control's number is whatever that detection costs. Readers issue one
query and read back to back with no pause between reads, which puts the control at
0.19 ms, and each observation is bracketed to 0.28 ms by the read that caught
it. Every number in this post is measured at that resolution.
Two corrections: the readers used to sleep 2 ms between reads, so a write landed
uniformly inside a detection window and half that window showed up as staleness.
And each poll ran both cached queries while inspecting only the vote count,
paying for a query it never used. Removing the sleep and the spare query moved
the control from 2.00 ms to 0.19 ms.
Staggering more reader threads, which looks like the obvious fix, does nothing. For
N readers at interval T the aggregate grid is T/N and the read load is N/T. So grid
spacing is one over the load, and four readers at 8 ms is the same grid as one reader
at 2 ms. The lever is aggregate read rate. Taking the sleep out reaches a grid of one
round trip with a single thread.
In ten trials we warmed every path, renamed an author, then read continuously
for 45 seconds and recorded when each path first returned the new name.
| Read path | Converged | Never converged |
|---|
| no cache (control) | 10 | 0 |
| look-aside, three-rule invalidator | 0 | 10 of 10 |
| look-aside, corrected invalidator | 10 | 0 |
| Readyset shallow, fixed refresh | 10 | 0 |
| Readyset shallow, adaptive refresh | 10 | 0 |
| Readyset deep (IVM) | 10 | 0 |
Ten out of ten. Every other path recovers. The three-rule invalidator never did,
and in production the entry would stay wrong until unrelated memory pressure
evicted it. That makes the bug's lifetime a property of the Redis eviction policy
rather than of anything in the application.
The fix is more expensive than it looks. The rename rule has to ask the database
which stories that author wrote, because that is the only way to learn which keys
were dirtied. That puts
a SELECT in the write path, with a fan-out equal to the number of stories the
author has written, which is unbounded and largest for exactly the accounts that
matter most. It also writes the join down a second time, so adding a column to
the cached page means finding every write path that can touch it, again, with
nothing to signal a miss.
A vote arrives and the count changes. This is the write path the three-rule
invalidator handled correctly, so it is the fairest comparison. Three runs of sixty
writes, medians across runs.
| Read path | p50 | p95 | Excess over the uncached control, p50 |
|---|
| no cache (control) | 0.19 ms | 0.40 ms | n/a, this is the control |
| look-aside, corrected invalidator | 1.11 ms | 1.57 ms | 0.92 ms |
| Readyset shallow, fixed refresh | 2.68 s | 4.74 s | 2.68 s |
| Readyset shallow, adaptive refresh | 2.29 s | 4.28 s | 2.29 s |
| Readyset deep (IVM) | 1.66 ms | 2.17 ms | 1.48 ms |
60 writes per run, 3 runs, medians across runs. Readers poll back to back at about 3569 reads/sec, so the instrument brackets each observation to 0.28 ms.
The TTL caches sit between two and five seconds behind. That is what a TTL is.
With a 5 s refresh and
uniformly phased writes, half the reads land in the first half of a refresh period,
so the theoretical p50 is 2.5 s. Measured 2.68 s. Adaptive refresh helped a little
and it can't help much, because it moves each entry's period between 10% and 100% of
the configured value, so a 5 s refresh has a floor of 500 ms.
The look-aside cache is marginally the freshest of the three.
At 1.11 ms it is about half a millisecond ahead of incremental view maintenance at
1.66 ms. Two conditions are doing work behind that number: the query is cheap, and
the write rate is one write every seven seconds. That ordering makes sense once you look at what each one does with a write.
A look-aside cache deletes the entry and lets the next reader refetch, so what it
serves next is whatever MySQL has at that instant. Incremental view maintenance has
to carry the write through the binlog and the dataflow graph before the stored result
changes, and on this schema that costs about 1.5 ms over an uncached read.
So on the write path a hand-written invalidator gets right, it wins by half a
millisecond. A harness that shows otherwise is probably measuring itself.
The story-page probe query is two indexed point lookups. When the look-aside cache
throws its entry away, refetching costs about a millisecond, which is why deleting
and refetching looks free. A query like that is rarely worth caching. The reason to
cache is that recomputing is expensive.
So the same measurement, on a query with no index to lean on:
SELECT user, COUNT(*) AS c FROM votes WHERE user = ? GROUP BY user;
votes is indexed on story_id, not on user, so this is a full scan of about
500,000 rows and takes roughly 35 ms on this machine. Twenty-five writes, same
method:
| Read path | Staleness p50 | Staleness p95 | One read, p50 |
|---|
| no cache (control) | 59 ms | 102 ms | 36.62 ms |
| look-aside, corrected invalidator | 42 ms | 51 ms | 0.16 ms |
| Readyset deep (IVM) | 1.48 ms | 1.96 ms | 0.23 ms |
The ordering inverts, and the deep cache is now about 28 times fresher rather
than half a millisecond behind.
Read the last column next to the first. Both caches answer a single read in a
fraction of a millisecond, so both are doing their job as caches. Their staleness
differs by a factor of 28 because they recover from a write differently. A
look-aside cache recovers by recomputing, so its staleness can never be lower than
what the query costs. Incremental view maintenance recovers by applying one delta
to the stored result, so its cost is set by the size of the change rather than the
size of the scan, and it did not move between the cheap query and this one.
The uncached control is the same story from the other side: at 59 ms it is not
stale, it is just slow, and every one of those milliseconds is work the database
repeats on every read.
Comparing against a fixed refresh period alone would be unfair, so the lab also runs
Readyset's shallow cache with ADAPTIVE. Each entry's refresh period then moves
between 10% and 100% of the configured value. The cache hashes each refreshed result,
shrinks the period when the value changed, and grows it when it did not.
Adaptive refresh did engage: across the three runs the vote-count entry recorded
197 refreshes that found a change against 199 that did not, an almost exactly even
split. Adaptation has nothing to bite on in that case, because the shrink and the
grow are the same size and cancel, and the staleness reflects it: 2.29 s against 2.68 s, an improvement
of about 15%.
Plotted per write, the two time-based lanes wander over the same range. The
maintained view sits three orders of magnitude below both, on every write rather than
on average:
Deleting a hot key produces one cache miss per reader in flight, all at the same
instant, all issuing the query to the database the cache was supposed to
protect.
We put 32 readers on one story and wrote to it once every ten seconds, counting with
MySQL's own Com_select so the harness could not inflate the number.
| Read path | SELECTs in the write second | In a quiet second | Increase |
|---|
| look-aside, corrected invalidator | 66 | 2 | 33x |
| Readyset shallow, fixed refresh | 2 | 2 | none |
| Readyset shallow, adaptive refresh | 2 | 2 | none |
| Readyset deep (IVM) | no write-correlated increase | | none |
60 s per arm, one write every 10 s. Com_select is MySQL's own counter.
Sixty-six is 32 readers times the two queries a story page needs, plus the couple
of background queries present in a quiet second. One vote
produced thirty-three times the steady query rate, in one second, against the
database the cache exists to shield.
This is what the look-aside cache's half-millisecond freshness advantage costs. It is
fresher because it throws the entry away and asks MySQL again, and asking
MySQL again is the expensive part. Making its connection handling realistic, which is
what closed the gap on the staleness table, did not soften the burst. It made the burst
arrive sooner.
Neither Readyset path shows a spike, for different reasons. The TTL cache never learns
that the write happened, so nothing changes at write time. The deep cache learns
immediately and updates the stored result in place, so there is no entry to refill and
no reader to send upstream.
Everything measured so far ran at one write every seven seconds on the probe row,
which is one invalidation per roughly thirty thousand reads. That is the regime
where a look-aside cache is at its strongest, because a look-aside cache is only
useful in the gap between one invalidation and the next.
So the last measurement holds the readers constant and sweeps the write rate.
Sixteen readers on one row, arms run one at a time so Com_select attributes
cleanly, and the look-aside arm keeps every advantage it had: the invalidation is
still a function call in the writing thread, still one cache key, still no queue
and no second cache to fan out to.
| Writes/sec on the row | Design | Cache hit rate | SELECTs/sec reaching MySQL | Writes behind, p50 | Writes behind, p95 |
|---|
| 0.1 | look-aside, corrected invalidator | 100.0% | 5 | 0 | 0 |
| 0.1 | Readyset shallow, fixed refresh | 100.0% | 2 | 0 | 1 |
| 0.1 | Readyset deep (IVM) | 100.0% | 2 | 0 | 0 |
| 1 | look-aside, corrected invalidator | 99.9% | 35 | 0 | 0 |
| 1 | Readyset shallow, fixed refresh | 100.0% | 2 | 2 | 5 |
| 1 | Readyset deep (IVM) | 100.0% | 2 | 0 | 0 |
| 5 | look-aside, corrected invalidator | 99.5% | 163 | 0 | 0 |
| 5 | Readyset shallow, fixed refresh | 100.0% | 2 | 11 | 23 |
| 5 | Readyset deep (IVM) | 100.0% | 2 | 0 | 0 |
| 20 | look-aside, corrected invalidator | 97.9% | 641 | 0 | 0 |
| 20 | Readyset shallow, fixed refresh | 100.0% | 2 | 45 | 94 |
| 20 | Readyset deep (IVM) | 100.0% | 2 | 0 | 0 |
| 50 | look-aside, corrected invalidator | 94.3% | 1600 | 0 | 1 |
| 50 | Readyset shallow, fixed refresh | 100.0% | 2 | 111 | 235 |
| 50 | Readyset deep (IVM) | 100.0% | 2 | 0 | 1 |
30 s per point, arms run one at a time so Com_select attributes cleanly. The look-aside arm is deliberately at its best case: invalidation in the writing thread, one cache key, no queue and no fan-out.
The two panels are the two different bills a cache can be handed, and each design
pays only one of them.
The left panel is what the database pays: how many SELECTs per second reach MySQL
while a cache is in front of it. The right panel is what the reader pays: how many
writes behind the cached answer is when someone reads it. Both axes are log
scaled, so a straight rising line is a proportional increase, and lower is better
on both. A genuinely free design would be a flat line near the bottom of
each panel.
As the write rate climbs, only one of the three changes is about staleness.
The look-aside cache stays current and sends the bill to the database. Its
upstream load goes from 5 SELECTs per second to 1,600, a 302-fold rise across the
sweep, tracking write rate times reader count almost exactly: 50 writes times 16
readers times the two queries a rebuild needs is 1,600. It is still fresh at 50
writes per second. It is fresh because it is asking MySQL sixteen hundred times a
second about a row whose answer changed fifty times.
Its hit rate over that same sweep goes from 99.99% to 94.27%, and the two readings
of that pair disagree completely:
On the left is what a hit-rate dashboard shows: a 5.7 point drift, which on any
monitoring page reads as a cache doing its job. On the right is the same 5.7 points
expressed as the thing the database actually receives, and it is a rise from 1.6
misses per second to 799, a factor of five hundred. Each of those misses costs two
upstream queries, which is exactly the 1,600 SELECTs per second in the table.
Hit rate is a ratio, and a database is not charged in ratios. At 94% and sixteen
thousand reads per second, the 6% is 799 requests that have to be computed from
scratch, every second, on top of the write traffic that caused them.
The TTL cache holds upstream load flat and pushes the cost onto the reader.
Two SELECTs per second at every write rate, because it never learns that anything
changed. What moves instead is how far behind it is: 2 writes at 1 per second, 11
at 5, 45 at 20, and 111 at 50, with a p95 of 235. A five second refresh window
times fifty writes a second is what that number has to be.
The maintained view does not move on either axis. 100% hit rate, zero writes
behind, and none of the application's reads reaching MySQL at any write rate. The
two SELECTs per second in that column are SELECT VERSION() and a session
variable read, issued by Readyset's own connection to the database. Neither
touches a table. The write side is
doing more work at 50 writes per second than at 0.1, but the work is one delta per
write through a graph, and on this query it does not show up as either staleness or
database load.
A hand-written look-aside cache really is a shade fresher than incremental
view maintenance, and it stays that way as the workload gets busier. It buys that by turning every write into a
burst of reads against the database the cache exists to protect, and the bill grows
with your write rate and your reader count at the same time.
Incremental view maintenance keeps the stored result of a query up to date by
applying each change to that result, rather than recomputing the query or
discarding the result. A write becomes a delta, the delta flows through the
relational operators of the query, and the stored answer is rewritten in place. A
COUNT node receives "one more vote for story 1" and emits "the count for story 1
went from 7 to 8". There is no invalidation step, because nothing is deleted.
Incremental view maintenance has decades of literature behind it, and memory is
what stopped it replacing caches. A maintained view is the whole answer set, so
materializing every query an application runs costs more memory than the database.
Streaming systems capped that by windowing, keeping only recent records, which is
useless for an application that has to serve a four-year-old story as fast as this
morning's.
In October 2018 a group at MIT CSAIL published
Noria: dynamic, partially-stateful data-flow for high-performance web
applications at the 13th
USENIX Symposium on Operating Systems Design and
Implementation,
the peer-reviewed systems conference usually shortened to OSDI.
Noria is a database backend that compiles an application's SQL
queries into a dataflow graph and keeps every one of their results materialized
and current as writes stream in.
The paper builds on incremental view maintenance rather than inventing it. Its
contribution is partially stateful dataflow, the
mechanism that makes maintaining every query affordable enough to replace a cache
rather than sit beside one. Readyset is the production descendant of that work.
The project's own history file records the lineage: the codebase "builds on the
Noria project, an open-source research prototype built by a team of grad students,
post-docs, professors, and research affiliates at the MIT Parallel and Distributed
Operating Systems (PDOS) lab, of which ReadySet's founding team was a part."
Partially stateful dataflow works like this. Operators are allowed to be
incomplete: an operator holds only the entries that have actually been read, and
treats a missing entry as a hole to fill on demand. A read for an absent key
issues an upquery, which travels backwards up the dataflow graph to the
operators that can recompute that entry, and the response flows forward along the
normal path to fill the hole. Under memory pressure an operator evicts an entry
and sends an eviction notice downstream, so everything derived from it is dropped
rather than left quietly out of date.
Memory therefore tracks the working set instead of the table. In the paper's Lobsters measurements, partial state cut
the state that could not be evicted to 73 MB, against 789 MB for full
materialization over 137 MB of base tables.
Our lab shows the same shape. Reading K distinct story pages and asking Readyset
what it is holding, via readyset_reader_state_size_bytes:
| Distinct story keys read | Deep cache state | Bytes per key | Share of base tables |
|---|
| 0 | 0 KB | 0 | 0.00% |
| 100 | 45 KB | 464 | 0.22% |
| 1,000 | 453 KB | 464 | 2.17% |
| 5,000 | 2.2 MB | 464 | 10.84% |
| 20,000 | 8.9 MB | 464 | 43.37% |
| 40,000 | 17.7 MB | 464 | 86.74% |
40,000 stories exist. Base tables are 20.4 MB of data in MySQL. Metric: readyset_reader_state_size_bytes.
464 bytes per key, flat across three orders of magnitude, and nothing held for keys
nobody asked for. Read a hundred story pages and the caches hold 45 KB against
20.4 MB of base tables. Read all 40,000 and they hold 17.7 MB, still under the base
tables, which is the case partial state does nothing for because there is nothing
partial about it any more.
The practical version: a deep cache is sized by the working set, the same rule
already used for Redis.
A query is cached automatically when adding the cache needs no application change
and keeping it correct needs none either. Readyset gives both. It speaks the MySQL
and Postgres wire protocols, so the application connects with its existing driver,
and a cache is one statement:
CREATE CACHE FROM
SELECT s.id, s.title, u.username
FROM stories s JOIN users u ON u.id = s.author WHERE s.id = 2;
The caching is automatic because the invalidation is automatic. Readyset
keeps each cached result current with incremental view maintenance, driven by
the MySQL binlog or the Postgres write-ahead log, so there is no invalidation
step for the application to write. A caching layer that stores results and hands
back an invalidation problem has automated the read path and left the write path
alone. Teams comparing SQL query caching tools for MySQL usually weigh hit rates
and latency, and the more useful question is what each tool requires in the
write path.
Incremental view maintenance is eventually consistent. The
Noria paper states the
guarantee this way: if writes quiesce, all external views eventually hold results
that are the same as if the queries had been executed directly against the base
tables. Under two milliseconds is short, and it is still not zero and not a
transaction, so a read-your-own-writes path belongs on the database rather than
behind any cache, this one included.
Accepting that window is a design decision, and it is the same one already being
made with a TTL, except that the window is milliseconds instead of seconds and it
does not have to be chosen or tuned.
The mapping from a write to the cached answers it falsified is a graph, and
nothing in application code validates that graph. Four out
of five projects in the survey reached the same conclusion and took the TTL, which
trades correctness for a window.
Partial state is what makes replacing invalidation practical. On our schema it
bought this: on a cheap query, a maintained view
sat 1.66 ms behind the database and a correctly written look-aside cache beat it,
at 1.11 ms, while a TTL cache sat 2.68 s behind. On a query expensive enough to be
worth caching, the same look-aside cache sat 42 ms behind and the maintained view
did not move from 1.48 ms, because one design recovers by recomputing and the
other by applying a delta.
The look-aside cache also paid for its freshness on both queries with a burst of
66 queries into MySQL after every write. The maintained view produced no burst,
needed no window chosen or tuned, and required no invalidation code, because in
that design there is nothing to invalidate. The three-rule invalidator, meanwhile,
is still serving the wrong author name.
For how the dataflow engine maintains a cached result, see
deep caching and How Readyset
Speeds Up Queries with Streaming
Dataflow.
For the TTL model and when it fits better, see
shallow caching, and the
CREATE CACHE reference for the statement
itself.
Readyset Team
