복제와 합의: Raft, Paxos, 리더 선출

합의가 없으면 분산 시스템은 작동하지 않는다

Kubernetes가 클러스터 상태를 저장하는 etcd, CockroachDB의 데이터 샤드, Kafka 3.0 이후의 KRaft 메타데이터 관리—이 시스템들이 장애 상황에서도 일관성을 유지할 수 있는 근거는 모두 합의 알고리즘(consensus algorithm)이다.

합의 알고리즘이 푸는 문제는 단순하게 들린다. 여러 노드가 있을 때, "다음 값은 X다"라는 사실에 모두 동의하게 만드는 것이다. 하지만 노드가 언제든 죽을 수 있고, 네트워크가 분단될 수 있고, 메시지가 지연·유실·중복될 수 있는 환경에서 이것은 매우 어려운 문제다.

이 문제를 풀지 못하면 두 노드가 동시에 리더라고 생각하는 split-brain이 발생하고, 데이터가 조용히 덮어쓰이거나 사라진다.

합의 문제의 핵심: 세 가지 속성

올바른 합의 알고리즘은 세 가지 속성을 보장해야 한다.

분산 환경에서 이 세 가지를 동시에 보장하려면 쿼럼(quorum), 즉 과반수 이상의 동의가 핵심 도구가 된다.

Paxos: 최초의 실용 합의 알고리즘

Paxos는 Leslie Lamport가 1989년(발표는 1998년) 설계한 합의 알고리즘이다. 분산 합의를 공식화한 최초의 실용적 알고리즘으로, 이후 나오는 모든 합의 알고리즘의 기준이 됐다.

Basic Paxos: 단일 값 합의

Basic Paxos는 하나의 값에 합의하는 과정을 두 단계로 나눈다.

Phase 1: Prepare

제안자(Proposer)가 고유 번호 n을 가진 Prepare 메시지를 수락자(Acceptor) 과반수에게 보낸다. Acceptor는 다음 조건이면 Promise를 응답한다.

• 이전에 n보다 큰 Prepare를 받지 않았다
• 이미 수락한 값이 있으면 함께 알려준다

Phase 2: Accept

제안자가 과반수의 Promise를 받으면 Accept 메시지를 보낸다. 값은 "응답 중 가장 높은 번호의 제안자가 수락한 값"이거나, 아무도 수락한 게 없으면 제안자 자신의 값이다. Acceptor가 받아들이면 학습자(Learner)에게 알린다.

Multi-Paxos: 연속 합의로 확장

실제 시스템은 하나의 값이 아니라 명령 로그 전체에 합의해야 한다. Multi-Paxos는 안정적인 리더를 선출하고, 리더가 Phase 1을 한 번 수행한 뒤 이후 Phase 2만 반복하는 최적화다.

Paxos의 현실적 문제

Paxos는 정확하지만 구현이 어렵다. Lamport 자신도 "Paxos Made Simple"을 별도로 써야 할 정도였다. 리더 선출, 로그 복제, 멤버십 변경을 하나의 일관된 알고리즘으로 결합하는 과정에서 많은 세부 구현 결정이 논문 외부에 남겨진다. Google의 Chubby 락 서비스가 Paxos 기반이지만 세부 구현 사항의 상당 부분이 공개되지 않은 이유도 여기에 있다.

Raft: 이해 가능성을 목표로 설계된 합의

Diego Ongaro와 John Ousterhout가 2014년 발표한 Raft는 "이해하기 쉬운 합의 알고리즘"을 명시적 설계 목표로 내세웠다. Paxos와 동등한 정확성을 보장하면서 리더 선출, 로그 복제, 안전성을 명확히 분리했다.

Term: Raft의 논리적 시계

Raft는 Term(임기)이라는 단조 증가하는 정수로 시간을 나눈다. 각 Term은 선거로 시작한다. 어느 노드든 더 높은 Term을 가진 메시지를 받으면 즉시 Follower로 복귀한다. Term은 Split-brain을 방지하는 핵심 도구다. 이전 Term의 리더는 새 Term에서 자신이 리더라고 주장할 수 없다.

