6 ms·

Thundering Herds and Promises

133 points by YoavShapira 7y ago

jelder 7y ago
It's been a while since I used Rails, but think the fragment cache does this "out of the box."
_bxg1 7y ago
"instead of caching the actual value, we cached a Promise that will eventually provide the value" I did this exact thing recently in a client-side HTTP caching system for frequently-duplicated API requests from within a single page. Cool to see it pop up elsewhere.
ris 7y ago
Came up with something along these lines at my last place - not actually the hardest thing to do as long as you've got a robust & convenient locking system available to you. In my case I abused the common db instance that all the clients were connected to anyway to synchronize the callers on postgres advisory locks. Sure, this isn't the infinitely scalable, Netflix-scale solution that everyone is convinced they need for everything, but it will probably work absolutely fine for >90% of development scenarios. https://gist.github.com/risicle/f4807bd706c9862f69aa https://gist.github.com/risicle/f4807bd706c9862f69aa
m0meni 7y ago
Interesting. I also ran into this on a much smaller scale 3 years ago and made https://github.com/AriaFallah/weak-memoize https://github.com/AriaFallah/weak-memoize
sbov 7y ago
Back when I worked on a similar problem 10 years ago, we solved it by having a quickly expiring memcached key for hitting the database. So if the value wasn't cached, and if that key wasn't there, it would attempt to add that key. If it was added, it would hit the database and cache the result. Otherwise, if that key was there or it didn't successfully add it, it would wait for a short period of time, then re-try the whole process again. There's other similar problems elsewhere too though. A cold MySQL start is a bitch when you have and rely upon huge amounts of memory for MySQL to service your requests - this is especially noticeable if you have so much traffic you need to cache some results. Back then it would take us about an hour before a freshly spun up MySQL instance could keep up with our regular traffic, even accounting for stuff being cached.
nicwolff 7y ago
Instead – and more usefully given how slow some of our backend APIs are – we cache each value twice, under e.g. `key` with a short TTL and `key_backup` with a long TTL. The first process to miss on `key` renames `key_backup` to `key` (which is atomic and fast on Redis) and goes to the backend for a new value to cache twice and return, while the rest of the herd reads the renamed backup. Yes, this doubles the total cache size, or equivalently halves the number of keys we have room for. That's a price we're OK with paying to avoid blocking reads while a value is recalculated.
- horsawlarway 7y ago
  How does this solve your cold start? What happens if I have a new request come in for which I have no key OR key_backup?
Johnny555 7y ago
I'm not a developer, but to be honest, thought that's how all non-trivial caching implementations worked -- instead of going directly to the back end or having each one trigger a read from the back end for a cache-miss, all of the threads that want that resource just waited on it to appear in the cache.
niklabh 7y ago
i have implemented this in node.js https://npmjs.com/package/memoise https://npmjs.com/package/memoise
aaron_m04 7y ago
This looks like it would be a very useful design, however the article doesn't discuss the implementation of the Promise. This is not something memcached or redis support out of the box, as far as I know. It would seem to imply a cache manager service that has its own in-memory table of Promises.
- jerf 7y ago
  "This is not something memcached or redis support out of the box, as far as I know. It would seem to imply a cache manager service that has its own in-memory table of Promises." Note that it isn't even meaningful to suggest that memcache or Redis should support this, because they aren't responsible for filling cache values for misses. Only something actually generating the value upon the miss can implement this "promise". And in the general case, you can't serialize promises either, so you can't be "putting a promise into memcached", because memcached only stores bytes. You'd have to wrap a lot of machinery around it, and even then, I personally would say it's the machinery doing it, not memcached. (I think Redis does have some features that could be pressed into service here for notification, but Redis still wouldn't be doing the actual filling in of the value, since it can't.)
- wccrawford 7y ago
  Yeah, some details on implementation would have been welcome. I'm not sure how often "thundering herd" is actually a problem for your cache, but I could definitely see this being a useful feature to add to a caching system. Even just a way to tell Redis that something will exist there soon and to delay response until it arrives would be nice. (In essence, a Promise.)
