단일 갱신 큐 & 요청 대기 목록

1. Pattern 11 — 단일 갱신 큐 (Singular Update Queue)

문제: 여러 스레드가 동시에 WAL에 쓰려고 한다

WAL은 append-only 로그라서 어차피 한 번에 하나씩, 순서대로 써야 한다. 가장 먼저 떠오르는
방법은 락이다. 그런데 여기서 정확히 짚어야 할 것이 있다. 락도 "한 번에 하나"는 보장한다.
락의 문제는 상호 배제가 아니라 기다리는 방식에 있다.

락 방식에서는 요청을 처리하는 스레드 자신이 락을 잡으려고 블로킹된다. 스레드 100개가
append를 시도하면 99개가 잠들어 있고, 락이 풀릴 때마다 깨어나기 경쟁(컨텍스트 스위칭)을
한다. 스레드는 잠들어 있는 동안에도 스택 메모리를 점유하고, 경합 비용은 동시성이 올라갈수록
커진다. 처리량은 정체되는데 지연시간만 늘어나는 최악의 조합이다.

해법: 큐 하나 + 전용 스레드 하나

요청 스레드들 ──▶ [ 작업 큐 ] ──▶ 전용 스레드 1개 ──▶ WAL / 상태 갱신
   (넣고 바로 리턴)                (하나씩 순서대로 꺼내 처리)

모든 갱신 요청을 큐에 넣고, 전용 스레드 하나가 순서대로 꺼내 처리한다. 요청 스레드는
큐에 넣고 즉시 리턴한다. 블로킹이 아니라 비동기다. 결과는 나중에 받을 수 있도록 작업에
CompletableFuture 같은 응답 핸들을 붙여둔다.

Kotlin 코루틴과 Channel로 표현하면 다음과 같다.

class SingularUpdateQueue<T, R>(
    private val handler: suspend (T) -> R,
    scope: CoroutineScope,
) {
    private data class Work<T, R>(val item: T, val result: CompletableDeferred<R>)
    private val channel = Channel<Work<T, R>>(capacity = 1000)  // bounded!

    init {
        scope.launch {                    // 소비자는 단 하나의 코루틴
            for (work in channel) {
                work.result.complete(handler(work.item))
            }
        }
    }

    suspend fun submit(item: T): Deferred<R> =
        CompletableDeferred<R>().also { channel.send(Work(item, it)) }
}

이 구조가 주는 네 가지 이점

첫째, 상태에 락이 아예 필요 없어진다. WAL 파일이든 인메모리 상태든 오직 한 스레드만
만지므로, 동기화 코드 없는 순수한 단일 스레드 로직으로 작성할 수 있다. 경합 버그(race
condition)의 가능성이 구조적으로 제거되고, 코드를 추론하기 쉬워진다.

둘째, 순서가 공짜로 보장된다. 큐는 FIFO이므로 들어온 순서가 곧 처리 순서다. 복제
로그처럼 "순서가 곧 정합성"인 시스템에서 이것은 부가 기능이 아니라 핵심 요구사항이다.

셋째, 배칭이 자연스러워진다. 지난 글에서 다룬 그룹 커밋을 떠올려 보자. 전용 스레드가
큐를 비울 때 "지금 쌓여 있는 것 전부"를 꺼내 한 번의 fsync로 묶는 것이 아주 쉽다. 락
방식에서는 이런 배칭을 구현하기가 몹시 어색하다. 부하가 높을수록 배치가 커져 처리량이
오히려 좋아지는, 부하에 우아하게 대응하는 특성이 생긴다.

넷째, 호출자가 블로킹되지 않는다. 요청 스레드는 큐에 넣고 다른 일을 하러 간다.
스레드가 잠들어서 낭비되는 일이 없다.

반드시 챙겨야 할 것 — 유한 큐와 배압(backpressure)

