Raft Consensus Algorithm

분산 시스템에서 여러 노드가 하나의 일관된 상태에 합의하는 것은 가장 어려운 문제 중 하나이다. Raft는 이 문제를 이해 가능한 방식으로 해결하기 위해 설계된 합의 알고리즘이다.

etcd(Kubernetes), Kafka KRaft, CockroachDB, TiKV 등 현대 분산 시스템의 핵심에 Raft가 있다.

Raft 란?

Raft의 접근

Raft 의 핵심 설계 원칙은 두 가지다.

문제 분해: 합의 문제를 세 개의 독립적인 서브문제로 나눈다
- Leader Election — 리더를 선출하는 방법
- Log Replication — 리더가 로그를 복제하는 방법
- Safety — 일관성을 보장하는 규칙
강한 리더(Strong Leader): 모든 쓰기는 리더를 통해서만 이루어진다. 리더에게 권한을 집중시켜 추론을 단순화한다

flowchart TB
    subgraph "Raft의 세 가지 서브문제"
        LE["Leader Election<br/>리더 선출"]
        LR["Log Replication<br/>로그 복제"]
        S["Safety<br/>안전성 보장"]
    end

    LE -->|"리더가 결정되면"| LR
    LR -->|"복제 규칙을 따르면"| S

노드 상태와 Term

세 가지 상태

Raft 클러스터의 모든 노드는 항상 다음 세 가지 상태 중 하나에 있다:

flowchart LR
    Start(( )) --> Follower
    Follower -->|"Election Timeout<br/>(heartbeat 미수신)"| Candidate
    Candidate -->|"과반수 투표 획득"| Leader
    Candidate -->|"더 높은 Term 발견"| Follower
    Candidate -->|"Split Vote<br/>(타임아웃 후 재선거)"| Candidate
    Leader -->|"더 높은 Term 발견"| Follower

상태	역할
Follower	수동적으로 리더의 요청에 응답한다. 초기 상태
Candidate	리더 선출에 참여한다. Follower가 heartbeat를 받지 못하면 전환
Leader	모든 클라이언트 요청을 처리하고 로그를 복제한다. 클러스터에 최대 1명

Term

Term은 Raft의 논리적 시간이다. 단조 증가하는 정수로, 각 Term은 선거로 시작한다.

모든 메시지에 sender의 Term이 포함된다
자신보다 높은 Term을 가진 메시지를 받으면, 즉시 Follower로 전환하고 Term을 업데이트한다
자신보다 낮은 Term을 가진 메시지는 거부한다
Term이 같은 리더가 2명 동시에 존재할 수 없다(과반수 투표가 보장하기 때문)

이 설계 덕분에 stale leader를 자동으로 감지하고 제거할 수 있다.

네트워크 파티션에서 복귀한 옛 리더는 높은 Term을 가진 메시지를 받는 순간 Follower로 돌아간다.

Leader Election

선거 과정

sequenceDiagram
    participant F1 as Follower A
    participant C as Follower B → Candidate B
    participant F2 as Follower C

    Note over C: Election Timeout 만료
    C->>C: Term++ (Term 2로 증가)
    C->>C: 자기 자신에게 투표

    par RequestVote 전송
        C->>F1: RequestVote(Term=2, lastLogIndex, lastLogTerm)
        C->>F2: RequestVote(Term=2, lastLogIndex, lastLogTerm)
    end

    F1->>C: VoteGranted=true
    F2->>C: VoteGranted=true

    Note over C: 과반수 획득 → Leader 당선
    C->>F1: AppendEntries (heartbeat)
    C->>F2: AppendEntries (heartbeat)

Follower가 Election Timeout 동안 heartbeat를 받지 못한다
Follower → Candidate로 전환, currentTerm을 1 증가시킨다
자기 자신에게 투표하고, 다른 모든 노드에 RequestVote RPC를 보낸다
투표를 받은 노드는 Term당 최대 1표만 행사할 수 있다 (first-come-first-served)
과반수(N/2 + 1) 투표를 획득하면 Leader가 된다
Leader는 즉시 빈 AppendEntries(heartbeat)를 모든 Follower에게 보내 자신의 존재를 알린다

Election Timeout과 Split Vote

