4 ms·

Another common problem in caching is the "thundering herd". You have a bit of data that is expensive to compute, very frequently requested, and fine to be a li

Another common problem in caching is the "thundering herd". You have a bit of data that is expensive to compute, very frequently requested, and fine to be a little bit stale. The naive approach is to follow the normal pattern: use the cached version of it's there, and otherwise compute and stick it in the cache with a TTL. The problem arises when you have a fleet of web nodes going at full bore, and the cache expires. If the data takes 10 seconds to compute, then for the whole next 10 seconds, every new request will find the data missing from the cache since it has expired and not yet been replaced, and so each of those requests will take on the expensive and redundant work of repopulating that data. It can be a performance blip at best, or a total disaster at worst, causing cascading failures and downtime. One relatively easy solution here is to just have a separate worker process that runs in an interval and preemptively freshens the data in the cache. In this case you can set with no TTL, and web front ends just use whatever they find. You also need to deal gracefully with the rare case where they may find nothing, like in the case of a cold cache boot.

filleokus 6y ago
It can also quite easily be solved by using something like nginx's proxy_cache_background_update and/or proxy_cache_lock, depending on wether it's permissible to send stale responses. Then you could have the cache serve stale content until it's updated, and/or only allow one upstream connection to refresh the cache. But yeah, unless you allow stale responses or refresh the cache periodically as you suggest, you would still have requests which takes 10 second to complete, but you would at least not crush the upstream service.
plett 6y ago
This is done in the DNS world too. The unbound[1] resolver can pre-fetch a new record half way through the TTL if enough clients have requested it. That guarantees that the cache remains hot for records that clients are requesting, but lets unused records expire. 1: https://nlnetlabs.nl/projects/unbound/about/ https://nlnetlabs.nl/projects/unbound/about/
revicon 6y ago
This runs afoul of the article’s warning to “ Never require a cache hit” It's important never to require a cache hit - even as a soft requirement. Evictions can happen at inconvenient times - such as when some other part of the system is under load - and there mustn't be any negative consequences to a cache miss If the cache does empty unexpectedly and that is going to cause your infrastructure to die in a cascade, probably some kind of fallback will be needed.
- stetrain 6y ago
  If you have a result that takes 10 seconds to calculate, and you need to read it faster than that, so you make a background processes to calculate it and keep it updated somewhere, you could argue that it's no longer caching. It's an asynchronous read model or a projection and it's now just part of your application.
  - hinkley 6y ago
    I find that when I'm in a dead-end conversation with people about caching that often they can't accept that pre-calculation and caching are two different concepts, and you conflate them at our peril. For instance if I look up a value and pass it to three pure functions to ask about it, versus having the 3 functions look up the value and try to share a cache entry. This is doubly wrong because the final question may see a cache eviction and answer a different question due to changes in the data. Now I may have a situation where True:False:True was not a corner case we cover because it's logically impossible, but it's happening in the code because the last one changed from False to True due to concurrent read and write. The latter is also harder to test, because it requires mocks instead of manufactured inputs. And at this point the code is using the cache as global, mutable state, instead of semi-local state. Three strikes, you're out.
- Thaxll 6y ago
  If the computation of the data takes 10sec and your hammered with request, you should def require a cache hit and return a 500 if there is no cache and do not go the DB or somebackup mechanism.
gonzo41 6y ago
Varnish has a keep time that allows you to hold a 'dead' object for ttl+X for exactly this reason. You server it for so many seconds whilst under load while a single origin request goes and grabs the data. It's a really solid way to shed load and avoid dropping so many connections at once and then getting slammed on retry.
nerdponx 6y ago
I once had this situation at an old job, and I ended up working around it by putting a lock around the re-computation: all requests had to wait for the 5-ish seconds while the cache was being refreshed. In this case, per-request latency wasn't as important as total throughput of the system over time. And the individual requests were small, so building up a queue of unhandled requests wasn't a problem. I have no idea if this is considered a "good" solution, but it worked well enough for me at the time.
hyperpape 6y ago
It's a pool, not a cache per se, but the Hikari database connection pool subtracts up to a random amount up to a few percent from each connection's lifetime to avoid a similar problem. If you have a 30 minute lifetime, you spread the expirations (and recreations) over half a minute or so.
- jeffbee 6y ago
  Another probabilistic approach is to have an increasing probability of an artificial cache miss as the TTL approaches zero. This forces some unlucky client to refresh it for everybody, avoiding the thundering herd. We used that technique in Google's DNS cache to fix what had been a monumental herd effect every 30 seconds when the RRs for outlook-com.olc.protection.outlook.com expired.
hinkley 6y ago
As the TTL shrinks to a smaller multiple of the time needed to generate the response, this problem becomes magnified. A two second response with a 10 second TTL could see 20% of the queries all trying to refresh the same cache at once. With a single server you can use promise caching to dedupe such things, with a cluster that's more difficult to avoid. Background processes are good for spiky traffic, and with reddit and HN around some of us at least have been trained that some information on a page is purely advisory. Do I have 22 upvotes or 28? Give it a couple minutes and try again. But what that work does is make you look at what the cost is of certain information, and some people are not comfortable with that. With caching you can delude yourself that you're getting a bargain on all of this information overload, even though the worst case scenarios and statistical clumping say you're off your gourd.
toast0 6y ago
Squid had a collapsed forwarding option that can help with the thundering herd. If multiple clients request the same uncached url, it can wait for the first origin request to finish and serve the response to all clients (if cachable). Of course, that backfires if the response was uncachable; so careful configuration is required. Also works well to combine that with stale-while-revalidate. Yahoo had some squid patches with nifty ways to have a response invalidate other cached urls, but I don't think those made it to the outside world (at least I can't find them now).
thaumasiotes 6y ago
> Another common problem in caching is the "thundering herd". > you have a fleet of web nodes going at full bore, and the cache expires. If the data takes 10 seconds to compute, then for the whole next 10 seconds, every new request will find the data missing from the cache since it has expired and not yet been replaced, and so each of those requests will take on the expensive and redundant work of repopulating that data. Wait, is the problem that as soon as the cache entry expires everyone requests the new data all at once, overwhelming the backend ("thundering herd"), or is it that requests follow whatever the normal pattern is but the backend doesn't know how to queue them?

