5 ms·

??? 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? Ho

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

uvdn7 4y ago
I think https://news.ycombinator.com/item?id=31672541 https://news.ycombinator.com/item?id=31672541 might address your question.
- moralestapia 4y ago
  No, mine was not a question, it was a statement. You misnamed the problem you are trying to solve.
  - uvdn7 4y ago
    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.
    - moralestapia 4y ago
      >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 :)
      - 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
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.
- wildmanx 4y ago
  > > 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?
  - uvdn7 4y ago
    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?
    - wildmanx 4y ago
      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.
      - uvdn7 4y ago
        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?
seqizz 4y ago
Yeah I was also intrigued by the title and couldn't find what I expected tbh.
cratermoon 4y ago
Yeah it reads to me like they redefined "cache consistency" to mean something different.
- uvdn7 4y ago
  That's not intended. What's your definition of cache consistency?
  - cratermoon 4y ago
    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?
throwdbaaway 4y ago
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.
- throwdbaaway 4y ago
  > 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.
  - uvdn7 4y ago
    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).
tremon 4y ago
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.
- uvdn7 4y ago
  > 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?
  - tremon 4y ago
    Actually, I was thinking of cache coherency protocols in multi-processor systems like MESIF or MOESI: - https://en.wikipedia.org/wiki/Cache_coherency_protocols_(examples) https://en.wikipedia.org/wiki/Cache_coherency_protocols_(exa... - https://www.cs.utexas.edu/~pingali/CS377P/2018sp/lectures/mesi.pdf 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_invalidation https://briandunnington.github.io/distributed_cache_invalida... ;)
    - uvdn7 4y ago
      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.
deleted 4y ago
[deleted]
btown 4y ago
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/ 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/ 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.
- moralestapia 4y ago
  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/ETag https://developer.mozilla.org/en-US/docs/Web/HTTP/Headers/ET...

uvdn7 4y ago

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

moralestapia 4y ago
No, mine was not a question, it was a statement. You misnamed the problem you are trying to solve.
- uvdn7 4y ago
  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.
  - moralestapia 4y ago
    >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 :)
    - 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

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.

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

seqizz 4y ago

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

cratermoon 4y ago

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

uvdn7 4y ago
That's not intended. What's your definition of cache consistency?
- cratermoon 4y ago
  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?

throwdbaaway 4y ago

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.

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

tremon 4y ago

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.

uvdn7 4y ago
> 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?
- tremon 4y ago
  Actually, I was thinking of cache coherency protocols in multi-processor systems like MESIF or MOESI: - https://en.wikipedia.org/wiki/Cache_coherency_protocols_(examples) https://en.wikipedia.org/wiki/Cache_coherency_protocols_(exa... - https://www.cs.utexas.edu/~pingali/CS377P/2018sp/lectures/mesi.pdf 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_invalidation https://briandunnington.github.io/distributed_cache_invalida... ;)
  - uvdn7 4y ago
    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.

deleted 4y ago

[deleted]

btown 4y ago

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

moralestapia 4y ago
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/ETag https://developer.mozilla.org/en-US/docs/Web/HTTP/Headers/ET...