랜덤 매칭이 두 번 교착에 빠진 이야기

왜 공부했나

블로그에 붙여둔 오목에 온라인 대전을 넣고 싶었다. 다만 조건이 하나 있었다. 서버 프로세스를 띄우지 않는다. 정적 사이트에 붙는 미니게임인데 매칭 서버를 따로 운영할 생각은 없었다.

그래서 Firebase Realtime Database(이하 RTDB) 하나만 놓고, 클라이언트끼리 알아서 짝을 짓게 만들기로 했다. 전용 서버가 있었다면 매칭 대기열은 그냥 서버 메모리 안의 큐 하나고 락 한 번이면 끝난다. 그게 사라지니 매칭이 통째로 분산 합의 문제가 됐고, 결과적으로 교착에 두 번 빠졌다.

만들려던 구조

omok_queue/{티켓키}   → { t: 서버시각, g: 매칭된 게임ID }
omok_games/{게임ID}/m/{수번} → { r, c }   착수
  • 대기열에 티켓을 하나 올리고 기다린다 → 누가 나를 잡으면 나는 흑(선수)
  • 대기열에 누가 있으면 그 티켓을 잡는다 → 내가 백(후수)
  • 착수는 m/{수번}에 트랜잭션으로 기록하고 양쪽이 onChildAdded로 받는다
  • 티켓과 대국방 모두 onDisconnect로 자동 삭제 — 대국이 끝나면 DB에 남는 게 없다

문제는 전부 “대기열에 누가 있으면 잡는다"는 저 한 줄에서 터졌다.

1차 교착 — 둘 다 줄만 섰다

처음 구현은 단순했다. 대기열을 한 번 훑고, 아무도 없으면 내 티켓을 올리고 기다린다.

두 명이 거의 동시에 ‘상대 찾기’를 누르면 이렇게 된다.

sequenceDiagram
    participant A as 플레이어 A
    participant Q as omok_queue
    participant B as 플레이어 B

    A->>Q: 대기열 스캔
    B->>Q: 대기열 스캔
    Q-->>A: 비어 있음
    Q-->>B: 비어 있음
    A->>Q: 내 티켓 등록
    B->>Q: 내 티켓 등록
    Note over A,B: 둘 다 상대가 있는데 둘 다 기다리기만 한다

교과서적인 check-then-act 경합이다. 확인한 시점과 행동한 시점 사이에 상대가 끼어들었는데, 스캔이 1회뿐이라 다시 볼 기회가 없었다.

고친 방향은 스캔을 반복 루프로 바꾸는 것이었다.

[대기열에서 내려오기] → [잡아보기] → [없으면 다시 줄서기] → 잠시 후 반복

여기에 두 가지를 더 얹었다.

  • 재시도 간격에 지터(2.2~4.4초) — 같은 주기로 재시도하면 동시 검색자끼리 위상이 계속 맞아서 영원히 서로를 비껴간다
  • “잡는 동안에는 내가 대기열에 없다"는 불변식 — 잡으러 나갈 때 내 티켓을 먼저 내린다. 그래야 A가 B를 잡는 동시에 B도 A를 잡아 한 사람이 두 대국에 들어가는 일이 없다

내려오는 것도 그냥 삭제하면 안 됐다. 내려오는 찰나에 누가 나를 잡았을 수 있어서, 삭제도 트랜잭션으로 하고 이미 매칭됐으면 삭제를 취소한다.

res = await f.runTransaction(ref, function(cur){
  if(cur && cur.g) return;   // 이미 매칭됨 → 삭제 취소(abort)
  return null;               // 삭제
});
if(!res.committed) return false;   // 매칭됐다 → 티켓 리스너가 대국으로 넘긴다

2차 교착 — 트랜잭션이 매번 abort

루프로 바꾸고 나니 증상이 달라졌다. 대기열에는 티켓이 정상적으로 오갔다. 서로 보이기는 하는데 아무도 잡히지 않았다. 양쪽 다 ‘상대를 찾는 중’에서 멈췄다.

원인은 RTDB 트랜잭션의 동작 방식이었다.

RTDB 트랜잭션은 해당 경로가 로컬 캐시에 없으면, 핸들러를 먼저 null로 호출한다.

트랜잭션 핸들러는 낙관적 동시성 제어라 “현재 값"을 받아 새 값을 반환하는 구조인데, SDK가 그 경로의 값을 모르면 일단 null로 한 번 불러본다. 핸들러가 undefined를 반환하면 트랜잭션은 그 자리에서 abort된다 — 서버에 물어보지도 않고.

내 코드가 정확히 그랬다.

runTransaction(상대티켓, function(cur){
  if(cur === null) return;   // ← 캐시 미스면 여기서 항상 중단
  if(cur.g) return;
  cur.g = gid; return cur;
});

