복제 로그 패턴

1. 시작하기 전에 — 장애 모델과 비잔틴 결함

분산 시스템의 모든 설계는 "어떤 장애까지 견딜 것인가"라는 가정 위에 서 있다. 장애 모델은 크게 두 급으로 나뉜다.

크래시 결함(Crash Fault) 은 노드가 그냥 멈추는 것이다. 프로세스가 죽거나, 느려지거나, 네트워크가 끊긴다. 중요한 것은 거짓말은 하지 않는다는 점이다. 응답을 한다면 그 내용은 올바르다.

비잔틴 결함(Byzantine Fault) 은 노드가 임의의(arbitrary) 동작을 하는 경우다. 잘못된 데이터를 보내거나, 노드 A에게는 "값이 1"이라 하고 노드 B에게는 "값이 2"라고 모순된 응답을 하거나, 프로토콜을 의도적으로 위반한다. 원인은 악의적 공격일 수도 있고, 메모리 비트 플립이나 심각한 버그일 수도 있다. 이름은 Lamport의 1982년 논문 "비잔틴 장군 문제"에서 왔다. 배신자 장군이 섞여 있어도 충직한 장군들이 같은 결론(공격/후퇴)에 도달할 수 있는가 하는 문제다.

실무적으로 중요한 포인트는 두 가지다.

첫째, 이 책의 패턴들(Raft 포함)은 비잔틴 결함을 다루지 않는다. 크래시 결함 모델을 가정한다. 크래시 결함은 f개의 장애를 허용하는 데 2f+1 노드면 충분하지만(과반수 정족수), 비잔틴 결함까지 견디려면 3f+1 노드와 PBFT 같은 훨씬 무거운 프로토콜이 필요하다. 사내 데이터센터처럼 모든 노드를 우리가 통제하는 환경에서 비잔틴 내성은 과한 비용이다. 서로 신뢰할 수 없는 참여자가 섞이는 블록체인 같은 환경에서 비로소 BFT가 필수가 된다.

둘째, 그렇다고 아무 방어도 없는 것은 아니다. 악의는 아니지만 "데이터가 잘못 전달되는" 문제는 저렴한 수단으로 막는다. 네트워크/디스크 손상은 체크섬(CRC) 으로, 외부 침입자는 TLS와 인증으로. "비잔틴 합의는 안 하지만, 흔한 비잔틴스러운 사고는 값싸게 걸러낸다"가 실무의 균형점이다.

2. WAL (Write-Ahead Log, 선행 기입 로그)

해결하려는 문제

서버가 데이터를 메모리에만 들고 있으면 프로세스가 죽는 순간 전부 사라진다. 그렇다고 상태가 바뀔 때마다 전체 자료구조(해시맵, B-Tree 등)를 디스크에 통째로 쓰는 것은 너무 비싸고, 쓰는 도중 크래시가 나면 파일이 반쯤 깨진 상태가 될 수도 있다.

핵심 아이디어

상태를 바꾸기 전에, 그 변경 내용(명령)을 append-only 로그 파일에 먼저 기록한다. 그래서 이름이 Write-Ahead Log다.

클라이언트 요청: SET name = "chulyun"
  1. 로그에 append: {seq: 42, cmd: SET, key: name, value: chulyun} + fsync
  2. 그 다음에 메모리 상태(KV 스토어)에 적용
  3. 클라이언트에 응답

서버가 재시작되면 로그를 처음부터 replay해서 메모리 상태를 복원한다. 즉 로그가 진실의 원천(source of truth)이고, 메모리 상태는 로그의 파생물이다.

왜 이게 빠른가? 로그는 항상 파일 끝에 순차적으로만 쓴다(sequential append). 디스크는 랜덤 I/O보다 순차 I/O가 압도적으로 빠르기 때문에, "매 변경마다 디스크에 쓴다"는 부담이 현실적으로 감당 가능해진다. Kafka가 디스크 기반으로도 엄청난 처리량을 내는 이유가 정확히 이것이다.

