8 ms·

Why disaster happens at the edges: An introduction to queue theory

245 points by ayewo 5y ago

mhdee740 5y ago
Free Download windows 11 pre-activated https://programs.themicrotech.net/app/windows-11-pro-latest-version-64bit https://programs.themicrotech.net/app/windows-11-pro-latest-...
fulion 5y ago
honestly speaking, I cannot really understand why the queue will grow infinitely when average arrival rate equals service rate. It's not intuitive to me. sometimes arrival rate is greater than service rate so the queue will grow but sometimes it is lower so the queue will shrink. To me, it will finally achieve a kind of balance...
wyager 5y ago
> The TCP protocol, for instance, generates backpressure with code 503 Doesn't TCP typically use sliding window flow control? I'm not sure what "code" is referring to in this context.
- detaro 5y ago
  That seems like a typo or confusion and they actually mean HTTP.
- addisonj 5y ago
  I think this might be an error in the text, HTTP status code 503 can be used for backpressure, which I think is what is being referred too But yes, TCP uses windows for back-pressure, but that isn't really useful for application level backpressure as the OS controls the queues sizes, so pretty much most systems have their own backpressure on top.
  - kqr 5y ago
    It's useful still! If you have an application that talks to another application on the other side of the world, you get to control how fast it sends you stuff with your reading speed. If you stop reading from the socket, the sending application will stop sending before long. It seems like spooky action at a distance but it's just backpressure propagating through many layers.
  - Matthias247 5y ago
    It's not that useless. A lot of applications these days are really using HTTP. And in HTTP/1 if you read from a response body from the socket (or write it), you are really already using the backpressure from TCP instead of having anything on top of it. With HTTP/2 and /3 that's different due to mulitplexing of multiple streams on the same socket - in that case there exists the additional flow control windows on top of TCP. These actually make those protocols rather hard to implement correctly.
thingsgoup 5y ago
A frustrating headline. Where else would it happen? The middle? Crystals fracture on their faces. Things tend to break along their boundaries.
- aaron695 5y ago
  Astroworld Festival was a mainstream festival with average aged festival goers dying in the main act. I have no idea on your point? A lot of people are trying to make Astroworld be on a boundary, I guess? Step one you worry about the middle. If crystals don't also fracture on the middle then it's a bad analogy. Rocks aren't the same as processes.
- bonestormii 5y ago
  I feel like you are understanding the title as I first understood it, meaning like, "the external facing portions of infrastructure". However, reading the article, it seems clear that he's referring to the edges of a distribution curve (i.e. Infrequent events that impact experience nonetheless). From the article: "It’s tempting to focus on the peak of the curve. That’s where most of the results are. But the edges are where the action is. Events out on the tails may happen less frequently, but they still happen. In digital systems, where billions of events take place in a matter of seconds, one-in-a-million occurrences happen all the time. And they have an outsize impact on user experience." EDIT: IMO, the title is still a little annoying in this respect. I think everyone would agree if a request to your site fails 5% of the time, that is unacceptable, even though it "usually works." The discussion of the distribution curve simply to make the point that spikes in usage cause backed up queues which impact performance isn't necessarily helpful as far as I can tell, and it seems done largely in service to the title. In my mind while reading this, I'm thinking, "Okay, cool, but how does the fact that this interesting issue exists at the edge of the curve help me identify it?" Answer: It doesn't. If you see errors occurring, you will investigate them once they are noticed. Being at the edge of the curve may mean it takes longer to notice, but like, what kind of alerting system are you using that discriminates against rare issues in favor of common ones? Discussing queues, over provisioning, back pressure, etc. are all super interesting and helpful.
  - deleted 5y ago
