Thundering Herds and Promises
instagram-engineering.com
Thundering Herds and Promises
1–10 of 41 posts
Re: Thundering Herds and Promises
#2This 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.
Re: Thundering Herds and Promises
#3This 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.
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.)
Re: Thundering Herds and Promises
#4This 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.
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.
Re: Thundering Herds and Promises
#5This 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.
> however the article doesn't discuss the implementation of the Promise.
Its not a "thundering herd" problem either. The Thundering herd is classically a scheduling problem.
You have 100-threads waiting on a resource (classically: a Mutex). The Mutex unlocks, which causes all 100-threads to wakeup. You KNOW that only one thread will win the Mutex, so 99 of the threads wasted CPU-time as they wokeup. When the next thread is done, 98 threads will wakeup (again, all wasting CPU time because only one can win).
Solving the thundering herd requires your scheduler to know all the resources that could be blocking a thread. The scheduler then only wakes ONE thread up at a time in these cases.
-----------
I'm not entirely sure what the problem should be named in the blog, but it definitely isn't a "thundering herd". I will admit that its a similar looking problem though.
Re: Thundering Herds and Promises
#6This 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.
With Redis it's just a matter of locking the request with an expiring key and the promise effect can be done with Pub/Sub.
Re: Thundering Herds and Promises
#7This 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.
> however the article doesn't discuss the implementation of the Promise. Its not a "thundering herd" problem either. The Thundering herd is classically a scheduling problem. You have 100-threads waiting on a resource (classically: a Mutex). The Mutex unlocks, which causes all 100-threads to wakeup. You KNOW that only one thread will win the Mutex, so 99 of the threads wasted CPU-time as they wokeup. When the next thr…
I agree with you, the article could have omitted the mention of the thundering herd and would still not feel any more incomplete.
I think it becomes a thundering herd problem when every request that's a potential cache miss tries to obtain a lock on the Promise for that request. Likely what the author was trying to get at which was lost due to overly generalising the problem.
Re: Thundering Herds and Promises
#8This 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.
Groupcache is one implementation in Go. However, it uses its own in-memory cache on your app servers instead of an external cache service.
https://github.com/golang/groupcache
Re: Thundering Herds and Promises
#9This 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.
My reading is that the cache is just another JavaScript service - a proxy that says "on: URL, if (in cache) return val, else fetch, add val to cache, return val."
Changing the cache to store promises is indeed an easy way to deduplicate most requests that occur roughly at the same time.
The logic now is: "on URL: if (in cache) return promise.resolve(), else add promise to cache, fetch, return promise.resolve()"
Re: Thundering Herds and Promises
#10This 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-...
* nginx: http://nginx.org/en/docs/http/ngx_http_proxy_module.html#pro...
* fastly: https://docs.fastly.com/guides/performance-tuning/request-co...
* cloudfront: https://docs.aws.amazon.com/AmazonCloudFront/latest/Develope...