"I think now caching is probably best understood as a tool for making software simpler" - that's cute. Caching might be beneficial for many cases, but if it doesn't do one thing then this is simplifying software. There's that famous quote "There are only two hard things in Computer Science: cache invalidation and naming things.", and, sure, it's a bit ironical, but there's some truth in there.
"Two programs could have similar behaviour but structured very differently, the difference being that one utilizes caching as an abstraction and one explicitly has the concept of different tiers of storage."
The author is comparing "off-the-shelf" caching with custom caching. They're coming from the assumption that you must be caching somehow and arguing that the word "caching" should be understood to mean only particular approaches to the general idea of caching. And obviously the whole point of the general idea is to optimize things.
> There's that famous quote "There are only two hard things in Computer Science: cache invalidation and naming things.", and, sure, it's a bit ironical, but there's some truth in there.
The joke form of this quote goes along the lines of:
There are only two hard things in Computer Science: cache
invalidation, naming things, and off-by-one errors.
Caching is simple, yes. The hard part is in the last word, invalidation. Even that is manageable for a single process. But as soon as you have multiple (threads / processes / nodes / data centers) updating the data, it does get quite complex, pretty fast.
Likewise, naming things is simple as long as you alone, or a in a small team. But as soon as there are multiple organizations with all their own traditions, it gets tricky. Just witness the eternal flame wars about camelCase, PascalCase, snake_case, kebab-case, and UPPER_CASE. It is almost as hopeless culture clash as Emacs vs Vi vs PowerPoint...
(I leave the off-by-one errors as an exercise for the reader)
I'd say this is not the "naming things" that's hard. Beyond picking a common identifier format in the team, there are at least two dimensions that are much harder:
- The language dimension - choice of words, that are good enough for the purpose, and not confusing. For example, "Manager" is as ambiguous as it gets, it can mean many thing, except we've been using it long enough that there's a more specific shape of meaning[0] for that word in code/program architecture contexts - so you still would use it instead of, say "Coordinator", which would raise all kinds of questions that "Manager" no longer does.
- The epistemological dimension - whether the word you chose correctly names the concept you meant, and whether the concept you meant is actually the right one to describe the thing you're trying to describe. Ultimately, this is the hard thing at the root of philosophy. In practice, it manifests like e.g. choice between digging into some obscure branches of mathematics to correctly name the thing "endofunctor" or something, or calling it "Square" and saying "fuck it, we'll clarify the exceptions in the comments".
--
[0] - I mean "more specific" in the sense it's distinct from the other meanings and somewhat narrow - but still it's fuzzy as heck and you can't describe it fully in words; it's basically tacit knowledge.
I try to name things descriptively in simple terms and often end up with NamesAboutThisLong, once they get too long i know the thing is doing too much and some refactoring is needed for readability.
I also avoid letting the reader make assumptions. HasPlayerJumpedRecently is bad. What does recently mean? HasPlayerJumpedInLastTenMs is better, even if it's a bit long...Which highlights that it should probably be refactored into a more flexible value; MsSincePlayerLastJumped.
If you arent assuming a time var wth Ms is milliseconds you aren't doing games dev so that one slides with me.
Wow cool, you just summed up something I’ve found myself doing subconsciously in the past few years. Thanks!
I use to be quite fond of short identifiers, especially ones the make the signs “line up”… until I worked with code long enough that I forgot what I did and had to read it again.
That's a great example. Personally, even beyond gamedev, units are an exception for me - they need to be somewhere, whether in type or in identifier name (or ideally both), or else bad things happen.
But that's what I meant by the epistemological aspect - what is "recently"? Still, "LastTenMs" is arguably even worse - why ten? Did you really mean "since last frame"? Then say "SinceLastFrame". Did you mean "since 2x update time delta"? Then maybe make a PlayerJumpCooldown constant, but then maybe it's not about cooldowns, so... here's when I'd probably say screw this, let's just track MsSincePlayerLastJumped and add a HasPlayerJumpedRecently() -> bool as a helper, with a fat interface comment explaining what "recently" means - and go back to talk with the game designers to give a more specific name for the "recently" thing here.
Point being, this is deceptively hard - doubly so because going all perfectionist about it is also bad.
I admit my example is slightly contrived and LastTen still raises questions re frames and time handling, especially as its so small, oops! Lets pretend i said LastHundred and its using a framerate independent method.
If i were to helperise it with a bool I'd use the intent for the bool, CanPlayerJumpAgain or something (again...contrived example).
I figured the naming issue is deciding how much context. A name might begin inside an organization but need to endure a wider area. If you make all names so long and context-free that they can work in any context, they become unwieldy. Also it can be hard to realize some of the implicit context and what needs to be differentiated with the name. Where server used to suffice, now you need server-a and server-b.
Even caching is not simple as the resources get consumed and you need an eviction policy. Like in a Maven cache, keep no more than one old version around of library to allow for upgrade windows.
All software has to name things, and count. Caching (including invalidation) is best understood as a liability. If you can foist it off on your CPU and OS and DB, good for you. Programming whatever you're actually trying to get done is already hard enough.
They're not hard but I will say that when I was writing an app that was using both JavaScript and Julia, I kept getting off-by-one errors because Julia starts at 1 instead of 0.
Really the only time in my entire professional career that off-by-one errors have actually given me headaches.
I think that is from a time when popular programming languages varied in their behavior and also when people were writing for loops with incrementation all the time.
A lot of languages have just settled on zero indexing, and many now have some variation of for/each or for/of that would eliminate a lot of potential ways to encounter this error.
Yeah, I mostly will do map/reduce/filter when possible, and obviously in those cases indexes don’t matter. It could start at index 12345 for all I care with that stuff.
Occasionally, though, I need to use the same index across multiple items, there’s not a trivial means in which to zip, and at that point I have to use an old school for loop. That’s when the 1-index vs 0-index bites me.
We use caching a lot, anything that gets cached can only be written by one service each. The writing services emit cache invalidation messages via SNS that cache users must listen to via SQS, to clear/update their cache.
Alternatively we cache stuff with just a TTL, when immediate cache invalidation is not important.
If there are no real consequences for reading stale data, and your writes are infrequent enough, then indeed you're lucky and have a relatively simple problem.
You don’t support read-your-own-write and your cache data might be stale for arbitrarily long. These relaxed consistency constraints make caching a lot easier. If that’s acceptable to your use cases then you’re in a great place! If not… well, at scale you often need to find a way for it to be acceptable anyway
Does SQS guarantee delivery to all clients? If it does then that’s doing a lot of heavy lifting for you.
If it doesn’t guarantee delivery, then I believe you will at some point have a client that reads a cached value thinking it’s still valid because the invalidation message got lost in the network.
> anything that gets cached can only be written by one service each
How do you guarantee it's only written by one service each? Sounds like locking across network boundaries, which is not easy.
> The writing services emit cache invalidation messages via SNS that cache users must listen to via SQS
SNS and SQS are both nontrivial services (at least you don't have to build / maintain them I suppose) that require training to use effectively and avoid any possible footguns
I think you're underestimating the complexity in your own solution, and you're probably lucky that some of the harder problems have already been solved for you.
If you don't understand how and why and when eventual consistency is a problem, you will never understand why cache invalidation is hard.
By the sound of your example, you only handle scenarios where naive approaches to cache invalidation serve your needs, and you don't even have to deal with problems caused by spikes to origin servers. That's perfectly fine.
Others do. They understand the meme. You can too if you invest a fee minutes reading up on the topic.
That's because relying on a TTL simplifies the concept of caching, and makes invalidation trivial, and also inflexible.
It's used in DNS, which already was an example here. There is no way to be sure clients see an updated value before end of TTL. As a result, you have to use very conservative TTLs. It's very inefficient.
> Think about all those times your program isn't building and `make clean` fixes it.
I don't think that's a good example. I've worked with more than 20 different build tools by now, and I cannot recall a single instance where the problem actually came down to cache invalidation. Every time I dug into it, the real cause was something else: a mistake in the build script, an incorrectly declared dependency, or something similar.
So when you say "think about all those times", not a single such time comes to my mind!
I think the idea is that if make clean allows the build to complete correctly, then the underlying issue is that the "mistake in the build script, incorrectly declared dependency, or similar" was causing the cached build results to not be invalidated when they should have.
That literally IS cache invalidation. Incremental build systems are caching previous artefacts. They're supposed to invalidate the artefact if a dependency changes. But you forgot to declare the dependency... so it doesn't get invalidated when it should.
In my experience, the larger the software you write, the truer these become. At some point all obvious names will have collisions, and getting caching right is crucial to do but difficult to achieve because it transcends the entire stack.
You could group these two things into "getting the data model right" as the single hard thing, perhaps that rings more true to you :)
It's a little bit tongue in cheek; no one is seriously suggesting it's harder than P=NP or the problem of consciousness. But there's something a bit "death and taxes" to the inevitability that any large enough project is going to have some corner cases involving these old chestnuts.
Heck you can probably prove that any system for naming things is either inconsistent or incomplete.
Namings things is of course a bit tongue in cheek. But cache invalidation is hard. For example, allegedly MESI is one of the hardest things to validate in processor design.
For "only two hard problems," read "two candidates for among the hardest problems (but we feel strongly that these are indeed good candidates)," or something along those lines, more or less.
It's also possible that these used to be the only two hard problems at the time the aphorism was first recorded, but the underlying state of the world has changed since then and the aphorism, as recorded, is no longer current.
There is a secret technique, called content-addressing[1], which elegantly solves both of them at once.
A lot of people haven't caught on, and try to cache things using ambiguous names, hence the struggle to invalidate their caches when the meaning changes.
[1] This can be applied even if you don't know the content yet; you just have to unambiguously name the inputs to the function that produces it. You might not know what all the inputs are, and then you have to start adding stuff like "unknown-unknown-2025-07-03T16", but it'll still basically work.
Really? Have you tried building any substantial program that makes use of caching and succeeded in invalidating the cache both correctly and efficiently? It's not all about simple things like disk access, caching is also useful in software that models complex hardware where properties depend on multitudes of interconnected calculated values that are time consuming to calculate and where you cannot predict which ones the client will ask for next.
I agree with you, but you are omitting a key aspect of the problem which makes this hard. If you have a single server serving from a local sqlite database, caching and invalidating the cache is trivially easy.
It becomes way more difficult when you have N servers all of which could potentially serve the same data. Local caches could then, yes easily become stale, and even if you have a propagation mechanism, you couldn't guarantee against network failures or latency issues.
But suppose you have an HA redis instance that you store your cached data in. Even with a write-through cache, you basically need to implement a 2-phase commit to ensure consistency.
See the thread below. Caches only become stale if you refuse to implement any sort of push architecture. And even then, frequent batch-polling with etags will quickly resolve it. (eg right after you used N entries, poll to see which of the N have changed).
Bloom filters, Prolly trees etc can speed the batch polling up. But push architecture obviates the need for it prevents caches from being stale, it’s called eventual consistency.
(Well, of course unless there is a network partition and you can’t communicate with the machine holding the actual source of truth then yeah, your local cache will be stale. And to catch up on missed updates you will need to request all updates since a certain marker you saved. If the upstream had a ton of updates since your marker and can’t send the entire history since your marker then you might have to purge your cache for that specific table / collection, yeah.).
I would love it if I could over-withdraw money from my bank account by having someone on the other side of the country take out money from my account at an ATM at the exact time as me, due to the fact that the bank's storage system was eventually consistent, but that's not the case.
Pretty sure that when it comes to write transactions, such as bank transactions, you want them to be executed on a source of truth with enforces consistency, not eventual consistency. Any client software should not be trusted -- especially one written by a silly programmer who uses a cache as the source of truth.
Your implementations are not cache systems: they are key-value store abstractions which can be used for caching. There is a simpler one in most languages (IIRC, named "hashes" in PHP).
Caching becomes hard when such a stores are used in distributed or concurrent contexts.
An example: imagine Qcache being used when fetching data from an SQL database. And data in the database changes with a direct SQL query from another process.
How will your key-value store know that the value in it is stale and needs refreshing?
Yes, they are cache systems. And as you say, they can be used for caching.
Caching systems know when something needs updating several ways. One is pubsub: When the information is loaded from the cache, you want to set up a realtime websocket or webhook for example, to reflect any changes since the cached info was shown. If you can manage to have a server running, you can simply receive new data (deltas) and update your cached data — in that case you can even have it ready and never stale by the time it is shown.
If you can’t run a server and don’t want to reveive pushes then another approach simply involves storing the latest ordinal or state for EACH cached item locally (e-tags does this) and then before rendering (or right after you do) bulk-sending the tags and seeing what has been updated, then pulling just that. The downside is that you may have a flash of old content if you show it optimistically.
If you combine the two methods, you can easily get an up-to-date syndication of a remote mutable data store.
My whole framework is built around such abstractions, to take care of them for people.
We can agree to disagree on this being a "caching system" and it "knowing when something needs updating" (from the API, I am guessing it's a "set" method).
Phrases like "simply" and "never stale" are doing a lot of heavy lifting. Yet you haven't answered a very simple question I posted above: how would Q_Cache structure handle a direct SQL write query from another process on the database it is being used as a cache for?
SQL databases don't run websockets to external servers, nor do they fire webhooks. If you are running a server which you are hitting with every update instead of doing direct SQL on the DB, there's always a small amount of time where a cache user can see stale data before this server manages to trigger the update of the cache.
Simple. Use the principles I said above, for distributed and asynchronous systems.
The SQL server should have a way to do pubsub. It can then notify your PHP webhook via HTTP, or run a script on the command line, when a row changes. It should have an interface to subscribe to these changes.
If your SQL data store lacks the ability to notify others that a row changed, then there’s your main problem. Add that functionality. Make a TRIGGER in SQL for instance and use an extension.
If MySQL really lacks this ability then just put node.js middleware in front of it that will do this for you. And make sure that all mysql transactions from all clients go through that middleware. Now your combined MySQL+Node server is adequate to help clients avoid stale data.
As I already said, if you for some reason refuse to handle push updates, then you have to store the latest row state (etags) in your PHP cache (apcu). And then when you access a bunch of cached items on a request, at the end collect all their ids and etags and simply bulk query node.js for any cached items that changed. You can use bloom filters or merkle trees or prolly trees to optimize the query.
You're just pushing much of the complexity to that notification layer.
What if an SQL update changes a million rows, and you had cached the sum of those million rows? Should it send a million notifications? Should it re-run the sum for you? What if it's a complex operation and it takes a while to re-compute, and another update arrives before the re-compute finishes?
And of course, you will always have some partitions, so you will occasionally need to re-query the data anyway and re-establish any kind of pubsub system. And the complexity in efficiently reconciling two views of a large amount of data is a major issue, that you are just brushing off as "you can do various things to maybe optimize the query".
Yes, if you really want to show something as ambitious as a sum of a million rows, then you should absolutely move to an event-based, push-based architecture. Because once you’ve calculated the sum, the least work you would need to do is to periodically look at batches of UPDATES to rows, and update your sum based on that (rather than, say, running SUM again on the whole entire table). You can either pull a digest periodically, or — you can handle incremental updates by listening for pushes.
All the difficulties you cite, including the “optimizations” I mentioned, stem from not using push, and insisting on periodically polling something.
If you step back, your whole problem is that you are using a system that only has pull and not push architecture. You’re trying to put a bandaid on that core fact. You chose a relational database system that you refuse to build extensions for (as opposed to pretty much any other system) in order to insist “nyeh nyeh you havent solved cache invalidation”.
Caching is just one part of sync. The part that stores a non-authoritative, slightly out of date copy locally. And sync, or replication, is just one part of an eventually consistent system. I mean, even MySQL supports replication, so just hook your client up to that protocol (encrypted in transit) and boom, now you can update your cache.
Here’s the thing. If you use any network protocol that is open, eg HTTP, then yea it’s solved. Because you can have webhooks and just spin up a server to handle them, and update your cache. A row is removed? Decrement your sum. A row is added? Increment it.
You are just insisting that “no, our system has to be clunky and we refuse to implement webhooks / websockets / sockets / push / mysql replication client / updates of any kind, now solve it for me to be as good as a system which has push capabilities.”
Well then maybe consider making a sql replication client that would ingest the changes (like most databases, mysql writes to a straming append-only log, before it is compacted). Just parse the log and act on them.
Well, good. Your problem is artificial, choosing tools and scenarios to avoid "push". Your problem isn't with invalidating caches being hard in 2025. I've explained how to do it in both pull and push scenarios. Certainly not "the only hard problems in computer science." And neither is naming!
I’m also not making my own programming language, I’m using PHP. And I’m using MySQL. What is your point?
Are you saying that “invalidating caches is hard… if you insist on using only systems with no way to push updates, and oh if they have a way to push updates then you’re using someone’s library to consume updates so it doesn’t count?”
I will answer your question directly, after having explained the core issue.
Mysql and Postgresql does in fact have push. It is called replication. The protocol is documented. So, much like a webhook with HTTP protocol, you can ingest changes on a table with a php long-running client and then simply update your apcu cache entries if they are still being stored, and matching that row. And all your PHP processes (managed by php-fpm or FrankenPHP or whatever) will benefit from that atomic apcu update.
There is nothing that says only another mysql server can be a mysql replication client.
Boom, solved. Even in your case. Note that the SQL database did in fact expect you to open a socket, and then it writes its log to that socket. That’s all the streaming events you need.
But now you’re gonna say “but but no you cant have a long running PHP client, we’re talking about a shared hosting environment where the host disables your ability to run a long PHP service that opens a socket”. Well, look. Most of the difficultu is that you’re intentionally trying to use the most clunky architectures just to “prove” that “cache invalidation is really hard.”
I wasn't going to say any of that ;) Yes, Postgres does have WAL log you can subscribe to, but you are creating a replicated slave really. There are many nuances to doing that right and you are downplaying how hard that is (it's not about API, it's about ACID).
More importantly, you are pushing all the complex logic to this imaginary DB replication client: your "caching system" is still nothing more than a KV store.
Caching system would be what you described as a response to my example case: your key-value store combined together with the entire mechanism to watch for DB writes (eg with triggers or the replication log) and tie them back to cached values which need to have their lifetime managed.
> caching often does simplify software though when done well
I have to push back here, I think this is objectively untrue. By definition a system or piece of code on where you add a condition where something else happens (cache) that behaves differently than the uncached path increases complexity.
I'm not saying it's wrong to cache things or that they aren't useful, but I think they absolutely are an abstraction and an optimization at the cost of complexity. Good code bases hide complexity from the devs all the time, so it's not a question of whether you can code it away, but rather how difficult is it to troubleshoot the internals of the system.
Caching is a performance improvement. There is no software that requires caching, therefore it is always something being added on top of the business logic that is fundamentally required. As such, a cache is increasing complexity by nature of its existence.
The only scenario where it would simplify software is if a bunch of complex (non-cache) things are being done to improve perf, and a cache would be the simpler solution. But in that case the simplifying step is not adding a cache, it is removing complex things that aren't actually required. After that you add a cache to improve performance (which increases complexity but is worth it for this imagined use-case). But maybe you remove the complex perf shenanigans, and realize that perf is still "good enough" even without a cache, keeping your software even simpler.
CPUs are still a great example for how caching simplifies things.
There's a long history in computer architecture of cores and accelerators that don't have a cache but instead rely on explicitly programmed local scratchpads. They are universally more difficult to program than general purpose CPUs because of that.
I’m sure the CPU designers would love it if they didn’t need several different layers of cache. Or no cache at all. Imagine if memory IOPS were as fast as L1 cache, no need for all that dedicated SRAM on the chip or worry about side channel attacks.
Sure, but we were talking about the perspective of software developers. The hardware designers take on complexity so that the software developer's work can be simpler.
That abstraction is another layer though. And additional layers are additional complexity. So, if you add another layer, the software is less simple than before.
You might need to have caching in your software. I don't doubt that. But there's simply no way it makes the software more simple except if you assume some unfortunate starting point where you could get rid of any high-complex performance optimizations in your existing code by replacing them with a more simple cache solution. But then the statement should be "refactoring makes your code simpler".
Getting cache keys or caching events wrong is easy and a nightmare.
But getting them right can easily cross the boundary of purely optimizing performance towards simplifying public API of something. I think this is true.
I'd imagine an involved example where semantics and caching really start to offer a trade-off.
Imagine that somehow querying the actual meteorological data is quite expensive, and consider this badly written pseudocode (equals sign denoting default parameters):
I know, reality is much more complicated, and using time (seeing it as quasi-continuous) as a caching parameter is already stretching it so far.
Just a stupid example that came to my mind.
I've bitten myself in the ass with caching rasterized reprentations of images more than once, where the input were SVG images or limited formats that convert to SVG.
On top of the other things mentioned (caching always introduces complexity with lifetime tracking, and thus can't make things simple), the article's got it the wrong way around.
When code has abstract interfaces for data access, introducing caching can be simpler (but not simple) by localizing it in the abstraction implementation which has or doesn't have caching.
But it is not an abstraction (you can perfectly well do caching without any abstractions, and it's frequently done exactly that way).
I think you and the article are referring to abstractions over different concerns.
The concern you're talking about is about the actual access to the data. My understanding of the article is that it's about how caching algorithms can abstract the concern of minimising retrieval cost.
So in some ways you're coming at it from opposite directions. You're talking about a prior of "disk by default" and saying that a good abstraction lets you insert cache layers above that, whereas for the author the base case is "manually managing the layers of storage".
Algorithms can't really abstract anything since they are, well, just algorithms (formal descriptions of how a computation should be done).
Looking at the author's examples again, I think most everybody would say that caching is used in both:
if data_id in fast_storage:
return fast_storage.get(data_id)
else:
data = slow_storage.get(data_id)
fast_storage.set(data_id, data)
return data
and
# Uses fast storage or slow storage just like above, but behind the get() method.
return storage.get(data_id)
The first one does not make an abstraction on storage, the second one does, but they are both "caching" data internally.
While there are genericimplementations of caching algorithms and we can consider those abstractions, "caching" is a wider term than those implementations, and is specifically not an abstraction (the fact that there is a caching implementation that abstracts something does not make all caching an abstraction).
Edit: Let me also point out that "abstract the concern of minimising retrieval cost" is not caching — I can say that eg. a simple interface with method FastGet(id) does the former, and it needs not use any caching if the underlying structure is fast enough and eg. directly in memory.
This is correct, I appreciate you for putting it so
coherently :). I think I didn’t make it clear enough in the piece that I’m coming from a stance of fast access being table stakes, and the question being about how that’s accomplished.
"Caching" is an idea of storing a result of an expensive computation in storage that is faster to get from than doing the original computation (in very generic computer terms, computation can be simply fetching from the network or slower local storage).
What you describe as "caching algorithms" are not really caching algorithms, but cached object lifetime management algorithms (LRU, LFU...).
It sounds like you are both trying to redefine what "caching" means (tying it to implementations of particular algorithms), but also what "abstraction" means.
We should be very deliberate with the language we use, and our main goal should be to make it simpler to understand, not harder — I believe you are doing the latter here.
Caching is an optimisation. Sometimes caching can be abstracted away, eg CPU cache or build cache are pretty much abstracted away for a usual web developer. But web page caching is very hard to abstract without any abstraction leaks and weird bugs. And even CPU cache is no longer an abstraction if you deal with very high performance code.
It sounds like they are arguing that when performance matters, you have to know more about caching. Fair enough, you have to know a lot more about things when optimizing. For a lot of cases you can ignore caching because it can be done transparently. You depend on it to some extent because if e.g. every instruction had to be fetched off rotating storage like the old days, it would play a big role in your design. It's just something solved in general for most software to not have to know much about it.
Most optimizations require you to think about how your code is structured, so as a side-effect you make the code more understandable.
In this article, it's cache levels forcing you to separate different types of data because they're accessed at different frequencies. Another example is Rust's borrow checker, whose main purpose is arguably to facilitate both safe and efficient memory management, but which can also be used to enforce invariants that aren't clearly memory-related (e.g. builder pattern, temp files that auto-delete after they're dropped).
These aren't abstractions though. An abstraction is the opposite, hiding structure when it's noisy and making it easier to change. For example, if you already have an architecture in mind and don't want to manually determine how frequently each type of data is accessed, it's better to use a compiler or library that automatically determines what to cache with little to no code or thought on your end; that's abstraction. Similarly, the abstract analogue to Rust's borrow checker is garbage collection, which allows programmers to not think about their data-structures' lifetimes at all. The cost is usually performance and you understand your application less in some ways (although you understand it more in other ways; abstraction hides details but too many details make it hard to see the big picture. Ideally, with abstractions in the right places, you hide only the "unimportant" details in ways that insignificantly affect performance).
Note: the author means that caching can be used as an implementation detail in an (abstracted) storage access system, as opposed to a baseline of having multiple storage systems (fast, medium, slow) and managing them directly.
This was confusing to me – the most obvious way to judge the purpose of a system is to compare with the baseline of not having that system at all, especially in the case of caching where the program is functionally complete and correct without a cache. Anyway, there may not be a right or wrong here. Just tripped me up.
Yes "good" caching - a consistent storage interface - is an abstraction over "bad" caching - multiple different storage interfaces with different speeds. But caching overall is not an abstraction over not having caching.
As can be seen from other comments, people tend to focus on the consistency implications, but something not discussed often in the context of distributed systems is that caches tend to introduce bimodality and metastability [0] [1].
See e.g. DynamoDB for an example of design taking it into account [2].
Let's first get the obvious out of the way: caching is not an abstraction, the "Storage" abstraction is what enables caching to be implemented. If I had to put Caching in a category, I would say that it's an optimization strategy.
But that's not really what the blogpost is about. The issue that it tries to discuss is the fact that this abstraction is often imposed to us, without any way to control its behaviour. That's the examples of the LOAD_NAME in python he points at. Without having a clear understanding of the access patterns the application mostly uses, a caching strategy cannot be well defined, and you'll end up with an inadequate solution.
Optimization isn't separable from abstraction. Abstraction is something that can be implemented in more than one way, while meeting the terms of its contract. That flexibility allows for optimization.
"fast storage" is about performance, your abstraction includes performance elements. If you go that down, then you are optimizing on your abstraction designs. What doesn't have to be wrong, but then don't say that is not optimization.
This article is talking about single-writer, single-reader storage. I think it's correct in that context. Most of the hairy problems with caches don't come up until you're multi-writer, multi-reader.
There is also an important (but often overlooked) detail that you/your application may not be the only user of the cache. At which point caching, indeed, is an optimization via abstraction: when you fetch an X, you are in no position to predict that the next fifty completely unrelated to you requests would also want to fetch the same X, so it should probably be cached to be readily served.
Which is why solving the "I want my data in fast storage as often as possible" problem may be counter-productive on the whole: you ain't the only client of the system; let it breath and server requests from others.
Ousterhout's grad students did work on ramcloud with some research at facebook and Amazon on cache use at scale in complex organizations.
One bit of interesting trivia say for facebook (from memory): if you add all the RAM caches in redis/memcached/disk + db caches to make the thing work at scale, then for about 20-30% more memory you could've had the whole thing in memory 100% of the time.
Even more obvious if you think about the case of hardware-managed caches! The ISA typically exposes some simple cache control instructions (and I guess non-temporal loads/stores?), but apart from that, the actual choice of storage location is abstracted away from you (and your compiler).
I believe this same language use is what makes this article confusing: Redis is not a cache, it is a key value store. Caching is usually implemented using key value stores, but it is not an abstraction (leaky or not).
In RDBMS contexts, index really is a caching mechanism (a cache) managed by the database system (query planner needs to decide when it's best to use one index or another).
But as you note yourself even in these cases where you've got cache management bundled with the database, having too many can slow down (even deadlock) writes so much as the database tries to ensure consistency between these redundant data storage elements.
I was discussing this with someone recently, caching is one of those things that people might do behind the scenes, thinking that it doesn't affect the API but in fact it can create all sorts of issues/complexity.
What? No, caching means a specific thing: keeping a copy of data away from the source of truth, closer to where you want to read it. Caching always makes systems more complex, it never makes things simpler, and it damn sure doesn't serve as any kind of abstraction unless you're redefining what words mean to indulge your technical philosophizing.
What if you have to keep some data closer and away from the source of truth though? Given that constraint, TFA argued that other architectures could do the job but that caching functions as an abstraction.
Sometimes posts are so difficult to read they're hard to respond to. I think I get what they're saying. I think they're saying that they think caching should be simple, or at least, that it should be obvious how you should cache in your particular situation such that you don't need things like algorithms. But that argument is kind of nonsense, because really everything in software is an algorithm.
Caching is storing a copy of data in a place or way that it is faster to retrieve than it would be otherwise. Caching is not an abstraction; it is a computer science technique to achieve improved performance.
Caching does not make software simpler. In fact, it always, by necessity, makes software more complex. For example, there are:
- Routines to look up data in a fast storage medium
- Routines to retrieve data from a slow storage medium and store them in a fast storage medium
- Routines to remove the cache if an expiration is reached
- Routines to remove cache entries if we run out of cache storage
- Routines to remove the oldest unused cache entry
- Routines to remove the newest cache entry
- Routines to store the age of each cache entry access
- Routines to remove cache entries which have been used the least
- Routines to remove specific cache entries regardless of age
- Routines to store data in the cache at the same time as slow storage
- Routines to store data in cache and only write to slow storage occasionally
- Routines to clear out the data and get it again on-demand/as necessary
- Routines to inform other systems about the state of your cache
- ...and many, many more
Each routine involves a calculation that determines whether the cache will be beneficial. A hit or miss can lead to operations which may add or remove latency, may or may not run into consistency problems, may or may not require remediation. The cache may need to be warmed up, or it may be fine starting cold. Clearing the cache (ex. restarts) may cause such a drastic cascading failure that the system cannot be started again. And there is often a large amount of statistics and analysis needed to optimize a caching strategy.
These are just a few of the considerations of caching. Caching is famously one of the hardest problems in computer science. How caching is implemented, and what it affects, can be very complex, and needs to be considered carefully. If you try to abstract it away, it usually leads to problems. Though if you don't try to abstract it away, it also leads to problems. Because of all of that, abstracting caching away into "general storage engine" is simply impossible in many cases.
Caching also isn't just having data in fast storage. Caching is cheating. You want to provide your data faster than actually works with your normal data storage (or transfer mechanism, etc). So you cheat, by copying it somewhere faster. And you cheat again, by trying to figure out how to look it up fast. And cheat again, by trying to figure out how to deal with its state being ultimately separate from the state of the "real" data in storage.
Basically caching is us trying to be really clever and work around our inherent limitations. But often we're not as smart as we think we are, and our clever cheat can bite us. So my advice is to design your system to work well without caching. You will thank yourself later, when you finally are dealing with the bug bites, and realize you dodged a bullet before.
"I think now caching is probably best understood as a tool for making software simpler" - that's cute. Caching might be beneficial for many cases, but if it doesn't do one thing then this is simplifying software. There's that famous quote "There are only two hard things in Computer Science: cache invalidation and naming things.", and, sure, it's a bit ironical, but there's some truth in there.
"Two programs could have similar behaviour but structured very differently, the difference being that one utilizes caching as an abstraction and one explicitly has the concept of different tiers of storage."
The author is comparing "off-the-shelf" caching with custom caching. They're coming from the assumption that you must be caching somehow and arguing that the word "caching" should be understood to mean only particular approaches to the general idea of caching. And obviously the whole point of the general idea is to optimize things.
It's a rhetorical mess
> There's that famous quote "There are only two hard things in Computer Science: cache invalidation and naming things.", and, sure, it's a bit ironical, but there's some truth in there.
The joke form of this quote goes along the lines of:
:-DI rather like the snark of:
there's two hard problems in computer science: we only have one joke and it's not funny.
Apparently⁰ by Philip Scott Bowden¹
⁰ https://martinfowler.com/bliki/TwoHardThings.html
¹ https://x.com/pbowden/status/468855097879830528
Just remembered another one: there are 10 types of people in the world: those who understand binary and those who don't. :)
Which leads to
> I don't see what's so hard about DNS, it's just cache invalidation and naming things.
Oh that's gooood. Got a cite or is it yours?
... and avoiding off-by-one errors.
My favorite variation only really works in text:
There are three hard problems in Computer Science:
1) Cache invalidation
2) Naming th3) Concurings
rency
4) Off-by-one errors
Caching is simple, yes. The hard part is in the last word, invalidation. Even that is manageable for a single process. But as soon as you have multiple (threads / processes / nodes / data centers) updating the data, it does get quite complex, pretty fast.
Likewise, naming things is simple as long as you alone, or a in a small team. But as soon as there are multiple organizations with all their own traditions, it gets tricky. Just witness the eternal flame wars about camelCase, PascalCase, snake_case, kebab-case, and UPPER_CASE. It is almost as hopeless culture clash as Emacs vs Vi vs PowerPoint...
(I leave the off-by-one errors as an exercise for the reader)
I'd say this is not the "naming things" that's hard. Beyond picking a common identifier format in the team, there are at least two dimensions that are much harder:
- The language dimension - choice of words, that are good enough for the purpose, and not confusing. For example, "Manager" is as ambiguous as it gets, it can mean many thing, except we've been using it long enough that there's a more specific shape of meaning[0] for that word in code/program architecture contexts - so you still would use it instead of, say "Coordinator", which would raise all kinds of questions that "Manager" no longer does.
- The epistemological dimension - whether the word you chose correctly names the concept you meant, and whether the concept you meant is actually the right one to describe the thing you're trying to describe. Ultimately, this is the hard thing at the root of philosophy. In practice, it manifests like e.g. choice between digging into some obscure branches of mathematics to correctly name the thing "endofunctor" or something, or calling it "Square" and saying "fuck it, we'll clarify the exceptions in the comments".
--
[0] - I mean "more specific" in the sense it's distinct from the other meanings and somewhat narrow - but still it's fuzzy as heck and you can't describe it fully in words; it's basically tacit knowledge.
I try to name things descriptively in simple terms and often end up with NamesAboutThisLong, once they get too long i know the thing is doing too much and some refactoring is needed for readability.
I also avoid letting the reader make assumptions. HasPlayerJumpedRecently is bad. What does recently mean? HasPlayerJumpedInLastTenMs is better, even if it's a bit long...Which highlights that it should probably be refactored into a more flexible value; MsSincePlayerLastJumped.
If you arent assuming a time var wth Ms is milliseconds you aren't doing games dev so that one slides with me.
Wow cool, you just summed up something I’ve found myself doing subconsciously in the past few years. Thanks!
I use to be quite fond of short identifiers, especially ones the make the signs “line up”… until I worked with code long enough that I forgot what I did and had to read it again.
That's a great example. Personally, even beyond gamedev, units are an exception for me - they need to be somewhere, whether in type or in identifier name (or ideally both), or else bad things happen.
But that's what I meant by the epistemological aspect - what is "recently"? Still, "LastTenMs" is arguably even worse - why ten? Did you really mean "since last frame"? Then say "SinceLastFrame". Did you mean "since 2x update time delta"? Then maybe make a PlayerJumpCooldown constant, but then maybe it's not about cooldowns, so... here's when I'd probably say screw this, let's just track MsSincePlayerLastJumped and add a HasPlayerJumpedRecently() -> bool as a helper, with a fat interface comment explaining what "recently" means - and go back to talk with the game designers to give a more specific name for the "recently" thing here.
Point being, this is deceptively hard - doubly so because going all perfectionist about it is also bad.
I admit my example is slightly contrived and LastTen still raises questions re frames and time handling, especially as its so small, oops! Lets pretend i said LastHundred and its using a framerate independent method.
If i were to helperise it with a bool I'd use the intent for the bool, CanPlayerJumpAgain or something (again...contrived example).
I figured the naming issue is deciding how much context. A name might begin inside an organization but need to endure a wider area. If you make all names so long and context-free that they can work in any context, they become unwieldy. Also it can be hard to realize some of the implicit context and what needs to be differentiated with the name. Where server used to suffice, now you need server-a and server-b.
Even caching is not simple as the resources get consumed and you need an eviction policy. Like in a Maven cache, keep no more than one old version around of library to allow for upgrade windows.
Don't bring a PowerPoint to a Vi/Emacs fight...
(You forgot off-by-1 errors.)
All software has to name things, and count. Caching (including invalidation) is best understood as a liability. If you can foist it off on your CPU and OS and DB, good for you. Programming whatever you're actually trying to get done is already hard enough.
Off by 1-errors is not part of the original quote, but is just a later addon to make it funny.
They also tend not to be very hard.
Except when they're part of some base assumptions in the domain or dozen of layers of abstractions below you. They are hard to prevent from happening.
They're not hard but I will say that when I was writing an app that was using both JavaScript and Julia, I kept getting off-by-one errors because Julia starts at 1 instead of 0.
Really the only time in my entire professional career that off-by-one errors have actually given me headaches.
I think that is from a time when popular programming languages varied in their behavior and also when people were writing for loops with incrementation all the time.
A lot of languages have just settled on zero indexing, and many now have some variation of for/each or for/of that would eliminate a lot of potential ways to encounter this error.
Yeah, I mostly will do map/reduce/filter when possible, and obviously in those cases indexes don’t matter. It could start at index 12345 for all I care with that stuff.
Occasionally, though, I need to use the same index across multiple items, there’s not a trivial means in which to zip, and at that point I have to use an old school for loop. That’s when the 1-index vs 0-index bites me.
If you omit the off-by-1 error from the two hard things joke, you're still off by 1, right? Kind of?
If you have a system with "slow storage", caching is a way to optimize that to "storage that is sometimes fast".
If you have a system with "slow storage" and "fast storage", caching is a way to abstract that away to just "storage".
The author is arguing that the latter is the default way we should think about the concept of caching, which is a valid opinion to have.
I never understood this meme.
We use caching a lot, anything that gets cached can only be written by one service each. The writing services emit cache invalidation messages via SNS that cache users must listen to via SQS, to clear/update their cache.
Alternatively we cache stuff with just a TTL, when immediate cache invalidation is not important.
Where‘s the struggle?
> Where‘s the struggle?
If there are no real consequences for reading stale data, and your writes are infrequent enough, then indeed you're lucky and have a relatively simple problem.
You don’t support read-your-own-write and your cache data might be stale for arbitrarily long. These relaxed consistency constraints make caching a lot easier. If that’s acceptable to your use cases then you’re in a great place! If not… well, at scale you often need to find a way for it to be acceptable anyway
Does SQS guarantee delivery to all clients? If it does then that’s doing a lot of heavy lifting for you.
If it doesn’t guarantee delivery, then I believe you will at some point have a client that reads a cached value thinking it’s still valid because the invalidation message got lost in the network.
Eventually. The problem is that eventually delivering that message will result in clients assuming that it will always be the same, when it’s not.
> Where‘s the struggle?
> anything that gets cached can only be written by one service each
How do you guarantee it's only written by one service each? Sounds like locking across network boundaries, which is not easy.
> The writing services emit cache invalidation messages via SNS that cache users must listen to via SQS
SNS and SQS are both nontrivial services (at least you don't have to build / maintain them I suppose) that require training to use effectively and avoid any possible footguns
I think you're underestimating the complexity in your own solution, and you're probably lucky that some of the harder problems have already been solved for you.
> I never understood this meme.
If you don't understand how and why and when eventual consistency is a problem, you will never understand why cache invalidation is hard.
By the sound of your example, you only handle scenarios where naive approaches to cache invalidation serve your needs, and you don't even have to deal with problems caused by spikes to origin servers. That's perfectly fine.
Others do. They understand the meme. You can too if you invest a fee minutes reading up on the topic.
Here's one: everybody invalidating and refreshing their cache at the same time can cause a thundering herd problem.
I've never really understood it either. In my experience, in order for a cache to be a possible solution to a given problem at all, you must either:
1. Be content with/resilient to the possibility of stale data.
2. Gatekeep all reads and writes (for some subset of the key space) through a single thread.
That's basically it.
That's because relying on a TTL simplifies the concept of caching, and makes invalidation trivial, and also inflexible.
It's used in DNS, which already was an example here. There is no way to be sure clients see an updated value before end of TTL. As a result, you have to use very conservative TTLs. It's very inefficient.
You can’t be sure even after the TTL to be fair.
I never understood about cache invalidation or naming things
Both are not that difficult, honestly.
Aren’t there a lot harder things out there
Cache invalidation isn't hard in theory. It's just one of those things that is very easy to get subtly wrong and difficult to test.
Think about all those times your program isn't building and `make clean` fixes it.
> Think about all those times your program isn't building and `make clean` fixes it.
I don't think that's a good example. I've worked with more than 20 different build tools by now, and I cannot recall a single instance where the problem actually came down to cache invalidation. Every time I dug into it, the real cause was something else: a mistake in the build script, an incorrectly declared dependency, or something similar.
So when you say "think about all those times", not a single such time comes to my mind!
I think the idea is that if make clean allows the build to complete correctly, then the underlying issue is that the "mistake in the build script, incorrectly declared dependency, or similar" was causing the cached build results to not be invalidated when they should have.
> an incorrectly declared dependency
That literally IS cache invalidation. Incremental build systems are caching previous artefacts. They're supposed to invalidate the artefact if a dependency changes. But you forgot to declare the dependency... so it doesn't get invalidated when it should.
In my experience, the larger the software you write, the truer these become. At some point all obvious names will have collisions, and getting caching right is crucial to do but difficult to achieve because it transcends the entire stack.
You could group these two things into "getting the data model right" as the single hard thing, perhaps that rings more true to you :)
It's a little bit tongue in cheek; no one is seriously suggesting it's harder than P=NP or the problem of consciousness. But there's something a bit "death and taxes" to the inevitability that any large enough project is going to have some corner cases involving these old chestnuts.
Heck you can probably prove that any system for naming things is either inconsistent or incomplete.
> no one is seriously suggesting it's harder than P=NP or the problem of consciousness.
Well, I for one feel that "naming things" ultimately boils down to the latter, which may or may not be harder than the former.
Namings things is of course a bit tongue in cheek. But cache invalidation is hard. For example, allegedly MESI is one of the hardest things to validate in processor design.
For "only two hard problems," read "two candidates for among the hardest problems (but we feel strongly that these are indeed good candidates)," or something along those lines, more or less.
It's also possible that these used to be the only two hard problems at the time the aphorism was first recorded, but the underlying state of the world has changed since then and the aphorism, as recorded, is no longer current.
There is a secret technique, called content-addressing[1], which elegantly solves both of them at once.
A lot of people haven't caught on, and try to cache things using ambiguous names, hence the struggle to invalidate their caches when the meaning changes.
[1] This can be applied even if you don't know the content yet; you just have to unambiguously name the inputs to the function that produces it. You might not know what all the inputs are, and then you have to start adding stuff like "unknown-unknown-2025-07-03T16", but it'll still basically work.
Really? Have you tried building any substantial program that makes use of caching and succeeded in invalidating the cache both correctly and efficiently? It's not all about simple things like disk access, caching is also useful in software that models complex hardware where properties depend on multitudes of interconnected calculated values that are time consuming to calculate and where you cannot predict which ones the client will ask for next.
I agree with you, but you are omitting a key aspect of the problem which makes this hard. If you have a single server serving from a local sqlite database, caching and invalidating the cache is trivially easy.
It becomes way more difficult when you have N servers all of which could potentially serve the same data. Local caches could then, yes easily become stale, and even if you have a propagation mechanism, you couldn't guarantee against network failures or latency issues.
But suppose you have an HA redis instance that you store your cached data in. Even with a write-through cache, you basically need to implement a 2-phase commit to ensure consistency.
See the thread below. Caches only become stale if you refuse to implement any sort of push architecture. And even then, frequent batch-polling with etags will quickly resolve it. (eg right after you used N entries, poll to see which of the N have changed).
Bloom filters, Prolly trees etc can speed the batch polling up. But push architecture obviates the need for it prevents caches from being stale, it’s called eventual consistency.
(Well, of course unless there is a network partition and you can’t communicate with the machine holding the actual source of truth then yeah, your local cache will be stale. And to catch up on missed updates you will need to request all updates since a certain marker you saved. If the upstream had a ton of updates since your marker and can’t send the entire history since your marker then you might have to purge your cache for that specific table / collection, yeah.).
I would love it if I could over-withdraw money from my bank account by having someone on the other side of the country take out money from my account at an ATM at the exact time as me, due to the fact that the bank's storage system was eventually consistent, but that's not the case.
Now you're just conflating things.
Pretty sure that when it comes to write transactions, such as bank transactions, you want them to be executed on a source of truth with enforces consistency, not eventual consistency. Any client software should not be trusted -- especially one written by a silly programmer who uses a cache as the source of truth.
Yes, I have. I've actually built a general-purpose cache system. Several, in fact:
Here's one for PHP: https://github.com/Qbix/Platform/blob/main/platform/classes/...
And here is for the Web: https://github.com/Qbix/Platform/blob/dc95bd85fa386e45546b0b...
I also discuss caching in the context of HTTP: https://community.qbix.com/t/caching-and-sessions/192
You should especially start here: https://community.qbix.com/t/qbix-websites-loading-quickly/2...And then you can read about incremental updates: https://community.qbix.com/t/streams-plugin-messages-subscri...
Your implementations are not cache systems: they are key-value store abstractions which can be used for caching. There is a simpler one in most languages (IIRC, named "hashes" in PHP).
Caching becomes hard when such a stores are used in distributed or concurrent contexts.
An example: imagine Qcache being used when fetching data from an SQL database. And data in the database changes with a direct SQL query from another process.
How will your key-value store know that the value in it is stale and needs refreshing?
Yes, they are cache systems. And as you say, they can be used for caching.
Caching systems know when something needs updating several ways. One is pubsub: When the information is loaded from the cache, you want to set up a realtime websocket or webhook for example, to reflect any changes since the cached info was shown. If you can manage to have a server running, you can simply receive new data (deltas) and update your cached data — in that case you can even have it ready and never stale by the time it is shown.
If you can’t run a server and don’t want to reveive pushes then another approach simply involves storing the latest ordinal or state for EACH cached item locally (e-tags does this) and then before rendering (or right after you do) bulk-sending the tags and seeing what has been updated, then pulling just that. The downside is that you may have a flash of old content if you show it optimistically.
If you combine the two methods, you can easily get an up-to-date syndication of a remote mutable data store.
My whole framework is built around such abstractions, to take care of them for people.
We can agree to disagree on this being a "caching system" and it "knowing when something needs updating" (from the API, I am guessing it's a "set" method).
Phrases like "simply" and "never stale" are doing a lot of heavy lifting. Yet you haven't answered a very simple question I posted above: how would Q_Cache structure handle a direct SQL write query from another process on the database it is being used as a cache for?
SQL databases don't run websockets to external servers, nor do they fire webhooks. If you are running a server which you are hitting with every update instead of doing direct SQL on the DB, there's always a small amount of time where a cache user can see stale data before this server manages to trigger the update of the cache.
Simple. Use the principles I said above, for distributed and asynchronous systems.
The SQL server should have a way to do pubsub. It can then notify your PHP webhook via HTTP, or run a script on the command line, when a row changes. It should have an interface to subscribe to these changes.
If your SQL data store lacks the ability to notify others that a row changed, then there’s your main problem. Add that functionality. Make a TRIGGER in SQL for instance and use an extension.
If MySQL really lacks this ability then just put node.js middleware in front of it that will do this for you. And make sure that all mysql transactions from all clients go through that middleware. Now your combined MySQL+Node server is adequate to help clients avoid stale data.
As I already said, if you for some reason refuse to handle push updates, then you have to store the latest row state (etags) in your PHP cache (apcu). And then when you access a bunch of cached items on a request, at the end collect all their ids and etags and simply bulk query node.js for any cached items that changed. You can use bloom filters or merkle trees or prolly trees to optimize the query.
Joel Gustafson had a great article on this and now uses it in gossiplog: https://joelgustafson.com/posts/2023-05-04/merklizing-the-ke...
You're just pushing much of the complexity to that notification layer.
What if an SQL update changes a million rows, and you had cached the sum of those million rows? Should it send a million notifications? Should it re-run the sum for you? What if it's a complex operation and it takes a while to re-compute, and another update arrives before the re-compute finishes?
And of course, you will always have some partitions, so you will occasionally need to re-query the data anyway and re-establish any kind of pubsub system. And the complexity in efficiently reconciling two views of a large amount of data is a major issue, that you are just brushing off as "you can do various things to maybe optimize the query".
Yes, if you really want to show something as ambitious as a sum of a million rows, then you should absolutely move to an event-based, push-based architecture. Because once you’ve calculated the sum, the least work you would need to do is to periodically look at batches of UPDATES to rows, and update your sum based on that (rather than, say, running SUM again on the whole entire table). You can either pull a digest periodically, or — you can handle incremental updates by listening for pushes.
All the difficulties you cite, including the “optimizations” I mentioned, stem from not using push, and insisting on periodically polling something.
If you step back, your whole problem is that you are using a system that only has pull and not push architecture. You’re trying to put a bandaid on that core fact. You chose a relational database system that you refuse to build extensions for (as opposed to pretty much any other system) in order to insist “nyeh nyeh you havent solved cache invalidation”.
Caching is just one part of sync. The part that stores a non-authoritative, slightly out of date copy locally. And sync, or replication, is just one part of an eventually consistent system. I mean, even MySQL supports replication, so just hook your client up to that protocol (encrypted in transit) and boom, now you can update your cache.
Here’s the thing. If you use any network protocol that is open, eg HTTP, then yea it’s solved. Because you can have webhooks and just spin up a server to handle them, and update your cache. A row is removed? Decrement your sum. A row is added? Increment it.
You are just insisting that “no, our system has to be clunky and we refuse to implement webhooks / websockets / sockets / push / mysql replication client / updates of any kind, now solve it for me to be as good as a system which has push capabilities.”
Adding change data capture to a database isn't exactly trivial.
Well then maybe consider making a sql replication client that would ingest the changes (like most databases, mysql writes to a straming append-only log, before it is compacted). Just parse the log and act on them.
Not trivial, really? Here, enjoy: https://github.com/krowinski/php-mysql-replication
That means they did implement change data capture, and only exposed it for a very specific use case.
Well, good. Your problem is artificial, choosing tools and scenarios to avoid "push". Your problem isn't with invalidating caches being hard in 2025. I've explained how to do it in both pull and push scenarios. Certainly not "the only hard problems in computer science." And neither is naming!
You didn't implement change data capture. You're using theirs.
I’m also not making my own programming language, I’m using PHP. And I’m using MySQL. What is your point?
Are you saying that “invalidating caches is hard… if you insist on using only systems with no way to push updates, and oh if they have a way to push updates then you’re using someone’s library to consume updates so it doesn’t count?”
I will answer your question directly, after having explained the core issue.
Mysql and Postgresql does in fact have push. It is called replication. The protocol is documented. So, much like a webhook with HTTP protocol, you can ingest changes on a table with a php long-running client and then simply update your apcu cache entries if they are still being stored, and matching that row. And all your PHP processes (managed by php-fpm or FrankenPHP or whatever) will benefit from that atomic apcu update.
There is nothing that says only another mysql server can be a mysql replication client.
Boom, solved. Even in your case. Note that the SQL database did in fact expect you to open a socket, and then it writes its log to that socket. That’s all the streaming events you need.
But now you’re gonna say “but but no you cant have a long running PHP client, we’re talking about a shared hosting environment where the host disables your ability to run a long PHP service that opens a socket”. Well, look. Most of the difficultu is that you’re intentionally trying to use the most clunky architectures just to “prove” that “cache invalidation is really hard.”
Shall we continue with Naming next? :)
I wasn't going to say any of that ;) Yes, Postgres does have WAL log you can subscribe to, but you are creating a replicated slave really. There are many nuances to doing that right and you are downplaying how hard that is (it's not about API, it's about ACID).
More importantly, you are pushing all the complex logic to this imaginary DB replication client: your "caching system" is still nothing more than a KV store.
Well what are the “real” caching systems, if my system can be used for caching but isnt “real”? This feels like a no true scotsman argument.
Caching system would be what you described as a response to my example case: your key-value store combined together with the entire mechanism to watch for DB writes (eg with triggers or the replication log) and tie them back to cached values which need to have their lifetime managed.
[dead]
caching often does simplify software though when done well
and - as the OP suggests - it works best when the cache is a well-defined abstraction with properties and rules about how it works
just because "caching" is mentioned in a meme doesn't mean it can't be true that it can simplify software
> caching often does simplify software though when done well
I have to push back here, I think this is objectively untrue. By definition a system or piece of code on where you add a condition where something else happens (cache) that behaves differently than the uncached path increases complexity.
I'm not saying it's wrong to cache things or that they aren't useful, but I think they absolutely are an abstraction and an optimization at the cost of complexity. Good code bases hide complexity from the devs all the time, so it's not a question of whether you can code it away, but rather how difficult is it to troubleshoot the internals of the system.
Caching is a performance improvement. There is no software that requires caching, therefore it is always something being added on top of the business logic that is fundamentally required. As such, a cache is increasing complexity by nature of its existence.
The only scenario where it would simplify software is if a bunch of complex (non-cache) things are being done to improve perf, and a cache would be the simpler solution. But in that case the simplifying step is not adding a cache, it is removing complex things that aren't actually required. After that you add a cache to improve performance (which increases complexity but is worth it for this imagined use-case). But maybe you remove the complex perf shenanigans, and realize that perf is still "good enough" even without a cache, keeping your software even simpler.
If you hide caching away as an implementation detail behind an abstraction, it comes back and bites you as a leaky abstraction later.
Look at how CPU cache line behaviors radically change the performance of superficially similar algorithms.
Look at how query performance for a database server drops off a cliff the moment the working cache no longer fits in memory.
Hiding complexity can be a simplification, until you exceed the bounds of the simplification and the complexity you hid demands your attention anyway.
CPUs are still a great example for how caching simplifies things.
There's a long history in computer architecture of cores and accelerators that don't have a cache but instead rely on explicitly programmed local scratchpads. They are universally more difficult to program than general purpose CPUs because of that.
I’m sure the CPU designers would love it if they didn’t need several different layers of cache. Or no cache at all. Imagine if memory IOPS were as fast as L1 cache, no need for all that dedicated SRAM on the chip or worry about side channel attacks.
Sure, but we were talking about the perspective of software developers. The hardware designers take on complexity so that the software developer's work can be simpler.
That abstraction is another layer though. And additional layers are additional complexity. So, if you add another layer, the software is less simple than before. You might need to have caching in your software. I don't doubt that. But there's simply no way it makes the software more simple except if you assume some unfortunate starting point where you could get rid of any high-complex performance optimizations in your existing code by replacing them with a more simple cache solution. But then the statement should be "refactoring makes your code simpler".
additional layers (or software in general) are not inherently additional complexity
In some sense they are, since establishing an abstraction is strictly additive. Abstractions help manage complexity.
Getting cache keys or caching events wrong is easy and a nightmare.
But getting them right can easily cross the boundary of purely optimizing performance towards simplifying public API of something. I think this is true.
I'd imagine an involved example where semantics and caching really start to offer a trade-off.
Imagine that somehow querying the actual meteorological data is quite expensive, and consider this badly written pseudocode (equals sign denoting default parameters):
- measureCurrentTemparature()
- retrieveAccurateTemperatureForNanoSecond(momentInTime)
-> cached abstractions which would access cached data:
- getTempearature(moment = now(), tolerance = 1min)
- getCurrentTemperature(tolerance = MIN_TOLERANCE)
I know, reality is much more complicated, and using time (seeing it as quasi-continuous) as a caching parameter is already stretching it so far.
Just a stupid example that came to my mind.
I've bitten myself in the ass with caching rasterized reprentations of images more than once, where the input were SVG images or limited formats that convert to SVG.
I guess simplification needs to include "at what level" as a qualifier.
Trying some other way to explicitly manage multiple storage tiers could get pretty complicated.
On top of the other things mentioned (caching always introduces complexity with lifetime tracking, and thus can't make things simple), the article's got it the wrong way around.
When code has abstract interfaces for data access, introducing caching can be simpler (but not simple) by localizing it in the abstraction implementation which has or doesn't have caching.
But it is not an abstraction (you can perfectly well do caching without any abstractions, and it's frequently done exactly that way).
I think you and the article are referring to abstractions over different concerns.
The concern you're talking about is about the actual access to the data. My understanding of the article is that it's about how caching algorithms can abstract the concern of minimising retrieval cost.
So in some ways you're coming at it from opposite directions. You're talking about a prior of "disk by default" and saying that a good abstraction lets you insert cache layers above that, whereas for the author the base case is "manually managing the layers of storage".
The language used is seriously confusing here.
Algorithms can't really abstract anything since they are, well, just algorithms (formal descriptions of how a computation should be done).
Looking at the author's examples again, I think most everybody would say that caching is used in both:
and The first one does not make an abstraction on storage, the second one does, but they are both "caching" data internally.While there are generic implementations of caching algorithms and we can consider those abstractions, "caching" is a wider term than those implementations, and is specifically not an abstraction (the fact that there is a caching implementation that abstracts something does not make all caching an abstraction).
Edit: Let me also point out that "abstract the concern of minimising retrieval cost" is not caching — I can say that eg. a simple interface with method FastGet(id) does the former, and it needs not use any caching if the underlying structure is fast enough and eg. directly in memory.
This is correct, I appreciate you for putting it so coherently :). I think I didn’t make it clear enough in the piece that I’m coming from a stance of fast access being table stakes, and the question being about how that’s accomplished.
"Caching" is an idea of storing a result of an expensive computation in storage that is faster to get from than doing the original computation (in very generic computer terms, computation can be simply fetching from the network or slower local storage).
What you describe as "caching algorithms" are not really caching algorithms, but cached object lifetime management algorithms (LRU, LFU...).
"Abstraction" is a higher level, simplified view of a set of concepts, yet caching is a single concept. See eg. https://en.wikipedia.org/wiki/Abstraction_(computer_science)
It sounds like you are both trying to redefine what "caching" means (tying it to implementations of particular algorithms), but also what "abstraction" means.
We should be very deliberate with the language we use, and our main goal should be to make it simpler to understand, not harder — I believe you are doing the latter here.
Caching is an optimisation. Sometimes caching can be abstracted away, eg CPU cache or build cache are pretty much abstracted away for a usual web developer. But web page caching is very hard to abstract without any abstraction leaks and weird bugs. And even CPU cache is no longer an abstraction if you deal with very high performance code.
It sounds like they are arguing that when performance matters, you have to know more about caching. Fair enough, you have to know a lot more about things when optimizing. For a lot of cases you can ignore caching because it can be done transparently. You depend on it to some extent because if e.g. every instruction had to be fetched off rotating storage like the old days, it would play a big role in your design. It's just something solved in general for most software to not have to know much about it.
Most optimizations require you to think about how your code is structured, so as a side-effect you make the code more understandable.
In this article, it's cache levels forcing you to separate different types of data because they're accessed at different frequencies. Another example is Rust's borrow checker, whose main purpose is arguably to facilitate both safe and efficient memory management, but which can also be used to enforce invariants that aren't clearly memory-related (e.g. builder pattern, temp files that auto-delete after they're dropped).
These aren't abstractions though. An abstraction is the opposite, hiding structure when it's noisy and making it easier to change. For example, if you already have an architecture in mind and don't want to manually determine how frequently each type of data is accessed, it's better to use a compiler or library that automatically determines what to cache with little to no code or thought on your end; that's abstraction. Similarly, the abstract analogue to Rust's borrow checker is garbage collection, which allows programmers to not think about their data-structures' lifetimes at all. The cost is usually performance and you understand your application less in some ways (although you understand it more in other ways; abstraction hides details but too many details make it hard to see the big picture. Ideally, with abstractions in the right places, you hide only the "unimportant" details in ways that insignificantly affect performance).
Note: the author means that caching can be used as an implementation detail in an (abstracted) storage access system, as opposed to a baseline of having multiple storage systems (fast, medium, slow) and managing them directly.
This was confusing to me – the most obvious way to judge the purpose of a system is to compare with the baseline of not having that system at all, especially in the case of caching where the program is functionally complete and correct without a cache. Anyway, there may not be a right or wrong here. Just tripped me up.
Yes "good" caching - a consistent storage interface - is an abstraction over "bad" caching - multiple different storage interfaces with different speeds. But caching overall is not an abstraction over not having caching.
This is basically semantic argument, and I will not be engaging in it
You're right, but caching is an optimization.
> I've always been told that caching is a tool to make software faster.
Who told you that?
> you don't have to go all the way back to some backend database or API server or SSD [...] Caching is thus a tool to improve performance.
That's called "latency." This is not at all the same as "performance."
> My feelings now are that that perspective on caching is wrong
I agree.
This whole discussion on caching and abstraction was completely befuddling to me.
As can be seen from other comments, people tend to focus on the consistency implications, but something not discussed often in the context of distributed systems is that caches tend to introduce bimodality and metastability [0] [1]. See e.g. DynamoDB for an example of design taking it into account [2].
[0] https://brooker.co.za/blog/2021/08/27/caches.html
[1] https://sigops.org/s/conferences/hotos/2021/papers/hotos21-s...
[2] https://brooker.co.za/blog/2022/07/12/dynamodb.html
Let's first get the obvious out of the way: caching is not an abstraction, the "Storage" abstraction is what enables caching to be implemented. If I had to put Caching in a category, I would say that it's an optimization strategy.
But that's not really what the blogpost is about. The issue that it tries to discuss is the fact that this abstraction is often imposed to us, without any way to control its behaviour. That's the examples of the LOAD_NAME in python he points at. Without having a clear understanding of the access patterns the application mostly uses, a caching strategy cannot be well defined, and you'll end up with an inadequate solution.
Optimization isn't separable from abstraction. Abstraction is something that can be implemented in more than one way, while meeting the terms of its contract. That flexibility allows for optimization.
"fast storage" is about performance, your abstraction includes performance elements. If you go that down, then you are optimizing on your abstraction designs. What doesn't have to be wrong, but then don't say that is not optimization.
This article is talking about single-writer, single-reader storage. I think it's correct in that context. Most of the hairy problems with caches don't come up until you're multi-writer, multi-reader.
There is also an important (but often overlooked) detail that you/your application may not be the only user of the cache. At which point caching, indeed, is an optimization via abstraction: when you fetch an X, you are in no position to predict that the next fifty completely unrelated to you requests would also want to fetch the same X, so it should probably be cached to be readily served.
Which is why solving the "I want my data in fast storage as often as possible" problem may be counter-productive on the whole: you ain't the only client of the system; let it breath and server requests from others.
I don’t really know what the point is… there are different kinds of caching that serve different purposes, just like everything else..
Cmd+F "invalidation" -- not found.
Author is talking about the least interesting, and easiest, piece of the overall caching problem.
Ousterhout's grad students did work on ramcloud with some research at facebook and Amazon on cache use at scale in complex organizations.
One bit of interesting trivia say for facebook (from memory): if you add all the RAM caches in redis/memcached/disk + db caches to make the thing work at scale, then for about 20-30% more memory you could've had the whole thing in memory 100% of the time.
The problem there is /the whole thing/ grows - often faster than your memory.
I think you need to read the papers.
Obviously things grow - look who i mentioned afterall.
The focus is on how you handle growth.
Did you hand-draw that graffiti? Never quite realized that graffiti of technical ideas looks really goated. Best part of the post, to be honest.
> looks really goated
Oof you're trying so hard you could cut diamond with that line.
I don't even understand what that means. Care to explain?
I think it's a drug reference‽
Even more obvious if you think about the case of hardware-managed caches! The ISA typically exposes some simple cache control instructions (and I guess non-temporal loads/stores?), but apart from that, the actual choice of storage location is abstracted away from you (and your compiler).
This reminds me of the use of materialized views as both a cache strategy and as an abstraction helper.
And they too can slow things down. Like all caches can. Like Redis can. Cache is a leaky abstraction.
(Although a materialised view is more like an index than a cache. The view won't expire requiring you to rebuild.)
I believe this same language use is what makes this article confusing: Redis is not a cache, it is a key value store. Caching is usually implemented using key value stores, but it is not an abstraction (leaky or not).
In RDBMS contexts, index really is a caching mechanism (a cache) managed by the database system (query planner needs to decide when it's best to use one index or another).
But as you note yourself even in these cases where you've got cache management bundled with the database, having too many can slow down (even deadlock) writes so much as the database tries to ensure consistency between these redundant data storage elements.
I thought Redis grew up as a KV cache and persistent storage came later.
In some sense though. If it ain't L1 it's storage :)
Maybe Redis started up as an in-memory KV store focused on caching use cases, but it was still a KV store that could be used for caching, or not.
Even if you use "cache" in the name (eg. memcached), that's still not a cache, even if it's a KV store designed for caching.
I was discussing this with someone recently, caching is one of those things that people might do behind the scenes, thinking that it doesn't affect the API but in fact it can create all sorts of issues/complexity.
Use of a better abstraction is an optimization, though.
Everything is caching. Almost nothing operates on the target data directly.
Do you think that's a useful definition of the term?
If everything is caching, why even introduce the term: language should help us describe ideas, it should not be superfluous.
Because you can operate directly on data
What? No, caching means a specific thing: keeping a copy of data away from the source of truth, closer to where you want to read it. Caching always makes systems more complex, it never makes things simpler, and it damn sure doesn't serve as any kind of abstraction unless you're redefining what words mean to indulge your technical philosophizing.
What if you have to keep some data closer and away from the source of truth though? Given that constraint, TFA argued that other architectures could do the job but that caching functions as an abstraction.
Anything can be an abstraction if designed carefully.
Why not both? :)
Sometimes posts are so difficult to read they're hard to respond to. I think I get what they're saying. I think they're saying that they think caching should be simple, or at least, that it should be obvious how you should cache in your particular situation such that you don't need things like algorithms. But that argument is kind of nonsense, because really everything in software is an algorithm.
Caching is storing a copy of data in a place or way that it is faster to retrieve than it would be otherwise. Caching is not an abstraction; it is a computer science technique to achieve improved performance.
Caching does not make software simpler. In fact, it always, by necessity, makes software more complex. For example, there are:
Each routine involves a calculation that determines whether the cache will be beneficial. A hit or miss can lead to operations which may add or remove latency, may or may not run into consistency problems, may or may not require remediation. The cache may need to be warmed up, or it may be fine starting cold. Clearing the cache (ex. restarts) may cause such a drastic cascading failure that the system cannot be started again. And there is often a large amount of statistics and analysis needed to optimize a caching strategy.These are just a few of the considerations of caching. Caching is famously one of the hardest problems in computer science. How caching is implemented, and what it affects, can be very complex, and needs to be considered carefully. If you try to abstract it away, it usually leads to problems. Though if you don't try to abstract it away, it also leads to problems. Because of all of that, abstracting caching away into "general storage engine" is simply impossible in many cases.
Caching also isn't just having data in fast storage. Caching is cheating. You want to provide your data faster than actually works with your normal data storage (or transfer mechanism, etc). So you cheat, by copying it somewhere faster. And you cheat again, by trying to figure out how to look it up fast. And cheat again, by trying to figure out how to deal with its state being ultimately separate from the state of the "real" data in storage.
Basically caching is us trying to be really clever and work around our inherent limitations. But often we're not as smart as we think we are, and our clever cheat can bite us. So my advice is to design your system to work well without caching. You will thank yourself later, when you finally are dealing with the bug bites, and realize you dodged a bullet before.