JA

Matching people into rooms of two or three with Redis sorted sets and Lua

Here is what this post covers:

Introduction

I’m building, as a side project, a chat service where people talk anonymously about a topic. In the previous post I wrote about the conversation that happens once you’re in a room — the WebSocket that starts at GET /ws/rooms/{roomID}.

This post covers the step before that: the matching that puts people who picked the same topic into rooms of two or three. The stack is Go / Redis / PostgreSQL.

What it needs to do

  • A user picks a topic and a room size (two or three), then waits
  • Once enough people are waiting under the same conditions, create a room (a conversation)
  • There are two API servers, so whichever server you hit, you join the same queue
  • Even with concurrent requests, one person must never end up in two rooms
  • If a three-person room is stuck waiting for a third, start it with two after 60 seconds

The overall flow

From the client’s side, there are only three APIs.

MethodPathPurpose
POST/api/matchingJoin the queue
GET/api/matchingAsk for the current state (waiting / matched)
DELETE/api/matchingStop waiting

The client doesn’t get pushed a notification when a match forms. It polls, asking with GET until the answer changes.

The overall matching flow. POST joins the queue; after that, every GET poll asks Redis whether a room can be formed, and once enough people are waiting the conversation is created in PostgreSQL Client API server Redis PostgreSQL POST /api/matching add to queue try to form a room 202 waiting repeat until matched GET /api/matching try to form a room when enough people are waiting participant list create conversation write conversation ID waiting / matched

The key point is that both POST and GET “try to form a room.” There’s no dedicated matching worker running on the side; the users’ own requests are what trigger matching.

The waiting queue is a Redis sorted set

The waiting queue lives in a Redis sorted set. A sorted set is a data type that gives each unique member a numeric score and keeps the members ordered by that score (official docs).

  • key: matching:queue:<topicID>:<size>
  • member: the user’s session token
  • score: when they started waiting (milliseconds)
matching:queue:42:3   (waiting for a 3-person room on topic 42)

  score (started)      member
  ─────────────────   ──────────
  1727300000000       token-A   ← oldest
  1727300015000       token-B
  1727300040000       token-C

Because the score is a timestamp, taking the lowest scores first (ZPOPMIN) is all it takes to match in arrival order. And since “how long has this person been waiting” lives inside the queue itself, checks like these can be answered from the sorted set alone:

  • Drop anyone who has waited five minutes or more (timeout)
  • Check whether the person at the front has waited 60 seconds or more (fallback)

I considered a List, but a List element can’t carry a timestamp, so timeout checks would have to look at a separate key. That’s why I went with a sorted set.

A user is only ever in one of three states

At any moment, a user is in exactly one of these three states.

User state transitions. POST moves Idle to Waiting, enough people moves Waiting to Matched, and DELETE or a timeout returns to Idle Idle Waiting Matched POST (join the queue) DELETE / 5-min timeout enough people DELETE (leave the room)

Each state is represented by Redis keys.

StateRedis keys
Idle (doing nothing)none
Waitingmatching:waiting:<token> + a member in the queue
Matched (room formed)matching:room:<token>

Put another way, “one person never ends up in two rooms” means every move between these states happens in a single step.

Preventing double assignment: do it all in one Lua script

With two servers, this race is possible:

A race where two servers read the same queue at almost the same time, and each takes A, B and C off it and puts them in a different room Server 1 Redis Server 2 read queue (A, B, C) read queue (A, B, C) A, B, C into room 1 A, B, C into room 2 A, B and C end up in two rooms at once

The problem is that another server can slip in between the “read” and the “take.”

So the whole room-forming step is a single Lua script that runs inside Redis. Redis doesn’t interleave other commands while a Lua script is running, so the whole script behaves as one operation. The official docs cover how Lua scripts are written and run in Redis.

Roughly, this is all the script does:

-- 1. Remove people whose wait has expired
redis.call('ZREMRANGEBYSCORE', queueKey, '-inf', timeoutBefore)

-- 2. Decide how many to take
local waiting = redis.call('ZCARD', queueKey)
local take = 0
if waiting >= size then
  take = size                      -- enough people
elseif size == 3 and waiting >= 2 then
  -- 3-person room with only 2 waiting: if the oldest has waited 60s+, match the 2
  local oldest = redis.call('ZRANGE', queueKey, 0, 0, 'WITHSCORES')
  if tonumber(oldest[2]) <= fallbackBefore then
    take = 2
  end
