분산 합의 완전 정복 — Paxos, Raft, ZAB, FLP, etcd, ZooKeeper, KRaft, BFT, CRDT까지 (2025)

"The problem with distributed systems is that the parts of the system you don't think about are the parts that will fail." — Leslie Lamport

왜 Kubernetes는 etcd에 의존하는가? 왜 Kafka는 ZooKeeper를 KRaft로 대체했는가? 왜 PostgreSQL HA 솔루션 Patroni는 "DCS"(Distributed Configuration Store)를 요구하는가? 답은 하나다. 분산 합의(consensus).

여러 노드가 하나의 결정에 "동의"하는 일은 로컬에서는 trivial이지만, 네트워크가 끼면 수학적으로 증명된 불가능의 영역이 된다. 이 글은 FLP 정리의 충격에서 시작해, Paxos와 Raft의 우아함, 그리고 2025년의 합의 지형(KRaft, BFT, CRDT)까지 한 번에 훑는 지도다.

1. 문제 정의 — "동의"가 왜 어려운가

합의가 보장해야 하는 것

Agreement (동의성) — 모든 정상 노드가 같은 값에 도달
Validity (유효성) — 결정된 값은 어떤 노드가 제안한 값이어야
Termination (종료성) — 결국 결정이 난다

분산 환경의 적대적 현실

네트워크 지연: 메시지가 언제 도착할지 모름
메시지 유실: 사라질 수 있음
노드 크래시: 무응답
네트워크 분할: 일부 노드들끼리만 통신 가능
비동기 환경: 글로벌 시계 없음

FLP 불가능성 정리 (1985)

Fischer, Lynch, Patterson의 충격적인 증명:

비동기 분산 시스템에서, 하나의 노드라도 fail-stop 할 수 있다면, 결정론적 합의 알고리즘은 불가능하다.

즉, "Agreement + Validity + Termination"을 완벽히 만족하는 알고리즘은 수학적으로 존재할 수 없다.

그럼 어떻게?

확률적 종료성: 결국 종료되지만 보장 안 함
부분 동기성 가정: "언젠가는 메시지 지연이 bounded"
타임아웃 기반 failure detector
라이브니스 vs 안전성 트레이드오프 — 안전성(Safety)는 항상, 진행성(Liveness)는 좋은 조건에서

Paxos, Raft 모두 이 방향이다.

2. Paxos — Lamport의 기념비

등장

Leslie Lamport가 1990년 논문 "The Part-Time Parliament"로 제안. 고대 그리스 Paxos 섬의 의회를 빗댄 풍자였다. 리뷰어들이 농담을 이해 못 해서 거절당했고, 1998년에야 간신히 게재.

2001년 "Paxos Made Simple"에서 다시 설명했지만... 여전히 어렵다. Lamport 본인조차:

"나는 Multi-Paxos 구현을 해본 적이 없다."

기본 Paxos 역할

Proposer — 값을 제안
Acceptor — 제안을 수락/거절
Learner — 결정된 값을 학습

2-Phase 프로토콜

Phase 1 (Prepare)

Proposer가 번호 n 선택, Prepare(n) 방송
Acceptor가 "n보다 큰 번호를 본 적 없으면" 약속 + 이전에 수락한 값 반환

Phase 2 (Accept)

과반 응답을 받으면, 기존 수락값이 있으면 그 값을, 없으면 자신 값을 Accept(n, v) 방송
Acceptor는 "n보다 큰 약속 없으면" 수락
과반 수락 시 결정

왜 이게 어려운가

여러 Proposer 동시 시도 시 진행이 멈출 수 있음(liveness 문제)
Multi-Paxos — 리더 선출로 효율화, 하지만 엔지니어링 디테일이 지옥
실무적 구현 자료 부족 — 의사코드와 실제 구현 사이의 간극 거대

실제 사용 사례

Google Chubby (Paxos 기반 락 서비스, ZooKeeper의 할아버지)
Google Spanner (진화된 Paxos)
CockroachDB (Multi-Raft지만 영향)

