15. 매치메이킹: 한 플레이어가 동시에 두 매치에 배정되는 상황 — C#
난이도 중해설 — 매치메이킹: 한 플레이어가 동시에 두 매치에 배정되는 상황 — C#
난이도: 중상
답변 프레임워크: 요약 → 문제 분류 → 원인 → 수정안 → 더 나은 설계
요약
핵심 결함은 여러 모드 매처가 병렬로 도는데, "후보가 Searching 인지 검사" 와 "InMatch 로
확정" 사이에 교차 모드 락이 없다는 점이다. 같은 플레이어가 "랭크 3v3" 와 "일반 3v3" 두 큐에
있을 때, 두 매처 스레드가 거의 동시에 (A)에서 그를 Searching 으로 보고 각자 매치에 넣은 뒤
(B)에서 둘 다 InMatch 로 확정 → 이중 배정. 게다가 큐 컬렉션(List)을 락 없이 동시
순회·Remove 하므로 자료구조 손상과, 순회 중 같은 리스트를 수정하는
InvalidOperationException("Collection was modified") 도 발생한다. 정답 한 줄: 플레이어
배정은 플레이어 단위로 원자적으로 "선점(claim)"하고(CAS/락), 큐 조작은 전역(또는 샤드) 락
아래에서 한다.
문제점
(A)+(B) 교차 모드 이중 배정 — TOCTOU (동시성) ★간판
- 증상: 한 플레이어가 두 매치(서로 다른 모드)에 동시에 들어간다. 한쪽 매치는 인원이 비거나, 플레이어가 두 게임에 입장 시도하며 세션이 꼬인다.
- 재현 조건: 플레이어 X 가 mode1, mode2 큐에 동시 등록. 매처1(mode1)·매처2(mode2)가
병렬로
TryFormMatch실행. 둘 다 (A)에서 X 를Searching으로 읽고 후보에 포함 → 각자 (B) 진입 전까지 아무도InMatch로 못 바꿈 → 둘 다 X 를 매치에 넣고 InMatch 확정. - 근본 원인: 플레이어 "선점"이 원자적이지 않다. 검사(
State==Searching)와 확정 (State=InMatch)이 분리돼 있고, 서로 다른 매처 스레드 간 동기화가 없다. 플레이어를 잡는 단위가 모드 큐가 아니라 플레이어여야 하는데 그 단위의 원자 연산이 없다.
(A) Where(...).Take(...) 와 (B) Remove 의 컬렉션 동시 수정 (동시성/메모리)
- 증상:
InvalidOperationException("Collection was modified; enumeration may not execute") 또는 요소 유실/중복.List는 스레드 세이프하지 않다. - 재현 조건: 한 매처가
q.Where(...)지연 평가로 큐를 순회하는 동안 다른 매처가 같은(또는 공유된) 큐에서Remove. 특히 (B)의_queues[m].Remove(p)는 다른 모드의 큐를 건드리므로 그 모드 매처와 정면 충돌. - 근본 원인: 큐 자료구조에 대한 임계 구역 부재.
(B) 등록 모드 목록과 실제 큐의 정합성 — 부분 제거 (정확성)
- 증상:
p.QueuedModes가 최신이 아니거나(취소로 한 모드만 빠졌는데 목록 미갱신), 도중 예외가 나면 일부 큐에서만 제거돼 플레이어가 유령처럼 한 큐에 남는다. - 근본 원인: 상태 전이와 "모든 큐 제거"가 하나의 트랜잭션(원자 단위)이 아니다.
매치 취소/재매칭과의 경합 (동시성)
- 매치 취소로
InMatch → Searching으로 되돌리는 경로와 (A)(B) 가 락을 공유하지 않으면, 되돌리는 순간 매처가 그를 다시 잡아 또 이중 배정/유실이 생긴다.
수정안
핵심: ① 매칭 전역(또는 MMR 버킷 샤드) 락 아래에서 후보 수집~배정~큐 제거를 한 임계 구역으로, ② 플레이어 선점을 원자적 claim(상태 CAS)으로, ③ 큐 스냅샷을 떠서 순회 중 수정 회피.
private readonly object _gate = new object(); // 매칭 도메인 락(또는 버킷별 샤드 락)
public Match TryFormMatch(int mode)
{
lock (_gate)
{
var q = _queues[mode];
// 스냅샷으로 후보 선정(지연 평가 + 동시 수정 회피)
var candidates = q.Where(p => p.State == MatchState.Searching)
.Take(_teamSize).ToList();
if (candidates.Count < _teamSize) return null;
// 같은 락 안이므로, 여기서 본 Searching 은 확정될 때까지 불변
var match = new Match { Mode = mode };
foreach (var p in candidates)
{
p.State = MatchState.InMatch; // 선점 확정
foreach (int m in p.QueuedModes.ToList()) // 사본으로 순회(원본 Remove 안전)
_queues[m].Remove(p);
match.PlayerIds.Add(p.Id);
}
return match;
}
}
모든 매처가 같은
_gate를 공유하면, mode1 과 mode2 매처가 같은 플레이어를 동시에 잡는 일이 불가능해진다(직렬화).QueuedModes.ToList()로 사본 순회해야 순회 중 원본Remove의 예외를 피한다.
전역 락이 처리량 병목이면, 플레이어 단위 원자 선점으로 락 범위를 줄인다:
// 전제: enum 은 Interlocked 오버로드가 없으므로 WaitingPlayer 에 int 백킹 필드
// public int StateInt; // 0=Searching, 1=InMatch (State 프로퍼티로 래핑)
// 를 두고, 그 int 를 CAS 한다.
// CAS 로 Searching -> InMatch 를 시도, 실패하면 다른 매처가 이미 잡은 것
bool TryClaim(WaitingPlayer p) =>
Interlocked.CompareExchange(ref p.StateInt,
(int)MatchState.InMatch, (int)MatchState.Searching) == (int)MatchState.Searching;
// 후보 전원 claim 에 성공해야 매치 확정, 일부 실패 시 성공분을 롤백(Searching 복구)
큐 제거는 여전히 큐 락이 필요하지만, "누가 그 플레이어를 갖는가"는 CAS 가 단번에 결정한다.
더 나은 설계
1) 매처 단일화 / 파티셔닝
- 모드별로 매처를 따로 두는 대신, 플레이어를 MMR 버킷으로 샤딩하고 한 버킷은 단일 스레드가 소유해 모든 모드를 함께 본다. 한 플레이어가 항상 한 매처에만 속해 교차 배정이 구조적으로 불가능. 트레이드오프: 버킷 경계 플레이어 매칭 품질 약간 손해.
2) 2단계 커밋(제안 → 수락)
- 매처는 "매치 제안"만 만들고(플레이어를 Reserved 상태로 잠금), 전원이 수락하면 확정, 하나라도 거절/타임아웃이면 전원 롤백(Searching 복구). 이중 배정 없이 취소도 깔끔.
3) 멀티 큐잉의 단일 소유
- 플레이어가 여러 모드에 있어도, 매칭 시스템 내부에서는 "이 플레이어를 잡을 권리"를 단일 토큰/락으로 관리. 잡힌 즉시 다른 모든 모드에서 보이지 않게 된다(논리 삭제).
4) 큐 자료구조
List.Remove(p)는 O(n) 이라 대형 큐에서 비싸다. 인덱스 가능한 우선순위 구조 + 지연 삭제(tombstone) 또는LinkedList노드 핸들 보관으로 O(1) 제거.
면접 포인트
- 핵심: 매칭의 동시성은 "잡는 단위가 무엇인가" 가 관건 — 모드 큐가 아니라 플레이어를 원자적으로 선점해야 하고, 멀티 큐잉에서 교차 매처 경합을 어떻게 직렬화하느냐.
- 예상 질문:
- "왜 한 플레이어가 두 매치에 들어가나?" → 검사-확정 비원자 + 매처 간 동기화 부재 (TOCTOU). 멀티 큐잉이 이를 노출.
- "전역 락이 병목이면?" → MMR 버킷 샤딩으로 한 플레이어 = 한 매처, 또는 플레이어 단위 CAS 선점 + 실패 롤백.
- "매치 취소와 재매칭이 겹치면?" → 상태 전이를 같은 락/CAS 도메인에서. 2단계 커밋으로 예약→확정/롤백을 원자화.
분류 메모: 이 문제는 매치메이킹(카탈로그 12.매치메이킹) 도메인 로직이지만 결함의 본질은 교차 스레드 TOCTOU + 공유 컨테이너 동시 변경이라 동시성 색채가 짙다. content_gamelogic 에 둔 것은 매칭이라는 게임 로직 맥락과 기존 content13(시즌 마감 경합)·content4(경매 입찰) 등 동시성 결함이 이미 이 카테고리에 다수 있는 선례에 따른 것이다. 기존 content4(단일 자원 최고가 경합)·session3(계정당 1세션 직렬화)과 달리 "여러 큐에서 한 엔티티를 선점하고 전 큐에서 일관 제거"라는 축이 신규다.
해설 — 매치메이킹: 한 플레이어가 동시에 두 매치에 배정되는 상황 — C++
난이도: 중상
답변 프레임워크: 요약 → 문제 분류 → 원인 → 수정안 → 더 나은 설계
요약
C# 트윈과 동일한 본질 결함(플레이어 선점이 비원자 → 교차 모드 이중 배정 TOCTOU)에 더해,
C++ 에서는 unordered_map::operator[] 묵시 삽입, 다른 매처 스레드와의 vector 동시
변경 데이터 레이스 UB, 순회 중 erase 로 인한 위험이 추가된다. 플레이어 X 가 mode1,
mode2 큐에 있을 때 두 매처가 동시에 (A)에서 X 를 Searching 으로 보고 각자 매치에 넣은 뒤
(B)에서 둘 다 InMatch 로 확정한다. 그리고 (B)의 queues_[m] 가 다른 모드 매처가 동시에
순회/erase 중인 벡터를 건드려 UB. 정답 한 줄: 플레이어를 원자적으로 선점(상태 CAS)하고,
큐 조작은 매칭 도메인 락(또는 샤드 락) 아래에서.
문제점
(A)+(B) 교차 모드 이중 배정 — TOCTOU (동시성) ★간판
- 증상: 한 플레이어가 두 매치(다른 모드)에 동시에 배정된다.
- 재현 조건: X 가 mode1, mode2 에 멀티 큐잉. 매처1·매처2 병렬 실행. 둘 다 (A)에서 X 를
Searching으로 읽고 후보에 포함 → 둘 다 (B)에서state = InMatch. 검사~확정 사이에 매처 간 동기화가 없다. - 근본 원인: "이 플레이어를 누가 갖는가"의 원자적 선점이 없다. 잡는 단위가 모드 큐가 아니라 플레이어여야 하는데 그 단위 원자 연산이 부재.
(B) 교차 큐 vector 동시 변경 — 데이터 레이스 / 이터레이터 무효화 UB (메모리) ★C++ 변별
- 증상: 비결정적 크래시·요소 손상·중복/유실.
- 재현 조건: 매처1 이 (A)에서
q(mode1) 를 범위 기반 for 로 순회하는 동안, 매처2 가 (B)에서queues_[mode1].erase(...)로 그 벡터를 재배치 → 순회 포인터 무효화(UB). 두 매처가 동시에 같은 벡터에erase/순회해도 UB. - 근본 원인: 공유
vector에 임계 구역 없음.shared_ptr의 refcount 는 atomic 이지만 컨테이너 본체와 노드 상태(p->state)는 보호되지 않는다.
(B) queues_[m] 묵시 삽입 — C++ 고유 (정확성)
- 증상:
p->queuedModes에 (취소 등으로) 더 이상 큐가 없는 모드 번호가 남아 있으면,queues_[m]가 그 모드의 빈 큐를 새로 만든다(의도치 않은 맵 증식).find로 검증해야.
(B) 상태 전이 + 전체 큐 제거 비원자 — 부분 제거 (정확성)
- 도중 예외/경합으로 일부 큐에서만 빠지면 플레이어가 유령으로 한 큐에 잔류. 상태 전이와 "모든 큐 제거"가 한 트랜잭션이어야 한다.
매치 취소/재매칭 경합
InMatch → Searching복구 경로가 (A)(B) 와 락/CAS 도메인을 공유하지 않으면 되돌리는 순간 다시 잡혀 이중 배정/유실.
수정안
핵심: ① 매칭 도메인 락(또는 MMR 버킷 샤드 락)으로 후보 수집~확정~큐 제거를 한 임계 구역으로,
② 플레이어 선점을 원자 CAS 로, ③ operator[] 대신 find, ④ 스냅샷 후 erase.
#include <mutex>
#include <atomic>
// WaitingPlayer::state 를 std::atomic<MatchState> 또는 atomic<int> 로
std::mutex gate_; // 매칭 도메인 락(또는 버킷별 샤드 락)
std::shared_ptr<Match> TryFormMatch(int mode) {
std::lock_guard<std::mutex> lk(gate_);
auto qit = queues_.find(mode);
if (qit == queues_.end()) return nullptr;
auto& q = qit->second;
std::vector<std::shared_ptr<WaitingPlayer>> cands;
for (auto& p : q) {
if (p->state == MatchState::Searching) {
cands.push_back(p);
if ((int)cands.size() == teamSize_) break;
}
}
if ((int)cands.size() < teamSize_) return nullptr;
auto match = std::make_shared<Match>(); match->mode = mode;
for (auto& p : cands) {
p->state = MatchState::InMatch; // 같은 락 안 → 확정 불변
for (int m : p->queuedModes) {
auto it = queues_.find(m); // 묵시 삽입 방지
if (it == queues_.end()) continue;
auto& mq = it->second;
mq.erase(std::remove(mq.begin(), mq.end(), p), mq.end());
}
match->playerIds.push_back(p->id);
}
return match;
}
모든 매처가
gate_를 공유하면 교차 모드 동시 선점이 불가능(직렬화). 처리량이 문제면 MMR 버킷별 샤드 락 + 플레이어 단위compare_exchange(Searching→InMatch) 로 락 범위를 좁히고, 큐 erase 만 짧게 보호한다.
더 나은 설계
1) MMR 버킷 샤딩 = 한 플레이어 한 매처
- 모드별 매처 대신 플레이어를 MMR 버킷으로 샤딩, 한 버킷을 단일 스레드가 소유해 모든 모드를 함께 본다. 교차 배정이 구조적으로 불가능. 트레이드오프: 버킷 경계 매칭 품질 손해.
2) 2단계 커밋(제안 → 수락)
- 매처는 제안만(Reserved 잠금), 전원 수락 시 확정·불일치 시 전원 롤백. 이중 배정 없이 취소가 깔끔.
3) O(1) 큐 제거
vector::erase(remove-erase) 는 O(n).std::list노드 핸들 보관 또는 tombstone 지연 삭제로 대형 큐에서 비용 절감.
4) shared_ptr/소유권 명확화
shared_ptrrefcount 는 atomic 이지만 가리키는 객체 필드는 별개. "atomic 포인터 ≠ atomic 객체"를 명확히 인지하고, 노드 상태는 별도 동기화.
면접 포인트
- 핵심: 잡는 단위는 플레이어(원자 선점)이고, 멀티 큐잉의 교차 매처 경합을 어떻게
직렬화/샤딩하느냐. C++ 에선 공유 컨테이너 동시 변경 UB 와
operator[]묵시 삽입까지. - 예상 질문:
- "왜 두 매치에 들어가나?" → 검사-확정 비원자 + 매처 간 동기화 부재(TOCTOU).
- "shared_ptr 라서 안전하지 않나?" → refcount 만 atomic, 객체 필드/컨테이너는 아님.
- "전역 락 없이 줄이려면?" → MMR 버킷 샤딩(한 플레이어 한 매처) 또는 상태 CAS 선점 + 실패 롤백.
분류 메모: 매치메이킹(카탈로그 12) 도메인 로직이지만 결함의 본질은 교차 스레드 TOCTOU + 공유 컨테이너 동시 변경이라 동시성 색채가 짙다. content_gamelogic 배치는 매칭이라는 게임 로직 맥락과 기존 content13/4 동시성 문제 선례에 따른 것. 기존 content4(단일 자원 경합)· session3(계정당 1세션)과 달리 "여러 큐에서 한 엔티티 선점 + 전 큐 일관 제거" 축이 신규다.