Hacker News Reader

Comment by k33P1Tr3aL | Hacker News Reader

the 'ol thundering herd problem...

Exponential backoff is your friend... too few people use it.

Don’t forget jitter!

I always add some jitter but never actually had a problem where it would have been relevant. Recently I added it to a project where others also see it (not just a hobby thingy but something at work) and I was wondering if it would look silly, like premature optimisation. I looked on Wikipedia for how established the practice is and it barely gets a sentence... with no reference.

Do you know of a documented instance where it would have helped?

If you’re talking about internet clients, I think the real world provides sufficient jitter. If you’re talking about a fleet of clients on your 10gbps network, jitter might be useful.

Have experienced it, but didn’t document.

Downstream database of our edge serverless platform went down. A tonne of requests failed all at once. Every service in the microservice request path, and the client, had their own retry policy.

Clients all retried at the same time. Retries amplified in our microservice graph (1 request at the front door ended up with like 10s of retries internally as each downstream microservice along the path retried requests). Request queues backed up and couldn’t drain fast enough. Clients all timed out at roughly the same time. All waited the same time. All retried again at the same time.

It was a pulsing thundering herd of many hundreds of thousands of requests at the front door that was amplified by internal retries.

Had to tune up load shedding to 100% after the database outage was mitigated until the backend recovered then tune it down in increments to restore service.

Added jitter to clients and turned off retries on the serverless platform.

Exactly, without jitter the thundering heard problem turns into trying to escape a small island with a small boat and big waves hitting the shore problem. You can never fully recover before you get smashed again.

It’s not hard to get started, it’s a case of adding small amounts of randomness.

If you have, say, a long poll then kick off all users due to a deploy or error (or a broadcast message) then you can have a situation where you’ve got a huge clustering of connections at 1 minute, which spreads very slowly out as real life issues give you jitter for free. You can avoid this or at least return to normal much quicker by adding some jitter.

It might happen if all your users back off at the same rate too, if the clustering causes a bunch of errors. Error -> lots reconnect 1 minute after -> fail -> lots reconnect 2, 4…

More likely to occur in cases where there’s a way you can have people all connecting at the same time - synchronisation to a real world event is one case and then connecting again at the same time after.

I've had to simulate jitter recently to reproduce a memory spike in a go app using traffic control (tc). have you observed how your app works under jittery network?

This doesn't answer your question, but I faced an issue where an application had to retry if things failed and I ended up with the "thundering herd" problem and introduced jitter without knowing it was a relatively standard practice.

I felt dirty implementing such a solution (introducing randomness for the sake of randomness is off-putting), but it worked. It wasn't until a while later that I even heard the term "jitter" in this context and realized this was a pretty decent solution for this kind of problem.

Regardless, if you're going to introduce something where adding jitter is appropriate, I'd just just add jitter. It's not premature optimization; it's an essential part of that kind of functionality.

It’s a fundamental property of Ethernet[1]. Does that count?

[1] https://en.wikipedia.org/wiki/Exponential_backoff#Example

It’s the first thing that came to mind!

Of Ethernet in the 1980s*

If you have a switch in your network, or a speed faster than 100Mbps, you aren't using this model.

However, WiFi uses it.

You have thousands of users connected to a chat via websockets to a small cheap server that can just handle the load. Server has a hiccup, all clients disconnect, server comes back, all clients reconnect at once. Server can’t handle the load.

Even if you're operating at a scale where thundering herd won't crash your service, introducing exponential backoff + jitter to your retries also helps when you're just viewing the logs. Massively reduces log spam when you make changes.

Reminds me of this blog post I read yesterday, about Buildkite introducing jitter in their CI agent to reduce synchronisation

https://buildkite.engineering/sleeping-at-scale/

Jittered exponential backoff. You don't want the whole herd to come back at the same time, you have to add timing jitter to the clients.

Possibly dumb/silly question.... Are there any sorts of reverse proxies out there that provide their own layer of jittered/exponential backoff based on patterns? (i.e. requesting IP, cookie, etc.)

I suppose the main reason I think it might be a bad idea, is that it would add complexity to the reverse proxy (i.e. now it's having to track whatever thing is being used and that complexity itself becomes a potential failure point...)

(To be clear, the clients should have their own backoff procedures, but I'm thinking about cases involving naughty clients, which are sometimes a harder problem to correct for...)

I believe envoy has it built in and istio (uses envoy) has different levers for circuit breaking and retries. I’m sure lots of them have it as an option though outside of these.

In general, helping prevent retry storms is one of the functions of a service mesh. E.g. Istio lets you configure exponential backoff with jitter, linkerd provides a retry budget and loadshedding based on backpressure.

“Adding complexity to the reverse proxy” is kind of the central feature of service meshes, but the point is you pick one that’s battle tested and solves more problems than it creates.

Exponential is also overkill (even with jitter as others have mentioned).

I seem to remember there was a "you failed 5 PIN entries in a row, please wait 500000 seconds before you retry" on Apple phones. So, you probably also want a sensible max... which makes exponential a bit pointless. Just do a basic fixed delay + (large, e.g. 0.5 x the delay) jitter and you'll be fine for most things. You can add a bit of cumulative delay if it's really costly to do retries.

Cap the number of retries before the user has to manually try again. That's fine.

Thundering herd is different. Thundering herd is when a lot of clients trigger requests at the same time. Common situations being a specific time, some other event just occurred or synchronize on other parts of your infrastructure (such as readers queuing behind a R/W lock that then get unblocked at the same time to continue to make a bunch of requests at the same time.

Request amplification via retries is a different problem that causes large amounts of traffic (but it is generally more steady than spiky)

Reply on news.ycombinator.com