Defeat your 99th percentile with speculative task

https://bjankie1.github.io/blog/

by jrpelkonen • 8 years ago

94 30 8 years ago

bjankie1.github.io

tshanmu• 8 years ago

isn't it just masking the root cause of whatever thats causing the delay in the first place?

KirinDave6• 8 years ago

Why does the consumer of a remote resource care about an emphemeral root cause? It's a massive scope creep for your API, which has SLAs to keep.

For all you know you're in the middle of a horizontal scaling event and hit an overloaded box, and there is no problem.

madamelic• 8 years ago

I agree.

There is no point in having your service try to speculate what happened when that isn't its job.

As long as your service doesn't need to ensure things happen only once or you build in that recovery mechanism (identifying unique events and throwing them out if your system has already seen them), being able to toss work to another instance is great in my mind.

colonelxc• 8 years ago

"The percentile values we observed had quite unusual distribution" It is pretty normal to have a long tail in the last few percentile/tenths. Fortunately, most latency monitoring tools do account for this now. Another gotcha is that 99.9 isn't the end of your tail either. Sometimes looking at the "100th percentile" request isn't useful/such an outlier, but you should know it exists.

(regarding "Speculative task") Also called "Hedged Request" here in an article called "The Tail at Scale"[1]

[1] http://www-inst.eecs.berkeley.edu/~cs252/sp17/papers/TheTail...

zzzcpan2• 8 years ago

Note that overhead that matters for Google doesn't matter as much for most other companies. Don't overcomplicate things just because Google does it like this.

pspeter3• 8 years ago

This seems like a useful practice. Do you log how often this happens and which task is the winner? It seems like without that, you may not notice actual issues.

KirinDave6• 8 years ago

Since the tasks are identical, the only real value such a metric would have is in considering memory allocation for green threads and other issues around memory pressure and resource pooling.

Usually, it doesn't matter why the consumer finds it slow; it could be anything from an unusual I/O issue (AWS is notorious for brief but painful networking issues) to a VM peer suddenly becoming ill behaved before being throttled.

dswalter• 8 years ago

Is your list of things AWS is notorious for available on your blog somewhere? That's valuable information.

esrauch• 8 years ago

If you find that something shifts and you are almost always starting the second task but the first task is still winning then you are in a state where the solution became extra load for no benefit.

KirinDave6• 8 years ago

I've seen this approach appear without a name very often in highly concurrent Haskell, Erlang and Elixir code. Often a "safe" race combinator appears in good libraries that handles graceful termination. So much so that you can often find local libraries that look like this Haskell code:

    speculatively :: Int -> IO a -> IO (Either a a)
    speculatively ms action = race action (threadDelay ms >> action)

spullara2• 8 years ago

I have found in many distributed systems the latency of top level requests follows a log-normal distribution, which sounds like what you are describing. But tuning when you launch backup requests you can trade off overhead for reduced tail latencies. After experimenting with it at Twitter I then found a Jeff Dean paper from Google describing it as well. Haven't been able to find that paper again though. Here is his presentation where he discusses backup requests:

https://static.googleusercontent.com/media/research.google.c...

hnaccy• 8 years ago

Non-intuitive: remove capacity under load to improve latency (?!)

Does he elaborate on this?

kolpa2• 8 years ago

It could mean

* one of your servers is unhealthy, remove it from the pool.

* reject some requests to make the rest faster.

spullara2• 8 years ago

The most common case I can think of is when you have local caches and randomly distribute traffic amongst your servers. The hit rate on the cache improves as you reduce the number of machines. If the cache expires before the same machine is hit again, you get no benefit from the cache at all. Even in the case where you are hitting the cache you are doing more original requests as you add more servers.

swsieber• 8 years ago

Removing capacity probably doesn't include removing capacity at all levels of the stack - perhaps it only means reducing the number of frontends, not db servers. That'd reduce load on the db server, allowing it to serve faster.

philsnow• 8 years ago

If your backend is Redis, how is starting more speculative hits to Redis going to help, since it's single threaded?

I mean if this is indeed helping it seems that it's not Redis that's the long pole, but maybe the request routing mesh or something.

xjia• 8 years ago

Variations are probably caused by TCP IMO

limeyx• 8 years ago

Wonder if for certain requests that are guaranteed to return smallish data sizes, having Redis support UDP would make sense and remove the TCP issues ...

maho• 8 years ago

But wouldn't this solution mean that once there is a small glitch in the system, say due to higher load than normal, there are 2x the requests and the system goes down completely?

I don't mean to be negative of the solution, I am just curious.

theparanoid• 8 years ago

You're correct, they should be more paranoid.

cortesoft• 8 years ago

Yes, I am always suspicious of techniques that add additional load under failure states. Good way to cascade your failure.

kolpa2• 8 years ago

That's why you need load shedding, regardless of whether you do speculative tasks.

zzzcpan2• 8 years ago

You are still bounded by just 2x the amount of requests, so no, this cannot take down the system, only slow it down a bit at worst. But not really, since you always need to have enough capacity for more than 2x load.

However, in my experience latencies are not static and depend on how far away the request is sent, the type of the resource requested, the size of the resource, current network load in that direction and other factors. Which gets tricky and complicated. At some point you need to store latest latency history for each request per each size group per each resource type per each node and dynamically calculate 90th percentile latency. But then things like size may not be predictable, so you may need to cap response sizes to a sufficiently small value. And so on.

If your responses are small, it's easier to just always send two requests in parallel to different servers and choose the fastest one.

karmakaze• 8 years ago

A week ago I might have thought this would be good for our microservices, as they were already using short timeouts with a retry but abandoning the original request. This is better. However it has limitations and isn't the solution. It suffers from request amplification if the called service also depends on other services and applies the same retry policy. It it still request latency bound. The main takeaway I've learned for bounding microservices is that the inflow of dependent data should be asynchronous and request latency dependent only on the service's data.

Defeat your 99th percentile with speculative task

Related Stories