리더 선출: 어떻게 하나의 리더만 당선되는가

선거 시작 조건

모든 Follower는 리더로부터 정기적으로 heartbeat(빈 AppendEntries RPC)를 받는다. 일정 시간(election timeout, 보통 150~300ms) 안에 heartbeat를 받지 못하면 리더가 죽었다고 판단하고 스스로 Candidate로 전환한다.

투표 과정

1. Candidate는 Term을 1 증가시키고 자신에게 투표한다.
2. 다른 모든 노드에게 RequestVote RPC를 보낸다.
3. 다음 조건을 모두 만족하면 각 노드는 투표한다.

- 요청자의 Term이 현재 Term 이상이다. - 이번 Term에 아직 투표하지 않았다. - 요청자의 로그가 자신의 로그만큼 최신이다 (log completeness 조건).

1. 과반수의 투표를 받으면 리더가 된다.

선거 충돌 방지

두 Candidate가 동시에 선거를 시작하면 과반수를 못 받을 수 있다. Raft는 election timeout을 무작위(randomized)로 설정해 이 문제를 해결한다. 먼저 타임아웃된 노드가 빠르게 과반수를 확보해 리더가 되는 경우가 대부분이다.

로그 복제: 합의된 명령이 어떻게 적용되는가

커밋의 의미

"커밋되었다"는 것은 과반수 노드가 해당 로그 항목을 디스크에 안전하게 저장했다는 뜻이다. 리더가 죽어도 과반수 중 한 노드는 살아있으므로, 다음 리더는 반드시 커밋된 항목을 가지고 있다. 이 속성을 Leader Completeness Property라 한다.

로그 불일치 해소

Follower의 로그가 리더와 다를 때(리더 교체 후 흔히 발생), 리더는 일치하는 지점까지 Follower의 로그를 덮어씌운다. 커밋되지 않은 항목만 덮어쓸 수 있으므로 데이터 손실은 없다.

Split-brain 방지: 쿼럼의 수학

Raft가 split-brain을 방지하는 원리는 쿼럼(quorum)의 수학에 있다. 5노드 클러스터에서 과반수는 3이다.

• 노드 A, B, C가 한 파티션, D, E가 다른 파티션으로 분리됐다고 하자.
• A, B, C는 과반수(3/5)이므로 리더를 선출할 수 있다.
• D, E는 과반수(2/5 < 3)이 안 되므로 리더를 선출할 수 없다.
• 두 파티션이 동시에 리더를 선출하려면 각각 3표가 필요한데, 5표를 두 그룹이 나눠 가질 경우 한쪽만 3을 넘을 수 있다.

이 원리 덕분에 네트워크 파티션이 발생해도 최대 하나의 리더만 존재할 수 있다.

주의: 네트워크 파티션이 완치된 후 이전 리더가 다시 등장해 구 Term으로 명령을 보낼 수 있다. Raft는 Term 비교로 이 오래된 메시지를 무시한다.

실세계 구현: Raft 기반 시스템

etcd 운영 시 Raft 관련 고려사항

etcd는 모든 쓰기가 Raft를 통하므로 디스크 I/O가 리더 선출 안정성에 직접 영향을 준다. 리더가 fsync에 시간이 걸려 heartbeat를 제때 못 보내면 불필요한 선거가 발생한다. 공식 문서는 SSD를 강력히 권장하며, HDD 환경에서는 heartbeat-interval과 election-timeout을 충분히 크게 설정해야 한다.

# etcd 권장 설정 (고레이턴시 환경)
heartbeat-interval: 250ms   # 기본 100ms → 늘림
election-timeout: 2500ms    # heartbeat의 10배 유지

Raft vs Paxos: 실무 관점 비교