- luhn 7y ago
  dogpile.cache [1] implements this pattern (or at least a very similar pattern) for both memcache and redis using locks. If the cache value doesn't exist, attempt to acquire the lock and generate the value. If the lock can't be acquired, wait until it frees then check for the value again. [1] https://dogpilecache.sqlalchemy.org/en/latest/ https://dogpilecache.sqlalchemy.org/en/latest/
- dragontamer 7y ago
sciurus 7y ago
This is how many HTTP caches and CDNs work. The terminology used to describe it is often request collapsing or request coalescing. Some examples: * varnish: https://info.varnish-software.com/blog/hit-for-pass-varnish-cache https://info.varnish-software.com/blog/hit-for-pass-varnish-... * nginx: http://nginx.org/en/docs/http/ngx_http_proxy_module.html#proxy_cache_lock http://nginx.org/en/docs/http/ngx_http_proxy_module.html#pro... * fastly: https://docs.fastly.com/guides/performance-tuning/request-collapsing https://docs.fastly.com/guides/performance-tuning/request-co... * cloudfront: https://docs.aws.amazon.com/AmazonCloudFront/latest/DeveloperGuide/RequestAndResponseBehaviorCustomOrigin.html#request-custom-traffic-spikes https://docs.aws.amazon.com/AmazonCloudFront/latest/Develope...
- sk5t 7y ago
  Plain-old-caches and even concurrent-aware maps do this too--several are the cases where I've slapped a Guava or Caffeine cache into place for quick 'n dirty concurrency control and key coalescing, even with a short TTL.
- camelspade 7y ago
  Also in Apache Traffic Server through the collapsed forwarding plugin: https://docs.trafficserver.apache.org/en/latest/admin-guide/plugins/collapsed_forwarding.en.html https://docs.trafficserver.apache.org/en/latest/admin-guide/...
layoutIfNeeded 7y ago
We do the same thing on client side when lazy-loading assets (typically textures) from the disk, cause you don’t want to hold multiple copies of the same asset in memory.
spankalee 7y ago
This is how all async caches are supposed to work. You never want concurrent requests for the same uncached resource to all hit the backend. For TypeScripters out there, this is what my team wrote for our static analysis framework: https://github.com/Polymer/tools/blob/master/packages/analyzer/src/core/async-work-cache.ts https://github.com/Polymer/tools/blob/master/packages/analyz...
thamer 7y ago
In practice there's a bit more to it than what the article describes, especially for a distributed cache: you need to have the Promise auto-expire so that if the machine that's performing the backend read disappears the other readers don't stay stuck forever waiting for it. It's also useful to have a feature in the cache itself that blocks the caller until the Promise has been fulfilled, so as to avoid repeated requests asking if the data is finally there. As an aside, Guava loading caches[1] implement per-key locking so that multiple threads accessing a missing key simultaneously[2] would only lead to a single load with all other readers waiting for the loading thread to complete the fetch and populate the cache. [1] https://github.com/google/guava/wiki/CachesExplained https://github.com/google/guava/wiki/CachesExplained [2] in the sense of "in the time it takes for the first accessor to complete the backend read"
- davinic 7y ago
  Why block the caller? Subsequent calls will have the same promise returned and notification will happen for all once the promise is resolved.
  - deleted 7y ago
    [deleted]
  - vhost- 7y ago
    Because then your caller will need to implement something that understands what a promise is instead of just getting a data object it already has to understand. Not only this, but the caller will need to also implement a polling mechanism to keep trying. Put into code: func get_value(key): value = backend.get(key) return value Is way better than something along these lines: func get_value(key): while true: response = backend.get(key) if response.type == "promise": sleep duration continue return response.value If your service looks like the former, then suddenly your unit tests can use a postgres database, a sqlite database, a rest client... that all implement the same backend.get(key) interface.
- NovaX 7y ago
  Guava cache's successor, Caffeine [1], handles the asynchronous case. In your scenario, you could set a timeout on the future as the entry will be discarded if the future results in an error. [1] https://github.com/ben-manes/caffeine/wiki/Population https://github.com/ben-manes/caffeine/wiki/Population
z3t4 7y ago
In an old apartment I had a lot of stuff on the same extension plug. I had to turn on the devices one by one to prevent power loss ... There's also the same problem/solution when boarding airplanes. Even if it feels backwards, it's actually faster to let one third of the requests go through first, then to let all requests go through at once.

