6 ms·

There are plenty of articles about writing simple job queues in Postgres using SKIP LOCKED, and I personally like that version quite a bit for cases where you d

There are plenty of articles about writing simple job queues in Postgres using SKIP LOCKED, and I personally like that version quite a bit for cases where you don't want to add another separate component just for the queue. But I haven't seen anyone addressing fairness in such a queue, e.g. for the multi-tenant case. Is there a simple way to get a very rough kind of fairness between tenants in this case? Doesn't have to be actually fair, just fair enough that no tenant gets fully stuck behind a large block of jobs from another tenant. The idea behind SKIP LOCKED is that you just get the first free job (potentially ordered by e.g. a priority column). Doing that in a way that switches between tenants doesn't seem straightforward. You could execute the query once per tenant, but that would be rather inefficient for many tenants. Is there a reasonably straightforward way to achieve this?

dimitropoulos 3y ago
Skip locked seems to be the way that new queueing packages are going, though they don’t solve fairness or multi-tenancy. It’s nice to keep things simple, but how does that work at scale? If I have 1,000 users I don’t think that these standard queueing systems can prevent one tenant from impacting another. It doesn’t look like that’s possible in SQS, either. On the other hand, is that even necessary? At what scale is this important?
- fabian2k 3y ago
  I'm thinking about relatively simple systems and not "real" fairness. The case where I've seen this being a bit problematic is with such a queue in an application where jobs are sometimes inserted in large bursts. It doesn't actually matter much if they are truly fair, but in the cases where a large number of jobs is inserted at once the result is that for some tenants the queue doesn't seem to move at all. It's not a huge problem in that case because the regular priority system still puts the urgent jobs at the front of the queue. But it does sometimes cause confusion for someone looking at this from a single-tenant perspective because the queue looks stuck. There are other ways to fix the confusion, but it would be nice to have a very rudimentary fairness in this simple queue that would ensure that the queue iterates a bit over the tenants.
  - deleted 3y ago
    [deleted]
- vosper 3y ago
  > On the other hand, is that even necessary? At what scale is this important? I can see it being helpful in front of a shared resource that doesn't have any way to control priority or fairness. My use case would be Elasticsearch. I don't want to block any searches from running if there's capacity, but also I don't want misbehaving clients to monopolise resources, and I want to make sure that all customers/users get to run their searches eventually, though I may prioritise some customers/users over others. And I may need my own internal jobs to run at a lower priority than a user search, but still within a guaranteed window (to avoid timeouts on the client side). Honestly for my use case this could be useful with just a handful of users - less than 10, even.
- whartung 3y ago
  Seems to me a solution is to have a "generic" queue handler that will take any message, and then have tenant specific queue handlers. Now, mind, I'm not thinking of a dedicated handler for each tenant, rather one that can round robin, or rotate through the tenants to pull items specific to that tenant off the queue. This can be the "fairness" arbiter. With the Postgres SKIP LOCKED technique, you can be selective as to which messages you pull (you're not limited to the head of the queue, but can dig deep if you want). So, you have one general purpose "head of the line" handler, and then one (or several) that acts like the fellow at the Post Office "Anyone here just picking up mail?", and pull them out of the queue. Of course the generic version can just switch modes (every 1m, or 100 messages, go into "fair mode" for a short time), vs having different handlers.
- foofie 3y ago
  > On the other hand, is that even necessary? At what scale is this important? That's the critical question. To that I had that there might be a myriad of articles on how someone used postgres to build a message queue instead of using a dedicated message broker, but there isn't a single article showing any form of benchmarking, performance tests, load test results, and more importantly report the correlation between load and performance degradation and eventual overload and resulting failure modes. This information is of critical importance to be able to design systems and pick which tool is suited for the job.
