Hacker News Reader

Comment by moralestapia | Hacker News Reader

???

We seem to have different concepts with regards to the cache invalidation problem.

The one I know has to do with "Is there a change in the source data? How should I check this? How often?" and such things.

Yours seems to be "In my distributed system, I cannot guarantee the order of the messages that get exchanged, and thus, different nodes may end up having different information at times".

IMO you have a consensus/distributed data problem, not a cache invalidation problem (the inconsistency between your cache nodes is a consequence of the underlying design of your system).

View on HN

Yep, cache invalidation is hard because you can't just cache /users/1/networkstatus as a function of the request itself; its underlying value is a complex function of values fetched from possibly dozens of tables and services, any of which could change at any time without any immediately discernable connection to User 1.

OP's response to this, in another comment, is: "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."

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

https://materialize.com/ is the closest thing I know of to a "solution" for this - it lets you build nested, realtime materialized views on top of streaming and non-streaming data, all with SQL syntax and Postgres wire compatibility, that fully recalculate and recache their results whenever any input changes, no matter how deep (based on https://timelydataflow.github.io/timely-dataflow/ from Microsoft Research).

You could either use the outputs of such a system as a cache, or weave together a cache invalidation signaling system that sends a stream of keys that need to be evicted from cache at any time, directly into a Kafka topic. And then, of course, this could plug into Meta's cache invalidation consensus system. But it's remarkably disingenuous for Meta to pretend that the dependency side of this problem is trivial or can be solved by TTLs alone.

Nice comment, you opened a new perspective on this.

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

I (we, as it was a team) once had a scenario where there was a big dependency graph with a lot of replicas (not necessarily caches but a similar thing) and if we just used TTLs the effect on the whole thing was that there were some periods of time where we've just got a flood of nodes (children, grandchildren, and so on) all wanting to update at the same time, talking to each other and whatnot.

In the end the solution was quite complex as it was a combination of a short TTL, some random delays here and there to lower the probability of things happening at the exact same time, very low message overhead and a system akin to ETags in HTTP [1]. It was very hard due to the scale of the whole system and I'm sure Meta has this problem 100x so, disregarding the poor choice of title, it was an interesting read nonetheless.

1: https://developer.mozilla.org/en-US/docs/Web/HTTP/Headers/ET...

Yeah, I came here for "Materialize but for Tao" and instead got "how we check correctness of Tao's single-entity cache"

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.

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

See also Noria, https://pdos.csail.mit.edu/papers/noria:osdi18.pdf - later research with similar thought process. Claims to scale better than differential-dataflow. Summary is, "let's make a timely distributed graph computation to keep SQL queries up-to-date, but this time we can forget some parts of the query to save on cache memory". Now productionized by https://readyset.io/

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.

The nice thing about these systems (Materialize/Timely/Differential-Dataflow/Noria/ReadySet) is that the invalidation pipeline is automatically derived from the query structure. The user just needs to know how to write their query (regular SQL with Materialize/ReadySet), pipe in the source-of-truth changelog from all the tables in the database, and the system takes care of the rest. Your answer is somewhat vague about how to build the invalidation pipeline. I think that's what many people find challenging about cache design.

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.

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

Exactly. The race condition problem from the example below still exists even without any caching, and perhaps still exists even without any replica.

> Imagine that after shuffling Alice’s primary message store from region 2 to region 1, two people, Bob and Mary, both sent messages to Alice. When Bob sent a message to Alice, the system queried the TAO replica in a region close to where Bob lives and sent the message to region 1. When Mary sent a message to Alice, it queried the TAO replica in a region close to where Mary lives, hit the inconsistent TAO replica, and sent the message to region 2. Mary and Bob sent their messages to different regions, and neither region/store had a complete copy of Alice’s messages.

A solution to this problem is to update Alice's primary message store to be "region 2;region 1" for a period of time, and get Alice to retrieve messages from both message stores during that period.

However, since you have a caching layer that doesn't have an explicit TTL, such that any cache inconsistency can last indefinitely, you now have a much bigger distributed data problem.

> 1. The cache tried to fill the metadata with version.

> 2. In the first round, the cache first filled the old metadata.

> 3. Next, a write transaction updated both the metadata table and the version table atomically.

> 4. In the second round, the cache filled the new version data.

Another way to look at this is that while the database can handle writes to the 2 tables atomically, the caching layer can't do a consistent read from the 2 tables, because it is either too expensive to do the 2 reads from within a database transaction, or too expensive to do a single read with join?

