Raft 알고리즘 논문 번역

Raft는 Reliable(신뢰성), Replicated(복제성), Redundant(중복성), And Fault-Tolerant(내장애성)에서 명명 되었으며, 분산 시스템에서 전체 노드의 동기화, 내결함성(False Tolerance)을 동시에 구현하기 위해 만들어진 합의 알고리즘의 한 종류이다. 분산 시스템을 이해하려면 알아야할 중요한 포인트이기도 하다. 여기에서는 Raft 알고리즘을 이해하는데 도움이 되는 “In Search of an Understandable Consensus Algorithm”이라는 논문에 소개한 Raft 합의 알고리즘을 번역해서 이해를 돕고자 한다.

소개

합의 알고리즘은 여러 머신이 구성원 중 일부의 실패에도 살아남을 수 있는 일관된 그룹으로 작동할 수 있도록 한다. 이 때문에 신뢰성이 높은 대규모 소프트웨어 시스템을 구축하는데 핵심적인 역할을 한다. Paxos는 지난 10년간의 합의 알고리즘 논의를 지배해 왔으며, 대부분의 합의 구현은 Paxos를 기반으로하거나 Paxos에 영향을 받았으며 Paxos는 학생들에게 합의 알고리즘을 가르치는 주요 수단이 되었다.

그러나 불행히도 Paxos는 접근성을 높이기 위한 수많은 시도에도 불구하고 이해하기가 너무 어렵다. 또한, 아키텍처는 실제 시스템을 지원하기 위해서는 복잡한 변경이 필요하다. 그 결과 시스템 구축자와 학생 모두Paxos를 사용하는 데 어려움을 겪었다.

Paxos를 직접 사용해본 후 우리는 시스템 구축과 교육을 위한 더 나은 기반을 제공할 수 있는 새로운 합의 알고리즘을 모색하기 시작했다. 주요 목적이 이해도를 높인다는 점에서 우리의 접근법은 독특했다. 실용적인 시스템을 위해 합의 알고리즘을 정의하고 Paxos보다 훨씬 쉽게 이해할 수 있는 방법으로 설명 할 수 있나요? 더 나아가, 우리는 이 알고리즘이 시스템 구축자에게 필수로 직관적 개발을 촉진하기를 원했다. 알고리즘이 작동하는 것뿐만 아니라 그것이 작동하는 이유를 명확히 보여주는 것도 중요했다.

이 연구의 결과는 Raft라는 합의 알고리즘이다. Raft의 설계에서는 이해도를 높이기 위해 분해(Raft는 리더 선출, 로그 복제 및 안전성을 분리함)나 공간 상태의 축소(Raft는 Paxos에 비해 비결정성의 정도와 서버간 불일치를 줄이고 있음) 등을 적용했다. 두 대학의 43명의 학생을 대상으로 한 사용자 조사는 Paxos보다 Raft가 훨씬 이해하기 쉽다는 것을 발견했다.

Raft는 많은면에서 기존의 합의 알고리즘(특히 Oki, Liskov의 Viewstamped Replication)과 비슷하지만 몇가지 새로운 기능이 있다.

• 강력한 리더 : Raft는 다른 합의 알고리즘보다 강력한 리더십을 사용한다. 예를 들어 로그 항목은 리더에서 다른 서버로만 흐른다. 이렇게하면 복제된 로그를 쉽게 관리할 수 ​​있으며 Raft를 쉽게 이해할 수 있도록 한다.
• 리더 선츨 : Raft은 리더를 선출하기 위하여 무작위 타이머를 이용한다. 이것은 기존의 컨센서스 알고리즘에서도 필요한 heartbeat에 극히 작은 메커니즘을 추가하는 것만으로 충돌을 쉽고 빠르게 해결한다.
• 멤버십 변경 : Raft 메커니즘은 클러스터의 서버 세트를 변경하기 위해 마이그레이션 중에 두개의 서로 다른 구성의 대부분이 중복되는 새로운 연결 합의(joint consensus) 접근법을 사용한다. 이렇게 하면 클러스터가 구성 변경중에도 정상적으로 계속 작동 할 수 있다.

Raft는 교육 목적과 구현의 기초로서 Paxos 및 기타 합의 알고리즘보다 우수하다고 생각한다. 다른 알고리즘보다 간단하고 이해하기 쉽고 실제 시스템의 요구를 충족할 만큼 충분히 설명되어 있다. 오픈 소스 구현이 몇가지 존재하고 일부 기업에서 사용되고 있으며, 그 안전성은 공식적으로 확인되고 입증되었다. 그리고 효율성은 다른 알고리즘과 유사하다.

Replicated state machines(복제 상태 머신)

복제 상태 머신(Replicated state machines)은 분산 시스템에서 다양한 내결함성 문제를 해결하는데 사용된다. 예를 들어 GFS, HDFS, RAMCloud와 같은 단일 클러스터 리더가 있는 대규모 시스템은 일반적으로 리더 선출을 관리하고 리더 충돌후에도 지속되어야 하는 구성 정보를 저장하기 위해 다른 복제 상태 시스템을 사용한다. 복제 상태 머신의 예로는 Chubby와 ZooKeeper가 있다.

복제 상태 머신은 복제된 로그를 사용하여 구현된다. 각 서버는 상태 머신이 순서대로 실행하는 일련의 명령을 포함하는 로그를 저장한다. 각 로그에는 동일한 명령이 동일한 순서로 포함되므로 각 상태 머신은 동일한 명령 시퀀스를 처리한다. 상태 머신은 결정론적이기 때문에 각각이 동일한 상태와 함께 출력 시퀀스를 계산한다.

복제된 로그의 일관성을 유지하는 것이 합의 알고리즘의 작업이다. 서버의 consensus modules은 클라이언트로부터 명령을 수신하여 로그에 추가한다. 다른 서버의 컨센서스 모듈과 통신하여 일부 서버에서 장애가 발생하더라도 결국 모든 로그에 동일한 요청이 동일한 순서로 포함되도록 한다. 명령이 올바르게 복제되면 각 서버의 상태 머신은 로그 순서대로 처리하고 그 출력이 클라이언트로 반환된다. 결과적으로 여러 서버는 하나의 서버처럼 동작하고, 높은 신뢰성을 가진 상태 머신이 된다.

현실적인 시스템을 위한 Consensus algorithm은 다음과 같은 특징을 갖는다:

• 네트워크 지연, 파티션 분할, 패킷 손실, 중복, 정렬 등 모든 비 비잔틴 상황에서 **(안전성)**을 보장한다(잘못된 결과가 반환되지 않음).
• 대부분의 서버가 구동중이며 클라이언트와 상호 작용할 수 있는 한 이들은 완전히 작동한다**(가용성)**. 즉, 5대의 서버로 구성된 일반적인 클러스터 구성에서 2대의 서버 장애를 견딜 수 있다. 서버가 중지되면 실패한다고 가정한다. 이들은 나중에 안정된 저장 장치의 상태로부터 복구되고 다시 클러스터에 참여할 수 있다.
• 로그 일관성을 보장하기 위해 타이밍에 의존하지 않는다: 불완전한 시계와 극단적인 메시지 지연은 최악의 경우 가용성 문제를 일으킬 수 있다.
• 일반적인 경우에는 대부분의 클러스터가 한번의 원격 프로시저 호출에 응답하자마자 명령이 완료된다. 소수의 느린 서버가 전체 시스템 성능에 영향을 미치지 않는다.

이해하기 쉬운 설계

Raft의 설계에는 몇가지 목표가 있다: 시스템 구축을 위한 완전하고 실용적인 기반(Paxos 알고리즘은 그렇지 못함)을 제공해야 하기 때문에 개발자에게 요구되는 설계 작업을 대폭 줄여야 한다; 그러나 우리의 가장 중요한 목표, 그리고 가장 어려운 과제는 이해하기 쉬움(understandability) 이었다. 많은 사람들이 알고리즘을 편안하게 이해할 수 있어야 한다. 또한, 시스템 구축자가 실제 구현에서 불가피한 확장을 할 수 있도록 알고리즘을 직관적으로 개발을 할 수 있어야 한다.

Raft의 설계에는 대안적인 접근방법들 중에서 선택해야 하는 점이 많았다. 이러한 상황에서 우리는 이해의 용이성을 바탕으로 선택 사항을 평가했다. 각 옵션을 설명하는 것은 얼마나 어려운가?

이러한 분석에는 높은 주관성이 존재한다는 것을 우리는 인식하고 있다; 그럼에도 불구하고, 우리는 일반적으로 적용가능한 두가지 기법을 사용하였다. 첫번째 접근법은 잘 알려진 문제 분해 접근법이다. 가능한 한 개별적으로 해결, 설명 및 이해할 수 있도록 우리는 문제를 가능한 한 별도의 부분으로 나누었다. 예를 들어 Raft에서는 리더 선출(leader election), 로그 복제(log replication), 안전성(safety), 멤버십 변경(membership change)을 분할했다. 두번째 접근법은 고려해야 할 상태의 수를 줄이고 시스템을 더 일관성 있게 만들고 가능한 경우 비결정성을 제거하여 상태 공간을 단순화하는 것이다. 구체적으로는, 일련의 로그에는 구멍이 생기는 것이 허용되지 않고, Raft는 로그가 서로 모순될 가능성이 있는 방법을 제한했다. 대부분의 상황에서 우리는 비결정성을 제거하려고 시도했지만, 그 비결정성이 실제로 이해 가능성을 개선하는 몇가지 상황이 있었다. 특히, 랜덤화된 접근법에서는 비결정성이 도입되고 있지만, 이들은 모든 가능한 선택사항을 똑같이 취급함으로써(어떤 것을 선택해도 변함없다) 상태 공간을 단순화할 수 있다. Raft의 리더 선출 알고리즘을 단순화하기 위해 우리는 무작위화를 사용한다.