ZooKeeper가 사용하는 ZAB(ZooKeeper Atomic Broadcast)는 Paxos와 유사하지만 독립적으로 설계된 프로토콜이다. 용어도 다르고(epoch, transaction id) 리더 선출 방식도 다르다.

합의의 한계: FLP 불가능성

실용적 논의에서 빠지지 않는 이론적 사실이 있다. FLP 불가능성(Fischer-Lynch-Paterson, 1985)은 단 하나의 노드도 실패할 수 있는 완전 비동기 시스템에서는 합의가 항상 가능하도록 보장하는 알고리즘이 존재하지 않는다고 증명했다.

Raft와 Paxos는 이 한계를 "충분한 수의 노드가 살아있다면"이라는 가정 하에 우회한다. 5노드 클러스터는 2노드 장애를 견딘다(3 > 2.5). 과반수가 죽으면 리더 선출이 완료되지 않으며, 이것이 Raft의 안전성 보장 방식이다.

운영자가 알아야 할 합의 관련 장애 패턴

리더 교체 폭풍(election storm): 네트워크 레이턴시 급증이나 디스크 I/O 부하가 heartbeat 타임아웃을 유발해 연속적으로 선거가 발생하는 현상. 이 기간 동안 쓰기가 거부된다. 모니터링 지표: etcd_server_leader_changes_seen_total, Raft 선거 이벤트 로그.

비대칭 파티션: 리더에서 Follower로는 패킷이 전달되지만 반대 방향은 안 되는 경우. 리더가 자신이 리더라고 믿고 로컬에 쓰지만, Follower는 heartbeat를 받지 못해 선거를 시작한다. 결국 두 리더가 잠깐 공존하는 것처럼 보이지만, 쿼럼 확보 여부에 따라 구 리더는 곧 강등된다.

디스크 I/O와 리더 안정성: etcd와 CockroachDB 모두 Raft 로그를 디스크에 fsync해야 커밋으로 인정한다. 느린 디스크는 쓰기 레이턴시를 높이고, 극단적 경우 heartbeat timeout을 유발한다. 프로덕션 환경에서는 Raft 노드에 전용 NVMe SSD를 권장한다.

기억할 문장

합의 알고리즘은 "노드가 고장나도 전체 시스템은 하나의 결정을 내린다"는 약속이다. Raft는 이 약속을 Term, 리더 선출, 로그 복제, 그리고 쿼럼이라는 네 가지 개념으로 구현한다. etcd 클러스터가 불안정하거나 리더가 자주 바뀐다면, 그 원인은 대부분 네트워크 레이턴시, 디스크 I/O 부하, 또는 쿼럼 밑으로 떨어진 노드 수다.

다음 장에서는 여러 서비스에 걸친 트랜잭션—2PC, Saga, TCC—을 살펴본다.

References

• Ongaro, D. & Ousterhout, J. (2014). In Search of an Understandable Consensus Algorithm — https://raft.github.io/raft.pdf
• Lamport, L. (1998). The Part-Time Parliament (Paxos) — https://www.microsoft.com/en-us/research/uploads/prod/2016/12/The-Part-Time-Parliament.pdf
• Lamport, L. (2001). Paxos Made Simple — https://www.microsoft.com/en-us/research/publication/paxos-made-simple/
• The Raft Consensus Algorithm (interactive visualization) — https://raft.github.io/
• Fischer, M., Lynch, N., Paterson, M. (1985). Impossibility of Distributed Consensus with One Faulty Process — https://dl.acm.org/doi/10.1145/3149.214121
• etcd, Tuning documentation — https://etcd.io/docs/v3.5/tuning/
• Cloudflare Blog, "A new era for etcd" (KRaft context) — https://blog.cloudflare.com/a-new-era-for-etcd/
• TiKV Documentation, "Raft in TiKV" — https://tikv.org/deep-dive/consensus-algorithm/raft/
• CockroachDB, "How CockroachDB Does Distributed Atomic Transactions" — https://www.cockroachlabs.com/blog/how-cockroachdb-distributes-atomic-transactions/