7 ms·

What happens to latency if service time is cut in half (2022)

130 points by luu 2y ago

alhaad 2y ago
Why is arrival rate a function of service time?
- cpitman 2y ago
  Utilization is Service Time times Arrival Rate, ie if requests arrive twice as fast utilization is doubled, and also if a service takes twice as long to process. When the theoretical service is optimized to take half a long, the assumption is that the request rate doesn't actually change. So they use the above relationship to calculate the new utilization, given half the service time and the same arrival rate.
  - amne 2y ago
    so the unit for Utilization in your example is "active request" ? I just wish the article didn't assume units are easily inferred which would imply most readers are familiar with the subject.
    - amne 2y ago
      Having read it more than once now I think utilization is a ratio, maybe? But that means the unit for S needs to be seconds/request such that: utilization(ro) = S * arrival_rate(lambda) = seconds/request * request/seconds = bare ratio. More coffee required.
      - ajb 2y ago
        Yes, that's normally how utilisation is understood - as the fraction of time used by requests, which is therefore a dimensionless quantity.
- ajb 2y ago
  I don't think he's claiming that it's causally a function of service time (although this can be the case if demand is elastic). Rather, utilisation is calculated from service time and arrival rate, and they're just stating that this equation can be rearranged to calculate arrival rate if you know the other two.
nailer 2y ago
What is service time? Edit: service time is processing time. 6:35 in https://youtu.be/03GsLxVdVzU https://youtu.be/03GsLxVdVzU
- amelius 2y ago
  And you can read more here: https://en.wikipedia.org/wiki/Queueing_theory https://en.wikipedia.org/wiki/Queueing_theory
davherrmann 2y ago
The math seems to be off in a few places: 1. When solving for the arrival rate λ, it should be λ=ρ/S instead of λ=S/ρ. 2. Calculating the arrival rate λ with the correct formula results in 9 requests/second instead of 10 request/second. 3. Calculating the new utilization ρ should be 0.05x9 instead of 0.05x10. The result of the calculated utilization ρ is correct (0.45), so is the calculated new latency. edit: new lines
- jankar 2y ago
  Even with the wrong formula for λ This one is also off: λ = S/ρ = 0.1/(1−0.9) = 10 Should be 1 not 10.
jph 2y ago
Queueing theory refresher for software developers: https://github.com/joelparkerhenderson/queueing-theory https://github.com/joelparkerhenderson/queueing-theory This can help put the article in context. The author writes "wanted to freshen up my queuing theory a bit".
fwlr 2y ago
In mathematical queueing theory, Little's law (also result, theorem, lemma, or formula[1][2]) is a theorem by John Little which states that the long-term average number L of customers in a stationary system is equal to the long-term average effective arrival rate λ multiplied by the average time W that a customer spends in the system. Expressed algebraically the law is L=λW The relationship is not influenced by the arrival process distribution, the service distribution, the service order, or practically anything else. In most queuing systems, service time is the bottleneck that creates the queue. https://en.m.wikipedia.org/wiki/Little%27s_law https://en.m.wikipedia.org/wiki/Little%27s_law An extremely useful law to remember. You’d be surprised how much bullshit it can detect!
- jethkl 2y ago
  > An extremely useful law to remember.... Would you be willing to provide an example where you applied Little's Law?
  - kqr 2y ago
    Many electronic queueing systems in hospitals etc. show you how many customers are ahead of you. If you observe the time it takes for a few people to receive service you can estimate how long you'll be stuck waiting. This is a number they rarely show you because it's often not encouraging... It's the most primitive application but immediately useful for anyone. I've used similar methods to estimate work lag: https://two-wrongs.com/estimating-work-lag.html https://two-wrongs.com/estimating-work-lag.html And to argue for concurrency limits in latency-sensitive backend serviced.
  - AceyMan 2y ago
    Every time I'm in a queue at a store I compute the arrival rate while I wait in line. (Little's Law is one of my very favorite pages in all of Wikipedia!).
  - fwlr 2y ago
    Sure! In a professional capacity - our customers were dissatisfied with the length of time and flakiness of a particular workload job[0], and I was party to the discussions on how to solve this problem. Knowing Little's Law allowed me to dissent against the prevailing opinion that we should customise our job processing queue to prioritise these jobs[1], arguing instead to provision more resources (i.e. beefier servers). The decision was still made to alter the priority. The change went into production and was found to unacceptably degrade the performance of other jobs. Thankfully, one of the engineers who I had convinced that "processing time is the only factor that matters" had spent all their time optimizing the heavy task, to the point where it was no longer a heavy task, thus saving the day. 0. The job was some kind of "export CSV" form, and it somehow involved both 'traversing dozens of highly normalised tables' and 'digging into json blobs stored as text'. 1. I specifically remember one of the arguments was that if you have 3 heavy tasks A B and C, best case is "in parallel" which takes max(A, B, C) time whereas worst case is "sequential" which takes (A) + (B + A) + (C + B + A) time, our current priority approximated the "sequential" scenario, and the priority change would instead approximate the "parallel" scenario. I use scare quotes because I felt it was a resource issue (the "sequential" pattern was a byproduct of the most common way a heavy task got enough resources... which was an earlier heavy task finished and freed up a lot of resources).
