A Video About Queues

Рет қаралды 52,669

Ай бұрын

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 🙏

Пікірлер: 154

@spageen Ай бұрын

I'll save this video for later

@amsyarasyiq 17 күн бұрын

video queued

@davidsiewert8649 Ай бұрын

We don't have to care about dropping requests, because our app with only

@saelorasinanardiel8983 27 күн бұрын

three days later: "So our little app went viral"

@abhisheknavgan6829 Ай бұрын

this was the first time I had fun reading and understanding a blog post.

@samrosewho Ай бұрын

❤

@yt-sh Ай бұрын

@@samrosewho it must have been tough to make that article bug free, how did you do it

@samrosewho Ай бұрын

@@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.

@danielgilleland8611 Ай бұрын

"... unless it was Jira and it was my job..." 🤣

@rashim Ай бұрын

Main thing I am taking away from this video... Sam is a FKKING LEGEND !!!

@kenscode Ай бұрын

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

@lazymass Ай бұрын

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.

@kenscode Ай бұрын

@@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 🙏

@samrosewho Ай бұрын

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 Ай бұрын

i've yet to see a priority queue used in system design... we just have a high priority queue and normal queue.

@samrosewho Ай бұрын

@@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 😅

@tuna5618 Ай бұрын

this article was incredible

@FryGuy1013 Ай бұрын

This reminded me a lot of the visualizations on the Nicky Case blog (particularly, the "build a better ballot" one)

@samrosewho Ай бұрын

I’m a big Nicky Case fan 😁

@roganl Ай бұрын

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.

@samrosewho Ай бұрын

What do you mean by "why isn't there a comparison and drop on enqueue"? And what do you mean by "dequeue capacity"?

@ShinyVeggie Ай бұрын

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.

@mduvigneaud Ай бұрын

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.)

@sebs4591 Ай бұрын

The amount of care and polish Sam puts into his posts cannot be understated. Really solid stuff!

@thisaintmyrealname1 Ай бұрын

absolutely loved this, and thank you for introducing me to Sam! all blogs and web based learning material should be as interactive as this!!

@samrosewho Ай бұрын

Nice to meet you 😊

@cherubin7th Ай бұрын

I wonder about using multiple queues in parallel? Like the priority queue on 2B2T.

@samrosewho Ай бұрын

Yeah, not an uncommon strategy. I didn't include it because it would have been a bit more difficult to visualise alongside the single queues 😅

@NickHamilton88 Ай бұрын

Queue the video

@samcalder6946 Ай бұрын

Queueing is Britain's national sport!

@samrosewho Ай бұрын

I’m glad someone said it. This article is a point of national pride.

@Winnetou17 Ай бұрын

Theo: Check out Sam! Me: Sam who ? Theo: Yeah!

@Paul-di9xv Ай бұрын

I don't think FIFO is from the engineering world though, I think it's originally used as an inventory method in retail for example

@ufffd 22 күн бұрын

yep, it was required knowledge on the food handlers test at least a decade ago

@IdoAloni123 Ай бұрын

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.

@samrosewho Ай бұрын

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.

@julesjacobs1 29 күн бұрын

@@samrosewho This type of queue management literally takes nanoseconds. Spending a few cycles is absolutely worth it.

@samrosewho 29 күн бұрын

@@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.

@julesjacobs1 29 күн бұрын

@@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.

@samrosewho 29 күн бұрын

@@julesjacobs1entirely possible. Dropping at the other end of the LIFO queue does seem objectively better. I tried, I guess 😅

@aghileslounis Ай бұрын

What an incredible article!

@anwiseru9064 Ай бұрын

omg the end of the article was so clever

@samrosewho Ай бұрын

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. 😁

@codeChuck Ай бұрын

Those interactive examples for teaching stuff - they are GOLDeN :) Good work! Dropped requests - very fun :)

@ShinyVeggie Ай бұрын

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.

@samrosewho Ай бұрын

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.

@ShinyVeggie Ай бұрын

@@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.

@sarjannarwan6896 Ай бұрын

Would be an interesting addition to account for request processing time. E.g. A ping vs something that does a bunch of database stuff / processing.

@JS-fd5oh Ай бұрын

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.

@samrosewho Ай бұрын

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.

@Primalmoon 29 күн бұрын

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.

@ivanmaglica264 27 күн бұрын

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.

@samrosewho 18 күн бұрын

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)

@mcgruff0972 Ай бұрын

FIFO was a term way before engineering. Great vid though!

@JJCUBER Ай бұрын

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.)

@Kane0123 Ай бұрын

Had to go and search for the other video to make sure I wasn't going crazy... loving Sam Rose's content

@samrosewho Ай бұрын

Thank you ❤

@FlorianEbeling 26 күн бұрын

great post, great discussion of it

@Aditya_Vyas Ай бұрын

I'll watch it now

@NithinJune 28 күн бұрын

british person’s dream

@tangentfox4677 27 күн бұрын

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!

@eth3792 27 күн бұрын

Fun drinking game: take a shot every time he geeks out over the visualizations (no but seriously they are incredible)

@samrosewho 18 күн бұрын

Thank you ❤

@sayemprodhanananta144 Ай бұрын

An engineer became bored, so he became a doctor 🙃

@abhisheknavgan6829 Ай бұрын

Your videos are getting high priority in my subscriptions nowadays 😂😂 (dropping other videos)

@Oktokolo Ай бұрын

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.

