In Search of an Understandable Consensus Algorithm 번역 및 정리

Raft란?

Raft는 tikv, etcd, MongoDB 등 다양한 분산 시스템에서 사용되는 실용적인 합의 알고리즘이다.

기존의 Paxos 같은 합의 알고리즘에 비해 훨씬 이해하거나 구현하기 쉬우면서 이에 필적할만한 성능을 제공한다. 특히 이해 가능성(Understandability)은 Raft 알고리즘의 가장 중요한 목표이기도 하다.

Raft는 크게 두 가지 접근을 통해 이해 가능성을 달성한다.

문제를 나눠서 접근하기: Leader Election, Log Replication, Membership changes.
고려해야 하는 상태의 수를 줄여 상태 공간 단순화 하기.

Raft만의 특징

Raft는 다른 분산 시스템 알고리즘들과 비슷하게 작동하지만 아래는 Raft만의 특징들이다.

Strong Leader: Raft는 다른 합의 알고리즘들에 비해 리더에게 더 많은 권한을 부여한다. 예를 들어 로그 엔트리들은 리더에서 다른 팔로워 서버들로 단방향으로 흐르게 된다. 이러한 단방향 흐름은 복제된 로그들을 관리하기 수월하고 이해하기 쉽게 만들어준다.
Leader Election: Raft는 리더를 선출할 때 무작위 타이머를 사용한다. 무작위 타이머는 아주 약간의 구현 추가로 충돌 문제를 단순하고 빠르게 해결해준다.
Membership Changes: Raft의 메커니즘은 클러스터 내 서버들을 변경할 때 업데이트 기간 동안 서로 다른 설정들이 overlap 되는 Joint consensus라는 새로운 접근 방식을 사용한다. 이러한 접근 방식은 클러스터가 운영 중일 동안 설정 업데이트를 가능하도록 만들어준다.

상태 머신 복제 (Replicated State Machines)

전형적으로 복제된 상태 머신은 복제된 로그를 사용하여 구현된다. 각각의 로그들은 같은 순서로 같은 명령의 집합을 포함하며, 따라서 각 상태 머신들은 같은 순서의 명령들을 처리하게 된다. 각 상태 머신들은 결정적이기 때문에 같은 상태라면 같은 출력이 보장된다.
복제된 로그들의 일관성을 보장하는 것이 합의 알고리즘의 역할이다.
합의 모듈은 클라이언트들의 요청을 받아 로그에 추가한다. 특정 서버에 장애가 발생하더라도 같은 요청들이 같은 순서로 복제되도록 보장한다. 결과적으로 서버들은 단일의 신뢰성 높은 상태 머신을 만들게 된다.

서버의 상태

특정 시각에 서버들은 Leader(리더), Follower(팔로워), Candidate(후보자) 셋 중 하나의 상태에 속하게 된다.
리더는 모든 클라이언트의 요청을 받는다. 만약 팔로워로 요청이 전달되면 리더에게 리다이렉트 된다.
팔로워는 어떤 요청도 능동적으로 보내지 않으며 리더와 후보자들로부터의 요청에 단순히 반응하기만 하는 수동적인 상태이다.
후보자는 리더 선출에 사용된다.

리더와 팔로워

하나의 리더를 선출함으로써 합의를 구현한다. 리더는 복제 로그들을 관리하기 위한 책임을 맡는다. 클라이언트들에게 로그 엔트리를 전달 받고 다른 서버들에 요청을 복제하며 상태 머신에 로그 엔트리들을 적용해야 할 때 알려준다.

리더를 갖는 것은 복제 로그들의 관리를 단순화 해 준다. 예를 들어 리더는 다른 팔로워들과의 소통 없이 새로운 로그 엔트리들을 어디에 놓아야 하는지 결정할 수 있다. 또한 데이터는 리더에서 팔로워 단방향으로 흐르게 된다. 리더에 장애가 생기게 되면 새 리더가 선출된다.

Term

Raft는 시간을 term이라고 하는 임의의 길이로 쪼갠다. term은 연속된 정수들로서 논리적인 시계의 역할을 맡는다. 각각의 서버들에 current term을 저장해 사용함으로써 stale된 리더를 탐지할 수 있다. current term은 서버들이 통신할 때 마다 교환되며 만약 한 서버의 current term이 다른 서버의 current term보다 작다면 해당 current term의 값을 더 큰 값으로 업데이트 한다.
만약 후보자나 리더가 자신의 term 값이 구식임을 확인하면 즉시 팔로워 상태로 돌아간다.
만약 서버가 구식 term 값을 포함하는 요청을 전달 받으면 해당 요청을 거절한다.

시간은 여러 term으로 나뉘며, 각 term은 선거로 시작한다. 선거가 성공적으로 끝나면 단일 리더가 그 term의 끝까지 클러스터를 관리한다. 선거가 실패하는 경우 리더 없이 term이 종료된다.

Raft 구현에 사용되는 RPC

기본적인 Raft 알고리즘에서의 서버들의 통신에는 오직 AppendEntries(AE), RequestVote(RV)라는 두 종류의 RPC가 필요하다.
만약 RPC가 타임 아웃되면 재요청(Retry)하게 되며 최적의 성능을 위해 RPC를 병렬로 요청한다.

Safety Properties

Raft는 아래와 같은 성질들이 항상 성립됨을 보장한다.

Election Safety: 주어진 term마다 하나의 리더만 선출된다.
Leader Append-Only: 리더는 절대 자신의 로그를 덮어쓰거나 삭제하지 않는다. 오직 새로운 엔트리를 추가하기만 한다.
Log Matching: 만약 두 로그가 동일한 index와 term 값을 가진 엔트리를 포함한다면 두 로그의 엔트리들은 주어진 그 엔트리의 index까지 모두 동일하다.
Leader Completeness: 만약 한 로그 엔트리가 어떤 term 값에 커밋된다면 해당 엔트리는 더 높은 term 값들을 갖는 리더들의 로그에 존재하게 될 것이다.
State Machine Safety: 어떤 서버가 로그 엔트리를 주어진 index에 상태 머신에 적용할 경우 다른 서버들은 해당 index에 다른 로그 엔트리를 적용할 수 없다. 해당 Property는 Raft의 안정성을 위한 Key Property이다.

리더 선출 (Leader Election)

Raft는 heartbeat라는 메커니즘을 통해 리더를 선출한다.

서버들은 시작할 때 팔로워 상태로 시작한다. 팔로워 상태의 서버는 리더나 후보자에게 유효한 RPC들을 받을 때 까지 팔로워 상태를 유지한다.

리더는 모든 팔로워들에게 주기적으로 heartbeat 신호를 보내는데, 이것은 빈 로그 엔트리를 가진 AppendEntries RPC로 구현된다.

만약 리더가 Election timeout이라고 부르는 정해진 기간 동안 RPC를 보내지 않으면, 리더에 장애가 생긴 것으로 간주하고 새로운 리더 선출 프로세스를 시작한다.

선거 시작을 위해 팔로워는 current term을 증가시키고 후보자 상태로 전이한다. 그리고 자신에게 투표하고 RequestVote RPC를 클러스터 내 서버들에게 병렬로 실행한다.

후보자는 아래 세 가지 중 하나가 일어날 때 까지 후보자 상태를 유지한다.

해당 후보자가 선거에 승리해 리더가 됨.
다른 후보자가 리더로 선출됨.
선거 시간이 끝났지만 어떤 서버도 리더로 선출되지 못함.

후보자는 클러스터 내 같은 term 값을 가진 다수의 서버들(Majority)에게 투표를 받게 되면 리더로 선출된다. 리더로 선출된 직후 추가적인 선거가 일어나는 것을 방지하기 위해 다른 모든 서버들에게 heartbeat를 보낸다.

투표 결과를 기다리는 동안 후보자는 본인이 리더라고 주장하는 서버로부터 AppendEntries RPC를 받게 될 수 있다. 이 경우 해당 리더의 term 값이 구식이라면 해당 RPC는 거절된다. 구식이 아닌 경우 리더가 클러스터 내에 이미 존재하므로 후보자는 다시 팔로워 상태로 돌아간다.