Raft consensus algorithm

Raft는 먼저 리더를 선출하고 복제된 로그 관리에 대한 완전한 책임을 그 리더에게 부여하는 식으로 합의 알고리즘을 구현한다. 리더는 클라이언트로부터 로그 엔트리를 수신하고, 이들을 다른 서버로 복제하고, 각 서버의 상태 머신에 로그 엔트리를 적용해도 안전한 시점에 서버에 통지한다. 리더를 가지는 것은 복제된 로그의 관리가 단순해 진다. 예를 들어 리더는 다른 서버에 상의하지도 않고 로그의 새 엔트리를 어디에 배치할지 결정할 수 있으며 데이터는 리더에서 다른 서버로 간단한 방식으로 전송된다. 리더에 장애가 나거나, 다른 서버와 연결이 끊어질 경우 새로운 리더가 선출된다.

리더 접근법을 고려하면 Raft는 합의 문제를 세가지 비교적 독립적인 하위 문제로 분해할 수 있다. 이들은 아래의 서브 섹션에서 설명한다.

• Leader election(리더 선출) : 기존 리더가 실패하면 새로운 리더가 선출되어야 한다.
• Log replication(로그 복제) : 리더는 클라이언트로부터 로그 엔트리를 받고 클러스터 전체에 복제하고 다른 로그를 자신의 로그 엔트리와 일치시켜야 한다.
• Safety(안전) : Raft의 중요한 안전은 State Machine Safety Property이다. 특정 로그 엔트리가 그 상태 머신에 적용되는 서버가 존재하는 경우, 다른 서버는 동일한 로그 인덱스에 대해 다른 명령을 적용할 수 없다.

Raft consensus algorithm의 중요한 특성은 아래와 같다.

• Election Safety : 주어진 기간 내에서 선출되는 리더는 한 명까지.
• Leader Append-Only : 리더는 로그의 엔트리을 덮어 쓰거나 삭제하지 않는다. 새 엔트리를 덮어쓴다.
• Log Matching : 2개의 로그에 같은 인덱스와 기간의 엔트리가 포함되어 있는 경우, 로그는 지정된 인덱스까지의 모든 엔트리에서 동일하다.
• Leader Completeness : 주어진 기간안에 로그 엔트리가 커밋되면 모든 엔트리 중 더 높은 등급의 기간을 가진 리더로 로그에 표시된다.
• State Machine Safety : 서버가 그 상태 머신에 특정 인덱스의 로그 엔트리를 적용했을 경우, 다른 서버가 같은 인덱스에 대해서 다른 로그 엔트리를 적용하는 것은 결코 없다.

1. Raft 기초

Raft 클러스터에는 여러대의 서버가 포함되어 있으며, 5대는 일반적인 수이며, 시스템은 2대까지의 장애를 허용할 수 있다. 각 서버는 항상 leader(리더), follower(팔로워), candidate(후보자)의 세가지 상태 중 하나이다. 보통의 운영에서는 리더는 1개만으로, 다른 모든 서버는 팔로워이다. 팔로워는 수동적이다: 그들은 스스로 요청을 발행하지 않으며 단지 리더와 후보자의 요청에 응답한다. 리더는 모든 클라이언트 요청을 처리한다(팔로어가 클라이언트 요청을 받으면 팔로어는 리더로 리디렉션한다). 세번째 상태인 후보자는 새로운 지도자를 선출하는 데 사용된다.

Raft는 위와 같이 시간을 임의의 길이의 기간으로 나눈다. 기간은 연속적인 정수로 번호가 매겨진다. 각 기간은 선거에서 시작하여 선거에서는 하나 이상의 후보자가 지도자가 되려고 시도한다. 상황에 따라 이 선거는 분할 투표(split vote)가 이루어질 수 있다. 이 경우 기간은 리더없이 끝나고 새로운 기간(새 선거)이 신속하게 시작된다. Raft는 주어진 기간에 최대 1명의 지도자가 있다는 것을 보증한다.

다른 서버에서 다른 타이밍에서 기간 간 전환을 관찰할 수 있으며 경우에 따라 서버는 선거 또는 전체 기간을 관찰을 못할 수도 있다. 기간은 Raft에서 논리 시간 역할을 하며 이전 리더와 같은 지연된 정보를 서버가 감지를 할 수 있다. 각 서버에는 현재 기간 번호가 저장되어 있으며 시간이 지남에 따라 순차적으로 번호가 증가한다. 현재 기간은 서버가 통신할 때마다 교환된다. 한 서버의 현재 기간이 다른 서버의 기간보다 작으면 현재 기간이 큰 값으로 업데이트 된다. 후보자 또는 리더가 만약 기간이 만료되었음을 발견하면 즉시 팔로워로 돌아간다. 서버가 만료된 기간 번호를 포함하는 요청을 수신하면 요청이 거부된다.

Raft 서버는 RPC를 사용하여 통신을 수행하고 기본 합의 알고리즘은 두가지 RPC만 필요로 한다. RequestVote RPC는 선거 중에 후보자가 초기화학고, AppendEntries RPC는 리더가 시작하여 로그 엔트리를 복제하고 heartbeat 형식을 제공하기 위해 초기화한다. Log compaction 섹션에서는 서버 간 스냅샷을 전송하기 위한 세번째 RPC를 추가한다. 서버는 시간내에 응답을받지 못하면 RPC를 다시 실행하고 최상의 성능을 얻기 위해 RPC를 병렬로 발행한다.

2. Leader election(리더 선출)

Raft는 heartbeat를 사용하여 리더 선출을 트리거 한다. 서버가 시작되면 팔로워로 시작한다. 서버는 리더 또는 후보자로부터 유효한 RPC를 수신하는 동안 팔로어의 상태를 유지한다. 리더는 권한을 유지하기 위해 정기적인 heartbeat(로그 엔트리가 없는 AppendEntries RPC)를 모든 팔로워에게 보낸다. 팔로워가 선거 타임아웃(election timeout)이라고 불리는 시간내에 메세지를 받지 못한 경우, 실행 가능한 리더가 존재하지 않는다고 판단하여 새로운 리더를 선출하기 위한 선거를 개시한다.

선거를 시작하기 위해 팔로어는 현재 기간을 늘려 후보자의 상태로 전환한다. 그런 다음 자신에게 투표하고 클러스터와 다른 서버에 RequestVote RPC를 발행한다. 후보자는 다음 3가지 중 하나가 일어날 때까지 상태를 계속 유지한다: (a)선거에서 승리, (b)다른 서버가 리더가 되었거나, (c)일정 시간 동안 승자가 없는 경우. 이러한 결과는 아래 단락에서 개별적으로 설명한다.

후보자는 같은 기간에 클러스터 전체의 과반수의 서버로부터 투표를 받았을 경우 선거에서 승리한다. 각 서버는 주어진 기간 내에 선착순으로 최대 한명의 후보자에게 투표를 수행한다. 이 다수결 규칙을 통해 최대 1명의 후보자가 특정 기간의 선거에서 승리할 수 있다. 후보자가 선거에 승리하면 리더가 된다. 그런 다음 다른 모든 서버에 heartbeat 메시지를 보내 권한을 설정하여 새로운 선거의 발생을 방지한다.

투표를 기다리는 동안 후보자는 리더라고 주장하는 다른 서버에서 AppendEntries RPC를 받을 수 있다. (그 RPC에 포함되는) 리더의 기간이 적어도 후보자의 현재의 기간과 같은 크기인 경우, 후보자는 리더를 정당한 것으로 인식하고 팔로워 상태로 돌아온다. RPC의 기간이 후보자의 현재 기간보다 작으면 후보자는 RPC를 거부하고 후보자 상태를 계속한다.

세번째로 고려되는 결과는 후보자가 선거를 이기거나 잃지 않는 상황이다: 다수의 팔로워가 동시에 후보자가 되는 경우, 투표가 분산되어 후보자가 과반수를 획득할 수 없게 된다. 이것이 발생하면 각 후보자는 타임 아웃하고 그 기간을 하나 증가시키고 다음 라운드의 RequestVote RPC를 시작하여 새로운 선거를 시작한다. 그러나 추가 조치가 없으면 분할표는 무제한으로 반복 될 수 있다.

Raft는 분할 투표가 드물고 발생하더라도 신속하게 해결할 수 있도록 무작위화 된 투표 시간 초과 기능을 사용한다. 첫번째 단계에서 투표가 나뉘지 않도록 선거 시간 초과는 일정 기간(예 : 150-300ms)에서 무작위로 선택된다. 이것은 서버간에 서로 다르기 때문에 대부분의 경우 단일 서버만 타임 아웃 된다. 분할 투표를 처리하기 위해 동일한 메커니즘이 사용된다. 각 후보자는 선거가 시작될 때 랜덤화된 선거 타임아웃을 재개하고 다음 선거를 시작하기 전에 타임아웃이 경과할 때까지 기다린다. 이로 인해 새로운 선거에서 다른 투표가 발생할 가능성이 낮아지게 된다. Performance 섹션에서 이 접근법이 리더를 신속하게 선출한다는 것을 보여준다.

