Atomic updates to ordering in a table for a waiting list application

Question

I am trying to implement a gamified waiting list. This waiting list is for eventual access to an application. A user on the waiting list can perform certain actions which may move them up in the waiting list. The table would look something like this (open to suggestions here as well):

# table waitinglist

user_id	position
12	0
3	1
15	2
10	3

... and so on.

This waiting list could potentially (hopefully) have millions of entries.

When a user performs an action that changes their order in the waiting list, I want to be able to update that order atomically so that if someone else does something to change their order at a similar time that they don't conflict.

We are using Postgres for our database, but I'm open to other (opensource) ideas as well.

In the example table, if user #3 did something that moves them to position 0, it means that user #12 would be moved to position 1. We could do a query like:

BEGIN;
UPDATE waitinglist AS w SET
    position = d.position
FROM (VALUES
    (3, 0),
    (12, 1)  
) AS d(user_id, position) 
WHERE d.user_id = w.user_id;
COMMIT;

However, if user #15 also moved up a position at nearly the same time, there might be conflict.

Are there some strategies I can use to make sure that the updates don't conflict?

Answer 1

Don't move around relative positions. This way, an update to a single users' position means updating all users that shift positions. And concurrent updates are hard to get right, and expensive, too. Would create a lot of lock contention.

Instead, update an absolute score, which is independent from other users. Writes get a lot cheaper, and concurrent writes for distinct users are no problem at all. The relative position then only materializes by sorting users. That means reading is a lot more expensive than with pre-determined positions, but it actually works.

Maybe you don't need the actual, precise, absolute position at all times, and a snapshot that's updated at certain time intervals (or trigger events) is good enough? Consider a MATERIALIZED VIEW for that. The relative comparison of given users always works cheaply.