Distributed Consensus Algorithm : RAFT 합의 알고리즘

Distributed System
2025. 3. 9.

들어가기 전

이 글은 RAFT 알고리즘 논문을 공부하며 개인적으로 정리한 글입니다. 틀린 부분이 있을 수 있으니 이해에 참고만 하시고, 피드백 주실만한 부분은 언제든 댓글로 부탁드립니다.

1. RAFT Introduction

Consensus 알고리즘은 여러 노드로 구성된 클러스터에서 일부 노드가 장애를 겪고 있더라도, 클러스터가 일관된 상태로 잘 동작할 수 있도록 지원한다. 이런 이유 때문에 Consensus 알고리즘은 신뢰할 수 있는 대규모 소프트웨어 시스템을 구축하는데 핵심적인 역할을 한다.

RAFT 알고리즘 이전에는 Paxos 알고리즘이 Consensus 알고리즘에서 중요한 역할을 해왔다. Paxos 알고리즘의 큰 문제점은 이해하기 어렵다는 것이다. 이해하기 어렵다는 것은 Paxos 알고리즘을 배우고, 현실의 문제를 풀기 위해 적용하는 것이 어렵다는 것을 의미한다.

RAFT 알고리즘은 '이해하기 쉬운' Consensus 알고리즘을 만들자는 것이 목표로 만들어졌다. 이 알고리즘을 사용하는 모든 사용자들이 '왜 이 알고리즘이 동작하는가?'를 명확하게 이해할 수 있도록 만들어진 알고리즘이다. 이 목표를 달성하기 위해 RAFT는 여러 기법을 적용했는데, 그 중 대표적인 두 가지 기법이 있다.

기능 분해 (Decomposition): 중요한 과정을 각각 분해했다. (Leader Election, Log Replication, Safety)
상태 공간 축소 (State Space Reduction) : Paxos와 비교하여 비결정성을 줄이고, 서버 간의 불일치가 발생할 가능성을 감소

RAFT Consensus 알고리즘의 주요 특징은 다음과 같다.

강한 리더 (Strong Leader)
- RAFT는 다른 합의 알고리즘에 비해 리더의 역할이 더 강하다. 모든 요청은 리더가 처리하고, 모든 로그는 리더 -> 팔로워로만 흐른다.
리더 선출 (Leader Election)
- RAFT는 랜덤 타이머를 사용하여 리더를 선출한다. 이를 통해 충돌을 신속히 해결할 수 있다.
구성원 변경 (Membership Changes)
- RAFT는 클러스터 내 서버 구성을 변경하는 과정에서 Joint Consensus라는 새로운 방식을 사용한다. 이 방법을 통해서 클러스터가 정상적으로 운영될 수 있도록 보장한다.

RAFT Consensus 알고리즘은 논문이 발표된지 이제 10년이 지났으며, 이 알고리즘으로 구현된 오픈소스(Zookeeper, Etcd)가 프로덕션 환경(Kafka의 KRAFT, Kubernetes)에서 널리 사용되고 있다. 또한, 실용적인 시스템에 적용할 수 있을만큼 설명이 제공되고 있으며 이해할 수 있다.

이번 포스팅에서는 RAFT Consensus 논문을 바탕으로 이해를 하며 계속 정리를 하고자 한다.

2. Replicated State Machine

5.2 리더 선출

리더는 AppendEntries RPC를 정해진 주기마다 팔로워에게 보낸다. 팔로워는 일정 시간동안 정상적인 Append Entries 리더로부터 받지 못하면, 클러스터에 리더가 없다고 판단하여 Leader Election을 시작한다. 만약 정상적인 Append Entries RPC를 받는다면 Follower는 자신이 측정하고 있는 Election Timeout을 갱신한다. 이처럼 리더가 보내는 Append Entries는 'HeartBeat'의 역할도 겸하게 되는 것이다.

Follower가 받은 Append Entries RPC에는 비정상인 경우도 있다. 예를 들어 Follower의 Term이 10인데, 받은 Append Entries RPC의 Term은 5라면 이것은 비정상적인 Append Entries RPC이다. 따라서 정상적인 Append Entries RPC가 아니기 때문에 Follower의 Election timeout의 갱신에 영향을 주지 않는다.

선거과정

팔로워는 Election timeout이 발생하면, 즉시 다음 작업을 수행한다.

팔로워 -> Candidate로 상태 전환.
NewTerm = CurrentTerm + 1 (임기를 올림)
자기 자신에게 투표
클러스터의 모든 멤버들에게 RequestVote RPC를 전송.

