6 ms·

I am the author of the blog post. I believe the methodology described should be applicable to most if not all invalidation-based caches. I am serious when I say

by uvdn7 4y ago

I am the author of the blog post. I believe the methodology described should be applicable to most if not all invalidation-based caches. I am serious when I say that cache invalidation might no longer be a hard thing in computer science. AMA!

politician 4y ago
I read the article. It seems to be suggesting that cache invalidation might no longer be a hard thing in computer science because of the insights uncovered by your tracing and observability solution. IOW, now that you can measure and audit the system, you're able to find and fix bugs in the system. Is that the correct take-away?
- uvdn7 4y ago
  Yep. You're exactly right. And the approach is generic and I think it should work for everyone. The idea is that with all these observability capabilities, debugging cache inconsistencies is getting very actionable and close to how we debug an error with message telling us exactly where an exception happened.
deleted 4y ago
[deleted]
robmccoll 4y ago
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.
jitl 4y ago
How do you handle caching derived data assembled from multiple individual records? For example, how would you maintain a cache for a query like getFriendsOfFriends(userId)? My context is working on Notion’s caches for page data. Our pages are made out of small units called “blocks” that store pointers to their child content. To serve all the blocks needed to render a page, we need to do a recursive traversal of the block tree. We have an inconsistent cache of “page chunks” right now, how would you think about making a consistent cache?
- uvdn7 4y ago
  This is fantastic question! We face something very similar (if not identical). There are two parts to solve this problem 1. monitor and measure how consistent the cache is 2. figure out why they are inconsistent I will focus on #1 in this comment. You can build something very similar to Polaris (mentioned in the blog) that - tails your database's binlog so it knows when e.g. "friendship" data is mutated - it can then perform the computation to figure out which cache entries "should have been" updated. E.g. if Alice just friended Bob, then Alice's friends-of-friends and Bob's friends-of-friends should reflect the change. And your monitoring service will "observe" that and alert on anomalies
  - ahahahahah 4y ago
    So if you just implement the cache invalidation logic in your monitoring system, you can tell if you got the cache invalidation logic correct in your caching system. That sounds really helpful!
    - uvdn7 4y ago
      That's not the case though. Polaris acts as a client and only monitors client observable effect, and assumes no knowledge of the server internals. I am trying to help.
      - ahahahahah 4y ago
        This continues to point out how you just completely don't understand the quote. You very clearly seem to think that the "hard" part of cache invalidation is how to implement invalidating it when you know exactly what needs invalidation. The "hard" part is actually in knowing what needs invalidation. Your grandiose claims make you, your team and org, and your company look bad.
continuational 4y ago
With the risk of stating the obvious - the hard part of cache invalidation is to know when to invalidate the cache.
- uvdn7 4y ago
  We invalidate cache upon mutations. When else would you do it?
  - continuational 4y ago
    Please see https://news.ycombinator.com/item?id=31672541 https://news.ycombinator.com/item?id=31672541
rajesh-s 4y ago
Off topic but what tool did you use to create those cache hierarchy diagrams?
simonw 4y ago
Is your argument here that cache invalidation may no longer be hard because you can implement systems like Polaris which continually test your cache implementation to try and catch invalidation problems so you can then go and fix them? EDIT: Already answered in this reply: https://news.ycombinator.com/item?id=31671794 https://news.ycombinator.com/item?id=31671794
- uvdn7 4y ago
  Polaris is actually fairly simple to build. The harder question to answer is "why cache is inconsistent" and how you debug. The second half of the post talks about consistency tracing, which tracks all cache data state mutations. Distributed systems are state machines, with consistency tracing keeping track of all the state transitions, debugging cache inconsistencies in an invalidation-based cache is very actionable and managable based on our experience.
ArrayBoundCheck 4y ago
I didn't understand the tracing part. Is tracing 100% inside of polaris? If not does it start at the database? The first cache? Does the invalidation need to be predictable before you can use tracing? What kind of parameters do you have so you don't have too much logging or too little?
- uvdn7 4y ago
  Tracing is not in polaris. It's a separate library that runs in every cache host. Its main job is logging every cache state mutation for traced writes. So when polaris detects cache inconsistencies, we know what happened and why cache is inconsistent. It starts all the way from client initiated write (where we mint a unique id, and plumb it all the way through). > What kind of parameters do you have so you don't have too much logging or too little? This is the key question! If you go to the second half of the post, it talks about an insight about how we managed to log only when and where cache inconsistencies _can_ be introduced. There's only a small window after mutation/write where cache can become inconsistent due to invalidation. So it's very cheap to trace and provide the information we need.
nixpulvis 4y ago
Correct me if I'm wrong, but don't we have general solutions that ensure correctness if you allow for enough time? Wouldn't performance be a critical aspect of the claim that this is "no longer a hard problem"? How about the CAP theorem?
- uvdn7 4y ago
  The "hard problem" defined here is more about the engineering side. The analogy I have is Paxos the protocol and Google's Paxos Made Live paper. We do have many cache coherency protocols that are provably correct (using TLA+ if you will); but making them actually consistent in production is a completely different story; and a hard problem for an invalidation-based cache.
  - gnomeduck 4y ago
    Can you speak more on why ‘making them actually consistent in production is a completely different story’? Curious because I’ve been learning TLA+ recently and interested to more know about cases where an algorithm has been proven but actual an implementation of it fails.
    - uvdn7 4y ago
      Let try to put this as concisely as possible. When you put an algorithm in code, when rubber hits the road, you have to make certain assumptions of how things work, eg how events are ordered, how fsync works, what kind of failure scenarios you are expecting, etc. More likely than not, the reality will be a little different. No to measure just innocent bugs in the code. My favorite example is Paxos. Its algorithm fits on a single slide. But it’s notoriously hard to make it actually work correctly in production.

