10.1 시간, 순서, 합의 — 부분 실패에서 하나의 결정까지

응답이 오지 않으면 무슨 일이 있었는지 알 수 없고, 두 이벤트 중 어느 것이 먼저인지도 시계로는 확정할 수 없다. 이 문서는 부분 실패를 성공·실패·모름의 세 상태로 재정의하고, 물리 시계 대신 논리 시계로 순서를 세운 뒤, 비동기 네트워크에서 합의가 왜 근본적으로 어려운지(FLP 불가능성)를 증명 수준까지 확인한다. 마지막으로 그 한계를 실무에서 우회하는 Raft와 Paxos의 안전성·가용성 조건을 추적한다.

학습 목표

• 부분 실패를 성공·실패·모름의 세 상태로 모델링하고, 재시도에 멱등성이 필요한 이유를 설명한다.
• Lamport 논리 시계와 vector clock이 정의하는 순서의 의미와 한계(동시성 이벤트 구분 가능 여부)를 구분한다.
• FLP 불가능성이 규정하는 비동기 합의의 근본 한계를 증명의 핵심 논증으로 설명하고, 실무 시스템이 이를 우회하는 전략(부분 동기성, 무작위화)을 설명한다.
• Raft의 리더 선출·로그 복제·안전성 조건을 추적하고, 이를 Paxos와 비교해 같은 문제의 다른 해법으로 설명한다.

배경: 왜 이것이 존재하는가

단일 프로세스 프로그래밍은 세 가지를 공짜로 얻는다. 함수 호출은 성공하거나 예외를 던지고(제3의 결과가 없다), 스택의 모든 지점에 전역적으로 합의된 순서가 있고("이 줄이 저 줄보다 먼저 실행됐다"는 항상 참이다), 그 순서를 재는 시계는 하나다. 여러 프로세스가 메시지로만 통신하는 순간 세 가지 모두 사라진다.

• 실패가 이분법이 아니다. 로컬 함수 호출의 실패는 스택 언와인딩으로 관찰 가능하지만, 원격 호출의 "응답 없음"은 요청 유실·처리 후 응답 유실·처리 중단을 구분하지 못한다.
• 시계가 하나가 아니다. 각 노드의 물리 시계는 독립적으로 흐르고 NTP로 보정해도 수 밀리초에서 수십 밀리초의 오차가 남는다. "타임스탬프가 크니 나중에 일어난 이벤트"라는 추론은 이 오차 안에서 무너진다.
• 유한한 응답 시간이 보장되지 않는다. 비동기 네트워크 모델에서는 메시지 지연에 상한이 없다. 이 가정 하나가 이 문서 후반의 FLP 불가능성을 만든다.

세 가지 붕괴는 독립적이지 않다. 부분 실패를 다루려면 "언제 포기하고 다른 노드를 대신 신뢰할 것인가"를 결정해야 하고, 그 결정은 순서(누구의 상태가 최신인가)에 의존하며, 순서를 세우려면 시간 대신 인과관계가 필요하다. 이 문서는 이 의존 순서 그대로 — 부분 실패 → 논리 시계 → 합의의 불가능성과 그 우회 — 개념을 쌓는다.

핵심 개념

부분 실패 — 성공, 실패, 모름

원격 호출 하나가 실행되는 동안 실패할 수 있는 지점은 세 곳이다.

클라이언트                네트워크              서버
   │── 요청 ──▶│                      │
              │─ 유실 ──✗             │             (1) 요청이 도달하지 못함
              │
   │── 요청 ──▶│───────────────▶│ 처리 시작
                                     │ 처리 완료
              │◀──────── 응답 ──✗ 유실 │             (2) 응답이 돌아오지 못함
   │
   │── 요청 ──▶│───────────────▶│ 처리 중 crash    (3) 처리 도중 중단

클라이언트가 관찰하는 신호는 세 경우 모두 타임아웃으로 동일하다. (1)은 재시도가 안전하다 — 서버는 아무 일도 하지 않았다. (3)도 재시도가 안전할 수 있다 — 단, 서버가 부분적으로 상태를 바꾸고 죽었다면 그 부분 상태를 정리해야 한다. (2)는 재시도하면 같은 작업이 두 번 실행된다. 문제는 클라이언트가 이 셋을 구분할 수단이 없다는 것이다.

그래서 정확한 모델은 이분법(성공/실패)이 아니라 삼분법이다.

호출 결과 ∈ { 성공, 실패, 모름 }

"모름"을 다루는 방법은 두 가지뿐이다. 결과를 알아낼 때까지 기다리거나(가용성을 희생), 결과를 몰라도 안전한 다음 행동을 정의하는 것이다. 후자의 표준 해법이 **멱등성(idempotency)**이다.

멱등성 — 모름을 안전하게 만드는 유일한 방법

멱등 연산은 한 번 실행하든 여러 번 실행하든 결과가 같다. 재시도가 안전해지는 이유는 재시도가 성공했기 때문이 아니라, 중복 실행 자체가 무해하기 때문이다.