상대 티켓 경로는 한 번도 구독한 적이 없으니 항상 캐시 미스였다. 그래서 매번 null 한 번 받고 abort. 대기열은 보이는데(그건 목록 조회라 별개다) 잡는 건 100% 실패하는 상태였다.

Node로 따로 재현해서 확인했다.

  • 캐시 미스 상태 → 핸들러가 null 한 번만 받고 aborted
  • 리스너로 예열한 뒤 → 첫 호출부터 실제 값이 오고 committed

수정은 검색 중에 대기열 전체를 구독해 캐시를 예열하는 것이었다.

onl.queueUn = f.onValue(f.ref(f.db, Q_PATH), function(snap){
  onl.queueSnap = snap;
  done();
  if(onl.state === 'searching' && hasClaimable(snap)) attempt();
});

부수 효과가 오히려 더 좋았다. 캐시가 채워지니 트랜잭션이 첫 호출부터 실제 값을 받고, 상대가 대기열에 나타나는 즉시 반응할 수도 있게 됐다.

대칭성 깨기

캐시를 고쳐도 A와 B가 서로를 동시에 잡으러 가면 둘 다 실패할 수 있다. 한쪽이 이기게 만들어야 한다.

RTDB의 push 키는 시간순으로 사전식 정렬되는 성질이 있다. 그걸 그대로 썼다.

if(myKey && ch.key >= myKey) return;   // 나보다 나중에 온 사람은 안 잡는다

나보다 먼저 온 티켓만 잡는다. 그러면 A와 B 사이에서 잡으러 가는 방향은 항상 한쪽뿐이라 상호 claim 자체가 성립하지 않는다. 별도의 우선순위 필드도, 추가 라운드 트립도 필요 없다.

루프를 죽이지 않기

또 하나 물렸던 것. 재시도 예약이 중간 return 경로에서 누락돼 있었다.

attempt()는 상태 확인 때문에 중간에 빠져나가는 지점이 많다. 그중 한 곳이라도 다음 시도를 예약하지 않으면 루프가 통째로 죽어서 영영 ‘찾는 중’에 머문다. 그래서 예약을 finally로 옮겼다.

}finally{
  onl.busy = false;
  // 어느 경로로 빠져나왔든 아직 검색 중이면 반드시 다음 시도를 예약한다.
  stopRetry();
  if(onl.state === 'searching'){
    const soon = hasClaimable(onl.queueSnap);   // 잡을 상대가 보이면 바로 재시도
    onl.retryTmr = setTimeout(attempt, soon ? 150 + Math.random() * 250
                                            : 2200 + Math.random() * 2200);
  }
  render();
}

잡을 상대가 보일 때는 0.150.4초, 아니면 2.24.4초. 덕분에 매칭 체감이 ~1초로 줄었다.

시계를 믿지 않기

유령 티켓(창을 강제 종료해서 onDisconnect가 못 돈 경우) 청소도 문제였다. 처음엔 Date.now()로 60초가 지났는지 봤는데, PC 시계가 1분 이상 어긋난 사람이 접속하면 멀쩡히 기다리는 사람들을 전부 지워버렸다.

RTDB는 .info/serverTimeOffset으로 서버와의 시각 차이를 알려준다. 이걸 보정해서 쓰면 로컬 시계와 무관해진다.

function serverNow(){ return Date.now() + onl.tOffset; }   // 서버 기준 시각

여기에 .info/connected도 화면에 노출시켰다. 네트워크가 막히면 SDK가 조용히 쓰기를 큐잉만 해서 겉보기엔 그냥 멈춘 것처럼 보이는데, ‘서버에 연결하는 중’으로 구분해주면 사용자가 상황을 알 수 있다.

정리

  • check-then-act은 한 번 확인으로 끝내면 안 된다. 스캔-등록 사이의 틈이 그대로 경합 구간이 된다. 반복 루프 + 지터가 기본
  • 낙관적 트랜잭션은 “현재 값"을 어디서 얻는지 알고 써야 한다. RTDB는 캐시가 없으면 null부터 주고, 그걸 모르면 서버에 닿지도 못하고 조용히 실패한다
  • 대칭을 깨면 경합이 사라진다. 정렬 가능한 ID로 방향을 한쪽으로 고정하는 게 가장 싼 해결책이었다
  • 재시도 루프는 죽을 수 있다. 예약은 finally처럼 반드시 지나는 자리에 둔다
  • 분산 환경에서 로컬 시계는 근거가 못 된다. 서버 시각 기준으로 통일한다

전용 서버였다면 락 한 줄로 끝났을 문제다. 서버를 없앤 대가로 이 전부를 직접 다뤄야 했는데, 덕분에 매칭 큐 경합이 왜 어려운지는 확실히 체감했다.