Our current system also suffers heavily from distributed inconsistency, mostly due to these "too expensive" constraints imposed by an ex-FB guy, even though our scale is nowhere near FB level. Yes I am bitter.

You assessment is good.

> Our current system also suffers heavily from distributed inconsistency

Despite of people having different definitions of cache invalidation (mine is narrower, and a subset), I hope the techniques covered here can be helpful (even a tiny bit).

FAFAIK the original cache invalidation problem is always seen from the point of view of a writer in a multiple-writer distributed system. It's not about determining the freshness of data as seen from a reader/consumer, but about atomically (!) updating all data copies by a write action in a distributed system.

If you assume loosely-coupled, eventually-consistent data, you haven't solved the problem at all -- you've just side-stepped it. If you assume a single-writer, multiple-reader architecture, you don't have the original problem at all.

> the original cache invalidation problem

Do you have any reference or links about it? Thanks.

> point of view of a writer in a multiple-writer distributed system > If you assume a single-writer, multiple-reader architecture, you don't have the original problem at all.

It starts to sounds like you are describing Paxos?

Actually, I was thinking of cache coherency protocols in multi-processor systems like MESIF or MOESI:

- https://en.wikipedia.org/wiki/Cache_coherency_protocols_(exa...

- https://www.cs.utexas.edu/~pingali/CS377P/2018sp/lectures/me...

I know the same problem exists in distributed shared-memory systems like supercomputers, but I'm not sure where the original term comes from.

(edit: you can take some comfort that you're not the first to define cache invalidation in this way, but then you're not the first to claim this victory either: https://briandunnington.github.io/distributed_cache_invalida... ;)

Thanks for the links!

Yeah I assumed it would originate cache coherency protocol as well. In that case, it's not hard to figure out "when" to invalidate, as you just invalidate the cacheline on mutates based on addresses. If cache invalidation originates from cache coherency protocols, I would assume Phil Karlton's quote was not referring to the "when" to invalidate as being the hard problem. But I will not die on this hill. I am open to rephrase/redefine/reword in anyway that is helpful to people.

Yeah I was also intrigued by the title and couldn't find what I expected tbh.

I think https://news.ycombinator.com/item?id=31672541 might address your question.

No, mine was not a question, it was a statement.

You misnamed the problem you are trying to solve.

OK. I am here to learn. Say we go with your definition of cache invalidation problem. Do you think that's THE hard part of cache invalidation?

Say, you are just caching simple k/v data (no joins, nothing). Are you claiming cache invalidation is simple in that case?

Also the reason why I didn't mention the cache invalidation dependencies is that _I believe_ it's a solved problem (see the link above, we do operate memcache at scale). I am happy to discuss if and why it wouldn't work for your case.

>Are you claiming cache invalidation is simple in that case?

No.

>I believe it's a solved problem

It's not.

Suppose you have source-of-truth A (doesn't really matter if it's a key-value store or whatever, it could even be a function for all intents) and a few clients B1, B2, B3, ... that rely on the data from A. You have to keep them in sync. When should B* check if A has changed? Every time they need it? Every minute? Every hour? Every day? This is the cache invalidation problem; which IMO is not even a problem but a tradeoff, but whatever.

Epilogue: With all due respect, you have an unbelievable career, IBM, Autodesk, Google, Box and now Meta. None of those companies would give me five minutes of their time because I am self-taught, yet here we are :)

> Suppose you have source-of-truth A (doesn't really matter if it's a key value store or whatever, it could be a function for all intents) and a few clients B1, B2, B3, ... that rely on the data from A. You have to keep them in sync. When should B* check if A has changed? Every time they need it? Every minute? Every hour? Every day? That is the cache invalidation problem.

A few things to clarify here what you are referring to as clients are cache hosts (as they keep data). You seem to imply that the cache is running on the client? I was referring to cache servers (think memcache, Redis, etc.), for which the membership can be determined. So on update (e.g. when you mutate A, you know all the Bs to invalidate).

Now continuing with your example, with cache running on the client. Assuming we are talking about same concept when we say "client", the membership is non deterministic. Clients can come and go (connect and disconnect as they wish). There are some attempts to do invalidation-based cache on clients, but they are hard because of the reason I just mentioned. So usually client cache is TTL'ed. E.g. the very browser you are using to see this comment has a lot of things cached. DNS is not going to send an invalidate event to your browser. It't TTL based.

I guess what I am saying is that cache invalidation rarely applies to cache side cache as far as I know. Maybe you have a different example, which we can discuss.

