7 ms·

Correct me if I'm wrong, but the title seems a little clickbaity. "Cache invalidation might no longer be hard" --> "We built a tracing library and manually fixe

Correct me if I'm wrong, but the title seems a little clickbaity. "Cache invalidation might no longer be hard" --> "We built a tracing library and manually fixed the bugs it uncovered"

uvdn7 4y ago
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 explained why cache invalidation is hard; and how we solve/manage its unique challenge and complexity. By my definition, we are solving the cache invalidation problem. The analogy I have is Paxos. It's notoriously hard to implement Paxos correctly. Google published a paper on Paxos Made Live just on how they managed the implementation and productionization complexity.
- 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.
- darig 4y ago
kilburn 4y ago
"A little clickbaity" if you are generous. Short-sighted and grandiloquent if you are not. Short-sighted because it narrows the original problem (cache invalidation) to a specific version (detecting cache invalidation errors past an arbitrary time-frame). Grandiloquent because it then claims to have "solved" the general problem, whereas they haven't even solved the narrowed version. Notice their own premise: > For any anomaly in a stateful service, it is an anomaly only if clients can observe it one way or the other. Otherwise, we argue that it doesn’t matter at all. This is a practical attitude that can yield great results, and probably even good engineering practice. However, it will never lead to solving a problem, because a problem isn't solved until you prove that it is.
- uvdn7 4y ago
  > For any anomaly in a stateful service, it is an anomaly only if clients can observe it one way or the other. Otherwise, we argue that it doesn’t matter at all. Thanks for the comment! I stand by this claim; I would love to hear more about why an anomaly (any anomaly) matters if it can't possibly be observed by any client for stateful service.
  - tofuahdude 4y ago
    It is just the difference between "matters" and "solved".
  - kilburn 4y ago
    The claim itself is fine because it is kind of tautological. An error that cannot be observed in any way is probably not an error. However, you have to prove that it can't be observed. This is quite different than what the described system does though. The system flags errors that have been observed. The correct claim to go with what the article does would thus be: > For any anomaly in a stateful service, it is an anomaly only if the current clients running their current operations happen to observe it. Otherwise, we argue that it doesn't matter at all. It's much more noticeable this way, isn't it?
    - uvdn7 4y ago
dang 4y ago
Yes - we changed it now and I posted https://news.ycombinator.com/item?id=31672562 https://news.ycombinator.com/item?id=31672562.

Correct me if I'm wrong, but the title seems a little clickbaity. "Cache invalidation might no longer be hard" --> "We built a tracing library and manually fixed the bugs it uncovered"

uvdn7 4y ago

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 explained why cache invalidation is hard; and how we solve/manage its unique challenge and complexity. By my definition, we are solving the cache invalidation problem. The analogy I have is Paxos. It's notoriously hard to implement Paxos correctly. Google published a paper on Paxos Made Live just on how they managed the implementation and productionization complexity.

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

kilburn 4y ago

"A little clickbaity" if you are generous. Short-sighted and grandiloquent if you are not. Short-sighted because it narrows the original problem (cache invalidation) to a specific version (detecting cache invalidation errors past an arbitrary time-frame). Grandiloquent because it then claims to have "solved" the general problem, whereas they haven't even solved the narrowed version. Notice their own premise: > For any anomaly in a stateful service, it is an anomaly only if clients can observe it one way or the other. Otherwise, we argue that it doesn’t matter at all. This is a practical attitude that can yield great results, and probably even good engineering practice. However, it will never lead to solving a problem, because a problem isn't solved until you prove that it is.

uvdn7 4y ago
> For any anomaly in a stateful service, it is an anomaly only if clients can observe it one way or the other. Otherwise, we argue that it doesn’t matter at all. Thanks for the comment! I stand by this claim; I would love to hear more about why an anomaly (any anomaly) matters if it can't possibly be observed by any client for stateful service.
- tofuahdude 4y ago
  It is just the difference between "matters" and "solved".
- kilburn 4y ago
  The claim itself is fine because it is kind of tautological. An error that cannot be observed in any way is probably not an error. However, you have to prove that it can't be observed. This is quite different than what the described system does though. The system flags errors that have been observed. The correct claim to go with what the article does would thus be: > For any anomaly in a stateful service, it is an anomaly only if the current clients running their current operations happen to observe it. Otherwise, we argue that it doesn't matter at all. It's much more noticeable this way, isn't it?
  - uvdn7 4y ago

dang 4y ago

Yes - we changed it now and I posted https://news.ycombinator.com/item?id=31672562 https://news.ycombinator.com/item?id=31672562.