Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Thundering Herds and Promises

instagram-engineering.com

Post reply on HN
Print view View original

21–30 of 41 posts

Re: Thundering Herds and Promises

#21

Post by drb91 »

nitrogen wrote: post #18
technoweenie wrote: post #12

Earlier quoted context omitted.

FWIW I've always heard it described as a thundering herd. Though, your description is spot on, according to Wikipedia [1]. The problem the article discusses is called a cache stampede or dog pile [2]. [1] https://en.wikipedia.org/wiki/Thundering_herd_problem [2] https://en.wikipedia.org/wiki/Cache_stampede I wouldn't fault anyone for getting these similar names mixed up though.

It's also possible the Wikipedia article is maintained by someone with a stronger opinion about the definition than would be reflected in the typical person using the term.

I'd hope so!

Re: Thundering Herds and Promises

#22

Post by mason55 »

fwip wrote: post #9
aaron_m04 wrote: post #2

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.

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()"

But what does it mean for a promise to be in the cache? If you're using an external cache, like redis or memcached, you can't just put a JavaScript promise in there and expect everything to work. Neither of those services understands what it means for the promise to resolve so that all the clients waiting on it can continue.

At best you could serialize the promise and then have everyone who was waiting on it poll the cache to see if the promise was resolved yet, but that is pretty inefficient.

You probably want another layer in there that handles the conversion of a JavaScript promise to something that can be awaited on from your cache, like a redis pub/sub. Then in JavaScript land your services just await on a promise as normal but under the covers your service is doing something else which is specific to the cache you're using.

Re: Thundering Herds and Promises

#24

Post by fwip »

mason55 wrote: post #22
fwip wrote: post #9

Earlier quoted context omitted.

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()"

But what does it mean for a promise to be in the cache? If you're using an external cache, like redis or memcached, you can't just put a JavaScript promise in there and expect everything to work. Neither of those services understands what it means for the promise to resolve so that all the clients waiting on it can continue. At best you could serialize the promise and then have everyone who was waiting on it poll the…

I don't think they are using an external cache.

Re: Thundering Herds and Promises

#25

Post by coding123 »

mason55 wrote: post #22
fwip wrote: post #9

Earlier quoted context omitted.

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()"

But what does it mean for a promise to be in the cache? If you're using an external cache, like redis or memcached, you can't just put a JavaScript promise in there and expect everything to work. Neither of those services understands what it means for the promise to resolve so that all the clients waiting on it can continue. At best you could serialize the promise and then have everyone who was waiting on it poll the…

even if you have 1000 servers that all have a local promise you may still be helping the backend service by reducing 10000000 requests to 1000.

Re: Thundering Herds and Promises

#26

Post by _bxg1 »

"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.

Re: Thundering Herds and Promises

#27

Post by jerf »

aaron_m04 wrote: post #2

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.

"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.)

Re: Thundering Herds and Promises

#28

Post by ris »

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

Re: Thundering Herds and Promises

#29

Post by mentat »

dragontamer wrote: post #16
mentat wrote: post #11

Earlier quoted context omitted.

Thundering herd has referred to demand spikes in services architectures for at least 8 years[0], probably much longer. 0. https://qconsf.com/sf2011/dl/qcon-sanfran-2011/slides/Siddha...

Hmm, the Netflix presentation there seems to make sense superficially though. The key attribute of the "Thundering Herd" problem is the LOOP. The Thundering Herd causes another Thundering Herd... which later causes another Thundering Herd. In the Netflix presentation, the "Thundering Herd" causes all of the requests to time out, which causes two new servers to be added ("automatic scale up"), then everyone tries agai…

Very good point, thanks for clarifying.
Post reply on HN