Election Timeout은 랜덤화된다. 일반적으로 150~300ms 범위에서 무작위로 설정된다.

이 랜덤화가 핵심인데, 모든 노드의 타임아웃이 동일하면 동시에 선거를 시작하여 Split Vote가 반복될 수 있기 때문이다.

예를 들면 다음과 같은 상황이다.

두 Follower가 거의 동시에 타임아웃되어 둘 다 Candidate가 된다
각각 일부 노드의 투표를 받아 과반수를 달성하지 못한다
Election Timeout이 다시 만료되면 새로운 Term으로 재선거를 시작한다
랜덤화된 타임아웃 덕분에, 다음 선거에서는 한 노드가 먼저 타임아웃되어 단독 당선될 확률이 높다

투표 제한 — Election Restriction

투표를 요청받은 노드가 무조건 투표하는 것은 아니다.

RequestVote에는 Candidate의 lastLogIndex와 lastLogTerm이 포함되며, 투표자는 다음을 항목들을 확인한다.

Candidate의 로그가 자신의 로그보다 최신이어야 한다
- 마지막 로그 엔트리의 Term이 더 크거나
- Term이 같으면 로그 길이(index)가 더 크거나 같아야 한다

이 규칙이 Safety의 핵심이다.

커밋된 엔트리를 가지지 않은 노드가 리더가 되는 것을 방지한다.

Pre-Vote

네트워크 파티션에서 격리된 노드가 반복적으로 선거를 시도하면 Term이 계속 증가한다.

파티션이 해소된 후 이 노드가 복귀하면, 높은 Term 때문에 불필요한 리더 교체가 발생할 수 있다.

Pre-Vote는 이 문제를 해결한다:

실제 선거 전에 PreVote를 먼저 보낸다
과반수로부터 “투표 의향 있음” 응답을 받으면 그때 실제 Term을 증가시키고 선거를 시작한다
과반수 동의를 얻지 못하면 Term을 증가시키지 않는다

과반수 동의를 얻지 못하는 경우는 두 가지다:

네트워크 단절: 메시지 자체가 도달하지 않아 응답을 받지 못한다
거부: PreVote를 받은 노드가 현재 리더로부터 heartbeat를 정상 수신 중이면 PreVote를 거부한다

어느 경우든 과반수 동의를 얻지 못하므로 실제 선거를 시작하지 않고, Term도 증가하지 않는다.

sequenceDiagram
    participant A as Node A (Leader, Term 3)
    participant B as Node B (Follower)
    participant C as Node C (격리됨)

    Note over C: 파티션으로 heartbeat 수신 불가
    C->>C: PreVote 전송 → 과반수 동의 불가 → Term 유지 (3)
    C->>C: PreVote 전송 → 과반수 동의 불가 → Term 유지 (3)
    Note over C: Term이 증가하지 않음

    Note over A,C: 파티션 해소
    C->>A: 메시지(Term=3)
    A->>C: AppendEntries(Term=3)
    Note over C: 정상적으로 Follower로 복귀
    Note over A: 리더 유지, 클러스터 안정

파티션 해소 후 기존 리더를 방해하지 않고 조용히 복귀할 수 있다.

etcd는 Pre-Vote를 기본 활성화하고 있다.

선거와 기존 리더의 강등

선거가 시작된다고 해서 기존 리더가 즉시 리더에서 해제되는 것은 아니다.

Pre-Vote 통과 → Candidate가 Term을 증가시키고 RequestVote(Term=4)를 전송
기존 리더는 이 시점에도 여전히 자신이 리더라고 생각한다
기존 리더가 RequestVote(Term=4)를 수신하는 순간, 자신의 Term(3)보다 높은 것을 확인하고 Follower로 전환된다

리더의 강등은 선거 시작 시점이 아니라 높은 Term의 메시지를 수신하는 시점에 발생한다.

실질적으로 Pre-Vote가 통과되는 상황 자체가, 과반수의 노드가 현재 리더의 heartbeat를 받지 못하고 있다는 의미이다. 대부분의 경우 기존 리더가 이미 장애 상태이거나 파티션된 상태이므로 RequestVote를 수신할 수 없다.

선거 중 클라이언트 요청

