1. 도입
분산 시스템을 공부하다 보면 "리더가 죽으면 가장 최신 노드가 새 리더가 된다"는 문장을 자주 만난다. 나도 그렇게 막연히 외우고 있었다. 그런데 막상 "그 최신을 무엇으로 판단하느냐"고 물으면 대답이 흐릿했다. 로그가 가장 긴 노드? 가장 마지막에 쓴 노드?
직접 Raft 논문(Ongaro & Ousterhout, 2014) §5를 따라가 보니, 답은 둘 다 아니었다. Raft는 "최신"을 로그 길이가 아니라 (lastLogTerm, lastLogIndex) 사전식 비교로 정의한다. 짧아도 더 최근 term의 로그를 가진 노드가 이기고, 길어도 낡은 term의 로그는 진다. 이 한 가지 규칙이 사실 Raft 안전성의 핵심이다.
이 글은 Raft의 리더 선출과 로그 복제를 따라가면서, "왜 가장 긴 로그가 이기지 않는가", 그리고 "한번 commit된 값이 왜 절대 뒤집히지 않는가"를 정리한 것이다.
2. 핵심 개념 — 합의를 세 조각으로 쪼개기
Raft는 합의 문제를 리더 선출 / 로그 복제 / 안전성 세 부분으로 나누고, "선출된 리더만 로그를 쓴다"와 "committed entry를 가진 노드만 리더가 될 수 있다"는 두 제약으로 복제 상태 기계(replicated state machine)의 일관성을 보장한다.
먼저 두 가지 단어만 잡고 가자.
- term: 논리 시계 역할을 하는 단조 증가 정수다. 시간이 임의 길이의 term으로 쪼개지고, 각 term은 리더를 최대 한 명만 가진다(선거에 실패하면 0명). term은 모든 RPC에 실려 다닌다.
- 세 가지 상태: 모든 노드는 항상 Follower / Candidate / Leader 중 하나다.
term의 위력은 단순한 규칙 하나에서 나온다. 노드는 자기 term보다 큰 term을 보는 순간 즉시 currentTerm을 갱신하고 Follower로 강등한다. 네트워크가 끊겼다 돌아온 "낡은 리더"가 이 규칙 하나로 자동 무력화된다 — 더 높은 term의 메시지를 보자마자 스스로 물러나기 때문이다.
timeout → 선거 시작 과반 득표
┌──────────────────┐ ┌──────────────────┐
│ ▼ │ ▼
Follower ───────► Candidate ───┘ Leader
▲ │
└──────────── 더 높은 term 발견 시 언제나 Follower로 강등 ┘3. 리더 선출 — 왜 타임아웃을 랜덤하게 하나
Follower는 election timeout(보통 150~300ms, 노드마다 랜덤) 동안 리더의 heartbeat를 못 받으면 선거를 시작한다.
currentTerm += 1, 자신을 Candidate로, 자기 자신에게 투표.- 모든 노드에
RequestVote(term, candidateId, lastLogIndex, lastLogTerm)발송. - 과반(majority) 표를 모으면 Leader 등극 → 즉시 heartbeat로 권위 선언.
타임아웃을 랜덤화하는 이유가 흥미롭다. 모든 노드가 동시에 후보가 되면 표가 갈려(split vote) 아무도 과반을 못 얻고 term만 헛돌게 된다. 타임아웃이 노드마다 다르면 보통 한 노드가 먼저 깨어나 당선되므로 빠르게 수렴한다. 결정론적 알고리즘이 아니라 무작위성으로 라이브니스(liveness)를 확보하는, 의외로 실용적인 설계다.
여기서 1절의 질문이 풀린다. 투표 규칙(§5.4.1)은 이렇다.
후보 로그가 더 최신이다 ⇔
(lastLogTerm 이 더 크다)
OR (lastLogTerm 같고 lastLogIndex 가 더 크거나 같다)term을 인덱스보다 먼저 비교한다. 그래서 로그가 길어도(인덱스가 커도) 마지막 entry의 term이 낮으면 진다. 노드는 한 term에 한 표만 주고(votedFor를 디스크에 영구 저장), 후보의 로그가 자기 것보다 최신이 아니면 거부한다. "가장 긴 로그가 리더가 된다"가 틀린 이유가 바로 이 비교 순서에 있다.
4. 로그 복제와 Log Matching
리더만 클라이언트 쓰기를 받는다. 각 명령은 {term, index, command} entry로 리더 로그에 append된 뒤 AppendEntries RPC로 팔로워에 복제된다.
index: 1 2 3 4 5
┌────┬────┬────┬────┬────┐
Leader │t1 │t1 │t2 │t3 │t3 │
└────┴────┴────┴────┴────┘
▲ committed (과반 복제 완료)어떤 entry가 과반 노드에 복제되면 리더는 그것을 committed로 표시하고 상태 기계에 apply한다. 핵심은 Log Matching Property다. AppendEntries는 새 entry 바로 앞 위치의 (prevLogIndex, prevLogTerm)을 함께 싣고, 팔로워는 그 위치의 term이 일치할 때만 받아들인다. 불일치하면 거부하고, 리더는 해당 팔로워의 nextIndex를 한 칸 내려 재시도한다. 이 귀납이 만드는 불변식:
두 로그가 같은 index·term의 entry를 가지면, 그 이전의 모든 entry도 동일하다.
즉 한 지점만 맞으면 그 앞은 전부 같다는 뜻이다. 충돌 구간은 리더 로그로 덮어쓴다(팔로워의 충돌 entry는 잘림). 리더는 절대 자기 로그를 덮어쓰지 않는다 — append-only. 이 단방향 흐름이 leader-driven 복제의 뼈대다.
5. 안전성 — committed 값이 뒤집히지 않는 이유
리더 선출의 투표 규칙(3절)이 사실은 "현재 committed된 모든 entry를 가진 노드만 당선 가능"을 강제한다. 논리를 따라가 보면:
- committed entry는 과반에 있다.
- 당선에도 과반의 표가 필요하다.
- 두 과반은 반드시 한 노드 이상에서 겹친다(quorum intersection).
- 그 겹친 노드가 "내 로그가 더 최신"이라며 투표를 거부하므로, committed entry가 없는 후보는 과반을 못 얻는다.
선출 규칙과 데이터 정합성이 별개가 아니라 한 몸이라는 게 여기서 드러난다.
과거 term entry의 함정 (§5.4.2)
내가 가장 잘못 알고 있던 부분이다. 새 리더는 "과반에 복제됐다"는 이유만으로 이전 term의 entry를 commit하지 않는다. 과거 term의 entry는 과반에 있더라도 나중에 다른 리더에게 덮일 수 있기 때문이다(논문 Figure 8 시나리오). Raft는 대신 현재 term의 새 entry를 commit하면서, Log Matching에 의해 그 앞의 과거 entry까지 함께 끌려 commit되게 한다(간접 커밋). "과반 복제 = 무조건 commit"이라는 단순한 직관이 깨지는 지점이다.
6. 한 번의 쓰기를 따라가 보기
논문 Figure 2의 상태 변수로 쓰기 한 건을 추적하면 흐름이 또렷해진다.
S1(leader, term=2) log=[a@1, b@2] nextIndex={S2:3, S3:3} commitIndex=1
→ AppendEntries(prevIdx=1, prevTerm=1, entries=[b@2], leaderCommit=1) → S2, S3
S2 success, S3 success → b@2가 3/3 과반에 복제됨
→ S1: commitIndex=2 로 전진, b를 상태 기계에 apply
→ 다음 heartbeat의 leaderCommit=2 로 S2, S3도 b를 apply불일치 케이스도 확인해 보자. 만약 S3가 log=[a@1, x@1](낡은 entry x)을 가졌다면, prevLogIndex=1·prevLogTerm=1은 맞지만 index=2의 x@1이 b@2와 충돌한다 → S3는 x@1을 잘라내고 b@2를 받는다. 리더 로그 기준으로 수렴한다.
선출 안전성도 같은 예에서 확인된다. term=2에서 낡은 S3가 먼저 타임아웃해 RequestVote(lastLogTerm=1, lastLogIndex=2)를 보내도, 이미 b@2(term 2)를 가진 S1·S2는 "내 lastLogTerm=2 > 후보의 1"이므로 투표를 거부한다 → 낡은 S3는 리더가 되지 못한다. 1절의 제목이 답해지는 순간이다.
7. 정리
Raft에서 리더가 되는 자격은 "로그가 길어서"가 아니라 "마지막 entry의 term이 더 최신이고, 그래서 committed된 모든 값을 이미 갖고 있어서"다. 이 한 줄이 리더 선출과 commit 불변식을 동시에 떠받친다.
세 가지만 남기면:
- "최신"은 길이가 아니라
(lastLogTerm, lastLogIndex)사전식 비교다. - committed entry는 quorum intersection 덕에 새 리더가 반드시 물려받는다.
- 과거 term entry는 직접 commit하지 않고, 현재 term entry에 딸려 간접 commit된다.
더 파고들 만한 주제로는 ① membership change의 joint consensus vs etcd의 single-server 방식, ② 무한히 커지는 로그를 자르는 log compaction과 InstallSnapshot RPC, ③ Raft와 Multi-Paxos·ZAB(ZooKeeper)의 리더십·복구 모델 차이가 있다.
참고 자료
- Diego Ongaro & John Ousterhout, "In Search of an Understandable Consensus Algorithm (Extended Version)" (Raft 논문, 2014) §5
- https://raft.github.io — 상태 전이 시각화
- etcd/raft, HashiCorp raft 구현 노트
