4 ms·

Good point! We have memcache which is a look-aside cache that serves this type of workload. What you described can be solved by adding one level of abstraction

by uvdn7 4y ago

Good point! We have memcache which is a look-aside cache that serves this type of workload. What you described can be solved by adding one level of abstraction and letting reads and writes all go through it. Now on your read path, you can construct arbitrary complex sql queries or whatnot, but it must take some kind of input to filter on. Those become part of the "keys". The invariant is that as long as the "context/filter" you encode covers all the mutations which would impact your cache data, you should be good. Based on our experience, it has been fairly managable.

irrational 4y ago
>The invariant is that as long as the "context/filter" you encode covers all the mutations which would impact your cache data, you should be good. Well, isn’t this the truly hard part of cache invalidation?
- ahahahahah 4y ago
  Yeah, the entire discussion here is fucked because the poster doesn't understand what the original quote even meant.
  - hinkley 4y ago
    Software developers: We didn't invent confidently incorrect, but by god are we going to become masters.
- uvdn7 4y ago
  I can see that. One can argue that the “difficulty” is front loaded. If or not you can identify the list of “context” is local. I guess you can probably come up with complicated dependencies and argue it’s hard to capture the dependencies and I would agree with you. Now getting back to the “what’s really hard about cache invalidation” part. Even with a much simpler model. Say you just have a k/v store, no joins, nothing. Is cache invalidation simple in that case? I went into details about why it’s still insanely hard. And the big example at the end might help make that point. And this is one level beneath challenges from tracking dependencies, and I argue that’s what makes cache invalidation hard. 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.
- uvdn7 4y ago
  I also think it can be solved by changing the data model. Say, you are caching a result of joining two tables with two ids that you are filtering on. It's still very managable to track the dependency and know when to invalidate. It can easily grow out of hand (talking about 10 table joins and 100 lines of SQL). Then solving the "when/who" to invalidate problem is essentially equivalent to doing "joins" on the write/invalidation path. First of all, it's unbounded. The number of cache entries you need to invalidate can be unbounded (not bounded by the number of indices, but a function of data in the database instead). My argument is that why do this to begin with? I acknowledge this is hard. But why do it? On the other hand, you can have simpler data models (e.g. TAO), fetching and stitching everything together on the read path scales fairly well. It's essentially doing "joins" on the read path. But it's all hitting caches, so it's fast still. For some complicated queries, you can cache secondary indices (which is easier to figure out the "when/who" question, just as how DB figures out which index entry to update on transactions) to make your read-path join faster.
- uvdn7 4y ago
  Let's actually also try to solve the "cache invalidation" by your definition. 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). 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)? 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). 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. Because the materialization in cache don't take writes themselves, so updates to them are essentially performed blindly and can be ordered by the commit time (TrueTime). 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.
  - hinkley 4y ago
    Throw a few bits of conditional logic onto that fire while you're at it. Some cache entries depend on the state of rows in Table C, but for some combinations of Table A and Table B, no data from Table C ends up in the cache entry. All of this is business logic, and now it's touching one of our supposedly low-level libraries, which is separated by at least one level of indirection from the rest of the business logic - if your architecture is good. But caching tends to rot architecture.
    - uvdn7 4y ago
      > Some cache entries depend on the state of rows in Table C, but for some combinations of Table A and Table B, no data from Table C ends up in the cache entry. This is a good example. Let's talk about it. Say we have a table for "friends", and a separate materialization, in cache!, for "friends-of-friends-who-lives-in-us". First of all, the query for the cache data needs to be schematized and made known to the data source. Otherwise, a client can cache arbitrary materialization of anything, it would be obvious that, in its most generic form, the problem can't be solved. Now assume the data in cache is schematized. There's a transaction that changes "friends" table. Now we have two options, one is that within the same transaction (x-system 2phase commit for example), updates cache (the one that stores "friends-of-friends-who-live-in-us"). This is the synchronous flavor of it, which has obvious scaling challenges. Spanner, etc. are about handling the async flavor of the same logic. > if your architecture is good. But caching tends to rot architecture. My speculation is that sometimes people are using cache without knowing they are dealing with a distributed system. A cache in its nature is a distributed system (because there's cache and the source of truth). The linked blog post is targeted towards cache service owners, not cache users (who puts materializations in cache). If I learned anything from this public civil discourse on Hacker News is that we should avoid putting the power/responsibility of cache invalidation in the hands of cache users we should provide guard rails via better abstractions, simpler data models (e.g. a graph data model) we should avoid caching relations (separate materializations) but prefer caching indices instead, so the write/invalidation amplification is bounded.