선거는 설계 옵션 중에서 이해 가능성이 우리의 선택을 어떻게 이끌었는지의 예이다. 처음에는 순위 시스템을 사용할 계획이었다 : 각 후보자는 경쟁하는 후보 중에서 선택에 사용되는 고유한 순위가 할당되었다. 후보자가 더 높은 수준의 다른 후보자를 발견하면, 더 높은 수준의 후보자가 선거에서 이길 수 있도록 자신은 팔로어로 돌아간다. 이 접근법은 가용성과 관련된 섬세한 문제가 발생하는 것으로 나타났다(상위 서버에 장애가 발생하면 하위 서버가 시간 초과되어 다시 후보자가 되어야 한다). 알고리즘을 여러번 조정했지만 각 조정 후에 새로운 특이 케이스가 발생했다. 결국, 우리는 무작위화된 재시도 접근법이 더 분명하고 이해하기 쉽다는 결론을 내렸다.

3. Log replication(로그 복제)

리더가 선출되면 리더는 클라이언트의 요청을 처리하기 시작한다. 각 클라이언트 요청에는 복제 상태 머신(Replicated state machine)에서 실행되는 명령이 포함된다. 리더는 새로운 엔트리로서 커멘드를 로그에 추가한 다음, 엔트리를 복제하기 위해서 다른 각 서버에 병렬로 AppendEntries RPC를 실행한다. 엔트리가 안전하게 복제되면 리더가 그 엔트리를 스테이트 머신에 적용해, 그 실행 결과를 클라이언트에 돌려준다. 팔로워가 충돌하거나, 동작이 느려지거나, 네트워크 패킷이 손실된 경우, 리더는 모든 팔로워가 최종적으로 모든 로그 엔트리를 저장할 때까지 (클라이언트에 응답한 후에도) AppendEntries RPC를 무제한으로 재시도한다.

로그는 위와 같이 구성된다. 각 로그 엔트리는 리더에 의해 엔트리가 수신될 때 상태 머신 커맨드와 기간 번호를 저장한다. 로그 엔트리의 기간 번호는 로그 간의 불일치를 감지하고 “Raft consensus algorithm의 중요한 특성”의 일부 속성을 확인하는 데 사용된다. 각 로그 엔트리에는 로그 내의 위치를 식별하는 정수 인덱스도 포함된다.

리더는 상태 머신에 로그 엔트리를 적용해도 안전하다고 판단하는 시점을 결정한다; 이러한 엔트리는 커밋이라고 불린다. Raft는 커밋된 엔트리는 영속적이며, 최종적으로는 이용 가능한 모든 스테이트 머신에 의해 실행되는 것을 보증한다. 로그 엔트리는 그 엔트리를 작성한 리더로부터 과반수의 서버에 복제되면 커밋된다. 또한 이것은 이전 리더가 만든 엔트리를 포함하여 리더가 가진 로그의 이전 엔트리르도 모두 커밋한다. Safety 섹션은 리더를 교체한 후에 이 규칙을 적용할 때의 미묘한 차이점을 설명하고, 이러한 커밋의 정의가 안전하다는 것을 보여준다. 리더는 커밋되고 있는 것을 알고 있는 최대의 인덱스를 추적해, 이후에 AppendEntries RPC(heartbeat를 포함)에 그 인덱스를 포함해, 다른 서버가 최종적으로 찾아낼 수 있도록 한다. 팔로워는 로그 엔트리가 커밋되었음을 알면 해당 엔트리를 로컬 상태 시스템에(로그 순서대로) 적용한다.

Raft 로그 메커니즘은 서로 다른 서버간에 높은 수준의 로그 일관성을 유지하도록 설계되어 있다. 이것은 시스템의 동작을 단순화하고, 보다 예측 가능하게 할 뿐만 아니라 안전성을 확보하기 위한 중요한 요소가 된다. Raft는 Log Matching Property를 구성하는 다음과 같은 특성을 보유하고 있다.

• 다른 로그의 2개의 엔트리에 같은 인덱스와 기간이 있는 경우, 그들은 같은 커멘드를 보관 유지하고 있다.
• 다른 로그의 2개의 엔트리에 같은 인덱스와 기간이 있는 경우, 그 이전의 모든 엔트리에 대한 로그는 동일하다.

첫번째 속성은 리더가 특정 기간 내에 특정 로그 인덱스를 가진 최대 하나의 엔트리를 만들고 로그 엔트리는 로그에서 위치를 변경하지 않는다는 사실에 기반한다. 두번째 속성은 AppendEntries가 수행하는 간단한 일관성 검사를 통해 보장된다. AppendEntries RPC를 송신할 때, 리더는 새로운 엔트리의 직전의 엔트리의 인덱스와 기간을 로그에 포함한다. 팔로어가 해당 로그에서 동일한 인덱스와 기간을 가진 엔트리를 찾을 수 없는 경우 새 엔트리를 거부한다. 일관성 검사는 유도 단계 역할을 한다. 로그 초기의 빈 상태는 Log Matching Property를 충족시키고 일관성 검사는 로그가 확장될 때마다 Log Matching Property를 유지한다. 결과적으로 AppendEntries가 성공적으로 반환되면 리더는 팔로워의 로그가 새 엔트리까지 자신의 로그와 동일하다는 것을 알 수 있다.

보통 운영시에는 리더와 팔로워의 로그는 일관된 채로 있기 때문에 AppendEntries의 일관성 체크가 실패하는 일은 없다. 그러나, 리더가 충돌하면 로그가 일관성이 깨질 수 있다(이전 리더는 로그의 모든 엔트리를 완전히 복제하지 않을 수 있다). 이러한 불일치는 일련의 리더와 팔로워의 충돌을 악화시킬 수도 있다.

위 그림은 팔로워의 로그가 새로운 리더의 로그와 어떻게 다른지를 보여준다. 팔로워는 리더에 존재하는 엔트리가 누락되었거나 리더에 존재하지 않는 추가 엔트리가 있거나 둘 다일 수 있다. 로그에 누락되거나, 관련없는 엔트리가 다수 기간에 걸쳐 있을지도 모른다. Raft에서 리더는 팔로워의 로그에 자신의 복제를 강제하여 모순을 처리한다. 즉, 팔로워 로그의 충돌하는 엔트리는 리더의 로그 엔트리로 덮어쓴다. Safety(안전) 섹션은 한가지 제한 사항과 함께 사용하면 이런 방식이 안전하다는 것을 보여준다.

팔로어의 로그를 자신의 로그와 일치시키려면 리더는 두개의 로그가 일치하는 최신의 로그 엔트리를 찾아, 그 이후는 팔로워의 로그내의 모든 엔트리를 삭제해, 그 후의 모든 리더 엔트리를 팔로워에 송신할 필요가 있다. 이러한 모든 동작은 AppendEntries RPC가 수행하는 일관성 검사에 대한 응답으로 수행한다. 리더는 각 팔로워의 nextIndex를 관리한다. 이것은 리더가 해당 팔로어에게 보내는 다음 로그 엔트리의 인덱스이다. 리더가 최초로 권한을 얻으면, 모든 nextIndex 값을, 자신의 로그내의 마지막 값의 직후에 있는 인덱스로 초기화한다. 팔로워의 로그가 리더의 로그와 일치하지 않으면 다음 AppendEntries RPC에서 AppendEntries 일관성 검사가 실패한다. 거부 후 리더는 nextIndex를 감소시키고 AppendEntries RPC를 다시 실행한다. 이윽고 nextIndex는 리더와 팔로워의 로그가 일치하는 포인트에 도달한다. 이것이 일어나면 AppendEntries가 성공해, 팔로워의 로그내의 경합하는 엔트리가 삭제되어(존재하는 경우) 리더의 로그로부터 엔트리가 추가된다. AppendEntries가 성공하면 팔로워의 로그는 리더의 로그와 일치하고 이 상태는 해당 기간동안 그대로 유지된다.

필요한 경우, 거부되는 AppendEntries RPC를 줄이기 위해 프로토콜을 최적화 할 수 있다. 예를 들어 AppendEntries 요청을 거부하면 팔로어는 충돌하는 엔트리의 기간과 해당 기간에 저장된 첫 번째 인덱스를 포함 할 수 있습니다. 이 정보에 의해 리더는 nextIndex를 감소시켜 그 기간내의 경합하는 엔트리 모두를 회피할 수 있다; 엔트리 마다 1개의 RPC는 아니고, 경합하는 엔트리를 가지는 각 기간에 대해 1개의 AppendEntries RPC가 필요하게 될 것이다. 실제로, 장애가 거의 발생하지 않으며, 많은 모순되는 엔트리가 존재할 가능성이 없기 때문에, 이 최적화가 필요하지 않을 수 있다.

이 메커니즘은 리더가 권한을 얻었을때 로그 무결성을 회복하기 위한 특별한 조치를 취할 필요가 없다. 일반 작업을 시작하기만하면 AppendEntries 일관성 검사 실패에 따라 로그가 자동으로 수렴된다. 리더 자체가 로그의 엔트리를 덮어쓰거나 삭제하지 않는다.

이 로그 복제 메커니즘은 Replicated state machines 섹션에서 설명한 바람직한 합의 특성을 보여준다. Raft는 과반수 서버가 구동하는 한 새로운 로그 엔트리를 수락, 복제, 적용할 수 있다. 일반적인 경우 새로운 엔트리는 클러스터 대부분에 대한 단일 RPC 라운드로 복제될 수 있으며, 단일의 느린 팔로워는 성능에 영향을 미치지 않는다.