polskibus 5y ago
I would love to read more on queue theory + web applications - is there anything out there worth reading for a more in-depth understanding (applied to applications) but with key takeways/rules of thumb presented like in this article?
jph 5y ago
Queueing theory-- my notes for programmers: https://github.com/joelparkerhenderson/queueing-theory https://github.com/joelparkerhenderson/queueing-theory Queueing theory is the mathematical study of waiting lines, or queues. We use queueing theory in our software development, for purposes such as project management kanban boards, inter-process communication message queues, and devops continuous deployment pipelines.
- layer8 5y ago
  The notes don’t explain what problems queue theory solves, i.e. why would I want to use it, as a programmer. The Wikipedia article’s second sentence is a bit more helpful in that respect: "A queueing model is constructed so that queue lengths and waiting time can be predicted."
  - jph 5y ago
    We typically track many things about the activities in the queue, and we want to summarize the results by choosing a shortlist of the most relevant ones for our projects. Dμ = Delivery service rate. Devops teams may say "deployment frequency" or "we ship X times per day". Rτ = Restore lead time. Site reliability engineers may say "time to restore service" or "mean time to restore (MTTR)".
- jimmySixDOF 5y ago
  All kinds of Queue analysis is also done extensively in Six Sigma practice
spicybright 5y ago
I'm going to sound like a jerk but there is just so much "fluff" to this, including the side bar Bio on the author.
kesor 5y ago
TheNewStack needs more articles like this one and less articles that talk about some new feature where by adding extra five lines of YAML you get something or other in your Kubernetes.
roenxi 5y ago
Queue theory is almost a distraction because it overcomplicates the situation. The underlying insight is that rates matter. If a system can handle 100 events a second, then 99 events per second everything is fine and 101 events per second the system is down. There is a threshold where everything falls apart. Queue theory encourages people to think in terms of flow rates and has the technically correct de-rates to nominal capacity to account for variance. But normally that is overkill except in highly engineered systems. The battle in an organisation is convincing people to look at flows at all. In my experience people love metrics that track stock (we have X widgets or can handle Y orders) and not flows (we built A widgets and sold B widgets). Anyone who has training in queue theory knows when it is appropriate to look at flows rather than stocks and that is where the value is. The formulas and variances tend to just scare people away from monitoring flows because they don't understand what is happening.
- kccqzy 5y ago
  > The underlying insight is that rates matter. If a system can handle 100 events a second, then 99 events per second everything is fine and 101 events per second the system is down. Not really. You need actual theory to inform you whether 99 events per second is okay. See https://www.johndcook.com/blog/2008/10/21/what-happens-when-you-add-a-new-teller/ https://www.johndcook.com/blog/2008/10/21/what-happens-when-...
  - roenxi 5y ago
    If you want to maintain 99.99989% uptime or are about to spend $10 million, yes. If you want the cheap option then measure (arrival rate / service rate) and try to keep that below 80%. Then if that doesn't work adjust accordingly. That isn't really queue theory because it doesn't consider variance and requires effectively no knowledge of literature, what rho means or why people use M/M/1 queues as a default. Don't have to spell Poisson. But it will usually get you to where you want to be. Most of the time feeling it out in production is a lot cheaper than keeping an in house specialist. If it isn't then sure, maintain a specialist to monitor the situation. It is a relatively rare role though.
crmd 5y ago
I worked at IBM in earlier days, and a couple of the Research people in the data storage group at Almaden and Poughkeepsie gave some great lectures and made excellent tools for modeling cache disk storage array performance that were based heavily on queue theory. This brings back great memories, thanks!
efitz 5y ago
There are secondary non-obvious effects of caching and queueing. Cold start is an important scenario that lots of people overlook - “we won’t restart it during busy times”, etc. however if you have a bug or outage then that might be precisely when you restart. During a cold start you will often find your system behaves as it does at the tails of the performance curve, either because you are getting 100% cache misses, or because all your queues are full due to a client pile-on or queued upstream work, or some combination. The article described back pressure; I can’t emphasize that enough as part of any resilient queuing system. Chains of queues are only as performant as their weakest link.
dboreham 5y ago
Throughout my career, the one thing I've noticed engineers/developers consistently have trouble modeling in their heads is queuing.
- sparsely 5y ago
  They absolutely love adding them to previously functional systems even so!