요청에 고유 idempotency key(예: 클라이언트가 생성한 요청 ID)를 부여한다.

서버:
  이 key로 이미 처리한 기록이 있는가?
    있음 → 새로 처리하지 않고 저장된 결과를 반환
    없음 → 처리하고, key와 결과를 원자적으로 기록한 뒤 반환

이 패턴이 안전하려면 "처리"와 "key 기록"이 하나의 원자적 단위여야 한다. 둘을 분리하면 그 사이에 또 다른 부분 실패 창이 생긴다 — 이 문제는 챕터 11.8의 분산 트랜잭션이 다루는 원자적 commit과 정확히 같은 구조다.

여기서 흔한 오해를 짚어야 한다. "exactly-once 전달(delivery)"은 일반적으로 달성할 수 없다. 메시지가 네트워크를 통과하는 한 유실·중복은 항상 가능하고, 이를 막을 방법은 없다. 실무 시스템이 파는 것은 전달의 정확히 한 번이 아니라 **effect의 정확히 한 번(effectively-once)**이다 — at-least-once 전달(안전하게 재시도)과 멱등한 처리(중복을 무해하게 만듦)를 결합해서 만든다. "이 큐는 exactly-once를 보장한다"는 문구를 볼 때는 항상 "전달인가, 처리 효과인가"를 확인해야 한다.

시간 — 물리 시계의 한계

물리 시계로 순서를 매기고 싶은 유혹은 자연스럽다. 두 이벤트에 각각 타임스탬프를 찍고 비교하면 될 것 같다. 문제는 노드 간 시계가 정확히 맞지 않는다는 것이다. NTP로 동기화해도 일반적인 데이터센터 환경에서 수 밀리초의 오차가 흔하고, 오차가 커지는 상황(NTP 서버 접근 불가, VM 일시정지, leap second)은 예고 없이 온다.

노드 A 시계: 12:00:00.100  ── 이벤트 a: "재고 확인, 여유 있음"
노드 B 시계: 12:00:00.095  ── 이벤트 b: "같은 재고 차감"

타임스탬프만 보면 b가 a보다 먼저다. 그러나 실제로는:
- A와 B 시계가 각각 얼마나 어긋나 있는지 그 순간에는 알 수 없다.
- a와 b가 서로의 결과를 참조하지 않았다면(원인 없음) "먼저"라는 말 자체가
  두 이벤트의 실제 관계를 설명하지 못한다.

Google Spanner의 TrueTime처럼 GPS·원자시계로 오차 구간을 좁히고 그 구간을 명시적으로 다루는 접근도 있지만, 이는 예외적인 인프라 투자로 얻은 결과이지 일반 시스템의 기본값이 아니다. 대부분의 시스템은 물리 시계를 순서의 근거로 쓰지 않는 쪽을 택한다.

논리 시계 — 인과관계로 순서를 정의한다

Lamport(1978)는 시간 대신 **인과관계(happens-before, →)**로 순서를 정의했다. 챕터 8a에서 본 happens-before가 동기화 연산으로 정의됐다면, 분산 시스템에서는 메시지 송수신이 그 역할을 한다.

• 같은 프로세스 안에서 a가 b보다 먼저 실행되면 a → b.
• a가 메시지를 보내고 b가 그 메시지를 받으면 a → b.
• →는 추이적이다: a → b이고 b → c이면 a → c.
• a → b도 b → a도 아니면 a와 b는 **동시(concurrent)**다 — 시간상 동시라는 뜻이 아니라 서로 원인이 될 수 없다는 뜻이다.

Lamport 논리 시계는 이 관계를 정수 하나로 근사한다.

각 프로세스는 카운터 L을 가진다.
1. 로컬 이벤트마다 L ← L + 1
2. 메시지를 보낼 때 현재 L을 함께 보낸다.
3. 메시지를 받으면 L ← max(L, 수신한 L) + 1

이 규칙은 a → b이면 L(a) < L(b)를 보장한다. 그러나 역은 성립하지 않는다 — L(a) < L(b)라고 해서 a → b인 것은 아니다. 두 동시 이벤트도 우연히 다른 타임스탬프를 받을 수 있기 때문이다. Lamport 시계는 인과관계와 **모순되지 않는 전순서(total order)**를 주지만, 그 전순서가 실제 인과관계를 복원해 주지는 않는다.

세 프로세스가 메시지를 주고받는 시나리오로 확인해 보자.

// lamport-vector-clock.mjs — 3개 프로세스의 이벤트 스케줄을 시뮬레이션한다
// 실제 분산 실행이 아니라 정해진 이벤트 순서를 재생하는 단일 프로세스 시뮬레이션이다.
class Process {
  constructor(id, n) {
    this.id = id;
    this.lamport = 0;
    this.vector = new Array(n).fill(0);
  }
  local() {
    this.lamport += 1;
    this.vector[this.id] += 1;
    return { lamport: this.lamport, vector: [...this.vector] };
  }
  send() {
    return this.local(); // 송신도 하나의 이벤트다
  }
  receive(msgLamport, msgVector) {
    this.lamport = Math.max(this.lamport, msgLamport) + 1;
    this.vector = this.vector.map((v, i) => Math.max(v, msgVector[i]));
    this.vector[this.id] += 1;
    return { lamport: this.lamport, vector: [...this.vector] };
  }
}

