Speaking of queues, any book on in-depth practical queuing theory? This book is highly recommended by many people, including those on HN: https://www.cs.cmu.edu/~harchol/PerformanceModeling/book.htm.... However, a reading group by seasoned researchers said the book was not necessarily practical on production systems: https://emptysqua.re/blog/review-queue-theory-book/.
Queues don't fix overload (2014)
131–140 of 156 posts
Re: Queues don't fix overload (2014)
#132Earlier quoted context omitted.
See https://en.wikipedia.org/wiki/Bufferbloat I lived in Germany in 1999 and then the internet connection from Germany to the US would get overloaded during the day. At maybe 9am the latency would be then it would start dropping packets. I don't know if it was the intention but it was about as good as a ban on VoIP at preventing people from making international VoIP calls. Today there is more consciousness about the…
See RFC 970, "On Packet Switches With Infinite Storage" by John Nagle: https://datatracker.ietf.org/doc/html/rfc970 Back then (I was studying networking as an undergrad at the time, and interned with the Arpanet team) people really did think of network congestion as a buffer allocation problem, so the obvious solution was more buffering - i.e. adding queues. Nagel was one of the first people to point out the problem…
> (...) people really did think of network congestion as a buffer allocation problem, so the obvious solution was more buffering - i.e. adding queues.
I don't think people believed network congestion was a buffer allocation problem. I think people believed buffering was a way to mitigate congestion caused by a spike in traffic before allowing connection problems to surface (dropped packets, dropped connections, etc).
Buffers are bounded which, by definition, means they can be filled up. Once they are filled up then the same problems that were caused by a congested network without buffering would also be experienced in connections with buffering. It's hard to believe that back then no one noticed that buffers would only take so much data.
> Nagel was one of the first people to point out the problem with this.
Correct me if I'm wrong, but the problem that was pointed out was instead modes of failure that take place when networks are congested but buffers are still able to take more data. We're talking about failure modes that happen when the network is congested and buffers are not completely filled but they neither can flush their data nor drop packets/connections, thus it's a steady state characterized by a network that in theory is working, but induces high latency.
Also, limiting buffers is also not a fix for network congestion problems. It's a way to allow a failure mode (dropped packets) to happen much earlier than another failure mode (long queues with high latency).
Re: Queues don't fix overload (2014)
#133Anyone looking to build a practical solution that involves weighted-fair queueing for request prioritization and load shedding should check out - https://github.com/fluxninja/aperture
The overload problem is quite common in generative AI apps, necessitating a sophisticated approach. Even when using external models (e.g. by OpenAI), the developers have to deal with overloads in the form of service rate limits imposed by those providers. Here is a blog post that shares how Aperture helps manage OpenAI gpt-4 overload with WFQ scheduling - https://blog.fluxninja.com/blog/coderabbit-openai-rate-limit...
Re: Queues don't fix overload (2014)
#134Earlier quoted context omitted.
Additionally, most users actually are happy with "slow me down if I'm making too many requests". This is much simpler than recovering from errors correctly.
Which is why your test integration environment has to throw 429 and 5xx errors consistently from day one. The error handling paths are hard to retrofit but easy to do before deployment.
(What test environment?)
That will make you introduce error handling, but not necessary "correct" handling. "Retry after errors" is a great way to overload a system.
Re: Queues don't fix overload (2014)
#135FIFO queues do not fix overload. Fair queuing queues, though, can fix it if the problem is coming from a specific source.
I have a web site set up that way. An in-memory table in MySQL is used to handle queuing for a slow operation. The queuing system has some fairness. This works well enough that one site sent bogus requests for a month at a high rate, and it had no effect on actual users.
Fair queuing in SQL:
SELECT domain, requestor_ip_hash, rating_state_int, base_domain FROM ratingqueue AS rqueue
WHERE (rating_state_int = 3 OR rating_state_int = 4)
AND NOT EXISTS(SELECT * FROM ratingqueue
WHERE base_domain = rqueue.base_domain
AND (rating_state_int = 1 OR rating_state_int = 2))
ORDER BY rating_state_int, request_timestamp
LIMIT 1;Re: Queues don't fix overload (2014)
#136Earlier quoted context omitted.
See https://en.wikipedia.org/wiki/Bufferbloat I lived in Germany in 1999 and then the internet connection from Germany to the US would get overloaded during the day. At maybe 9am the latency would be then it would start dropping packets. I don't know if it was the intention but it was about as good as a ban on VoIP at preventing people from making international VoIP calls. Today there is more consciousness about the…
See RFC 970, "On Packet Switches With Infinite Storage" by John Nagle: https://datatracker.ietf.org/doc/html/rfc970 Back then (I was studying networking as an undergrad at the time, and interned with the Arpanet team) people really did think of network congestion as a buffer allocation problem, so the obvious solution was more buffering - i.e. adding queues. Nagel was one of the first people to point out the problem…
That was a long time ago. Yet we still have bufferbloat problems. Sigh.
Re: Queues don't fix overload (2014)
#137Earlier quoted context omitted.
See RFC 970, "On Packet Switches With Infinite Storage" by John Nagle: https://datatracker.ietf.org/doc/html/rfc970 Back then (I was studying networking as an undergrad at the time, and interned with the Arpanet team) people really did think of network congestion as a buffer allocation problem, so the obvious solution was more buffering - i.e. adding queues. Nagel was one of the first people to point out the problem…
> (...) people really did think of network congestion as a buffer allocation problem, so the obvious solution was more buffering - i.e. adding queues. I don't think people believed network congestion was a buffer allocation problem. I think people believed buffering was a way to mitigate congestion caused by a spike in traffic before allowing connection problems to surface (dropped packets, dropped connections, etc).…
> I don't think people believed network congestion was a buffer allocation problem.
Actually, they did, because everything in the early days had very small memory sizes. This was the 16-bit era.
Re: Queues don't fix overload (2014)
#138Earlier quoted context omitted.
See RFC 970, "On Packet Switches With Infinite Storage" by John Nagle: https://datatracker.ietf.org/doc/html/rfc970 Back then (I was studying networking as an undergrad at the time, and interned with the Arpanet team) people really did think of network congestion as a buffer allocation problem, so the obvious solution was more buffering - i.e. adding queues. Nagel was one of the first people to point out the problem…
Sometimes it is - TCP incast [1] in a fast LAN can be mostly alleviated by using switches with large buffers. Generally the higher throughput the bigger buffers you need unless having low latency is more important than low packet loss. The queue size is a tradeoff (as almost everything). [1] https://www.usenix.org/system/files/login/articles/chen12-06...
One of our customers bought a special switch with huge buffers, on the order of hundreds of megabytes per port.
It was a specialised SKU used only for dedicated backup networks. As in, networks that process only the traffic for disaster recovery backups. Latency on that type of network traffic is totally irrelevant, and the only thing that matters is achieving the maximum possible throughput — whatever the wire protocol allows.
That’s the one time I’ve seen exactly 10 Gbps sustained.
Re: Queues don't fix overload (2014)
#139What queues do is smooth out the mismatch between supply and demand. If the mismatch lasts long enough, the queue will overflow, and then you need to load shed (and you need to plan for what the least bad way of load shedding is). But queues do increase overall throughput, up to a point. If the demand was bursty on short timescales and you only allow a small queue to build before load-shedding, you may be wasting cap…
We have been building a platform called Aperture in the open-source trying to solve this very problem.
Our approach is to let the developer decide how long they want to wait in the queue using a timeout parameter. If timeout is hit, they may re-try with exponential backoff or load shed.
While in the queue, requests get prioritized based on a weighted fair queuing algorithm. If there is tiering in the app, there could be a policy that can allocate majority of the capacity to paid vs free customer tiers. But this allocation is not really static, if there is free capacity available in the system then the free customer tier can take all of it. This is just like how CPU time is allocated by Linux based on nice values, even low priority processes are allowed to take up all the CPU time when demand is low.
Apart from relative allocation across user tiers, Aperture's request scheduler can also ensure fairness across individual users within each tier to make sure no single user is hogging up all of the server capacity.
The demand and capacity is determined based on a request rate quota or the maximum number of in-flight requests.
Would love the community here to check us out on GitHub and provide feedback: https://github.com/fluxninja/aperture
Re: Queues don't fix overload (2014)
#140Earlier quoted context omitted.
See https://en.wikipedia.org/wiki/Bufferbloat I lived in Germany in 1999 and then the internet connection from Germany to the US would get overloaded during the day. At maybe 9am the latency would be then it would start dropping packets. I don't know if it was the intention but it was about as good as a ban on VoIP at preventing people from making international VoIP calls. Today there is more consciousness about the…
See RFC 970, "On Packet Switches With Infinite Storage" by John Nagle: https://datatracker.ietf.org/doc/html/rfc970 Back then (I was studying networking as an undergrad at the time, and interned with the Arpanet team) people really did think of network congestion as a buffer allocation problem, so the obvious solution was more buffering - i.e. adding queues. Nagel was one of the first people to point out the problem…
Ugh. WiFi signals aren't the best in my A/V cabinet, so I ran G.hn powerline to it. This works great 98% of the time, but occasionally there will be something that blocks traffic for a short period of time, and those things must have huge buffers.
If I'm e.g. watching Netflix when there is a hiccup, I see ping times of over a minute! I wrote a program that monitors ping times and reboots the G.hn adapters when they get too high and the problem mostly went away. I tried a couple different brands of adapters, but they are all obviously the same firmware.