Thundering Herds and Promises • Hacker News Board

Re: Thundering Herds and Promises

#11

Post by mentat » Wed, Apr 17, 2019, 4:32 PM UTC

dragontamer wrote: post #5

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.

> 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…

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

Re: Thundering Herds and Promises

#12

Post by technoweenie » Wed, Apr 17, 2019, 4:35 PM UTC

dragontamer wrote: post #5

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.

> 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…

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.

Re: Thundering Herds and Promises

#13

Post by camelspade » Wed, Apr 17, 2019, 4:50 PM UTC

sciurus wrote: post #10

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-... * 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/AmazonClou…

Also in Apache Traffic Server through the collapsed forwarding plugin: https://docs.trafficserver.apache.org/en/latest/admin-guide/...

Re: Thundering Herds and Promises

#14

Post by layoutIfNeeded » Wed, Apr 17, 2019, 4:53 PM UTC

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.

Re: Thundering Herds and Promises

#15

Post by spankalee » Wed, Apr 17, 2019, 4:54 PM UTC

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/analyz...

Re: Thundering Herds and Promises

#16

Post by dragontamer » Wed, Apr 17, 2019, 5:09 PM UTC

mentat wrote: post #11

dragontamer wrote: post #5

Earlier quoted context omitted.

> 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…

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

When everyone tries again, there's more people waiting, so everyone times-out AGAIN, which causes everything to shutdown, add two more servers to scale up, and start over. Etc. etc. Its a cascading problem that gets worse and worse each loop. You solve the Thundering Herd not by adding more resources (that actually makes the problem worse!!), but by cutting off the feedback loop somehow.

The problem discussed in the blog post has no feedback loop. Its simply a problem that happens once on startup.

Re: Thundering Herds and Promises

#17

Post by thamer » Wed, Apr 17, 2019, 5:14 PM UTC

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

[2] in the sense of "in the time it takes for the first accessor to complete the backend read"

Re: Thundering Herds and Promises

#18

Post by nitrogen » Wed, Apr 17, 2019, 5:57 PM UTC

technoweenie wrote: post #12

dragontamer wrote: post #5

Earlier quoted context omitted.

> 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…

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.

Re: Thundering Herds and Promises

#19

Post by nitrogen » Wed, Apr 17, 2019, 6:05 PM UTC

thamer wrote: post #17

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 reque…

> 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

For anyone using Rails, Rails internal cache does this on expiration, but might not on initial load.

Re: Thundering Herds and Promises

#20

Post by z3t4 » Wed, Apr 17, 2019, 6:36 PM UTC

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.