by uvdn7 4y ago

politician 4y ago

I read the article. It seems to be suggesting that cache invalidation might no longer be a hard thing in computer science because of the insights uncovered by your tracing and observability solution. IOW, now that you can measure and audit the system, you're able to find and fix bugs in the system. Is that the correct take-away?

uvdn7 4y ago
Yep. You're exactly right. And the approach is generic and I think it should work for everyone. The idea is that with all these observability capabilities, debugging cache inconsistencies is getting very actionable and close to how we debug an error with message telling us exactly where an exception happened.

deleted 4y ago

[deleted]

robmccoll 4y ago

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.

jitl 4y ago

How do you handle caching derived data assembled from multiple individual records? For example, how would you maintain a cache for a query like getFriendsOfFriends(userId)? My context is working on Notion’s caches for page data. Our pages are made out of small units called “blocks” that store pointers to their child content. To serve all the blocks needed to render a page, we need to do a recursive traversal of the block tree. We have an inconsistent cache of “page chunks” right now, how would you think about making a consistent cache?

uvdn7 4y ago
This is fantastic question! We face something very similar (if not identical). There are two parts to solve this problem 1. monitor and measure how consistent the cache is 2. figure out why they are inconsistent I will focus on #1 in this comment. You can build something very similar to Polaris (mentioned in the blog) that - tails your database's binlog so it knows when e.g. "friendship" data is mutated - it can then perform the computation to figure out which cache entries "should have been" updated. E.g. if Alice just friended Bob, then Alice's friends-of-friends and Bob's friends-of-friends should reflect the change. And your monitoring service will "observe" that and alert on anomalies
- ahahahahah 4y ago
  So if you just implement the cache invalidation logic in your monitoring system, you can tell if you got the cache invalidation logic correct in your caching system. That sounds really helpful!
  - uvdn7 4y ago
    That's not the case though. Polaris acts as a client and only monitors client observable effect, and assumes no knowledge of the server internals. I am trying to help.
    - ahahahahah 4y ago
      This continues to point out how you just completely don't understand the quote. You very clearly seem to think that the "hard" part of cache invalidation is how to implement invalidating it when you know exactly what needs invalidation. The "hard" part is actually in knowing what needs invalidation. Your grandiose claims make you, your team and org, and your company look bad.

continuational 4y ago

With the risk of stating the obvious - the hard part of cache invalidation is to know when to invalidate the cache.

uvdn7 4y ago
We invalidate cache upon mutations. When else would you do it?
- continuational 4y ago
  Please see https://news.ycombinator.com/item?id=31672541 https://news.ycombinator.com/item?id=31672541

rajesh-s 4y ago

Off topic but what tool did you use to create those cache hierarchy diagrams?

simonw 4y ago

Is your argument here that cache invalidation may no longer be hard because you can implement systems like Polaris which continually test your cache implementation to try and catch invalidation problems so you can then go and fix them? EDIT: Already answered in this reply: https://news.ycombinator.com/item?id=31671794 https://news.ycombinator.com/item?id=31671794

uvdn7 4y ago
Polaris is actually fairly simple to build. The harder question to answer is "why cache is inconsistent" and how you debug. The second half of the post talks about consistency tracing, which tracks all cache data state mutations. Distributed systems are state machines, with consistency tracing keeping track of all the state transitions, debugging cache inconsistencies in an invalidation-based cache is very actionable and managable based on our experience.

ArrayBoundCheck 4y ago

I didn't understand the tracing part. Is tracing 100% inside of polaris? If not does it start at the database? The first cache? Does the invalidation need to be predictable before you can use tracing? What kind of parameters do you have so you don't have too much logging or too little?

uvdn7 4y ago
Tracing is not in polaris. It's a separate library that runs in every cache host. Its main job is logging every cache state mutation for traced writes. So when polaris detects cache inconsistencies, we know what happened and why cache is inconsistent. It starts all the way from client initiated write (where we mint a unique id, and plumb it all the way through). > What kind of parameters do you have so you don't have too much logging or too little? This is the key question! If you go to the second half of the post, it talks about an insight about how we managed to log only when and where cache inconsistencies _can_ be introduced. There's only a small window after mutation/write where cache can become inconsistent due to invalidation. So it's very cheap to trace and provide the information we need.

nixpulvis 4y ago

Correct me if I'm wrong, but don't we have general solutions that ensure correctness if you allow for enough time? Wouldn't performance be a critical aspect of the claim that this is "no longer a hard problem"? How about the CAP theorem?

uvdn7 4y ago
The "hard problem" defined here is more about the engineering side. The analogy I have is Paxos the protocol and Google's Paxos Made Live paper. We do have many cache coherency protocols that are provably correct (using TLA+ if you will); but making them actually consistent in production is a completely different story; and a hard problem for an invalidation-based cache.
- gnomeduck 4y ago
  Can you speak more on why ‘making them actually consistent in production is a completely different story’? Curious because I’ve been learning TLA+ recently and interested to more know about cases where an algorithm has been proven but actual an implementation of it fails.
  - uvdn7 4y ago
    Let try to put this as concisely as possible. When you put an algorithm in code, when rubber hits the road, you have to make certain assumptions of how things work, eg how events are ordered, how fsync works, what kind of failure scenarios you are expecting, etc. More likely than not, the reality will be a little different. No to measure just innocent bugs in the code. My favorite example is Paxos. Its algorithm fits on a single slide. But it’s notoriously hard to make it actually work correctly in production.