Raft Figure 8 문제 파헤치기 - "과반수 복제 = 커밋"이 위험한 이유

들어가며

분산 시스템에서 합의(Consensus) 알고리즘은 여러 노드가 하나의 일관된 상태를 유지하도록 보장하는 핵심 메커니즘이다. Raft는 이해하기 쉬운 합의 알고리즘을 목표로 설계되었지만, 그 안에는 깊이 생각하지 않으면 놓칠 수 있는 미묘한 안전성 문제가 숨어 있다.

그중 대표적인 것이 Figure 8 문제다. 이 글에서는 Raft 논문의 Figure 8이 보여주는 시나리오를 단계별로 분석하고, 해결 규칙이 왜 필요한지, 그리고 이것이 Kafka(KRaft)와 어떻게 다른지까지 살펴본다.

---

Raft의 기본 커밋 규칙

Raft에서 로그 엔트리가 커밋되려면 과반수(majority) 노드에 복제되어야 한다. 리더가 엔트리를 기록하고, 팔로워들에게 AppendEntries RPC로 복제한 뒤, 과반수 이상이 응답하면 커밋으로 간주한다.

이 규칙은 직관적이고 단순하다. 하지만 "이전 텀의 엔트리를 새 리더가 복제하는 경우"에는 이 규칙만으로 안전성을 보장할 수 없다. Figure 8이 바로 이 상황을 보여준다.

---

Figure 8 시나리오 분석

5개의 노드(S1~S5)가 있는 클러스터를 가정한다. 각 단계에서 어떤 일이 벌어지는지 살펴보자.

(a) 텀 2 — S1이 리더

S1이 리더로 선출되어 인덱스 2에 텀 2 엔트리를 기록한다. S2에게만 복제한 뒤 S1이 다운된다.

         idx 1    idx 2
S1 ★   [  1  ]  [  2  ]    ← 리더, 다운됨
S2     [  1  ]  [  2  ]    ← 복제 받음
S3     [  1  ]
S4     [  1  ]
S5     [  1  ]

이 시점에서 인덱스 2(텀 2)는 S1, S2 두 곳에만 있다. 과반수(3)에 도달하지 못했으므로 미커밋 상태다.

(b) 텀 3 — S5가 리더

S5가 새 리더로 선출되어 인덱스 2에 텀 3 엔트리를 기록한다. 아직 어디에도 복제하지 않은 상태다.

         idx 1    idx 2
S1     [  1  ]  [  2  ]    ← 다운 상태
S2     [  1  ]  [  2  ]
S3     [  1  ]
S4     [  1  ]
S5 ★   [  1  ]  [  3  ]    ← 새 리더

(c) 텀 4 — S1이 다시 리더

S1이 복귀하여 텀 4의 리더가 된다. S1은 인덱스 3에 텀 4 엔트리를 기록한다.

이때 S3의 로그가 뒤처져 있으므로 AppendEntries의 일관성 검사(consistency check) 과정에서 nextIndex가 줄어들면서, 인덱스 2의 텀 2 엔트리가 S3에 복제된다.

         idx 1    idx 2    idx 3
S1 ★   [  1  ]  [  2  ]  [  4  ]    ← 리더
S2     [  1  ]  [  2  ]
S3     [  1  ]  [  2  ]              ← 복제 받음!
S4     [  1  ]
S5     [  1  ]  [  3  ]

인덱스 2(텀 2)가 S1, S2, S3 세 곳에 존재한다. 과반수를 달성했다!

만약 여기서 "과반수에 복제되었으니 커밋"이라고 판단하면 어떻게 될까?

(d) 문제 발생 — S5가 텀 5 리더

S1이 다시 다운되고, S5가 텀 5의 리더로 선출된다.

S5가 리더로 선출될 수 있는 이유가 중요하다. Raft의 투표 규칙은 마지막 로그의 텀을 먼저 비교한다. S5의 마지막 로그 텀은 3이고, S2와 S3의 마지막 로그 텀은 2다. 텀 3 > 텀 2이므로 S5가 "더 최신"으로 판단되어 투표를 받을 수 있다.

S5가 리더가 되면 자신의 로그가 진실(truth)이 된다. S5의 인덱스 2에는 텀 3 엔트리가 있으므로, S1, S2, S3의 텀 2 엔트리는 텀 3 엔트리로 덮어씌워진다.

         idx 1    idx 2    idx 3
S1     [  1  ]  [  2  ]  [  4  ]    ← 다운, 복귀 시 덮어씌워짐
S2     [  1  ]  [  3  ]             ← 덮어씌워짐!
S3     [  1  ]  [  3  ]             ← 덮어씌워짐!
S4     [  1  ]  [  3  ]             ← 덮어씌워짐!
S5 ★   [  1  ]  [  3  ]             ← 리더

(c)에서 커밋되었다고 판단한 인덱스 2(텀 2) 엔트리가 사라졌다.

이것은 Raft의 핵심 안전성 속성인 "커밋된 로그는 절대 유실되지 않는다"를 정면으로 위반한다.

---

