Hacker News Reader

Comment by jitl | Hacker News Reader

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?

View on HN

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

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!

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.

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.

> 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.

I acknowledge that both are hard. The former can't be avoided. And the latter is easy in certain cases (if you have a simpler data model, etc.). I am not saying the latter is easy. More details in https://news.ycombinator.com/item?id=31676102

And I made the mistake of assuming the definition of “cache invalidation” as it means different things to different people. Marc’s view is a very good one https://twitter.com/marcjbrooker/status/1534944340266864640?... but it’s actually different than some people’s definition on this thread.

I will not defend myself; and you are welcome to speculate. I said it here https://twitter.com/uvdn7/status/1534978702609682432, and other places on this thread, and I will repeat it again.

I should have applied a narrower and more specific definition of cache invalidation in the blog post. The confusion it caused is not intended.

> how to implement invalidating it when you know exactly what needs invalidation

I stand by the claim that this is a hard problem, as explained in the blog post. When you deal with a cache you are inherently dealing with a distributed system (there's cache and the source of truth). And the contribution is making this aspect more manageable, which is common to all invalidation based caches.

You think figuring out when to invalidate is the harder part of cache invalidation; in that sense Polaris is not checking the “when” logic but rather repeating it. And you are right. This is not the problem we solved in the post. I should have applied a narrower definition to cache invalidation, and I apologize for the confusions.

On the other hand, I don’t think figuring out “when” to invalidate is what makes cache invalidation hard. I shared the same view as Marc https://twitter.com/marcjbrooker/status/1534944340266864640?....

There is a trade off between coordination (in some cases with unbounded write amplification https://twitter.com/uvdn7/status/1534979480363667457?s=21&t=...) and relaxed consistency. I assumed this is a trade off that people just have to make based on their workload (hence you saw me saying in other comments about TTL; it’s about tradeoffs, when the cost of coordination/invalidate surpasses the benefit — higher hit rate, etc.)

https://blog.the-pans.com/when-and-how-to-invalidate-cache/ Does this address the "knowing what needs invalidation" part?

I basically wrote a separate blog just for replying to this https://blog.the-pans.com/when-and-how-to-invalidate-cache/.

Reply on news.ycombinator.com