그리고 Candidate가 된 팔로워는 클러스터의 멤버들에게서 Request Vote RPC에 대한 응답을 기다린다. Request Vote RPC 응답에 따라서 Candidate의 상태가 바뀌게 될 것이다. Candidate의 상태는 다음 세 가지 경우에 의해서 결정된다.

Candidate가 선거에서 승리
다른 Candidate가 선거에서 승리
선거의 승자가 없음.

각 내용은 아래에서 살펴본다.

한편 RequestVote RPC를 받은 Follower들은 투표를 해야한다. 투표의 조건은 다음과 같다.

유효한 RequestVote RPC를 받았다면, 해당 Candidate에게 투표를 고려할 수 있다. 그렇지 않다면 투표를 하지 않는다.
- 유효한 Request Vote RPC는 아래 두 가지 조건 중 하나를 만족해야한다. 그렇지 않다면 유효하지 않은 RPC다.
  1. Follower Term < Candidate Term (Request Vote RPC)
  2. Follower Term = Candidate Term -> Candidate가 보낸 마지막 로그는 Follower의 마지막 로그보다 최신이어야 함. 최신 로그의 판단 기준은 아래를 참고. (우선순위대로 적용)
    1. Candidate Last Log Term > Follower Last Log Term
    2. (Candidate Last Log Term = Follower Last Log Term) and (Candidate Last Log Index > Follower Last Log Index)
한번의 Leader Election에서 Candidate는 단 한번만 투표할 수 있다.
팔로워는 투표할 수 있을 때 바로 투표한다. (Candidate1이 먼저 RequestVote RPC를 보내고, 그 RPC가 유효한다면 Follower는 바로 Candidate1에 투표한다.)

1) 선거에서 승리하는 경우

Candidate는 과반수의 클러스터 멤버로부터 득표했을 때, 선거에서 승리한다.
승리하면 Candidate는 리더 상태로 바뀌고, 클러스터 멤버들에게 Append Entries RPC를 보내어 리더가 선출된 것을 알린다. 이것은 새로운 Leader Election이 발생하는 것을 방지하기도 한다.

선거에서 승리하는 조건이 과반수 이상의 득표이기 때문에 오직 하나의 Candidate만 선거에서 승리할 수 있다.

2) 다른 Candidate가 선거에서 승리

Candidate가 RequestVote RPC의 응답을 기다리는 동안 어떤 리더로부터 Append Entries RPC를 받는 경우가 있다. 이 때, 두 가지 행동을 할 수 있다.

Candidate Term > Append Entries Term: Candidate 상태 유지. Append Entries를 보낸 Leader에게는 '너는 outdated' 되었다고 응답하여, Follower 상태로 돌아갈 것을 안내.
Candidate Term <= Append Entires Term: Leader로 인정하고, Candidate는 Follower로 돌아간다.

3) 선거의 승자가 없는 경우

여러 팔로워가 동시에 Candidate가 되는 경우, 나머지 팔로워들의 투표는 분산될 수 있다. 누구는 Candidate1에게 투표, 누구는 Candidate2에게 투표할 수도 있다. 전체 4개의 노드가 있을 때 Candidate1이 2표, Candidate2가 2표가 된 경우 누구도 선거에서 승리할 수 없다. 이것을 Split Vote(분할 투표)라고 한다.

Follower는 기본적으로 RequestVote RPC를 받자마자 바로 그 Candidate에게 투표한다. 생각해보면 먼저 Candidate가 된 노드가 모든 투표를 독차지 할 것 같지만, 그렇지 않을 수도 있다. 분산환경에 존재하는 각 Node는 서로에게 도달하는 Network Distance가 다를 수 있기 때문이다. 따라서 늦게 Candidate가 되어 RequestVote RPC를 보내더라도, 그 RPC가 먼저 도달하는 경우는 존재할 수 있다.

RAFT에서는 Split Vote를 Election Timeout에 Candidate마다 서로 다른 Jitter를 주는 것으로 해결한다.

누구도 과반수를 받지 못했기 때문에 Candidate1, Candidate2는 곧 각자 Election Timeout을 만나게 될 것이다. 이것은 동시에 일어날 수도 있고, 누군가 먼저 Election Timeout을 만날 수도 있다. 이때, 각 Candidate는 Candidate 상태를 유지하면서 Term을 올리고 다시 한번 선거를 시작한다. 이때, Election Timeout에 서로 다른 Jitter를 주어서 각 Candidate마다 Election Timeout이 되는 시점을 다르게 한다.

