Thank you Sam for another phenomenal post. This one was so so so good SOURCE encore.dev/blog/queueing FOLLOW SAM x.com/samwhoo Check out my Twitch, Twitter, Discord more at t3.gg S/O Ph4se0n3 for the awesome edit 🙏
@@yt-sh It isn't bug free, but I think it's reasonably close. You do actually see one bug in the video, I'll leave it as an exercise to the reader to find it. I spend a lot of time on these and test them extensively on a range of devices and browsers. I also have wonderful friends who help me test them, too. There are a few automated tests but nothing substantial.
We just finished learning priority queues and now working with weighted graphs and trees in school. A lot of people say you don't need to know these things, but they really are used in a lot of applications
You don't need to learn them all, you can definitely make a quick research before deciding the architecture of whatever you are working on. You should do that research anyway, since you can always find out some better solution. So I kinda get why people say that. But it's still highly preferable to at least know these stuff exist.
@@lazymass I agree 100%. I got lucky and was able to go back to college and study this stuff, which I am highly grateful for because there is so much information out there now its hard for me too stay focused and know what to study. It kind of keeps me structured. Lots of cool stuff out there 🙏
I've long been a defender of learning data structures and algorithms. I don't think you necessarily need to have implemented them, and you certainly don't need to be able to do it from memory like so many companies ask you to in interview, but knowing what tools you have available to you helps you solve problems better.
@@hellowill yep, common approach due to its simplicity and, in a way, is a form of priority queue (if slightly crude). If I was going to go back and change one thing about this post it’d be to include this because so many people keep bringing it up 😅
As you mentioned in passing, it would seem trivial to add an initial processing branch that filters "expired/timed-out" requests providing an early exit, and rapid dequeuing of these abandoned requests. Similarly, why isn't there a comparison and drop on enqueue, that prioritizes oldest entries, which at worst would restart the TTL for its queue slot. Yet another thought, dequeue capacity is the metric to gauge - how long does a request take to process? Once that time, multiplied by the depth has elapsed, the system has gone pear shaped and additional capacity should be allocated. I am reminded of all the priority queuing knobs at the network layer (including WRED and RED) that exist but are both largely unused on the "public" net, and used only in limited fashion on corporate networks, to accommodate RTP media traffic. It was telling that in the US and parts of Europe, ISPs strongly preferred simply adding capacity, rather than tinker with queuing. This was in large part because non-FIFO queues were hard to reason about, and turning the knobs only makes a difference on the edge cases - and when I say edge cases, think about the last person being shoved onto the subway by a train attendant in Tokyo. If you wanted a better "experience" then adding capacity, i.e. ability to handle/dequeue requests, is the only game in town. One more thought; Fry's Electronics utilized a single queue for its dozens of checkout counters - effectively a shared scalable processing queue. This was effectively human scale load balancing.
Mythbusters did an episode on using one long queue for multiple store checkouts, and the results were that average wait time was higher, but average satisfaction was also higher due to fairness.
I wrote a queuing system some years ago that allowed a mix of all of those strategies plus some other features. It was for data processing, though. I was converting a large, monolithic batch process (a couple hours to run) to be parallel and closer to realtime (sub second.)
What about if we have the priority queue but when a priority request arrives we would drop a low priority request from the back of the queue, then add it after the last priority request, that if the queue is not filled with priority requests. I think this may be better then the queues in this article.
In practice this queue management makes the most sense under load, and under load you probably don't want to be wasting cycles doing that sort of queue management. Simple usually trumps complex here.
@@julesjacobs1I’d love to see examples of it being done in the wild. I’ve no doubt people are doing it and there are workloads where it’s an appreciable optimisation, I just haven’t seen it myself.
@@samrosewho I'm pretty sure everyone who uses priority queues or even LIFO queues does it that way. The way it's implemented in this blog post is simply wrong.
16:40 "Let's be real a priority request should never take 18 seconds. Like imagine hitting a checkout button, and 18 seconds later you finally get to checkout. That's not acceptable" Surprisingly, this is the opposite of how I would feel. While I wouldn't like it, I'm much more forgiving of such delays on stuff like a checkout because at that point I'm committed. I've been trained to not try to refresh the page or hit the button again when doing the scary operations for fear of getting duplicate charges to my cards and what not, so I'm much more likely to actually see the request to completion. But if I'm getting such delays on the non-important stuff, like simply showing me product pages in the first place or on adding stuff to my cart, then I'm much more likely to bounce off the website entirely since I'm not committed to anything yet.
How about priority + RED, but LIFO for lowest priority? (Or, we could use LIFO within each priority bracket, especially if we have multiple priority levels.)
It was my friend Colin’s idea. He said “wouldn’t it be fun if all my dropped requests were lying at the bottom” like… 2 days before the article was scheduled to be published. Had to rush to learn Matter.js and get it in, too good an idea not to. 😁
Seems like a priority LIFO would be a smart choice. If the queue is full, you could also drop a normal request inside the queue if a priority request is coming in. Also instead of dropping new requests, maybe you could instead drop the oldest request in the queue, or have a 50/50 chance of dropping either.
I also thought about this but only once I was near the end of writing the post. Never did try it, but it’s hard to imagine it being bad isn’t it? Priority LIFO with RED.
@@samrosewho Is RED better than dropping requests already in the queue? I suppose it's better to fail fast rather than waiting a long time and still failing in the end.
@@Deemo_codesRU-vid auto translate video titles sometimes. I'm in France but I switched my system to English. I end up with french video titles translated in English sometimes
The thing I'm stuck on is "what is a priority request" at the moment. I guess because I was only thinking of a basic user collab app, there is no priority. I guess if I have moderators, they should have priority at least!
And then there is the elephant in the room: Don't actually process a disconnected or nearly timed-out request. Just drop it instead. This is a trivial optimization and should be the first thing to do. When trying to enque any request while the queue is full, replace the request waiting the longest with the new request. That way, it's still fair FIFO but when not everyone can be served, you still get a chance as the requests in front of you might be about to time out. You totally can scan the entire queue every time a request arrives to determine which one to drop. Worst you get is O(N). It's fine. Don't go all-in optimization fetish on request queues. The CPU shouldn't be the bottleneck in your load balancers.
Trade-offs, innit. I'd love to see more things dropping timed-out requests by default, not sure why they don't. Not quite as sure about scanning the queue for each new request, it wouldn't surprise me if that has an overall negative affect under load and only marginal benefit at lower scale.
Do people really click off when a page takes more than 5 seconds to load? For me, when doing things like shopping, during checkout the "brain timeout" is way above 30 seconds.
LIFO is not a good option for PUT requests (or any state update), since it makes them out of order. You can't afford to switch cancel and resume actions or updating same field with different data.
The network isn’t going to guarantee you an ordering for PUT requests even if you issue them in sequence, so you’d want to have another mechanism for those anyway (revision ID, deterministic conflict resolution, etc)
There's an error with Priority Queue demonstration and explanation. Priority queue will not let a checkout request with high priority drop because it will replace a low priority requests in the queue. That's how bounded PQ works by definition. It's impossible to lose a priority request if there's a low priority request in the queue. You can only lose a priority request if ALL requests in the queue are priority requests.
I actually hadn’t considered this, believe it or not. I’m struggling to find a formal definition of priority queues that mandates pushing out lower priority items when full but it’s logical and strikes me as good default behaviour. No one has called me out for it yet but this article desperately skirts around having to explain TCP global synchronisation and congestion control, the primary motivations for RED.
I have one problem with RED: If the queue is below like 5% full or something, instead of dropping 5% of requests, none should be dropped. Why always have a minimum level of failure when you probably would always be able to handle all of those requests?
I didn’t really talk about it but you could set whatever thresholds you want. I’d recommend simulating them first, this sort of stuff has a habit of not being intuitive. For the post, I kept it simple 😊
I guess this explains why all the balls at the bottom had stripes, because I kept forcing priority requests to drop just for funsies. Going into the hundreds kind of breaks it, though.
It should cap out at 100 and remove older requests to keep the CPU down. I did notice it can chug a bit when full on less powerful devices, which I wasn’t happy with but decided it was okay enough to ship.
wait, why are LIFOs better for most workloads? did I miss something? Seems like FIFOs are much better queues.. edit: ok it's because fewer 'timed out' but what scenario would that be the most important consideration in?
For HTTP requests it is, generally, better to reject a request than to make it wait a long time. It’s a broad general statement and there are going to be HTTP workloads where it’s not true, but I wish LIFO was the default everywhere instead of FIFO.
@@Holobrine There are certainly exceptions, but the worst case in FIFO if you've got no logic to drop timed out requests means you can get into a totally broken state that's hard to recover from. At least with LIFO the worst case still has you serving users.
@@samrosewhoI figured out how to put visualizations in my own local web page. I added s-multi-queues id="a" timeout="6" with FIFO, LIFO, FIRO (first in, random out), FIRFOLO (first in, randomly first or last out). I added s-wait-time-bar-graph id="ag" target="a". I added s-latency-percentile-toggle target="ag" options="50 75 90 95 99". I added s-timeouts-served-graph target="a". I only spam click yellow ball. Results are inconsistent between attempts. s-wait-time-bar-graph: 50th: FIFO 7.0s, LIFO 1.3s, FIRO 6.3s, FIRFOLO 4.7s 75th: FIFO 7.1s, LIFO 1.4s, FIRO 11.1s, FIRFOLO 14.1s 90th: FIFO 7.1s, LIFO 31.0s, FIRO 12.8s, FIRFOLO 14.5s 95th: FIFO 7.1s, LIFO 32.5s, FIRO 13.9s, FIRFOLO 17.0s 99th: FIFO 7.1s, LIFO 33.7s, FIRO 17.6s, FIRFOLO 18.1s s-timeouts-served-graph: FIFO 21 LIFO 4 FIRO 13 FIRFOLO 11
really interesting video, the thumbnail and title don't do it justice. it could benefit from a better title like: "Queues are more interesting than you think", "I bet you didn't know this about queues" and a proper thumbnail visualizing the priority conundrum. What about a thumbnail with the text "don't do this" and a red arrow pointing to the bottom end of the queue
Believe it or not this is one of my best performing thumbnails of recent lol. The vague nature of it stands out. Will likely play with it in the future
If you have a good reach, like Theo, you may cover the work of other specialized devs, like Sam, who have a good content. A mutually benefitial thing :)
@@samrosewho Certainly. The receiving end of a networking APIs can associate a timestamp for when a packet is received and dumped into a queue. The processing end of the API can immediately drop the packet if the timestamp is too old. It's literally the following: if (timeout < (currentTime - packetTimestamp)) continue; That's easily less than 4-8 clock cycles on any server produced in the last 7 years.
@@samrosewho YT refuses to post my reply. The summary is processing a timeout takes less than 4 clock cycles whilst processing a request could be in the order of hundreds or thousands of clock cycles depending on what the request is.
@@mohammedgoder Do you have a code example showing what you mean here? I tested a variety of setups and nothing I tested drops timed out requests by default.
@@samrosewho if (timeout < (currentTime - packetTimestamp)) continue; This is something that has to be done once the packet reaches userspace. My point was that larger FIFO queues are not going to cause older packets to timeout. What do you mean a variety of setups?
it's a nitpick, but pronunciation isn't defined by the letters in a word, but by how a consensus of people pronounce it, like all language. maybe Fee-Foe is a dialect, but I've only heard as F-eye-Foe for the last ~30 years.
Fantastic visualizations, but the article misses the mark quite a lot IMO. Two tings that do way more than anything in the examples here is: - Drop the the requests that are considered timed out. - Have a separete queue for priority requests and serve that queue first. The visualization is also misrepresenting what would happen in a real life scenario where you have multiple servers/workers processing requests in parallel. The scenarios where the server capacity is so under dimentioned is also very extreme and not realistic at all.
Dropping timed out requests would make a big difference, you’re not wrong. Here’s a fun thought experiment: how does 2 queues differ from a single priority queue in practice? I’m also interested in how multiple servers would make a meaningful difference to the post. Abstractly requests get taken off the queue at some rate and the number of consumers is mostly irrelevant. The only relevance I could think of is if I were modelling queues at both the load balancer and server level, which does get a bit hairy. Was beyond the scope of what I wanted to talk about though.
@@samrosewho Two queues would make a lot of difference. Mainly because you can balance the how many jobs that are popped from each queue. You can for example take 3 jobs from the priority queue for every job you take from the normal queue, and thus, the normal queue will not starve out completely. But the biggest problem is that the whole setup is very unrealistic. In pretty much any a system with high thouput you measure the wait time for each queue(how long it takes between a job is added to the queue and then it is handled). When the wait time exceeds some threshold, you just spin up more workers for that queue. Then you will be fine with a FIFO-queue and all this would be pretty much irrelevant.
I am so not the target demographic to tell "waiting longer than 5 seconds makes users leave the page" - I am sorry but I am so used to the internet being spotty at times I will always wait as long as I have to for a page to load. What arrogance leads people to quit interacting with something they actively chose to interact with if they need to wait a bit? Screw statistics and user surveys, if a user quits when they have to wait, I do not want to serve them.
I know PHP by default stops execution if the client disconnects in the middle, I'd assume that would also apply if the client has disconnected before the script even starts but I never tested that
@@ILsupereroe67 That would make sense to me as PHP is typically writing the response back to the user during execution. When a client disconnects it sends a TCP FIN and gets an ACK back from the server (this happens when you close a tab in your browser or kill curl on the CLI), from that point on any data sent to the client will result in the client sending an RST back to the server and I suspect the server would stop sending the response. I think this likely happens in most of the ones I tested but the tests I did had a bunch of processing followed by a short response. Until you start trying to write to the broken connection, you'll keep processing. I'd be surprised to see PHP behaving differently to this. If you have time, I'd love to see a small project displaying otherwise.