구현 시 챙겨야 하는 디테일

각 로그 엔트리에는 단조 증가하는 로그 순서 번호(log sequence number) 를 붙인다. 이 번호가 복제 로그, 로우/하이 워터 마크 같은 패턴들의 기반이 된다. 쓰다가 크래시가 나면 마지막 엔트리가 반쯤 잘린 채 남을 수 있으므로 엔트리마다 CRC(체크섬) 를 기록해 두고, 재시작 시 손상된 엔트리를 감지해 버린다. 로그는 무한히 자랄 수 없으니 세그먼트 분할(Segmented Log) + 스냅샷 + 로우 워터 마크 이전 세그먼트 삭제로 관리한다.

Kotlin으로 뼈대만 그리면 다음과 같다.

class WriteAheadLog(private val file: RandomAccessFile) {
    private var lastLogSequence = 0L

    fun append(command: ByteArray): Long {
        val entry = WalEntry(++lastLogSequence, command, crc32(command))
        file.seek(file.length())          // 항상 끝에만 append
        file.write(entry.serialize())
        file.fd.sync()                    // fsync — 내구성 보장 지점
        return entry.sequence
    }

    fun readAll(): List<WalEntry> = TODO("재시작 시 replay용, CRC 검증 포함")
}

fsync 배치 처리 — 무엇을 얻고 무엇을 잃는가

fsync를 매 append마다 하면 안전하지만 느리고, OS 페이지 캐시에만 쓰고 응답하면 빠르지만 전원 장애 시 유실된다. 배치로 모아서 fsync하면 디스크 I/O 횟수가 줄어 처리량이 올라가는데, 여기서 유실 위험이 생기느냐 마느냐는 배치 자체가 아니라 "클라이언트에게 언제 응답하느냐"가 결정한다.

방식 A — ack 먼저, fsync 나중. append 후 바로 성공 응답을 주고 fsync는 주기적으로 모아서 한다. 처리량과 지연시간 모두 좋지만, 크래시 시 "성공했다고 답해놓고 사라진 데이터"가 생긴다. Redis AOF의 appendfsync everysec가 이 모드다.

방식 B — 그룹 커밋(group commit). 여러 요청의 append를 모아 fsync 한 번을 하되, fsync가 끝난 뒤에야 해당 배치의 클라이언트들에게 응답한다. 처리량은 똑같이 올라가고 유실은 없다. 잃는 것은 개별 요청의 지연시간이다. Postgres의 그룹 커밋, Kafka 브로커가 이쪽이다.

정리하면 배치는 처리량을 사고, 그 대가로 지연시간을 지불할지(방식 B) 내구성을 지불할지(방식 A) 선택하는 문제다. "성공 응답 = fsync 완료"라는 계약만 지키면 배치 자체는 안전하다. 이 트레이드오프가 Kafka의 acks, Postgres의 synchronous_commit 같은 설정으로 그대로 노출된다.

3. 복제 로그 — WAL을 여러 노드에

복제 로그(Replicated Log)는 WAL을 한 대가 아니라 여러 노드에 같은 순서로 복제하는 패턴이다. 핵심 전제는 상태 머신 복제(State Machine Replication)다.

모든 노드가 동일한 로그를 가지면, 동일한 순서로 replay했을 때 동일한 상태가 된다.

"같은 순서 보장"을 하는 것이 Raft/Paxos 같은 합의 알고리즘이고, 이 글은 Raft를 골격으로 설명한다.

왜 리더가 필요한가

아무 노드나 로그에 쓸 수 있게 하면 순서를 합의하는 문제가 매 엔트리마다 발생한다. 그래서 문제를 둘로 쪼갠다. (1) 리더를 하나 뽑는다. (2) 그다음엔 리더 혼자 로그 순서를 결정하고, 나머지(팔로워)는 그대로 복제한다. 합의라는 비싼 작업을 "엔트리마다"가 아니라 "리더가 바뀔 때만" 하도록 만드는 구조다.

4. 리더 선출 (Leader Election)

