3 ms·

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 funct

by 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...
jitl 4y ago
Yeah, I came here for "Materialize but for Tao" and instead got "how we check correctness of Tao's single-entity cache"
uvdn7 4y ago
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.
uvdn7 4y ago
Thanks for the reference. Naiad: A Timely Dataflow System is an interesting paper!
- jitl 4y ago
  See also Noria, https://pdos.csail.mit.edu/papers/noria:osdi18.pdf 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/ https://readyset.io/
  - uvdn7 4y ago
    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 https://news.ycombinator.com/item?id=31676849.
    - jitl 4y ago
      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.
      - uvdn7 4y ago
        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.
uvdn7 4y ago
> 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.

by btown 4y ago

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

jitl 4y ago

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

uvdn7 4y ago

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.

uvdn7 4y ago

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

jitl 4y ago
See also Noria, https://pdos.csail.mit.edu/papers/noria:osdi18.pdf 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/ https://readyset.io/
- uvdn7 4y ago
  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 https://news.ycombinator.com/item?id=31676849.
  - jitl 4y ago
    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.
    - uvdn7 4y ago
      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.

uvdn7 4y ago

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