19 ms·
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 ins
by chx 5y ago
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/lib/Drupal/Core/Queue/DatabaseQueue.php#L116 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.
- habibur 5y agoRight. And this article reminds me of people trying to use a SQL database like a filesystem. "Lock file before update otherwise it will get overwritten". Don't use record lock as like it's an attribute of a row. Add a column on the table called "status" and use it.
- 0x0nyandesu 5y agoI recently switched from rolling my own table to SQS. The main issue is making a job queue dispatcher and runner which most people aren't familiar with.
- edwinyzh 5y agoGreat! So I learned this technique. But one thing that's not clear to me - how a "expired" datetime field can allow easy retries? Anyone give me an example? Thanks!
- chx 5y agoSuccessful items are deleted from the queue before they expire. So an item with expired > current time needs to be retried because it failed processing. So, a cronjob resets these to expire 0 and the next worker can pick them up.
- edwinyzh 5y agoThanks for the explanation and time is needed in order to digest it... I guess one might start with the simple "status" field approach ;)
- DangitBobby 5y agoThe status doesn't help if the worker died during processing. If you've got something that's been "in progress" for 20 minutes of a job that takes 2, your job might not be getting done. That's what expired is for.
- edwinyzh 5y agoI see now! So the 'expired' field is for checking died/incompleted workers.
- layoutIfNeeded 5y agoDoesn’t sound like a robust solution. What if the job takes longer than your estimated expire time? Does the worker keep updating the expiry date on a background thread while doing the processing?
- cbo100 5y agoSame for any queuing system. You need to set the expiry time long enough for the expected task duration. In SQS, for example, you use a visibility timeout set high enough that you will have time to finish the job and delete the message before SQS hand it off to another reader. You won’t always finish in time though, so ideally jobs are idempotent.
- 5y ago
- cerved 5y agono you don't but it's a lot better to do an atomic select/update IMHO. Basically you have status = 0,1,2 for queued, processing, done. You have a filtering CTE that returns the queued rows, sort by id and update status = status +1 of the top one. You can even get fancy and disallow updates on the status column for other users to make it immutable. I've done this in SQL server in a very similar way to as explained in the post
- Twisol 5y agoFor 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.
- 5y ago
- kalleboo 5y agoThe way we did it (in MYSQL) was "UPDATE tasks SET processid=<unique id for the queue consumer task> WHERE processid IS NULL ORDER BY taskid LIMIT 1" and then look for processid to find your task. I guess the LIMIT on UPDATE might be an mysql extension? Then if your task crashes or dies you can look for invalid processids and do cleanup
- chx 5y agoOur initial did that too but generating a unique was removed soon after as had expire in there anyways for retries as I mentioned and that is enough.
- hughrr 5y agoOh please stop using databases as queues. I spent a disproportionate amount of time in the last 20 years undoing that decision. It doesn’t scale at all well.
- ngrilly 5y agoLook at SKIP LOCKED in PostgreSQL and MySQL.
- hughrr 5y agoIt’s not that. It usually ends up in the same storage engine as the main business functionality which leads to IO contention. The some sick and twisted bastard does a join to it from somewhere abhorrent which means it requires some serious heavy lifting to fix it. This is unfortunately the status quo in the slightly less ideal universe than “seemed like a good idea at the time” Use SQS or RabbitMQ or something. Edit: Also if you’re using something SQL for queues you’re going to have to build out your monitoring stack yourself based on your implementation rather than suck up a metrics endpoint with queue stats or pull from cloudwatch.
- jbverschoor 5y agoI dunno. If it’s usually the same problem, it should be easy to identify and fix. Unless we’re talking about a high load, there should be no problem doing this.
- hughrr 5y agoIt’s only the same problem until someone dumps 25,000 entries in your queue.
- kasey_junk 5y agoI’ve seen all manner of hokey queue implementations in sql going back about 20 years and all of them could handle 25k enqueue bursts. That wasn’t a problem for a Sybase database on a commodity host circa 2000. I think if I were going to argue against using DBs as queues it would be around: heavy parallel write use cases, latency concerns of both reads/writes and scaling to millions of events per second. If you don’t have those concerns using a properly normalized and protected schema (which you are doing anyway right? Cause if not you are already shooting your toes off) for queues goes a very long way and removes a very big operational burden and tons of failure modes.
- hardwaresofton 5y agoDon't forget SKIP LOCKED[0]! [0]: https://blog.2ndquadrant.com/what-is-select-skip-locked-for-in-postgresql-9-5/ https://blog.2ndquadrant.com/what-is-select-skip-locked-for-...
- masklinn 5y ago`FOR UPDATE` is also a good idea.
- Koffiepoeder 5y agoThe article mentions that.. The comment by chx was rather a more generalized idea for implementing a queue that is not database-specific.
- pjmlp 5y agoYeah, most of the NoSQL solutions boil down to not learning how powerful SQL and its programming extensions are.
- rad_gruchalski 5y agoHow so?
- kasey_junk 5y agoThat’s a bit of rewriting history. NoSql, particularly document style stores came about at least as much as a reaction to the overweight policies & orms the sql world has made rampant at the time. You’d be trying to store a tiny bit of simple state and all the books/articles would have you standing up read only views & stored procedures for all your crud ops. The document stores came along with a fresh perspective and easy scaling. Then their were the columnar stores and time-series stores that really did solve the newer scale problems in ways the existing sql stores didn’t. I’m a sql guy through and through but it’s important to recognize the nosql movement was a reaction to real pain points. Also it made the sql databases better.
- pjmlp 5y agoWhat history rewriting? I have been using RDMS all along since 1996. Nokia NetAct was scaling GB of data across multiple clusters with OLAP reporting engine in 2005 with no hiccups. The experience I had with DynamoDB kind of proved to me I haven't lost anything by staying in the SQL path. Most NoSQL deployments I have seen, could have been easily done in Oracle or SQL Server, provided they actually had a DBA on the team.
- kasey_junk 5y agoBut that’s sort of the point. You are saying “if you have a DBA and use proprietary products and have the skill to understand the trade offs of running a db with another data warehouse product layered in you can handle GB of data”. Mongo said “Throw data at me and I’ll scale with very little work”. Now, I’ve always largely believed that’s penny wise and pound foolish but it’s certainly a good pitch.
- wodenokoto 5y ago> SELECT item_id WHERE expire = 0 I come across a lot of SQL databases that uses 0 instead of false. Is there any good reason for this?
- xupybd 5y agoOnly in databases that have no Boolean type. Sometimes it's an artifact of the orm mapping.
- masklinn 5y agoSo that you don't need a separate column for an associated datum?
- chx 5y agofalse would be "expired", this is called "expire" because it is a timestamp, it's the epoch time when the item expires. The worker presumably finishes before that time and if it does then the item is deleted. So, if any item has a nonzero expires in the past then it needs to be reset to 0 so it can be retried.
- zapstar 5y agoI have done something similar to this to implement queues in Postgres. And at quite a large scale with lots of workers all pulling items off the queue at once. One huge advantage over, say, SQS, is that you also get easy visibility! You can query and see what’s been completed, what’s still not worked on, etc.! Oh, and do you want a priority queue? Just add a priority field and sort before picking an item! Do you need to change the priority of an item while it’s already in the queue? Go right ahead. Do you want to enforce some constraints so that duplicates don’t get added to the queue? It’s a database — add the constraints. If you’re already using a relational database, and now you need a queue, start with this approach. Odds are, it’ll work just fine, and it’ll give you the perks above.
- GordonS 5y agoInteresting! What kind of scale did you run it at? Also keen to know if you saw any disadvantages with this approach?
- sorokod 5y agoWhat happens if the process that performed 2. crashes before it was able to complete whatever processing it was supposed to do?
- jffry 5y agoThe idea, I think, is you wouldn't delete the job from the queue until the processing was done. Of course, this relies on the jobs being something that can be retried.
- shawnz 5y agoBut you will have marked it as in progress by setting the "expire" to a non-zero value, preventing any other workers from trying to work on it. How will they know that the worker which marked it actually crashed and will never finish? By using SELECT ... FOR UPDATE SKIP LOCKED, the record will automatically get unlocked if the worker crashes.
- jffry 5y agoNot sure. Maybe something else is responsible for identifying "stuck" jobs and kicking them out to humans to decide what to do (assuming worker crashes are rare) If we're talking PostgreSQL specifically, and newer-ish Postgres (9.5+ I think), then you can leverage its abilities to do all this in one atomic query: UPDATE jobs SET status='working' WHERE id = (SELECT id FROM jobs WHERE status=NULL LIMIT 1 FOR UPDATE SKIP LOCKED) RETURNING id
- shawnz 5y agoIf you are willing to use SELECT ... FOR UPDATE SKIP LOCKED, then you can implement the queue without any UPDATE query or status column at all. Just lock the record to mark it as in progress, that is how you get the benefit that when the worker crashes, it will automatically be returned to the queue.
- sorokod 5y ago
- ryanthedev 5y agoI believe something like this would have issues with multiple consumers.
- dragonwriter 5y ago> You need a table with a primary id and a "status" field. For a queue, you need a table with an insertion order and a status indicator. “Primary id” is not enough because “primary id” may not be ordered (e.g., a UUID primary key is a primary id.) OTOH, while a DB can do this, therr are plenty of well-tested open source purpose built message queueing solutions, so the swt of scenarios where “roll your own with a DB” isn’t a misuse of effort is limited.
- lolinder 5y agoWhy on earth would you make a queue table with a non-serial primary key? What benefit do you gain from a UUID here?
- deleted 5y ago[deleted]
- viraptor 5y agoThis sounds dangerous. Without some good way to prevent workers stepping on each other, that will result in lots of useless queries and failed updates if a lot of jobs get scheduled at the same time. In the Drupal case, the database returns a single row which is pretty much guaranteed to be the same for all workers in between updates. You really don't want that in the same database your page views hit. At least selecting N rows at a time and then claiming a random item from them would be slightly better.
- viraptor 5y agoI find the downvotes weird without any explanation why the raised issue doesn't sound important.
- joelbluminator 5y agoSo you need to keep polling the db?
- lolinder 5y agoPostgres has LISTEN/NOTIFY for this.
- jayd16 5y agoA single Rabbit node seems easier than rolling this yourself and doing all the work to test it.
- solipsism 5y agoBut if we always do what's easiest, then we will make a bunch of horrible choices. Other things that matter, often more than what's easiest: * Flexibility. If you aren't 100% sure what you'll need, but need something in place today, it can make sense to choose an unopinionated, generic solution. * Familiarity. Maybe you've never used Rabbit. * Ops simplicity. Maybe you already have a bunch of postgres deployed. Adding a new type of system means you need new ways of monitoring, new dependencies, different deployment.
- throwaway894345 5y agoOf these, I think the last is the most compelling. Why introduce something new if you already have all of the infra and tooling configured for managing postgres? The parent mentioned testing the postgres implementation, but that seems like quite a lot less work than configuring the infra-as-code, monitoring, alerting, etc required for a new type of thing.
- z77dj3kl 5y agoIt's a tradeoff between software and infra complexity. I would argue that if you've built a system up from scratch, this is much easier to debug and maintain than a foreign piece of software. Rabbit is just way overkill if you have a couple of jobs per hour, for example.
- jasonwatkinspdx 5y agoThere's off the shelf libraries to do this in nearly every language. It's always about tradeoffs in context, but I have seen plenty of instances of someone setting up a rabbit cluster for something that could be done trivially in their existing db cluster via the above.
- solipsism 5y agoWhat am I missing? With your description, nothing ever sets expire to 0. Can't look at the code comfortably as I'm on mobile.
- ukd1 5y agoYou really really wanna do everything (locking, working, unlocking, deleting or completing) in a transaction, and use SKIP LOCKED to find work. It's actually pretty high performance when you so this.
- phumberdroz 5y agodo you have a more detailed example on how this could look like?
- dillondoyle 5y agoThanks for posting this! It is relevant to me right now and great example. Especially since I'm using a new to me database, Spanner. Specifically I similarly pull rows into a 'queue' like that linked sql by WHERE primary key, primary key, and queue_status ORDER BY timestamp, uuid LIMIT 10. I was worried what would happen with many requests around the same time if it would accidentally pull duplicates into 'queue.' I think hopefully I've implemented Spanner locking read write transaction correctly and that this won't cause problems at scale (we're not even close to google scale lol).
- sigil 5y agoProblems with this approach: 1. Recovery. 2. Concurrency. 3. Polling. In more detail: 1. Recovery. Suppose a worker dies while processing a job. The job should be retried, but how do you know this, since expire > 0? You can impose a timeout, but that has drawbacks -- there might be long jobs you repeatedly start but never finish. To recover failed jobs without imposing a timeout, you'd have to run both the UPDATE and the job processing inside a transaction. That way, a failed job can result in an implicit ROLLBACK, freeing the job for future worker attempts. 2. Concurrency. So now recoverable workers are trying to claim jobs inside a transaction. If there are 10 jobs and 10 workers, we want all 10 jobs processing concurrently. However, each worker SELECTs the first item_id and tries to UPDATE that same row. 1 worker wins. The other 9 workers block while that transaction completes, then update zero rows. Concurrency will hover around 1. 3. Polling. In the transactional UPDATE approach, there's no way to tell whether there are free jobs short of trying to claim them via UPDATE, which blocks. So you must poll, and either burn cpu on quiet queues, or introduce an artificial delay into job processing times. The beauty of the SKIP LOCKED approach is that it can tell whether there are free (not currently processing) jobs. Even if you wake all 10 workers up via LISTEN / NOTIFY for a lone job, 9 workers in the thundering herd will fail to claim the job, and go back to sleep. I blame TFA for not sufficiently explaining the SKIP LOCKED approach. A much better explanation is here: https://www.2ndquadrant.com/en/blog/what-is-select-skip-locked-for-in-postgresql-9-5/ https://www.2ndquadrant.com/en/blog/what-is-select-skip-lock...
- jsmith45 5y ago1. I interpreted expires to be the timeout. Their could either be a stand alone transaction run periodically, that sets the expiration back to zero, or you just update the queries to read `expire < now()`. Thus neither are running in the same transaction as anything else. The SELECT will never block, since it is not specified as "FOR update". The update itself specified the key. On the other hand, the SKIP LOCKED approach is really nice for allowing the queue processing to be one single transaction that commits atomically, and thus nicer semantics than a timeout based retry strategy. I do like that approach. The only downside is that not all RDBMS support those semantics, but for an app that only needs to support Postgres it does look like the smart approach.