const [P0, P1, P2] = [0, 1, 2].map((id) => new Process(id, 3));

const a = P0.local();                          // P0 로컬 이벤트
const m1 = P0.send();                          // P0 → P1로 메시지 발송 (send도 하나의 이벤트)
const b = P1.local();                          // P1 로컬 이벤트 (m1과 무관, 동시)
const c = P1.receive(m1.lamport, m1.vector);    // P1이 m1 수신
const m2 = P2.send();                          // P2 → P1로 메시지 발송 (역시 무관)
const d = P1.receive(m2.lamport, m2.vector);    // P1이 m2 수신

for (const [name, e] of [
  ['a(P0)', a], ['m1(P0→P1 발송)', m1], ['b(P1)', b],
  ['c(P1 recv m1)', c], ['m2(P2→P1 발송)', m2], ['d(P1 recv m2)', d],
]) {
  console.log(`${name}: lamport=${e.lamport} vector=[${e.vector}]`);
}

a(P0): lamport=1 vector=[1,0,0]
m1(P0→P1 발송): lamport=2 vector=[2,0,0]
b(P1): lamport=1 vector=[0,1,0]
c(P1 recv m1): lamport=3 vector=[2,2,0]
m2(P2→P1 발송): lamport=1 vector=[0,0,1]
d(P1 recv m2): lamport=4 vector=[2,3,1]

b와 a는 Lamport 값이 각각 1로 같다 — 둘은 서로 다른 프로세스의 동시 이벤트이므로 순서를 규정할 수 없고, 우연히 같은 값을 받았다(전순서로 만들려면 프로세스 ID 같은 tie-break 규칙을 추가로 정해야 한다). 여기서 Lamport 시계의 한계가 드러나는 쌍은 c와 m2다. c의 Lamport 값(3)이 m2의 값(1)보다 크므로 숫자만 보면 "m2가 c보다 먼저 일어났다"고 읽고 싶어진다. 그러나 c는 P1이 P0의 메시지를 받은 이벤트이고 m2는 P2가 독립적으로 메시지를 보낸 이벤트다 — 둘 사이에는 어떤 인과관계도 없다. Lamport 숫자의 크고 작음이 실제 인과관계와 무관하게 발생할 수 있다는 것이 정확히 이 지점이다.

vector clock은 이 구분을 정확히 제공한다. 두 vector V(a), V(b)에 대해:

V(a) < V(b)  ⟺  a → b   (모든 성분에서 V(a) ≤ V(b)이고, 적어도 하나는 <)
V(a), V(b) 비교 불가(어느 쪽도 다른 쪽보다 작지 않음)  ⟺  a와 b는 동시

위 실행에서 d = [2,3,1]과 a = [1,0,0]을 비교하면 모든 성분에서 a ≤ d이므로 a → d가 확정된다 — P0의 첫 이벤트가 P1의 최종 상태에 인과적으로 앞선다는 것이 정확히 맞다. 반면 c = [2,2,0]과 m2 = [0,0,1]을 비교하면 어느 쪽도 다른 쪽보다 작지 않다 — Lamport 숫자로는 순서가 있어 보였던 이 쌍이 실제로는 동시임을 vector clock이 정확히 짚어낸다. 이 정밀함의 대가는 크기다. vector clock은 프로세스 수만큼 성분이 필요해 노드가 많은 시스템에서 메타데이터 비용이 커진다. Dynamo 계열의 leaderless 복제 시스템이 동시 쓰기 충돌을 탐지할 때 이 성질을 사용하며, 10.2에서 다시 등장한다.

FLP 불가능성 — 비동기 합의의 근본 한계

이제 질문을 더 근본적인 곳으로 옮긴다. 노드 여러 개가 하나의 값에 합의해야 한다(예: "누가 리더인가", "이 트랜잭션을 commit할 것인가"). 이 문제를 **합의(consensus)**라 부르고, 다음 세 조건을 만족하는 알고리즘을 찾는 것이 목표다.

• agreement(합의): 모든 올바른 프로세스는 같은 값을 결정한다.
• validity(유효성): 결정된 값은 어떤 프로세스가 제안한 값이어야 한다.
• termination(종료): 모든 올바른 프로세스는 유한한 시간 안에 결정한다.

Fischer, Lynch, Paterson(FLP, 1985)은 다음을 증명했다. 완전히 비동기적인 시스템(메시지 지연에 상한이 없음)에서, 단 하나의 프로세스라도 crash로 실패할 수 있다면, 이 세 조건을 항상 만족하는 결정적(deterministic) 알고리즘은 존재하지 않는다.

증명의 핵심 논증을 따라가 보자. 알고리즘의 실행 상태를 configuration(각 프로세스의 상태 + 전달 중인 메시지)이라 하면, 어떤 configuration에서 이후 실행 결과가 이미 값 0으로 고정된 것을 0-valent, 값 1로 고정된 것을 1-valent, 아직 둘 다 가능한 것을 bivalent라 부른다.

