consensus 알고리즘은 어떻게 동작할까?

N 대 컴퓨터가 같은 값에 동의해야 한다. 일부는 죽고, 일부는 느리고, 네트워크는 패킷을 떨어뜨린다. 이 상황에서 "진실은 뭐인가" 를 결정하는 문제 = consensus. etcd / Consul / ZooKeeper / Kafka controller / Spanner — 모든 distributed 시스템의 바닥. 이 가이드는 Paxos · Raft 의 메커니즘, FLP 불가능성, 왜 실전에서 Raft 가 이겼는지 정리한다.

Consensus 가 푸는 문제

5 대 서버: A, B, C, D, E
client 가 "x = 42 로 박아줘" 요청.

Naive: 한 대만 받음 — 그 서버 죽으면 데이터 손실
모든 대 받음? — 동기화 비용 ↑, 한 대 느리면 전체 멈춤
과반수 (3/5)?  → consensus 의 핵심 아이디어

요구사항:
- safety: 다른 값에 동의하면 안 됨 (split-brain X)
- liveness: 일정 시간 안에 결정 (한 대 죽어도 진행)

FLP 불가능성 (1985)

Fischer-Lynch-Paterson 정리: 완전히 비동기 환경에서 한 대라도 fail 가능하면 consensus 보장 불가능.

"이 서버가 죽었는가 / 느린가" 를 비동기에서는 구분 불가
→ 죽었다 가정하고 진행? → 사실 살아있어서 동시 결정 → split-brain
→ 살아있다 가정하고 대기? → 영원히 멈춤 (liveness 손실)

해결: 부분 동기 (partial synchrony) 가정 + timeout 기반
- 보통은 비동기, 가끔 동기 가정 깨짐
- timeout 으로 "느리면 죽었다 취급" — 가짜 양성 OK
- safety 는 보장, liveness 는 "결국 진행" 정도로 완화

Paxos (1990, Lamport)

Consensus 의 최초 정형 알고리즘. 두 단계 (Prepare → Accept) 의 2-phase commit 패턴.

Proposer (값 제안하는 서버) → Acceptors (과반수 acceptor 의 동의)

Phase 1 — Prepare:
  Proposer 가 ballot number n 으로 "prepare(n)" 모든 acceptor 에게
  Acceptor: n > 본 적 있는 모든 n' 이면 → "promise(n)" 반환
                                 + 이전 accept 한 값 v 가 있으면 함께

Phase 2 — Accept:
  과반수 promise 받으면 → 값 결정
    (이전 accept 한 v 있으면 그 값 / 없으면 자기 값)
  "accept(n, value)" 모든 acceptor 에게
  과반수 acceptor 가 accept 하면 → 결정됨

특징:
- 두 phase × 두 RTT — latency 큼
- 동시에 여러 proposer = livelock (서로 ballot 올리기 경쟁)
- 매우 단순하지만 이해 어려움 (Lamport 본인 "the part-time parliament"
  논문이 너무 추상적이라 후속 논문으로 다시 설명)

Multi-Paxos / Raft — 실용 진화

Paxos 를 매 결정마다 돌리면 latency 큼. 한 leader 가 잠시 유지되며 여러 결정 처리 → Multi-Paxos. Raft (2014) 는 같은 아이디어를 더 이해하기 쉽게 재구성.

Raft 의 3 단계

1. Leader Election (한 leader 뽑기)
   - 모든 follower 가 election timeout (150-300ms random)
   - timeout 지나도 leader 의 heartbeat 안 오면 → candidate 변경
   - 자신 vote + 다른 서버에 vote 요청
   - 과반수 vote 받으면 → leader, 새 term 시작

2. Log Replication (값 박기)
   - client 요청 → leader 가 자기 log 에 append
   - follower 들에게 AppendEntries RPC (heartbeat 겸용)
   - 과반수 follower 의 ack → commit + state machine 적용
   - follower 들에게 "commit 됐다" 알림

3. Safety (split-brain 방지)
   - 새 leader 는 이전 leader 의 모든 commit log 포함해야 (vote 시 검증)
   - 같은 term 에서는 한 leader 만

Quorum — 과반수의 마법

5 대 cluster:
- write quorum: 3/5 (과반수)
- read quorum: 3/5 (선택적, 보통 leader 만 읽음)

왜 과반수?
  과반수 두 그룹은 반드시 하나 이상의 서버에서 겹침
  → 같은 서버가 두 결정 다 보면 → 일관성 자동 보장

cluster size 추천: 홀수
- 3 대: 1 fail 허용
- 5 대: 2 fail 허용
- 7 대: 3 fail 허용 (그러나 commit latency ↑)

짝수도 가능하지만 "과반수" 의미가 애매 (4/8 vs 4/8 split-brain 가능)

Split-Brain — 가장 위험한 실패

network partition:
[A, B, C]  ←→ [D, E]   (가운데 끊김)

만약 두 partition 모두 leader 뽑으면? → split-brain
  - [A,B,C] 의 leader 가 "x=1" 결정
  - [D,E] 의 leader 가 "x=2" 결정
  - partition 회복 시 → 어느 게 맞나?

방지:
- 과반수 (3/5 또는 2/3) 만 leader 가능
- [D,E] 는 2 뿐 → 과반수 못 만듦 → leader 못 뽑음
- [A,B,C] 만 progress

대가: minority partition 은 진행 못 함 (availability 손실, CAP 의 P)

실제 시스템들

왜 실전에서 Raft 가 Paxos 를 이겼나

• 이해도 — Paxos 는 "내가 정말 이해했나" 가 어려움. Raft 는 명시적 단계 (leader / log / safety) 로 학습 곡선 완만. Raft 의 논문 제목 자체가 "In Search of an Understandable Consensus Algorithm".
• 구현 단순 — Multi-Paxos 의 구현 detail (ballot 관리, optimization) 이 vendor 마다 다름. Raft 는 spec 이 명확.
• 오픈소스 reference — etcd / hashicorp/raft 같은 production-grade 구현이 공개되어 borrow 쉬움.

흔한 함정

• 3 대 cluster 의 위험 — 1 대 fail 시 quorum = 2/3 OK 지만, 동시에 2 대 fail (예: 같은 AZ 정전) 시 전체 down. AZ 별 분산 필수.
• leader 의 high latency 가 throughput 발목 — 모든 write 가 leader 거쳐 quorum. read replica 로 read scale, write 는 leader 한 대 한계.
• cluster 규모 변경 (membership change) 의 전이성 — joint consensus 같은 protocol 필요. 잘못하면 split-brain.
• log 의 크기 폭증 — snapshot 으로 압축. 그러나 snapshot install 도 IO 큼.
• clock skew 가정 — Raft 는 NTP-level (수십 ms) 이면 OK. Spanner 의 TrueTime 같은 sub-ms clock 은 별도 영역.

마무리

Consensus 는 distributed 시스템의 atomic primitive — 위에 모든 일관성 보장이 build. Paxos 가 먼저, Raft 가 이해 단순함으로 mainstream.

consensus 의 cost 가 모든 distributed write 의 cost 결정. 그래서 모든 작업을 consensus 거치지 않고 — 일부만 strong, 나머지는 eventual 하게 분리하는 게 실용 디자인.