uvdn7

Good catch! I shouldn't have omitted the details here. Roughly there are two ways to solve the race you mentioned here.

You can use a versioning scheme supported by the database to do compare-and-swap – i.e. sending invalidate along with a hybrid-logical-clock. HLC is nice in this case as it handles DB transaction rollback gracefully, if the database supports it.

Or we can always do the invalidation asynchronously (by recording the invalidation keys transactionally and have a tailer that sends out the invalidation).

I will make an edit to the blog to make it more clear. Let me know if that makes sense!

I mean this – cache invalidate/fill race specifically – is very much a solved problem from a protocol perspective, as long as our definition of the problem is the same – do not leave stale data in cache indefinitely. That is not to say it is easy; I am not trying to minimize anyone's struggles. https://research.facebook.com/publications/scaling-memcache-... might be of interest.

A lot of the challenges in cache are in making the tradeoffs between consistency and coordination overhead based on the workload and the requirement, _and actually_ making caches consistent in production. As explained in the post, there are practical challenges that are very unique to cache and cache invalidation.

More details can be found at https://blog.the-pans.com/when-and-how-to-invalidate-cache/

I wrote a separate blog post focusing on when and how to invalidate cache and how it can be done – https://blog.the-pans.com/when-and-how-to-invalidate-cache/.

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

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

> Given this statement, the original title of this submission is even more baffling. If you recognize that data can be cached in clients, and that invalidating those caches is so hard that most systems -- including yours -- just completely abandon the goal of being able to do it correctly/reliably, then how can you claim your system makes it no longer a hard problem?

I see where you are coming from; and I don't disagree. I just want to clarify a few things I talked about.

It's not that actually doing the invalidation in the most complicated scenarios can't be done, but rather not worth it (a tradeoff). I tried to explain it here https://news.ycombinator.com/item?id=31676102. But I think Marc did a much job at putting it concisely https://twitter.com/MarcJBrooker/status/1534944338341310470.

I know the tradeoff and I didn't consider the tradeoff specifically is what made cache invalidation hard (it's a distributed system challenge in general I thought). In in that context, I brought up TTL, as I think it makes a better tradeoff in the scenario. Again, cache invalidation can be done (in some cases with unbounded write/invalidation amplifications). It's just that IMO it's not worth it in that case.

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.

Marc put it extremely well. I agree with every single word of his thread. I should have applied a narrower and more specific definition of cache invalidation in the blog post. I apologize for any confusions it caused.

> Some cache entries depend on the state of rows in Table C, but for some combinations of Table A and Table B, no data from Table C ends up in the cache entry.

This is a good example. Let's talk about it. Say we have a table for "friends", and a separate materialization, in cache!, for "friends-of-friends-who-lives-in-us". First of all, the query for the cache data needs to be schematized and made known to the data source. Otherwise, a client can cache arbitrary materialization of anything, it would be obvious that, in its most generic form, the problem can't be solved.

Now assume the data in cache is schematized. There's a transaction that changes "friends" table. Now we have two options, one is that within the same transaction (x-system 2phase commit for example), updates cache (the one that stores "friends-of-friends-who-live-in-us"). This is the synchronous flavor of it, which has obvious scaling challenges.

Spanner, etc. are about handling the async flavor of the same logic.

> if your architecture is good. But caching tends to rot architecture.