Leader Election이 진행되는 동안에는 클러스터에 리더가 존재하지 않는다. 이 기간에 들어오는 클라이언트 요청은 어떻게 되는가?

Follower/Candidate에 도달한 요청: Raft에서 클라이언트 요청은 오직 리더만 처리한다. Follower나 Candidate는 요청을 거부하거나, 알고 있는 리더 정보를 응답에 포함하여 클라이언트가 리더에게 재시도하도록 유도한다
리더가 없는 상태: 선거가 완료될 때까지 쓰기 요청은 처리되지 않는다. 클라이언트는 타임아웃 후 다른 노드에 재시도한다
새 리더 선출 후: 새 리더가 빈 no-op 엔트리를 커밋하여 자신의 commitIndex를 확정한 뒤, 클라이언트 요청을 처리하기 시작한다

선거는 보통 수백 밀리초 내에 완료되므로, 클라이언트 입장에서는 짧은 지연으로 체감된다. Raft는 CP 시스템이므로 이 기간 동안 가용성보다 일관성을 우선한다.

Log Replication

로그 구조

flowchart LR
    subgraph "Leader의 로그"
        E1["Index 1<br/>Term 1<br/>set x=1"]
        E2["Index 2<br/>Term 1<br/>set y=2"]
        E3["Index 3<br/>Term 2<br/>set x=3"]
        E4["Index 4<br/>Term 3<br/>set z=5"]
    end

    E1 --> E2 --> E3 --> E4

로그는 순서가 보장된 엔트리의 배열이다
각 엔트리는 Index(위치), Term(생성 시점), Command(상태 머신에 적용할 명령)를 가진다
커밋된 엔트리는 모든 노드의 상태 머신에 동일한 순서로 적용된다

복제 과정

sequenceDiagram
    participant Client
    participant Leader
    participant F1 as Follower 1
    participant F2 as Follower 2

    Client->>Leader: set x=5
    Note over Leader: 로컬 로그에 엔트리 추가

    par AppendEntries
        Leader->>F1: AppendEntries(entries=[set x=5])
        Leader->>F2: AppendEntries(entries=[set x=5])
    end

    F1->>Leader: Success
    F2->>Leader: Success

    Note over Leader: 과반수 응답 → commitIndex 갱신
    Leader->>Client: OK (committed)

    Note over Leader: 다음 heartbeat에서 commitIndex 전파
    par 커밋 알림
        Leader->>F1: AppendEntries(commitIndex=N)
        Leader->>F2: AppendEntries(commitIndex=N)
    end

클라이언트가 리더에게 명령을 보낸다
리더는 자신의 로그에 엔트리를 추가한다
AppendEntries로 모든 Follower에게 복제한다
과반수의 Follower가 성공 응답을 보내면 해당 엔트리를 커밋한다
커밋된 엔트리를 상태 머신에 적용하고 클라이언트에 응답한다
Follower는 다음 AppendEntries에서 리더의 commitIndex를 받아 자신도 커밋한다

Log Matching Property

Raft는 두 가지 속성으로 로그 일관성을 보장한다:

같은 Index와 Term을 가진 엔트리는 같은 Command를 저장한다 — 리더는 주어진 Term에서 특정 Index에 최대 하나의 엔트리만 생성하기 때문
같은 Index와 Term을 가진 엔트리가 있으면, 그 이전의 모든 엔트리도 동일하다 — AppendEntries의 일관성 검사가 보장

AppendEntries에는 직전 엔트리의 Index와 Term(prevLogIndex, prevLogTerm)이 포함된다. Follower는 해당 위치의 엔트리가 일치하지 않으면 거부한다.

로그 충돌 해소

리더 교체 후 Follower의 로그가 리더와 불일치할 수 있다 (빠진 엔트리, 추가 엔트리, 또는 둘 다). 이 경우:

리더는 각 Follower에 대해 nextIndex를 유지한다
AppendEntries가 거부되면 nextIndex를 1 감소시키고 재시도한다
일치하는 지점을 찾으면, 그 이후의 Follower 로그를 리더의 로그로 덮어쓴다