큐를 무한(unbounded)으로 두면 소비 속도보다 유입이 빠를 때 큐가 무한히 자라 OOM으로
죽는다. 큐는 반드시 크기를 제한하고, 가득 찼을 때의 정책을 정해야 한다. 넣는 쪽을 잠시
블로킹하거나(위 코드의 channel.send가 이 방식), 즉시 에러를 반환해 클라이언트가
재시도하게 하거나. 어느 쪽이든 "밀려드는 부하를 상류로 알리는" 배압이 있어야 시스템이
과부하에서 붕괴하지 않고 버틴다.

주의: 전용 스레드는 짧고 예측 가능한 일만

전용 스레드가 느린 I/O나 무거운 계산으로 막히면 시스템 전체의 처리량 상한이 거기서
결정된다. 무거운 작업(직렬화, 검증 등)은 이 스레드 밖에서 미리 준비해 오고, 큐의 소비자는
"순서가 중요한 최소한의 갱신"만 하는 것이 원칙이다.

실제 사례

Raft 구현체들의 로그 append, Kafka 브로커의 요청 처리가 이 구조다. 극단적으로 최적화한
예로 LMAX Disruptor(큐를 링 버퍼로 바꿔 GC와 캐시 미스까지 제거)가 있다. 사실 Node.js의
이벤트 루프나 액터 모델(Akka)의 메일박스도 같은 아이디어의 변주다. "상태는 한 스레드에
가두고, 접근은 메시지로".

2. Pattern 12 — 요청 대기 목록 (Request Waiting List)

문제: 응답은 "나중에, 다른 스레드에서" 완성된다

단일 갱신 큐에서 요청 스레드는 큐에 넣고 바로 리턴한다. 그러면 클라이언트에게 보낼 응답은
언제, 누가 완성하는가? 복제 로그와 결합하면 문제가 선명해진다. SET x = 10 요청이 리더에
도착한 뒤의 타임라인이다.

t1: 요청 도착 → 단일 갱신 큐에 투입, 요청 스레드는 리턴
t2: 전용 스레드가 WAL에 append (인덱스 42 부여)
t3: 팔로워들에게 복제 전파          ← 여기서부터 "기다림"
t4: 팔로워들의 ack가 하나둘 도착
t5: 과반수 달성 → HWM이 42를 통과 → 커밋!
t6: 이제야 클라이언트에게 성공 응답 가능

문제는 t3~t5 구간이다. 팔로워의 ack는 언제 올지 모르는 비동기 이벤트다. 요청 스레드가
폴링하며 블로킹 대기하면, 단일 갱신 큐로 애써 없앤 블로킹을 도로 들여오는 꼴이다. 게다가
t6 시점에 실행되고 있는 것은 원래 요청을 받았던 스레드가 아니라 팔로워의 ack를 처리하던
전혀 다른 스레드다.

해법: 요청을 키와 함께 걸어두고, 이벤트가 오면 깨운다

리더는 로그 인덱스를 키로 하는 대기 목록(맵) 을 유지한다.

WaitingList: { 로그 인덱스 → 미완성 응답(Future/콜백) }

t2에서 append하고 인덱스 42를 받는 순간, 응답 핸들을 키 42로 대기 목록에 등록해 두고
잊어버린다. 이후 ack를 처리하던 스레드가 t5에서 HWM을 42 이상으로 전진시키면, 대기
목록에서 인덱스 ≤ 42인 항목들을 전부 꺼내 future를 완성시킨다. 그 완성이 곧 클라이언트
응답 전송으로 이어진다.

class RequestWaitingList<R> {
    private val waiting = ConcurrentHashMap<Long, CompletableDeferred<R>>()

    fun waitFor(logIndex: Long): CompletableDeferred<R> =
        CompletableDeferred<R>().also { waiting[logIndex] = it }

