Proposal for simulation claiming with fewer queries

[mattdailis]

Currently, simulations are claimed as follows:

• The simulate action inserts a row into simulation_dataset
• A trigger issues a NOTIFY to "simulation_notification"
• Each worker adds the notification to their queue
• Each available worker iterates through all received notifications, attempting to claim each one
  • Claiming is done by update set status='incomplete' where id=? and status='pending'

There are a couple of aspects here that I think have room for improvement:

• If a worker goes down and comes back up, any queued notifications are lost, and the worker will not attempt to claim previously requested simulations
• Every worker issues one UPDATE per request

The former is a more pressing issue than the latter - the multiple requests aren't really a performance bottleneck. Two open questions there are:

• If a worker crashes during simulation in a way that it doesn't have time to report the simulation as failed, what should it do when it comes back up?
  • If we were to somehow give workers ids, and allow the worker to identify that there's an incomplete simulation with its own id, could/should it toggle it to failed?
• If a new worker comes up, with an empty queue, should it attempt to claim existing simulation requests?

I engaged in a thought exercise - would it be possible to write a "Claim" action (in the Java database action sense) that atomically claimed any single pending simulation? This action could be used when a worker starts up, to claim previously issued simulation requests, and it could also be used in lieu of iterating over every notification in the queue.

Essentially I'm looking for something like this:

update simulation_dataset
  set status='incomplete'
  where id=(select id from simulation_dataset where status='pending' order by id limit 1);

It turns out there are a few problems with this. The trouble comes from the fact that the select statement may return rows that are concurrently being modified by another transaction - i.e. another worker may already be in the process of claiming that simulation. The consequence is two-fold:

• This transaction will block until the other transaction commits or rolls back
• If the other transaction commits, this transaction will unblock and set the status to 'incomplete' again - meaning that this simulation got claimed by two workers (oops!)

To try to solve that, we could add a seemingly redundant where clause to the update statement:

update simulation_dataset
  set status='incomplete'
  where id=(select id from simulation_dataset where status='pending' order by id limit 1)
    and status='pending';

This prevents double claiming, but it doesn't quite give us the "claim any simulation" semantics. Instead, this is "try to claim the first pending dataset - give up if you can't". We could issue the above query repeatedly, and eventually claim a simulation request, but that seems suboptimal.

We need the select and the update to operate atomically - so that no concurrent modification can sneak in between the worker observing a row as 'pending' and that worker updating that row to 'incomplete'. Enter the select for update feature:

update simulation_dataset
  set status='incomplete'
  where id=(select id from simulation_dataset for update where status='pending' order by id limit 1);

⭐

select for update will set row-level locks on each row returned from that select statement. In this case, that means the select statement will lock the first 'pending' simulation request it encounters, and then the update can safely claim it, with no interference from concurrent transactions.

This achieves the goal of a single query that claims any simulation request 🎉 This next step I'm less sure is necessary, but for the sake of completeness I'll include it.

The only arguably undesirable property of the above query is that concurrent claim requests block each other - the first query will lock the first pending simulation - and the second query cannot proceed until that query commits. If we want to allow the second query to skip the first simulation request, and move on to the second request, we can add the skip locked option to `select for update:

update simulation_dataset
  set status='incomplete'
  where id=(select id from simulation_dataset for update skip locked where status='pending' order by id limit 1);

This query will claim the first pending simulation request that doesn't have a row-level lock. It introduces a vulnerability that if the locking transaction rolls back rather than commits, our worker may claim zero simulation requests, even though there is one that is available to be claimed. For that reason, I think it might be better to leave off the skip locked option, use the option marked with a ⭐ and make sure the claiming transactions are short.

[Twisol]

The only arguably undesirable property of the above query is that concurrent claim requests block each other - the first query will lock the first pending simulation - and the second query cannot proceed until that query commits.

Just to make sure I understand, this sounds less like "block eachother" (which sounds like a deadlock) and more like "are linearized" -- if one worker is in the process of trying to claim a job, then every other worker has to wait on the first one before they get a shot. Is that right?

[mattdailis]

Precisely, yes 👍

[Twisol]

I think I agree about preferring the ⭐ option -- I don't necessarily like its linearizing behavior, but uniquely claiming a job seems like an action that inherently requires consensus/agreement/exclusion, so I don't think it's incorrect.

In some ways, it might be better to have jobs assigned to workers instead of having workers clamor for jobs. But I think that's beyond the scope of this work, and moreover is likely to have other implications on the system.

[mattdailis]

Yes - one property of the linearizing behavior is that simulation requests are claimed strictly in the order that they were issued, which could be a good thing.