19 ms·

I really love this point. For most applications the optimal size of a (time-based) cache is around the point that keeping an item around in the cache is equal

by mjb 4y ago

I really love this point. For most applications the optimal size of a (time-based) cache is around the point that keeping an item around in the cache is equal to the cost of accessing it again. This is a point that Jim Gray made in the classic "The 5 Minute Rule for Trading Memory for Disc Accesses" (http://www.hpl.hp.com/techreports/tandem/TR-86.1.pdf http://www.hpl.hp.com/techreports/tandem/TR-86.1.pdf) back in 1986. A side effect of that is that systems that run faster, and therefore access each cached it more often, get more benefit out of a cache by pushing that set point out further. Whether that happens in any given system depends a lot on the access patterns, and especially temporal locality within those access patterns, but the effect is real in a lot of different kinds of systems. > It's common wisdom that systems with caches can fail badly when the caches are cold. When every request misses the cache, the system is overloaded, and never recovers. What I observed was the mirror image. The bottom line is that both locality and memoization are huge contributor to the performance of systems, both positive and negative. When folks (including me) point out the risks of caches, we're not implying that caches are always bad. Instead, it's pointing out a risk that sometimes they are too good, leading to a system that can't function when the normal level of locality and memoization are not available.

bombcar 4y ago
Reminds me of: There are only two hard things in Computer Science: cache invalidation, and naming things, and off-by-one errors. What people don't realize is caches are much harder than just invalidation. I'm a fan of continually testing (and running) things without cache at all just to verify what they do, caching can often cover a multitude of sins that you really don't need to be doing.
- hinkley 4y ago
  Caches are global shared state. Correction: lossy global shared state. 'Naming things' when they are in a global namespace is really hard, to the point where I'm starting to thing that cache invalidation and naming things are not two problems but the same problem in two manifestations.
  - kwhitefoot 4y ago
    > Caches are global shared state Not necessarily. I designed an object oriented simulation system which had a lot of calculated properties where the calculation was a substantial amount of work but the result would be queried many times before the input the function changed. Caching the results inside the object provided a substantial speed up (orders of magnitude) while keeping the cache completely local and hidden from the client code and keeping the program very modular. Keeping the cache inside the objects allowed us to keep the parts of the program neatly separated and minimized the amount of knowledge that client code, and more importantly client coders, needed to have about the objects they were using.
    - hinkley 4y ago
      What happens when the system of record changes the answer halfway through the transaction? By caching answers to calculations you've moved the source of truth from the function to the cache. But the cache is also acting as a proxy for the system of record, which is a conflict of interests. That's substantially part of the problem with cache invalidation. ETA: There's also a common category error here that I see with people who grossly misunderstand DP as 'caching'. First that they think that caching and memoization are the same thing, which they emphatically are not, and second that DP is about memoization, which means they listened for the first ten minutes and then fell asleep. Tabulation is much more powerful than memoization, so equating DP with memoization is impoverishing it and yourself. But importantly here, the distinction between memoization and caching is that memoization is scoped while caching is global. With memoization a single call tree gets the same answers every time, which means the mental process of Local Reasoning is maintained. If you know the call graph for this operation you know everything that interacts with it. You know if 'eviction' is even a thing. You also know that your unit tests are testing the code as it will behave under load, not some fictional happy path. tl;dr: If your calculation is important it should show up in your data flow, not arrive out of band from a magic oracle.
    - bmm6o 4y ago
      If we're splitting hairs, your situation sounds more like memoization, where you have saved the output of an expensive but deterministic calculation. With the correct assumptions, this can never result in incorrect behavior. Worst case is excessive memory consumption. Whereas a stale cache is something that needs to be taken into account.
hinkley 4y ago
Caching is a weapon of last resort. In most cases it is the last major performance improvement you will see from your code, even if other options were available, and any information architecture problems you have are set in stone or will get worse. Because of the locality aspect, people will assume that it's 'free' to look up a value multiple times instead of passing these data dependencies between the relevant methods. This turns your cache into global shared state, and once that happens you can't turn the cache off again. There are other problems with this arrangement as well. The easiest to understand (and yet I've failed on at least one project) is that if the working set for a problem ever becomes proportional to the size of the cache (>1 for single task systems, > 1/n for systems with n concurrent tasks), then you can end up evicting data in the middle of a transaction. The obvious consequence is that it causes performance to jump off a cliff. Particularly bad behavior with LRUs but switching to a different statistical model simply reduces the height of the cliff. There is still a cliff. The less obvious consequence is now you have concurrency bugs, because the code assumes that decisions made about the data will go the same way on each call, but due to eviction, two halves of the transaction may make conflicting decisions with undefined behavior. But speaking as the guy who fixes the perf issues other people gave up on: Once you introduce caching you poison the performance well. Flame charts lie when cache is used, and after people rely on the cache it is lying in the other direction when the cache is off, because you're calling that path 5 times now and it's swamping other bottlenecks. This is what I really mean when I say it's a weapon of last resort. Because once you use it, it attempts to take any other options off the table. Caching will be most of the last order of magnitude in scalability that your system ever sees. Every 'win' from there on will take more time and energy than most people are willing to invest.
- brightball 4y ago
  I like applying the Circuit Breaker approach to caching. Rather than applying a cache everywhere, setup a cache wrapper that only triggers if the accessed resource is slower than a certain threshold. The goal is for the cache to go unused most of the time, but during times of unexpected system stress the caches will kick in, provide relief to the system and reduce impact to users.
  - 4y ago
gav 4y ago
> Instead, it's pointing out a risk that sometimes they are too good, leading to a system that can't function when the normal level of locality and memoization are not available. And at that point cache management starts to be a huge problem. Clearing caches becomes a death spiral because your system can't actually support your normal load. For example I worked with a large retailer, who had a giant monolithic enterprise Java ecommerce system. It was so slow that product detail pages took upwards of 30 seconds to render. There was a cache in front of that system (Ehcache), then a page-level cache (Varnish) in front of that, then finally Akamai took 98% of the load. Rollouts were terrifying, you cleared the cache and the site might come back up. Changing Akamai configuration was also similarly risky. It's critical that systems don't become cache dependent for load, they should be a performance boost, not a required component.

by mjb 4y ago

bombcar 4y ago

Reminds me of: There are only two hard things in Computer Science: cache invalidation, and naming things, and off-by-one errors. What people don't realize is caches are much harder than just invalidation. I'm a fan of continually testing (and running) things without cache at all just to verify what they do, caching can often cover a multitude of sins that you really don't need to be doing.

hinkley 4y ago
Caches are global shared state. Correction: lossy global shared state. 'Naming things' when they are in a global namespace is really hard, to the point where I'm starting to thing that cache invalidation and naming things are not two problems but the same problem in two manifestations.
- kwhitefoot 4y ago
  > Caches are global shared state Not necessarily. I designed an object oriented simulation system which had a lot of calculated properties where the calculation was a substantial amount of work but the result would be queried many times before the input the function changed. Caching the results inside the object provided a substantial speed up (orders of magnitude) while keeping the cache completely local and hidden from the client code and keeping the program very modular. Keeping the cache inside the objects allowed us to keep the parts of the program neatly separated and minimized the amount of knowledge that client code, and more importantly client coders, needed to have about the objects they were using.
  - hinkley 4y ago
    What happens when the system of record changes the answer halfway through the transaction? By caching answers to calculations you've moved the source of truth from the function to the cache. But the cache is also acting as a proxy for the system of record, which is a conflict of interests. That's substantially part of the problem with cache invalidation. ETA: There's also a common category error here that I see with people who grossly misunderstand DP as 'caching'. First that they think that caching and memoization are the same thing, which they emphatically are not, and second that DP is about memoization, which means they listened for the first ten minutes and then fell asleep. Tabulation is much more powerful than memoization, so equating DP with memoization is impoverishing it and yourself. But importantly here, the distinction between memoization and caching is that memoization is scoped while caching is global. With memoization a single call tree gets the same answers every time, which means the mental process of Local Reasoning is maintained. If you know the call graph for this operation you know everything that interacts with it. You know if 'eviction' is even a thing. You also know that your unit tests are testing the code as it will behave under load, not some fictional happy path. tl;dr: If your calculation is important it should show up in your data flow, not arrive out of band from a magic oracle.
  - bmm6o 4y ago
    If we're splitting hairs, your situation sounds more like memoization, where you have saved the output of an expensive but deterministic calculation. With the correct assumptions, this can never result in incorrect behavior. Worst case is excessive memory consumption. Whereas a stale cache is something that needs to be taken into account.

hinkley 4y ago

Caching is a weapon of last resort. In most cases it is the last major performance improvement you will see from your code, even if other options were available, and any information architecture problems you have are set in stone or will get worse. Because of the locality aspect, people will assume that it's 'free' to look up a value multiple times instead of passing these data dependencies between the relevant methods. This turns your cache into global shared state, and once that happens you can't turn the cache off again. There are other problems with this arrangement as well. The easiest to understand (and yet I've failed on at least one project) is that if the working set for a problem ever becomes proportional to the size of the cache (>1 for single task systems, > 1/n for systems with n concurrent tasks), then you can end up evicting data in the middle of a transaction. The obvious consequence is that it causes performance to jump off a cliff. Particularly bad behavior with LRUs but switching to a different statistical model simply reduces the height of the cliff. There is still a cliff. The less obvious consequence is now you have concurrency bugs, because the code assumes that decisions made about the data will go the same way on each call, but due to eviction, two halves of the transaction may make conflicting decisions with undefined behavior. But speaking as the guy who fixes the perf issues other people gave up on: Once you introduce caching you poison the performance well. Flame charts lie when cache is used, and after people rely on the cache it is lying in the other direction when the cache is off, because you're calling that path 5 times now and it's swamping other bottlenecks. This is what I really mean when I say it's a weapon of last resort. Because once you use it, it attempts to take any other options off the table. Caching will be most of the last order of magnitude in scalability that your system ever sees. Every 'win' from there on will take more time and energy than most people are willing to invest.

brightball 4y ago
I like applying the Circuit Breaker approach to caching. Rather than applying a cache everywhere, setup a cache wrapper that only triggers if the accessed resource is slower than a certain threshold. The goal is for the cache to go unused most of the time, but during times of unexpected system stress the caches will kick in, provide relief to the system and reduce impact to users.
- 4y ago

gav 4y ago

> Instead, it's pointing out a risk that sometimes they are too good, leading to a system that can't function when the normal level of locality and memoization are not available. And at that point cache management starts to be a huge problem. Clearing caches becomes a death spiral because your system can't actually support your normal load. For example I worked with a large retailer, who had a giant monolithic enterprise Java ecommerce system. It was so slow that product detail pages took upwards of 30 seconds to render. There was a cache in front of that system (Ehcache), then a page-level cache (Varnish) in front of that, then finally Akamai took 98% of the load. Rollouts were terrifying, you cleared the cache and the site might come back up. Changing Akamai configuration was also similarly risky. It's critical that systems don't become cache dependent for load, they should be a performance boost, not a required component.