xyzzy_plugh 3y ago
There is probably a better way (I no longer use Postgres for this) but I solved this in the past by evaluating priority after popping an item off the queue. If the item was low priority and there was higher priority work to do, or if a customer was over their quota, I would reschedule the work item. In that scenario I employed an earliest-deadline-first scheduler table so rescheduling was just re-inserting or updating with a new deadline.
- RaftPeople 3y ago
  > In that scenario I employed an earliest-deadline-first scheduler... I did something that sounds similar with the skip locked technique for a request queueing system supporting conveyor routing in a DC. Priority alone wouldn't work because requests in different areas of the conveyor had different lead times until the response was required, sometimes 5 feet and sometimes 300 feet. If I made the shorter lead times all higher priority then they could all supersede an older request for longer sections that is now nearing the divert. So the requests get submitted with a deadline datetime, and that is the index used to select the next request (top 1, order by deadline), worked pretty well.
pphysch 3y ago
You have the full power of PostgreSQL at your disposal, so there are many ways you can effectively tackle this issue. - Decrement priority of all tenants jobs by 1 each time their job is executed, or increment other tenants' priorities (more ops but better behavior) - Maintain a separate tenant priority table and join it + use for ordering when fetching the next job And so on
- fabian2k 3y ago
  I can think of plenty of inefficient ways to do this. The nice thing about the SKIP LOCKED queue is that it is very simple and pretty fast. Postgres just has to use an index to look at the jobs in some defined order and take the first one that isn't locked. The first option here would create an enormous amount of writes for each job fetched and likely slow it down to a crawl if enough jobs are in the queue.
  - pphysch 3y ago
    Many scheduling systems have a "time in queue increases priority" behavior; it is not an exotic proposition and could be implement efficiently in PostgreSQL. Having too many jobs in queue is a problem on its own that should be addressed. Each tenant should be rate-limited or have a reasonable cap on number of waiting jobs.
- karldcampbell 3y ago
  As long as you don't need a strict priority and a worker can just grab the next waiting job: SELECT * FROM jobs ORDER BY RANDOM() LIMIT 1 SKIP LOCKED should do the trick
  - gnud 3y ago
    This will give more resources to tenants that schedule more jobs. If tenant A schedules 99 jobs and tenant B schedules 1 job, a "fair" algorithm would pick B's job either first or second, RANDOM() will not.
paulddraper 3y ago
The solution is to maintain two queues. One queu is your normal queue. A second queue that is your tenant queue (one record for each tenant that has queued items). You select from your tenant queue, then select from your normal queue. All the while keeping your tenant invariant (one record for each tenant that has queued items). --- It's certainly more complex but no one said that fair was easy.
10000truths 3y ago
This depends largely on your requirements. * How well can you estimate job cost? How should overestimates and/or underestimates be treated? * Where, when and how often does resource contention occur between jobs? Is it from a single resource, or from multiple different resources? * What constraints or behaviors does the contended resource(s) possess (e.g. rate limits, pipelining, etc.) that would materially impact how you determine which job to run next? * What guarantees do you wish to make (e.g. execution latency, resource availability, etc.)? * How is resource usage quota determined? Are quotas updated frequently? Are there any circumstances under which you would like to allow users to exceed their quota (e.g. temporary burst workloads, idle periods of time)?
nurettin 3y ago
First, query total time spent today for each tenant. Then, pick a job from the most unfortunate tenant's queue.
smallnamespace 3y ago
> Is there a simple way to get a very rough kind of fairness between tenants in this case? Yes, since the SKIP LOCKED query is just a special sort of SELECT that skips over locked rows, you can use all the normal SQL tools such as ORDER BY to accomplish what you want. One way is to make the top row fair by randomizing over the tenant ID, for example SELECT itemid FROM queue ORDER BY md5(tenant_id || current_timestamp::TEXT), item_id FOR UPDATE SKIP LOCKED LIMIT 1; Here we append the ID to the timestamp and then hash it, so each time the SELECT is run there is effectively a different ordering between tenant IDs, hence fairness. Note that this will eventually have performance implications for a deep queue since it forces a scan on the whole table. Adding an index on tenant_id may mitigate that, but as always do your own profiling.
- btown 3y ago
  Out of curiosity, is Postgres usually able to use a b-tree index's representation of the columnar data for its (set of) columns to calculate a derived value for those column(s), then scan through that in-memory derived data? Certainly not as fast as the index lookup itself, but avoids needing to have the entire table in memory, I would hope? The documentation under https://www.postgresql.org/docs/16/indexes-types.html https://www.postgresql.org/docs/16/indexes-types.html implies that it can be used to access the sorted values - but does that feed through the query planner?