Leader Append-Only: 리더는 자신의 로그에서 엔트리를 절대 삭제하거나 덮어쓰지 않는다. 오직 Follower의 로그만 리더에 맞게 교정한다.

Figure 8 문제

Raft의 가장 미묘한 안전 규칙이다.

Term 2의 리더 S1이 엔트리를 일부 노드에 복제했지만 커밋하지 못하고 장애가 발생했다
Term 3에서 S5가 새 리더가 되어 다른 엔트리를 작성했다가 역시 장애가 발생했다
Term 4에서 S1이 다시 리더가 되었다. Term 2의 엔트리가 과반수에 존재한다

S1은 Term 2의 엔트리를 “과반수에 복제되었으므로” 커밋해도 되는가?

안 된다. 커밋 후 S1이 다시 장애가 나면, S5가 자신의 더 긴 로그를 가지고 Term 5에서 리더가 되어 해당 엔트리를 덮어쓸 수 있다. 이미 커밋된 엔트리가 사라지는 것이다.

Raft의 해결책:

리더는 이전 Term의 엔트리를 복제 수로 커밋하지 않는다
오직 현재 Term의 엔트리만 복제 수로 커밋한다
현재 Term의 엔트리가 커밋되면, Log Matching Property에 의해 이전 Term의 엔트리도 간접적으로 커밋된다

이것이 새 리더가 취임 후 빈 no-op 엔트리를 로그에 추가하여 커밋하는 이유이다.

Safety 속성

Raft가 보장하는 다섯 가지 안전성 속성:

속성	설명
Election Safety	하나의 Term에서 최대 하나의 리더만 선출된다
Leader Append-Only	리더는 자신의 로그에서 엔트리를 삭제하거나 덮어쓰지 않는다
Log Matching	두 로그에서 같은 Index/Term의 엔트리가 있으면, 그 이전의 모든 엔트리도 동일하다
Leader Completeness	특정 Term에서 커밋된 엔트리는 이후 모든 Term의 리더 로그에 존재한다
State Machine Safety	특정 Index의 엔트리를 상태 머신에 적용했다면, 다른 서버는 같은 Index에 다른 엔트리를 적용하지 않는다

이 중 Leader Completeness가 가장 핵심적이다. Election Restriction과 Figure 8 커밋 규칙이 함께 작동하여 이 속성을 보장한다.

Leader 장애 시나리오

sequenceDiagram
    participant F1 as Follower A
    participant L as Leader (장애)
    participant F2 as Follower B
    participant F3 as Follower C

    Note over L: 정상 운영 중 heartbeat 전송
    L->>F1: Heartbeat (Term=3)
    L->>F2: Heartbeat (Term=3)
    L->>F3: Heartbeat (Term=3)

    Note over L: Leader 장애 발생

    Note over F1,F3: Election Timeout 대기 중...
    Note over F2: F2의 타임아웃이 먼저 만료

    F2->>F2: Term=4, Candidate로 전환
    F2->>F1: RequestVote(Term=4)
    F2->>F3: RequestVote(Term=4)

    F1->>F2: VoteGranted (로그가 최신이므로)
    F3->>F2: VoteGranted

    Note over F2: 과반수 획득 → 새 Leader (Term=4)
    F2->>F1: AppendEntries(heartbeat, Term=4)
    F2->>F3: AppendEntries(heartbeat, Term=4)

    Note over L: 장애 복구 후 복귀
    F2->>L: AppendEntries(Term=4)
    Note over L: Term 4 > Term 3 → Follower로 전환

장애 시점에 따른 영향

보다시피 꽤나 복잡해서, 장애가 터지는 시점에 따라 영향도가 다르다.

장애 시점	영향	복구
클라이언트 요청 수신 전	영향 없음	새 리더가 이어받는다
로컬 로그 기록 후, 복제 전	새 리더에 엔트리가 없을 수 있다	클라이언트가 타임아웃 후 재시도
복제 중 (과반수 미달)	일부 Follower에만 엔트리 존재	새 리더 로그에 포함되면 유지, 아니면 누락된다
과반수 복제 후 커밋 전	엔트리는 과반수에 존재	Election Restriction으로 이 엔트리를 가진 노드가 리더로 선출
커밋 후 클라이언트 응답 전	엔트리는 커밋됨	새 리더가 이어받고, 클라이언트는 재시도 가능