만약 너무 많은 팔로워들이 후보자로 동시에 참가하면, 표가 분산되어 어떤 서버도 리더로 선출되지 못할 수 있다. 이런 일이 발생하면 각 후보자들의 RequestVote RPC들은 모두 타임아웃 될 것이고, 그들의 term 값을 증가시킨 후 새 선거를 시작하게 된다. 여기에서 추가적인 조치를 취하지 않는다면 표 분산(Split vote)은 영원히 계속될 것이다.

Raft는 Election timeout 값을 고정된 값(150ms - 300ms)으로 무작위 선정함으로써 이런 표 분산 문제를 해결한다.

무작위성으로 인해 어떤 하나의 서버가 먼저 투표에 승리할 것이고, 다른 후보자들이 타임 아웃 되기 전에 heartbeat를 보낼 것이다.

로그 복제 (Log Replication)

리더로 선출된 서버는 클라이언트 요청들에 대해 서비스 하기 시작한다.

각 클라이언트 요청들은 복제된 상태 머신들에 의해 실행되어야 하는 명령을 포함한다. 리더는 그 명령을 새로운 엔트리로 자신의 로그에 추가한다.

그리고 AppendEntries RPC들을 병렬로 실행해 각 서버들에게 해당 엔트리를 복제하도록 한다. 해당 엔트리가 안전하게 복제되고 나면, 리더는 자신의 상태 머신에 해당 엔트리를 적용해 실행 결과를 클라이언트에 돌려주게 된다.

만약 팔로워 서버에 장애가 발생하거나, 패킷 로스가 발생하는 경우 (클라이언트에 응답한 이후에도) 지속적으로 Retry 요청을 보내 모든 팔로워들이 최종적으로 같은 로그 엔트리들을 저장하도록 만든다.

상태 머신과 로그 엔트리 커밋

각각의 로그 엔트리들은 해당 엔트리를 저장했을 때의 term 값과 함께 상태 머신 명령을 저장한다.

로그 엔트리의 term 값들은 로그들 간에 비일관성을 탐지하기 위해 사용되며, 각 로그 엔트리들은 또한 해당 로그에서의 위치를 파악하기 위한 정수 인덱스(index) 값을 갖는다.

리더는 각 로그 엔트리들을 언제 상태 머신들에 적용해도 괜찮은지를 판단한다. 상태 머신에 적용해도 괜찮다고 판단한 로그 엔트리들은 커밋되었다고(Committed) 표현한다.

Raft는 커밋된 로그 엔트리들에 안전함, 견고함을 보장하며, 커밋된 엔트리들은 최종적으로 가용한(Available) 상태 머신들에 의해 실행된다.

로그 엔트리는 대다수의 서버들에 복제되었을 때 리더에 의해 커밋된다. 이 때 또한 해당 엔트리보다 앞서 있는 다른 로그 엔트리들도 같이 커밋된다. (해당 리더 이전의 리더들이 만든 엔트리들까지 포함하여)

리더는 커밋된 엔트리들 중 가장 높은 엔트리의 index를 추적하며, 해당 index 값을 heartbeat를 포함한 모든 AppendEntries RPC에 포함시킨다.

팔로워들은 특정 엔트리가 커밋되었다는 것을 알게 되면 자신의 상태 머신에 해당 엔트리를 로그 순서대로 적용한다.

Log Matching Property

Raft 로그 메커니즘은 서버들의 로그 시퀸스들이 높은 Coherency를 갖도록 설계되어 있다. 이 점은 단지 시스템의 행동을 단순화하고 예측 가능하게 만들어 줄 뿐 아니라 안정성을 보장해주는 중요한 요인이다.

Raft는 아래 Log Matching Property가 성립하도록 보장한다.

만약 서로 다른 로그의 두 엔트리가 같은 index와 term 값을 가진다면 두 엔트리는 같은 명령을 저장한다.
만약 서로 다른 로그의 두 엔트리가 같은 index와 term 값을 가진다면 해당 엔트리 앞의 모든 엔트리들 또한 동일하다.

첫 번째 성질은 리더가 주어진 index와 term에 대해 최대 1개의 엔트리를 만들어내며, 로그 엔트리들은 절대 그들의 위치를 바꾸지 않는다는 점에서 유도될 수 있다.

두 번째 성질은 AppendEntries RPC를 수행할 때 간단한 일관성 검사를 수행함으로써 만족될 수 있다. AppendEntries RPC를 보낼 때 리더는 새 엔트리의 바로 앞 엔트리의 index 및 term 값을 RPC에 포함시킨다. 팔로워가 그들의 로그에서 같은 index와 term 값을 갖는 엔트리를 찾지 못하면 해당 AppendEntries RPC는 거절된다. 이 일관성 검사에 의해 Log Matching Property가 유도된다.

로그의 초기 상태는 Log Matching Property를 만족한다. 그리고 위 AppendEntries의 일관성 검사에 의해 로그가 늘어날 때 마다 Log Matching Property가 보존된다. 결과적으로 AppendEntries가 성공적으로 리턴될 때 마다 리더는 각 팔로워들의 로그가 자신의 로그와 추가된 새 엔트리 항목까지 동일할 것이라는 것을 알 수 있다.

장애 상황에서 비일관성 해결

장애가 없는 경우 리더의 로그들과 팔로워의 서버들은 일관성을 갖는다. 따라서 AppendEntries의 일관성 검사는 절대 실패하지 않을 것이다.

그러나 리더의 장애는 로그를 비일관적으로 만들 수 있다. (구식 리더가 로그 엔트리들을 완전히 복사하지 않았을 수 있다.) 이러한 비일관성은 리더와 팔로워들에게 일련의 장애를 유발할 수 있다.

리더에 있는 엔트리들의 일부가 팔로워에 존재하지 않거나 리더에 없는 추가적인 엔트리들을 갖고 있을 수도 있으며, 이러한 엔트리 장애가 몇 차례의 term에 걸쳐 있을 수 있다.

Raft는 이러한 비일관성을 리더가 팔로워들의 로그에 자신의 로그를 붙여 넣게 함으로써 해결한다. 이것은 팔로워들에서 발생한 엔트리 충돌을 리더의 로그를 덮어 씌움으로써 해결한다는 것을 의미한다.

위 그림에서 이 작업은 한 가지의 제한을 가정함으로써 안전하게 이뤄질 수 있다.

팔로워의 로그와 리더의 로그를 일치 시키기 위해 리더는 두 개의 로그가 일치하는 가장 최신의 지점(가장 높은 인덱스)을 찾아야 한다. 팔로워는 찾은 해당 지점 이후의 모든 엔트리들을 삭제한다. 리더는 팔로워에게 리더가 갖고 있는 해당 지점 이후의 모든 엔트리들을 보낸다.

이 모든 작업들은 AppendEntries RPC에 의해 수행된 일관성 검사에 대한 응답으로 발생한다.

리더는 각 팔로워들에 대해 해당 팔로워에게 보낼 다음 로그 엔트리의 index인 nextIndex[]를 유지한다.

리더는 자신이 리더로 선정되었을 때 nextIndex[] 값들을 서버의 마지막 엔트리의 다음 index 값으로 설정한다.

팔로워의 로그가 리더의 로그와 비일관성을 갖는다면 AppendEntries의 일관성 검사는 다음 AppendEntries RPC에서 실패할 것이다. RPC가 거절된 후 리더는 nextIndex 값을 감소시키고 AppendEntries를 재시도하게 된다.

결과적으로 nextIndex는 리더와 팔로워의 로그가 매칭되는 지점에 도달하게 된다. 이 지점에 도달했을 때 AppendEntries는 성공하게 될 것이고, 팔로워에 존재하는 충돌을 일으키고 있는 모든 엔트리들이 제거되고 리더에 존재하는 엔트리들을 덧붙이게 될 것이다.

이런 메커니즘을 통해 리더는 별 다른 추가 조치 없이 로그 일관성을 복원할 수 있다.

리더는 일반적인 동작(Normal Operation)으로 시작해서, AppendEntries의 일관성 검사 실패에 대한 응답으로 자동으로 로그를 동기화시킨다. 리더는 절대로 자신의 로그를 삭제하거나 덮어쓰지 않는다.