이렇게 하면 다시 한번 Split Vote가 발생하더라도, 어떤 Candidate는 빠르게 Election Timeout이 발생해 혼자서만 Leader Election을 다시 한번 시작하게 된다. 이를 통해 다른 Candidate는 Follower로 돌아가게끔 유도하고, 자신이 과반수 투표를 받아 Leader가 되는 형태로 Split Vote가 해결된다.

1. Candidate1(Term 10), Candidate2(Term 10)을 가지고 있다고 가정하자.
2. Candidate1이 먼저 Election Timeout이 되어, 다시 한번 새로운 선거를 시작한다. Candidate1(Term 11), Candidate2(Term 10)
3. Candidate1은 Candidate2에게도 Request Vote RPC를 보낸다.
4. Candidate2가 받은 Request Vote RPC를 보니 자신이 가지고 있는 Term(10)보다 높은 Term(11)이 왔다. 따라서 Candidate2는 선거를 포기하고 Follower 상태로 전환된다.

5.3 Log Replication(로그 복제)

리더가 선출되면, RAFT 클러스터는 클라이언트의 요청을 처리하기 시작한다. 클라이언트는 리더에게 '새로운 로그'를 추가해달라는 요청을 주로 보낸다. 이때, 리더는 다음 순서대로 클라이언트의 요청을 처리한다. (리더는 로그를 Append 하는 기능만 수행한다. 로그를 빼거나 Rollback 하는 행위는 지원하지 않는다.)

리더는 새로운 Command(Log)를 자신의 Entry에 추가한다.
RAFT 클러스터의 모든 멤버들에게 새로운 Command가 포함된 Append Entries RPC를 전송한다. (Async)
과반수의 Follower가 리더가 보낸 Entry를 자신의 Entry에 추가했다는 응답을 리더에게 보내오면, 리더는 해당 Log Entries를 커밋하고 자신의 Local State Machine에 해당 Log Entry를 적용한다.
만약 Follower가 어떤 이유로 Append Entries RPC를 거절(Refuse)하는 응답이 오면, 다음 Append Entires RPC에 다시 한번 Entry를 포함해서 보낸다.

이 과정은 비동기로 이루어지고, 클러스터 멤버의 과반수만 로그를 복제하기만 하면 된다. 따라서 Follower가 죽거나, 네트워크 경로가 일시적으로 느려진다고 하더라도 RAFT 클러스터 전체의 속도에 많은 영향을 주지는 않는다.

또한 분산환경의 특성상, 리더가 보낸 Append Entries RPC가 팔로워에게 전달되지 않거나, 거절할 수도 있다. 이 상황은 리더가 각 팔로워들이 리더가 보낸 로그를 정상적으로 받을 때까지(복제할 때까지) Append Entries RPC를 무한히 재시도한다.

또한 분산환경의 특성상, 리더가 보낸 Append Entries RPC가 팔로워에게 전달되지 않거나, 거절할 수도 있다. 이 상황은 리더가 각 팔로워들이 리더가 보낸 로그를 정상적으로 받을 때까지(복제할 때까지) Append Entries RPC를 무한히 재시도한다.

이것은 리더는 [A, B, C] 로그를 가지지만, 일부 팔로워들은 [A,B] 로그를 가질 가능성이 있음을 의미한다. 이것은 RAFT 알고리즘이 Eventually Consistency 동작하는 것처럼 보인다. 그러나 RAFT는 Strong Consistency다. Strong Consistency는 다음에 의해서 보장된다.

1. Entry의 추가 / 조회는 항상 리더를 통해서만 이루어진다.
2. 리더는 과반수의 노드가 동의하는 상태(Entry)만 Commit한다.
3. 만약 리더가 죽어서, 새로운 리더가 선출되는 과정일 때는 '과반수의 노드가 인정하는 가장 최신의 Entry'를 가지는 노드가 리더로 선출된다.

일시적으로 노드가 가지는 상태는 다르더라도, 클라이언트는 리더를 통해서만 조회를 할 수 있고, 리더는 과반수의 노드가 동의하는 State만 Apply한다. 그리고 새로운 리더가 선출될 때에도 과반수의 노드가 인정하는 가장 최신 Entry를 가진 노드가 리더가 된다. 이런 이유 때문에 RAFT 클러스터는 Strong Consistency를 가진다고 볼 수 있다.

그럼에도 불구하고 리더가 Commit한 내용은 다음 Append Entries RPC 주기에 팔로워에게 전달되어, 팔로워 역시 Commit하며 로컬 State에 반영하기 때문에 일부 Data Inconsistency는 존재할 수 있다. 그러나 클라이언트는 항상 리더를 통해서 조회/추가를 하기 때문에 클러스터 전체적인 상태는 Strong Consistency라고 이해할 수 있다.