1. 초기 configuration 중 적어도 하나는 bivalent다. 프로세스가 둘 이상이고 서로 다른 초깃값을 제안할 수 있다면, 어떤 프로세스가 먼저 죽느냐에 따라 결정값이 0도 1도 될 수 있는 초기 상태를 구성할 수 있다.
2. bivalent configuration에서, 다음 이벤트를 신중히 고르면 항상 또 다른 bivalent configuration으로 갈 수 있다. 이것이 논문의 "critical step" 논증이다 — 직관적으로, 특정 프로세스 하나의 메시지 처리가 configuration을 0-valent와 1-valent로 갈라놓는 지점이 있다면, 그 프로세스를 골라 그 메시지 전달만 미루고 다른 프로세스들을 먼저 진행시키면 원래의 분기를 다시 bivalent 상태로 되돌릴 수 있다.
3. 이 두 프로세스가 crash 가능하다는 조건과 만난다. 그 "미뤄지는" 프로세스가 실제로는 정상이지만 메시지가 무한히 지연되는 것인지, 아니면 실제로 crash한 것인지 나머지 프로세스는 유한한 시간 안에 구분할 수 없다. 비동기 모델에는 지연의 상한이 없으므로 "조금만 더 기다리면 알 수 있다"는 시점이 존재하지 않는다.

이 세 단계를 이어 붙이면, 적대적인 스케줄러(메시지 전달 순서를 고르는 존재)는 항상 configuration을 bivalent 상태에 묶어 둘 수 있다 — 즉 결정을 무한히 미루는 실행이 항상 존재한다.

여기서 정확히 이해해야 할 것은 이 결과가 "합의는 절대 불가능하다"는 뜻이 아니라는 점이다. "모든 실행에서 유한 시간 안에 반드시 결정한다"를 보장하는 알고리즘이 없다는 뜻이다. 운이 좋은 실행(메시지가 적당히 빨리 도착하는 실행)에서는 합의가 정상적으로 끝난다. FLP가 배제하는 것은 "어떤 스케줄에서도 항상 끝난다"는 보장이다. 정지 문제의 결정 불가능성과 형태는 비슷하지만("모든 경우를 처리하는 알고리즘은 없다") 메커니즘은 다르다. 정지 문제는 계산 가능성 자체의 한계이고, FLP는 계산 가능한 알고리즘이라도 적대적 타이밍 아래서는 종료를 보장할 수 없다는 한계다.

FLP를 우회하는 세 가지 실무 전략

FLP는 "완전 비동기 + 결정적 알고리즘 + 종료 보장"이라는 세 조건이 동시에 성립할 수 없다는 결과다. 실무 시스템은 이 중 하나를 완화한다.

완화하는 조건	전략	대표 사례
완전 비동기	부분 동기성(partial synchrony) — 메시지 지연에 (알려지지 않았거나, 어느 시점 이후부터 적용되는) 상한이 있다고 가정	Raft·Paxos의 타임아웃 기반 리더 선출
종료의 항상 보장	장애 탐지기(failure detector) — "죽었다고 의심됨"이라는 신호를 제공하는 오라클을 추가 가정. 오탐이 있어도 결국 정확해지면(◇W) 합의를 풀 수 있다(Chandra–Toueg, 1996)	하트비트 기반 리더 임대(lease)
결정성	무작위화(randomization) — 각 라운드에서 동전을 던져 대칭을 깨면, 확률 1로 종료를 보장할 수 있다(Ben-Or, 1983)	Raft의 무작위 election timeout

실무에서 가장 흔한 조합은 부분 동기성과 무작위화다. Raft가 election timeout을 고정값이 아니라 무작위 범위(예: 150~300ms)에서 고르는 이유가 바로 이것이다 — 여러 노드가 동시에 후보가 되는 상황(split vote)은 완전한 동기 시스템이라면 반복해서 재현될 수 있는 대칭이지만, 무작위 타이밍이 그 대칭을 깨서 한 노드가 먼저 후보가 될 확률을 높인다. FLP가 말하는 "적대적 스케줄러가 항상 결정을 미룰 수 있다"는 최악의 시나리오를, 무작위성과 "네트워크가 결국은 안정될 것"이라는 부분 동기성 가정으로 실무에서 무력화하는 것이다.

중요한 것은 이 우회가 안전성(safety)은 그대로 지키면서 진행(liveness)만 조건부로 얻는다는 점이다. Raft와 Paxos는 네트워크가 아무리 나빠도(심지어 계속 비동기여도) 잘못된 값에 합의하는 일은 없다 — 안전성은 무조건 지킨다. 다만 진행(누군가 리더가 되고 로그가 전진하는 것)은 네트워크가 "충분히 안정되는" 순간이 와야 보장된다. 이 안전성-진행 분리는 다음 절의 Raft·Paxos를 이해하는 핵심 축이며, 10.2의 CAP 논의로 직접 이어진다.