3. Raft — "이해 가능한 합의"

동기

2014년 Diego Ongaro & John Ousterhout(Stanford)가 논문 "In Search of an Understandable Consensus Algorithm"을 발표. 목표는 단 하나: Paxos보다 이해 가능하게.

핵심 분해

Raft는 합의 문제를 세 부분으로 나눈다:

Leader Election — 리더 뽑기
Log Replication — 리더가 로그 복제
Safety — 리더가 죽어도 일관성

상태

각 노드는 세 상태 중 하나:

Follower — 리더 메시지 수동 수신
Candidate — 선거 중
Leader — 리더

Leader Election

Follower가 electionTimeout(150-300ms 랜덤) 동안 리더에게서 heartbeat 못 받으면 Candidate로 전환
Term 증가, 자기 투표 + RequestVote 방송
과반 득표 → Leader. 동률이면 타임아웃 후 재시도.
랜덤 타임아웃 덕에 split vote가 자연 해소됨

Log Replication

클라이언트 → 리더로 요청
리더가 자기 로그에 append, 팔로워에게 AppendEntries 방송
과반 팔로워 확인 시 "committed"
리더가 상태머신에 적용, 클라이언트 응답
팔로워도 commit index 전달받아 적용

Safety — Log Matching Property

두 로그가 같은 인덱스에 같은 term의 엔트리를 가지면, 그 이전 모든 엔트리도 같다
리더 선출 시 "가장 최신 로그를 가진 노드만 리더가 될 수 있음" (Election Restriction)
이전 term의 로그는 자기 term의 로그와 함께 커밋 (Figure 8 시나리오 방지)

Raft의 실제 구현

etcd (CoreOS → CNCF) — Kubernetes 컨트롤 플레인의 심장
Consul (HashiCorp)
TiKV (Multi-Raft)
Kafka KRaft (2022년 ZooKeeper 대체)
CockroachDB (Multi-Raft)

Joint Consensus — 멤버십 변경의 우아함

노드 추가/제거 시 두 설정이 공존하는 Joint Consensus 단계를 거쳐 무정지 변경. 실수하면 split brain의 지름길이라 논문이 크게 강조.

4. ZooKeeper와 ZAB

ZooKeeper의 역사

2007년 Yahoo가 개발, Hadoop 생태의 분산 코디네이터
Apache 톱 프로젝트
Kafka, Hadoop, HBase, Solr 등 수많은 시스템이 의존

ZAB (ZooKeeper Atomic Broadcast)

Paxos와 유사하지만:

FIFO 순서 보장 — 특정 클라이언트 요청 순서를 유지
Primary-Backup 모델 — 리더가 모든 쓰기 중개
에포크(epoch) 기반 — term과 유사한 세대 번호

Znode 모델

계층적 경로 (/app/config/foo)
Ephemeral — 세션 끊기면 자동 삭제 (Leader Election용)
Sequential — 자동 증가 번호 (Lock 구현)
Watch — 변경 알림 (pub/sub처럼)

ZooKeeper의 유즈케이스

Leader Election (ephemeral + sequential)
분산 락 (sequential znode 경쟁)
설정 저장소
서비스 디스커버리
Kafka 브로커 메타데이터 (KRaft 이전)

한계

JVM 기반 — GC 일시정지 시 세션 만료 → 장애 연쇄
쓰기 확장 어려움 — 리더 단일 병목
운영 복잡 — 서버 수 홀수, quorum 유지
세션 모델의 함정 — 초심자의 디버그 지옥

5. KRaft — Kafka가 ZooKeeper를 버린 이유

동기

Kafka는 ZooKeeper에 브로커/토픽/파티션/ACL 메타데이터를 저장
대규모에서 ZooKeeper가 병목 (수만 파티션 등록/해제)
2개의 분산 시스템을 운영하는 부담
이중 인증/보안 설정

KRaft 등장

KIP-500 (2019 제안)
2022년 Kafka 3.3에서 Production Ready
2023년 3.5에서 ZooKeeper Deprecated
2025년 4.0에서 완전 제거