4. Safety(안전)

이전 섹션에서는 Raft가 리더를 선택하고 로그 엔트리를 복제하는 방법에 대해 설명했다. 그러나 지금까지 설명한 메커니즘은 각 상태 머신이 동일한 명령을 동일한 순서로 실행하는 것을 보장하기에는 충분하지 않다. 예를 들면, 리더가 복수의 로그 엔트리를 커밋하고 있는 동안 팔로워를 사용할 수 없는 경우가 있다. 그 팔로워가 리더에 선출되어 버리면, 그 엔트리를 새로운 엔트리로 덮어쓰는 것이 가능해, 그 결과로 다른 스테이트 머신이 다른 명령 순서를 실행할 가능성이 있다.

이 섹션에서는 어느 서버가 리더에 선출되는지에 제한을 가함으로써 Raft 알고리즘을 완성시킨다. 이 제한으로 인해 특정 기간의 리더가 이전 기간에 커밋된 모든 엔트리를 포함하게 된다(Leader Completeness Property). 선거의 제한을 부여하고 커밋 규칙을 더 정확하게 만들었다. 마지막으로 Leader Completeness Property에 대한 증명을 제시하고, 복제 상태 머신의 올바른 동작으로 어떻게 연결되는지를 보여준다.

4.1 Election restriction(선거 제한)

리더 기반 합의 알고리즘에서 리더는 결국 모든 커밋된 로그 엔트리를 저장해야 한다. Viewstamped Replication과 같은 일부 합의 알고리즘은 초기에 커밋된 모든 로그 엔트리를 보유하지 않은 서버조차도 리더로 선택할 수 있다. 이러한 알고리즘은 선거 과정 동안 또는 그 직후에 누락된 엔트리를 식별하고 새로운 리더에게 전송하기 위한 추가적인 메커니즘을 포함되어 있다. 불행히도 이로 인해 상당한 추가 메커니즘과 복잡성이 발생한다. Raft는 보다 단순한 접근법을 채택하고, 각 새로운 리더가 선출된 순간부터 이전의 기간에 커밋 된 모든 엔트리가 존재하는 것을 보증한다. 이러한 엔트리를 리더에게 전송할 필요는 없다. 즉, 로그 엔트리는 리더에서 팔로워로의 한 방향으로만 흐르고 리더는 로그의 기존 엔트리를 덮어 쓰지 않는다.

Raft는 로그에 모든 커밋 된 엔트리를 포함하지 않는 후보자가 선거에서 이길 수 없도록 하는 투표 프로세스를 사용한다. 후보자가 선출되기 위해서는 클러스터의 과반수와 접촉할 필요가 있다. 즉, 커밋 된 모든 엔트리는 이러한 서버 중 적어도 하나에 존재해야 함을 의미한다. 후보자의 로그가 이들 과반수 서버의 다른 로그와 적어도 같은 최신의 상태로, 모든 커밋이 끝난 엔트리를 보관 유지하고 있을 것이다. RequestVote RPC는 이 제한을 구현한다. PRC에는 후보자의 로그에 대한 정보가 포함되어 있으며 자신의 로그가 후보자의 로그보다 최신인 경우 투표자는 투표를 거부한다.

Raft는 로그내의 마지막 엔트리의 인덱스와 기간을 비교하여 2개의 로그의 어느 쪽이 최신인지를 판단한다. 로그가 다른 기간의 최종 엔트리를 갖는 경우 새 기간의 로그가 최신인 것이 된다. 로그가 같은 기간으로 끝나는 경우, 어느 쪽이든 긴쪽의 로그가 최신의 것이다.

4.2 Committing entries from previous terms(직전 기간의 커밋 엔트리)

로그 복제 섹션에서 설명한 바와 같이 리더는 현재 기간의 엔트리가 과반수의 서버에 저장한 시점에서 커밋이 되었음을 인식한다. 엔트리를 커밋하기 전에 리더가 충돌하면, 이후 리더는 엔트리의 복제를 완료하려고 시도한다. 그러나 리더는 과반수의 서버에 저장되었다고 해서 즉시 이전 기간의 엔트리가 커밋 되었다고 결론을 내릴 수 없다. 아래 그림은 이전 로그 엔트리가 과반수의 서버에 저장되어 있음에도 불구하고 미래의 리더가 항목을 덮어 쓰는 상황을 보여준다.

위 그림과 같은 문제를 없애기 위해 Raft는 복제본을 계산하여 이전 기간의 로그 엔트리를 커밋하지 않는다. 복제본을 계산하면 리더의 현재 기간의 로그 엔트리만 커밋한다. 현재 기간의 엔트리가 커밋되면 Log Matching Property는 이전의 모든 항목을 간접적으로 커밋한다. 리더는 오래된 로그 엔트리가 커밋 끝났다고 안전하게 결론할 수 있는 상황(예를 들어 그 엔트리가 모든 서버에 저장되어 있는 경우)도 있지만, Raft는 단순화를 위해서 보다 보수적인 어프로치를 채용하고 있다.

Raft에서는 리더가 이전의 기간으로부터 엔트리를 복제할 때에 로그 엔트리가 원래의 기간 번호를 보관 유지하기 때문에, 커밋 룰에 불필요한 복잡성을 발생시킨다. 다른 컨센서스 알고리즘에서는 새로운 리더가 이전의 기간으로부터 엔트리를 재복제하는 경우, 새로운 기간 번호를 사용해 재복제할 필요가 있다. Raft 접근법은 로그 엔트리가 시간이 지남에 따라 로그 전체에 동일한 기간 번호를 유지하기 때문에 로그 엔트리를 쉽게 결정할 수 있다. 게다가 Raft의 새로운 리더는 그외의 알고리즘보다 이전의 기간으로부터 보내지는 로그 엔트리가 적다(다른 알고리즘에서는 커밋하기 전에 중복한 로그 엔트리를 송신해 재번호 붙여야 한다)

4.3. Safety argument(Safety 토론)

완전한 Raft 알고리즘을 제공함으로써, 우리는 Leader Completeness Property가 성립하는 것을 보다 정확하게 논의할 수 있다(이 논의는 안전성의 증명에 근거하고 있다). 우리는 Leader Completeness Property가 성립하지 않는다고 가정하고 그 모순을 증명한다. 기간 T의 리더(leader T)가 그 기간의 로그 엔트리를 커밋하지만, 그 로그 엔트리가 어느 미래 기간의 리더에 저장되지 않았다고 가정한다. 리더(leader U)가 엔트리를 저장하지 않는 최소 기간 U > T 생각하자.

• 1. 커밋된 엔트리는 리더 U가 선출된 시점의 로그에는 아직 존재하지 않아야 한다(리더는 결코 엔트리를 삭제하거나 덮어쓰지 않는다).
• 2. 리더 T는 클러스터의 과반수에 엔트리를 복제하고, 리더 U는 클러스터의 과반수에서 득표를 얻었다. 따라서 아래 그림에서 볼 수 있듯이 적어도 하나의 서버(“the voter”)가 리더 T의 항목을 수락하고 리더 U에 투표했다. the voter는 모순에 도달하는 열쇠다.
• 3. the voter는 leader U에 투표하기 전에 leader T로부터 커밋된 엔트리를 받아야 한다; 그렇지 않으면 leader T로부터의 AppendEntries 요청은 거절되었을 것이다(그 시점의 기간은 T보다 더 커질 것이다).
• 4. leader U에 투표했을 때에도 the voter는 엔트리를 보존하고 있다. 이는 잠재적인 모든 리더가(가정에 따라) 엔트리를 포함하며 리더는 엔트리를 삭제하지 않고 팔로워가 리더와 충돌하는 엔트리만 삭제하기 때문이다.
• 5. the voter는 leader U에게 표를 주었기 때문에, leader U의 로그는 the voter의 로그와 친숙한 정도로 최신이어야 한다. 이것은 두가지 모순 중 하나를 이끌어 낸다.
• 6. 첫째, the voter와 leader U가 동일한 최종 로그 기간을 공유하는 경우, leader U의 로그는 the voter의 로그의 모든 항목을 포함하도록 적어도 the voter의 로그와 동일한 길이여야 한다. 이것은 모순된다. 왜냐하면 the voter는 커밋된 엔트리를 가지고 있고 leader U는 그렇지 않다고 가정되었기 때문이다.
• 7. 그렇지 않으면 leader U의 최종 로그 기간은 the voter보다 길어야 한다. 또한 the voter의 최종 로그 기간 T 이상이었기 때문에, T보다 더 크다(기간 T에 커밋된 엔트리 포함). leader U의 마지막 로그 엔트리를 작성한 이전의 리더는(가정에 의해) 그 로그에 커밋된 엔트리를 포함하지 않으면 안된다. 그리고 Log Maching Property에 의해 리더 U의 로그에는 커밋된 엔트리도 포함되어 있지 않으면 안되어, 이것은 모순되고 있다.
• 8. 이것으로 모순이 완결되었다. T보다 더 큰 기간을 가진 모든 리더는 기간 T에서 커밋된 기간 T의 모든 항목을 포함해야 한다.
• 9. Log Matching Property는 미래의 리더가 전 섹터에서의 그림 인덱스 2와 같은 간접적으로 커밋되는 엔트리도 포함하는 것을 보증한다.

위 그림에서 S1(기간 T 리더)가 해당 기간에 새 로그 항목을 커밋하고 나중에 U S5가 리더로 선출되면 로그 항목을 수락하고 S5에 투표한 서버 (S3)가 적어도 하나 있어야 한다.