Raft — 이해 가능성을 설계 목표로 삼은 합의

Raft(Ongaro & Ousterhout, 2014)는 상태 기계 복제(replicated state machine)를 위한 합의 알고리즘이다. 여러 서버가 같은 명령 로그를 같은 순서로 적용하면 같은 상태에 도달한다는 것이 상태 기계 복제의 원리이고, Raft는 그 로그의 순서에 대한 합의를 담당한다.

리더 선출

각 서버는 Follower, Candidate, Leader 세 상태 중 하나다. 시간은 term이라는 단조 증가 정수로 나뉘고, 한 term에는 리더가 최대 하나다(election safety).

Follower ──election timeout 만료──▶ Candidate
Candidate ──과반 득표──▶ Leader
Candidate ──다른 리더의 AppendEntries 수신──▶ Follower
Candidate ──election timeout 재만료(split vote)──▶ Candidate(새 term)
Leader ──더 높은 term을 관찰──▶ Follower

Candidate는 term을 증가시키고 자신에게 투표한 뒤 RequestVote(term, candidateId, lastLogIndex, lastLogTerm)를 모두에게 보낸다. 각 서버는 term당 최대 한 표만 던지며, 후보의 로그가 자신의 로그만큼 최신일 때만 투표한다(lastLogTerm이 더 크거나, 같다면 lastLogIndex가 더 크거나 같아야 한다). 이 규칙이 election restriction이다 — 로그가 뒤처진 후보는 애초에 리더가 될 수 없다.

로그 복제

리더는 AppendEntries(term, prevLogIndex, prevLogTerm, entries[], leaderCommit)로 새 명령을 followers에 전파한다(빈 entries는 heartbeat 역할도 겸한다). Follower는 자신의 로그에서 prevLogIndex 위치의 항목이 prevLogTerm과 일치할 때만 새 항목을 받아들인다. 이 일치 검사가 log matching property를 유지한다 — 두 로그가 같은 index·term의 항목을 가지면, 그 이전 모든 항목도 동일하다는 불변식이다. 불일치가 발견되면 리더는 prevLogIndex를 하나씩 줄여가며 재시도해 follower의 잘못된 항목을 덮어쓴다.

리더는 항목이 과반의 서버에 복제되면 commit으로 간주한다. 단, 한 가지 예외 규칙이 있다 — 리더는 자신의 현재 term에 만든 항목이 과반에 복제됐을 때만 그 항목을 commit으로 표시하며, 이전 term의 항목은 그 규칙만으로 직접 commit하지 않는다. 이전 리더가 만든 항목이 과반에 복제됐어도, 새 리더가 자신의 term에 새 항목을 추가해 그것이 함께 과반에 도달해야 이전 항목까지 안전하게 commit된 것으로 확정한다. 이 규칙이 없으면 과반에 복제됐던 항목이 이후 리더 교체 과정에서 덮어써질 수 있는 사례가 논문에 반례로 제시되어 있다.

안전성 — leader completeness

election restriction과 과반 commit 규칙을 합치면 leader completeness property가 나온다 — 어떤 term에서 commit된 로그 항목은 그보다 높은 모든 term의 리더 로그에 반드시 존재한다. 증명의 핵심은 과반의 교차다.

commit된 항목은 과반 집합 M1에 존재한다.
새 리더가 되려면 과반 집합 M2의 투표가 필요하다.
M1과 M2는 서버가 N대일 때 각각 과반이므로 반드시 교집합이 있다.
→ M1 ∩ M2에 속한 서버 중 적어도 하나는 그 항목을 이미 가지고 있고,
   election restriction 덕분에 그 서버보다 로그가 뒤처진 후보는 투표를 받지 못한다.
→ 새 리더의 로그는 그 commit된 항목을 반드시 포함한다.

이것이 Raft 안전성의 전부다 — 과반의 교차는 항상 성립한다는 집합론적 사실 하나가 split-brain을 구조적으로 막는다. 두 서버가 같은 term에서 동시에 과반의 표를 받는 것은 불가능하다(두 과반은 반드시 겹치고, 겹치는 서버는 한 표만 던졌으므로).

네트워크 분단 시나리오

5대 서버(A~E)가 A를 리더로 정상 동작 중이라고 하자. 네트워크가 {A, B}와 {C, D, E}로 분단된다.

시각	A, B (소수 파티션)	C, D, E (다수 파티션)
t0	A가 리더(term 5)로 정상 동작	정상 동작
t1	분단 발생	분단 발생
t2	A는 계속 리더라고 믿지만 과반(3표) 응답을 못 받아 새 항목을 commit하지 못함	C의 election timeout 만료 → candidate(term 6) → D, E 투표 → 리더 확정
t3	A는 여전히 쓰기 요청을 받지만 client에 성공을 응답할 수 없음(과반 미달)	새 리더 C가 정상적으로 로그를 전진시킴
t4	분단 복구	—
t5	A가 더 높은 term(6)의 메시지를 보고 즉시 Follower로 전환, 자신의 미commit 항목은 폐기될 수 있음	클러스터 전체가 term 6, 리더 C로 수렴