내부

특별한 메타데이터 토픽 __cluster_metadata
Controller 노드들이 Raft로 이 토픽에 합의
브로커들은 이 토픽을 replica로 팔로우 (zero-downtime)
리더 전환, 토픽 생성 등이 이 로그의 append로 표현

이점

시작 속도 10배 이상 빨라짐
수백만 파티션 지원 가능
운영 단순화
Kafka-only 배포

마이그레이션

ZooKeeper → KRaft 마이그레이션은 2024-2025에 대형 기업들이 일제히 진행. "모든 Kafka 클러스터는 결국 KRaft로 수렴한다."

6. etcd — Kubernetes의 심장

왜 Kubernetes가 etcd인가

K8s API Server의 모든 상태(Pod, Service, ConfigMap, Secret)는 etcd에 저장. 리더 선출, 분산 락도 etcd 기반.

Raft 구현

Go로 Raft 구현 (go.etcd.io/raft)
분산 key-value store
버전(revision) 기반 스냅샷
watch 기능으로 변경 스트림

성능 특성

쓰기 지연: 10-30ms (replication + fsync)
초당 쓰기: 단일 리더 ~10K
용량: 8GB 기본 제한 (수백만 키)
etcd는 고성능 DB가 아니라 고가용 KV

운영 팁

SSD 필수 — fsync가 바닥
전용 네트워크, 낮은 레이턴시
defrag 주기적으로 (compaction과 별개)
백업 자동화 — etcdctl snapshot save
Kubernetes 클러스터 전체 복구가 이것에 달림

etcd vs ZooKeeper vs Consul

측면	etcd	ZooKeeper	Consul
언어	Go	Java	Go
합의	Raft	ZAB	Raft
데이터 모델	flat KV	계층 tree	KV + 서비스 디스커버리
Watch	스트림	일회성	스트림
헬스체크	외부	Ephemeral	내장
주 사용처	Kubernetes	Kafka(구), Hadoop	Service mesh, 레거시 HA

2025년 대세: 신규 프로젝트는 etcd 또는 Consul, Kafka는 KRaft로.

7. Byzantine Fault Tolerance (BFT)

비잔틴 장군 문제

Lamport의 고전적 문제 (1982): 적진을 포위한 장군들이 메시지로 공격/후퇴를 합의하려는데, 배신자 장군이 있어 거짓 메시지를 보낼 수 있다. 과반이 올바른 결정에 도달하려면?

Paxos/Raft는 BFT인가?

아니다. 이들은 **Crash Fault Tolerant (CFT)**만 가정:

노드는 멈춰서 사라지지만, 거짓말을 하지 않음
메시지는 유실될 수 있지만 조작되지 않음

악의적 노드(해킹, 버그)가 있으면 Paxos/Raft는 깨진다.

PBFT (Practical Byzantine Fault Tolerance)

1999년 Castro & Liskov 제안
$n \geq 3f + 1$ 노드 필요 (f는 비잔틴 노드 수)
즉 1명의 악의 허용하려면 4대, 2명이면 7대
3-phase 프로토콜: Pre-prepare → Prepare → Commit

HotStuff (2018)

Facebook Libra(현 Aptos/Sui) 기반
BFT에 chain-like 단순함 부여
선형 메시지 복잡도

블록체인과 BFT

Tendermint (Cosmos) — BFT 기반
Algorand, Avalanche, Aptos, Sui — 모두 BFT 변형
Bitcoin/Ethereum PoW/PoS는 확률적 합의 (다른 범주)

기업에서 BFT가 필요한가?

일반 내부 시스템: Raft/Paxos로 충분
여러 조직 공유 인프라 (은행 간, 정부 간): BFT 검토
2025년 Hyperledger Fabric, Corda 같은 엔터프라이즈 블록체인에서 BFT가 실무 대상

8. CRDT — 합의 없이도 수렴하는 마법

동기

합의는 비싸다. 네트워크 왕복 + 과반 동의가 필요. 오프라인에서는 작동도 안 한다. 그런데...