선출은 언제, 어떻게 일어나는가

평상시 리더는 팔로워들에게 주기적으로 하트비트를 보낸다. 팔로워는 각자 선출 타임아웃(예: 150~300ms 사이 랜덤값)을 두고, 그동안 하트비트가 안 오면 리더가 죽었다고 판단해 스스로 후보(candidate) 가 되어 선거를 시작한다.

이때 등장하는 것이 세대 시계(Generation Clock), Raft 용어로는 term이다. 후보는 자신의 term을 1 올리고, 자신에게 투표한 뒤, 다른 노드들에게 투표 요청을 보낸다. 과반수(quorum) 의 표를 얻으면 그 term의 리더가 된다.

과반수가 중요한 이유는 어떤 term에도 리더가 둘일 수 없음을 보장하기 때문이다. 각 노드는 한 term에 딱 한 번만 투표하고(이 투표 기록은 WAL에 영속화된다), 과반수 집합 두 개는 반드시 겹치므로 두 후보가 동시에 과반을 얻는 것은 불가능하다.

아무나 리더가 되면 안 된다 — 투표 조건

단순히 "빨리 손든 노드가 리더"가 되면, 로그가 뒤처진 노드가 리더가 되어 이미 커밋된 엔트리를 덮어쓸 수 있다. 그래서 투표 요청에는 후보의 마지막 로그 엔트리의 term과 인덱스가 담기고, 투표자는 이렇게 판단한다.

후보의 로그가 내 로그보다 뒤처져 있으면 거부한다.
(마지막 엔트리의 term이 높은 쪽이 최신, term이 같으면 로그가 긴 쪽이 최신)

커밋된 엔트리는 정의상 과반수 노드에 존재한다. 리더가 되려면 과반수의 표가 필요하다. 두 과반수는 반드시 겹치므로, 커밋된 엔트리를 갖지 않은 후보는 그 엔트리를 가진 누군가에게 반드시 거부당해 리더가 될 수 없다. 과반수 두 개가 겹친다는 사실 하나로 "커밋된 데이터는 리더가 바뀌어도 유실되지 않는다"가 증명된다.

스플릿 보트와 유령 리더

타임아웃이 비슷하게 만료되면 여러 노드가 동시에 후보가 되어 표가 갈릴 수 있다(split vote). 아무도 과반을 못 얻으면 선거는 무산되고 각자 랜덤한 타임아웃 후 재시도한다. 이 랜덤화 덕분에 다음 라운드에서는 누군가 먼저 깨어나 표를 쓸어갈 확률이 높아져 몇 라운드 안에 수렴한다.

네트워크 분단 후 구버전 리더가 돌아오는 경우는 term이 해결한다. 모든 메시지에 term이 실려 다니므로, 구 리더는 자기보다 높은 term을 보는 순간 즉시 팔로워로 강등되고, 노드들은 낮은 term의 요청을 거부한다. 세대 시계가 "과거에서 온 유령 리더"를 걸러내는 것이다.

실무에서의 두 갈래

직접 선출을 구현하는 시스템(etcd, Consul, Kafka KRaft)이 있는가 하면, ZooKeeper의 임시 노드(ephemeral node)처럼 외부 코디네이터에 선출을 위임하는 시스템도 많다(구세대 Kafka, HBase). 데이터 노드가 수백 대라면 그들끼리 과반 투표는 비현실적이므로, "합의는 작은 클러스터(3~5대)에 맡기고 나머지는 그 결과를 따른다"는 분업이 일반적이다.

5. 로그 복제와 하이 워터 마크 (High-Water Mark)

정상 흐름

클라이언트 쓰기 요청이 오면 리더는 (1) 자기 WAL에 append하고, (2) 팔로워들에게 엔트리를 전파하고, (3) 과반수가 자기 로그에 썼다고 응답한 순간 그 엔트리를 커밋으로 선언한다. 이 "여기까지는 커밋됐다"는 인덱스가 하이 워터 마크(Raft의 commitIndex)다. 리더는 HWM을 넘긴 뒤에야 상태 머신에 엔트리를 적용하고 클라이언트에 성공을 응답한다.

