News for hackers. Stuff that matters.
Re:Cache made consistent: Meta’s cache invalidation solution by moralestapia on Wednesday June 08, 2022 @05:35PM (#31674606)
>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 :)

Re:Cache made consistent: Meta’s cache invalidation solution by dang on Thursday June 09, 2022 @01:59AM (#31678004)
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

Re:Cache made consistent: Meta’s cache invalidation solution by moralestapia on Thursday June 09, 2022 @04:12PM (#31686169)
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.

Re:Cache made consistent: Meta’s cache invalidation solution by dang on Thursday June 09, 2022 @06:22PM (#31687708)
Appreciated!
Re:Cache made consistent: Meta’s cache invalidation solution by unboxingelf on Wednesday June 08, 2022 @06:21PM (#31675142)

  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.

Re:Cache made consistent: Meta’s cache invalidation solution by uvdn7 on Wednesday June 08, 2022 @05:41PM (#31674685)
> 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.

Re:Cache made consistent: Meta’s cache invalidation solution by teraflop on Wednesday June 08, 2022 @05:54PM (#31674838)
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?

Re:Cache made consistent: Meta’s cache invalidation solution by uvdn7 on Wednesday June 08, 2022 @06:19PM (#31675115)
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.

Re:Cache made consistent: Meta’s cache invalidation solution by uvdn7 on Friday June 10, 2022 @10:41AM (#31694877)
> 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.

Re:Cache made consistent: Meta’s cache invalidation solution by moralestapia on Wednesday June 08, 2022 @05:53PM (#31674818)
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.