31: Distributed Priority Queue | Systems Design Interview Questions With Ex-Google SWE

[@thunderzeus8706]

Thanks for the great video Jordan! Here are some questions to help me understand better: 1). Is the following understanding correct: When a task is consumed by a consumer, it removes the task from the heap and stores that task to some pending storage. When it gets the ACK that the task is done, it removes the task. When it expires or gets a failure message from the consumer, it repopulates the task into the queue of the same partition. 2). I think we need some not-that-frequent heartbeat between the partition server and the consumer. Say the tasks are some time-consuming batch jobs, we cannot always wait for the consumer to report the task has succeeded or not. In such scenario, a "partial failure" is a headache say the consumer is down, but the batch job task might still be running. We have to take care of the exact-once-processing aspect too. What is your favorite way to tackle that?

[@jordanhasnolife5163]

1) Yes, agree 2) You can either use a heartbeat or some sort of time out. Not sure what you mean by "a headache say the consumer is down, but the batch job task might still be running", but typically you want either a) your jobs to be idempotent b) use some external store or idempotency key to determine whether you've already run a job, could even be a distributed lock if need be.

[@mayezabdul4342]

Awesome video, been binging your playlist as someone who is new to system design and loving the breadth and depth of knowledge and application of it provided here. I did have one question though and please correct me if I am wrong. I noticed in your older system design questions playlist, it seemed to be more in line with grokking, where the video is broken off into more concrete sections and having "API Design" and such but on the other hand this 2.0 questions playlist is more in depth but more freeflowing. In an actual interview would it be more in line with how your initial playlist was or this 2.0 playlist? Also, my goal of going through this playlist is to build up my "instincts" when it comes to system design atleast to a respectable level and so in your opinion would watching your videos while taking notes be enough to do that to where if I had a new problem not covered on the channel yet or in an interview it would be enough or one would have to do practice outside of these videos? Not sure if that was clear enough on my part but interested to hear your thoughts and once again appreciate the time you take for this, real help!!!

[@jordanhasnolife5163]

Yeah I think that this playlist is probably more focused on a complete solution and edge cases rather than its presentation in a 30-45 minute timeframe. In an interview itself you would probably want to organize by API and data schema etc etc, but I do think that if you're just starting out it could make more sense to watch this one!

[@mayezabdul4342]

​@@jordanhasnolife5163 so then is it safe to presume that the older questions playlist is better if I'm attempting to brush up for a system design interview in the future and this playlist is meant for a more complete understanding or this current playlist on its own accomplishes that?

[@jordanhasnolife5163]

@@mayezabdul4342 I guess that would be in the eye of the viewer - personally when I need to remember what I said I tend to just watch like the last 3 mins of the video, but perhaps what you proposed might work better for you!

[@k.alipardhan6957]

the description 😂

[@unkgoku9]

Hey Jordan Your videos are great. Please keep uploading. Just curious, what is this drawing tool you use?

[@jordanhasnolife5163]

It's an iPad and an apple pencil

[@monk_learn]

You are doing great work man. A slight calculation error on 8:25 I presume, isn't (16bits * 1 billion )16 billion bits approximately 1.86 GB?

[@jordanhasnolife5163]

yeah I think someone else pointed this one out, nice catch

[@manojgoyal-y3k]

keeping a in-memory heap for priority queue may be not durable when node make crash recovery. what about if we make index on priority column of the table in sql and it will be stored in disk memory itself?

[@jordanhasnolife5163]

I think your solution works. I also think a normal write ahead log with background thread checkpointing may work a bit better.

[@s09021994]

Hi Jordan. The videos are amazing. Thank you. A suggestion - can you please post a link to youtube video with your substack post if possible? I know I can always open youtube in a new tab and search, but it will save 3 seconds every time I go through your notes, which I would rather spend trying to search for your feet pics

[@jordanhasnolife5163]

I'll get to it eventually, but for now less feet for you I guess

[@lalasmith2137]

Hey Jordan and congrats on the milestone :) where does the in memory heap lives? is it in the DB, is it possible? it's just i didn't see in the final design so i wanted to make sure and ask

[@jordanhasnolife5163]

I believe certain databases support sorted set in memory indexes - otherwise you'd have to modify an existing db implementation :)

[@lalasmith2137]

@@jordanhasnolife5163 thank you for your time and your answer as always :)

[@alphabeta644]

Hello Jordan, Question regarding writing to consensus/raft from load balancer (near @18:50). I remember from one of your previous videos about consensus/raft that it is very slow, but we take the hit for the most critical pieces of information like ip addresses of server, hash ranges, configurations. Coming back to current video, the distributed priority queue is expected to take billions of items / day (@03:37), do you think that consensus/raft usage is alright for this scale? Why would a simpler single leader with a standby not work for this case?

[@jordanhasnolife5163]

It would - but you may lose a couple messages if the leader goes down. In reality, who cares, so I agree we should just use that (see Kafka for example).

[@harman654321]

couldnt you use redis sorted set for this for the priorities and point to data on disk or somewhere. and then to enquee, add to the set. to deque, write a redis key to lock the element (Redis incr for distributed lock with ttl), then process and remove the element from sorted set

