Hacker News Reader

Comment by uvdn7 | Hacker News Reader

I am glad that you liked the content.

On the definition of cache invalidation, and specifically why it's hard. Can you send me a link to any definition of it? This is what's in wikipedia and I think it's reasonable.

> Cache invalidation is a process in a computer system whereby entries in a cache are replaced or removed.

And I think I am describing that process, and what's hard about it. Some comments here explicitly talk about dependencies, which I can see why it's hard. My point is that even without dependencies, cache invalidation remains a hard problem. Now about dependency tracking, some of my thoughts are captured here https://news.ycombinator.com/item?id=31674933.

View on HN

Numerous replies to your comments here have pointed out why cache invalidation is hard. You've responded to them by saying "Good point!" (always with an exclamation point), and then proceeded to demonstrate in your response that you didn't understand their point.

This comment describes the "hard" part of cache invalidation best: https://news.ycombinator.com/item?id=31674251 - your response to them makes very little sense.

First, you acknowledge that they're correct, though you use obtuse language to say so: you seem to like using the very abstract term "dependency" to represent the very simple concept of detecting updates.

In your second paragraph you then go off on an unrelated tangent by saying:

> Now getting back to the “what’s really hard about cache invalidation” part.

No. You're not "getting back" to that - you're changing the subject back to the topic of your article, which is unrelated to cache invalidation.

> Say you just have a k/v store, no joins, nothing.

Cache invalidation is about invalidation - it's not about your store architecture. It's not about the implementation of logic that processes the clearing/overwrite of values, it's about the when and nothing else.

> just doing TTL, would be simpler.

Yes. It is simpler. If you want to avoid solving the hard problem, you can use a TTL. Now... how long should it be?

First of all, I do think you folks make good points. Let me try again.

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

I wrote this line, which is referred to as that being exactly why cache invalidation is hard, in the commented you linked.

> it's about the when and nothing else.

Let's talk about that. Not to over generalize this, with a simpler cache model (say you just cache a single item), do you agree that solving the "when" problem is very managable? If not, I would like to be enlightened.

Now with this very simple cache model, where we have "magically" solved the "when" problem. Do you think cache invalidation is solved? Or it's simple? After knowing when, you still need to actually update cache right, and not to leave it in an inconsistent state (against the source of truth). Is that simple?

Let's essentially break cache invalidation into a few parts 1. knowing when/who to invalidate 2. actually processing the invalidate

My argument is that #1 can be very managable with simpler data models. #2 can't be avoided; and #2 is very hard.

> with a simpler cache model (say you just cache a single item), do you agree that solving the "when" problem is very managable?

The "when" problem is dependent on your application architecture, not on your cache backend nor the number of keys in it.

If, overall, you have an extremely simplistic application architecture, then cache invalidation may be quite easy, but you'll either:

1. forgo advanced user interaction or dynamic updates, in which case cache invalidation may not even be required at all (excepting publishing)

2. have scalability problems, and need to increase the complexity of your application to meet those challenges

The difficulty of cache invalidation scales with the complexity of your application (and not necessarily linear scaling)

> My argument is that #1 can be very managable with simpler data models. #2 can't be avoided; and #2 is very hard.

Yes, #1 can be manageable for low-traffic simple static applications. It is a general problem who's difficulty relates to the complexity of the application.

Yes, #2, can't be avoided. But, while it is interesting, and - in some cases, given a specific caching stack - it may be relatively hard, it's not a general problem. Difficulties with it are implementation-specific, not broadly applicable. Significantly, it's not the general and fundamental hard problem being referred when people talk about the universal difficulty of "cache invalidation".

> The "when" problem is dependent on your application architecture, not on your cache backend nor the number of keys in it.

I would argue the "when" problem is dependent on data models. And it's possible that we are referring to the same thing with different names.

> If, overall, you have an extremely simplistic application architecture

I mean FB is not a simple app. A complicated app can be built on a relatively simple data model as well (that's essentially how TAO works). But we do have memcache as well; and in some cases it can be complicated/hard. I can see that, and I won't argue against it.

> Yes, #2, can't be avoided. But, while it is interesting, and - in some cases, given a specific caching stack - it may be relatively hard, it's not a general problem.

I respectfully disagree. I explained in the blog post about why #2 is a generally hard problem. The analogy I like to use is Paxos. The protocol fits on a single slide. It's easier to feel like you have Paxos work; but it's very hard to have Paxos actually work.

Paxos is an implementation (of protocols).

I think you fundamentally misunderstand what the word "general" means here.

> Paxos is an implementation (of protocols).

I have nothing more to add, if that's your standpoint. But I am glad that we "debugged" to close to the "root" of our assumptions/context.

Let's solve the "cache invalidation problem" by your definition.

E.g. in its most generic form, a cache can store arbitrary materialization from any data source. Now when updating the data source, in order to keep caches consistent, you essentially need to transact (cross system transaction) on both the data source and cache(s). Usually cache has more number of replicas, I am not sure running this type of transactions is practical at scale.

What happens if we don't transact on both systems (the data source, and cache)? Well, now whenever the asynchronous update pipeline performs the computation, it's done against a moving data source (not a snapshot of when the write was committed). Now let's say the data source is Spanner, which provides point-in-time snapshots. On Spanner commit you can get a commit time (TrueTime) back. Now using that commit time, to read the data and compute cache update asynchronously can be done.

Because the materialization in cache don't take writes themselves, so updates to them are essentially performed blindly and can be ordered by the commit time (TrueTime).

Now this does assume whatever we cache (the query e.g.) needs to be schematized, and made known to the invalidation pipeline (in the form of some control plane metadata). I think it's a very fair assumption to make. As otherwise (anyone can cache anything without the invalidation pipeline knowing at all), it's pretty obvious that this problem can't be solved.

Reply on news.ycombinator.com