리더/팔로워 Entry Conflict Resolve 최적화 방법

리더는 Append Entries RPC를 보낼 때, 팔로워와 리더가 동의한 Match Index, Match Term을 메타 정보에 포함한다. 만약 리더가 보낸 Match Index, Match Term이 팔로워가 봤을 때 유효하지 않다면, 팔로워는 Append Entries RPC를 거절한다. 구현마다 다르지만 이때, 팔로워의 Entry들중에서 리더가 보낸 Term과 매치되는 가장 빠른 Index를 찾아서 응답한다.

리더는 이 정보를 받게 되면 다음 Append Entries RPC를 보내는 시점에 이 정보를 참고해서 다시 한번 Append Entries RPC를 보내게 되고, 리더/팔로워의 Log Entries 사이의 Conflict는 해소되게 될 것이다.

각 RAFT 노드에는 아래처럼 Entry가 저장된다. 각 Entry는 다음으로 이루어진다.

Term : Entry가 리더에게 추가된 Term
Index : Entries중에서 몇번째로 추가되었는지를 나타냄.
Data or Command : 클라이언트가 추가한 데이터, 혹은 커맨드가 될 수 있음.

리더는 새롭게 추가된 로그가 Local State Machine에 적용되는 시점을 결정한다. Local State machine에 적용될 수 있는 로그들을 커밋(Commit) 되었다고 한다. 리더는 RAFT 클러스터 멤버의 과반수 이상에 복제된 로그만을 Commit한다. 따라서 클러스터 전체적으로 봤을 때, 특정 시점에 리더와 일부 Follower(Minority)들은 서로 다른 Local State Machine을 가지는 순간이 존재할 수 있다.

위 그림(Figure 6)에서 그것은 더욱 자명한다. Index7은 3개의 노드에 복제되어있기 때문에 Commit 되었다. 한편으로는 2개의 노드는 아직 Index 5, Index 2의 정보 밖에 모르기 때문에 Leader/Follower에게 쿼리했을 때 받는 값이 다르다.

리더는 Last Commit Index를 계속 추적한다. 그리고 Append Entries RPC에 이 정보를 포함해서 보낸다. Follower들도 리더가 보낸 Last Commit Index를 참고해서, Follower들의 Commit Index도 점진적으로 리더를 따라잡게 된다. 그 과정에서 Follower는 자신의 Commit Index가 갱신될 때 마다, 자신의 Local State Machine에도 반영한다. 이것은 Follower / Leader의 Local State Machine이 가리키는 값이 일시적으로는 다를 수 있다는 것을 다시 한번 보여준다.

RAFT는 Strong Consistency 특성을 가진다. (Eventually Consistency는 어떨 때는 최신값, 어떨 때는 Outdated된 값을 반환함.)
Strong Consistency 특성은 '클라이언트가 요청했을 때, 항상 최신의 데이터를 보여준다'는 것을 의미한다. 즉, 외부에서 봤을 때 시스템이 일관성을 유지해야한다. 그렇다면 RAFT는 어떻게 Strong Consistency를 달성할까?

- 클라이언트는 리더를 통해서만 로그의 추가/조회가 이루어진다.
- 리더는 로그를 RAFT 노드에 복제할 책임을 가진다.
- 과반수의 RAFT 노드에 로그가 복제되었을 때, 해당 로그는 리더에서 커밋된다.
- 커밋된 로그는 각 RAFT 노드의 State에 적용된다.
- 또한, 커밋된 로그는 절대로 되돌릴 수 없다.

이 과정에서 한번 커밋된 로그는 모든 노드가 같은 순서로 적용된다.
리더를 통해 추가/조회가 되기 때문에 외부 관점에서는 항상 최신의 로그가 조회된다.
또한, 과반수의 노드가 동일한 순서로 커밋된 로그를 가지기 때문에 기존 리더에 문제가 생기더라도, 리더로 새로 선출되는 노드는 최신의 로그를 여전히 가지고 있다. (과반수 이상이 보유했을 때, 커밋되기 때문에). 따라서 기존 리더에 문제가 생겨서 새로운 리더가 만들어지더라도, Local State에 반영된 Entry의 상태는 최신의 상태를 항상 유지한다.

따라서 RAFT는 Strong Consistency 특성을 가진다

RAFT의 Log Entry는 다음 두 가지 특성을 가진다.

서로 다른 로그에 있는 두 항목이 같은 인덱스와 임기를 가진다면, 그들은 동일한 명령을 저장함.
서로 다른 로그에 있는 두 항목이 같은 인덱스와 임기를 가졌다면, 그 로그들의 앞선 항목들도 모두 동일하다.