Leader Completeness Property를 제공함으로써 State Machine Safety Property를 증명할 수 있다. 이 특성은 한 서버가 특정 인덱스의 로그 엔트리를 상태 머신에 적용하면 다른 서버가 동일한 인덱스에 대해 다른 로그 항목을 적용하지 않음을 말한다. 서버가 로그 엔트리를 상태 머신에 적용할 때, 그 로그는 그 엔트리까지 리더의 로그와 동일해야 하며, 엔트리는 커밋되어야 한다. 여기서, 임의의 서버가 특정 로그 인덱스를 적용하는 최하위의 기간을 고려해 보자. Log Completeness Property는 더 높은 기간의 모든 리더가 동일한 로그 항목을 저장할 수 있도록 보장하므로 이후의 기간에 인덱스를 적용하는 서버도 동일한 값을 적용한다. 따라서 State Machine Safety Property가 성립한다.

마지막으로 Raft는 서버에 로그 인덱스 순서를 항목에 적용하도록 요청한다. State Machine Safety Property와 결합하면 모든 서버가 각각의 상태 시스템에 동일한 순서로 동일한 로그 항목 집합을 적용하게 된다.

5. Follower and candidate crashes (팔로워와 후보자 충돌)

여기까지는 리더의 충돌에 초점을 맞추어 왔다. 팔로워 충돌과 후보자 충돌은 리더 충돌보다 훨씬 다루기 쉽고 둘 다 같은 방식으로 해결할 수 있다. 팔로워 또는 후보자가 충돌하면 이후에 보낸 RequestVote 및 AppendEntries RPC는 실패한다. Raft는 이러한 실패를 무제한으로 재시도하여 처리한다. 충돌한 서버가 다시 시작되면 RPC가 성공적으로 완료된다. 서버가 RPC가 완료된 후 응답하기 전에 충돌하면 서버는 다시 시작한 후 다시 동일한 RPC를 수신하게 된다. Raft RPC는 멱등이므로 해를 입히지 않는다. 예를 들어 팔로어의 로그에 이미 존재하는 로그 엔트리를 포함한 AppendEntries 리퀘스트를 수신했을 경우, 새로운 리퀘스트의 엔트리는 무시된다.

6. Timing and availability(타이밍과 가용성)

Raft에 대한 우리의 요구 사항 중 하나는 안전성이 타이밍에 의존하지 않는다는 것이다. 특정 이벤트가 예상보다 빠르거나 느리게 발생한다고해서 시스템이 잘못된 결과를 생성해서는 안된다. 그러나 가용성(클라이언트에게 적시에 응답하는 시스템의 능력)은 필연적으로 타이밍에 의존해야 한다. 예를 들어, 메시지 교환이 서버 장애 사이의 일반적인 시간보다 오래 걸린다면, 후보자는 선거를 승리하기에 충분한 시간 상태를 유지할 수 없을 것이다; 안정된 리더가 없으면 Raft는 처리를 진행할 수 없다.

리더 선출은 Raft에서 타이밍이 가장 중요한 측면이다. Raft는 시스템이 다음 타이밍 요구 사항을 충족하는 한 안정적인 리더를 선택하고 유지할 수 있다.

broadcastTime << electionTimeout << MTBF

이 부등식에서 broadcastTime는 서버가 클러스터의 모든 서버에 RPC를 병렬로 전송하고 응답을 수신하는 데 걸리는 평균 시간; electionTimeout은 선거 시간 초과; MTBF는 단일 서버의 평균 장애 시간이다. 리더는 팔로어가 선거를 시작하지 않도록 heartbeat 메시지를 확실하게 전송할 수 있도록 브로드캐스트 시간은 선거 타임아웃보다 한자리 작아야 한다; 시스템이 꾸준히 진행되도록 선거 타임아웃은 MTBF보다 몇자리수 작아야 한다. 리더가 충돌하면 시스템은 대략 선거 시간 초과 동안 사용할 수 없게 된다; 이 시간이 전체 시간의 극히 일부이길 바라고 있다.

브로드캐스트 시간과 MTBF는 시스템의 기초가 되는 속성이지만, 선거 타임 아웃은 선택해야 하는 것이다. 일반적으로 Raft RPC는 수신자가 안정된 스토리지에 정보를 저장해야하므로 브로드 캐스트 시간은 저장 기술에 따라 0.5ms에서 20ms까지 다양할 수 있다. 그 결과 선거 타임 아웃은 10ms에서 500ms 사이가 될 가능성이 높다. 일반적인 서버 MTBF는 몇개월 이상이며 타이밍 요구 사항을 쉽게 충족시킨다.

Cluster membership changes(클러스터 멤버쉽 변경)

지금까지 클러스터 구성(컨센서스 알고리즘에 참여하는 서버 세트)은 고정되어 있다고 가정했다. 그러나 실제로는 장애가 발생한 서버를 교환하는 경우나 복제의 수준을 변경하는 경우 등 구성 변경이 필요할 수도 있다. 이것은 클러스터 전체를 오프라인으로 하고 설정 파일을 변경하고 나서 클러스터를 재기동하는 방식으로 시도할 수 있지만, 변경 중에는 클러스터를 이용할 수 없게 된다. 또한 수동 작업이 있는 경우 운영자의 실수가 발생할 위험이 있다. 이러한 문제를 피하기 위해 구성 변경을 자동화하여 Raft 컨센서스 알고리즘에 통합하기로 결정했다.

구성 변경 메커니즘이 안전하기 위해서는 마이그레이션 중에 동일한 기간에 두명의 지도자가 선출 될 수 없어야 한다. 불행히도 서버가 이전 구성에서 새 구성으로 직접 전환하는 접근법은 안전하지 않다. 모든 서버를 한번에 원자로 전환하는 것은 불가능하기 때문에 마이그레이션 중에 클러스터가 두개의 독립적인 과반수로 분할될 수 있다(아래 그림 참조).

안전성을 보장하기 위해 구성 변경은 2단계 접근 방식을 취해야 한다. 이 두단계를 구현하는 방법에는 몇가지가 있다. 예를 들어, 일부 시스템은 첫번째 단계를 사용하여 이전 설정을 비활성화하고 클라이언트 요청을 처리할 수 없도록 한다. 그런 다음 두번째 단계에서 새 설정을 활성화 한다. Raft에서 클러스터는 먼저 결합 합의(joint consensus)라고 우리가 부르는 마이그레이션 구성으로 전환한다; 결합 합의가 얻어지면 시스템은 새로운 구성으로 이행한다. 결합 합의는 새로운 구성과 이전 구성 모두를 결합한다.

• 로그 항목은 두 구성의 모든 서버에 복제된다.
• 두 구성의 모든 서버는 리더 역할을 할 수 있다.
• 합의(선거와 엔트리 커밋)는 이전 구성과 새 구성 양쪽 모두에서 개별적으로 과반수가 필요하다.

결합 합의를 통해 개별 서버는 안전성을 희생하지 않고 서로 다른 시점에 구성간에 전환을 수행할 수 있다. 또한, 클러스터는 구성 변경 동안에도 클라이언트 요청의 처리를 계속할 수 있다.

클러스터 구성은 복제된 로그의 특수 엔트리를 사용하여 저장 및 통신한다. 위 그림은 구성 변경 프로세스를 보여준다. 리더가 Cold 로부터 Cnew로 구성 변경하는 요구를 받으면, 결합 합의(도면내의 Cold, new)의 구성을 로그 엔트리로서 저장하고, 앞서 설명한 메카니즘을 사용해 그 엔트리를 복제한다. 하나의 서버가 새로운 구성 엔트리를 로그에 추가하면, 그 이후의 모든 판단에 그 구성을 사용한다(엔트리가 커밋 되어 있는지에 관계없이, 서버는 항상 로그내의 최신의 구성을 사용한다). 즉, 리더는 Cold, new의 로그 엔트리가 언제 커밋되는지를 판단하기 위해서 Cold, new의 룰을 사용하게 된다. 리더가 충돌했을 경우, 선출된 후보자가 Cold, new를 받고 있는지 여부에 따라 Cold 또는 Cold, new의 어느 쪽인가에서 새로운 리더를 선택할 수 있다. 어쨌든 이 기간 내에 Cnew는 일방적인 결정을 내릴 수 없다.

Cold, new가 커밋되면, Cold도 Cnew도 상대의 승인 없이 결정을 내릴 수 없게 된다. 또한 Leader Completeness Property는 Cold 및 new 로그 엔트리를 가진 서버만 리더로 선출되도록 보장한다. 이것으로 리더가 Cnew를 지정하는 로그 엔트리를 작성해, 클러스터에 복제해도 안전하게 되었다. 다시 말하지만, 이 구성은 각 서버에서 확인되는 즉시 적용된다. 새 구성이 Cnew 규칙에 따라 커밋되면 이전 구성은 독립적이며 새 설정에 포함되지 않은 서버는 종료 될 수 있다. 이제 위 그림과 같이 Cold 와 Cnew가 모두 일방적인 결정을 내리지 않게 되 안전성이 보장된다.