- grogers 3y ago
  Having a query like this that gets slower as the queue gets bigger is a really bad idea. It'll work just fine in the steady state when your queue is short. And then when you get overloaded and start queueing, you will be adding more load into the equation just to drain the queue. It's a recipe for a metastable system that causes a major outage. Adding an index on tenant_id will do nothing because you are always appending the current timestamp before hashing.
  - smallnamespace 3y ago
    The query running in O(queue size) is very likely avoidable if you add an index on the tenant_id. Ideally the query planner figures this out (see the sibling comment), but if not, the query can likely be written to "encourage" the planner, for example by first selecting the top few values of md5(tenant_id, current_timestamp) within a subquery before lateral joining into the SKIP LOCKED table. If the concern is only that the queue falls over once it gets large enough, you can also LIMIT to a fixed number of rows before doing the outer SELECT. This gives a weaker fairness bound (tenants that have fewer than O(queue size / selected items) rows are at risk of being ignored) but you get a better guarantee of progress under contention.
deleted 3y ago
[deleted]
jillesvangurp 3y ago
I found a nice article on skip locked last week: https://www.crunchydata.com/blog/message-queuing-using-native-postgresql https://www.crunchydata.com/blog/message-queuing-using-nativ... We went ahead and implemented our own little queue in postgres based on that to get rid of a wonky thing we had that built on top of redis. What I like about this is that it's simple, robust, and transactional. So, you get some nice guarantees out of that. For fairness, you might do stuff with partitioning on the priority column. Simply set up your workers to only hit a certain partition. So you have separate workers for higher and lower priority queue items. If you then dynamically lower the priority of tenants sending you lots of traffic, the system becomes more fair for the others. You could work with some simple moving average here. Just an idea, but something like this might work.

dimitropoulos 3y ago

Skip locked seems to be the way that new queueing packages are going, though they don’t solve fairness or multi-tenancy. It’s nice to keep things simple, but how does that work at scale? If I have 1,000 users I don’t think that these standard queueing systems can prevent one tenant from impacting another. It doesn’t look like that’s possible in SQS, either. On the other hand, is that even necessary? At what scale is this important?

fabian2k 3y ago
I'm thinking about relatively simple systems and not "real" fairness. The case where I've seen this being a bit problematic is with such a queue in an application where jobs are sometimes inserted in large bursts. It doesn't actually matter much if they are truly fair, but in the cases where a large number of jobs is inserted at once the result is that for some tenants the queue doesn't seem to move at all. It's not a huge problem in that case because the regular priority system still puts the urgent jobs at the front of the queue. But it does sometimes cause confusion for someone looking at this from a single-tenant perspective because the queue looks stuck. There are other ways to fix the confusion, but it would be nice to have a very rudimentary fairness in this simple queue that would ensure that the queue iterates a bit over the tenants.
- deleted 3y ago
  [deleted]