로컬 로그 기록 후 ~ 과반 수 미달 노드에 복제 중일 때 장애가 터지는게 제일 문제라고 볼 수 있다.

네트워크 파티션

flowchart TB
    subgraph "다수 파티션 (3노드)"
        L2["새 Leader (Term 4)"]
        F1["Follower"]
        F2["Follower"]
    end

    subgraph "소수 파티션 (2노드)"
        OL["옛 Leader (Term 3)"]
        F3["Follower"]
    end

    L2 <-->|정상 통신| F1
    L2 <-->|정상 통신| F2
    OL <-->|정상 통신| F3
    OL -.->|차단| L2

다수 파티션: 과반수를 유지하므로 새 리더를 선출하고 정상 운영한다
소수 파티션: 옛 리더가 쓰기 요청을 받아도 과반수 복제가 불가능하여 커밋할 수 없다
파티션 해소 시: 옛 리더는 높은 Term의 메시지를 받고 즉시 Follower로 전환된다. 소수 파티션의 미커밋 엔트리는 새 리더의 로그로 덮어써진다

이것이 Raft가 Split Brain을 구조적으로 방지하는 메커니즘이다. 과반수 투표와 과반수 커밋이라는 두 가지 Quorum 요건이 “동시에 두 개의 유효한 리더가 클러스터를 변경하는 상황”을 원천 차단한다.

Log Compaction

로그가 무한히 커지면 저장 공간과 복구 시간이 문제가 된다. Raft는 스냅샷(Snapshot)으로 이를 해결한다.

각 노드가 독립적으로 스냅샷을 생성한다
스냅샷에는 상태 머신의 현재 상태와, 마지막으로 포함된 엔트리의 Index/Term이 기록된다
스냅샷 생성 후 해당 Index까지의 로그를 삭제한다
Follower가 너무 뒤처져서 리더의 로그에 없는 엔트리가 필요하면, 리더가 InstallSnapshot RPC로 스냅샷을 전송한다

한계

리더 병목: 모든 쓰기가 리더를 경유하므로, 리더의 대역폭이 처리량의 상한
Crash Fault만 지원: 악의적인 노드(Byzantine Fault)는 처리하지 못한다. 블록체인처럼 신뢰할 수 없는 환경에서는 PBFT, Tendermint 등이 필요하다
읽기 성능: 기본적으로 읽기도 리더를 경유해야 일관성이 보장된다

내가 궁금했던 것들

리더는 SPOF인가

리더가 반드시 1개라면 SPOF(Single Point of Failure)가 아닌가 하는 의문이 생길 수 있다. 리더는 병목이지 SPOF가 아니다. SPOF는 해당 컴포넌트의 장애가 시스템 전체의 영구적 중단을 의미하는데, Raft에서 리더가 죽으면 Election Timeout 내에 새 리더가 자동 선출된다. 수동 개입이 필요 없다. 커밋된 엔트리는 이미 과반수 노드에 복제된 상태이므로 데이터 손실이 없다 선거 동안 쓰기가 잠깐 불가능하지만, 이는 일시적 가용성 저하이지 시스템 장애가 아니다

모든 노드에 동일한 로그를 복제하면 비효율적이지 않을까?

단일 Raft 그룹에서는 모든 노드가 동일한 로그를 보유한다. 이것은 공간을 대가로 내결함성을 확보하는 트레이드오프이며, 3벌 복제는 1노드 장애 허용을 위한 최소 비용이다.

다만 두 가지 메커니즘이 비효율을 완화한다:

Log Compaction: 각 노드가 스냅샷을 생성한 뒤 해당 시점까지의 로그를 삭제한다. 실제 저장 비용은 “현재 상태 스냅샷 + 최근 로그”뿐이다
Multi-Raft: CockroachDB, TiKV 같은 시스템에서는 데이터를 Range/Region으로 분할하고, 각 Range가 보통 3~5개 노드에만 복제된다. 10노드 클러스터라도 각 Range는 3노드에만 존재하므로 전체 데이터가 10벌 복제되는 것이 아니다

Multi-Raft 에 대해서는 별도의 글로 다루기로 한다