첫번째 속성은 '리더는 특정 임기의 특정 로그 인덱스에 대해 최대 한 개의 Entry만 생성'하기 때문에 보장한다. 하나의 Term(임기)에 리더는 하나뿐이고, 리더가 Entry를 생성해서 Follower들에게 AppendEntries RPC로 전달하는 방식이다. 따라서 같은 Term, Index에 저장된 로그는 동일한 값을 가지는 것이 보장된다.

두번째 속성은 Append Entries RPC를 수행할 때 이루어지는 일관성 검사(Consistency Validation)에 의해서 귀납적으로 보장된다. 리더는 Append Entries RPC를 보낼 때마다, 새로운 Entry 바로 앞 인덱스(PrevIndex = NextIndex - 1)와 그 인덱스의 Term을 함께 보낸다. 그리고 Follower는 해당 Index에 있는 Term과 리더가 보낸 PrevIndex, PrevTerm을 비교한다. 만약 같지 않다면 Follower는 False를 반환, 성공한다면 True를 반환한다. 그 이후 Leader는 Index를 더 앞으로 땡겨가면서 Follower / Leader가 같은 로그를 바라보는 순간을 찾기 위해 노력하고 로그를 복원한다. 이를 통해 두번째 속성이 귀납적으로 보장된다.

Leader - Follower의 Entry Conflict

Leader -> Follower로 Append Entries RPC를 보내 동기화 하는 방식 덕분에 일반적인 경우에는 Leader/Follower 사이의 Append Entries 일관성 검사가 실패하는 일은 없다. 그러나 Leader가 Down되면 Leader/Follower 사이의 Consistency가 없어질 수 있다. Leader는 Append Entries RPC로 과반수의 Follower들에게 로그를 복제해야 로그의 Consistency가 유지된다. 그러나 Append Entries RPC가 이루어지기 전에 Leader가 Down되면 로그 복제에 실패하는 경우가 생긴다. 이런 Inconsistency는 연속된 Leader Down으로 인해 누적될 수도 있다.

위 그림(Figure 7)은 새로운 Leader / Follower의 로그가 어떻게 다를 수 있는지 보여준다.

팔로워는 리더가 가진 항목 일부를 갖고 있지 않을 수 있음.
팔로워는 리더가 갖지 않은 추가 항목을 포함하고 있을 수 있음.
위 두 가지 경우가 동시에 해당될 수도 있음.

Log Conflict이 발생했을 때, 로그에서 Conflict이 발생한 부분부터 팔로워들이 리더의 로그를 그대로 복제하도록 해서 리더/팔로워의 Log Inconsistency를 해소한다. 즉, 팔로워 로그에 Conflict된 부분이 리더 로그의 값으로 Overwrite 된다. 섹션 5.4에서는 이 방식에 한 가지 제약을 더하면, 이 방식이 안전하다는 것을 보여준다.

리더는 리더/팔로워가 가진 두 로그들에서 일치하는 가장 최신의 로그 항목을 찾아낸다. 그리고 그 시점 이후에 있는 팔로워의 로그들을 모두 리더의 로그들로 덮어쓰는 방식으로 Conflict을 해소한다. 그리고 이 작업은 Follower가 Append Entries RPC를 수신했을 때 수행하는 Log Consistency Check에서 처리된다. 자세한 내용은 바로 아래에서 후술한다.

Leader - Follower의 Entry Conflict Resolve

리더는 각 팔로워들에 대한 NextIndex를 유지한다. NextIndex는 리더가 팔로워에게 다음으로 전송해야할 가장 첫번째 인덱스를 의미한다. 예를 들어 Index 10까지 어떤 팔로워에게 전송했다면, 팔로워가 다음에 받아야 할 Index의 시작 지점은 11인데 이것을 의미한다.

Candidate가 처음으로 Leader가 되면, Leader는 모든 Follower에 대한 NextIndex를 아래와 같이 초기화한다.

# Python
new_next_index = []
for peer, _index in next_indexes.items():
  new_next_index[peer] = len(my_log_entries)

리더는 팔로워들에게 Append Entries RPC를 보내기 시작하는데, 이 과정에서 리더-팔로워의 Log Conflict가 해소되기 시작한다. Leader/Follower의 (PrevIndex, PrevTerm)이 다르면, Log Conflict가 발생한다. Follower는 Append Entries RPC가 실패한 것을 Leader에게 알린다.