Raft는 대부분의 서버들이 가용 중인 한 새로운 로그 엔트리들을 받아들이고, 복제하고, 새로운 로그 엔트리들을 적용할 수 있다. 일반적인 경우 한 라운드의 RPC들을 통해 새로운 엔트리를 클러스터 내에 복제시킬 수 있으며, 소수의 느린 팔로워는 성능에 영향을 주지 못할 것이다.

AppendEntries 최적화

바람직하게는 거절되는 AppendEntries RPC의 갯수를 줄이는 방향으로 프로토콜을 최적화할 수 있다.

예를 들어 AppendEntries 요청을 거절할 때 팔로워는 충돌이 난 엔트리의 term과 그 term을 저장하는 첫 번째 index를 포함시킬 수 있다. 이 정보들로, 리더는 nextIndex를 해당 term에 해당하는 모든 충돌 엔트리들을 건너뛰도록 조정 할 수 있다. 이런 최적화를 통해 한 개의 RPC로 한 개의 엔트리를 건너뛰는 것에서 해당 term에 해당하는 엔트리들을 모두 건너뛰는 방식으로 최적화 할 수 있다.

다만 실제 시스템에서 장애는 이렇게 빈번하게 일어나지 않고, 여러 엔트리에 비일관성이 나타날 가능성이 희박하기 때문에 이러한 최적화가 필요한 것인지는 의문이다.

안정성 보장

이전의 섹션들에서, Raft가 어떻게 리더를 선출하고 로그 엔트리들을 복제하는지에 대해 다루었다. 그러나, 지금까지의 메커니즘만으로는 각각의 상태 머신들이 정확하게 같은 명령들을 같은 순서로 시행하는 것을 보장해주지 못한다.

예를 들어 리더가 여러 개의 로그 엔트리들을 커밋할 때 어떤 팔로워가 불가용할 수 있다. 그리고 리더로 선출되고 커밋된 로그 엔트리들을 새 엔트리로 덮어씌워 버릴 수 있다.

이는 결과적으로 다른 상태 머신들에서 서로 다른 명령어 시퀀스가 실행될 수 있다는 것을 의미한다.

Election restriction

어떤 리더 기반의 합의 알고리즘에서든 리더는 결과적으로 커밋된 모든 로그 엔트리들을 저장해야 한다.

어떤 합의 알고리즘에서는 모든 커밋된 엔트리들을 포함하지 않는 서버를 리더로 선출하기도 한다. 이런 접근 방법은 불행하게도 상당한 복잡함을 유발하기 때문에, Raft는 이전 term 값에서 커밋된 모든 엔트리들이 새 리더에 존재함을 보장한다 (Leader Completeness 참고). 이것은 로그 엔트리들을 팔로워에서 리더로 옮길 필요가 없게 만들어주고 데이터의 흐름을 리더에서 팔로워의 단방향으로 흘라가게 만들어주며, 리더가 절대 기존의 엔트리들을 덮어씌우지 않게 만들어준다.

Raft는 모든 커밋된 로그들을 갖고 있지 않은 후보자가 선거에서 이기지 못하도록 만듦으로써 이것을 구현한다. 후보자는 클러스터 내 대다수의 서버들에게 접촉해야 한다. 이 중 적어도 하나의 서버는 모든 커밋된 엔트리들을 갖고 있을 것이므로 이것은 후보자가 모든 커밋된 엔트리들을 갖고 있도록 보장해준다.

RequestVote RPC가 이러한 제한을 구현한다. 이 RPC는 후보자 로그의 정보를 포함하며, 투표자는 자신의 로그가 후보자의 로그보다 더 최신일 때 투표를 부정하게 된다.

Raft는 두 로그 중 어떤 로그가 최신인지를 index 및 로그 마지막 엔트리의 term 값을 비교함으로써 결정한다.

두 로그의 마지막 엔트리가 다른 term 값을 지닌다면 더 큰 term 값을 갖는 로그가 더 최신 로그가 된다.
두 로그의 마지막 엔트리가 같은 term 값을 지닌다면 두 로그 중 긴 것이 가장 최신의 로그가 된다.

previous term 값을 지닌 엔트리 커밋

이전 섹션에서 설명한 것과 같이 리더는 current term으로부터 해당 엔트리가 대다수의 서버에 저장되면 어떤 엔트리가 커밋되었는지 알게 된다.

해당 엔트리가 커밋되기 전에 리더에 장애가 발생하는 경우 미래의 새로 선출된 리더가 그 엔트리의 복제를 끝내려고 시도하게 될 것이다.

그러나 리더는 엔트리가 대다수의 서버에 저장되는 previous term로부터 엔트리가 커밋되었는지에 대해 즉시 알 수 없다.

위 그림은 대다수의 서버들에 로그 엔트리가 저장되어 있지만 미래의 리더가 값을 덮어씌울 수 있는 문제를 보여준다.

이런 문제가 발생하는 것을 막기 위해 Raft는 이전 term 값에선 절대 Replica의 갯수를 세는 방식으로 커밋하지 않는다.

오직 리더의 current term으로부터의 로그 엔트리들만이 Replica의 갯수를 세는 방식을 통해 커밋된다.

current term으로부터 로그 엔트리가 이 방식으로 커밋되고 나면, 모든 이전의 엔트리들은 Log Matching Property에 의해 간접적으로 커밋된다.

사실 리더가 오래된 로그들을 커밋할 수 있는 안전한 상황들이 몇 가지 더 있지만, Raft는 단순성을 위해 보수적인 접근 방법을 취한다.

Raft는 리더가 이전 term의 엔트리들을 복제할 때 원래 term 값을 유지하도록 만들기 때문에 커밋 규칙에 이런 추가적인 복잡성이 유발된다.

안정성 증명 (Safety Argument)

여기서는 Leader Completeness가 False라고 가정한 후 모순을 증명한다.

리더가 term T 에서 로그 엔트리를 커밋했고, 해당 로그 엔트리가 미래의 term U에서 리더에 저장되지 않았다고 가정해보자. (term T의 리더를 leaderT, term U의 리더를 leaderU라고 지칭)

리더는 결코 엔트리들을 지우거나 덮어쓰지 않으므로 해당 로그 엔트리는 leaderU의 로그에 누락되어 있어야 한다.
leaderT는 클러스터 대다수에 로그를 복제했고 leaderU는 클러스터 대다수에서 투표를 받았다. 따라서 적어도 한 노드(voter)는 leaderT로 부터 로그 엔트리를 받아들이고 leaderU에 투표했을 것이다. 이 투표자가 모순에 도달하는 키이다.
투표자는 leaderU에 투표하기 전에 leaderT로부터 커밋된 엔트리를 받아들였어야 한다. 그렇지 않았다면 투표자의 term이 T 보다 높기 때문에 leaderT의 AppendEntries 요청이 거절되었을 것이다.
투표자는 leaderU에 투표할 때 까지 해당 로그 엔트리를 저장하고 있었다. 왜냐하면 그 사이의 모든 리더가 해당 로그 엔트리를 포함했기 때문이다. 리더는 엔트리를 절대 덮어쓰지 않고 팔로워는 리더와 충돌하는 경우에는 엔트리를 제거한다.
투표자는 leaderU에게 투표했으므로 leaderU의 로그는 투표자의 로그만큼 최신이어야 하며 이것은 아래 두 모순 중 하나로 이어진다.
첫째로, 만약 투표자와 leaderU가 같은 마지막 term이 같다면 leaderU의 로그는 투표자의 로그만큼 길어야 한다. 따라서 투표자의 로그에 있는 모든 항목은 leaderU에 포함되어야 하는데 이는 term U에 해당 로그 엔트리가 저장되지 않았다는 가정과 모순된다.
둘째로, 투표자 보다 leaderU의 term이 길다면 투표자의 최소 term 값은 T일 것이다 (term이 T인 커밋된 엔트리를 포함하고 있으므로). leaderU의 마지막 로그 엔트리를 커밋한 리더는 그 로그에 커밋된 항목을 포함해야 하므로, Log Matching Property에 의해 leaderU의 로그 또한 커밋된 항목을 포함해야 한다. 즉 이 역시 가정과 모순된다.
따라서, T보다 큰 모든 term의 리더들은 T에서 커밋된 모든 엔트리를 포함해야 한다.
Log Matching Property는 미래의 리더들도 간접적으로 커밋된 항목들을 포함할 것임을 보장한다.