filleokus 6y ago

It can also quite easily be solved by using something like nginx's proxy_cache_background_update and/or proxy_cache_lock, depending on wether it's permissible to send stale responses. Then you could have the cache serve stale content until it's updated, and/or only allow one upstream connection to refresh the cache. But yeah, unless you allow stale responses or refresh the cache periodically as you suggest, you would still have requests which takes 10 second to complete, but you would at least not crush the upstream service.

plett 6y ago

This is done in the DNS world too. The unbound[1] resolver can pre-fetch a new record half way through the TTL if enough clients have requested it. That guarantees that the cache remains hot for records that clients are requesting, but lets unused records expire. 1: https://nlnetlabs.nl/projects/unbound/about/ https://nlnetlabs.nl/projects/unbound/about/

revicon 6y ago

This runs afoul of the article’s warning to “ Never require a cache hit” It's important never to require a cache hit - even as a soft requirement. Evictions can happen at inconvenient times - such as when some other part of the system is under load - and there mustn't be any negative consequences to a cache miss If the cache does empty unexpectedly and that is going to cause your infrastructure to die in a cascade, probably some kind of fallback will be needed.

stetrain 6y ago
If you have a result that takes 10 seconds to calculate, and you need to read it faster than that, so you make a background processes to calculate it and keep it updated somewhere, you could argue that it's no longer caching. It's an asynchronous read model or a projection and it's now just part of your application.
- hinkley 6y ago
  I find that when I'm in a dead-end conversation with people about caching that often they can't accept that pre-calculation and caching are two different concepts, and you conflate them at our peril. For instance if I look up a value and pass it to three pure functions to ask about it, versus having the 3 functions look up the value and try to share a cache entry. This is doubly wrong because the final question may see a cache eviction and answer a different question due to changes in the data. Now I may have a situation where True:False:True was not a corner case we cover because it's logically impossible, but it's happening in the code because the last one changed from False to True due to concurrent read and write. The latter is also harder to test, because it requires mocks instead of manufactured inputs. And at this point the code is using the cache as global, mutable state, instead of semi-local state. Three strikes, you're out.
Thaxll 6y ago
If the computation of the data takes 10sec and your hammered with request, you should def require a cache hit and return a 500 if there is no cache and do not go the DB or somebackup mechanism.

gonzo41 6y ago

Varnish has a keep time that allows you to hold a 'dead' object for ttl+X for exactly this reason. You server it for so many seconds whilst under load while a single origin request goes and grabs the data. It's a really solid way to shed load and avoid dropping so many connections at once and then getting slammed on retry.

nerdponx 6y ago

I once had this situation at an old job, and I ended up working around it by putting a lock around the re-computation: all requests had to wait for the 5-ish seconds while the cache was being refreshed. In this case, per-request latency wasn't as important as total throughput of the system over time. And the individual requests were small, so building up a queue of unhandled requests wasn't a problem. I have no idea if this is considered a "good" solution, but it worked well enough for me at the time.

hyperpape 6y ago

It's a pool, not a cache per se, but the Hikari database connection pool subtracts up to a random amount up to a few percent from each connection's lifetime to avoid a similar problem. If you have a 30 minute lifetime, you spread the expirations (and recreations) over half a minute or so.

jeffbee 6y ago
Another probabilistic approach is to have an increasing probability of an artificial cache miss as the TTL approaches zero. This forces some unlucky client to refresh it for everybody, avoiding the thundering herd. We used that technique in Google's DNS cache to fix what had been a monumental herd effect every 30 seconds when the RRs for outlook-com.olc.protection.outlook.com expired.

hinkley 6y ago

As the TTL shrinks to a smaller multiple of the time needed to generate the response, this problem becomes magnified. A two second response with a 10 second TTL could see 20% of the queries all trying to refresh the same cache at once. With a single server you can use promise caching to dedupe such things, with a cluster that's more difficult to avoid. Background processes are good for spiky traffic, and with reddit and HN around some of us at least have been trained that some information on a page is purely advisory. Do I have 22 upvotes or 28? Give it a couple minutes and try again. But what that work does is make you look at what the cost is of certain information, and some people are not comfortable with that. With caching you can delude yourself that you're getting a bargain on all of this information overload, even though the worst case scenarios and statistical clumping say you're off your gourd.

toast0 6y ago

Squid had a collapsed forwarding option that can help with the thundering herd. If multiple clients request the same uncached url, it can wait for the first origin request to finish and serve the response to all clients (if cachable). Of course, that backfires if the response was uncachable; so careful configuration is required. Also works well to combine that with stale-while-revalidate. Yahoo had some squid patches with nifty ways to have a response invalidate other cached urls, but I don't think those made it to the outside world (at least I can't find them now).

thaumasiotes 6y ago

> Another common problem in caching is the "thundering herd". > you have a fleet of web nodes going at full bore, and the cache expires. If the data takes 10 seconds to compute, then for the whole next 10 seconds, every new request will find the data missing from the cache since it has expired and not yet been replaced, and so each of those requests will take on the expensive and redundant work of repopulating that data. Wait, is the problem that as soon as the cache entry expires everyone requests the new data all at once, overwhelming the backend ("thundering herd"), or is it that requests follow whatever the normal pattern is but the backend doesn't know how to queue them?