**협업 문서(Google Docs), 채팅(WhatsApp), 장바구니(Shopping Cart)**는 합의 없이도 "결국 동일한 상태로 수렴"한다. 어떻게?

CRDT (Conflict-free Replicated Data Type)

Strong Eventual Consistency 보장
어느 순서로 병합해도 같은 결과
Commutativity + Associativity + Idempotency

2가지 종류

State-based (CvRDT): 전체 상태를 공유, merge(a, b)가 semilattice (∨) 연산

G-Counter (증가만), PN-Counter, OR-Set, LWW-Register

Operation-based (CmRDT): 연산을 공유, 메시지는 순서/신뢰 보장 채널로 전송

더 효율적이지만 조건 엄격

유명한 CRDT 구현

Automerge — JSON-like 데이터 협업
Yjs — 문서 협업 (VS Code Live Share, Notion 후보 검토)
Riak (2010s) — CRDT 기반 분산 DB
Redis — CRDT enterprise (Active-Active)
Figma — 자체 CRDT 변형

2024년 이후 — Local-First

Local-First Software 운동
오프라인 우선 + CRDT 동기화
서버 없이도 작동
Jamsocket, Automerge, Y.js가 리더

9. 약한 일관성 모델들

일관성 스펙트럼

강 ← Linearizable → Sequential → Causal → Eventual → 약

Linearizable (Strong Consistency)

모든 연산이 하나의 전역 순서
한 번 쓰면 모든 독자가 봄
Raft/Paxos 기반 시스템이 제공
비용: 지연 ↑, 가용성 ↓

Causal Consistency

원인-결과 관계만 보존 (병행은 자유)
Vector Clock / Version Vector 활용
COPS, Eiger 논문
소셜 타임라인에 충분

Eventual Consistency

"언젠가는" 수렴
DynamoDB 기본, Cassandra 기본
성능 ↑, 일관성 ↓
비극: 아직 AP 쪽 시스템을 CA처럼 쓰는 팀이 많음

CAP 정리의 오해

Brewer(2000) — "네트워크 분할 시 Consistency OR Availability 중 하나 포기"
흔한 오해: "C/A/P 중 둘만 고르기"
실제: 분할(P)은 피할 수 없으므로 C vs A 중 선택
현대는 PACELC로 확장: 분할이 없어도 Latency vs Consistency 선택 필요

10. 분산 락 — 합의의 응용

ZooKeeper 방식

/locks/resource/ 아래 sequential + ephemeral znode 생성
자기보다 작은 번호 znode를 watch
그게 삭제되면 자기 차례

etcd 방식

lease = client.grant(10)  # 10초 TTL
client.put("/lock", "me", lease)  # 성공하면 락 획득

compare-and-swap으로 원자적 획득
TTL로 좀비 락 방지

Redlock (Redis) — 논란

앞선 Redis 글에서 다룬 대로:

성능용이면 OK
정확성이 중요하면 ZooKeeper/etcd 사용

Fencing Token

락 획득 시 단조 증가 토큰 발급
자원에 쓰기 시 토큰 확인 → 오래된 토큰 거부
GC 정지/네트워크 지연 복구 후 좀비 쓰기 방지

11. 리더 선출 실전 — 실수 안내

Split Vote

Raft에서 여러 Candidate가 같은 term에 동시에 투표 시작 → 아무도 과반 못 얻음

해결: 랜덤 타임아웃 (150-300ms)
선거는 한 번만 있어야 함 (consensus round 낭비)

Leader Flapping

네트워크 불안정으로 리더가 빈번히 바뀜:

커넥션 리셋 → commit 지연
증상: leader changed 로그 폭주
해결: 네트워크 안정화, heartbeat 주기 조정, PreVote (리더 되기 전 Pre-election)

Network Partition (Brain Split)

과반 없는 쪽은 읽기/쓰기 거부 (잘 설계된 경우)
잘못 설계: 양쪽이 리더 → 데이터 분기
복구: 한 쪽 강제 폐기, 다른 쪽에서 재복제