Leader Completeness를 통해 State Machine Safety Property를 증명할 수 있다.

State Machine Safety Property에 따르면 주어진 인덱스에서 서버가 로그 엔트리를 상태 머신에 적용했다면 다른 서버는 그 인덱스에 대해 다른 로그 엔트리를 절대 적용하지 않을 것이다.

서버가 로그 엔트리를 상태 머신에 적용할 때 그 로그는 해당 엔트리를 포함해 리더의 로그와 동일해야 합니다. 이제 주어진 로그 인덱스를 적용하는 서버가 있는 가장 낮은 term 값을 고려해보자. Log Completeness 속성은 모든 더 높은 임기의 리더들이 동일한 로그 엔트리를 적용할 것임을 보장한다. 따라서 나중 임기에서 로그를 적용하는 서버들은 같은 로그를 적용할 것이다. 따라서 State Machine Safety Property가 유지된다

마지막으로 Raft는 서버가 로그 인덱스 순서대로 엔트리를 적용하도록 요구한다. 이것은 State Machine Safety Property과 결합되어, 모든 서버가 동일한 로그 엔트리 집합을 자신의 상태 기계에 적용하게 될 것임을 의미한다.

팔로워, 후보자 서버 장애 핸들링

팔로워, 후보자에 발생하는 장애는 리더에 발생하는 장애보다 핸들링하기 쉽다.

둘은 같은 방식으로 핸들링 할 수 있는데 팔로워나 후보자에 장애가 발생하면 AppendEntries나 RequestVote RPC가 실패하게 될 것이다.

Raft는 이러한 장애를 계속해서 Retry를 시도하는 것으로 해결한다. 장애가 난 서버의 재시작이 끝나면 RPC가 성공할 것이다.

만약 팔로워, 후보자에 RPC가 성공했지만 응답 하기 전, 장애가 발생하면 서버의 재시작 후에 동일한 RPC를 받게 될 것이다. Raft의 RPC들은 멱등성을 지니므로(Idempotent, 연산을 여러 번 적용해도 같은 결과를 내는 성질) 이것은 문제가 되지 않는다.

타이밍과 가용성

Raft의 요구 사항 중 하나는 안정성이 타이밍에 의존하지 않아야 한다는 것이다. 시스템은 단지 특정 이벤트가 예상보다 빨리 일어났다거나 늦게 일어났다는 이유로 잘못된 결과를 내 놓지 않아야 한다.

그러나 가용성은 필연적으로 타이밍에 의존하게 된다. 예를 들어, 메세지 교환이 예상보다 오래 걸린다면 후보자들은 선출될 수 있을만큼 긴 기간 동안 살아 있을 수 없을 것이다. Raft는 안정적인 리더 없이 성립할 수 없다.

리더 선출은 Raft에서 가장 타이밍 크리티컬한 측면이다. 아래 타이밍에 관한 부등식을 만족해야만 안정적으로 리더를 선출하고 유지할 수 있다.

broadcastTime << electionTimeout << MTBF

위 부등식에서 broadcastTime은 서버가 매 다른 서버들에게 RPC 요청을 보내고 응답을 받기 까지 소요되는 평균 시간이며, MTBF (Mean Time Between Failure)는 단일 서버 장애에 발생하는 장애 간격의 평균 값이다.

broadcastTime과 MTBF가 시스템의 근본적인 성질인 반면, electionTimeout은 우리가 선택할 수 있는 값이다.

Raft의 RPC들이 전형적으로 피호출자에게 정보를 안정적 저장소(Stable store)에 저장하도록 요구하기 때문에 broadcastTime은 스토리지 기술에 따라 아마도 0.5ms에서 20ms 사이일 것이다.

결과적으로 electionTimeout 값은 10ms - 500ms 사이의 값 어딘가로 선정될 가능성이 높다.

서버 MTBF 값의 경우 전형적으로 몇 달 이상이기 때문에 위 조건을 쉽게 만족할 수 있다.

Membership changes

지금까지의 섹션들에선 클러스터의 설정이 고정되어 있다고 가정했지만 실제로는 설정을 바꿔야 할 필요가 종종 생긴다. 이 경우 전체 클러스터 내 서버들을 모두 종료하고 설정 파일을 업데이트 하고 클러스터를 재시작하면 쉽지만 이렇게 하면 업데이트 동안 클러스터가 불가용해지며, 수동으로 설정 파일들을 업데이트 하기 때문에 리스크가 존재한다.

이런 이슈들을 피하기 위해 설정 파일 변경 자동화를 Raft 합의 알고리즘의 일부로 포함시킬 수 있다.

설정 파일 업데이트 자동화를 안전하게 수행하기 위해, 업데이트가 이행되는 동안 두 개의 리더가 같은 term에서 선출되는 지점이 있으면 안 된다.

불행하게도 설정 파일을 직접 업데이트하는 어떤 접근도 안전하지 못하다. 원자적으로 모든 서버들을 한 번에 변경하는 것은 가능하지 않고, 따라서 클러스터는 업데이트 기간 동안 잠재적으로 독립적인 두 부분(Two Disjoint Majorities) 으로 나뉘게 된다.

안정성 보장을 위해 설정 업데이트는 반드시 Two-phase에 걸쳐 이뤄져야 한다. 이런 Two-phase의 구현에는 다양한 방법이 있다. 예를 들어 어떤 시스템은 첫 번째 페이즈를 구식 설정을 비활성화 하는데 사용해 클라이언트 요청을 처리할 수 없게 만들고, 두 번째 페이즈에서 새로운 설정을 활성화한다.

Raft에서 클러스터는 우선 Joint consensus라고 불리는 중간 단계의 설정으로 전환한 후, Joint consensus가 커밋된 후 새 설정으로 전이한다. Joint consensus는 구식 설정과 새 설정 양쪽을 합쳐서 구성된다.

로그 엔트리들은 양쪽 설정의 모든 서버들에 복제된다.
어느 쪽 설정의 서버든 리더로 선출될 수 있다.
리더 선출, 엔트리 커밋을 위해 구식 설정의 서버들과 새 설정의 서버들 각각은 별도의 다수의 서버들(Majority)의 합의가 필요하다.

Joint consensus는 각각의 서버들이 설정 사이를 각각 다른 시간에 안전하게 전이할 수 있도록 해 준다. 뿐만 아니라, 설정 파일 업데이트를 서비스 중단 없이 진행할 수 있게 만들어준다.

클러스터 설정은 복제된 로그에서 특별한 엔트리들을 사용해 저장되고 통신된다.

리더가 설정 파일을 변경하라는 요청을 받게 되면, Joint consensus를 위한 설정을 로그 엔트리로 저장하고 이전 섹션들에서 설명한 메커니즘을 사용하여 해당 엔트리를 복제한다.

한 번 서버가 새 설정 엔트리를 로그에 추가하고 나면, 서버는 해당 설정을 모든 미래의 결정들에 사용한다. (서버는 해당 엔트리가 커밋 되었는지 여부에 상관 없이 항상 자신의 로그의 최신 설정을 사용한다.)

이것은 리더가 Joint consensus가 커밋될 시기를 결정하기 위해, Joint consensus의 설정을 사용한다는 것을 의미한다.

(새 설정을 C_new, 구식 설정을 C_old, Joint consensus를 C_old_new라고 표현)

만약 리더에 장애가 발생하면 선출된 후보자가 C_old_new를 받았는지 여부에 따라 새로운 리더가 C_old 또는 C_old_new 내에서 선출될 수 있다.

어떤 케이스에도 C_new는 이 기간 동안 단독으로 의사 결정을 내릴 수 없다.

한 번 C_old_new가 커밋되고 나면, C_old, C_new 양쪽 모두 다른 쪽의 동의 없이 의사 결정을 내릴 수 없으며, Leader Completeness 성질에 의해 오직 C_old_new 로그를 가지고 있는 서버만 리더로 선출될 수 있다. Joint consensus가 커밋되었으니 이제 리더가 안전하게 C_new를 로그 엔트리로 만들고 클러스터에 복제할 수 있다. 해당 설정은 서버에서 발견되는대로 바로 적용된다.