Leader는 NextIndex를 하나 줄여서 다시 Append Entries RPC를 보낸다. 이 과정이 반복되면, 결국 NextIndex에서 Leader/Follower의 Entry가 일치하는 지점에 도달하게 된다. 이후, Leader의 Entry가 Follower에게 Overwrite 되면서 Leader의 로그가 Follower에게 복제된다.

간단히 설명하면 Log Replication은 다음 과정을 통해 이루어진다.

Append Entries RPC가 성공하면, Leader의 로그가 Follower에게 성공적으로 복제됨.
Append Entries RPC가 실패하면, Append Entries RPC가 성공할 때까지 Leader는 NextIndex를 감소시키며 Leader/Follower의 Log Conflict이 해소되는 부분을 찾아서 Append Entries RPC를 성공시킨다.

Figure 7에 대한 설명.

- (a) Index 10이 없다.
- (b) Index 5~10이 없다.
- (c) 리더에게 없는 Index 11이 있다.
- (d) 리더에게 없는 Index 11~12가 있다.
- (e) Index 6~7의 Term이 불일치(4!=5)하고, 인덱스도 없다.
- (f) Index 4~11까지 불일치한다.

(c)~(d) 같은 경우에는 Leader가 보낸 PrevIndex 이후의 Entry는 OverWrite 방식으로 구현되기 때문에 Append Entries RPC 한번에 해소된다.

(f)는 f가 스스로 Term 2,3에서 리더가 되고 클라이언트로부터 로그 추가 요청을 받았으나 자기 자신에만 추가하고, Follower에게는 복제하지 못한 채로 빠르게 Down되고, 다시 한번 리더로 선출된 경우에 발생할 수 있는 경우다. Leader는 (PrevTerm=6, PrevIndex=10)을 보내보는데 Follower에서는 Conflict가 있는 것을 확인하고 (ConflictTerm=3, ConflictIndex=7)을 응답한다. Leader에는 Term이 3인 Entry가 없기 때문에 ConflictIndex 7을 그대로 NextIndex로 설정한다. 그렇기 때문에 Leader는 (PrevTerm=5, PrevIndex=6)을 보내고, Follower는 다시 한번 (ConflictTerm =2, ConflictIndex=4)를 응답한다. Leader는 위와 동일하게 (PrevTerm=1, PrevIndex=3)을 보낸다. 이때, Follower의 Index 3의 Entry는 Term이 1이기 때문에 Conflict가 해소된 것으로 보고 여기서 [1,1,1,4,4,5,5,6,6,6]으로 Conflict이 해소된다.

Append Entries RPC를 최적화하기 위한 아이디어는 Append Entries가 실패했을 때, 리더에게 Conflict Term, Conflict Index를 함께 전송하는 것이다. 리더는 Conflict Term을 기반으로 NextIndex를 다시 결정할 수 있다. 실패할 때 마다 NextIndex = NextIndex - 1를 하는 것에 비해 Append Entries RPC 횟수가 줄어든다. 네트워크 비용이 줄어들기 때문에 Append Entries RPC의 최적화가 일부 가능하다.

5.4 안정성 (Safety)

위에서 설명한 메커니즘 만으로는 Strong Consistency(각 상태 머신이 정확히 동일한 명령을 동일한 순서대로 실행하도록)를 보장할 수는 없다. 예를 들어 한 Follower가 Leader가 여러 로그 항목을 커밋하는 동안 Unavailable 상태였다가 이후로 리더로 선출될 수 있다. 이때, 리더가 된 Follower는 최신 로그를 가지지 않은 상태인데 Append Entries RPC로 다른 Follower의 로그를 덮어쓴다면 RAFT 클러스터의 모든 노드는 태초 상태의 로그로 돌아가게 된다.

따라서 안정성을 위한 제약조건이 반드시 필요하다. 이 섹션에서는 리더로 선출될 수 있는 노드의 제약조건을 추가하여, RAFT 알고리즘을 완성한다. 즉, Figure 3에서 이야기 한 Leader Completeness Property를 만족하도록 한다. 이후 커밋 규칙을 더욱 명확히 정의할 것이다.

5.4.1 선거 제한 (Election Restirction)

RAFT 알고리즘에서는 새로운 리더가 선출되는 순간부터, 리더에게는 모든 이전 임기(Term)에서 커밋된 항목이 반드시 포함되도록 보장한다. 그렇기 때문에 Leader는 커밋되지 않은 로그를 다른 Follower에게 요구할 필요가 없다. 이 제한 덕분에 로그는 반드시 Leader -> Follower 단방향으로만 흐르게 되고, 알고리즘의 전체적인 복잡도를 단순화 해준다.