vosper 3y ago
> On the other hand, is that even necessary? At what scale is this important? I can see it being helpful in front of a shared resource that doesn't have any way to control priority or fairness. My use case would be Elasticsearch. I don't want to block any searches from running if there's capacity, but also I don't want misbehaving clients to monopolise resources, and I want to make sure that all customers/users get to run their searches eventually, though I may prioritise some customers/users over others. And I may need my own internal jobs to run at a lower priority than a user search, but still within a guaranteed window (to avoid timeouts on the client side). Honestly for my use case this could be useful with just a handful of users - less than 10, even.
whartung 3y ago
Seems to me a solution is to have a "generic" queue handler that will take any message, and then have tenant specific queue handlers. Now, mind, I'm not thinking of a dedicated handler for each tenant, rather one that can round robin, or rotate through the tenants to pull items specific to that tenant off the queue. This can be the "fairness" arbiter. With the Postgres SKIP LOCKED technique, you can be selective as to which messages you pull (you're not limited to the head of the queue, but can dig deep if you want). So, you have one general purpose "head of the line" handler, and then one (or several) that acts like the fellow at the Post Office "Anyone here just picking up mail?", and pull them out of the queue. Of course the generic version can just switch modes (every 1m, or 100 messages, go into "fair mode" for a short time), vs having different handlers.
foofie 3y ago
> On the other hand, is that even necessary? At what scale is this important? That's the critical question. To that I had that there might be a myriad of articles on how someone used postgres to build a message queue instead of using a dedicated message broker, but there isn't a single article showing any form of benchmarking, performance tests, load test results, and more importantly report the correlation between load and performance degradation and eventual overload and resulting failure modes. This information is of critical importance to be able to design systems and pick which tool is suited for the job.

xyzzy_plugh 3y ago

There is probably a better way (I no longer use Postgres for this) but I solved this in the past by evaluating priority after popping an item off the queue. If the item was low priority and there was higher priority work to do, or if a customer was over their quota, I would reschedule the work item. In that scenario I employed an earliest-deadline-first scheduler table so rescheduling was just re-inserting or updating with a new deadline.

RaftPeople 3y ago
> In that scenario I employed an earliest-deadline-first scheduler... I did something that sounds similar with the skip locked technique for a request queueing system supporting conveyor routing in a DC. Priority alone wouldn't work because requests in different areas of the conveyor had different lead times until the response was required, sometimes 5 feet and sometimes 300 feet. If I made the shorter lead times all higher priority then they could all supersede an older request for longer sections that is now nearing the divert. So the requests get submitted with a deadline datetime, and that is the index used to select the next request (top 1, order by deadline), worked pretty well.

pphysch 3y ago

You have the full power of PostgreSQL at your disposal, so there are many ways you can effectively tackle this issue. - Decrement priority of all tenants jobs by 1 each time their job is executed, or increment other tenants' priorities (more ops but better behavior) - Maintain a separate tenant priority table and join it + use for ordering when fetching the next job And so on

fabian2k 3y ago
I can think of plenty of inefficient ways to do this. The nice thing about the SKIP LOCKED queue is that it is very simple and pretty fast. Postgres just has to use an index to look at the jobs in some defined order and take the first one that isn't locked. The first option here would create an enormous amount of writes for each job fetched and likely slow it down to a crawl if enough jobs are in the queue.
- pphysch 3y ago
  Many scheduling systems have a "time in queue increases priority" behavior; it is not an exotic proposition and could be implement efficiently in PostgreSQL. Having too many jobs in queue is a problem on its own that should be addressed. Each tenant should be rate-limited or have a reasonable cap on number of waiting jobs.
karldcampbell 3y ago
As long as you don't need a strict priority and a worker can just grab the next waiting job: SELECT * FROM jobs ORDER BY RANDOM() LIMIT 1 SKIP LOCKED should do the trick
- gnud 3y ago
  This will give more resources to tenants that schedule more jobs. If tenant A schedules 99 jobs and tenant B schedules 1 job, a "fair" algorithm would pick B's job either first or second, RANDOM() will not.

paulddraper 3y ago

The solution is to maintain two queues. One queu is your normal queue. A second queue that is your tenant queue (one record for each tenant that has queued items). You select from your tenant queue, then select from your normal queue. All the while keeping your tenant invariant (one record for each tenant that has queued items). --- It's certainly more complex but no one said that fair was easy.