C_new까지 커밋되고 나면 구식 설정은 무관한 설정으로 간주되며, 새 설정으로 업데이트 되지 않은 서버들은 종료될 수 있다.

위 그림에서 볼 수 있듯이 C_old와 C_new 모두 단독으로 의사 결정을 내릴 수 있는 시기는 존재하지 않으며, 이 점이 안정성을 보장해준다.

설정 업데이트 자동화를 위해 다루어야 하는 몇 가지 이슈들이 더 있다.

첫 번째 이슈: 초기에 새 서버들의 로그 엔트리가 비어 있는 경우

첫 번째 이슈는 새로운 서버들이 초기에 어떤 로그 엔트리들도 저장하고 있지 않을 수 있다는 점이다.

만약 이들이 이 상태로 클러스터에 추가되게 되면 이들이 동기화하는데 어느 정도 시간이 소요될 수 있으며, 이 시간 동안 새로운 로그 엔트리들을 커밋할 수 없게 된다. 불가용한 시간이 생기는 것을 막기 위해, Raft는 설정 업데이트 이전에 추가적인 페이즈를 도입한다.

이 추가적인 페이즈 동안 새로운 서버들은 클러스터에 Non-voting 멤버로서 참여하게 된다. 리더는 Non-voting 멤버들에게도 로그 엔트리들을 복제하지만, 이들의 투표는 다수파 결정에 포함되지 않는다. 새로운 서버들이 클러스터 내 다른 서버들을 따라잡고 나면 설정 업데이트가 진행될 수 있다.

두 번째 이슈: 리더가 새 설정에 포함되지 않는 경우

두 번째 이슈는 리더가 새 설정에 포함되지 않을 수 있다는 점이다. 이 경우 리더는 C_new 로그 엔트리를 커밋한 후 팔로워 상태로 돌아간다. 이것은 리더가 C_new를 커밋하는 동안 자신을 포함하지 않는 클러스터를 관리하는 기간이 있을 것임을 의미한다.

리더는 로그 엔트리들을 복제하지만 자기 자신을 다수의 서버(Majority)로 카운트 하지는 않는다. 리더의 상태 변화는 새로운 설정이 독립적으로 운용되는 첫 번째 지점인 C_new가 커밋될 때 일어날 것이다. 이 지점까지 오직 C_old에서의 서버만 리더로 선출될 수 있을지도 모른다.

세 번째 이슈: 제거된 서버들이 클러스터를 방해하는 경우

세 번째 이슈는 C_new에서 제거된 서버들이 클러스터를 방해할 수도 있다는 점이다.

이 서버들은 heartbeat를 받지 않을 것이기 때문에 타임아웃 된 후 다음 선거를 시작할 것이다. 그리고 새로운 term 값으로 RequestVote RPC를 보낼 것이고 이것은 현재 리더가 팔로워 상태로 돌아가도록 만들 것이다. 결과적으로 새로운 리더가 선출되겠지만 제거된 서버들은 다시 타임아웃을 일으킬 것이고 이 과정이 반복되면서 가용성을 떨어뜨릴 것이다.

이 문제를 방지하기 위해 서버들은 현재 리더가 존재한다고 판단될 때 RequestVote RPC를 무시한다. 특히나 서버가 현재 리더에게 Minimum election timeout 값 이전에 RequestVote RPC를 받으면 term값을 업데이트 하지도, 투표를 하지도 않는다.

이것은 각 서버들이 선거를 시작하기 전 적어도 Minimum election timeout 동안 기다리기 때문에 일반적인 선거에 영향을 끼치지 않는다.

그러나 이것은 제거된 서버들로부터의 방해를 피하도록 도와준다.

Log Compaction

Raft의 로그는 일반적으로 클라이언트 요청이 많아질수록 늘어나지만 실제 시스템에선 무한정 늘어날 수는 없다. 로그가 길어질수록 더 많은 공간을 차지할 것이고, 상태 복구(Replay)에 더 많은 시간이 소요된다.

결과적으로 축적된 로그들 중 오래된 로그들을 제거하는 메커니즘(Log Compaction) 없이는 가용성 문제가 발생하게 된다.

스냅샷

스냅샷은 Chubby, ZooKeeper 등에서 사용되는 Log Compaction에 대한 가장 간단한 접근이다. 스냅샷은 현재 전체 시스템의 상태를 안정적 저장소에 기록하고, 이전까지의 전체 로그를 버린다.

아래 그림은 스냅샷의 기본적인 아이디어를 보여준다.

각각의 서버가 독립적으로 스냅샷을 유지하고 그들의 로그에서 커밋된 엔트리들을 처리한다.

Raft는 또한 스냅샷에 작은 양의 메타 데이터를 포함시킨다.

Last included index는 스냅샷에 포함될 가장 마지막 엔트리의 index이며, Last included term은 해당 엔트리의 term 값이다.

이 값들은 스냅샷 바로 이후의 엔트리에 대한 AppendEntries 일관성 검사를 돕기 위해 저장된다.

Cluster membership change를 위해 스냅샷은 로그 안에 마지막으로 포함된 index의 최신 클러스터 구성 설정도 포함한다.

서버가 스냅샷을 모두 쓰고나면 즉시 Last included index까지의 모든 로그 엔트리들과 이전 스냅샷을 제거할 수 있다.

동기화 문제

일반적으로 서버들이 독립적으로 스냅샷을 구성하지만, 리더는 때때로 지연이 생긴 팔로워들에게 스냅샷을 보내줘야 한다. 이런 상황은 리더가 팔로워에게 보내줘야 했던 다음 엔트리를 이미 제거해버린 경우 발생한다. 운 좋게도 이런 상황이 발생할 가능성은 낮다.

리더와 동기화 된 팔로워는 이미 이 엔트리를 갖고 있을 것이다. 그러나 굉장히 느린 팔로워나 새로 클러스터에 조인된 팔로워는 그렇지 않을 수 있다.

리더는 InstallSnapshot이라는 새로운 RPC를 통해 뒤쳐진 팔로워들에게 스냅샷을 보낸다.

팔로워가 이 RPC를 받으면 기존의 로그 엔트리들을 어떻게 처리해야 할 지 결정해야 한다. 대게 이 스냅샷은 팔로워의 스냅샷엔 들어 있지 않은 새로운 정보를 갖고 있다.

이 경우 팔로워는 기존의 로그 전체를 버리게 된다. 기존의 모든 로그가 이 스냅샷에 의해 대체되며, 스냅샷과 충돌하는 커밋되지 않은 엔트리들이 있을 수도 있다.

팔로워가 수신한 스냅샷이 재전송이나 실수로 인해 팔로워 로그의 Prefix에 해당한다면 스냅샷에 포함된 로그 엔트리들은 삭제하고, 스냅샷 뒤의 항목들은 여전히 유효하므로 유지해야 한다.

정당성

이러한 스냅샷 접근은 Raft의 강한 리더 정책(Strong Leader Principle)에서 출발한다. 팔로워들이 리더의 정보를 통해 스냅샷을 생성할 수 있기 때문이다.

리더를 갖는 것은 합의 도출에서 충돌이 발생하는 것을 피하도록 도와주는 반면, 스냅샷이 생성될 때 합의는 이미 도출되어 있으므로 의사 결정 충돌은 일어나지 않는다.

데이터는 여전히 리더에서 팔로워 단방향으로 흐른다. 단지 팔로워들은 이제 그들의 데이터를 재구성할 수 있다.

우리는 리더만이 스냅샷을 생성하고 각 팔로워들에게 복제하는 리더 중심의 접근 방법도 고려해보았다. 그러나 이런 접근 방법은 두 가지 문제가 있다.

스냅샷을 각 팔로우들에게 모두 보내는 것은 네트워크 대역폭을 낭비하며 스냅샷 절차를 느려지게 만든다. 각 팔로워들은 이미 스냅샷을 생성하기 위한 그들만의 정보를 갖고 있으며, 일반적으로 리더가 로컬에 스냅샷을 생성하는 비용이 네트워크를 거쳐 스냅샷을 전달하는 비용보다 싸다.
리더의 구현이 더 복잡해진다. 리더는 새로운 엔트리들을 복제하는 것과 동시에 그들에게 스냅샷을 보내야 한다.