재구성에서 해결해야하는 세가지 문제가 더 있다. 첫번째 문제는 새 서버가 초기 상태에서 로그 항목을 저장하지 않을 수도 있다는 것이다. 이 상태에서 클러스터에 추가되면 그들이 따라 잡는데 상당한 시간이 걸릴 수 있다. 이시간 동안 새로운 로그 엔트리를 커밋할 수 없게 될지도 모른다. 가용성의 격차를 피하기 위해 Raft는 구성 변경 전에 새 서버가 비투표 멤버로 클러스터에 참여하는 추가 단계를 도입한다(리더는 로그 항목을 복제하지만 과반수로 간주되지 않음). 새 서버가 나머지 클러스터를 따라잡으면 위에서 설명한 구성 변경을 진행할 수 있다.

두번째 문제는 클러스터 리더가 새로운 구성의 일부가 되지 않을 수 있다는 것이다. 이 경우, 리더는 Cnew 로그 엔트리를 커밋한 후 스텝 다운한다(팔로워 상태에 돌아간다). 이것은 리더가 자신을 포함하지 않는 클러스터를 관리하고 있는 일정한 기간(Cnew를 커밋하고 있는 동안)이 있는 것을 의미하고, 로그 엔트리는 복제되지만 자신은 과반수로서 카운트하지 않는다. 이것은 새로운 구성이 독립적으로 작동할 수 있는 첫번째 포인트이기 때문에 Cnew가 커밋 될 때 리더 마이그레이션이 발생한다(Cnew 에서 리더를 선택하는 것은 항상 가능하다). 그 이전에는 Cold 의 서버 밖에 리더에 선출될지도 모른다.

세번째 문제는 삭제된 서버(Cnew에는 없는 서버)가 클러스터를 혼란을 줄 수 있다는 것이다. 이러한 서버는 heartbeat를 수신하지 않으므로 타임 아웃이 발생하여 새로운 선거를 시도한다. 그리고 그들은 새로운 기간 번호로 RequestVote RPC를 전송하여 현재 리더를 팔로워 상태로 되돌린다. 궁극적으로 새로운 리더가 선출되지만 삭제된 서버는 다시 시간 초과가 발생하고 이 과정이 반복되므로 가용성이 떨어진다.

이 문제를 방지하기 위해 서버는 현재 리더가 있다고 확신하는 경우 RequestVote RPC를 무시한다. 구체적으로는, 서버가 현재의 리더로부터 최소 선거 타임 아웃내에 RequestVote RPC를 수신했을 경우, 그 서버는 기간을 갱신하거나 투표는 허용되지 않는다. 이것은 각 서버가 선거를 시작하기 위해 적어도 최소 선거 시간 초과를 기다리는 정상적인 선거에는 영향을 미치지 않는다. 그러나 이것은 삭제된 서버의 혼란을 피하는 데 도움이 된다. 리더가 클러스터에 heartbeat가 도달하면 더 큰 기간 번호로 인해 퇴진하지는 않을 것이다.

Log compaction(로그 압축)

Raft의 로그는 정상 작동중에 많은 클라이언트 요청으로 커져 가지만, 현실의 시스템에서는 한없이 확대하는 것은 불가능하다. 로그가 커짐에 따라 더 많은 공간을 차지하고 재생하는데 많은 시간이 걸린다. 이것은 로그에 누적된 불필요한 정보를 버리는 메커니즘이 없다면 결국 가용성 문제로 이어질 것이다.

스냅샷은 압축의 가장 간단한 접근이다. 스냅샷 생성에서 현재 시스템 상태 전체를 안정된 저장소에 스냅샷으로 저장하고 그 시점까지의 모든 로그가 삭제한다. 스냅샷은 Chubby와 ZooKeeper에서 사용되며이 이 섹션의 나머지 부분에서는 Raft의 스냅샷에 대해 자세히 설명한다.

로그 클리닝이나 Log Structured Merge Tree(LSM-Tree)와 같은 압축에 대한 증분 접근법도 가능하다. 이들은 한번에 데이터의 일부에만 작용하기 때문에 압축 부하를 시간이 지남에 따라 균등하게 분산시킬 수 있다. 이들은 먼저 삭제되고 덮어 쓰여진 객체를 많이 누적된 데이터 영역을 선택하고, 그 영역의 활성 객체를 보다 컴팩트하게 재기록하여 영역을 개방한다. 이는 스냅샷에 비해 상당한 추가 메커니즘과 복잡성을 요구하며, 항상 전체 데이터 세트에 대해 작업을 수행함으로써 문제를 단순화한다. 로그 클리닝은 Raft에 수정을 필요로 하지만, 스테이트 머신은 스냅샷과 같은 인터페이스를 사용해 LSM 트리를 구현할 수가 있다.

위 그림은 서버는 로그의 커밋된 항목을 현재 상태(이 예에서는 변수 x와 y)만 저장하는 새로운 스냅 샷으로 바꿉니다. 스냅샷의 last included index와 term은 이전 로그에 스냅 샷을 배치하는 데 사용된다. 위 그림은 Raft에서 스냅샷 생성의 기본 개념을 보여준다. 각 서버는 독립적으로 스냅샷을 만들고 로그의 커밋된 항목만 포함합한다. 대부분의 작업은 상태 머신이 현재 상태를 스냅 샷에 쓰는 것이다. Raft도 스냅샷에 소량의 메타데이터도 포함한다: last included index는, 스냅샷이 옮겨놓는 로그내의 마지막 엔트리(스테이트 머신이 적용한 마지막 엔트리)의 인덱스이며, last included term은 이 엔트리의 기간이다. 이들은, 엔트리가 직전의 로그 인덱스와 텀을 필요로 하기 때문에, 스냅샷에 계속되는 최초의 로그 엔트리에 대해서 AppendEntries 일관성 체크를 서포트하기 위해서 보존된다. 클러스터 멤버쉽 변경을 활성화하기 위해 스냅샷에는 마지막으로 추가된 인덱스 시점의 최신 구성도 로그에 포함된다. 서버가 스냅샷 쓰기를 완료하면, 마지막으로 추가된 인덱스까지의 모든 로그 엔트리와 이전 스냅샷을 모두 삭제할 수 있다.

일반적으로 서버는 각각 스냅샷을 생성하지만 리더는 때때로 뒤처진 팔로어에게 스냅샷을 보내야 한다. 이 경우는 리더가 팔로워에게 송신할 필요가 있는 다음의 로그 엔트리를 이미 삭제했을 경우에 발생한다. 다행스럽게도 이러한 상황은 정상적인 운영환경에서는 발생할 수 없다. 리더를 따라잡은 팔로워는 이미 해당 로그 엔트리를 가지고 있다. 그러나 매우 느린 팔로워와 클러스터에 참여하는 새로운 서버는 그렇지 않다. 이러한 팔로워를 최신 상태로 만들려면 리더가 네트워크에 스냅샷을 보내는 것이다.

리더는 InstallSnapshot이라는 새로운 RPC를 사용하여 너무 느린 팔로워에게 스냅샷을 보낸다; 팔로어는 이 RPC를 사용하여 스냅샷을 받을 때 기존 로그 항목을 어떻게 할지 결정해야 한다. 일반적으로 스냅샷에는 아직 수신자의 로그에 없는 새로운 정보가 포함될 것이다. 이 경우 팔로어는 전체 로그를 삭제한다. 모든 로그가 스냅샷으로 대체되며 스냅샷과 충돌하는 커밋되지 않은 엔트리가 있을 수 있다. 또한 팔로어가 가진 로그의 앞부분을 설명하는 스냅샷을(재전송 또는 미스에 의해) 수신했을 경우, 스냅샷의 대상이 되고 있는 로그 엔트리는 삭제되지만, 스냅샷 이후의 엔트리는 여전히 유효하며 보관해야 한다.

팔로어는 리더의 동의 없이 스냅샷을 찍을 수 있기 때문에 이런 스냅샷의 방식은 Raft의 강력한 리더 원리칙과는 다르다. 그러나 우리는 이런 방식의 출발이 정당하다고 생각한다. 러더가 있을때는 합의에 도달할 때 충돌하는 결정을 회피하는 데 도움이 되지만, 스냅샷 찍을때는 이미 합의에 도달했기 때문에 결정의 충돌을 일어나지 않는다. 데이터는 리더로부터 팔로워로 흐르지만, 이제 팔로워만이 데이터를 재구성할 수 있다.

우리는 리더만이 스냅샷을 만들고 그 스냅샷을 각 팔로워에게 보내는 리더 기반 대안 접근법을 검토했다. 그러나 이것에는 두가지 단점이 있다. 먼저 각 팔로어에게 스냅샷을 전송하면 네트워크 대역폭이 소모되어 스냅샷 생성 프로세스가 지연된다. 각 팔로어는 자신의 스냅샷을 만드는데 필요한 정보가 이미 가지고 있고, 일반적으로 각 서버가 로컬 상태에서 스냅샷을 만드는 것이 네트워크를 통해 스냅샷을 송수신하는 것보다 훨씬 저렴하다. 둘째, 리더의 구현이 더 복잡해진다는 것이다. 예를 들어, 리더는 새로운 클라이언트 요청을 차단하지 않기 위해 새로운 로그 엔트리의 복제와 병행하여 팔로어에게 스냅샷을 전송할 필요가 있다.

스냅샷 성능에 영향을 주는 두가지 문제가 있다. 먼저 서버는 언제 스냅샷을 만들지 결정해야 한다. 서버의 스냅샷이 너무 자주 발생하면 디스크 대역폭과 전력이 낭비되고, 스냅샷이 생성 빈도가 너무 낮으면 스토리지 용량이 부족할 수 있으며 재부팅 중에 로그를 재생하는데 필요한 시간이 길어진다. 간단한 방법 중 하나는 로그가 바이트 단위로 고정 크기에 도달했을 때 스냅샷을 만드는 것이다. 이 사이즈가 스냅샷의 예상 사이즈보다 상당히 크게 설정되어 있는 경우, 스냅샷 생성에 필요한 디스크 대역폭의 오버헤드는 작을 것이다.