투표 과정에서 Follower는 자신의 Committed Entry를 Candidate가 포함하고 있는지를 검사하여, 충족하지 않은 후보자에게는 투표를 하지 않는다. 그리고 Leader 되기 위해서는 과반수 이상의 투표를 받아야 하고, Committed Entry 역시 과반수 이상이 동의해야한다. 이 제약 덕분에 리더로 선출된 노드는 과반수 이상의 노드가 동의하는 '최신 로그'를 가지고 있는 것이 보장된다.

구체적으로 이 선거 제한은 RequestVote RPC에서 구현된다.

Candidate가 Leader가 되기 위해서 과반수 서버의 투표를 얻어야 한다.
Follower의 로그가 Candidate보다 더 최신이라면, Follower는 투표하지 않는다.
최신 로그는 다음 조건으로 비교한다.
- 각 로그에서 가장 마지막 항목의 Index / Term을 비교한다.
- Term이 다르면, 더 큰 Term을 가진 쪽이 최신 로그다.
- Term이 같으면, 더 긴 로그(Index가 큰)가 최신이다.

%%% erlang
can_vote(VotedFor, FollowerTerm, FollowerLastLogTerm, FollowerLastLogIndex, VotedArgs) ->
  #vote_args{candidate_name=CandidateName,
             candidate_term=CandidateTerm,
             candidate_last_log_term=CandidateLastLogTerm,
             candidate_last_log_index=CandidateLastLogIndex} = VotedArgs,

  IsEqualTerm = FollowerTerm =:= CandidateTerm,
  NotYetVotedOrVotedSamePeer = VotedFor =:= undefined orelse VotedFor =:= CandidateName,
  CandidateHasLatestLogTerm = ((CandidateLastLogTerm > FollowerLastLogTerm) orelse
                               (CandidateLastLogTerm =:= FollowerLastLogTerm andalso CandidateLastLogIndex >= FollowerLastLogIndex)
  ),
  IsEqualTerm andalso NotYetVotedOrVotedSamePeer andalso CandidateHasLatestLogTerm.

이것은 위 코드로 표현할 수 있다.

5.4.2 이전 임기의 항목 커밋 (Commiting Entries from Previous Terms)

리더가 어떤 Entry를 과반수의 Follower에게 복제하였으나, Leader가 Commit하기 전에 Crash 되는 경우를 생각해보자. 이때, 그 Entry는 과반수 노드가 가지고 있기 때문에 Commit 요건을 만족하지만 Commit 되지는 않은 상태다. Commit 되지 않은 로그는 언제든지, 다음 리더에 의해서 덮어씌워질 수 있다.

위 이미지에서 '과반수 노드에 복제되었으나, 커밋되지 않고 다음 리더에 의해서 덮어씌워지는 경우'를 확인할 수 있다.

(a) S1(Term=2)은 리더. Index2(Term=2)는 부분적으로 복제됨.
(b) S1 crash. S5(Term=3)가 새로운 리더가 됨. Index2에 새로운 로그가 들어옴. (Term=3)
(c) S5 crash. S1(Term=4)가 새로운 리더가 됨. S1의 Index 2(Term=2)는 과반수의 노드에 복제됨. 그러나 커밋할 수는 없다. 왜냐하면 RAFT 리더는 자신의 임기에 만들어진 Entry가 복제되었을 때 커밋을 할 수 있기 때문이다.
(d) 만약 (c)에서 S1이 Crash되면, S2~S4의 투표로 S5는 리더가 될 수 있다. 그러나 Index 2(Term=3)를 모든 노드에 복제하더라도 Commit 할 수는 없다. 현재 리더의 Term이 5이기 때문이다.
(e) 반면 (c)에서 S1이 그대로 자신이 만든 Entry(Term=4)를 과반수의 노드에 복제하면 Commit 할 수 있다. 리더의 임기에 만들어진 로그가 과반수에 복제되었기 때문이다.

여기서 (c) ~ (d) 항목을 보면 Index2(Term=2)는 과반수에 복제되었으나, 커밋되지 않았기 때문에 (d)에서 새로둔 리더가 만들어졌을 때 덮어씌워질 수 있음을 보여준다.

이 문제를 단순히 해결하기 위해서 RAFT는 이전 임기의 항목을 Commit 할 때는 다음을 만족할 때만 처리한다.

Commit 하고자 하는 Entry의 Term = 현재 Leader의 Term이면 Commit한다. 이때, 이전 Term(임기)의 Entry까지 함께 커밋한다.
Commit 하고자 하는 Entry의 Term != 현재 Leader의 Term이면 Commit 하지 않는다. 앞서 이야기 한 것처럼 Commit 되지 않은 Entry는 다른 리더에 의해서 덮어씌워질 수 있기 때문이다.