성능 이슈

스냅샷 성능에 영향을 끼치는 두 개의 요소가 더 있다.

서버들은 언제 스냅샷을 생성할 것인지 결정해야 한다. 만약 너무 자주 스냅샷을 생성한다면 디스크 대역폭과 에너지를 낭비하게 되며, 반대로 스냅샷을 너무 가끔 생성하는 경우 스토리지 용량이 소진될 위험이 있고 로그를 재현(Replay)할 때 필요한 시간이 늘어나게 된다. 간단한 전략으로 로그 크기가 특정 바이트 수에 도달했을 때 스냅샷을 생성하는 방법이 있다. 만약 이 크기가 스냅샷의 예상되는 크기보다 좀 더 크게 설정된다면 스냅샷 생성을 위한 디스크 대역폭 오버헤드는 줄어들 것이다.
두 번째 성능 이슈는 스냅샷 생성이 상당한 양의 시간을 소요한다는 것이다. 우리는 스냅샷 생성이 다른 연산을 지연시키는 것을 원하지 않는다. Copy-On-Write 전략을 사용하여 생성 중인 스냅샷에 영향을 끼치지 않고 새로운 업데이트들을 적용할 수 있다. 함수형 자료구조를 통해 설계한 상태 머신의 경우 본질적으로 Copy-On-Write 전략을 지원한다. 그 대안으로 OS 시스템의 Copy-On-Write 지원을 이용해 전체 상태 머신의 인메모리 스냅샷을 생성할 수도 있다.

다른 접근법

Compaction에 대한 접근으로서 Log-cleaning, Log-Structured Merge trees (LSM)와 같은 방법도 사용할 수 있다. 이들은 언제나 전체 데이터 셋에 대해 작동하는 스냅샷에 비해 더 복잡한 메커니즘을 요구한다.

Log-cleaning은 Raft 구현의 수정을 요구하는 반면 LSM은 상태 머신으로 스냅샷과 동일한 인터페이스를 사용해 구현할 수 있다.

클라이언트와의 상호 작용

이 섹션에서는 Raft가 어떻게 선형화 가능한 시맨틱(Linearizable semantic)을 지원하는지 설명한다. 이 이슈들은 모든 합의 기반의 시스템들에도 적용되며 Raft의 솔루션도 다른 시스템들과 비슷하다.

Raft 클라이언트들은 모든 요청을 리더에게 보낸다. 클라이언트가 처음 시작되었을 땐 무작위로 선정한 서버에 연결한다. 만약 무작위로 선정된 서버가 리더가 아니라면 해당 서버는 그 요청을 거절할 것이고, 서버가 알고 있는 가장 최신의 리더가 누구인지에 대한 정보를 전해줄 것이다. 만약 리더에 장애가 발생하면 클라이언트 요청은 타임 아웃될 것이고 클라이언트들은 다시 무작위로 서버를 선정해 연결을 요청할 것이다.

Raft의 목표 중 하나는 선형화 가능한 시맨틱(각 연산이 호출과 응답 사이 어느 지점에서 정확히 한 번 즉시 실행 되는 것처럼 보이는 것)을 구현하는 것이다. 그러나 여태까지 설명한 것처럼 Raft는 같은 명령을 여러 번 실행할 수 있다 (멱등성). 예를 들어 로그 엔트리를 커밋했으나 클라이언트에 응답하기 전에 리더에 장애가 발생하면, 클라이언트는 새 리더에게 Retry 요청을 보낼 것이고 이것은 같은 명령이 중복되어 실행될 수 있다는 것을 의미한다.

해결책은 클라이언트가 명령마다 고유한 시리얼 번호를 배정해 주는 것이다. 그런 다음 상태 머신은 클라이언트마다 처리된 가장 최신의 시리얼 번호를 추적한다. 이미 실행된 시리얼 넘버의 명령을 받는 경우 해당 요청을 실행하지 않고 즉시 반환해 명령이 중복되어 실행되지 않게 한다.

읽기 전용 연산들은 로그에 아무것도 쓰지 않고 수행될 수 있지만 이들은 추가적인 조치 없이는 오래된 데이터를 반환할 위험이 있다.

요청에 응답하는 리더가 모르는 사이에 새 리더로 교체 되었을 수 있기 때문이다. 선형화 가능한 읽기(Linearizable reads) 명령은 구식 데이터를 반환하지 않아야 한다.

Raft는 로그를 쓸 필요 없이 이것을 보장하기 위해 아래 두 가지 추가적인 예방 조치(Precaution)를 필요로 한다.

리더는 어떤 엔트리들이 커밋되었는지에 대한 최신 정보를 갖고 있어야 한다. Leader Completeness는 리더가 모든 커밋된 엔트리들을 갖고 있다는 것을 보장해주지만, 그 term의 시작 부분에 커밋된 엔트리들이 누구인지 모를 수 있다. Raft는 이 문제를 각 리더가 no-op 엔트리를 로그의 term의 시작 부분에 커밋함으로써 해결한다.
리더는 읽기 전용 요청을 처리하기 전에 해당 요청이 폐기된 요청인지 확인해야 한다. (새로운 리더가 선출되었을 경우 해당 요청은 폐기되어야 한다.) Raft는 이것을 리더가 읽기 전용 요청에 응답하기 전 heartbeat 메세지를 클러스터 내 다수의 서버들(Majority)과 교환하게 만들어 처리한다.

Raft 알고리즘 구현

상태 (States)

모든 서버들의 persisted 상태

아래 상태들은 RPC에 응답하기 전 안정적 저장소에 업데이트 된다.

currentTerm: 서버가 관측했던 가장 최신의 term값.
votedFor: currentTerm에서 투표한 후보자의 Id. 없는 경우 null.
log[]: 로그 엔트리들의 배열. 각 로그 엔트리들은 상태 머신을 위한 명령 및 엔트리가 리더에게 수신되었을 때의 term 값을 포함하고 있다.

모든 서버들의 휘발성(volatile) 상태

commitIndex: 커밋된 것으로 알려진 로그 엔트리들 중 가장 높은 index 값.
lastApplied: 상태 머신에 적용된 로그들 중 가장 높은 index 값.

리더의 휘발성(volatile) 상태

아래 상태들은 리더 선거 이후 다시 초기화 된다.

nextIndex[]: 각각의 서버들에 대해 다음에 보내줘야 하는 로그 엔트리의 index 값들.
matchIndex[]: 각각의 서버들에 대해 복제된 것으로 알려진 가장 높은 로그 엔트리의 index 값들.

서버들을 위한 규칙

모든 서버들

commitIndex > lastAppied인 경우, lastApplied를 증가시키고 상태 머신에 log[lastApplied]를 적용한다.
RPC 요청이나 응답에 포함된 term 값이 currentTerm보다 높은 경우, currentTerm을 term 값으로 설정하고 팔로워 상태로 돌아간다.

팔로워

후보자와 리더들의 RPC에 응답한다.
Election timeout 시간 동안 리더와 후보자에게 AppendEntries 요청을 받지 못한 경우 후보자가 된다.

후보자

후보자로 전환되면 아래 절차를 거쳐 선거를 시작한다.
1. currentTerm을 증가시킨다.
2. 자기 자신에게 투표한다.
3. Election timer를 초기화한다.
4. 다른 모든 서버들에게 RequestVote RPC를 보낸다.
다수의 서버들에게 투표를 받게 되면 리더가 된다.
리더에게 AppendEntries RPC를 받게 되면 팔로워가 된다.
Election timer가 만료되면 새 투표를 시작한다.

리더

