4 ms·

I am the author; so I am obviously biased here. I am serious when I say cache invalidation might no longer be a hard thing in computer science. In the post, I

• continuational 4y ago
  Please be careful with such bold claims. You don't really address the hard part of cache invalidation, which is to figure out when to do it.
  • uvdn7 4y ago
    > which is to figure out when to do it. Can you elaborate?
    • continuational 4y ago
      Sure - you typically cache the result of some expensive query. The hard part of cache invalidation is to detect when an update somewhere in your system is going to affect the result of that query, such that you need to trigger an invalidation.
      • 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.
• darig 4y ago