drewhk 2y ago
I am a bit worried of the overuse of Little's formula, especially in these catchy educational presentations. In reality queue sizes will dictate your consumer observable latency profile, which is in turn is dictated by the actual distribution of the service time - it is not a constant. If you think about it, if you have an ideal system that serves users like a clockwork, every X ms with no jitter, while your arrival is also completely regular, every Y ms (Y < X), then basically a queue length of 1 is sufficient. In reality, just like we all observe in real-life queues, service time is far from constant, and outliers result in queue buildup. This is why often cutting the tail of service-time latency results in better overall latency than simply reducing average service-time. Little's formula of course holds also in the above scenario, but it handles long-time averages and does not give you any indication what extreme behavior is lurking under the mask of these averages.
- kqr 2y ago
  > ...the actual distribution of the service time - it is not a constant. I'm concerned by the number of misunderstandings expressed in short time here. 1. Nobody claims service time is constant. 2. Little's law is one of the few parts of queueing theory that remarkably does not depend on service time distribution. 3. Many results for typical simplified M/M/c systems apply well also to any other service time distribution provided (a) arrivals are Poisson, and (b) the server uses time slicing multiprocessing. These are not very severe requirements, fortunately! Long-term average sounds restrictive but it really just means a period long enough to exhibit some statistical stability. Most systems I see sit mainly in those regimes.
  - drewhk 2y ago
    > I'm concerned by the number of misunderstandings expressed in short time here. I have a feeling you misread my comment completely, and the misunderstandings are on your part? > Nobody claims service time is constant. Neither did I. Neither did I claimed that Little's Formula requires a constant service time. > Little's law is one of the few parts of queueing theory that remarkably does not depend on service time distribution. I did not say otherwise either. My point is that it is way less useful and enlightening than these edutainment posts make it. Two systems with the exact same parameters and results by Little's Formula might behave completely differently, and in many cases, counterintuitively. > Many results for typical simplified M/M/c systems apply well also to any other service time distribution provided (a) arrivals are Poisson, and (b) the server uses time slicing multiprocessing. These are not very severe requirements, fortunately! This was not my point. Or do you claim that queue size distributions DO NOT depend on service time distribution? Because that WAS my point. Averages do not tell the story you are most interested in. The whole point of queues is that service and arrival times have distributions with deviation. I personally think queues and buffers are very-very important and I am a huge proponent of predictable user-observable latencies as they improve general system health and resiliency under load. > Long-term average sounds restrictive but it really just means a period long enough to exhibit some statistical stability. Most systems I see sit mainly in those regimes. Long-term averages do not talk about pathological transient behavior, do not help you with queue sizing - or setting ideal timeouts. Also, statistical stability is misleading, the convergence time to the given statistic might be arbitrarily slow. Also, if we talk about real-world systems (which you do), they exhibit feedback do to clients retrying, throwing off the formula and potential ergodicity.