선거를 마치자마자 각 서버들에게 비어 있는 AppendEntries RPC를 호출하고, Idle 상태일 동안 Election timeout을 막기 위해 지속적으로 heartbeat을 보낸다.
만약 클라이언트에게 명령을 받게 되면 엔트리를 로컬 로그에 추가하고, 상태 머신에 엔트리를 적용한 후 응답한다.
nextIndex[] 배열을 순회하며 last log index >= nextIndex인 팔로워들에 대해 nextIndex에서 시작하는 로그 엔트리들의 배열을 entries 인자에 넘겨 AppendEntries RPC를 호출한다. 성공하는 경우 해당 팔로워의 nextIndex, matchIndex를 업데이트 한다. 만약 AppendEntries가 로그 비일관성으로 인해 실패한다면 nextIndex를 낮추고 Retry 요청을 보낸다.
N > commitIndex, 대다수 서버들(Majority)에 대해 matchIndex >= N, log[N].term == currentTerm을 만족하는 N이 존재하는 경우, commitIndex에 N을 대입한다.

AppendEntries RPC

AppendEntries는 로그 엔트리들을 복제하기 위해 리더에 의해 호출되며 heartbeat 목적으로도 사용된다.

AppendEntries 인자 (Arguments)

term: 리더의 term 값.
leaderId: 리더에게 요청을 리다이렉트 할 수 있도록 전달해주어야 하는 리더의 Id.
prevLogIndex: 새 로그 엔트리 바로 앞 index.
prevLogTerm: 새 로그 엔트리 바로 앞 엔트리(prevLogIndex의 엔트리)의 term 값.
entries[]: 저장할 로그 엔트리들. (heartbeat인 경우 빈 배열)
leaderCommit: 리더의 commitIndex 값.

AppendEntries 리턴 값 (Results)

term: 리더를 업데이트 하기 위한 currentTerm 값.
success: 팔로워가 prevLogIndex, prevLogTerm에 매칭되는 엔트리를 포함할 경우 True.

AppendEntries 메시지 수신부 구현

term < currentTerm 인 경우 False를 리턴.
prevLogIndex의 로그 엔트리가 prevLogTerm에 매칭되지 않는 경우 False를 리턴.
기존의 엔트리가 새로운 엔트리와 충돌(index 값이 같은데 term 값이 다른 경우)을 일으키는 경우, 기존의 엔트리를 지운다.
기존 로그에 존재하지 않는 모든 새 엔트리들을 추가한다.
leaderCommit > commitIndex인 경우 commitIndex 값을 min(leaderCommit, 새 엔트리의 인덱스)값으로 정한다.

RequestVote RPC

RequestVote는 투표를 위해 후보자에 의해 호출된다.

RequestVote 인자 (Arguments)

term: 후보자의 term 값.
candidateId: 투표를 요청하는 후보자의 id.
lastLogIndex: 후보자의 마지막 로그 엔트리의 index.
lastLogTerm: 후보자의 마지막 로그 엔트리의 term 값.

RequestVote 리턴 값 (Results)

term: 후보자를 업데이트 하기 위한 currentTerm 값.
voteGranted: 후보자가 표를 받았다면 True.

RequestVote 메시지 수신부 구현

term < currentTerm 인 경우 False를 리턴.
만약 votedFor이 null이거나 candidateId이라면 후보자의 로그는 적어도 수신자의 로그와 업데이트된 상태이며, 투표한다.

InstallSnapshot RPC

InstallSnapshot은 스냅샷 청크들을 팔로워에게 보내기 위해 리더에 의해 호출된다.

InstallSnapshot 인자 (Arguments)

term: 리더의 term 값.
leaderId: 리더에게 요청을 리다이렉트 할 수 있도록 전달해주어야 하는 리더의 Id.
lastIncludedIndex: 해당 index까지 스냅샷으로 생성.
lastIncludedTerm: lastIncludedIndex에 해당하는 엔트리의 term 값.
offset: 스냅샷 파일 청크가 위치하는 바이트 오프셋.
data: 오프셋으로부터 시작하는 스냅샷 청크의 raw bytes.
done: 이 청크가 마지막 청크인 경우 True.

InstallSnapshot 리턴 값 (Results)

term: 리더를 업데이트 하기 위한 currentTerm 값.

InstallSnapshot 메시지 수신부 구현

term < currentTerm인 경우 즉시 응답.
만약 첫 번째 청크라면 (오프셋이 0) 새 스냅샷을 생성.
주어진 오프셋에서 스냅샷으로 데이터를 씀.
응답하고, 만약 done이 False인 경우 더 많은 데이터 청크를 기다림.
스냅샷을 저장. 기존에 존재하는 index가 작은 부분들은 모두 삭제.
기존 로그 엔트리의 index 및 term이 스냅샷의 index 및 term과 동일하다면 로그에 마지막으로 포함된 엔트리와 해당 엔트리 뒤의 로그 엔트리들을 유지하고 응답.
전체 로그를 삭제.
스냅샷을 사용해 상태 머신을 리셋. (그리고 스냅샷의 클러스터 설정을 로드)

평가

우리는 Raft를 RAMCloud의 구성 정보 저장 및 RAMCloud 코디네이터의 장애 조치를 지원하는 복제 상태 기계의 일부로 구현했다. Raft 구현은 테스트, 주석 또는 공백 줄을 제외하고 대략 2000줄의 C++ 코드로 구성된다. 소스 코드는 무료로 제공된다. 또한, 이 논문의 초안을 바탕으로 다양한 개발 단계에 있는 약 25개의 독립적인 타사 오픈 소스 Raft 구현이 있다. 여러 회사들도 Raft 기반 시스템을 배포하고 있다.

이 절의 나머지 부분에서는 Raft를 이해도, 정확성 및 성능의 세 가지 기준으로 평가한다.

이해 가능성

Raft의 이해 가능성을 Paxos와 비교하기 위해, 우리는 Stanford University의 고급 운영 체제 과정과 UC Berkeley의 분산 컴퓨팅 과정에 참여한 상급 학부생 및 대학원생을 대상으로 실험 연구를 진행했다. Raft와 Paxos에 대한 비디오 강의를 녹화하고 해당 강의에 대한 퀴즈를 만들었다. Raft 강의는 로그 컴팩션을 제외한 이 논문의 내용을 다루었다.

Paxos 강의는 단일 명령 Paxos, 다중 명령 Paxos, 재구성 및 실제로 필요한 리더 선출 등 몇 가지 최적화를 포함하여 동등한 복제 상태 기계를 만들기 위한 충분한 자료를 다루었다. 퀴즈는 알고리즘에 대한 기본 이해를 테스트하고 학생들이 예외적인 경우에 대해 논리적으로 사고할 것을 요구했다. 각 학생은 한 개의 비디오를 시청한 후 해당 퀴즈를 보고, 두 번째 비디오를 시청한 후 두 번째 퀴즈를 보았다. 참가자의 절반은 Paxos 파트를 먼저 수행했고, 나머지 절반은 Raft 파트를 먼저 수행하여 개개인의 성능 차이와 첫 번째 파트에서 얻은 경험을 모두 고려했다. 우리는 참가자들이 Raft를 더 잘 이해했는지 여부를 판단하기 위해 각 퀴즈의 점수를 비교했다.

Paxos와 Raft 간의 비교를 최대한 공정하게 만들기 위해 노력했다. 실험은 두 가지 방식으로 Paxos에 유리하게 진행되었다. 43명의 참가자 중 15명이 Paxos에 대한 사전 경험이 있었고, Paxos 비디오는 Raft 비디오보다 14% 길었다. 표 1에 요약된 것처럼, 우리는 잠재적인 편향 원인을 완화하기 위해 여러 조치를 취했다. 우리의 모든 자료는 검토를 위해 공개되어 있다.

평균적으로, 참가자들은 Raft 퀴즈에서 Paxos 퀴즈보다 4.9점 더 높은 점수를 얻었다 (60점 만점 중, Raft의 평균 점수는 25.7점, Paxos의 평균 점수는 20.8점이었다); 개별 점수는 그림 14에 나와 있다. 짝을 이룬 t-검정 결과, 95%의 신뢰 수준에서 Raft 점수의 실제 분포가 Paxos 점수의 실제 분포보다 평균적으로 최소 2.5점 더 높다고 결론지을 수 있다.