팔로워는 HWM을 스스로 계산할 수 없다. 과반수가 어디까지 복제했는지는 리더만 알기 때문이다. 그래서 리더는 다음 복제 요청이나 하트비트에 HWM을 실어서(piggyback) 전파하고, 팔로워는 그것을 받고서야 해당 지점까지 상태 머신에 적용한다.

로그의 각 엔트리는 세 단계를 거친다.

appended(리더 로그에 기록됨, 아직 사라질 수 있음)
→ committed / HWM 통과(과반수 복제 완료, 유실 불가)
→ applied(상태 머신에 반영됨)

이 구분이 복제 로그 이해의 절반이다.

네트워크 분단 시나리오 — 왜 HWM 아래에서만 읽어야 하는가

5노드 클러스터가 2대/3대로 분단되고 기존 리더가 2대 쪽에 있다고 하자.

3대 쪽에서는 하트비트가 끊기므로 새 리더 선출이 일어난다(과반 3/5 달성 가능). 2대 쪽 구 리더는 자기가 강등된 것을 모르므로 쓰기 요청을 받으면 일단 로그에 append하고 복제를 시도한다. 하지만 과반수 응답을 영영 못 받으므로 그 엔트리는 커밋되지 못하고, 클라이언트는 타임아웃을 받는다. 즉 정확히는 "쓰기가 거부된다"기보다 "커밋이 불가능하다"이다. 로그에 적히는 것과 커밋되는 것은 다른 사건이다.

분단이 복구되면 구 리더는 새 리더의 높은 term을 보고 팔로워로 강등되고, 커밋되지 못한 엔트리들은 잘려나가고 새 리더의 로그로 덮어써진다. 만약 커밋 전 데이터를 클라이언트에게 보여줬다면 "분명히 읽었던 데이터가 사라지는" 일이 생긴다. HWM은 "여기까지는 어떤 장애가 나도 사라지지 않는다"는 경계선이고, 그래서 읽기도 HWM 아래에서만 서빙한다.

팔로워 로그가 어긋나 있을 때

리더는 복제 요청에 "이 엔트리 직전 엔트리의 (인덱스, term)"을 함께 보낸다. 팔로워는 자기 로그의 그 위치에 같은 (인덱스, term)이 없으면 요청을 거부하고, 리더는 한 칸씩 뒤로 물러나며 일치 지점을 찾아 그 이후를 자기 로그로 덮어쓴다. 이 일관성 검사 덕분에 "팔로워의 로그는 리더 로그의 접두사(prefix)와 항상 일치한다"는 불변식이 유지되고, 새로 합류하거나 오래 죽어 있던 노드도 자동으로 따라잡는다.

심화: 이전 term의 엔트리는 세어서 커밋하면 안 된다 (Raft Figure 8)

새 리더는 이전 term의 엔트리를 "과반수에 복제돼 있네?"라고 세어서 커밋 처리하면 안 된다. 연쇄적인 리더 교체 상황에서 그렇게 커밋한 엔트리가 나중에 덮어써지는 반례가 존재한다(Raft 논문 Figure 8). 대신 새 리더는 자기 term의 no-op 엔트리를 즉시 append해서 복제한다. 이 no-op이 커밋되는 순간, 로그 일치 특성(Log Matching)에 의해 그 앞의 모든 엔트리도 함께 커밋 확정된다. 커밋 여부를 "판정"하는 게 아니라, 새 커밋을 만들어 이전 것들을 딸려서 확정시키는 것이다.

이 규칙은 다음 심화 질문의 답이기도 하다.

Q. 리더가 정족수를 달성해 커밋했지만, 커밋 인덱스를 팔로워에게 전파하지 못한 채 다운됐다. 새 리더는 이 엔트리를 어떻게 처리하나?