ignoramous 5y ago
Bitten by queues in every team I was at AWS: > As a rule of thumb, target utilization below 75% This is one good reason to rely on serverless. Simply outsource the problem to a system that knows how to handle this better. > Steer slower workloads to paths with lower utilization This is fraught with all sorts of perils [0], so take caution going down this valid but tricky route. > Limit variance as much as possible when utilization is high This is key, and one of the most elegant solutions to this problem I know of comes from a Facebook talk on CoDel + Adaptive LIFO. [1] > Implement backpressure in systems where it is not built-in Making downstream dependencies behave is never an option. Selectively isolating noisy neighbours, if possible, from other well behaved clients, tends to work well for multi-tenant systems [2], in addition to monitoring long work (by dropping work that takes forever) [3], or better yet, doing constant amount of work [4] (aka eliminating modes) [5]. > Use throttling and load shedding to reduce pressure on downstream queues. One way is to impl admission control (ala Token Bucket) to minimise the impact of thundering herds. Though, clients do not take kindly to being throttled. [6] A great article; many have been written at this point. Very many still have been burned by queues. Though, in my experience, without an exception, some component somewhere was always building up that backlog! [7][8][9] [0] Interns with Toasters: How I taught people about Load Balancers, https://news.ycombinator.com/item?id=16894946 https://news.ycombinator.com/item?id=16894946 [1] Fail at scale: Controlling queue delays, https://blog.acolyer.org/2015/11/19/fail-at-scale-controlling-queue-delay/ https://blog.acolyer.org/2015/11/19/fail-at-scale-controllin... [2] Worload isolation, https://aws.amazon.com/builders-library/workload-isolation-using-shuffle-sharding/ https://aws.amazon.com/builders-library/workload-isolation-u... [3] Avoiding insurmountable queue backlogs, https://aws.amazon.com/builders-library/avoiding-insurmountable-queue-backlogs/ https://aws.amazon.com/builders-library/avoiding-insurmounta... [4] Constant work, https://aws.amazon.com/builders-library/reliability-and-constant-work/ https://aws.amazon.com/builders-library/reliability-and-cons... [5] Cache, modes, and unstable systems, https://news.ycombinator.com/item?id=28344561 https://news.ycombinator.com/item?id=28344561 [6] Fairness in multi-tenant systems, https://aws.amazon.com/builders-library/fairness-in-multi-tenant-systems/ https://aws.amazon.com/builders-library/fairness-in-multi-te... [7] Using load shedding to avoid overload, https://aws.amazon.com/builders-library/using-load-shedding-to-avoid-overload/ https://aws.amazon.com/builders-library/using-load-shedding-... [8] Treadmill: Precise load testing, https://research.fb.com/publications/treadmill-attributing-the-source-of-tail-latency-through-precise-load-testing-and-statistical-inference/ https://research.fb.com/publications/treadmill-attributing-t... [9] Cascading failures, https://sre.google/sre-book/addressing-cascading-failures/ https://sre.google/sre-book/addressing-cascading-failures/
Neverending 5y ago
Don’t canceled/rejected requests have infinite latency by definition?
- bonestormii 5y ago
  For the one request that is cancelled/rejected, but not for every other request behind them in a queue.
overkalix 5y ago
Seems like this guy is about to discover six sigma...
xmcqdpt2 5y ago
I'm being pedantic but, >Every distribution can be described as a curve. The width of this curve is known as its variance. Not every distribution has a variance. Some notable examples include the Cauchy distribution (or Lorentz lineshape in physics), https://en.m.wikipedia.org/wiki/Cauchy_distribution https://en.m.wikipedia.org/wiki/Cauchy_distribution the Power law distribution for powers lesser or equal to 2, https://en.m.wikipedia.org/wiki/Pareto_distribution https://en.m.wikipedia.org/wiki/Pareto_distribution and the Levy distribution, https://en.m.wikipedia.org/wiki/Lévy_distribution https://en.m.wikipedia.org/wiki/Lévy_distribution These are not mathematical curiousities but actually describe real physical systems. Additionally, the variance works as a "width" only for unimodal distributions. Any variance based metrics or analysis should only be used after checking for multimodality and, for multimodal data, with extreme caution thereafter.
lelanthran 5y ago
> The TCP protocol, for instance, generates backpressure with code 503 Surely they mean 'HTTP protocol'? TCP doesn't do back pressure but IP does at the router level, IIRC.

