zlacker

>>hyzyla+(OP)
You really don't need anything fancy to implement a queue using SQL. You need a table with a primary id and a "status" field. An "expired" field can be used instead of the "status". We used the latter because it allows easy retries.

1. SELECT item_id WHERE expire = 0. If this is empty, no items are available.

2. UPDATE SET expire = some_future_time WHERE item_id = $selected_item_id AND expire = 0. Then check whether UPDATE affected any rows. If it did, item_id is yours. If not, loop. If the database has a sane optimizer it'll note at most one document needs locking as the primary id is given.

All this needs is a very weak property: document level atomic UPDATE which can return whether it changed anything. (How weak? MongoDB could do that in 2009.)

Source code at https://git.drupalcode.org/project/drupal/-/blob/9.2.x/core/... (We cooked this up for Drupal in 2009 but I am reasonably sure we didn't invent anything new.)

Of course, this is not the fastest job queue there is but it is quite often good enough.

>>_ugfj+z2
For other readers, the `UPDATE` step is an exact anlogue of the "compare-and-set" atomic instruction [0]. It's really cool to see how you've realized it in SQL!

As a capability, compare-and-swap has an infinite consensus number [1], meaning it's sufficient to implement wait-free consensus algorithms with an arbitrary number of participants. That makes it a perfect fit for managing a scalable pool of workers that need to coordinate on consuming from a queue!

[0] https://en.wikipedia.org/wiki/Compare-and-swap

[1] https://en.wikipedia.org/wiki/Consensus_(computer_science)#C...

>>Twisol+Xa
Yes, the UPDATE command is the exact equivalent of LOCK CMPXCHG (the SELECT can be seen as computing the memory address). So the discussion about that in the comments of https://stackoverflow.com/a/59022356/308851 totally applies: if two queue runner threads pick the same item exactly one will succeed so it can't happen both tries and tries the same item. So there's no busy wait (reminder: a busy wait is where it does nothing just tests a condition), it just goes over every candidate until one succeeds.

>>chx+hd
I have been asked this question in interviews for how to prevent two people from booking the same seat. Interviewers don’t seem to be satisfied by the answer that I will let the query go to the database and see who ends up booking. They want some advanced locking mechanism using redis. Redis does serialize queries using lua thus avoiding two people from booking the same seat.

>>abhish+2G
based on experience arriving very last minute to flight, nobody has problem with letting two people book the same seat.

>>bryanr+6K
mmmm no

They allow overbooking the flight but you can't book the same seat twice.

Overbooking can make financial sense -- even if you need to hand a little compensation from time to time it's still better than flying with empty seats. Of course it sucks big time for the travelers especially if there are no volunteers. IDB is miserable. https://www.transportation.gov/individuals/aviation-consumer...

>>chx+ne1
>They allow overbooking the flight but you can't book the same seat twice.

ok, but how do you overbook a flight without booking at least one of the seats twice?

>>bryanr+AB1
You don't assign all the seats up front. Some are marked to be assigned at the gate.

>>Jailbi+lJ1
Well then the problem moves a little to the left. If there are x seats to be booked up front and y seats to be allocated later. How many times can each of the x seats be booked and how do you prevent that n and n+1 over the limit booking for some seat? The problem is still there.

>>abhish+mH2
Airlines have been data mining for a very, very long time now and have a reasonably guess of the ratio of people booking vs showing up at the gate to fly. So you set your buckets to oversell by that much and assign seats later. If more people show up than expected than you throw them a voucher to go away. Hopefully enough will.

Sometimes it doesn't work out and that's when airlines bleed. I was flying home one day from some US city (was it Denver? the years and cities blend together) when a Drupal conference and some major sports thing ended the same day and the airport was a total gong show. United first offered a paltry 120 USD but when they raised to 400 USD to go home the next day instead my hand went up -- and I was such a greenhorn I didn't know they will pay for the hotel, too. A buddy pocketed no less than 1200 USD from Delta.