I am the author of the blog post. I believe the methodology described should be applicable to most if not all invalidation-based caches. I am serious when I say that cache invalidation might no longer be a hard thing in computer science. AMA!
> you have tools to analyze the correctness of your solution
That's half of it. Cache invalidation is hard not only because of the complexity of cache coherence protocols, some of which is not very complicated. But cache invalidation does introduce countless races that manage to introduce cache inconsistencies in ways that are just hard to imagine ahead of time (in my experience). IMO, that's the harder part of cache invalidation – when cache inconsistencies happen, answering the "why" question is much harder than having a cache invalidation protocol (you can have TLA+ for one if you will). And answering the "why my cache is inconsistent" is the problem we solved, which I think is the harder part of the cache invalidation problem.
That should be the title and focus of your post. Instead, it feels like grandiose claims about solving cache invalidation itself.
That is definitely something I worried about. But at the same time, I do think we solved the harder part of the cache invalidation problem. TAO and Memcache serves quadrillions queries a day. Based on our experience, answering the question of "why my cache is inconsistent" is the hardest thing about cache invalidation.
Cache invalidation protocols can be complicated, but some are pretty managable. You can also verify it using TLA+ if you will. But once the rubber hits the road, some cache entries tend to be inconsistent.
I definitely worry about people taking this the wrong way, but at the same time, I stand by the claim of "cache invalidation might no longer be a hard thing in computer science".
> How is that solving a computer science problem?
It depends on your definition of a computer science problem. I am definitely not solving P = NP. By your definition, does Google's Paxos Made Live paper solve a computer science problem?
The claim is more a play on Phil Karlton's quote, as the work here makes cache invalidation much easier (in my opinion). Also Phil Karlton's quote doesn't necessarily _make_ a problem a computer science problem, don't you think? I think it's a good quote and there's a lot of truth in it.
> the work here makes cache invalidation much easier
The tool itself doesn't make cache invalidation easier, it makes finding bugs (that happen to be cache invalidation bugs), easier. By that logic, if one never wrote a bug, cache invalidation would still be as difficult as before.
Again, good work on the tool. That's fantastic. I've definitely done some huge work in this area myself and struggled a lot. Let's also realize that it is also FB internal, so whatever solutions you've come up with aren't really helping anyone else without spending the same amount of engineering time and resources on the problem.
I understand if you disagree with these premises. And all these make sense.
Let's discuss the "cache invalidation problem" by your definition.
E.g. in its most generic form, a cache can store arbitrary materialization from any data source. Now when updating the data source, in order to keep caches consistent, you essentially need to transact (cross system transaction) on both the data source and cache(s). Usually cache has more number of replicas, I am not sure running this type of transactions is practical at scale.
What happens if we don't transact on both systems (the data source, and cache)? Well, now whenever the asynchronous update pipeline performs the computation, it's done against a moving data source (not a snapshot of when the write was committed). Now let's say the data source is Spanner, which provides point-in-time snapshots. On Spanner commit you can get a commit time (TrueTime) back. Now using that commit time, to read the data and compute cache update asynchronously can be done.
Now this does assume whatever we cache (the query e.g.) needs to be schematized, and made known to the invalidation pipeline (in the form of some control plane metadata). I think it's a very fair assumption to make. As otherwise (anyone can cache anything without the invalidation pipeline knowing at all), it's pretty obvious that this problem can't be solved.
My context is working on Notion’s caches for page data. Our pages are made out of small units called “blocks” that store pointers to their child content. To serve all the blocks needed to render a page, we need to do a recursive traversal of the block tree. We have an inconsistent cache of “page chunks” right now, how would you think about making a consistent cache?
There are two parts to solve this problem 1. monitor and measure how consistent the cache is 2. figure out why they are inconsistent
I will focus on #1 in this comment. You can build something very similar to Polaris (mentioned in the blog) that - tails your database's binlog so it knows when e.g. "friendship" data is mutated - it can then perform the computation to figure out which cache entries "should have been" updated. E.g. if Alice just friended Bob, then Alice's friends-of-friends and Bob's friends-of-friends should reflect the change. And your monitoring service will "observe" that and alert on anomalies
I am trying to help.
I acknowledge that both are hard. The former can't be avoided. And the latter is easy in certain cases (if you have a simpler data model, etc.). I am not saying the latter is easy. More details in https://news.ycombinator.com/item?id=31676102
And I made the mistake of assuming the definition of “cache invalidation” as it means different things to different people. Marc’s view is a very good one https://twitter.com/marcjbrooker/status/1534944340266864640?... but it’s actually different than some people’s definition on this thread.
I will not defend myself; and you are welcome to speculate. I said it here https://twitter.com/uvdn7/status/1534978702609682432, and other places on this thread, and I will repeat it again.
I should have applied a narrower and more specific definition of cache invalidation in the blog post. The confusion it caused is not intended.
> how to implement invalidating it when you know exactly what needs invalidation
I stand by the claim that this is a hard problem, as explained in the blog post. When you deal with a cache you are inherently dealing with a distributed system (there's cache and the source of truth). And the contribution is making this aspect more manageable, which is common to all invalidation based caches.
On the other hand, I don’t think figuring out “when” to invalidate is what makes cache invalidation hard. I shared the same view as Marc https://twitter.com/marcjbrooker/status/1534944340266864640?....
There is a trade off between coordination (in some cases with unbounded write amplification https://twitter.com/uvdn7/status/1534979480363667457?s=21&t=...) and relaxed consistency. I assumed this is a trade off that people just have to make based on their workload (hence you saw me saying in other comments about TTL; it’s about tradeoffs, when the cost of coordination/invalidate surpasses the benefit — higher hit rate, etc.)
The idea is that with all these observability capabilities, debugging cache inconsistencies is getting very actionable and close to how we debug an error with message telling us exactly where an exception happened.
Does the invalidation need to be predictable before you can use tracing? What kind of parameters do you have so you don't have too much logging or too little?
It starts all the way from client initiated write (where we mint a unique id, and plumb it all the way through).
> What kind of parameters do you have so you don't have too much logging or too little?
This is the key question! If you go to the second half of the post, it talks about an insight about how we managed to log only when and where cache inconsistencies _can_ be introduced. There's only a small window after mutation/write where cache can become inconsistent due to invalidation. So it's very cheap to trace and provide the information we need.
EDIT: Already answered in this reply: https://news.ycombinator.com/item?id=31671794
Distributed systems are state machines, with consistency tracing keeping track of all the state transitions, debugging cache inconsistencies in an invalidation-based cache is very actionable and managable based on our experience.
Curious because I’ve been learning TLA+ recently and interested to more know about cases where an algorithm has been proven but actual an implementation of it fails.
My favorite example is Paxos. Its algorithm fits on a single slide. But it’s notoriously hard to make it actually work correctly in production.