01 · Raft의 리더 중심 합의 — 선출·복제·안전성과 리더 의존의 대가
Raft 논문 확장판(Ongaro·Ousterhout, 2014)과 Ongaro의 박사논문, 2026-11-22에 확인한 etcd v3.7·Consul v2.1 문서를 바탕으로 썼습니다. 직접 실험한 결과는 없습니다. Raft의 동작과 리더 의존의 대가를 다루는 1편이며, 2편은 QuePaxa입니다.
같은 상태를 만드는 복제 로그
etcd나 Consul은 여러 서버가 같은 상태를 유지하도록 합니다. 그 바탕은 복제 로그입니다. 로그에 같은 명령이 같은 순서로 담기고, 같은 입력에 같은 결과를 내는 결정적 상태 머신이 이를 실행하면 서버들은 같은 상태에 도달합니다. 합의 알고리즘은 어떤 명령을 어떤 순서로 확정할지 서버들이 합의하도록 합니다.
Raft가 복제하는 상태의 범위는 시스템마다 다릅니다.
| 시스템 | Raft를 쓰는 자리 |
|---|---|
| etcd | 키-값 저장소 전체. Kubernetes의 상태 저장소 |
| Consul | 서버 에이전트 사이의 합의 |
| CockroachDB, TiKV | 데이터 범위(range, Region)마다 Raft 그룹 하나 |
| Kafka KRaft | 메타데이터 쿼럼. Kafka 4.0부터 ZooKeeper 없이 동작 |
| ClickHouse Keeper | NuRaft 구현. 이 사이트의 Keeper 글 참고 |
강한 리더의 역할과 term·RPC
Paxos의 제안자는 번호를 붙인 prepare로 과반의 약속을 받고 accept를 보냅니다. Lamport는 「Paxos Made Simple」에서 두 제안자가 번갈아 더 큰 번호를 내면 서로의 accept를 계속 막을 수 있다고 설명합니다. 그래서 제안을 시도할 제안자 하나를 정해야 한다고 썼습니다.
Raft의 저자들은 이해하기 쉬운 알고리즘을 가장 중요한 목표로 삼아 선출·복제·안전성을 나눴습니다. 리더 선출은 합의 절차에 포함되고, 로그 엔트리는 리더에서 다른 서버로만 흐릅니다. 논문이 내세운 강한 리더의 역할입니다.
서버는 리더, 팔로워, 후보 중 한 상태입니다. 정상 상태에서는 리더 하나가 클라이언트 요청을 처리합니다. 나머지 팔로워는 스스로 요청을 보내지 않고 리더와 후보의 요청에 응답합니다.
term은 선거로 시작하는 번호 붙은 구간입니다. 당선자가 없으면 리더 없이 다음 term으로 넘어갈 수도 있습니다. 서버는 통신할 때 term을 교환하고, 더 큰 term을 만나면 자기 term을 갱신합니다. 리더나 후보였다면 즉시 팔로워로 돌아가며, 낡은 term의 요청은 거절합니다. 이렇게 term은 낡은 리더를 가려내는 논리 시계로 쓰입니다.
후보와 리더가 쓰는 기본 RPC(원격 프로시저 호출)는 다음과 같습니다.
| RPC | 보내는 쪽 | 주요 인자 | 받는 쪽이 거절하는 경우 |
|---|---|---|---|
| RequestVote | 후보 | term, candidateId, lastLogIndex, lastLogTerm | 후보의 term이 낮을 때, 이번 term에 이미 다른 후보에게 투표했을 때, 후보의 로그가 자기 로그보다 덜 최신일 때 |
| AppendEntries | 리더 | term, leaderId, prevLogIndex, prevLogTerm, entries[], leaderCommit | 리더의 term이 낮을 때, prevLogIndex 위치에 엔트리가 없거나 그 엔트리의 term이 prevLogTerm과 다를 때 |
엔트리 없이 보내는 AppendEntries는 리더의 생존 신호인 heartbeat가 됩니다. 서버는 currentTerm, votedFor, 로그의 변경을 RPC에 응답하기 전에 디스크에 기록해야 합니다.
과반의 표와 무작위 선거 타임아웃
팔로워는 선거 타임아웃 동안 리더의 AppendEntries를 받지 못하고 다른 후보에게 표도 주지 않았다면 선거를 시작합니다. 다음은 후보가 term을 올리고 자신에게 투표한 뒤 RequestVote로 과반의 표를 모으는 과정입니다.
도식 텍스트
- S1 (이전 리더)
- S2 (후보)
- S3 (팔로워)
- 1. heartbeat(term 1)
- 1. heartbeat(term 1)
- 장애
- heartbeat 없이 선거 타임아웃 경과 · S2의 무작위 타임아웃이 먼저 만료
- 2. RequestVote(term 2)
- 3. 투표
- 3대 중 2표 · 리더 당선
- 4. heartbeat(term 2)
각 서버는 같은 term에서 투표 조건을 만족한 첫 요청에 한 표만 줍니다. 후보가 여럿이면 표가 나뉘어 아무도 과반을 얻지 못할 수 있습니다.
Raft는 선거 타임아웃을 고정 구간에서 서버마다 무작위로 뽑아 이런 상황을 줄입니다. 논문의 예시는 150~300ms입니다. 대개 한 서버가 먼저 타임아웃되어 다른 서버의 타임아웃이 끝나기 전에 당선됩니다. 같은 시점에 선거를 다시 시작하는 일이 반복되지 않도록 하는 장치입니다.
로그의 복제와 불일치 복구
로그 엔트리에는 상태 머신이 실행할 명령, 리더가 그 명령을 받은 term, 위치를 나타내는 index가 들어갑니다. 다음은 리더가 AppendEntries를 병렬로 보내 엔트리를 확정하는 커밋 과정입니다.
도식 텍스트
- 클라이언트
- 리더
- 팔로워 A
- 팔로워 B
- 1. 명령
- 2. AppendEntries
- 2. AppendEntries
- 3. 성공
- 리더와 A, 과반에 복제 · 커밋하고 적용
- 4. 결과
- 5. 성공(늦게 도착)
- 6. leaderCommit 전달
- 6. leaderCommit 전달
리더가 바뀌면 팔로워에는 엔트리가 빠져 있거나 이전 리더의 미커밋 엔트리가 남아 있을 수 있습니다. 리더는 팔로워마다 다음에 보낼 위치를 기억합니다. 팔로워가 prevLogIndex·prevLogTerm 검사에서 거절하면 그 위치를 하나씩 낮춰 공통 지점을 찾습니다. 일치 지점 뒤에 충돌하는 엔트리가 있으면, 팔로워는 그 엔트리와 이후 엔트리를 지우고 리더의 로그를 받아 일치시킵니다.
투표와 커밋이 지키는 안전성
커밋에 참여한 과반과 새 리더에게 투표한 과반은 적어도 한 서버를 공유합니다. 투표자가 후보 로그를 검사하는 이유입니다. 최신 여부는 마지막 엔트리의 term부터 비교합니다. term이 큰 쪽이 더 최신이고, term이 같을 때는 더 긴 로그가 최신입니다.
커밋에도 제한이 붙습니다. 리더는 자기 term에 만든 엔트리만 과반에 복제된 수를 근거로 커밋합니다. 이전 term의 미커밋 엔트리는 과반에 있어도 그 수만으로 커밋하지 않습니다. 현재 term 엔트리가 커밋될 때 그 앞의 엔트리도 함께 커밋됩니다.
논문 Figure 8은 이 제한이 필요한 이유를 보여줍니다. 이전 term 엔트리는 과반에 복제됐어도, 이후 다른 서버가 당선되어 덮어쓸 수 있는 순서가 존재합니다. 새 리더가 term 시작에 명령이 없는 no-op 엔트리를 커밋하는 것도 현재 term의 커밋 조건을 충족하기 위해서입니다.
Raft는 서버가 프로토콜을 벗어난 임의의 동작을 하지 않는 비비잔틴 장애를 가정합니다. 논문은 다음 안전성(safety) 속성이 항상 성립한다고 적습니다.
| 속성 | 뜻 |
|---|---|
| Election Safety | 한 term에 리더는 최대 하나 |
| Leader Append-Only | 리더는 자기 로그에 덧붙이기만 함 |
| Log Matching | 두 로그에 index와 term이 같은 엔트리가 있으면 그 index까지의 모든 엔트리가 같음 |
| Leader Completeness | 커밋된 엔트리는 이후 모든 term의 리더 로그에 있음 |
| State Machine Safety | 한 서버가 어떤 index의 엔트리를 적용했다면 다른 서버는 그 index에 다른 엔트리를 적용하지 않음 |
멤버십 변경·스냅샷·읽기
멤버십 변경에는 논문의 joint consensus와 박사논문이 권한 한 번에 한 대씩 바꾸는 방식이 있습니다.
로그가 끝없이 자라지 않도록 스냅샷을 만들고, 뒤처진 팔로워에게는 InstallSnapshot으로 보냅니다.
읽기에는 ReadIndex와 lease가 있습니다. ReadIndex는 현재 term 엔트리의 커밋과 과반의 heartbeat 확인, 읽을 위치까지의 적용을 기다리며, lease는 시계 오차 상한을 가정해 매번 과반에 확인하는 절차를 생략합니다.
리더 의존의 대가
논문은 안전성이 타이밍에 의존해서는 안 되지만 가용성은 타이밍에 의존할 수밖에 없다고 적습니다. 합의가 계속 진행되는 성질인 liveness는 리더를 유지하고 교체하는 시간 조건에 기댑니다.
선거가 끝날 때까지의 중단
Raft 논문은 진행에 필요한 조건을 broadcastTime ≪ electionTimeout ≪ MTBF로 나타냅니다. broadcastTime은 모든 서버에 RPC를 병렬로 보내 응답을 받는 평균 시간이며, MTBF는 서버 한 대의 평균 장애 간격입니다. 논문은 선거 타임아웃이 broadcastTime보다 대략 10배 길어야 한다고 설명합니다. 리더가 죽으면 시스템을 대략 선거 타임아웃 동안 쓸 수 없다는 것도 논문의 설명입니다.
아래 표에서 논문 §9.3의 실험은 로그 길이와 heartbeat 시점을 조절해 선출에 불리한 조건을 만들고 측정한 것입니다.
| 출처 | 조건 | 수치 |
|---|---|---|
| Raft 논문 §9.3 (2014) | 5대, broadcast time 약 15ms, 타임아웃 150~150ms(무작위 없음) | 선출에 계속 10초 넘게 걸림 |
| 같은 실험 | 타임아웃 150~155ms | 중단 시간 중앙값 287ms |
| 같은 실험 | 타임아웃 12~24ms | 평균 35ms, 최장 152ms. 더 낮추면 불필요한 리더 교체 발생 |
| etcd v3.7 문서 | 기본값 | heartbeat 100ms, 선거 타임아웃 1000ms |
| etcd v3.7 문서 | 권장 | 선거 타임아웃은 멤버 간 왕복 시간의 10배 이상, 상한 50초(전 지구 배치용) |
| Consul v2.1 문서 | 기본값(raft_multiplier 5) | heartbeat 타임아웃·선거 타임아웃 5000ms. 운영 환경에는 1 권장 |
선거 타임아웃의 딜레마
타임아웃을 줄이면 장애를 빨리 감지하지만, 네트워크가 잠깐 느려진 것만으로 선거가 시작되기 쉬워집니다. Consul 문서는 지연이 큰 환경에서 짧은 값이 잦은 리더 교체를 부를 수 있다고 적습니다. 오판을 피하려고 타임아웃을 늘리면 실제 리더 장애 뒤의 중단도 길어집니다. 대륙 사이 왕복 시간이 수백 ms인 배치에서는 이 값이 초 단위가 됩니다.
오판을 줄이는 PreVote와 CheckQuorum
클러스터에서 빠진 서버나 네트워크 분할로 고립된 서버는 heartbeat를 받지 못한 동안 term을 계속 올릴 수 있습니다. 이 큰 term이 다른 서버에 전해지면 정상인 리더도 물러납니다. 리더를 유지하거나 교체하는 판단을 보완하는 장치가 PreVote와 CheckQuorum입니다.
- PreVote: 후보가 term을 올리기 전에 과반에게 투표 의향을 확인한다. 투표자는 후보의 로그가 충분히 최신이고, 최소 선거 타임아웃 동안 유효한 리더의 heartbeat를 받지 않았을 때 동의한다. Ongaro 박사논문 §9.6이 제안했고, etcd는 v3.5부터 기본으로 켠다.
- CheckQuorum: 리더가 선거 타임아웃 동안 과반과 heartbeat를 주고받지 못하면 스스로 물러난다. etcd v3.7.4는 이 값을 켠 채로 고정한다.
과반이 남아 있는 부분 네트워크 장애
Howard와 Abraham은 2020년 글에서, 기본 Raft는 과반이 서로 통신할 수 있어도 안정된 리더를 세우지 못할 수 있음을 보였습니다. 서버 다섯 대 가운데 S1·S2·S3은 서로 연결되고, S4는 S2와만, S5는 S3과만 연결된 경우입니다. 다음은 리더 S3과 끊긴 S4가 선거를 시작했을 때의 흐름입니다.
도식 텍스트
- S4 (S2와만 연결)
- S2
- S3 (리더)
- 1. heartbeat(term 1)
- 리더의 heartbeat를 못 받음 · 선거 타임아웃
- 2. RequestVote(term 2)
- 더 큰 term을 보고 · 자기 term을 2로 올림
- 3. 응답에 term 2
- 자기 term이 낡았다고 보고 · 리더에서 물러남
S1·S2·S3 가운데 누가 다시 리더가 되어도 S4나 S5 중 하나는 리더와 끊겨 있어 같은 일이 반복됩니다.
PreVote만 추가해도 진행이 막히는 경우가 남습니다. 과반과 끊긴 리더가 일부 서버에 계속 heartbeat를 보내면, 그 서버가 새 후보의 PreVote를 거절할 수 있기 때문입니다. 두 사람은 PreVote와 CheckQuorum을 함께 쓰면 자신들이 다룬 링크 단절 모델에서 liveness가 보장된다고 결론 냅니다. 여기서는 이를 타이밍 가정이 성립하는 구간에서 안정된 리더가 생긴다는 뜻으로 해석합니다.
두 사람이 글을 쓴 계기는 Cloudflare의 2020-11-02 장애입니다. Cloudflare의 사후 보고에 따르면 스위치 하나가 일부 패킷만 전달하는 상태로 6분간 고장 났습니다. etcd 노드 하나는 리더와 끊기고 다른 노드와는 연결된 상태였습니다. Cloudflare는 그 노드가 선거를 반복해서 시작했고, 스위치가 회복될 때까지 etcd 클러스터가 읽기 전용이었다고 보고했습니다.
etcd 중단은 데이터베이스 승격과 복제본 재구축으로 이어졌고, API와 대시보드의 가용성 저하는 6시간 33분 지속됐습니다. 대시보드는 최대 80배 느렸습니다. 당시 etcd 버전과 PreVote·CheckQuorum 설정은 보고에 나오지 않습니다. 보고서는 후기에서 이 네트워크 장애를 Byzantine fault보다 메시지 전달이 누락되는 omission fault로 보는 편이 적절하다고 정정했습니다.
리더 장애와 오판이 모두 쓰기를 멈출 수 있다는 점이 2편 QuePaxa의 출발점입니다.
참고 자료
- Ongaro·Ousterhout, In Search of an Understandable Consensus Algorithm (Extended Version) (2014)
- Ongaro, Consensus: Bridging Theory and Practice (박사논문, 2014)
- Lamport, Paxos Made Simple (2001)
- etcd v3.7 Tuning, Consul 서버 성능 문서
- Howard·Abraham, Raft does not Guarantee Liveness in the face of Network Faults (2020-12-12)
- Cloudflare, A Byzantine failure in the real world (2020-11-27)