133 points by YoavShapira 7y ago

It's been a while since I used Rails, but think the fragment cache does this "out of the box."

"instead of caching the actual value, we cached a Promise that will eventually provide the value" I did this exact thing recently in a client-side HTTP caching system for frequently-duplicated API requests from within a single page. Cool to see it pop up elsewhere.

ris 7y ago

Came up with something along these lines at my last place - not actually the hardest thing to do as long as you've got a robust & convenient locking system available to you. In my case I abused the common db instance that all the clients were connected to anyway to synchronize the callers on postgres advisory locks. Sure, this isn't the infinitely scalable, Netflix-scale solution that everyone is convinced they need for everything, but it will probably work absolutely fine for >90% of development scenarios. https://gist.github.com/risicle/f4807bd706c9862f69aa https://gist.github.com/risicle/f4807bd706c9862f69aa

m0meni 7y ago

Interesting. I also ran into this on a much smaller scale 3 years ago and made https://github.com/AriaFallah/weak-memoize https://github.com/AriaFallah/weak-memoize

sbov 7y ago

Back when I worked on a similar problem 10 years ago, we solved it by having a quickly expiring memcached key for hitting the database. So if the value wasn't cached, and if that key wasn't there, it would attempt to add that key. If it was added, it would hit the database and cache the result. Otherwise, if that key was there or it didn't successfully add it, it would wait for a short period of time, then re-try the whole process again. There's other similar problems elsewhere too though. A cold MySQL start is a bitch when you have and rely upon huge amounts of memory for MySQL to service your requests - this is especially noticeable if you have so much traffic you need to cache some results. Back then it would take us about an hour before a freshly spun up MySQL instance could keep up with our regular traffic, even accounting for stuff being cached.

nicwolff 7y ago

Instead – and more usefully given how slow some of our backend APIs are – we cache each value twice, under e.g. `key` with a short TTL and `key_backup` with a long TTL. The first process to miss on `key` renames `key_backup` to `key` (which is atomic and fast on Redis) and goes to the backend for a new value to cache twice and return, while the rest of the herd reads the renamed backup. Yes, this doubles the total cache size, or equivalently halves the number of keys we have room for. That's a price we're OK with paying to avoid blocking reads while a value is recalculated.

horsawlarway 7y ago
How does this solve your cold start? What happens if I have a new request come in for which I have no key OR key_backup?

Johnny555 7y ago

I'm not a developer, but to be honest, thought that's how all non-trivial caching implementations worked -- instead of going directly to the back end or having each one trigger a read from the back end for a cache-miss, all of the threads that want that resource just waited on it to appear in the cache.

niklabh 7y ago

i have implemented this in node.js https://npmjs.com/package/memoise https://npmjs.com/package/memoise

aaron_m04 7y ago

This looks like it would be a very useful design, however the article doesn't discuss the implementation of the Promise. This is not something memcached or redis support out of the box, as far as I know. It would seem to imply a cache manager service that has its own in-memory table of Promises.

jerf 7y ago
"This is not something memcached or redis support out of the box, as far as I know. It would seem to imply a cache manager service that has its own in-memory table of Promises." Note that it isn't even meaningful to suggest that memcache or Redis should support this, because they aren't responsible for filling cache values for misses. Only something actually generating the value upon the miss can implement this "promise". And in the general case, you can't serialize promises either, so you can't be "putting a promise into memcached", because memcached only stores bytes. You'd have to wrap a lot of machinery around it, and even then, I personally would say it's the machinery doing it, not memcached. (I think Redis does have some features that could be pressed into service here for notification, but Redis still wouldn't be doing the actual filling in of the value, since it can't.)
wccrawford 7y ago
Yeah, some details on implementation would have been welcome. I'm not sure how often "thundering herd" is actually a problem for your cache, but I could definitely see this being a useful feature to add to a caching system. Even just a way to tell Redis that something will exist there soon and to delay response until it arrives would be nice. (In essence, a Promise.)
luhn 7y ago
dogpile.cache [1] implements this pattern (or at least a very similar pattern) for both memcache and redis using locks. If the cache value doesn't exist, attempt to acquire the lock and generate the value. If the lock can't be acquired, wait until it frees then check for the value again. [1] https://dogpilecache.sqlalchemy.org/en/latest/ https://dogpilecache.sqlalchemy.org/en/latest/
dragontamer 7y ago

