LabHub

블로그

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

2026-04-15 · 21 분 읽기 · #distributed-systems#consensus#paxos#raft#etcd#zookeeper#culture

한국어English

"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. 문제 정의 — "동의"가 왜 어려운가

합의가 보장해야 하는 것

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

분산 환경의 적대적 현실

FLP 불가능성 정리 (1985)

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

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

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

그럼 어떻게?

Paxos, Raft 모두 이 방향이다.

2. Paxos — Lamport의 기념비

등장

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

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

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

기본 Paxos 역할

2-Phase 프로토콜

Phase 1 (Prepare)

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

Phase 2 (Accept)

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

왜 이게 어려운가

실제 사용 사례

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

동기

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

핵심 분해

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

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

상태

각 노드는 세 상태 중 하나:

Leader Election

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

Log Replication

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

Safety — Log Matching Property

Raft의 실제 구현

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

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

4. ZooKeeper와 ZAB

ZooKeeper의 역사

ZAB (ZooKeeper Atomic Broadcast)

Paxos와 유사하지만:

Znode 모델

ZooKeeper의 유즈케이스

한계

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

동기

KRaft 등장

내부

이점

마이그레이션

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

6. etcd — Kubernetes의 심장

왜 Kubernetes가 etcd인가

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

Raft 구현

성능 특성

운영 팁

etcd vs ZooKeeper vs Consul

측면etcdZooKeeperConsul
언어GoJavaGo
합의RaftZABRaft
데이터 모델flat KV계층 treeKV + 서비스 디스커버리
Watch스트림일회성스트림
헬스체크외부Ephemeral내장
주 사용처KubernetesKafka(구), HadoopService 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)

HotStuff (2018)

블록체인과 BFT

기업에서 BFT가 필요한가?

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

동기

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

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

CRDT (Conflict-free Replicated Data Type)

2가지 종류

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

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

유명한 CRDT 구현

2024년 이후 — Local-First

9. 약한 일관성 모델들

일관성 스펙트럼

강 ← Linearizable → Sequential → Causal → Eventual → 약

Linearizable (Strong Consistency)

Causal Consistency

Eventual Consistency

CAP 정리의 오해

10. 분산 락 — 합의의 응용

ZooKeeper 방식

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

etcd 방식

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

Redlock (Redis) — 논란

앞선 Redis 글에서 다룬 대로:

Fencing Token

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

Split Vote

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

Leader Flapping

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

Network Partition (Brain Split)

Clock Drift

12. 2025년 합의 지형

주류

부상

프론티어

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

  1. "직접 Paxos 구현" 시도 — 실패 확정
  2. Raft 라이브러리 포크 후 패치 남발 — 업스트림 놓침
  3. 홀수 노드 아닌 4대 cluster — Quorum(3)이 두 번 분할 허용
  4. WAN에 걸친 합의 — 지연 폭발, regional split
  5. ZooKeeper 세션 타임아웃 기본값 방치 — GC 길면 잦은 연쇄
  6. etcd 8GB 제한 무시 — 어느 날 갑자기 장애
  7. 비잔틴이 필요한 환경에 Raft — 악의 노드가 모든 걸 망침
  8. 합의 시스템에 대량 쓰기 — KV만, 1MB 넘는 값 금지
  9. 자체 구현 분산 락 — 99% 버그
  10. 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는 현대 개발의 혈관이다. 다음 글에서는:

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

"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)

원문 보기: https://www.youngju.dev/blog/culture/2026-04-15-distributed-consensus-paxos-raft-zab-flp-etcd-zookeeper-kraft-bft-crdt-deep-dive-guide-2025

댓글

아직 댓글이 없습니다.

로그인하면 댓글을 쓸 수 있습니다