[@jordanhasnolife5163]

Probably

[@ika9095-o2s]

Could we build everything on top of Postgres with additional index on priority? I'd expect a service then run SELECT FOR UPDATE * from tasks ORDER BY priority ASC LIMIT 1 SKIPPED LOCKED (10, 20 depending on the clients request). We can update a state of a task as RUNNING and have a separate process that makes RUNNING task available again after some timeout. It requires much more DB writes/reads than the min heap in memory but doesn't need PAXOS. Thx

[@jordanhasnolife5163]

Yes you can do this, FB uses MySQL. I do believe you'd still want paxos in a replication group to ensure writes aren't dropped after hitting your single leader, but that being said you can forfeit it in exchange for imperfect durability.

[@NBetweenStations]

Thanks Jordan! I have a couple questions for you. 1. If there are multiple consumers long polling the same partitions, do they need to somehow mark the next highest priority item as “pending” so the other consumer doesn’t also read it? How does long polling help here?

[@jordanhasnolife5163]

1) Yes you need to mark it as pending, then the DB knows not to reassign it to another consumer until it is either completed or timed out 2) long polling only helps in the case where a node is responsible for handling events from multiple partitions

[@iknowinfinity]

Hey Jordan, how will you modify the priorities of the existing elements with the way that you have partitioned the db? It seems like we will have to search through all the partitions to find the element and then update its priority!

[@jordanhasnolife5163]

Rather than doing load balancing, you can just hash some aspect of the data and send it accordingly. That way to modify a priority you can go find the hash of it and get to the proper node.

[@fallencheeto4762]

Great video, Facebook engineering blog is indeed interesting 😅

[@shuozhang236]

great video, could you please elaborate why using priority as partition key will end up locking in that one node ? thanks

[@jordanhasnolife5163]

It's not necessarily that it would be more locking, but every consumer wants to read items with high priority So the partition that holds the highest priority items will get a ton of read load

[@shuozhang236]

@@jordanhasnolife5163 make sense thanks for explaining

[@maxvettel7337]

Next video - distributed stack 😅

[@siddharthsingh7281]

Is that even a thing

[@fallencheeto4762]

Maybe there is a use case somewhere for this 😂

[@jordanhasnolife5163]

Lmao I don't believe this has any use case, but that one is probably going in memory haha

[@maxvettel7337]

@@jordanhasnolife5163 who knows, maybe there could be any exotic systems like cashback service or price drop tracker

[@ameddin73]

If you had an only once requirement, how would you prevent 2 consumers from processing the same event at the same time? The replication scheme you suggested doesn't lock rows across multiple records on read, does it?

[@vietnguyenquoc4948]

He said it at about 03:15 I in the video and he did use locking on the consumers's side at 19:05

[@jordanhasnolife5163]

Nope - no locks across nodes fortunately. You need to lock a node when you dequeue it, but if your consumer goes down and comes back up another consumer may have also processed that event due to a timeout. The only way to ensure "exactly once" requirement is idempotency of consumer handlers.

[@ameddin73]

Damn I'm always so focused on my impotence I forget about idempotency!

[@dirty-kebab]

Hey, why Ex? I just started watching your earlier videos.

[@jordanhasnolife5163]

kzbin.info/www/bejne/qZrUhXyGgryarJI&ab_channel=Jordanhasnolife This should sum it up

[@2devanshi]

Can you create a design video on insurance marketplace system and online course platform system ( teacher can register courses, students can subscribe, how do you get users on platform etc)

[@jordanhasnolife5163]

How is this different than any other e-commerce site?

[@samiransari3361]

I believe it’s 2 GB in memory. 16 bits = 2 bytes. 2 bytes x 1 billion = 2 GB.

[@jordanhasnolife5163]

I think I made a typo on the iPad, longs are 64 bits (8bytes), so should be 16gb

[@aritrasen88]

​@@jordanhasnolife5163 "8 bits to store the pointer" is throwing people off. You need 30 bits to be able to refer to 1 billion distinct ids. Same goes for priority. Round them up to 32 bits (standard size of ints on most modern language). So total of 64 bits (8 bytes) * 1 billion ( 2^30) will get you 1 billion id + priority -> 8 GB of memory.

[@jordanhasnolife5163]

@@aritrasen88 yep I said bits when I meant bytes

[@romangavrilovich8453]

@@jordanhasnolife5163 it would be great to pin a message to explain such stuff, because I also had a question about bits amount, WDYT? :)

[@jordanhasnolife5163]

@@romangavrilovich8453 While I agree that pinning would be nice, I do like pinning people's messages when I acknowledge them as a way to tell myself that I have. I need a double pin lmao

[@emenikeanigbogu9368]

you should have like a coffee meetup!!

[@jordanhasnolife5163]

Haha perhaps so, though admittedly you guys probably don't want to meet me in person, as I fart a lot

[@dirty-kebab]

​@@jordanhasnolife5163 Jordan watches too much JREG for sure, post-meta irony mf 🏋️

[@marcosoliveira1538]

Great video 😊