4 ms·

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

by uvdn7 4y ago

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

moralestapia 4y ago
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.
teraflop 4y ago
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?
- uvdn7 4y ago
  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.
- uvdn7 4y ago
  > 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 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 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.

by uvdn7 4y ago

moralestapia 4y ago

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.

teraflop 4y ago

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?

uvdn7 4y ago
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.
uvdn7 4y ago
> 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 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 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.