My speculation is that sometimes people are using cache without knowing they are dealing with a distributed system. A cache in its nature is a distributed system (because there's cache and the source of truth).

The linked blog post is targeted towards cache service owners, not cache users (who puts materializations in cache). If I learned anything from this public civil discourse on Hacker News is that

    we should avoid putting the power/responsibility of cache invalidation in the hands of cache users
    we should provide guard rails via better abstractions, simpler data models (e.g. a graph data model)
    we should avoid caching relations (separate materializations) but prefer caching indices instead, so the write/invalidation amplification is bounded.

This is a very good question.

The number of nines actually go up with increasing timescale windows because Polaris checks anomalies at write-time/invalidation-time.

I guess the behavior of what you are describing is cache inconsistencies at read-time. E.g. if I introduced an inconsistent cache entry at time T, it can be exposed to many subsequent reads (hence the "building up over time" as you mentioned). This is an important metric as well – we actually measure it as well.

The key difference between read-time cache consistency measurement and write-time cache consistency measurement is about "purpose". Write-time cache consistency measurement is more actionable, as it captures the moment (or very close) of when cache becomes inconsistent. If one wants to debug something, you want to get close to when the anomaly happens. Read-time cache consistency measurement is more about measuring the negative impact of cache inconsistencies (which are client facing).

I can't give away details/numbers. But I have to say, what you did right here is very impressive.

> Paxos is an implementation (of protocols).

I have nothing more to add, if that's your standpoint. But I am glad that we "debugged" to close to the "root" of our assumptions/context.

Interesting… what are your thoughts on Lamport’s TLA+?

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.

My experience is that this is easier said than done. But I agree with you that in theory, one can inject failure and run tests with all possible combinations, and have a repeatable test framework (think about foundationdb’s test framework) to help root cause test failures. Sqlite has very impressive reliability; its test framework is not open sourced. It also benefits from user bug reports, as it’s literally the widest deployed db. Bugs/flaws happen.

Having better tests and better observability in production are also not mutually exclusive.

Yep. To generalize this even more, it’s not that cache invalidation is hard but “materialization/denormalization is hard” (even if it’s a table on the same database). Hence why I never thought this is what made cache invalidations hard (because it’s not even unique to cache).

I can imagine an automated solution to achieve what you described eg by keeping track of the table:columns touched by the query. Maybe that’s what these system did.

It has its downside though, as the invalidation cost in this case can be unbounded (read as huge write amplification in some cases). I imagine it would be hard to provision the invalidation pipeline. This is where it gets into trade offs. Eg by just caching the primary index and secondary indices (not materializations) you can very far as well (do joins on read). But it depends on the workload.

Looks like the separate materialization (what's stored in cache) is schematized?

I will take a closer read. It seems similar to what I described here https://news.ycombinator.com/item?id=31676849.

Let's actually also try to solve the "cache invalidation" 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.

Because the materialization in cache don't take writes themselves, so updates to them are essentially performed blindly and can be ordered by the commit time (TrueTime).

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.

Let's solve 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.

Because the materialization in cache don't take writes themselves, so updates to them are essentially performed blindly and can be ordered by the commit time (TrueTime).

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.

> Good work, but not a solution for cache invalidation.

Assuming your definition of cache invalidation is about "when/who" to invalidate on writes. Let's actually try solving it.

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.

Because the materialization in cache don't take writes themselves, so updates to them are essentially performed blindly and can be ordered by the commit time (TrueTime).

Now this does assume whatever we cache (the query e.g.) needs to be schematized, and made known to the invalidation pipeline. 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.

No actually. When a sample has crossed the reporting timescale, and it's inconsistent. Regardless of if the db changes later or cache becomes consistent later, at the moment it's still an anomaly (inconsistency in this case).

> But what if you actually do want your dependency list to trigger invalidation?

Let's do it.

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). So in theory this can be done. 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); but rather invalidate caches asynchronously? 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). It can't be done.

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.

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.

I also think it can be solved by changing the data model.

Say, you are caching a result of joining two tables with two ids that you are filtering on. It's still very managable to track the dependency and know when to invalidate. It can easily grow out of hand (talking about 10 table joins and 100 lines of SQL). Then solving the "when/who" to invalidate problem is essentially equivalent to doing "joins" on the write/invalidation path. First of all, it's unbounded. The number of cache entries you need to invalidate can be unbounded (not bounded by the number of indices, but a function of data in the database instead). My argument is that why do this to begin with? I acknowledge this is hard.

But why do it? On the other hand, you can have simpler data models (e.g. TAO), fetching and stitching everything together on the read path scales fairly well. It's essentially doing "joins" on the read path. But it's all hitting caches, so it's fast still.

For some complicated queries, you can cache secondary indices (which is easier to figure out the "when/who" question, just as how DB figures out which index entry to update on transactions) to make your read-path join faster.

Thanks for the reference. Naiad: A Timely Dataflow System is an interesting paper!

These are good questions. I might not have satisfying answers to all of them but I will try.

> what about many-to-many where one fetch returns inconsistent results Are you referring to the case when cache stores a complicated result of a function that fetches data from many sources, and how to figure out when to invalidate? If so, I am sorry but that's not the cache invalidation I was referring to. (https://news.ycombinator.com/item?id=31676102)