먼저, 새 리더는 그 엔트리를 반드시 가지고 있다. 엔트리는 과반수에 존재하고, 당선에는 과반수의 표가 필요하며, 투표 조건 때문에 그 엔트리를 가진 노드들은 엔트리가 없는 후보를 거부한다. 두 과반수는 겹치므로 데이터 자체는 유실되지 않는다. 다만 새 리더는 그것이 커밋됐는지 모르므로, 자기 term의 no-op을 커밋시켜 이전 엔트리들을 딸려서 확정한다. 구 리더가 클라이언트에 성공 응답을 이미 보냈더라도 약속은 지켜지고, 응답을 못 보냈다면 클라이언트의 재시도를 멱등 수신자가 처리한다.

6. 재시도와 중복 — 멱등 수신자 (Idempotent Receiver)

클라이언트가 쓰기 요청을 보냈는데 응답을 못 받고 타임아웃되면 재시도한다. 이때 같은 명령이 로그에 두 번 적히는 것을 막아야 한다.

구체적인 처리 방식

1단계 — 클라이언트 등록. 클라이언트가 처음 접속하면 리더에 등록하고 고유한 클라이언트 ID를 받는다. 이 등록 자체도 로그 엔트리로 복제된다. 그래야 리더가 바뀌어도 새 리더가 클라이언트 정보를 안다.

2단계 — 요청 번호 부여. 클라이언트는 모든 요청에 (클라이언트 ID, 요청 시퀀스 번호)를 붙인다. 재시도할 때는 같은 시퀀스 번호를 그대로 다시 보낸다.

3단계 — 서버 측 중복 감지와 응답 캐시. 서버는 클라이언트별로 "마지막으로 처리한 시퀀스 번호와 그때의 응답"을 저장한다.

fun handle(request: ClientRequest): Response {
    val session = sessions[request.clientId]
        ?: return Response.sessionExpired()

    return when {
        // 이미 처리한 요청 → 재실행하지 않고 저장해 둔 응답을 그대로 반환
        request.sequenceNumber <= session.lastProcessedSeq ->
            session.cachedResponse(request.sequenceNumber)

        // 새 요청 → 로그에 복제하고, 적용 후 응답을 캐시에 저장
        else -> replicateAndApply(request).also {
            session.record(request.sequenceNumber, it)
        }
    }
}

핵심은 응답까지 저장한다는 점이다. 중복을 감지만 하고 버리면 클라이언트는 결과를 영영 못 받는다. 그리고 이 세션 상태도 상태 머신의 일부로 취급되어 로그 적용과 함께 갱신된다. 리더가 바뀌어도 새 리더가 같은 로그를 replay하면 같은 세션 상태를 갖게 되므로, 재시도가 어느 리더에게 가든 중복 실행되지 않는다.

4단계 — 상태 정리. 클라이언트가 "시퀀스 N까지 응답을 잘 받았다"고 알려주면(다음 요청에 piggyback) 그 이전 캐시는 버린다. 세션에는 리스(lease)/타임아웃을 걸어 하트비트가 끊긴 클라이언트의 상태를 만료시킨다. 만료 후 뒤늦게 도착한 재시도는 거부할 수밖에 없다. 완벽한 exactly-once는 무한한 상태 없이는 불가능하다는 한계가 여기서 드러난다.

왜 UUID가 아니라 시퀀스 번호인가

임의의 UUID 키로도 중복 감지는 되지만, 본 적 있는 키를 전부 집합으로 들고 있어야 한다. 단조 증가하는 시퀀스 번호를 쓰면 "클라이언트별 마지막 번호 하나"만 기억해도 그 이하는 전부 중복으로 판정할 수 있어 저장 공간이 극적으로 줄어든다. Kafka의 멱등 프로듀서가 (Producer ID, 파티션별 시퀀스 번호)로 중복 배치를 걸러내는 것이 정확히 이 방식이다.

전달 보장 의미론으로 정리

재시도를 안 하면 at-most-once(유실 가능), 재시도만 하면 at-least-once(중복 가능), 재시도 + 멱등 수신자 = 사실상 exactly-once다. 즉 exactly-once는 마법 같은 전송 프로토콜이 아니라 "at-least-once로 배달하고 수신 측에서 중복을 제거한다"는 조합으로 만들어진다.