Clock Drift

Raft는 시계 동기 가정이 약함 (타임아웃만)
그래도 NTP는 기본
Spanner는 TrueTime(GPS + 원자시계)로 글로벌 linearizable 제공

12. 2025년 합의 지형

주류

Raft — 사실상 신규 시스템의 기본값
Multi-Raft — 샤드별 Raft 그룹 (CockroachDB, TiKV, YugabyteDB)
Paxos/EPaxos — Google 내부, 일부 DB
ZAB — ZooKeeper, 신규 채택 거의 없음

부상

HotStuff — 메타(Libra) 기원, 엔터프라이즈 BFT로 확산
Narwhal & Bullshark (Sui/Aptos) — 메시지 격리 최적화
Paxos-like Quorum Read/Write — etcd, Spanner의 실제 읽기 경로

프론티어

FastPaxos / MencLib — 최적 경로에서 1-RTT
Generalized Paxos — 명령 의존성 기반 합의
Rollups 합의 — Ethereum L2의 sequencer consensus

13. 분산 합의 안티패턴 TOP 10

"직접 Paxos 구현" 시도 — 실패 확정
Raft 라이브러리 포크 후 패치 남발 — 업스트림 놓침
홀수 노드 아닌 4대 cluster — Quorum(3)이 두 번 분할 허용
WAN에 걸친 합의 — 지연 폭발, regional split
ZooKeeper 세션 타임아웃 기본값 방치 — GC 길면 잦은 연쇄
etcd 8GB 제한 무시 — 어느 날 갑자기 장애
비잔틴이 필요한 환경에 Raft — 악의 노드가 모든 걸 망침
합의 시스템에 대량 쓰기 — KV만, 1MB 넘는 값 금지
자체 구현 분산 락 — 99% 버그
Eventual Consistency를 Strong처럼 사용 — 데이터 분기

14. 분산 합의 현명하게 쓰기 체크리스트

마치며 — 합의의 역설

분산 시스템의 모든 흥미로운 문제는 결국 합의로 환원된다. Kubernetes가 Pod 상태에 동의하는 것도, Kafka가 파티션 리더를 뽑는 것도, 블록체인이 트랜잭션 순서를 정하는 것도, 협업 문서가 편집을 머지하는 것도.

FLP 정리가 말하듯, "완벽한 합의"는 수학적으로 불가능하다. 우리가 쓰는 모든 알고리즘은 안전성과 진행성 사이의 실용적 타협이다. Paxos는 우아하지만 어렵고, Raft는 이해 가능하지만 디테일이 많으며, BFT는 강력하지만 비싸고, CRDT는 합의를 회피하는 대안이다.

"The only way to make distributed systems simple is to understand that they're fundamentally hard, and stop pretending otherwise." — Kyle Kingsbury (Jepsen)

다음 글 예고 — 현대 CI/CD 파이프라인 완전 분해

합의가 분산 시스템의 심장이라면, CI/CD는 현대 개발의 혈관이다. 다음 글에서는:

CI/CD의 역사 — Hudson → Jenkins, Travis, CircleCI, GitHub Actions
Pipeline as Code — .github/workflows 철학
Build Caching — Turborepo, Nx, Bazel 원격 캐시
Container 기반 빌드 — BuildKit, Nixpacks, Bun
Test Parallelization — Sharding, Flaky Test 방어
Artifact Management — OCI Registry, GHCR, Artifactory
Secrets Management — Vault, AWS Secrets Manager, OIDC
Deployment 전략 — Blue/Green, Canary (앞 글 연결)
GitOps — Argo CD, Flux, Pull 기반 배포
Supply Chain Security — SLSA, Sigstore, SBOM, provenance
Dev Loop Speed — 커밋부터 배포까지 5분 철학

개발 생산성의 마지막 퍼즐을 맞추는 여정.

"The impossibility of consensus is not a bug in distributed systems — it's the fundamental feature that makes them interesting." — Leslie Lamport (Turing Award lecture, 2013)