5 ms·
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!
by Twisol 5y ago
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 https://en.wikipedia.org/wiki/Compare-and-swap
[1] https://en.wikipedia.org/wiki/Consensus_(computer_science)#Consensus_number https://en.wikipedia.org/wiki/Consensus_(computer_science)#C...
- chx 5y agoYes, 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 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.
- abhishekjha 5y agoI 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.
- bryanrasmussen 5y agobased on experience arriving very last minute to flight, nobody has problem with letting two people book the same seat.
- kyleee 5y agoLet the check-in attendant handle it; that's what I call a no-code solution! You're hired
- Tostino 5y agoThat's solid middle management thinking right there!
- lootsauce 5y agoReminds me of Starbucks does not use two phase commit. https://news.ycombinator.com/item?id=6229004 https://news.ycombinator.com/item?id=6229004
- abhishekjha 5y agoWouldn’t the attendant be in trouble if two people at the gate start fighting for the same window seat as printed on their ticket?
- chx 5y agommmm 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-protection/bumping-oversales https://www.transportation.gov/individuals/aviation-consumer...
- mianos 5y agoThey obviously don't have the transaction semantics worked out. I have been at the gate and the person in front of me had the same seat number. They read it out. When I presented my pass the girl politely took my ticket and printed another one. If the person was not right in front of me I would never have known why. It is not unusual.
- bryanrasmussen 5y ago
- agf 5y agoI think this being a good answer hinges on the resulting user experience. If one person spends several minutes going through the process of putting in their payment and other info only to be told you don't have a ticket, they're going to be pissed. So you need a good answer on how to avoid that experience, however you implement the locking. Saying this as someone who has been on both sides of that interview question, and also evaluated performance in it as a hiring manager.
- lstamour 5y agoSend bookings to the database early, with an expiry time and a counter visible on the screen? Thing is, because purchasing is often shared across third-parties, even then you can’t guarantee that you’ll have the reservation until it’s paid and entered into the shared booking backend… unless the third party backend has a locking mechanism, at which point you’re probably not using your own Postgres to do this, but their mainframe instead.
- spockz 5y agoIs there any other solution other than going full STM on this?
- mathfailure 5y agoYes a simple SCRM will do.
- abhishekjha 5y agoWhat is SCRM?
- abhishekjha 5y agoSo what do you propose here? I see that stackoverflow mentions some preemptive locking for a seat in cache for a few minutes. During that time the seat is taken out of the pool for potential booking. If the time lapses without the seat getting booked then the seat returns to the pool. This avoids going to the DB and see who wins.
- kccqzy 5y agoI had a similar question asked of me in an interview. The interviewer was also surprised by my solution of letting the database decide the winner.
- abhishekjha 5y agoWhat exactly is the right answer here?
- phamilton 5y agoThe "what actually happens" answer is often "let them both book successfully and then rebook the person with lower loyalty status".
- halifaxbeard 5y agoPostgres’s transactional semantics are really useful when building a queue, because of how it interacts with the various pieces. Connection 1 LISTEN 'job-updates'; Connection 2 BEGIN; INSERT INTO jobs ('a-uuid', …); SELECT PG_NOTIFY('job-update', 'json blob containing uuid and state change info'); COMMIT; Connection 3 (used when Connection 1 is notified) BEGIN; SELECT id, … FROM jobs WHERE id = 'a-uuid' FOR UPDATE SKIP LOCKED; UPDATE 'jobs' SET state = 'step1_completed' WHERE is = 'a-uuid'; SELECT PG_NOTIFY('job-update', 'json blob containing uuid and state change info'); -- do the thing here: computation, calling external API, etc. If it fails then rollback. COMMIT; Because notify has transactional semantics, the notify only goes out at transaction commit time. You want to use a dedicated connection for the notify. The only downsides I immediately think of are you will have every worker contending to lock that row, and you’ll need to write periodic jobs to cleanup/retry failures.