4 ms·
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 perform
by kazinator 6y ago
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 ...
- Slartie 6y agoAnd 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.
- kazinator 6y agoIn 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.
- kcolford 6y agoCareful, 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.
- outime 6y ago>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 https://en.wikipedia.org/wiki/Eventual_consistency
- IgorPartola 6y agoEventual 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.
- staticassertion 6y agoIt'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.