이 표에서 확인할 두 가지가 있다. 첫째, 소수 파티션의 A는 "리더처럼 행동"하지만 과반이 없어 어떤 쓰기도 확정(commit)하지 못한다 — client는 응답을 못 받을 뿐, 잘못된 값이 확정되는 일은 없다(안전성 유지, 가용성 손실). 둘째, term 번호가 fencing 역할을 한다 — 분단이 복구되면 더 높은 term을 가진 리더가 자동으로 우선하고, 낮은 term에서 하던 일은 무효가 된다. 챕터 11.6의 failover와 fencing이 "옛 리더의 쓰기 권한을 박탈해야 한다"고 요구했던 그 메커니즘의 원형이 Raft에서는 term 비교로 구현되어 있다.

Paxos — 같은 문제의 더 오래된, 더 일반적인 해법

Paxos(Lamport, 1998/2001)는 Raft보다 먼저 나온 합의 알고리즘이며 세 역할로 구성된다: proposer(값을 제안), acceptor(값을 수락), learner(결정된 값을 학습). 실무 구현은 흔히 한 프로세스가 여러 역할을 겸한다.

두 단계 프로토콜

Phase 1a (Prepare)   proposer → acceptors: Prepare(n)   (n: 이전에 쓴 적 없는 제안 번호)
Phase 1b (Promise)   acceptor → proposer: n보다 작은 제안은 앞으로 거부하겠다고 약속.
                      단, 이미 수락한 제안이 있다면 그 (번호, 값)도 함께 반환.
Phase 2a (Accept)    proposer가 과반의 Promise를 받으면:
                      반환된 것 중 가장 번호가 높은 값이 있으면 그 값을, 없으면 자신의 값을
                      Accept(n, v)로 전송.
Phase 2b (Accepted)  acceptor는 n보다 높은 번호를 이미 promise하지 않았다면 수락하고 응답.

과반의 acceptor가 (n, v)를 수락하면 v가 **선택(chosen)**된 것이다. 안전성은 Raft와 같은 원리 — 과반의 교차 — 에서 나온다. 어떤 제안자가 더 높은 번호 n'으로 Prepare를 보내도, 과반의 acceptor에게 물어보는 한 이전에 선택된 값을 수락한 acceptor를 반드시 한 명 이상 만나게 되고, Phase 2a 규칙("반환된 것 중 가장 번호가 높은 값을 그대로 쓴다")이 이미 선택된 값을 다시 제안하도록 강제한다. 즉 한 번 선택된 값은 이후 어떤 라운드에서도 절대 바뀌지 않는다.

Raft와의 관계

기본 Paxos는 값 하나에 대한 합의만 다룬다. 로그 전체를 복제하려면 로그 위치마다 별도의 Paxos 인스턴스를 돌려야 하고(Multi-Paxos), 매 값마다 Phase 1을 반복하는 비용을 줄이려면 안정된 리더를 세워 Phase 1을 생략하는 최적화가 필요하다 — 이 최적화를 하고 나면 사실상 Raft와 같은 모양(리더가 로그를 순서대로 밀어 넣는 구조)이 된다. 차이는 명세의 층위다. Paxos는 "안전한 합의"라는 최소 프로토콜을 아주 일반적으로 정의하고 리더 선출·로그 관리·멤버십 변경 같은 실무적 요소는 구현자에게 맡긴다. Raft 논문은 정확히 이 지점을 문제로 지목했다 — Paxos는 실무 시스템을 만들기 위한 뼈대로 쓰기에는 설명되지 않은 부분이 너무 많고, 그 공백을 각 구현이 다르게 채우면서 이해와 검증이 어려워졌다는 것이다. Raft는 강한 리더, 명시적인 로그 일치 검사, 제한된 리더십 이전 규칙을 처음부터 명세에 포함시켜 "이해 가능성(understandability)"을 1급 설계 목표로 삼았다.

두 알고리즘은 안전성의 근거(과반 교차)가 같고, 표현력도 동등하다(둘 다 crash-fault-tolerant 상태 기계 복제를 푼다). 실무에서 무엇을 골라 쓸지는 알고리즘 자체보다 검증된 구현(etcd의 Raft, Chubby·ZooKeeper 계열의 Paxos/ZAB 변형)이 있는지가 더 큰 판단 기준이다.

실무 관점

"타임아웃을 늘리면 더 안전해진다"는 오해

election timeout, RPC timeout 같은 값은 진행(liveness)의 파라미터이지 안전성(safety)의 파라미터가 아니다. Raft와 Paxos는 타임아웃을 아무리 잘못 설정해도(너무 짧아 계속 리더가 바뀌든, 너무 길어 장애 감지가 늦든) 잘못된 값에 합의하는 일은 없다 — 과반 교차라는 안전성의 근거는 타이밍과 무관하기 때문이다. 타임아웃을 조정해서 얻거나 잃는 것은 오직 가용성과 지연이다. "합의 알고리즘을 쓰는데도 데이터가 갈렸다"는 장애가 있다면, 원인은 타임아웃 설정이 아니라 구현이 과반 교차 규칙을 어딘가에서 어겼거나(예: 자체 구현한 리더 선출에 election restriction이 빠짐), Byzantine 실패(다음 절 참고)를 crash 실패로 잘못 가정한 경우일 가능성이 크다.