두번째 성능 문제는 스냅샷을 만드는 데 상당한 시간이 걸릴 수 있다는 것이다. 이로 인해 정상 작동에 지연이 발생하는 것은 바람직하지 않다. 해결책은 작성된 스냅샷에 영향을주지 않고 새로운 업데이트를 적용할 수 있도록 copy-on-write 기술을 사용하는 것이다. 예를 들어, 함수형 데이터 구조를 갖는 상태 머신은 본질적으로 이것을 지원한다. 또는 운영 체제의 copy-on-write 지원(예 : Linux에서 fork)을 사용하여 상태 시스템 전체의 in-memory 스냅샷을 만들 수 있다(본 구현에서는 이 접근법을 사용하고 있다).

Client interaction(클라이언트와의 상호 전달)

이 섹션에서는 클라이언트가 클러스터의 리더를 찾는 방법과 Raft가 선형화 가능한 의미 체계를 지원하는 방법 등 클라이언트와 Raft가 상호 작용하는 방법에 대해 설명한다. 이러한 문제는 다른 모든 합의 기반 시스템에도 적용되며 Raft 솔루션도 해당 시스템과 유사하다.

Raft 클라이언트는 모든 요청을 리더에게 보낸다. 클라이언트는 처음 시작할 때 무작위로 선택된 서버에 연결한다. 클라이언트의 최초의 선택이 리더가 아닌 경우, 그 서버는 클라이언트의 요구를 거부하고 가장 최신에 수신한 리더에 관한 정보를 제공한다(AppendEntries 에는 리더의 주소가 포함되어 있다). 리더가 충돌하면 클라이언트 요청이 시간 초과된다. 클라이언트는 무작위로 선택한 서버에서 다시 시도를 한다.

Raft의 목표는 선형화 가능한 시멘틱스(각 조작은 호출로부터 응답까지의 어느 시점에서, 순간에, 정확하게 1회(exactly once) 실행되는 것처럼 보인다)를 구축하는 것이다. 그러나 이전에 설명한 것처럼 Raft는 명령을 여러번 실행할 수 있다. 예를 들어 로그 엔트리를 커밋한 후, 클라이언트에 응답하기 전에 리더가 크래쉬 했을 경우, 클라이언트는 새로운 리더를 사용해 그 커멘드를 재실행하는 것으로 커멘드는 2회 실행되게 된다. 해결 방법은 클라이언트가 각 명령에 고유한 일련 번호를 할당하는 것이다. 그런 다음 상태 머신은 각 클라이언트에 대해 처리된 최신 일련 번호를 관련 응답과 함께 추적한다. 이미 실행중인 일련 번호의 명령을 수신하면 요청을 다시 실행하지 않고 즉시 응답한다.

읽기 전용 조작은 로그에 아무것도 쓰지 않고 처리할 수 있다. 그러나 요청에 응답하는 리더가 자신이 인식하지 못하는 새로운 리더로 교체되었을 수 있으므로 추가 조치를 취하지 않으면 오래된 데이터를 반환할 위험이 있다. 선형 가능 읽기는 오래된 데이터를 반환해서는 안되며 Raft는 로그를 사용하지 않고 이를 보장하기 위해 두가지 추가 조치가 필요하다. 첫째, 리더는 어떤 항목이 커밋되었는지에 대한 최신 정보를 가지고 있어야 한다. Leader Completeness Property는 리더가 모든 커밋된 엔트리를 보관 유지하고 있는 것을 보증하지만, 임기 시작 시점에는 어느 엔트리까지 커밋되고 있는지 모르는 경우가 있다. 그것을 알기 위해서는 임기내에 엔트리를 커밋할 필요가 있다. Raft는 각 리더가 해당 임기 시작 시점에 로그에 빈 no-op 항목을 커밋하여이 문제를 처리한다. 그런 다음 리더는 읽기 전용 요청을 처리하기 전에 자신이 폐기되었는지 확인해야 한다(새로운 리더가 선출되면 정보가 오래되었을 수 있음). Raft는 리더가 읽기 전용 요청에 응답하기 전에 클러스터의 과반수와 heartbeat를 교환하도록 함으로써 이 문제를 처리한다. 혹은, 리더는 heartbeat의 메카니즘을 사용해 일종의 임대를 제공할 수도 있지만, 이 때 안전성은 타이밍에 의존하게 된다(이것은 bounded clock skew를 전제로 하고 있다).

Implementation and evaluation(구현 및 평가)

우리는 RAMCloud의 구성 정보를 저장하고 RAMCloud 코디네이터의 장애 조치를 지원하는 복제 상태 머신의 일부로 Raft를 구현했다. Raft의 구현에는 테스트, 코멘트, 공백 라인을 제외한 약 2000행의 C++ 코드가 포함되어 있다. 소스 코드는 자유롭게 이용할 수 있다. 이 논문의 초안을 기반으로 개발의 다양한 단계에 있는 약 25개의 독립적인 타사 오픈 소스 Raft 구현도 존재한다. 또한 다양한 기업이 Raft 기반 시스템을 배포하고 있다.

이 섹션의 나머지 부분에서는 이해 가능성, 정확성 및 성능의 세가지 관점에서 Raft를 평가한다.

1. Understandability(이해 가능성)

Paxos 대비 Raft의 이해 용이성을 측정하기 위해 스탠포드 대학의 Advanced Operation Systems 과정과 UC Berkeley의 Distributed Computing 과정의 상급 학부생과 대학원생을 대상으로 실험 연구를 수행했다. Raft와 Paxos에서 별도의 비디오 강의를 녹화하고 해당 퀴즈를 만들었다. Raft의 강의에서는 로그 압축을 제외한 본 논문의 내용에 대해 설명했다; Paxos의 강의에서는 단일 결정 Paxos, multi-decree Paxos, 재구성, 실제로 필요한 몇개의 최적화(리더 선출 등) 등, 동등한 복제 스테이트 머신을 만드는데 충분한 내용을 다루었다. 이 퀴즈에서는 알고리즘의 기본적인 이해도를 테스트한 것 외에 학생들에게 코너 케이스에 대한 추론도 요구했다. 각 학생은 하나의 비디오를 보고 해당 퀴즈를 풀고 두번째 비디오를 보고 두번째 퀴즈를 풀었다. 참가자의 약 절반은 먼저 Paxos 파트를, 나머지 절반은 먼저 Raft 파트를 실시했고, 연구의 첫번째 부분에서 얻은 성과와 경험의 개인차를 모두 고려하기 위함이다. 각 퀴즈의 참가자 점수를 비교하여 참가자가 Raft를 더 잘 이해하고 있는지 확인했다.

Paxos와 Raft의 비교는 가능한 한 공정하게 하려고 노력했다. 43명의 참가자 중 15명이 Paxos를 사용한 경험이 있다고 보고하고, Paxos의 동영상은 Raft의 동영상보다 14% 길었다. 아래 표에 요약된 바와 같이, 우리의 잠재적인 편향의 원인을 완화하기 위한 조치를 취해 왔다.

평균적으로 참가자는 Paxos 퀴즈보다 Raft 퀴즈에서 4.9포인트 높았다(60점 만점 중 Raft 평균 점수는 25.7, 평균 Paxos 점수는 20.8이었다); 상응하는 t-검정에서 95% 신뢰도에서 Raft 접수의 실제 분포는 Paxos 점수의 실제 분포보다 적어도 2.5포인트 더 큰 평균을 보였다.

우리는 또한 신입생들의 퀴즈 점수를 세가지 요인, 즉 응시한 퀴즈, 이전 Paxos 경험 정도, 알고리즘을 학습한 순서를 기반에 따라 예측하는 선형 회귀 모델을 만들었다. 이 모델은 퀴즈의 선택에 따라 Raft가 12.5 포인트 유리한 차이를 보일 것으로 예측하고 있다. 이것은 관측된 4.9 포인트의 차이보다 상당히 높고, 실제 학생의 대부분이 과거에 Paxos를 경험하고 있었고, 그것이 Paxos에는 상당히 도움이 되었지만, Raft는 약간 덜 도움이 되었다. 이상하게도 이 모델에서는 이미 Paxos의 퀴즈를 받은 사람의 Raft 스코어가 6.3 포인트 내려갈 것으로 예측하고 있다. 이유는 불명하지만 통계적으로 유의미하다고 생각된다.

또한 퀴즈 후에 참가자를 설문조사하여 어떤 알고리즘이 구현 또는 설명하기 쉬운지를 확인했다; 참가자의 압도적 다수가 Raft쪽이 구현과 설명이 용이하다고 보고하고 있다. 그러나 이러한 자기 보고의 감정은 참가자의 퀴즈 점수보다 신뢰성이 낮고 참가자는 Raft가 이해하기 쉽다는 우리의 가설을 알고 있었기에 참가자가 편향되었을 가능성이 있다.

2. Correctness(정확성)

