Thundering herd problem: Preventing the stampede

Thundering herd problem: Preventing the stampede(distributed-computing-musings.com)

49 points by pbardea 237 days ago | 20 comments

larkost 237 days ago |

Some years back, at a previous employer I had a related thundering herd problem: I was running an automated testing lab, and if a new job came in after a period of idleness, then we would have 100+ computers all downloading 3 (or more) multi gigabyte files at the same time (software-under-test, symbols files, and compiled tests).

To make matters worse, due to the budget for this lab, we had just three servers that the testing computers could download from. In the worst case the horrible snarl-up would cause computers to wait for as much as two hours before they got the materials needed to run the tests.

My solution was to use peer-to-peer BitTorrent (no Trackers involved), with HTTP seeding. So the BitTorrent files had no trackers listed, but the three servers listed as HTTP seeds, and the clients were all started with local peer discovery. So the first couple of computers to get the job would pull most/all of the file contents from our servers, and then the rest of the computers would wind up getting the file chunks mostly from their peers.

I did need to do some work so that the clients would first try a URL on the servers that would check for the .torrent file, and if it did not exist, build it (sending the clients a 503 code, causing them to wait a minute or two before retrying).

There are lots of things I would do differently if I rebuilt the system (write my own peer-to-peer code), but the result meant that we rarely had systems waiting more than a few minutes to get full files. It took the thundering heard and made it its own solution.

raffraffraff 237 days ago | |

Cool. That's reminds of an approach I took back in 2011 when implementing a Linux build / update system in a (small) bank. 8000 machines across hundreds of branches, no servers in the branches, no internet access, limited bandwidth. The goal was to wake one machine (WOL) which detects an update (via LDAP attribute) and then rsyncs repo update + torrent file. Once complete, that machine would load the torrent, verify the synced files, update it's version in LDAP and wake all of its peers. Each peer host would also query LDAP, detect the need to update, but also notice a peer with the latest version, so skip repo rsync and grab the torrent file and load it. So a branch with hundreds of hosts would torrent the repo update pretty quickly to each other. Pretty cool tbh, you could PXE boot and rebuild a bunch of hosts remotely, and once built, any one of them could act as an installation point. I even used this to do a distribution change, switching from SLES to Ubuntu.

achalshah 237 days ago | |

Uber built Kraken to solve the same problem with distributing images: https://github.com/uber/kraken

blakepelton 237 days ago |

Some recent academic work suggests implementing caches directly in network switches. Tofino switches are programmable enough that academics can implement this today.

OrbitCache is one example, described in this paper: https://www.usenix.org/system/files/nsdi25-kim.pdf

It should solve the thundering herd problem, because the switch would "know" what outstanding cache misses it has pending, and the switch would park subsequent requests for the same key in switch memory until the reply comes back from the backend server. This has an advantage compared to a multi-threaded CPU-based cache, because it avoids performance overheads associated with multiple threads having to synchronize with each other to realize they are about to start a stampede.

A summary of OrbitCache will be published to my blog tomorrow. Here is a "draft link": https://danglingpointers.substack.com/p/4967f39c-7d6b-4486-a...

vlovich123 236 days ago | |

> This has an advantage compared to a multi-threaded CPU-based cache, because it avoids performance overheads associated with multiple threads having to synchronize with each other to realize they are about to start a stampede.

The switch presumably also has multiple cores which still need to do this work, no? Or is the claim that moving this synchronization to the router behind a network hop saves CPU cycles on the app server?

blakepelton 236 days ago | | |

The relevant part of the switch hardware described by the OrbitCache paper doesn't have typical processor cores. Instead it is an "RMT" pipeline.

I wrote a brief description of RMT here: https://danglingpointers.substack.com/p/scaling-ip-lookup-to...

fidotron 237 days ago | |

That's not completely unheard of. Cavium used to sell chips intended to go in switches and routers which had a sort of programmable hash function that could be applied to incoming packets, and then use the result of that hash to route the packets.

These days you'd have to assume someone somewhere has a neural net based router.

alfons_foobar 237 days ago | |

This sounds intriguing and terrible at the same time :D

fidotron 237 days ago |

This reads like LLM noise, with headings missing articles.

It also doesn't mentionn the most obvious solution to this problem: adding a random factor to retry timing during backoff, since a major cause of it is everyone coming back at the precise instant a service becomes available again, only to knock it offline.

glhaynes 237 days ago | |

I don't associate missing articles with LLMs and I've known people, always for whom English was a second language, who dropped them often.

raffraffraff 237 days ago | | |

If anything I'd say that "excellent formatting" with fancy headings and formatting is the hallmark of llm

vlovich123 236 days ago | |

That works when you control the client but not when you have a case like this fetching state from a DB. For that you do in fact need some kind of locking mechanism, although it’s better if it’s implemented within the cache as a pass through cache that parks the concurrent requests except one if an outbound is needed rather than hitting the database directly. That’s how Cloudflare’s CDN works to minimize requests into the origin.

sriram_malhar 237 days ago |

This particular example of thundering herd isn't convincing. First, the database has a cache too, and the first query would end up benefiting the other queries for the same key. The only extra overhead is of the network, which is something a distributed lock would also have.

I would think that in the rare instance of multiple concurrent requests for the same key where none of the caches have it cached, it might just be worth it to take the slightly increased hit (if any) of going to the db instead of complicated it further and slowing down everyone else with the same mechanism.

to11mtm 237 days ago | |

> The only extra overhead is of the network, which is something a distributed lock would also have.

Well, There's also the 'overhead' of connection pooling. I put it that way because I've definitely run into the case of a 'hot' key (i.e. imagine hundreds of users that all need to download the same set of data because they are in the same group). Next thing you know your connection pool is getting saturated with these requests.

To your point however, I've also had cases where frankly querying the database is always fast enough (i.e. simple lookup on a table small enough that the DB engine practically always has it in memory anyway) so a cache would just be wasted dev time.

jayd16 237 days ago | |

Yeah, honestly a read replica is usually a lot less bug prone than a custom rolled cache if you just need traffic off main instance.

Ciantic 237 days ago |

I've stumbled on this twice now, usually you can use just CDN caching, but I once solved it with redis locks, and once with simply filling the cache periodically in the background.

If you can, it's easier to have every client fetch from cache, and then a cron job e.g., every second, refresh the cache.

In CDN feature to prevent this is "Collapse Forwarding"

ecoffey 237 days ago |

Interesting! Reading the headline before the article, my brain immediately thought of "jitter".

I wonder if you could extend the `In-process synchronization` example so that when `CompleteableFuture.supplyAsync()` thunk first does a random sleep (where the sleep time is bounded by an informed value based on the expensive query execution time), then it checks the cache again, and only if the cache is still empty does it proceed with the rest of the example code.

That way you (stochastically) get some of the benefits of distributed locking w/o actually having to do distributed locking.

Of course that only works if you are ok adding in a bit of extra latency (which should be ok; you're already on the non-hot path), and that there still may be more than 1 query issued to fill the cache.

chmod775 237 days ago |

This is just how you should implement any (clientside) cache in a concurrent situation. It's the obvious and correct way. I expect you'll find this pattern implemented with promises in thousands of javascript/typescript codebases.

This query will probably find loads already: https://github.com/search?q=language%3Atypescript+%22new+Map...

jedberg 237 days ago |

Exponential backoff is the usual solution to thundering herd problems. The solution of in-app coordination could certainly help, by making sure each app only requests the data once instead of each thread, but at the end of the day, you still need exponential backoff.

ciupicri 237 days ago |

    if (Boolean.TRUE.equals(lockAcquired))

WTF?!