Hacker News Reader

Comment by fabian2k | Hacker News Reader

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?

View on HN

I found a nice article on skip locked last week: 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.

> 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.

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 implies that it can be used to access the sorted values - but does that feed through the query planner?

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.

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.

I'm not addressing your point on fairness but I've been working on a similar program but instead of taking locks out on the queue table I maintain a consumers position for locked and acknowldeged messages on the consumers table. It makes lots of queries simpler. Here's a simplified schema using SQL Server:

  CREATE TABLE [dbo].[Nodes] (
    [Id]             UNIQUEIDENTIFIER NOT NULL,
    [NetworkId]      UNIQUEIDENTIFIER NOT NULL,    
    [Locked]         INT              NOT NULL,
    [Acknowledged]   INT              NOT NULL,
  );

  CREATE TABLE [dbo].[Messages] (
    [Id]            UNIQUEIDENTIFIER NOT NULL,
    [NetworkId]     UNIQUEIDENTIFIER NOT NULL,
    [NodeId]        UNIQUEIDENTIFIER NOT NULL,    
    [Payload]       NVARCHAR (MAX)   NULL,
    [InsertedOrder] INT DEFAULT (NEXT VALUE FOR dbo.MessageSequence) NOT NULL,
    [TimestampUtc]  DATETIME2 (7)    DEFAULT (sysutcdatetime()) NOT NULL,
  );

  Select * 
  From Nodes With (Rowlock, Holdlock)
  Where NetworkId = @networkId
  And Id = @nodeId

Multi-tenancy is per database.

(edit: simplified sql)

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?

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.

> 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.

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.

> 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.

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)?

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.

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

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.

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.

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

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.

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

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.

> 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.

Reply on news.ycombinator.com