end
if take == 0 then return {} end

-- 3. Pop oldest first, and move each participant from "waiting" to "has a room"
local participants = {}
local popped = redis.call('ZPOPMIN', queueKey, take)
for i = 1, #popped, 2 do
  local token = popped[i]
  redis.call('DEL', waitingPrefix .. token)
  -- write room information to roomPrefix .. token (fields omitted)
  table.insert(participants, token)
end
return participants

“Clean up expired entries → decide the count → pop → rewrite state” runs as one unit, with nothing able to cut in partway. So even if both servers run it at the same moment, the people the first run popped are already gone from the queue by the time the second run looks at it.

Optimistic locking with WATCH / MULTI was also on the table, but on a conflict the app has to retry. Conflicts go up exactly when things are busy, which is when retries are most likely to keep failing. I didn’t like that, so I went with Lua.

Joining the queue (Enqueue) is also a Lua script, and it’s where people who “already have a room” or “are waiting in another queue” get turned away.

The fallback for three-person rooms

A three-person room never starts if the third person never shows up. Late at night, or while the service is new, there aren’t many people around, so users tend to wait and wait and then give up.

So I made a rule: if the person at the front of a three-person queue has waited 60 seconds or more, and at least two people are waiting, start with two.

The room-forming decision. If the chosen number of people are waiting, match at that size; if it is a three-person room with two or more waiting and the first has waited 60 seconds or more, match the first two; otherwise keep waiting Try to form a room Enough people for the chosen size? yes Match at that size no 3-person room with 2 or more waiting? no yes Has the first one waited 60s or more? no Keep waiting yes Match the first two

When a match forms, the API response includes the actual room size (room_type), and the client uses that value to decide how to render the screen.

This check, too, is triggered by the waiting users’ own GET polls. There’s no timer that fires when 60 seconds pass; the match forms the next time someone asks for their state.

What if a server dies between Redis and PostgreSQL?

After the room is popped, the conversation is written to the conversations table in PostgreSQL. The problem case is “popped from Redis, but the server died before writing to the DB.”

There are two layers of protection for this.

After the Lua pop, the conversation is created in PostgreSQL. On success the conversation ID is written to the room key and its TTL extended; on failure the room key is deleted; if the server dies, the room key expires on its own thanks to a 30-second TTL Pop with Lua room key gets a 30s TTL Create conversation in PostgreSQL success Write conversation ID extend the TTL to 10 min failure Delete the room key back to before waiting server died Room key expires on its own after 30s
  • The DB write returned an error → delete the room key and put the participants back to their state before waiting
  • The whole server died → the room key had a 30-second TTL from the start, so it expires on its own and things go back to how they were

Either way, from the user’s side it just looks like “one wait was wasted,” and they can queue up again. The judgment call here is that wasting one wait is better than creating a conversation twice.

Also, while the room key exists but no conversation ID has been written to it yet, the client gets waiting back — because there’s no conversation to enter yet.

Checks before joining the queue

Finally, here are the checks that run before someone joins the queue.

  1. Is the room size 2 or 3?
  2. Rate limiting (don’t let the same IP queue up over and over in a short time) → 429 with Retry-After
  3. Are they on the ban list? → 403
  4. Does the topic exist, and is it active? → 400
  5. Are they already waiting in another queue, or do they already have a room? → 409

The ban list and topic data belong to other modules. The matching module only asks them through interfaces and never touches their DB tables directly.

Wrapping up

  • The waiting queue is a Redis sorted set (score = when they started waiting)
  • Popping a room is done atomically in a single Lua script, which prevents double assignment
  • Three-person rooms fall back after 60 seconds and start with two
  • If a server dies before the DB write, a 30-second TTL puts things back on its own
  • There’s no dedicated worker; users’ polling is what triggers matching

For the requirement “share one waiting queue across several servers without ever assigning someone twice,” Redis sorted sets plus Lua turned out to be pleasantly simple to write, and I’m happy with it.

Right now, matches are announced through polling. As I wrote in the previous post, that’s so I don’t have to hold a connection open for everyone who’s still waiting. If I want matches announced sooner, pushing them over WebSocket is the next improvement on the list.