Hacker News Reader

Comment by kazinator | Hacker News Reader

Invalidating caches is super easy when you don't have to do it. You just pick some element of the cache and blow it away; nothing is affected other than performance.

What is hard is invalidating a cache in that situation when an item must be removed from the cache, because it no longer exists outside the cache. If that is not done, you get a stale cache entry, which is incorrect and possibly breaks the system.

So now suppose the cache is multi-threaded, distributed and whatever. Now you have edge cases and race conditions. Is it okay if the item is gone, but the cache remains for just a little window of time? If not, can we remove it from the cache first, then for real? What if in between those two, something accesses it so it reappears in the cache? Pardon me, did I say the cache? I meant seventeen different caches throughout the distributed system ...

View on HN

And now imagine all of this logic has to be implemented in the form of silicon transistors that cannot be changed without incurring many millions of $ in losses if a tiny bug slips through. And the tiniest bug will most likely make every application under the sun crash within a few seconds, or at least deliver wrong results.

That's basically what happens today in bleeding-edge CPU architecture development.

In the area of caching among multiple cores, we have well-researched cache coherency protocols that can be implemented.

We can assume all the processors that are relevant are online; no processor core will try to invalidate an item while being cut off from communication, which is then re-established later. (If a processor comes online dynamically, we can assume it's coming in with a clear cache.)

Bus snooping is possible: every cache can see every memory access, and based on that, it can invalidate (or even update) entries that would be made stale due to stores. In a distributed system, no such thing is possible; you can't feasibly have 10,000 geographically distributed nodes all watching every transaction.

We can also assume that any remaining race conditions are handled by the software: that the software will use tools like memory barriers in the right places; we don't have to solve every possible concurrency problem that interacts with caching effects.

Careful, memory barriers/fences have nothing to do with caches, they're for establishing an observed order on when the processor is using out of order execution. The cache still has to be strongly consistent at all times or else there's nothing that a memory barrier can do to save it.

>Is it okay if the item is gone, but the cache remains for just a little window of time? If not, can we remove it from the cache first, then for real?

This is typically called eventual consistency [1] which is common when working with distributed systems, the same way you may write an entry and doesn’t become immediately available. This is often the case on my day to day work and you “just” have to work under the assumption that data isn’t the most recent sometimes.

[1] https://en.wikipedia.org/wiki/Eventual_consistency

Eventual consistency, if I recall correctly, stands for “race conditions”. During the NoSQL craze I read one opinion piece on it that I thought was pretty well put together. It boiled down to this: eventual consistency data stores are easy to implement so lots of people create them. But they are not easy to use, just easy to get started on. They are fine until they aren’t and they are overused as a solution to anything distributed.

I personally much prefer to start with a system that has strong consistency guarantees and then relax those guarantees exactly where necessary. Trying to work it from the other end will show you exactly why data store developers often choose EC even if it’s not the best pattern.

It's perfectly fine to use an EC system for many use cases. Caches are a perfect example. If one reader happens to get a stale entry from a cache, but that stale entry is sufficient for your task, why pay the price of transactions?

As an example, I build a system with exclusively commutative, restricted operations. What that means is that I can look at an item and know, regardless of when that item was written, that only certain operations will be applied in certain ways.

To serve a query, such as "Find me the item with an element X greater than 100", I don't need to find every item's consistent state of X. If an item's X from cache is, say, 50, and I know that X is restricted to only ever shrink in value, I don't need to hit the database for a consistent view of X.

Application level constraints like this are much more powerful than database transactions and radically more efficient, which is why EC systems can perform so well.

Not if you are caching permissions. Or bank account balances. Or game scores. Or a million other things that are not Facebook comments.

OK, don't do that? Or do it carefully.

We do it to answer very correctness-sensitive questions around security, but it doesn't matter because stale answers are still valid if you know how those answers could have possibly been updated - and that's just an application invariant.

In that very specialized case this works. Does your system have any guarantees beyond eventual consistency where eventual could mean hours or days?

My point is that in general, EC is not a feature. Nobody sets out hoping to find a database that provides EC. They usually set out to find a database that can be globally distributed and have strong ACID guarantees. When confronted with various cost constrains they eventually settle for a system that makes trade offs where part of the price is EC. They then work around EC, usually not completely but enough that most of the time the system works fine. But EC is not in and of itself good or desirable, it’s just a less of several evils. Moreover, of the evils that it does compete with its necessarily the least, just the easiest to implement and as a result the most popular.

Your argument of “it works in this one case and it works well” is a bit of a straw man in that no cache at all also works in some cases, but that doesn’t make it a general solution. I have successfully used an EC system for a decently sized (at the time at least) dataset and it worked well but it was only because that particular workflow naturally allowed for EC semantics (streaming updates every few seconds/source). But I sure as hell wouldn’t want to build a bank on EC.

> In that very specialized case this works.

The specialized case is where you can ensure a few application level constraints about your data, which so far in my experience are extremely valuable constraints. It's maybe a less trotted road, but not a difficult one.

The benefit is massive improvements to performance and reduction in complexity - you eliminate the need for a complex consensus system.

It is far more than "it works in this one case", it is that EC removes a massive cost in databases that is often unnecessary - transactional logic, and in return it gives huge improvements in other areas. Specifically, and relevant to this thread (because the article is on caching), in the area of caching this is particularly desirable.

This is, as another user mentioned, called strong eventual consistency.

Your comment compared EC to race conditions, which I think is quite a negative way to view them, so I wanted to point out that EC is not "strictly worse" or buggy or whatever.

I think you are saying what I am saying: in specialized cases EC is fine and a good cost saving measure.

My only addition to that is that it’s popularity may be due to ease of developing EC databases vs ones with distributed consensus algorithms, and that personally I prefer to start with a system not based on EC, then add EC where necessary whereas it sounds like you prefer to start with EC and add constraints. I think your approach is more popular, but in my personal work experience it leads to more fragile systems which is why I advocate for at least understanding why that choice is being made.

EC systems aren’t inherently buggy. They just by themselves don’t include guarantees that you might find useful or desirable for general workloads.

To establish that using an EC system is "perfectly safe" for any given use case, stronger properties are required than mere EC since that by itself provides no safety guarantees at all, only an assertion that data will "eventually" be reconciled in some arbitrary way. One example would be "strong eventual consistency" as provided by CRDT's ("conflict-free replicated data types").

Yep, exactly. It's actually pretty trivial for some work. If you can do that, you get the best of both worlds. Lots of queries can be answered with stale data, which means you drop the massive overhead of strong consistency and transactional workloads.

Reply on news.ycombinator.com