sciurus 7y ago

This is how many HTTP caches and CDNs work. The terminology used to describe it is often request collapsing or request coalescing. Some examples: * varnish: https://info.varnish-software.com/blog/hit-for-pass-varnish-cache https://info.varnish-software.com/blog/hit-for-pass-varnish-... * nginx: http://nginx.org/en/docs/http/ngx_http_proxy_module.html#proxy_cache_lock http://nginx.org/en/docs/http/ngx_http_proxy_module.html#pro... * fastly: https://docs.fastly.com/guides/performance-tuning/request-collapsing https://docs.fastly.com/guides/performance-tuning/request-co... * cloudfront: https://docs.aws.amazon.com/AmazonCloudFront/latest/DeveloperGuide/RequestAndResponseBehaviorCustomOrigin.html#request-custom-traffic-spikes https://docs.aws.amazon.com/AmazonCloudFront/latest/Develope...

sk5t 7y ago
Plain-old-caches and even concurrent-aware maps do this too--several are the cases where I've slapped a Guava or Caffeine cache into place for quick 'n dirty concurrency control and key coalescing, even with a short TTL.
camelspade 7y ago
Also in Apache Traffic Server through the collapsed forwarding plugin: https://docs.trafficserver.apache.org/en/latest/admin-guide/plugins/collapsed_forwarding.en.html https://docs.trafficserver.apache.org/en/latest/admin-guide/...

layoutIfNeeded 7y ago

We do the same thing on client side when lazy-loading assets (typically textures) from the disk, cause you don’t want to hold multiple copies of the same asset in memory.

spankalee 7y ago

This is how all async caches are supposed to work. You never want concurrent requests for the same uncached resource to all hit the backend. For TypeScripters out there, this is what my team wrote for our static analysis framework: https://github.com/Polymer/tools/blob/master/packages/analyzer/src/core/async-work-cache.ts https://github.com/Polymer/tools/blob/master/packages/analyz...

thamer 7y ago

In practice there's a bit more to it than what the article describes, especially for a distributed cache: you need to have the Promise auto-expire so that if the machine that's performing the backend read disappears the other readers don't stay stuck forever waiting for it. It's also useful to have a feature in the cache itself that blocks the caller until the Promise has been fulfilled, so as to avoid repeated requests asking if the data is finally there. As an aside, Guava loading caches[1] implement per-key locking so that multiple threads accessing a missing key simultaneously[2] would only lead to a single load with all other readers waiting for the loading thread to complete the fetch and populate the cache. [1] https://github.com/google/guava/wiki/CachesExplained https://github.com/google/guava/wiki/CachesExplained [2] in the sense of "in the time it takes for the first accessor to complete the backend read"

davinic 7y ago
Why block the caller? Subsequent calls will have the same promise returned and notification will happen for all once the promise is resolved.
- deleted 7y ago
  [deleted]
- vhost- 7y ago
  Because then your caller will need to implement something that understands what a promise is instead of just getting a data object it already has to understand. Not only this, but the caller will need to also implement a polling mechanism to keep trying. Put into code: func get_value(key): value = backend.get(key) return value Is way better than something along these lines: func get_value(key): while true: response = backend.get(key) if response.type == "promise": sleep duration continue return response.value If your service looks like the former, then suddenly your unit tests can use a postgres database, a sqlite database, a rest client... that all implement the same backend.get(key) interface.
NovaX 7y ago
Guava cache's successor, Caffeine [1], handles the asynchronous case. In your scenario, you could set a timeout on the future as the entry will be discarded if the future results in an error. [1] https://github.com/ben-manes/caffeine/wiki/Population https://github.com/ben-manes/caffeine/wiki/Population

z3t4 7y ago

In an old apartment I had a lot of stuff on the same extension plug. I had to turn on the devices one by one to prevent power loss ... There's also the same problem/solution when boarding airplanes. Even if it feels backwards, it's actually faster to let one third of the requests go through first, then to let all requests go through at once.