Saying a problem isn't hard to solve because you have tools to analyze the correctness of your solution seems like a stretch.

But that's not what I am saying though ...

> 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.

> answering the "why my cache is inconsistent" is the problem we solved

That should be the title and focus of your post. Instead, it feels like grandiose claims about solving cache invalidation itself.

> 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".

The jist of what I got from the post was that you created a tool which monitors caches and that helped find bugs that cause inconsistent cache issues. How is that solving a computer science problem?

The tool that monitors cache consistency is easy to build. That by itself doesn't solve anything major. The most important contribution is a novel approach on consistency tracing that helps find out "why" caches are inconsistent – pinpoint a bug is much harder than saying "there is a bug". This is based on the key insight that a cache inconsistency can only be introduced (for an invalidation-based cache) in a short time window after the write/mutation, this is what makes the tracing possible.

> 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.

I disagree with your claim that "cache invalidation might no longer be a hard thing in computer science" for the same reason that you say that pinpointing bugs is harder than saying "there is a bug". You can't just build a tool and declare a whole problem space in computer science (and a long running joke) as being solved.

> 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.

You are right. The assumptions I made are - the definition of cache invalidation https://news.ycombinator.com/item?id=31676102 - subsequently, by that definition, _make_ cache consistent in production is the harder 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.

With the risk of stating the obvious - the hard part of cache invalidation is to know when to invalidate the cache.

We invalidate cache upon mutations. When else would you do it?

Please see https://news.ycombinator.com/item?id=31672541

How do you handle caching derived data assembled from multiple individual records? For example, how would you maintain a cache for a query like getFriendsOfFriends(userId)?

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?

This is fantastic question! We face something very similar (if not identical).

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

So if you just implement the cache invalidation logic in your monitoring system, you can tell if you got the cache invalidation logic correct in your caching system. That sounds really helpful!

That's not the case though. Polaris acts as a client and only monitors client observable effect, and assumes no knowledge of the server internals.

I am trying to help.

This continues to point out how you just completely don't understand the quote. You very clearly seem to think that the "hard" part of cache invalidation is how to implement invalidating it when you know exactly what needs invalidation. The "hard" part is actually in knowing what needs invalidation. Your grandiose claims make you, your team and org, and your company look bad.

You think figuring out when to invalidate is the harder part of cache invalidation; in that sense Polaris is not checking the “when” logic but rather repeating it. And you are right. This is not the problem we solved in the post. I should have applied a narrower definition to cache invalidation, and I apologize for the confusions.

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.)

> You very clearly seem to think that the "hard" part of cache invalidation is how to implement invalidating it when you know exactly what needs invalidation. The "hard" part is actually in knowing what needs invalidation.

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.

https://blog.the-pans.com/when-and-how-to-invalidate-cache/ Does this address the "knowing what needs invalidation" part?

I basically wrote a separate blog just for replying to this https://blog.the-pans.com/when-and-how-to-invalidate-cache/.

I read the article. It seems to be suggesting that cache invalidation might no longer be a hard thing in computer science because of the insights uncovered by your tracing and observability solution. IOW, now that you can measure and audit the system, you're able to find and fix bugs in the system. Is that the correct take-away?

Yep. You're exactly right. And the approach is generic and I think it should work for everyone.

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.

Off topic but what tool did you use to create those cache hierarchy diagrams?

I didn't understand the tracing part. Is tracing 100% inside of polaris? If not does it start at the database? The first cache?

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?

Tracing is not in polaris. It's a separate library that runs in every cache host. Its main job is logging every cache state mutation for traced writes. So when polaris detects cache inconsistencies, we know what happened and why cache is inconsistent.

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.

Is your argument here that cache invalidation may no longer be hard because you can implement systems like Polaris which continually test your cache implementation to try and catch invalidation problems so you can then go and fix them?

EDIT: Already answered in this reply: https://news.ycombinator.com/item?id=31671794

Polaris is actually fairly simple to build. The harder question to answer is "why cache is inconsistent" and how you debug. The second half of the post talks about consistency tracing, which tracks all cache data state mutations.

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.

Correct me if I'm wrong, but don't we have general solutions that ensure correctness if you allow for enough time? Wouldn't performance be a critical aspect of the claim that this is "no longer a hard problem"? How about the CAP theorem?

The "hard problem" defined here is more about the engineering side. The analogy I have is Paxos the protocol and Google's Paxos Made Live paper. We do have many cache coherency protocols that are provably correct (using TLA+ if you will); but making them actually consistent in production is a completely different story; and a hard problem for an invalidation-based cache.

Can you speak more on why ‘making them actually consistent in production is a completely different story’?

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.

Let try to put this as concisely as possible. When you put an algorithm in code, when rubber hits the road, you have to make certain assumptions of how things work, eg how events are ordered, how fsync works, what kind of failure scenarios you are expecting, etc. More likely than not, the reality will be a little different. No to measure just innocent bugs in the code.

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.