245 points by ayewo 5y ago

Free Download windows 11 pre-activated https://programs.themicrotech.net/app/windows-11-pro-latest-version-64bit https://programs.themicrotech.net/app/windows-11-pro-latest-...

fulion 5y ago

honestly speaking, I cannot really understand why the queue will grow infinitely when average arrival rate equals service rate. It's not intuitive to me. sometimes arrival rate is greater than service rate so the queue will grow but sometimes it is lower so the queue will shrink. To me, it will finally achieve a kind of balance...

wyager 5y ago

> The TCP protocol, for instance, generates backpressure with code 503 Doesn't TCP typically use sliding window flow control? I'm not sure what "code" is referring to in this context.

detaro 5y ago
That seems like a typo or confusion and they actually mean HTTP.
addisonj 5y ago
I think this might be an error in the text, HTTP status code 503 can be used for backpressure, which I think is what is being referred too But yes, TCP uses windows for back-pressure, but that isn't really useful for application level backpressure as the OS controls the queues sizes, so pretty much most systems have their own backpressure on top.
- kqr 5y ago
  It's useful still! If you have an application that talks to another application on the other side of the world, you get to control how fast it sends you stuff with your reading speed. If you stop reading from the socket, the sending application will stop sending before long. It seems like spooky action at a distance but it's just backpressure propagating through many layers.
- Matthias247 5y ago
  It's not that useless. A lot of applications these days are really using HTTP. And in HTTP/1 if you read from a response body from the socket (or write it), you are really already using the backpressure from TCP instead of having anything on top of it. With HTTP/2 and /3 that's different due to mulitplexing of multiple streams on the same socket - in that case there exists the additional flow control windows on top of TCP. These actually make those protocols rather hard to implement correctly.

thingsgoup 5y ago

A frustrating headline. Where else would it happen? The middle? Crystals fracture on their faces. Things tend to break along their boundaries.

aaron695 5y ago
Astroworld Festival was a mainstream festival with average aged festival goers dying in the main act. I have no idea on your point? A lot of people are trying to make Astroworld be on a boundary, I guess? Step one you worry about the middle. If crystals don't also fracture on the middle then it's a bad analogy. Rocks aren't the same as processes.
bonestormii 5y ago
I feel like you are understanding the title as I first understood it, meaning like, "the external facing portions of infrastructure". However, reading the article, it seems clear that he's referring to the edges of a distribution curve (i.e. Infrequent events that impact experience nonetheless). From the article: "It’s tempting to focus on the peak of the curve. That’s where most of the results are. But the edges are where the action is. Events out on the tails may happen less frequently, but they still happen. In digital systems, where billions of events take place in a matter of seconds, one-in-a-million occurrences happen all the time. And they have an outsize impact on user experience." EDIT: IMO, the title is still a little annoying in this respect. I think everyone would agree if a request to your site fails 5% of the time, that is unacceptable, even though it "usually works." The discussion of the distribution curve simply to make the point that spikes in usage cause backed up queues which impact performance isn't necessarily helpful as far as I can tell, and it seems done largely in service to the title. In my mind while reading this, I'm thinking, "Okay, cool, but how does the fact that this interesting issue exists at the edge of the curve help me identify it?" Answer: It doesn't. If you see errors occurring, you will investigate them once they are noticed. Being at the edge of the curve may mean it takes longer to notice, but like, what kind of alerting system are you using that discriminates against rare issues in favor of common ones? Discussing queues, over provisioning, back pressure, etc. are all super interesting and helpful.
- deleted 5y ago

polskibus 5y ago

I would love to read more on queue theory + web applications - is there anything out there worth reading for a more in-depth understanding (applied to applications) but with key takeways/rules of thumb presented like in this article?

jph 5y ago

Queueing theory-- my notes for programmers: https://github.com/joelparkerhenderson/queueing-theory https://github.com/joelparkerhenderson/queueing-theory Queueing theory is the mathematical study of waiting lines, or queues. We use queueing theory in our software development, for purposes such as project management kanban boards, inter-process communication message queues, and devops continuous deployment pipelines.

