4 ms·

Saying a problem isn't hard to solve because you have tools to analyze the correctness of your solution seems like a stretch.

uvdn7 4y ago
But that's not what I am saying though ... > you have tools to analyze the correctness of your solution That's half of it. Cache invalidation is hard not only because of the complexity of cache coherence protocols, some of which is not very complicated. But cache invalidation does introduce countless races that manage to introduce cache inconsistencies in ways that are just hard to imagine ahead of time (in my experience). IMO, that's the harder part of cache invalidation – when cache inconsistencies happen, answering the "why" question is much harder than having a cache invalidation protocol (you can have TLA+ for one if you will). And answering the "why my cache is inconsistent" is the problem we solved, which I think is the harder part of the cache invalidation problem.
- latchkey 4y ago
  > answering the "why my cache is inconsistent" is the problem we solved That should be the title and focus of your post. Instead, it feels like grandiose claims about solving cache invalidation itself.
  - uvdn7 4y ago
    > Instead, it feels like grandiose claims about solving cache invalidation itself. That is definitely something I worried about. But at the same time, I do think we solved the harder part of the cache invalidation problem. TAO and Memcache serves quadrillions queries a day. Based on our experience, answering the question of "why my cache is inconsistent" is the hardest thing about cache invalidation. Cache invalidation protocols can be complicated, but some are pretty managable. You can also verify it using TLA+ if you will. But once the rubber hits the road, some cache entries tend to be inconsistent. I definitely worry about people taking this the wrong way, but at the same time, I stand by the claim of "cache invalidation might no longer be a hard thing in computer science".
    - latchkey 4y ago
      The jist of what I got from the post was that you created a tool which monitors caches and that helped find bugs that cause inconsistent cache issues. How is that solving a computer science problem?
      - uvdn7 4y ago
        The tool that monitors cache consistency is easy to build. That by itself doesn't solve anything major. The most important contribution is a novel approach on consistency tracing that helps find out "why" caches are inconsistent – pinpoint a bug is much harder than saying "there is a bug". This is based on the key insight that a cache inconsistency can only be introduced (for an invalidation-based cache) in a short time window after the write/mutation, this is what makes the tracing possible. > How is that solving a computer science problem? It depends on your definition of a computer science problem. I am definitely not solving P = NP. By your definition, does Google's Paxos Made Live paper solve a computer science problem? The claim is more a play on Phil Karlton's quote, as the work here makes cache invalidation much easier (in my opinion). Also Phil Karlton's quote doesn't necessarily _make_ a problem a computer science problem, don't you think? I think it's a good quote and there's a lot of truth in it.
        latchkey 4y ago
        I disagree with your claim that "cache invalidation might no longer be a hard thing in computer science" for the same reason that you say that pinpointing bugs is harder than saying "there is a bug". You can't just build a tool and declare a whole problem space in computer science (and a long running joke) as being solved. > the work here makes cache invalidation much easier The tool itself doesn't make cache invalidation easier, it makes finding bugs (that happen to be cache invalidation bugs), easier. By that logic, if one never wrote a bug, cache invalidation would still be as difficult as before. Again, good work on the tool. That's fantastic. I've definitely done some huge work in this area myself and struggled a lot. Let's also realize that it is also FB internal, so whatever solutions you've come up with aren't really helping anyone else without spending the same amount of engineering time and resources on the problem.

uvdn7 4y ago

But that's not what I am saying though ... > you have tools to analyze the correctness of your solution That's half of it. Cache invalidation is hard not only because of the complexity of cache coherence protocols, some of which is not very complicated. But cache invalidation does introduce countless races that manage to introduce cache inconsistencies in ways that are just hard to imagine ahead of time (in my experience). IMO, that's the harder part of cache invalidation – when cache inconsistencies happen, answering the "why" question is much harder than having a cache invalidation protocol (you can have TLA+ for one if you will). And answering the "why my cache is inconsistent" is the problem we solved, which I think is the harder part of the cache invalidation problem.

latchkey 4y ago
> answering the "why my cache is inconsistent" is the problem we solved That should be the title and focus of your post. Instead, it feels like grandiose claims about solving cache invalidation itself.
- uvdn7 4y ago
  > Instead, it feels like grandiose claims about solving cache invalidation itself. That is definitely something I worried about. But at the same time, I do think we solved the harder part of the cache invalidation problem. TAO and Memcache serves quadrillions queries a day. Based on our experience, answering the question of "why my cache is inconsistent" is the hardest thing about cache invalidation. Cache invalidation protocols can be complicated, but some are pretty managable. You can also verify it using TLA+ if you will. But once the rubber hits the road, some cache entries tend to be inconsistent. I definitely worry about people taking this the wrong way, but at the same time, I stand by the claim of "cache invalidation might no longer be a hard thing in computer science".
  - latchkey 4y ago
    The jist of what I got from the post was that you created a tool which monitors caches and that helped find bugs that cause inconsistent cache issues. How is that solving a computer science problem?
    - uvdn7 4y ago
      The tool that monitors cache consistency is easy to build. That by itself doesn't solve anything major. The most important contribution is a novel approach on consistency tracing that helps find out "why" caches are inconsistent – pinpoint a bug is much harder than saying "there is a bug". This is based on the key insight that a cache inconsistency can only be introduced (for an invalidation-based cache) in a short time window after the write/mutation, this is what makes the tracing possible. > How is that solving a computer science problem? It depends on your definition of a computer science problem. I am definitely not solving P = NP. By your definition, does Google's Paxos Made Live paper solve a computer science problem? The claim is more a play on Phil Karlton's quote, as the work here makes cache invalidation much easier (in my opinion). Also Phil Karlton's quote doesn't necessarily _make_ a problem a computer science problem, don't you think? I think it's a good quote and there's a lot of truth in it.
      - latchkey 4y ago
        I disagree with your claim that "cache invalidation might no longer be a hard thing in computer science" for the same reason that you say that pinpointing bugs is harder than saying "there is a bug". You can't just build a tool and declare a whole problem space in computer science (and a long running joke) as being solved. > the work here makes cache invalidation much easier The tool itself doesn't make cache invalidation easier, it makes finding bugs (that happen to be cache invalidation bugs), easier. By that logic, if one never wrote a bug, cache invalidation would still be as difficult as before. Again, good work on the tool. That's fantastic. I've definitely done some huge work in this area myself and struggled a lot. Let's also realize that it is also FB internal, so whatever solutions you've come up with aren't really helping anyone else without spending the same amount of engineering time and resources on the problem.