> What about data queried while there's a transaction rollback.. when is it updated in the cache

This might be easier to answer. I assume if you run the database with isolation level higher than read-committed, you will be fine.

I am using the following definition from Wikipedia

> Cache invalidation is a process in a computer system whereby entries in a cache are replaced or removed.

It's the smallest unit of function that "cache invalidation" must perform. Some people define cache invalidation as a problem of figuring out "when/who" to invalidate. That's not the definition I am using (and my definition is narrower in that sense). The confusion is not intended, as I believe (as I explained in the post) that even with the narrower definition, cache invalidation is still insanely hard.

It's not disingenuous. You are welcome to speculate.

If it helps, let's essentially break cache invalidation into a few parts 1. knowing when/who to invalidate 2. actually processing the invalidate

My argument is that #1 can be very managable with simpler data models (as we did). #2 can't be avoided; and #2 is very hard. And the post is about how we believe we have a systemic approach for managing #2.

It's very easy to feel like #2 is an easy problem, which probably explains why people think #1 is what Phil Karlton was referring to. The analogy I like to use is Paxos. The protocol fits on a single slide. It's easier to feel like you have Paxos work; but it's very hard to have Paxos actually work.

> Now going back to your example with complicated dependencies. Maybe TTL is a better solution. With many dependencies, any changes from the dependency list might trigger invalidation. At some point, just doing TTL, would be simpler.

#1 is a hard problem, if the data model and data in cache is complex I agree. My comment here is referring to update-heavy workloads. If you have a large dependency, your invalidation workload will tend to be heavy. At some point, you will spend more power on processing invalidation than serving user queries. The post is talking about a narrower problem; and I am not trying to minimize anyone's struggle.

Yep. I respect this definition, and I tried to clarify things a bit here https://news.ycombinator.com/item?id=31676102.

I am sorry for the confusion. We have internal abstractions that deals with the problem you described (especially in simpler forms, the example you have is fairly managable actually).

EDIT: I can see why it gets complicated if your data model and query is very complicated.

I understand some people have a different definition of cache invalidation. I am using the following definition from Wikipedia

> Cache invalidation is a process in a computer system whereby entries in a cache are replaced or removed.

It's the smallest unit of function that "cache invalidation" must perform. Some people define cache invalidation as a problem of figuring out "when/who" to invalidate. That's not the definition I am using (and my definition is narrower in that sense). The confusion is not intended, as I believe (as I explained in the post) that even with the narrower definition, cache invalidation is still insanely hard.

If it helps, let's essentially break cache invalidation into a few parts 1. knowing when/who to invalidate 2. actually processing the invalidate

My argument is that #1 can be very managable with simpler data models (as we did). #2 can't be avoided; and #2 is very hard. And the post is about how we believe we have a systemic approach for managing #2.

For #1, say, you are caching a result of joining two tables with two ids that you are filtering on. It's still very managable to track the dependency and know when to invalidate. It can easily grow out of hand (join 10 tables with 100 lines of SQL). Then solving the "when/who" to invalidate problem is essentially equivalent to doing "joins" on the write/invalidation path. First of all, it's unbounded. The number of cache entries you need to invalidate can be unbounded (not bounded by the number of indices, but a function of data in the database instead). My argument is that why do this to begin with? I acknowledge this is hard. But why do it? On the other hand, you can have simpler data models (e.g. TAO), fetching and stitching everything together on the read path scales fairly well. It's essentially doing "joins" on the read path. But it's all hitting caches, so it's fast still.

For some complicated queries, you can cache secondary indices (which is easier to figure out the "when/who" question, just as how DB figures out which index entry to update on transactions) to make your read-path join faster. The write amplification / cache invalidation fanout is bounded. You don't do "join" on writes/invalidations.

Let's discuss the "when/who" problem specifically, if say we just have to solve it.

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.

On the other hand, it's very easy to feel like #2 is an easy problem, which probably explains why people think #1 is what Phil Karlton was referring to. The analogy I like to use is Paxos. The protocol fits on a single slide. It's easier to feel like you have Paxos work; but it's very hard to have Paxos actually work.

Here's the recording of my talk at systems @scale which I hope people find it helpful (no matter how you define cache invalidation – the broader vs. narrower definition) – https://www.facebook.com/watch/live/?ref=watch_permalink&v=3....