실무에서 HTTP API에 쓰는 Idempotency-Key 헤더(Stripe, 토스페이먼츠 결제 API 등)가 이 패턴의 응용이다. 키 저장소가 복제 로그가 아니라 DB나 Redis일 뿐, "키로 중복 감지 + 저장된 응답 재반환"이라는 구조는 동일하다.

7. 심화: 클러스터 멤버십 변경 (Membership Change)

노드 구성은 고정이 아니다. 그리고 구성 변경은 보기보다 위험하다.

왜 위험한가

3대 클러스터 {A, B, C}에서 {A, B, C, D, E}로 한 번에 바꾼다고 하자. 구성 변경 정보가 노드마다 도착하는 시점이 다르므로, 어느 순간 A, B는 구 구성(정족수 2/3)으로, C, D, E는 신 구성(정족수 3/5)으로 동작할 수 있다. 그러면 {A, B}가 구 구성 기준 과반으로 리더를 뽑고, 동시에 {C, D, E}가 신 구성 기준 과반으로 또 다른 리더를 뽑는 스플릿 브레인이 가능해진다. 정족수의 안전성은 "모두가 같은 구성을 본다"는 전제 위에 있는데, 과도기에 그 전제가 깨진다.

해법: 구성 자체를 로그로 합의한다

멤버십 구성을 설정 파일이 아니라 복제 로그를 통해 합의되는 데이터로 취급한다. 그 위에서 두 가지 방식이 있다.

단일 서버 변경(single-server change) — 실무의 주류. 한 번에 노드를 딱 하나만 추가/제거한다. 한 대씩만 바꾸면 구 구성의 과반과 신 구성의 과반이 수학적으로 반드시 겹치므로 리더 둘이 나올 수 없다. 5대로 만들려면 두 번 반복하면 된다. etcd가 이 방식이다.

공동 합의(joint consensus) — Raft 논문의 원래 방식. 한 번에 여러 대를 바꿀 때 과도기에 C(old,new)라는 중간 구성을 거치며, 이 기간에는 구 구성과 신 구성 양쪽 모두에서 과반을 얻어야 커밋과 선출이 가능하다. 안전하지만 구현이 까다로워 실제로는 단일 서버 변경이 선호된다.

새 노드는 로그가 빈 채로 합류하므로 바로 투표권을 주면 정족수 분모만 늘려 가용성을 해친다. 그래서 etcd 같은 시스템은 학습자(learner) 노드로 먼저 붙여 투표권 없이 로그를 따라잡게 한 뒤 정식 멤버로 승격한다.

8. 정리

Pattern 10의 골격은 세 겹이다.

WAL이 "변경을 먼저 순차 로그에 기록"함으로써 단일 노드의 내구성과 성능을 잡고, 리더 선출이 로그 순서 결정권의 유일성을 보장하며(term + 과반수 + 투표 조건), 복제와 하이 워터 마크가 유실 없는 커밋 경계를 만든다. 그 위에 멱등 수신자가 재시도로 인한 중복을 제거해 exactly-once 의미론을 완성하고, 멤버십 변경조차 로그를 통한 합의로 처리된다.

그리고 이 모든 것은 "노드가 거짓말은 하지 않는다"는 크래시 결함 가정 위에 서 있다. Kafka의 ISR과 high watermark, etcd/Raft의 commitIndex, ZooKeeper의 Zab이 전부 이 구조의 변주다.

참고 자료

• 『30가지 패턴으로 배우는 분산 시스템 설계와 구현 기법』 — Pattern 10 복제 로그
• Diego Ongaro, John Ousterhout, "In Search of an Understandable Consensus Algorithm" (Raft 논문)
• Leslie Lamport et al., "The Byzantine Generals Problem" (1982)
• Martin Kleppmann, 『데이터 중심 애플리케이션 설계』 8~9장