kqr 2y ago
Another of those somewhat counter-intuitive results is the answer to the question "how much do we need to scale up to avoid response time regression when the request rate is doubled?" It is very easy to blurt out "well obviously we need twice the processing power!" but if we scale to twice the processing power, then start accepting twice the request rate – we will actually be serving each request in half the time we originally did. To many people that sounds weird; it sounds like we got something for nothing. If I invite twice as many people to a party and buy twice as many cookies, it's not like each guest will get twice as many cookies – that just leaves the originally planned number of cookies for each guest. But for response time it comes back to the first equation in TFA: T = 1/μ · 1/(1 - ρ) Doubling both arrival rate and maximum service rate leaves ρ – and the second factor with it – unchanged, but still halves the 1/μ factor, resulting in half the response time. The appropriate amount to scale by is the k that solves the equation we get when we set the old response time T at request rate λ equal to the one at request rate 2λ and kμ processing power. This is something like T = 1/μ · 1/(1 - λ/μ) = 1/kμ · 1/(1 - 2λ/kμ) but rearranges to the much simpler k = ρ + 1 which a colleague of mine told me interprets intuitively as "the processing power that needs to be added is exactly that which will handle an additional unit of the current utilisation on top of the current utilisation, i.e. twice as much." This is mostly good news for people doing capacity planning in advance of events etc. If you run your systems at reasonable utilisation levels normally, you don't actually need that much additional capacity to handle peak loads.
- CaptainNegative 2y ago
  A simple way to view the first statement is that by both doubling the request rate and halving the processing time, you're effectively speeding up time by a factor of 2. If you were to record a video of the entire system, someone switching the parameters as you describe and someone putting the recorded video on a 2x fast forward would be fundamentally indistinguishable. So, naturally, the response time gets cut down on half as well.
- steveBK123 2y ago
  > This is mostly good news for people doing capacity planning in advance of events etc. If you run your systems at reasonable utilisation levels normally, you don't actually need that much additional capacity to handle peak loads. Stop using math that will put the hyperscalers/serverless/microservices bros out of business! /s
vitus 2y ago
> a utilization of 0.90 > So we went from a latency of 1 second to 0.091 seconds which is an 11 times improvement. There's your problem -- you should never allow unbounded queue growth at high utilization. Going from 80% to 90% utilization doubles your average wait times. We could similarly make this number arbitrarily large by pushing that utilization closer to 1, e.g. "We halved service time at 99.99% utilization and saw a 10000x improvement". But that's not interesting, as your users will complain that your service is unusable under heavy load far before you get to that point. The typical "fix" is to add load shedding (e.g. based on queue length) combined with some intelligent backoff logic at the client (to reduce congestion), and call it a day. This has its own downsides, e.g. increased latency for everyone in cases of overload. Or, if your configured queue length is too large, you get bufferbloat. (I have seen an argument for using LIFO instead of FIFO, which achieves much more predictable median performance at the expense of causing unbounded badness in the worst case. For this, your client needs to set deadlines, which it should probably be doing anyways.)
- paulsutter 2y ago
  A counterintuitive idea would be to use the machines for two purposes. - a high priority service with arbitrarily low utilization with low latency, and - a low priority high utilization service like batch processing to keep overall use near 100%
  - vitus 2y ago
    Why is this counterintuitive? You're describing scheduling -- your high priority service has the ability to preempt the low priority service and use more of your CPU (or whatever your bottleneck is) if there are pending requests. If you have a high-availability, latency-sensitive service that's processing incoming requests in realtime, you want it to be overprovisioned (for limiting queue lengths, the ability to soak up DoS before other systems kick in, etc). But that's wasteful if you're idle half the time. (Or generally, off-peak -- you might explore spinning up / down nodes dynamically, but you probably still want some baseline amount of capacity in each of your availability zones.) Another dimension you could explore (if your problem space allows it) is varying the amount of work you perform depending on your current load -- for instance, you could imagine a video server that serves 4k at light load, then degrades to 1080p at moderate load, and then degrades even further to 720p at heavy load. That said, it depends on your cost model. If you're dealing with bare metal (or you are the cloud) where your principal operating expenses are space and power, then you might be fine with servers idling if power is expensive. If depreciation of your servers drives your costs (or if you get charged the same amount regardless of your actual utilization), then you might want to run your servers hotter.
deleted 2y ago
[deleted]
YetAnotherNick 2y ago
> a utilization of 0.90 Industry standard utilization is 50-60%, not 90%. If it is 90% utilization, you are destined for failure as 10% extra requests even for few seconds would kill your service. And it should be 60% even if service time increases or decreases, so decreasing the service time by half should ideally halve the resources.

