난이도: 중상

모범답안 — 생산자-소비자 큐 설계

1. 생산자/소비자 수에 따른 분류

큐를 쓰는 스레드 수로 4가지로 나눈다.

• SPSC(Single Producer Single Consumer): 한 스레드만 넣고 한 스레드만 뺀다. head는 소비자만, tail은 생산자만 갱신하므로 두 인덱스에 대한 경쟁 쓰기가 없다. 각 인덱스를 원자적으로 읽고 적절한 acquire/release만 걸면 락 없이(lock-free), 심지어 CAS 없이 구현된다. 가장 빠르고 예측 가능.
• MPSC(Multi Producer Single Consumer): 여러 생산자가 tail을 두고 경쟁 → tail 갱신에 CAS 필요. 소비 측은 단순.
• SPMC: 반대로 head에 CAS 경쟁.
• MPMC: 양쪽 다 경쟁 → 가장 복잡. CAS 또는 락, 시퀀스 번호 기반 슬롯(Vyukov 큐) 같은 기법이 필요.

게임 서버 매핑: 특정 클라이언트의 수신 스레드 → 그 세션 전용 로직 처리는 흔히 SPSC. 여러 세션 스레드가 하나의 DB 쓰기 워커로 보내면 MPSC. 스레드풀 워커들이 공용 잡 큐를 공유하면 MPMC. 가능하면 문제를 SPSC/MPSC로 좁히는 설계가 성능·정확성 모두에 유리하다.

2. 바운드 링버퍼 vs 무제한 큐

• 링버퍼(고정 크기 배열 + head/tail 인덱스, 2의 거듭제곱 크기로 마스킹):
  • 장점: 연속 메모리라 캐시 지역성이 좋다. push/pop 시 노드 할당이 없다 (미리 잡은 배열 재사용) → GC/malloc 압박 0, 지연 예측 가능.
  • "가득 참" 처리: 생산자가 tail이 head를 따라잡으면 가득 참. 이때 블로킹, 거절, 덮어쓰기(최신 우선) 중 정책을 정한다. 즉 바운드는 백프레셔 지점을 강제한다.
• 무제한 연결 리스트 큐: 크기 제한이 없어 "가득 참"이 없지만, 노드마다 할당 (캐시 미스·GC 압박), 그리고 무엇보다 생산자가 빠르면 무한히 커져 메모리 폭증. 실시간 서버에서는 위험. 링버퍼가 기본, 무제한은 정말 필요할 때만.

3. 블로킹 vs 논블로킹 대기

• (a) 조건 변수 블로킹: 큐가 비면 소비자가 잠들고, 넣으면 깨운다. CPU를 안 태우고 대기하므로 유휴 시 효율적. 단 깨우기 지연(수 µs~)과 커널 진입 비용이 있어 초저지연 경로엔 불리. 술어는 반드시 while로 재검사.
• (b) 스핀/양보: 짧게 바쁜-대기하다가 yield/pause. 항목이 곧 온다고 기대되는 초저지연 핫패스에서 깨우기 지연을 없앤다. 대신 CPU를 태운다 → 코어 수·전력 트레이드오프. 하이브리드(짧게 스핀 후 블로킹)가 실용적.
• (c) try_push/try_pop(즉시 실패): 절대 안 막히고 실패를 반환. 호출자가 대체 동작(드롭, 다른 일 하기)을 결정. 틱 루프처럼 "이번 틱에 없으면 다음 틱" 구조에 적합.
• 요약: 처리량·유휴 효율 = 블로킹, 지연 최소 = 스핀, 제어권·논블로킹 = try 계열.

4. 백프레셔

• 생산자가 소비자보다 지속적으로 빠르면, 무제한 큐는 지연과 메모리가 무한히 증가한다(latency가 계속 늘고 결국 OOM). 큐 길이는 곧 지연이다(리틀의 법칙).
• 백프레셔 수단:
  • 블로킹: 큐가 차면 생산자를 멈춘다. 소비 속도로 생산을 자동 제한(가장 정확). 단 생산자가 네트워크 수신 스레드면 그 연결 전체가 느려질 수 있어 격리 필요.
  • 거절/드롭: 넘치면 새 항목을 버리거나(최근 우선), 오래된 것을 버린다. 손실 허용 데이터(위치 스냅샷, 로그, 메트릭)에 적합.
  • 샘플링/병합: 같은 종류 업데이트를 최신값으로 합쳐 큐 길이를 줄인다(coalescing).
  • 생산 속도 조절: 상류에 rate limit.
• 게임에서의 선택: 입력 커맨드 큐는 유실이 곧 조작 손실이라 블로킹/충분한 버퍼 + 이상 시 연결 종료. 위치 브로드캐스트·로그·메트릭 큐는 최신 우선 드롭이 낫다(오래된 위치는 쓸모없음). "무엇을 버려도 되는가"가 정책을 결정한다.

5. 거짓 공유와 배치

• 거짓 공유: MPMC 링버퍼에서 head와 tail이 같은 캐시 라인(보통 64B)에 있으면, 생산자(tail 갱신)와 소비자(head 갱신)가 서로의 라인을 계속 무효화시켜 성능이 급락한다. head와 tail을 각각 별도 캐시 라인에 정렬(alignas(64)/패딩)해 분리한다. 또한 각자가 상대 인덱스를 캐시해 두고 필요할 때만 다시 읽으면 라인 공유 빈도를 줄인다.
• 배치(batching): 소비자가 한 번에 여러 항목을 꺼내면(예: 한 틱에 큐를 통째로 드레인), 동기화 연산 횟수와 캐시 라인 왕복이 항목당에서 배치당으로 줄어 처리량이 크게 오른다. 대신 첫 항목의 처리 지연이 배치가 모일 때까지 늘 수 있어(지연↔처리량) 틱 주기·배치 상한으로 균형을 잡는다.

한 줄 요약

생산자/소비자 수로 SPSC~MPMC를 나눠 가능한 한 경쟁을 줄이고, 실시간 서버는 바운드 링버퍼로 백프레셔 지점을 강제하며, 대기 전략(블로킹/스핀/try)과 드롭 정책은 "지연·CPU·손실 허용치"로 고른다. head/tail 캐시 라인 분리와 배치로 처리량을 끌어올린다.