layer8 5y ago
The notes don’t explain what problems queue theory solves, i.e. why would I want to use it, as a programmer. The Wikipedia article’s second sentence is a bit more helpful in that respect: "A queueing model is constructed so that queue lengths and waiting time can be predicted."
- jph 5y ago
  We typically track many things about the activities in the queue, and we want to summarize the results by choosing a shortlist of the most relevant ones for our projects. Dμ = Delivery service rate. Devops teams may say "deployment frequency" or "we ship X times per day". Rτ = Restore lead time. Site reliability engineers may say "time to restore service" or "mean time to restore (MTTR)".
jimmySixDOF 5y ago
All kinds of Queue analysis is also done extensively in Six Sigma practice

spicybright 5y ago

I'm going to sound like a jerk but there is just so much "fluff" to this, including the side bar Bio on the author.

kesor 5y ago

TheNewStack needs more articles like this one and less articles that talk about some new feature where by adding extra five lines of YAML you get something or other in your Kubernetes.

roenxi 5y ago

Queue theory is almost a distraction because it overcomplicates the situation. The underlying insight is that rates matter. If a system can handle 100 events a second, then 99 events per second everything is fine and 101 events per second the system is down. There is a threshold where everything falls apart. Queue theory encourages people to think in terms of flow rates and has the technically correct de-rates to nominal capacity to account for variance. But normally that is overkill except in highly engineered systems. The battle in an organisation is convincing people to look at flows at all. In my experience people love metrics that track stock (we have X widgets or can handle Y orders) and not flows (we built A widgets and sold B widgets). Anyone who has training in queue theory knows when it is appropriate to look at flows rather than stocks and that is where the value is. The formulas and variances tend to just scare people away from monitoring flows because they don't understand what is happening.

kccqzy 5y ago
> The underlying insight is that rates matter. If a system can handle 100 events a second, then 99 events per second everything is fine and 101 events per second the system is down. Not really. You need actual theory to inform you whether 99 events per second is okay. See https://www.johndcook.com/blog/2008/10/21/what-happens-when-you-add-a-new-teller/ https://www.johndcook.com/blog/2008/10/21/what-happens-when-...
- roenxi 5y ago
  If you want to maintain 99.99989% uptime or are about to spend $10 million, yes. If you want the cheap option then measure (arrival rate / service rate) and try to keep that below 80%. Then if that doesn't work adjust accordingly. That isn't really queue theory because it doesn't consider variance and requires effectively no knowledge of literature, what rho means or why people use M/M/1 queues as a default. Don't have to spell Poisson. But it will usually get you to where you want to be. Most of the time feeling it out in production is a lot cheaper than keeping an in house specialist. If it isn't then sure, maintain a specialist to monitor the situation. It is a relatively rare role though.

crmd 5y ago

I worked at IBM in earlier days, and a couple of the Research people in the data storage group at Almaden and Poughkeepsie gave some great lectures and made excellent tools for modeling cache disk storage array performance that were based heavily on queue theory. This brings back great memories, thanks!

efitz 5y ago

There are secondary non-obvious effects of caching and queueing. Cold start is an important scenario that lots of people overlook - “we won’t restart it during busy times”, etc. however if you have a bug or outage then that might be precisely when you restart. During a cold start you will often find your system behaves as it does at the tails of the performance curve, either because you are getting 100% cache misses, or because all your queues are full due to a client pile-on or queued upstream work, or some combination. The article described back pressure; I can’t emphasize that enough as part of any resilient queuing system. Chains of queues are only as performant as their weakest link.

dboreham 5y ago

Throughout my career, the one thing I've noticed engineers/developers consistently have trouble modeling in their heads is queuing.

sparsely 5y ago
They absolutely love adding them to previously functional systems even so!

ignoramous 5y ago