우리는 또한 새로운 학생의 퀴즈 점수를 예측하기 위해 세 가지 요소에 기반한 선형 회귀 모델을 만들었다: 어떤 퀴즈를 봤는지, Paxos에 대한 사전 경험 정도, 그리고 알고리즘을 학습한 순서를 포함한 세 가지 요소를 기반으로 새로운 학생의 퀴즈 점수를 예측하는 선형 회귀 모델도 만들었다. 이 모델은 퀴즈 선택이 Raft에 유리한 12.5점의 차이를 만든다고 예측한다. 실제 관찰된 차이인 4.9점보다 훨씬 높게 나타나는데, 이는 실제 학생들 중 많은 이들이 Paxos에 대한 사전 경험이 있었기 때문이다. 이 경험이 Paxos에는 상당히 도움이 되었고, Raft에는 상대적으로 약간 덜 도움이 되었다. 흥미롭게도, 모델은 Paxos 퀴즈를 이미 본 사람들의 Raft 점수가 6.3점 낮아질 것이라고 예측한다. 그 이유는 알 수 없지만, 이는 통계적으로 유의미한 것으로 보인다.

우리는 또한 퀴즈 후 참가자들에게 어떤 알고리즘이 구현하거나 설명하기 더 쉬울 것이라고 느끼는지 설문조사를 실시했다. 이 결과는 아래 그림에 나와 있다. 압도적인 다수의 참가자들이 Raft가 구현하고 설명하기 더 쉬울 것이라고 보고했다(각 질문에 대해 41명 중 33명). 그러나 이러한 감정은 참가자들의 퀴즈 점수만큼 신뢰할 수 없으며, 참가자들은 Raft가 이해하기 더 쉽다는 우리의 가설을 알고 편향될 수도 있다.

정확성

우리는 Raft 합의 메커니즘에 대해 공식 명세와 안전성 증명을 개발했다. 공식 명세서는 TLA+ 명세 언어를 사용하여 그림 2에서 요약된 정보를 완전히 정확하게 만들었다. 이 명세서는 약 400줄 분량으로 정확성을 증명하기 위해 사용되며, Raft를 구현하는 누구에게나 유용하다. 우리는 TLA 증명 시스템을 사용하여 Log Completeness 속성을 기계적으로 증명했다. 그러나 이 증명은 기계적으로 확인되지 않은 불변성에 의존한다 (예를 들어, 명세의 타입 안전성을 증명하지는 않았다).

또한 우리는 State Machine Safety에 대한 비공식적인 증명서를 작성했으며, 이는 완전한 것으로 (명세에만 의존한다) 간주되며 상대적으로 정확하다. (3500 단어 정도의 길이)

성능 측정

Raft에서의 성능은 Paxos 같은 다른 합의 알고리즘과 유사하게 이뤄진다. 가장 눈여겨봐야 할 것은 새 리더가 새로운 로그 시퀸스를 복제할 때다. Raft는 최소한의 메시지 수(리더에서 클러스터의 절반까지의 단일 왕복)를 사용하여 이를 달성한다. 또한 Raft의 성능을 더욱 향상시킬 수도 있다.

예를 들어, 더 높은 처리량과 더 낮은 지연 시간을 위해 요청을 배치 및 파이프라인 처리할 수 있다. 다른 알고리즘에 대해 제안된 다양한 최적화가 있으며, 이들 중 많은 것을 Raft에 적용할 수 있지만, 이는 향후 작업으로 남겨둔다. 우리는 Raft의 리더 선출 알고리즘의 성능을 측정하고 아래 두 가지 질문에 답하고자 했다.

리더 선출 프로세스에 어느 정도의 시간이 소요되는가?
리더가 충돌한 후 최소 다운타임은 얼마인가?

우리는 다섯 대의 서버로 구성된 클러스터의 리더를 반복적으로 충돌시키고, 충돌을 감지하여 새로운 리더를 선출하는 데 걸리는 시간을 측정했다(그림 16 참조).

상단 그래프는 election_timeout의 무작위성 정도, 하단 그래프는 최소 election_timeout에 따른 리더 선출에 걸리는 시간을 나타낸다. 각 선은 1000번의 실험(“150–150ms”는 100번의 실험)을 나타내며, 특정 election_timeout에 해당한다. 예를 들어, “150–155ms”는 election_timeout이 150ms에서 155ms 사이에서 무작위로 선택되었음을 의미한다. 측정은 약 15ms의 브로드캐스트 시간을 가진 다섯 대의 서버 클러스터에서 이루어졌다. 아홉 대의 서버 클러스터에 대한 결과도 유사하다.

최악의 시나리오를 만들기 위해, 각 실험에서 서버들은 모두 서로 다른 로그 길이를 가지고 있었으며, 이로 인해 일부 후보는 리더가 될 자격이 없었다.

또한, Split vote를 유도하기 위해, 테스트 스크립트는 리더 프로세스가 종료되기 전에 하트비트 RPC를 브로드캐스팅해 동기화되도록 유도했다. (이는 리더가 충돌 전에 새로운 로그 엔트리들을 복제하는 동작을 근사화한 것이다).

리더는 하트비트 간격 내에서 균일하게 무작위로 충돌시켰으며, 이는 모든 테스트에서 최소 election_timeout의 절반이었다. 따라서 가능한 최소 다운타임은 최소 선거 타임아웃의 절반 정도였다.

그림 16의 상단 그래프는 election_timeout에 약간의 무작위성을 추가하는 것만으로도 선거에서 Split vote를 피할 수 있음을 보여준다. 무작위성이 없을 경우, 많은 Split vote로 인해 리더 선출에는 일관되게 10초 이상이 걸렸다. 5ms의 무작위성을 추가하는 것만으로도 상당한 개선이 이루어져, 다운타임의 중앙값은 287ms였다. 더 많은 무작위성을 사용하면 최악의 경우도 개선된다. 50ms의 무작위성을 사용할 경우 최악의 완료 시간(1000번의 시험 중)은 513ms였다.

그림 16의 하단 그래프는 election_timeout을 줄임으로써 다운타임을 줄일 수 있음을 보여준다.

12–24ms의 선거 타임아웃을 사용할 경우, 리더를 선출하는 데 평균적으로 35ms밖에 걸리지 않았으며, 가장 긴 시험도 152ms가 걸렸다. 그러나 타임아웃을 이보다 더 낮추면 Raft의 타이밍 요구 사항을 위반하게 된다. 리더는 다른 서버가 새로운 선거를 시작하기 전에 하트비트를 브로드캐스트하는 데 어려움을 겪게 되며, 이는 불필요한 리더 교체를 초래하고 전체 시스템 가용성을 낮출 수 있다.

우리는 election_timeout을 150–300ms와 같은 보수적인 값으로 사용할 것을 권장한다. 이러한 타임아웃은 불필요한 리더 교체를 초래하지 않으면서도 여전히 높은 가용성을 제공할 가능성이 크다.

결론

알고리즘은 종종 정확성, 효율성 및 간결성을 주요 목표로 설계된다. 이러한 목표들이 모두 가치 있는 목표이지만, 우리는 이해 가능성 또한 이것들만큼이나 중요하다고 믿는다. 이해 가능성 외의 다른 목표들은 개발자들이 알고리즘을 실질적인 구현으로 전환하기 전까지 달성될 수 없으며, 구현체는 불가피하게 처음 발표된 형태에서 벗어나고 확장될 것이다. 개발자들의 알고리즘에 대한 깊은 이해와 직관 없이는 구현 과정에서 알고리즘의 바람직한 특성을 유지하기 어려울 것이다.

이 논문에서 우리는 분산 합의 문제를 다루었다. 오랫동안 학생들과 개발자들을 어렵게 했던 널리 받아들여진 알고리즘인 Paxos에 도전했다. 우리는 새로운 알고리즘인 Raft를 개발했으며, Paxos보다 더 이해하기 쉽다는 것을 보여주었다. 또한 Raft가 시스템 구축을 위한 더 나은 기초를 제공한다고 믿는다.

이해 가능성을 주요 설계 목표로 삼음으로써 Raft의 설계 접근 방식이 바뀌었다. 설계가 진행되면서 문제를 분해하고 상태 공간을 단순화하는 몇 가지 기술을 반복적으로 사용하게 되었다. 이러한 기술은 Raft의 이해 가능성을 향상시켰을 뿐만 아니라, Raft의 정확성을 확신하는 데도 더 쉽게 만들었다.