130 points by luu 2y ago

alhaad 2y ago

Why is arrival rate a function of service time?

cpitman 2y ago
Utilization is Service Time times Arrival Rate, ie if requests arrive twice as fast utilization is doubled, and also if a service takes twice as long to process. When the theoretical service is optimized to take half a long, the assumption is that the request rate doesn't actually change. So they use the above relationship to calculate the new utilization, given half the service time and the same arrival rate.
- amne 2y ago
  so the unit for Utilization in your example is "active request" ? I just wish the article didn't assume units are easily inferred which would imply most readers are familiar with the subject.
  - amne 2y ago
    Having read it more than once now I think utilization is a ratio, maybe? But that means the unit for S needs to be seconds/request such that: utilization(ro) = S * arrival_rate(lambda) = seconds/request * request/seconds = bare ratio. More coffee required.
    - ajb 2y ago
      Yes, that's normally how utilisation is understood - as the fraction of time used by requests, which is therefore a dimensionless quantity.
ajb 2y ago
I don't think he's claiming that it's causally a function of service time (although this can be the case if demand is elastic). Rather, utilisation is calculated from service time and arrival rate, and they're just stating that this equation can be rearranged to calculate arrival rate if you know the other two.

nailer 2y ago

What is service time? Edit: service time is processing time. 6:35 in https://youtu.be/03GsLxVdVzU https://youtu.be/03GsLxVdVzU

amelius 2y ago
And you can read more here: https://en.wikipedia.org/wiki/Queueing_theory https://en.wikipedia.org/wiki/Queueing_theory

davherrmann 2y ago

The math seems to be off in a few places: 1. When solving for the arrival rate λ, it should be λ=ρ/S instead of λ=S/ρ. 2. Calculating the arrival rate λ with the correct formula results in 9 requests/second instead of 10 request/second. 3. Calculating the new utilization ρ should be 0.05x9 instead of 0.05x10. The result of the calculated utilization ρ is correct (0.45), so is the calculated new latency. edit: new lines

jankar 2y ago
Even with the wrong formula for λ This one is also off: λ = S/ρ = 0.1/(1−0.9) = 10 Should be 1 not 10.

jph 2y ago

Queueing theory refresher for software developers: https://github.com/joelparkerhenderson/queueing-theory https://github.com/joelparkerhenderson/queueing-theory This can help put the article in context. The author writes "wanted to freshen up my queuing theory a bit".

fwlr 2y ago

In mathematical queueing theory, Little's law (also result, theorem, lemma, or formula[1][2]) is a theorem by John Little which states that the long-term average number L of customers in a stationary system is equal to the long-term average effective arrival rate λ multiplied by the average time W that a customer spends in the system. Expressed algebraically the law is L=λW The relationship is not influenced by the arrival process distribution, the service distribution, the service order, or practically anything else. In most queuing systems, service time is the bottleneck that creates the queue. https://en.m.wikipedia.org/wiki/Little%27s_law https://en.m.wikipedia.org/wiki/Little%27s_law An extremely useful law to remember. You’d be surprised how much bullshit it can detect!

jethkl 2y ago
> An extremely useful law to remember.... Would you be willing to provide an example where you applied Little's Law?
- kqr 2y ago
  Many electronic queueing systems in hospitals etc. show you how many customers are ahead of you. If you observe the time it takes for a few people to receive service you can estimate how long you'll be stuck waiting. This is a number they rarely show you because it's often not encouraging... It's the most primitive application but immediately useful for anyone. I've used similar methods to estimate work lag: https://two-wrongs.com/estimating-work-lag.html https://two-wrongs.com/estimating-work-lag.html And to argue for concurrency limits in latency-sensitive backend serviced.
- AceyMan 2y ago
  Every time I'm in a queue at a store I compute the arrival rate while I wait in line. (Little's Law is one of my very favorite pages in all of Wikipedia!).
