waitlist in postgres, deadlock

I'm trying to create a waiting list in Postgres. Minimal code:

CREATE TABLE IF NOT EXISTS applies(
    created TIMESTAMP DEFAULT CURRENT_TIMESTAMP,
    user_id SMALLINT REFERENCES users(id) ON DELETE CASCADE,
    service_id SMALLINT REFERENCES services(id) ON DELETE CASCADE,
    status SMALLINT DEFAULT 0, --0: new 1: waitlisted, 2: applied
    PRIMARY KEY (user_id, service_id)
    -- ...
);

CREATE INDEX ON applies (service_id);

status is important, because I want to be able to notify users when they are applied after waitlisted. But don't want to notify them based on that they are in the first n position if they wasn't waitlisted at all. Services are limited to a given number of users. There are multiple choices how the system decides which user gets the service. The simplest is first come first served. That's the reason it has two phases (but it shouldn't change the use case in any way).

Possible requests are:

Insert: a user applies/enrolls for a service
1. Inserting (user_id, service_id, CURRENT TIMESTAMP, state: 0 (new))
2. a Updating state to 1 (waitlisted) or 2 (applied) based on the COUNT(*) with the same service_id
Remove: a user cancels his/her application for a service
1. Removing the given application
2. If there's someone in waitlisted state, move to applied, and send notification about it

My first try was a naive implementation. Let's say service limit is 10.

1/2 OnAdd:

UPDATE applies
SET status = (
    SELECT CASE WHEN COUNT(*) <= 10 THEN 2 ELSE 1 END
    FROM applies
    WHERE service_id = 7918
    AND created <= '2021-08-16 16:20:34.161274+00:00:00'
)
WHERE user_id = 5070
AND service_id = 7918
RETURNING status

2/2 OnRemove:

SELECT user_id
FROM applies
WHERE status = 1
AND service_id = 7915
ORDER BY created
LIMIT 1

and then ( I know they could be joined)

UPDATE applies
SET status = 2
WHERE status = 1
AND user_id = 5063
AND service_id = 7915

It worked for a sequential test, but the multi-threading test showed cases when there were more than 10 rows with applied state.

So I put them in a transaction started with SET TRANSACTION ISOLATION LEVEL SERIALIZABLE, then REPEATABLE READ, they gave me a lot of ERROR #40001 could not serialize access due to concurrent update. Then the same with READ COMMITTED. It was way much better, than the naive version, but it ended in over-applications as well.

Then I started using FOR NO KEY UPDATE in selects instead, but they always ended in a deadlock very soon. I searched a lot on deadlocks, but couldn't find anything useful.

So I came up with a version, where OnAdd and OnRemove had very similar queries, only differing in selecting user_id, where I didn't add FOR UPDATE. I had to change 1/1 Insert so the default state is waitlisted.

OnAdd:

UPDATE applies
SET status = 2
WHERE service_id = 7860
AND 10 > (
    SELECT COUNT(*)
    FROM (
        SELECT service_id, user_id
        FROM applies
        WHERE service_id = 7860
        AND status = 2
        FOR NO KEY UPDATE
    ) as newstate)
AND user_id = 5012 RETURNING status

OnRemove:

UPDATE applies
SET status = 2
WHERE service_id = 7863
AND 10 > (
    SELECT COUNT(*)
    FROM (
        SELECT service_id, user_id
        FROM applies
        WHERE service_id = 7863
        AND status = 2
        FOR NO KEY UPDATE
    ) as newstate)
AND user_id = (
    SELECT user_id
    FROM applies
    WHERE service_id = 7863
    And status = 1
    ORDER BY created
    LIMIT 1
)
RETURNING user_id

But in the multi-threading test it ended up in a deadlock too.

Edit:

As melcher suggested below, I added a column instead of counting. Not to a separate table, but inside services.

I added a transaction to OnAdd and OnRemove that starts with

SELECT *
FROM services
WHERE id = ?
FOR NO KEY UPDATE

Sometimes in the multithreading test it under-applied. So I joined Remove to be in the same transaction with OnRemove, and that works finally.

Solution

Based on my understanding of what you're trying to do and how databases work - you're going to need a shared resource that gets locked OnAdd.

The reason is that two threads that are both trying to 'add' at the same time must compete for a shared resource so that only one of them wins and the other errors / fails. You cannot accomplish your goal using a count of rows.

One solution would be a locks table:

CREATE TABLE IF NOT EXISTS applies(
    service_id SMALLINT REFERENCES services(id) ON DELETE CASCADE,
    applied_count SMALLINT
);

And then:

Open transaction (if outside of a procedure)
Acquire an exclusive/write lock to services row in the lock table
IF the limit/constraint is satisfied (e.g. applied_count < 10) then...
Mark the "applies" as applied UPDATE applies SET status = 2
Update lock table (e.g. SET applied_count = applied_count + 1)
Commit transaction