@samrosewho Ай бұрын

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.

@DMZT_dhruv Ай бұрын

I thought you started data structures lol

@ryanmatthews5771 Ай бұрын

Was FIFO really a tech thing first? I learned about it for the first time prepping food for freebirds (restaurant)

@RyanAustinx98 Ай бұрын

No, it’s been used in asset management and inventory management long before.

@ryanmatthews5771 Ай бұрын

@@RyanAustinx98 yeah that’s kinda what I expected

@tangentfox4677 27 күн бұрын

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?

@samrosewho 18 күн бұрын

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 😊

@JimmyNguyen-h6o Ай бұрын

doesnt apache kafka handle queues under the hood? // im still learning more about this stuff.

@chad_giga6934 Ай бұрын

Really nice video

@SecretMoose Ай бұрын

0:05 speak for yourself, I’m British. 😂

@samrosewho Ай бұрын

Same :)

@nezu_cc 24 күн бұрын

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.

@drachebrume3257 Ай бұрын

Video’s title brings a different vibe in French

@Deemo_codes Ай бұрын

What?

@tipeon Ай бұрын

Ah ah! You're telling so much about yourself in this single comment. Don't forget to delete your browser history 😅

@MrDadidou Ай бұрын

@@Deemo_codesKZfaq 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

@sub-harmonik Ай бұрын

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?

@samrosewho Ай бұрын

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 Ай бұрын

@@samrosewhoTbh yeah, an explicit “nope try again” is better than leaving you hanging

@samrosewho Ай бұрын

@@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.

@oaklyfoundation Ай бұрын

This post is amazing.

@samrosewho 29 күн бұрын

Thank you 🙏

@smoked-old-fashioned-hh7lo Ай бұрын

your video quality has increased in the last few videos. when you're not constantly shilling vercel and react it's much better.

@anon_y_mousse Ай бұрын

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.

@samrosewho Ай бұрын

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.

@anon_y_mousse Ай бұрын

@@samrosewho You don't have to tell me, I already know I've got a potato. Cool interactive article though.

@fev4 Ай бұрын

damn, this is an insta-save article and video

@pawan29121991 28 күн бұрын

I have seen this nice interactive one

@codeChuck Ай бұрын

Drop the timed out requests from the queue, do let them go to the server.

@pramudyaindra Ай бұрын

finnaly, a video thumbnail without face

@mihirphadnis2 Ай бұрын

Caught in time..

@thebahrimedia Ай бұрын

Queues

@JohnMullee 12 күн бұрын

watch queing video? = 'at least once'

@Pekz00r Ай бұрын

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.

@samrosewho Ай бұрын

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.

@Pekz00r Ай бұрын

@@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.

@socialvideoplaza Ай бұрын

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

@t3dotgg Ай бұрын

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

@JagdeepSinghKalsi Ай бұрын

ThE pHp ExPeRiEnCe... Bah! Try sending many(hundreds or thousands or more) requests to a PHP server, and share the percentage of dropped requests.

@RandomGeometryDashStuff Ай бұрын

07:58 what if random request processed?

@samrosewho Ай бұрын

What do you mean?

@RandomGeometryDashStuff Ай бұрын

@@samrosewhoprocess random item from queue instead of first or last

@samrosewho Ай бұрын

@@RandomGeometryDashStuff ahh hm, not sure. I've never seriously considered it. What problem would it solve?

@RandomGeometryDashStuff Ай бұрын

@@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

@TokyoXtreme Ай бұрын

People lining up to watch this video.

@mohammedgoder Ай бұрын

This article grossly misrepresents how long timeout take to process in proportion to requests.

@samrosewho Ай бұрын

Could you go into more detail here? I'm not sure what you mean.

@mohammedgoder Ай бұрын

@@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.

@mohammedgoder Ай бұрын

@@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.

@samrosewho Ай бұрын

@@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.

@mohammedgoder Ай бұрын

@@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?

@jeroenw9853 Ай бұрын

Hi Twitch!

@willcoder Ай бұрын

FIFO is pronounced "F-eye Foe" rhyming with High-Low. And rhymes with LIFO.

@ItsUhMeIbraheem Ай бұрын

The way everyone around me has always pronounced it is "Fee Foo" and "Leaf Ooh"

@mathijsriezebos Ай бұрын

You're both wrong. It's _f_irst _i_n _f_irst _ou_t, so it should be pronounced "fì-fow" rhyming with "give now". /s

@willcoder Ай бұрын

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.

@user-xs2yl4gd7n Ай бұрын

Open for the listen queue spelling on english 🎉 thank you!

@andrewkosenko2757 28 күн бұрын

For the Americans out there: Lines Thank me later 😂

@codeChuck Ай бұрын

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 :)

@cerulity32k Ай бұрын

kwewes

@Salbeira Ай бұрын

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.

@josedallasta Ай бұрын

14:15 bruh really

@ProSureStrings Ай бұрын

@ILsupereroe67 Ай бұрын

What http servers are so stupid as to serve a request from a client that has already disconnected?

@samrosewho Ай бұрын

I tested quite a few and they all processed requests from clients that had disconnected. I'd love to see examples where that's not true.

@ILsupereroe67 Ай бұрын

@@samrosewho Is Apache one of those you tested? 🤔

@samrosewho Ай бұрын

@@ILsupereroe67 No.

@ILsupereroe67 Ай бұрын

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

@samrosewho Ай бұрын

@@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.