- fwlr 2y ago
  Sure! In a professional capacity - our customers were dissatisfied with the length of time and flakiness of a particular workload job[0], and I was party to the discussions on how to solve this problem. Knowing Little's Law allowed me to dissent against the prevailing opinion that we should customise our job processing queue to prioritise these jobs[1], arguing instead to provision more resources (i.e. beefier servers). The decision was still made to alter the priority. The change went into production and was found to unacceptably degrade the performance of other jobs. Thankfully, one of the engineers who I had convinced that "processing time is the only factor that matters" had spent all their time optimizing the heavy task, to the point where it was no longer a heavy task, thus saving the day. 0. The job was some kind of "export CSV" form, and it somehow involved both 'traversing dozens of highly normalised tables' and 'digging into json blobs stored as text'. 1. I specifically remember one of the arguments was that if you have 3 heavy tasks A B and C, best case is "in parallel" which takes max(A, B, C) time whereas worst case is "sequential" which takes (A) + (B + A) + (C + B + A) time, our current priority approximated the "sequential" scenario, and the priority change would instead approximate the "parallel" scenario. I use scare quotes because I felt it was a resource issue (the "sequential" pattern was a byproduct of the most common way a heavy task got enough resources... which was an earlier heavy task finished and freed up a lot of resources).

drewhk 2y ago

I am a bit worried of the overuse of Little's formula, especially in these catchy educational presentations. In reality queue sizes will dictate your consumer observable latency profile, which is in turn is dictated by the actual distribution of the service time - it is not a constant. If you think about it, if you have an ideal system that serves users like a clockwork, every X ms with no jitter, while your arrival is also completely regular, every Y ms (Y < X), then basically a queue length of 1 is sufficient. In reality, just like we all observe in real-life queues, service time is far from constant, and outliers result in queue buildup. This is why often cutting the tail of service-time latency results in better overall latency than simply reducing average service-time. Little's formula of course holds also in the above scenario, but it handles long-time averages and does not give you any indication what extreme behavior is lurking under the mask of these averages.

kqr 2y ago
> ...the actual distribution of the service time - it is not a constant. I'm concerned by the number of misunderstandings expressed in short time here. 1. Nobody claims service time is constant. 2. Little's law is one of the few parts of queueing theory that remarkably does not depend on service time distribution. 3. Many results for typical simplified M/M/c systems apply well also to any other service time distribution provided (a) arrivals are Poisson, and (b) the server uses time slicing multiprocessing. These are not very severe requirements, fortunately! Long-term average sounds restrictive but it really just means a period long enough to exhibit some statistical stability. Most systems I see sit mainly in those regimes.
- drewhk 2y ago
  > I'm concerned by the number of misunderstandings expressed in short time here. I have a feeling you misread my comment completely, and the misunderstandings are on your part? > Nobody claims service time is constant. Neither did I. Neither did I claimed that Little's Formula requires a constant service time. > Little's law is one of the few parts of queueing theory that remarkably does not depend on service time distribution. I did not say otherwise either. My point is that it is way less useful and enlightening than these edutainment posts make it. Two systems with the exact same parameters and results by Little's Formula might behave completely differently, and in many cases, counterintuitively. > Many results for typical simplified M/M/c systems apply well also to any other service time distribution provided (a) arrivals are Poisson, and (b) the server uses time slicing multiprocessing. These are not very severe requirements, fortunately! This was not my point. Or do you claim that queue size distributions DO NOT depend on service time distribution? Because that WAS my point. Averages do not tell the story you are most interested in. The whole point of queues is that service and arrival times have distributions with deviation. I personally think queues and buffers are very-very important and I am a huge proponent of predictable user-observable latencies as they improve general system health and resiliency under load. > Long-term average sounds restrictive but it really just means a period long enough to exhibit some statistical stability. Most systems I see sit mainly in those regimes. Long-term averages do not talk about pathological transient behavior, do not help you with queue sizing - or setting ideal timeouts. Also, statistical stability is misleading, the convergence time to the given statistic might be arbitrarily slow. Also, if we talk about real-world systems (which you do), they exhibit feedback do to clients retrying, throwing off the formula and potential ergodicity.

kqr 2y ago