Bitten by queues in every team I was at AWS: > As a rule of thumb, target utilization below 75% This is one good reason to rely on serverless. Simply outsource the problem to a system that knows how to handle this better. > Steer slower workloads to paths with lower utilization This is fraught with all sorts of perils [0], so take caution going down this valid but tricky route. > Limit variance as much as possible when utilization is high This is key, and one of the most elegant solutions to this problem I know of comes from a Facebook talk on CoDel + Adaptive LIFO. [1] > Implement backpressure in systems where it is not built-in Making downstream dependencies behave is never an option. Selectively isolating noisy neighbours, if possible, from other well behaved clients, tends to work well for multi-tenant systems [2], in addition to monitoring long work (by dropping work that takes forever) [3], or better yet, doing constant amount of work [4] (aka eliminating modes) [5]. > Use throttling and load shedding to reduce pressure on downstream queues. One way is to impl admission control (ala Token Bucket) to minimise the impact of thundering herds. Though, clients do not take kindly to being throttled. [6] A great article; many have been written at this point. Very many still have been burned by queues. Though, in my experience, without an exception, some component somewhere was always building up that backlog! [7][8][9] [0] Interns with Toasters: How I taught people about Load Balancers, https://news.ycombinator.com/item?id=16894946 https://news.ycombinator.com/item?id=16894946 [1] Fail at scale: Controlling queue delays, https://blog.acolyer.org/2015/11/19/fail-at-scale-controlling-queue-delay/ https://blog.acolyer.org/2015/11/19/fail-at-scale-controllin... [2] Worload isolation, https://aws.amazon.com/builders-library/workload-isolation-using-shuffle-sharding/ https://aws.amazon.com/builders-library/workload-isolation-u... [3] Avoiding insurmountable queue backlogs, https://aws.amazon.com/builders-library/avoiding-insurmountable-queue-backlogs/ https://aws.amazon.com/builders-library/avoiding-insurmounta... [4] Constant work, https://aws.amazon.com/builders-library/reliability-and-constant-work/ https://aws.amazon.com/builders-library/reliability-and-cons... [5] Cache, modes, and unstable systems, https://news.ycombinator.com/item?id=28344561 https://news.ycombinator.com/item?id=28344561 [6] Fairness in multi-tenant systems, https://aws.amazon.com/builders-library/fairness-in-multi-tenant-systems/ https://aws.amazon.com/builders-library/fairness-in-multi-te... [7] Using load shedding to avoid overload, https://aws.amazon.com/builders-library/using-load-shedding-to-avoid-overload/ https://aws.amazon.com/builders-library/using-load-shedding-... [8] Treadmill: Precise load testing, https://research.fb.com/publications/treadmill-attributing-the-source-of-tail-latency-through-precise-load-testing-and-statistical-inference/ https://research.fb.com/publications/treadmill-attributing-t... [9] Cascading failures, https://sre.google/sre-book/addressing-cascading-failures/ https://sre.google/sre-book/addressing-cascading-failures/

Neverending 5y ago

Don’t canceled/rejected requests have infinite latency by definition?

bonestormii 5y ago
For the one request that is cancelled/rejected, but not for every other request behind them in a queue.

overkalix 5y ago

Seems like this guy is about to discover six sigma...

xmcqdpt2 5y ago

I'm being pedantic but, >Every distribution can be described as a curve. The width of this curve is known as its variance. Not every distribution has a variance. Some notable examples include the Cauchy distribution (or Lorentz lineshape in physics), https://en.m.wikipedia.org/wiki/Cauchy_distribution https://en.m.wikipedia.org/wiki/Cauchy_distribution the Power law distribution for powers lesser or equal to 2, https://en.m.wikipedia.org/wiki/Pareto_distribution https://en.m.wikipedia.org/wiki/Pareto_distribution and the Levy distribution, https://en.m.wikipedia.org/wiki/Lévy_distribution https://en.m.wikipedia.org/wiki/Lévy_distribution These are not mathematical curiousities but actually describe real physical systems. Additionally, the variance works as a "width" only for unimodal distributions. Any variance based metrics or analysis should only be used after checking for multimodality and, for multimodal data, with extreme caution thereafter.

lelanthran 5y ago

> The TCP protocol, for instance, generates backpressure with code 503 Surely they mean 'HTTP protocol'? TCP doesn't do back pressure but IP does at the router level, IIRC.