이 방식은 로그 매칭 속성 (Log Matching Property)에 의해서 보장된다. Log Consistency 유효성 검사에서 Conflict가 발생한 것은 모두 해소될 것이기 때문이다.

5.5 Follower and Candidate crashes

앞선 설명에서는 리더의 장애에 초점을 맞췄다. 그렇다면 Follower, Candidate에 장애가 발생하면 어떻게 처리해야할까? Follower, Candidate 장애는 동일하게 처리된다.

AppendEntries, RequestVote RPC는 무한히 실패한다.
RPC가 실패하면 무한히 재시도한다.

RPC가 무한히 재시도 되기 때문에 Follower, Candidate가 장애에서 돌아오면 응답을 하게 될 것이다. 만약 Follower/Candidate가 동일한 RPC를 받더라도 RAFT RPC는 Idempotence를 가지기 때문에 중복 요청을 받아도 문제가 없다. 따라서 Follower/Candidate가 장애가 생기면 '리더가 무한히 RPC를 재시도한다'로 문제를 해결할 수 있다.

5.6 Timing and Availability

RAFT 요구사항 중 하나는 Safety가 타이밍에 의존하지 않아야 한다는 것이다. 그러나 Availability는 필연적으로 타이밍에 의존할 수 밖에 없다. 만약 RequestVote RPC 메세지 교환 시간이 Election Timeout 시간보다 길다면, Candidate는 절대로 Leader가 될 수 없다. RAFT는 Leader 없이 운영할 수 없기 때문에 RAFT는 Available 하지 않게 된다. 따라서 RAFT의 Availability는 타이밍에 의존적인 것을 인정하고, 타이밍을 넉넉하게 설정해서 RAFT가 안정적으로 운영될 수 있도록 해야한다.

BroadCast Time << Election Timeout << MTBF

Broadcast Time은 서버가 클러스터 내에 RPC를 전송하고, 응답을 받는데 걸리는 시간이다.
Election Timeout은 각 Follower 노드의 Election Timeout되는데 필요한 시간이다. (유효한 Append Entries RPC를 받아야 하는 시간)
MTBF (Mean Time Between Failures) : 단일 서버의 평균 장애 발생 간격

BroadCast Time은 Election Timeout보다 1 order가 작아야한다. 즉, 1/10 수준이 되어야한다. 이 조건을 만족하면 RequestVote RPC/AppendEntries RPC를 안정적으로 주고 받을 수 있게 되어 RAFT는 정상적으로 리더를 선출하고, 클러스터를 운영할 수 있게 된다.

또한 Election Timeout은 MTBF에 비해 몇 Order는 작아야한다. MTBF는 시스템에 의해서 결정되는 값이고, Election Timeout은 사용자가 선택할 수 있는 값이다. 만약 리더가 Crash 된다면, 일반적으로 Election Timeout 이내에 새로운 리더가 선출될 것이다. 그리고 새로운 리더가 선출되는 시간동안은 RAFT 클러스터는 Unavailable한 상태가 된다. 즉, Election Timeout을 가능한 짧게 가져가는 것이 좋다.

그러나 AppendEntries RPC 등은 전송된 Entry가 DISK에 영속화되는 시간 역시 필요할 수 있고, 거기에 Network RTT가 추가된다. 이 시간을 가리키는 BroadCast Time이다. 지구 반대편까지 필요한 RTT는 250ms~300ms 정도가 걸린다고 하는데, RAFT Node가 같은 지역에 있다면 broad cast time은 0.5ms ~ 20ms정도면 충분하다고 한다. 따라서 우리는 Election Timeout의 범위를 5ms ~ 200ms까지로 추산할 수 있다. 논문에서는 여기에서 좀 더 여유를 두어 Election Timeout의 범위가 20ms ~ 500ms 정도가 될 것으로 기대한다.

6. Cluster Membership Changes

저작자표시 비영리 변경금지

'Distributed System' 카테고리의 다른 글

Distributed Membership Protocol : HyParView 프로토콜 (0)	2025.02.15
Distributed Gossip Protocol : Plum tree 프로토콜 (0)	2025.02.14
Distributed Membership Protocol : SWIM 프로토콜 (0)	2025.01.31
분산 컴퓨팅 10. 벡터 시계와 스냅샷 찍기 (0)	2024.03.17
분산 컴퓨팅 3. 시간 동기화 문제와 논리적 시계 (램포트 시계) (0)	2024.03.17

만년 꼴지 공대생 세상 이야기