split-brain은 합의로 예방하고, fencing은 그 적용이다

챕터 11.6에서 본 "옛 primary가 partition 반대편에서 계속 쓰기를 받는" 문제를 이 문서의 언어로 다시 보면, 옛 primary는 소수 파티션에 남아 과반을 얻지 못하는 Raft 리더와 같은 처지다. 차이는 DB 복제가 반드시 Raft급 합의로 리더를 정하지는 않는다는 점이다 — 단순 primary-backup 구성에서는 fencing을 별도 메커니즘(epoch 토큰, storage fence, 운영자 개입)으로 직접 구현해야 한다. 합의 알고리즘 위에 구축된 시스템은 term/epoch 비교가 fencing을 자동으로 제공하지만, 그렇지 않은 시스템은 이 문서가 보여준 term의 역할을 다른 수단으로 재발명해야 한다는 뜻이다.

직접 합의 알고리즘을 구현하지 않는다

Raft의 상태 기계 자체는 이 문서의 설명만으로 이해할 수 있는 수준이지만, 프로덕션 구현은 스냅샷·로그 압축·멤버십 변경(joint consensus)·클럭 드리프트가 있는 실제 네트워크 조건까지 다뤄야 하며 미묘한 경계 조건에서 안전성이 깨지기 쉽다. 검증된 라이브러리(etcd/raft, Hashicorp raft)나 이미 합의를 내장한 시스템(ZooKeeper, etcd, Consul)을 조정 계층으로 쓰는 것이 실무의 기본값이다.

더 깊이

crash-fault와 Byzantine-fault

이 문서가 다룬 Raft·Paxos는 모두 crash-fault-tolerant다 — 실패한 노드는 멈추거나 응답하지 않을 뿐, 거짓 정보나 모순된 메시지를 적극적으로 보내지 않는다고 가정한다. 노드가 악의적이거나 소프트웨어 결함으로 임의의(모순되는) 메시지를 보낼 수 있는 환경(Byzantine fault)에서는 다른 부류의 프로토콜(PBFT 등, 일반적으로 3f+1대의 노드로 f개의 Byzantine 실패를 견딤)이 필요하다. 블록체인의 합의 프로토콜 다수가 이 범주에 속한다. 일반적인 사내 분산 시스템(같은 조직이 모든 노드를 통제하는 클러스터)은 crash-fault 가정으로 충분한 경우가 대부분이며, 이 문서의 범위도 여기까지로 한정한다.

Raft의 election timeout과 무작위성의 실제 효과

Raft 논문은 election timeout을 무작위 범위에서 뽑는 것만으로 대부분의 split vote를 막을 수 있음을 실험으로 보였다(150~300ms 범위, 하트비트 주기 대비 충분히 큰 값). 이후 실무 구현(etcd 등)은 소수 파티션에 갇힌 노드가 계속 term만 올리며 재선거를 시도하다가, 분단이 복구된 순간 더 높은 term으로 정상 리더를 실각시키는 부작용을 줄이기 위해 PreVote(정식 선거 전에 "내가 후보가 되면 표를 얻을 수 있을지" 사전 질의하는 단계)를 추가로 도입했다. 이는 원 논문의 범위를 넘는 구현 확장이지만, 안전성 근거(과반 교차)는 그대로 유지한 채 가용성만 개선한다는 점에서 이 문서가 세운 안전성-진행 분리의 좋은 예다.

정리

• 부분 실패는 성공·실패·모름의 세 상태이며, 타임아웃은 실패 판정이 아니라 모른다는 관찰이다. 안전한 재시도는 멱등성을 전제해야 하고, exactly-once는 전달이 아니라 처리 효과 수준에서만 달성된다.
• Lamport 논리 시계는 인과관계와 모순되지 않는 전순서를 주지만 동시 이벤트를 구분하지 못한다. vector clock은 각 프로세스별 성분을 유지해 인과관계를 정확히 포착하는 대가로 크기 비용을 낸다.
• FLP 불가능성은 완전 비동기 + 결정적 알고리즘 + crash 1개 허용이라는 조건에서 합의의 항상 종료를 보장할 수 없음을 증명한다. 실무는 부분 동기성·장애 탐지기·무작위화로 이 조건을 완화해 우회한다.
• Raft와 Paxos는 모두 과반의 교차라는 집합론적 사실로 안전성을 지킨다. 안전성은 타이밍과 무관하게 항상 성립하고, 진행(리더 선출·commit)만 네트워크 조건에 의존한다 — 소수 파티션은 안전하게 멈출 뿐 잘못된 값을 확정하지 않는다.

확인 문제