10000truths 3y ago

This depends largely on your requirements. * How well can you estimate job cost? How should overestimates and/or underestimates be treated? * Where, when and how often does resource contention occur between jobs? Is it from a single resource, or from multiple different resources? * What constraints or behaviors does the contended resource(s) possess (e.g. rate limits, pipelining, etc.) that would materially impact how you determine which job to run next? * What guarantees do you wish to make (e.g. execution latency, resource availability, etc.)? * How is resource usage quota determined? Are quotas updated frequently? Are there any circumstances under which you would like to allow users to exceed their quota (e.g. temporary burst workloads, idle periods of time)?

nurettin 3y ago

First, query total time spent today for each tenant. Then, pick a job from the most unfortunate tenant's queue.

smallnamespace 3y ago

> Is there a simple way to get a very rough kind of fairness between tenants in this case? Yes, since the SKIP LOCKED query is just a special sort of SELECT that skips over locked rows, you can use all the normal SQL tools such as ORDER BY to accomplish what you want. One way is to make the top row fair by randomizing over the tenant ID, for example SELECT itemid FROM queue ORDER BY md5(tenant_id || current_timestamp::TEXT), item_id FOR UPDATE SKIP LOCKED LIMIT 1; Here we append the ID to the timestamp and then hash it, so each time the SELECT is run there is effectively a different ordering between tenant IDs, hence fairness. Note that this will eventually have performance implications for a deep queue since it forces a scan on the whole table. Adding an index on tenant_id may mitigate that, but as always do your own profiling.

btown 3y ago
Out of curiosity, is Postgres usually able to use a b-tree index's representation of the columnar data for its (set of) columns to calculate a derived value for those column(s), then scan through that in-memory derived data? Certainly not as fast as the index lookup itself, but avoids needing to have the entire table in memory, I would hope? The documentation under https://www.postgresql.org/docs/16/indexes-types.html https://www.postgresql.org/docs/16/indexes-types.html implies that it can be used to access the sorted values - but does that feed through the query planner?
grogers 3y ago
Having a query like this that gets slower as the queue gets bigger is a really bad idea. It'll work just fine in the steady state when your queue is short. And then when you get overloaded and start queueing, you will be adding more load into the equation just to drain the queue. It's a recipe for a metastable system that causes a major outage. Adding an index on tenant_id will do nothing because you are always appending the current timestamp before hashing.
- smallnamespace 3y ago
  The query running in O(queue size) is very likely avoidable if you add an index on the tenant_id. Ideally the query planner figures this out (see the sibling comment), but if not, the query can likely be written to "encourage" the planner, for example by first selecting the top few values of md5(tenant_id, current_timestamp) within a subquery before lateral joining into the SKIP LOCKED table. If the concern is only that the queue falls over once it gets large enough, you can also LIMIT to a fixed number of rows before doing the outer SELECT. This gives a weaker fairness bound (tenants that have fewer than O(queue size / selected items) rows are at risk of being ignored) but you get a better guarantee of progress under contention.

deleted 3y ago

[deleted]

jillesvangurp 3y ago

I found a nice article on skip locked last week: https://www.crunchydata.com/blog/message-queuing-using-native-postgresql https://www.crunchydata.com/blog/message-queuing-using-nativ... We went ahead and implemented our own little queue in postgres based on that to get rid of a wonky thing we had that built on top of redis. What I like about this is that it's simple, robust, and transactional. So, you get some nice guarantees out of that. For fairness, you might do stuff with partitioning on the priority column. Simply set up your workers to only hit a certain partition. So you have separate workers for higher and lower priority queue items. If you then dynamically lower the priority of tenants sending you lots of traffic, the system becomes more fair for the others. You could work with some simple moving average here. Just an idea, but something like this might work.