Caches, clients, Facebooks, hosts, Metas, Redises(?), ... all those things don't really matter.

What matters is B* reads from A, but how often should that be? That's it, literally. That's the whole problem.

It doesn't matter whether the cache is co-located with the "client" that ultimately uses the data. Say A is a database, and B1, B2, B3... are memcached servers. The exact same situation applies.

> So on update (e.g. when you mutate A, you know all the Bs to invalidate).

But "knowing" this is a big part of what people mean when they say cache invalidation is hard! If the value in B is dependent on a complicated function of A's state, then it may be difficult to automatically determine, for any given mutation to A, which parts of B's cache need to be invalidated.

> There are some attempts to do invalidation-based cache on clients, but they are hard because of the reason I just mentioned. So usually client cache is TTL'ed.

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?

Good points. I will try to address them.

> But "knowing" this is a big part of what people mean when they say cache invalidation is hard!

I can see that. Memcache is a look-aside cache we have at scale. There are abstractions on top to manage this complexity; and it has been fairly managable. I am sure you can come up with a complicated dependency tree that things are not obvious at all. But when you do have a very large dependency tree, any change in them can trigger cache invalidation, at which point, caching with TTL will be a better option IMO. I can see where you are coming from.

> If you recognize that data can be cached in clients, and that invalidating those caches is so hard that most systems

My reasoning for this being hard is different than yours I think. In my comment, it's due to indeterminism of the cluster membership. I think in that case, we are talking about different problems.

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

  Epilogue: With all due respect, you have an unbelievable career, IBM, Autodesk, Google, Box and now Meta. None of those companies would give me five minutes of their time because I am self-taught, yet here we are :)

Correlation does not imply causation. I’m also self taught and some of those companies have given me a lot more than 5 minutes of their time.

Here’s some unsolicited feedback - I interpreted your comment above as implying you know more than $peer, and it comes off a little snarky with the emoji face. That approach doesn’t demonstrate professionalism to me. On the other end, $peer focuses on the technical challenge. Most of the gig boils down to communicating ideas.

Please don't cross into personal attack. It's not obvious what you were intending by that last paragraph, but it doesn't sound nice, and bringing someone's personal details into an argument is already not ok.

https://news.ycombinator.com/newsguidelines.html

You're right,

Although I didn't mean it as an attack it def. didn't add to the discussion, so I'll be more careful onwards.

Appreciated!

It's a good observation that out-of-orderness and asynchrony contribute a lot to the challenge.

> the inconsistency between your cache nodes is a consequence of the underlying design of your system

I disagree with this. First of all, imposing order and synchrony is expensive, slow and unreliable. Even if we do that, cache fill and invalidation will never be externally coordinated; and will collide on the cache host.

> > the inconsistency between your cache nodes is a consequence of the underlying design of your system

> I disagree with this. First of all, imposing order and synchrony is expensive, slow and unreliable. Even if we do that, cache fill and invalidation will never be externally coordinated; and will collide on the cache host.

This is a weird reply. GP writes "A implied B" and you disagree by arguing that you had to do A. Sure. But it's still what implied B. Quite a fundamental logic flaw, no?

I don't see that. Yes I did say I had to do A. Then I said that it doesn't imply B. Because even if the underlying system is strongly ordered, we can't order external events. Did I miss something?

A == "Design of your system"

B == "Inconsistency between your caches"

GP: A -> B

You: "Imposing order and synchrony is [bad things]" == "If you don't do A then [bad things]", i.e., (not A) -> [bad things]

Also you: "Even if we did, then [other issues]" == "Even if you don't do A then [other issues]", i.e., (not A) -> ..what? B?

You are certainly not arguing against the A -> B implication.

I really appreciate your comment. I am learning as we speak.

I was essentially saying !A !-> !B - even if we have a strongly ordered system, there will still be inconsistencies/races/problems.

And I can see why it's a bad/weird argument. Thank you for pointing it out. Really appreciate it!

EDIT: I would have rephrased it this way

- A -> B is right - But !A -> B also holds. Hence what we talked about here is relevant/useful regardless. And it's not about A.

Would that be better?

Yeah it reads to me like they redefined "cache consistency" to mean something different.

That's not intended. What's your definition of cache consistency?

There are multiple models for cache consistency. What I'm saying is that it seems this tracing library is built on a particular model of cache consistency, and that if it doesn't find any issues, then it regards the cache as consistent. The question is, how much does that model accurately reflect actual cache behavior in the live system, and how much does it simply test that the cache behaves according to its internal model?

Reply on news.ycombinator.com