1. 결제 서비스가 idempotency key 없이 "타임아웃이면 최대 3번 재시도"하는 정책을 쓰고 있다. 이 정책이 위험한 이유를 부분 실패의 삼분법으로 설명하고, 최소한의 수정 방향을 제시하라.

정답과 해설

타임아웃은 요청 미도달·응답 유실·처리 중단 중 무엇인지 구분하지 못하는 관찰이다. 서버가 이미 결제를 완료했는데 응답만 유실된 경우("모름"의 한 갈래) 재시도는 결제를 중복 실행시킨다. 최소 수정은 클라이언트가 요청마다 고유한 idempotency key를 생성하고, 서버가 그 key로 이미 처리된 요청인지 확인한 뒤 처리와 key 기록을 원자적으로 묶는 것이다. 이 원자성이 없으면 "확인"과 "처리" 사이에 또 다른 race window가 생긴다.

2. 두 이벤트 x, y의 Lamport 타임스탬프가 각각 5, 7이다. "x가 y보다 먼저 일어났다"고 말할 수 있는가? vector clock이었다면 답이 어떻게 달라지는가?

정답과 해설

Lamport 타임스탬프만으로는 말할 수 없다. a → b이면 L(a) < L(b)가 보장되지만 역은 성립하지 않으므로, x와 y가 서로 무관한 동시 이벤트인데 우연히 다른 값을 받았을 가능성을 배제할 수 없다. vector clock이었다면 V(x) ≤ V(y)(모든 성분에서, 적어도 하나는 엄격히 작음)를 직접 확인해 인과관계 여부를 정확히 판정할 수 있다. 두 벡터가 서로 비교 불가능하다면 동시 이벤트임이 확정된다.

3. "FLP 불가능성 때문에 Raft 같은 실무 합의 알고리즘은 이론적으로 안전하지 않다"는 주장을 평가하라.

정답과 해설

틀렸다. FLP가 배제하는 것은 "모든 실행에서 유한 시간 안에 항상 종료를 보장하는 결정적 알고리즘"이지, 합의 자체의 안전한 실행이 아니다. Raft는 부분 동기성과 무작위 타임아웃으로 종료(진행)를 조건부로 얻고, 안전성(과반 교차로 인한 정확성)은 네트워크 상태와 무관하게 항상 지킨다. 즉 나쁜 네트워크 조건에서는 리더를 못 뽑고 멈출 수 있지만(진행 실패), 잘못된 값에 합의하는 일은 없다(안전성 유지). 이 구분이 FLP를 실무에서 우회하는 정확한 방식이다.

4. 5노드 Raft 클러스터가 {A,B}(소수)와 {C,D,E}(다수)로 분단됐다. 분단 중 A가 클라이언트로부터 쓰기 요청을 받는다면 무슨 일이 일어나는가? 분단이 복구되면 어떻게 되는가?

정답과 해설

A가 이전 term의 리더였더라도 과반(3표)의 응답을 받을 수 없으므로 어떤 새 로그 항목도 commit으로 확정하지 못한다. 클라이언트는 응답을 받지 못하거나 명시적 실패를 받는다 — 가용성은 잃지만 잘못된 값이 확정되지는 않는다. 한편 다수 파티션에서는 C가 새 term으로 리더가 되어 정상적으로 진행한다. 분단이 복구되면 A는 더 높은 term을 관찰하는 즉시 Follower로 전환하고, 자신이 commit하지 못한 항목은 새 리더의 로그로 덮어써질 수 있다. term 비교가 fencing 역할을 대신한다.

참고 자료

• Leslie Lamport, "Time, Clocks, and the Ordering of Events in a Distributed System" (CACM 1978) — happens-before와 논리 시계의 원 논문. 본문의 Lamport clock 정의가 여기서 나온다.
• Colin J. Fidge, "Timestamps in Message-Passing Systems That Preserve the Partial Ordering" (1988), Friedemann Mattern의 독립 연구와 함께 vector clock을 처음 제시한 논문 중 하나다.
• Michael J. Fischer, Nancy A. Lynch, Michael S. Paterson, "Impossibility of Distributed Consensus with One Faulty Process" (JACM 1985) — FLP 불가능성의 원 증명. 본문의 bivalent configuration 논증이 여기서 나온다.
• Cynthia Dwork, Nancy Lynch, Larry Stockmeyer, "Consensus in the Presence of Partial Synchrony" (JACM 1988) — 부분 동기성 모델로 FLP를 우회하는 조건을 formal하게 정의한다.
• Diego Ongaro, John Ousterhout, "In Search of an Understandable Consensus Algorithm (Extended Version)" (USENIX ATC 2014) — Raft의 원 논문. 본문의 리더 선출·로그 복제·안전성 논증 전체의 1차 출처다.
• The Raft Consensus Algorithm — 원 저자들이 제공하는 시각화 데모. 리더 선출과 분단 시나리오를 직접 조작하며 확인할 수 있다.
• Leslie Lamport, "Paxos Made Simple" (2001) — 저자 본인이 원 Paxos 논문을 재정리한 버전. 본문의 Phase 1/2 설명이 이 구성을 따른다.