    // HWM이 전진할 때마다 호출됨 (ack 처리 스레드에서)
    fun onHighWaterMarkAdvanced(hwm: Long, resultFor: (Long) -> R) {
        waiting.keys.filter { it <= hwm }.forEach { index ->
            waiting.remove(index)?.complete(resultFor(index))
        }
    }
}

핵심 구조를 한 문장으로 말하면 이렇다. "요청 접수"와 "응답 완성"을 서로 다른 스레드가
담당하도록 분리하고, 그 둘을 키(로그 인덱스)로 연결한다. 어떤 스레드도 기다리느라 잠들지
않는다. 모두가 이벤트에 반응만 할 뿐이다.

반드시 챙겨야 할 두 가지

만료(expiration). 과반수 ack가 영영 안 오면? (네트워크 분단으로 리더가 소수 쪽에
고립된 경우 — 지난 글의 그 시나리오다.) 대기 목록의 항목이 무한히 기다리면 클라이언트도
무한히 기다린다. 각 항목에 타임아웃을 걸고, 주기적으로 목록을 순회하며 만료된 요청은
에러로 완성시킨다. 클라이언트는 에러를 받고 재시도하고, 그 재시도는 멱등 수신자가 안전하게
처리한다.

리더 교체 시 정리. 리더가 팔로워로 강등되면 대기 목록에 남은 요청들은 완성될 가망이
없다. 목록 전체를 "리더 아님" 에러로 비워서 클라이언트가 새 리더로 재시도하게 만든다.
커밋되지 못한 로그 엔트리가 잘려나가는 것과 짝을 이루는 정리 작업이다.

실제 사례

가장 유명한 구현이 Kafka의 Purgatory(연옥 — 이름부터 "응답이 기다리는 곳"이다)다.
acks=all 프로듀서 요청은 ISR 전체의 복제가 끝날 때까지, 컨슈머의 long-poll fetch 요청은
새 데이터가 도착할 때까지 purgatory에서 대기한다. 수십만 건의 대기 요청에 타임아웃을
효율적으로 걸기 위해 계층형 타이밍 휠(hierarchical timing wheel)이라는 자료구조까지
동원한다. etcd도 같은 구조로 커밋 대기를 처리한다.

애플리케이션 레벨에서도 이 구조는 낯설지 않다. Spring의 DeferredResult, 코루틴의
suspendCancellableCoroutine으로 만드는 비동기 API가 정확히 같은 모양이다. 요청을 받은
스레드는 핸들만 등록하고 리턴하며, 완성은 나중에 다른 스레드(이벤트)가 한다.

3. 세 패턴이 만드는 하나의 파이프라인

Pattern 10, 11, 12를 겹쳐 놓으면 리더 노드의 쓰기 경로 전체가 블로킹 없는 이벤트
파이프라인이 된다.

클라이언트 요청
    │
    ▼
[단일 갱신 큐] ── 순서 보장, 락 제거, 배칭(그룹 커밋)
    │
    ▼
WAL append → 복제 전파          [요청 대기 목록에 (인덱스 → 응답 핸들) 등록]
    │
    ▼
과반수 ack → HWM 전진 ──────────▶ 대기 목록에서 해당 인덱스 완성 → 응답 전송

단일 갱신 큐가 순서를, 복제 로그가 내구성을, 요청 대기 목록이 비동기 응답을 담당한다.
어느 스레드도 다른 스레드를 기다리며 잠들지 않고, 각자 자기 이벤트에만 반응한다. 이것이
합의 기반 시스템들이 강한 일관성을 보장하면서도 높은 처리량을 내는 구조적 비결이다.

참고 자료

• 『30가지 패턴으로 배우는 분산 시스템 설계와 구현 기법』 — Pattern 11 단일 갱신 큐, Pattern 12 요청 대기 목록
• Martin Thompson et al., "LMAX Disruptor: High performance alternative to bounded queues"
• Apache Kafka 문서 — Request Purgatory, Hierarchical Timing Wheels