해결 규칙: 이전 텀의 엔트리를 직접 커밋하지 않는다

이 문제를 방지하기 위해 Raft는 다음 규칙을 도입한다.

Raft는 이전 텀의 로그 엔트리를 복제본 수를 세는 방식으로 커밋하지 않는다.

새 리더는 반드시 현재 텀의 엔트리를 로그에 추가하고, 이것을 과반수에 복제하여 커밋해야 한다. Raft의 로그는 순차적이므로, 현재 텀의 엔트리가 커밋되면 그 앞의 이전 텀 엔트리들도 간접적으로 커밋된다.

no-op: 현재 텀의 빈 엔트리

새 리더가 취임 직후 사용하는 "현재 텀의 엔트리"를 no-op(no operation)이라 한다. 말 그대로 아무 작업도 하지 않는 빈 엔트리지만, 현재 텀 번호가 찍혀 있다는 것이 핵심이다.

(e) 규칙 적용 후 — 안전한 시나리오

(c)에서 S1은 이전 텀(텀 2)의 인덱스 2를 직접 커밋하지 않는다. 대신 인덱스 3에 텀 4 엔트리를 과반수(S1, S2, S3)에 복제한다.

         idx 1    idx 2    idx 3
S1 ★   [  1  ]  [  2  ]  [  4  ]    ← 리더
S2     [  1  ]  [  2  ]  [  4  ]    ← 텀 4 복제 완료
S3     [  1  ]  [  2  ]  [  4  ]    ← 텀 4 복제 완료
S4     [  1  ]
S5     [  1  ]  [  3  ]

텀 4 엔트리가 과반수에 복제되어 커밋되면, 로그 순서에 의해 인덱스 2(텀 2)도 간접 커밋된다.

이 상태에서 S5가 리더에 도전하면 어떻게 될까? S2, S3의 마지막 로그 텀은 4이고, S5의 마지막 로그 텀은 3이다. 텀 4 > 텀 3이므로 S2, S3은 S5에게 투표하지 않는다. S5는 과반수 투표를 받을 수 없어 리더 선출 자체가 불가능하다.

따라서 (d) 상황이 원천 차단된다.

---

커밋되지 않은 엔트리의 운명

만약 S1이 텀 4 엔트리를 과반수에 복제하기 전에 다운되면 어떻게 될까?

인덱스 2는 미커밋 상태이므로, 누가 리더가 되느냐에 따라 텀 2 엔트리 또는 텀 3 엔트리 중 하나가 채택된다. Raft의 투표 규칙이 자연스럽게 더 최신 로그를 가진 쪽이 리더가 되도록 유도하고, 리더의 로그가 곧 진실이 된다.

어느 쪽이 선택되든 미커밋 엔트리이므로 안전성을 위반하지 않는다. Raft가 보장하는 것은 "커밋된 로그는 절대 유실되지 않는다"이지, "복제된 로그가 유실되지 않는다"가 아니기 때문이다.

---

Kafka(KRaft)는 다르게 동작한다

같은 합의 문제를 Kafka는 다른 방식으로 해결한다. Kafka에서는 하이워터마크(High Watermark)를 기준으로 커밋 여부를 판단하는데, 하이워터마크가 팔로워의 fetch 요청을 통해 비동기적으로 전파된다는 점이 Raft와 다르다.

하이워터마크의 비동기 전파

Raft에서는 리더가 AppendEntries 응답으로 팔로워의 복제 상태를 실시간으로 파악하고 commitIndex를 직접 계산한다. 반면 Kafka에서는 팔로워가 리더에게 fetch 요청을 보내면서 자신의 현재 오프셋을 알려주고, 리더가 이를 보고 하이워터마크를 갱신한 뒤 다음 fetch 응답에 실어 보내는 구조다.

이 때문에 팔로워가 알고 있는 하이워터마크는 항상 리더보다 최소 한 라운드 이상 뒤처져 있다.

Log Truncation

새 리더로 승격된 팔로워는 자신의 하이워터마크까지만 커밋이 확정된 것으로 판단하고, 그 이후의 로그는 잘라낸다(truncate). Raft처럼 no-op을 써서 이전 엔트리를 살리는 방식을 택하지 않았다.

메시지 유실과 프로듀서의 선택

Log truncation으로 인해 잘려나간 메시지는 유실될 수 있다. 하지만 이것이 실제 "데이터 손실"로 이어지는지는 프로듀서의 acks 설정에 따라 결정된다.

acks 설정동작유실 가능성

acks=0	프로듀서가 응답을 기다리지 않음	유실 인지 불가, 재전송 없음
acks=1	리더 기록 시점에 성공 응답	유실 사실 인지 못함 → 실질적 데이터 유실
acks=all	ISR 전체 복제 후 성공 응답	리더 다운 시 타임아웃 → 프로듀서가 재전송 가능

Kafka의 설계 철학은 유실 방지의 책임을 프로듀서에게 선택권을 주는 것이다. 처리량이 중요하면 acks=1, 안정성이 중요하면 acks=all을 선택하는 트레이드오프를 제공한다.