Another of those somewhat counter-intuitive results is the answer to the question "how much do we need to scale up to avoid response time regression when the request rate is doubled?" It is very easy to blurt out "well obviously we need twice the processing power!" but if we scale to twice the processing power, then start accepting twice the request rate – we will actually be serving each request in half the time we originally did. To many people that sounds weird; it sounds like we got something for nothing. If I invite twice as many people to a party and buy twice as many cookies, it's not like each guest will get twice as many cookies – that just leaves the originally planned number of cookies for each guest. But for response time it comes back to the first equation in TFA: T = 1/μ · 1/(1 - ρ) Doubling both arrival rate and maximum service rate leaves ρ – and the second factor with it – unchanged, but still halves the 1/μ factor, resulting in half the response time. The appropriate amount to scale by is the k that solves the equation we get when we set the old response time T at request rate λ equal to the one at request rate 2λ and kμ processing power. This is something like T = 1/μ · 1/(1 - λ/μ) = 1/kμ · 1/(1 - 2λ/kμ) but rearranges to the much simpler k = ρ + 1 which a colleague of mine told me interprets intuitively as "the processing power that needs to be added is exactly that which will handle an additional unit of the current utilisation on top of the current utilisation, i.e. twice as much." This is mostly good news for people doing capacity planning in advance of events etc. If you run your systems at reasonable utilisation levels normally, you don't actually need that much additional capacity to handle peak loads.

CaptainNegative 2y ago
A simple way to view the first statement is that by both doubling the request rate and halving the processing time, you're effectively speeding up time by a factor of 2. If you were to record a video of the entire system, someone switching the parameters as you describe and someone putting the recorded video on a 2x fast forward would be fundamentally indistinguishable. So, naturally, the response time gets cut down on half as well.
steveBK123 2y ago
> This is mostly good news for people doing capacity planning in advance of events etc. If you run your systems at reasonable utilisation levels normally, you don't actually need that much additional capacity to handle peak loads. Stop using math that will put the hyperscalers/serverless/microservices bros out of business! /s

vitus 2y ago

> a utilization of 0.90 > So we went from a latency of 1 second to 0.091 seconds which is an 11 times improvement. There's your problem -- you should never allow unbounded queue growth at high utilization. Going from 80% to 90% utilization doubles your average wait times. We could similarly make this number arbitrarily large by pushing that utilization closer to 1, e.g. "We halved service time at 99.99% utilization and saw a 10000x improvement". But that's not interesting, as your users will complain that your service is unusable under heavy load far before you get to that point. The typical "fix" is to add load shedding (e.g. based on queue length) combined with some intelligent backoff logic at the client (to reduce congestion), and call it a day. This has its own downsides, e.g. increased latency for everyone in cases of overload. Or, if your configured queue length is too large, you get bufferbloat. (I have seen an argument for using LIFO instead of FIFO, which achieves much more predictable median performance at the expense of causing unbounded badness in the worst case. For this, your client needs to set deadlines, which it should probably be doing anyways.)

paulsutter 2y ago
A counterintuitive idea would be to use the machines for two purposes. - a high priority service with arbitrarily low utilization with low latency, and - a low priority high utilization service like batch processing to keep overall use near 100%
- vitus 2y ago
  Why is this counterintuitive? You're describing scheduling -- your high priority service has the ability to preempt the low priority service and use more of your CPU (or whatever your bottleneck is) if there are pending requests. If you have a high-availability, latency-sensitive service that's processing incoming requests in realtime, you want it to be overprovisioned (for limiting queue lengths, the ability to soak up DoS before other systems kick in, etc). But that's wasteful if you're idle half the time. (Or generally, off-peak -- you might explore spinning up / down nodes dynamically, but you probably still want some baseline amount of capacity in each of your availability zones.) Another dimension you could explore (if your problem space allows it) is varying the amount of work you perform depending on your current load -- for instance, you could imagine a video server that serves 4k at light load, then degrades to 1080p at moderate load, and then degrades even further to 720p at heavy load. That said, it depends on your cost model. If you're dealing with bare metal (or you are the cloud) where your principal operating expenses are space and power, then you might be fine with servers idling if power is expensive. If depreciation of your servers drives your costs (or if you get charged the same amount regardless of your actual utilization), then you might want to run your servers hotter.

deleted 2y ago

[deleted]

YetAnotherNick 2y ago

> a utilization of 0.90 Industry standard utilization is 50-60%, not 90%. If it is 90% utilization, you are destined for failure as 10% extra requests even for few seconds would kill your service. And it should be 60% even if service time increases or decreases, so decreasing the service time by half should ideally halve the resources.