- uvdn7 4y ago
  https://blog.the-pans.com/when-and-how-to-invalidate-cache/ https://blog.the-pans.com/when-and-how-to-invalidate-cache/ Does this address the "knowing what needs invalidation" part?

by uvdn7 4y ago

irrational 4y ago

>The invariant is that as long as the "context/filter" you encode covers all the mutations which would impact your cache data, you should be good. Well, isn’t this the truly hard part of cache invalidation?

ahahahahah 4y ago
Yeah, the entire discussion here is fucked because the poster doesn't understand what the original quote even meant.
- hinkley 4y ago
  Software developers: We didn't invent confidently incorrect, but by god are we going to become masters.
uvdn7 4y ago
I can see that. One can argue that the “difficulty” is front loaded. If or not you can identify the list of “context” is local. I guess you can probably come up with complicated dependencies and argue it’s hard to capture the dependencies and I would agree with you. Now getting back to the “what’s really hard about cache invalidation” part. Even with a much simpler model. Say you just have a k/v store, no joins, nothing. Is cache invalidation simple in that case? I went into details about why it’s still insanely hard. And the big example at the end might help make that point. And this is one level beneath challenges from tracking dependencies, and I argue that’s what makes cache invalidation hard. 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.
uvdn7 4y ago
I also think it can be solved by changing the data model. Say, you are caching a result of joining two tables with two ids that you are filtering on. It's still very managable to track the dependency and know when to invalidate. It can easily grow out of hand (talking about 10 table joins and 100 lines of SQL). Then solving the "when/who" to invalidate problem is essentially equivalent to doing "joins" on the write/invalidation path. First of all, it's unbounded. The number of cache entries you need to invalidate can be unbounded (not bounded by the number of indices, but a function of data in the database instead). My argument is that why do this to begin with? I acknowledge this is hard. But why do it? On the other hand, you can have simpler data models (e.g. TAO), fetching and stitching everything together on the read path scales fairly well. It's essentially doing "joins" on the read path. But it's all hitting caches, so it's fast still. For some complicated queries, you can cache secondary indices (which is easier to figure out the "when/who" question, just as how DB figures out which index entry to update on transactions) to make your read-path join faster.
uvdn7 4y ago
Let's actually also try to solve the "cache invalidation" by your definition. 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). 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)? 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). 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. Because the materialization in cache don't take writes themselves, so updates to them are essentially performed blindly and can be ordered by the commit time (TrueTime). 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.
- hinkley 4y ago
  Throw a few bits of conditional logic onto that fire while you're at it. Some cache entries depend on the state of rows in Table C, but for some combinations of Table A and Table B, no data from Table C ends up in the cache entry. All of this is business logic, and now it's touching one of our supposedly low-level libraries, which is separated by at least one level of indirection from the rest of the business logic - if your architecture is good. But caching tends to rot architecture.
  - uvdn7 4y ago
    > Some cache entries depend on the state of rows in Table C, but for some combinations of Table A and Table B, no data from Table C ends up in the cache entry. This is a good example. Let's talk about it. Say we have a table for "friends", and a separate materialization, in cache!, for "friends-of-friends-who-lives-in-us". First of all, the query for the cache data needs to be schematized and made known to the data source. Otherwise, a client can cache arbitrary materialization of anything, it would be obvious that, in its most generic form, the problem can't be solved. Now assume the data in cache is schematized. There's a transaction that changes "friends" table. Now we have two options, one is that within the same transaction (x-system 2phase commit for example), updates cache (the one that stores "friends-of-friends-who-live-in-us"). This is the synchronous flavor of it, which has obvious scaling challenges. Spanner, etc. are about handling the async flavor of the same logic. > if your architecture is good. But caching tends to rot architecture. My speculation is that sometimes people are using cache without knowing they are dealing with a distributed system. A cache in its nature is a distributed system (because there's cache and the source of truth). The linked blog post is targeted towards cache service owners, not cache users (who puts materializations in cache). If I learned anything from this public civil discourse on Hacker News is that we should avoid putting the power/responsibility of cache invalidation in the hands of cache users we should provide guard rails via better abstractions, simpler data models (e.g. a graph data model) we should avoid caching relations (separate materializations) but prefer caching indices instead, so the write/invalidation amplification is bounded.
uvdn7 4y ago
https://blog.the-pans.com/when-and-how-to-invalidate-cache/ https://blog.the-pans.com/when-and-how-to-invalidate-cache/ Does this address the "knowing what needs invalidation" part?