Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

thenewstack.io

Post reply on HN
Print view View original

51–60 of 62 posts

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

#51

Post by roenxi »

antman wrote: post #47
roenxi wrote: post #14

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 nom…

That is absolutely not what queuing theory says. In equally simplified terms, queuing theory says that for a system that handles 99 events per second if you size it for 100 it will probably fail because 99 is just the mean, and when you overshoot (in events per second) you don’t have the capability to cover it during the undershoot (in events per second) period because events have piled up. For a numerical example of…

It is my example, I can set the variance to whatever I like. It is a D/D/1 queue in case that isn't abundantly clear.

Which, in practice, is a model of queuing systems that often gets most of the value of queue theory and is easy to explain without jargon. Then apply an 80% fudge factor. Unless the situation needs care.

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

#52

Post by antman »

vosper wrote: post #48
antman wrote: post #47

Earlier quoted context omitted.

That is absolutely not what queuing theory says. In equally simplified terms, queuing theory says that for a system that handles 99 events per second if you size it for 100 it will probably fail because 99 is just the mean, and when you overshoot (in events per second) you don’t have the capability to cover it during the undershoot (in events per second) period because events have piled up. For a numerical example of…

I don’t know anything about queue theory, but I’m not sure how your point differs from GP? You both said that a system designed for 100 and being run at 99 falls apart at 101? I didn’t understand GPs comment about flows - perhaps that’s where the dispute is. Genuine question, looking forward to learning more :)

I am saying that the system should fail in terms of SLA even at 99.

In the link I shared there is a simple worked example of 10.3 capacity/hr for 10 events/hr that piles up 28 events. It also shows the problem can be mitigated by analysing it in queuing/probabilistic terms. In real life it is even more complicated obviously!

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

#53

Post by roenxi »

jimkleiber wrote: post #26
roenxi wrote: post #14

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 nom…

> 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). This reminds me of an entrepreneurship class I took in college where the professor emphasized the importance of cash flow, something I hadn't considered much and found somewhat counterintuit…

Queue theory is a lot of fun. There aren't a lot of variables needed to characterise a queue (rate in, rate out, variance of both the rates encoded into a probability distribution). But there are a lot of observable variables (queue length, wait times, utilisation of the servers, probability of there being a queue when a new customer enters the system, probability of the queue overflowing, etc). That means the system is highly over-determined, you need a very small number of observed variables to be able to calculate everything.

Basically all you are doing when you "study queue theory" is training your brain to go very quickly from looking at some random metric to thinking "oh, this is a queue with X distribution, I need to work out the arrival rate and service rate then I know everything".

My personal reference is "Fundamentals of Queuing Theory" by Gross, Shortle, Thomson & Harris. But to learn, just pick some interesting queues (ie, queues with variance in the rates) and start calculating (if cars arrive at a light with X mean rate, what variance means that there will sometimes be a queue extending around the street? Would adding another server at this shop have a big or small difference on how long it takes to prepare my order? Based on the number of checkouts at this supermarket, what rate are their planners expecting - is this a busy period?).

No individual idea in queue theory is that powerful, the advantage is really that when you see a queue you don't waste hours trying to link variables in O(n^2) ways and instead work with arrival/service rates. And you realise that the system works by phase changes rather than anything else, which is in a sense obvious but not actually very intuitive if you haven't identified the queue.

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

#54

Post by gpderetta »

vishnugupta wrote: post #30
btilly wrote: post #29

Earlier quoted context omitted.

So we should solve the problem at the port of Long Beach by randomly dropping cargo into the ocean until we no longer get container ships piling up off the coast?

Or build sufficient back pressure mechanisms so that the cargo doesn’t get loaded in the first place or better still the goods doesn’t get manufactured and so on. Send the feedback as far up the source as possible.

AKA "there are no truly unbounded queues, only queues you do not know the bounds yet". Back Pressure is good (but also hard).

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

#56

Post by xmcqdpt2 »

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

the Power law distribution for powers lesser or equal to 2,

https://en.m.wikipedia.org/wiki/Pareto_distribution

and the Levy 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.

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

#58

Post by tharkun__ »

NegativeLatency wrote: post #27
tharkun__ wrote: post #21

Earlier quoted context omitted.

Why is 101 events per second == system down? Of course there are systems where not being able to process everything right when it comes in means that you're "down". It's not a given though and queuing systems are actually perfect for use cases where not being able to process at the speed of incoming requests is completely fine. Eventual consistency is a thing. I have the same experience though that it seems to be har…

Assuming you have queues and stuff that can hold the requests in the intermediary time. Some systems will just start dropping the data or crashing and loose data. If you have a queue or something in the middle then the failure is potentially recoverable or never happens in the first place.

The term here is literally queues, so yes, there's a queue in there. I.e. HornetQ, RabbitMQ etc. I'm talking about distributed systems that are built with queuing in mind and that analyze the specific use case to understand when it is OK to have a queue build up and when it isn't.

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

#59

Post by tharkun__ »

dinosaurdynasty wrote: post #25
tharkun__ wrote: post #21

Earlier quoted context omitted.

Why is 101 events per second == system down? Of course there are systems where not being able to process everything right when it comes in means that you're "down". It's not a given though and queuing systems are actually perfect for use cases where not being able to process at the speed of incoming requests is completely fine. Eventual consistency is a thing. I have the same experience though that it seems to be har…

If you can only handle 100 events/second and you are getting 101 events/second continuously the queue depth is going to go up by 1 event/second up to infinity, causing your latency to go to infinity.

I am not talking about infinity. I am not talking about a scenario where you have a constant event stream, which will never vary. You are correct that if you have such a system, then at 101 events/second "you're dead".

I am talking about a bazillion other use cases in which there is variance in the number of events produced at any given time and where the immediate processing of those events is not of utmost importance. "Slap a queue in between" and suddenly you are no longer bound by what your systems can handle, you are only bound by what the queuing system can handle and that is usually much easier to scale (or can already handle this kind of load).

E.g. think about a system needing to synchronize with another external system. Back in the old days (and well I'm sure those systems are still out there today) synchronizing two systems may well have been an overnight job. A nightly sync job. Nowadays many such systems probably try near realtime synchronization but you don't want to make it part of the regular flow either and block the actual operation.

But sometimes there's too many synchronizations that need to happen at once, so a queue builds up over some period and goes down again a bit later. It's still better user experience than a nightly job. E.g. your regular load might be at 10 e/s. During some particularly busy time or specific bulk operations being executed in parallel by multiple people, you might have an influx of 200 e/s for a minute or so.

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

#60

Post by fulion »

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...
Post reply on HN