우리는 섹션 5에서 설명한 합의 메카니즘에 대한 공식적인 사양(formal specification)과 안전성의 증명을 개발했다. 공식 명세는 TLA + 명세 설명 언어를 사용하여 요약된 정보를 정확하게 표현한다. 이것은 약 400행의 길이로 증명의 대상 역할을 한다. Raft를 구현하는 모든 사람들에게도 유용할 것이다. 우리는 TLA 인증 시스템을 사용하여 Log Completeness Property를 기계적으로 증명했다. 그러나 이 증명은 기계적으로 확인되지 않은 불변식에 의존한다(예 : 명세의 유형 안전성은 입증되지 않음). 또한, 우리는 (명세에만 의존하기 때문에) 완전하고 (약 3500 단어의 길이 때문에) 비교적 정확한 State Machine Safety 특성의 비공식 증명을 만들었다.

3. Performance(성능)

Raft의 성능은 Paxos와 같은 다른 합의 알고리즘과 유사하다. 성능에 가장 중요한 경우는 기존 리더가 새로운 로그 엔트리를 복제하는 경우이다. Raft는 이것을 최소한의 메시지수(리더로부터 클러스터의 절반까지 1회의 왕복)를 사용하여 이를 달성하고 있다. Raft의 성능을 더욱 향상시킬 수 있다. 예를 들어, 더 높은 처리량 및 낮은 대기 시간을 위한 배치 처리 및 파이프라인 처리 요청을 지원하는 것이 용이하다. 다른 알고리즘에 대한 다양한 최적화가 논문에 제안되었다; 이들 중 많은 것들이 Raft에도 적용될 수 있지만, 우리는 향후 연구에 맡길 것이다.

우리는 Raft 구현을 사용하여 Raft 리더 선출 알고리즘의 성능을 측정하고 두가지 질문에 답변했다. 첫째, 리더 선출 과정은 빠르게 수렴할 것인가? 둘째, 리더 충돌 후 달성 가능한 최소 다운타임은 얼마인가?

리더 선출을 측정하기 위해 우리는 5대의 서버로 구성된 클러스터의 리더를 반복적으로 충돌시키고 크래시 감지에서 새로운 리더 선출까지 소요되는 시간을 측정했다(위 그림 참조). 최악의 시나리오를 생성하기 위해 각 평가판의 서버가 서로 다른 로그 길이를 갖게 되었기 때문에 일부 후보자는 리더가 될 자격이 없었다. 또한 분할 투표를 유도하기 위해 테스트 스크립트는 프로세스를 종료하기 전에 리더에서 heartbeat RPC의 동기 브로드 캐스트를 트리거했다(이것은 충돌 전에 새 로그 항목을 복제하는 리더의 동작과 비슷하다). 리더는 모든 테스트의 최소 선거 시간 초과의 절반인 heartbeat 간격 내에서 균일하게 무작위로 충돌했다. 따라서 가능한 최소 다운 타임은 최소 선거 타임 아웃의 약 절반이었다.

위 그림의 위쪽 그래프는 선거 시간 초과에서 소량의 무작위화가 선거에서 분할 투표를 피하기에 충분하다는 것을 보여준다. 무작위성이 없는 경우, 우리의 테스트에서는 많은 분할 투표로 인해 리더 선출은 일관되게 10초보다 길었다. 불과 5ms의 랜덤성을 추가하는 것만으로 다운타임의 중앙값은 287ms가 되었다. 무작위성을 높이면 최악의 경우의 동작이 개선된다. 랜덤성이 50ms의 경우, 최악의 경우의 완료 시간(1000이상의 트라이얼)은 513ms였다.

위 그림의 하단 그래프는 선거 타임아웃을 단축함으로써 다운타임을 단축할 수 있음을 보여준다. 12~24ms의 선거 타임아웃에서는 리더 선출에 평균 35ms 밖에 걸리지 않았다(최장의 시도는 152ms 걸렸다). 그러나 이 시점을 넘어 타임아웃을 단축하는 것은 Raft의 타이밍 요건을 위반한다. 즉, 리더는 다른 서버가 새로운 선거를 시작하기 전에 heartbeat를 브로드 캐스트하는 것이 어렵다. 이로 인해 불필요하게 리더 변경이 발생하여 전체 시스템의 가용성이 저하될 수 있다. 150-300ms와 같은 보수적인 선거 타임 아웃을 사용하는 것이 좋다. 이러한 타임 아웃은 불필요하게 리더를 변경할 가능성이 낮고 좋은 가용성을 유지한다.

Conclusion(결론)

많은 경우 알고리즘은 정확성, 효율성 및 간결성을 주요 목적으로 설계되었다. 이것들은 모두 가치 있는 목적이지만, 우리는 이해하기 쉬움도 중요하다고 생각하고 있다. 개발자가 알고리즘을 실제로 구현하기 전까지는 다른 어떤 목표도 달성할 수 없으며 필연적으로 발표시의 형태에서 벗어나 확장된다. 개발자가 이 알고리즘을 깊이 이해하고 직관적이지 않으면 구현시 원하는 특성을 유지하기가 어려울 것이다.

본 논문에서는 널리 받아들여지고 있지만 깊이까지 이해할 수 없는 알고리즘인 Paxos가 오랜 세월에 걸쳐 학생과 개발자들에게 어려움을 겪게 한 분산 컨센서스의 문제를 다루었다. 우리는 새로운 알고리즘 Raft를 개발하고 Paxos보다 이해하기 쉽다는 것을 보여 주었다. 또한 우리는 Raft가 시스템 구축을 위한 더 나은 기반을 제공한다고 생각한다. 주요 설계 목표로 이해하기 쉬움을 삼음으로써 Raft의 설계 접근 방식이 바뀌었다. 설계가 진행됨에 따라 우리는 문제를 분해하고 상태 공간을 단순화하는 등 몇가지 기법을 반복적으로 재사용하게 되었다. 이 기술은 Raft의 이해를 용이하게 할뿐만 아니라 그 정확성을 스스로 납득시키하게 했다.

추가로 Replication이나 Cluster 환경에서 노드를 3개 이상 두는 이유

Replication이나 Cluster 환경에서 노드를 3개 이상 두는 이유는 합의(Consensus), 가용성(Availability), 정족수(Quorum) 문제를 해결해야하기 때문이다.

1. 3개 이상 필요한 이유

합의(Quorum) 기반의 분산 시스템에서 의사결정은 과반수에 의해 이루어진다. 3개 노드라면 최소 2개가 일치해야 합의가 성립된다. 그래야 하나가 장애 나도 서비스가 계속 가능하게 된다. 그래서 합의에 도달할 수 있는 숫자가 최소 3개 이상인 것이다. 예를 들어 2개 노드에서 1개가 장애 나면 1개 노드로는 정상인지 아닌지 스스로 판단할 수 없어 합의가 불가능하지만, 3개 노드에서는 1개가 장애가 나도 여전히 2개가 살아있으므로 합의(의사 결정의 과반수 성립)가 가능해 정상 동작이 가능하게 된다.

2. 클러스터 노드 수별 장애 허용 시나리오

3. 사례

• MongoDB Replica Set : 최소 3개의 노드를 권장 (Primary + Secondary + Arbiter).

복제본 세트의 최소 권장 구성은 데이터를 보유하는 멤버가 3개( 주 노드 1개, 보조 노드 멤버 2개)인 3명의 멤버로 구성된 복제본 세트다.

• Redis

Note that the minimal cluster that works as expected must contain at least three master nodes. For deployment, we strongly recommend a six-node cluster, with three masters and three replicas. 예상대로 작동하는 최소 클러스터에는 최소 3개의 마스터 노드가 필요하다는 점에 유의하라. 첫 번째 테스트는 3개의 마스터 노드와 3개의 슬레이브를 포함하여 총 6개의 노드로 시작하는 것이 좋다.

• Kubernetes etcd : 홀수 개(3, 5, 7)를 권장. 과반수 확보가 핵심.

It is recommended to have an odd number of members in a cluster. An odd-size cluster tolerates the same number of failures as an even-size cluster but with fewer nodes. The difference can be seen by comparing even and odd sized clusters: 클러스터에는 홀수개의 멤버를 두는 것이 좋다. 홀수 크기의 클러스터는 짝수 크기의 클러스터와 동일한 수의 장애를 허용하지만 노드 수는 더 적다. 짝수 크기와 홀수 크기의 클러스터를 비교하면 그 차이를 확인할 수 있다.

• Kafka Cluster : 복제 팩터와 ISR(in-sync replica) 개수에 따라, 안정적인 운영을 위해 최소 3개 broker 권장.

A common production setting is a replication factor of 3, i.e., there will always be three copies of your data. This replication is performed at the level of topic-partitions. 일반적인 프로덕션 설정은 복제 계수 3이다. 즉, 항상 데이터 사본이 세 개 생성된다. 이 복제는 토픽 파티션 수준에서 수행된다.*

• Docker

Raft tolerates up to (N-1)/2 failures and requires a majority or quorum of (N/2)+1 members to agree on values proposed to the cluster. This means that in a cluster of 5 Managers running Raft, if 3 nodes are unavailable, the system cannot process any more requests to schedule additional tasks. Raft는 최대 (N-1)/2회의 장애를 허용하며, 클러스터에 제안된 값에 대해 (N/2)+1명의 멤버중 과반수 또는 정족수가 동의해야 한다. 즉, Raft를 실행하는 5개의 관리자로 구성된 클러스터에서 3개의 노드를 사용할 수 없으면 시스템은 추가 작업 스케줄링 요청을 더 이상 처리할 수 없다.

• 그외 HashiCorp Consul, CockroachDB, HashiCorp Nomad, Influxdb, TiDB 등에 사용되고 있다.

참조 사이트

• The Raft Consensus Algorithm
• In Search of an Understandable Consensus Algorithm