tech

[논문 직역] In Search of an Understandable Consensus Algorithm

downfa11 2025. 12. 7. 02:05

Diego Ongaro and John Ousterhout Stanford University

 

Paxos나 불필요한 부분은 공부하면서 제외했음. 자체적으로 넘버링 및 생략한 문단이 있음.

모든 사진은 내렸고, usenix의 원본 논문을 찾아가면 볼 수 있으니 직접 찾아가길 권장함.

 

Abstract

Raft는 복제된 로그를 관리하기 위한 consensus 알고리즘이다. 이 방법은 (multi-)Paxos와 같은 결과를 내며 효율적이지만, 그 구조는 Paxos와 다르다. 이로 인해서 Raft가 Paxos보다 이해하기 쉬워지고, 실용적인 시스템을 구축하는데 더 나은 기반을 제공한다.

이해를 쉽게 하기 위해서 Raft는 Leader election, Log Replication, Safety같은 consensus 핵심 요소를 분리하고, 고려해야할 요소를 줄이기 위해 더욱 강한 일관성을 강제한다. 연구 결과에 따르면 Raft가 Paxos보다 학생들이 더 배우기 쉽다. 거기에 클러스터 구성원 변경을 위한 새로운 메커니즘도 포함되어 있는데, 이는 overlapping majorities를 이용해서 안정성을 보장한다.

1. Introduction

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

안타깝게도, 이 Paxos는 이해하기 매우 어렵다. 여러 차례 접근성을 높이려는 시도에도 불구하고, 실용적인 시스템을 지원하기 위해서 복잡한 구조를 변경할 필요가 있다. 그 결과, 시스템 구축자와 학생들 모두가 어려움을 겪고 있다.

우리도 Paxos에 고생하고서 새로운 알고리즘을 찾기 시작했다. 우리의 접근법은 독특했는데, 주된 목표는 understandability이었다:

이 연구의 결과물이 Raft라는 합의 알고리즘이다. 여기에는 분해, 상태 공간의 축소 등의 특정 기법을 적용해서 이해도를 높히고자 했다.

  • decomposition(분해): Raft는 Leader election, Log Replication, Safety를 분리함
  • state space reduction(상태 공간의 축소): Paxos에 비해 비결정성과 서버간 불일치 가능성을 줄여줌

이를 통해서 두 대학에서 43명의 학생을 대상으로 한 사용자 연구에 따르면, Raft가 Paxos보다 훨씬 이해하기 쉽다는 결과가 나왔다. 두 알고리즘을 모두 배운 후 33명의 학생이 Raft에 관한 질문에 대해 Paxos에 관한 질문보다 더 잘 답변할 수 있었다.

Raft는 기존의 합의 알고리즘(특히 Oki와 Liskov의 Viewstamped Replication)과 여러 면에서 유사하지만, 여러 새로운 특징을 가지고 있다.

  • Strong leader: 다른 합의 알고리즘보다 더 강력한 리더 형태를 사용한다. 예를 들어, 로그는 리더에서 다른 노드로만 흐르기 때문에 복제된 로그의 관리가 간소화되어 더 이해하기 쉽다.
  • Leader election: 무작위 timeout을 통해 리더를 선출하기에, 합의 알고리즘에 필요한 heartbeat에서 작은 메커니즘만 추가해도 충돌을 해결할 수 있다.
  • Membership changes: 클러스터 내의 set of servers 변경 메커니즘은 다수가 전환시 겹치는 새로운 공동 합의 방식을 사용한다. 이를 통해서 구성 변경 중에도 클러스터가 정상적으로 계속 작동할 수 있다.

우리는 Raft가 교육적 목적과 구현의 기초 모두에서 Paxos 및 다른 합의 알고리즘보다 우수하다고 믿는다.

다른 알고리즘보다 더 간단하고 이해하기 쉽다.

실용적인 시스템의 요구를 충족할만큼 충분히 완벽하게 설명되어 있다.

여러 오픈소스 구현체가 있으며 여러 회사에서 사용되고 있다.

안정성 부분은 공식적으로 명시되고 입증되었으며 그 효율성은 다른 알고리즘과 비교할만 하다.

2. Replicated state machines

consensus 알고리즘은 일반적으로 context of replicated state machines에서 발생한다. 이러한 접근은 상태 머신들이 동일한 상태의 복사본을 연산하며 일부 서버가 다운되어도 계속 작동할 수 있다.

이 replicated state machines은 분산 시스템에서 다양한 내결함성 문제를 해결하는데 사용된다. 예를 들어, GFS, HDFS, RAMCloud처럼 단일 클러스터 리더를 가진 대규모 시스템은 일반적으로 별도의 상태 머신을 사용해서 리더 선출을 관리하고, 선출 과정에서 리더가 충돌되는 경우에도 살아남아야 하는 구성 정보를 저장한다. 이 replicated state machines의 예시로는 Chubby와 Zookeeper가 있다.

 

[상태 머신 그림]

replicated state machines은 일반적으로 replicated log를 사용해서 구현된다. 각 서버는 명령어들이 포함된 로그를 저장하며, 상태 머신은 이를 순서대로 실행한다. 각 로그는 동일한 명령어를 동일한 순서로 포함하므로, 각 상태 기계는 순서대로 처리하기만 해도 deterministic(결정적)이므로 각각 동일한 상태와 출력 순서를 계산한다.

 

이때 replicated log를 일관되게 유지하는 것이 consensus 알고리즘의 역할이다. 서버 내부의 합의 module은 클라이언트들로부터 명령을 받아 로그에 추가한다. 다른 합의 모듈들과 통신하여 일부 서버가 실패하더라도 모든 로그가 동일한 요청과 순서를 포함하도록 보장한다. commands들이 적절하게 복제되면 각 서버의 상태 머신이 순서대로 처리하고 출력이 클라이언트로 반환된다.

그 결과, 서버들은 단일 highly reliable 상태 머신을 구축한 것처럼 보이게 된다.

 

실용적인 시스템을 위한 consensus 알고리즘은 일반적으로 다음과 같은 특성을 가진다.

  • 네트워크 지연, 파티션, 패킷 손실, 중복, 재정렬 등 모든 비복잡한 조건에서 안전성을 보장한다. (잘못된 결과를 반환하지 않는다는 의미)
    • 📌 non-byzantine conditions: 우리의 동로마가 흑흑
      • 여러 명의 장군이 도시를 포위하고 공격 또는 후퇴 시점을 결정해야 한다. 성공하려면 모든 장군이 같은 시점에 행동해야 하지만, 통신 수단의 불안정성과 배신자의 존재 가능성이 있다는 문제
      • 컴퓨터 과학(분산 시스템)에서는 Byzantine Fault라고 부르며, 일부 노드가 충돌, 부정확한 데이터 전송, 일관성 없는 정보 제공 등 임의의(arbitrary) 방식으로 작동하는 오류 상태를 말한다.
      • 그냥 시스템 내부에 신뢰할 수 없는 구성 요소가 존재하며, 전체의 합의 도달 및 정상적인 작동을 위협하는 환경을 의미한다.
  • 서버 대다수가 정상 작동하고, 서로간이나 클라이언트와 통신할 수 있는한 완전히 기능한다.
  • 로그 일관성을 보장하기 위해서 타이밍에 의존하지 않는다. 잘못된 clock이나 극심한 메시지 지연은 최악의 경우, 가용성 문제를 일으킨다.
  • 소수의 느린 서버가 전체 시스템 성능에 영향을 미치지 않는다. 클러스터 과반수가 RPC 통신에 응답하기만 하면 명령이 완료될 수 있어야 한다.

 

3. Designing for understandability

우리는 Raft 설계 과정에서 여러 목표를 설정했다. 시스템 구축을 위한 완전하고 실용적인 기반을 제공하여 개발자가 요구하는 설계 작업을 크게 줄여야 한다는 것; 모든 조건에서 안전해야 하며, 일반적인 작동 조건에서 사용할 수 있어야 한다; 그리고 일반적인 작업에 효율적이어야 한다. 하지만 우리의 가장 중요한 목표이자 가장 어려운 도전은 ‘이해하기 쉬워야 한다’였다. 많은 사용자들이 알고리즘을 편안하게 이해할 수 있어야 한다. 또한, 알고리즘에 대한 intuitions을 개발할 수 있어야 실제 구현에서 불가피한 확장을 할 수 있다.

 

첫 번째 기법은 잘 알려진 문제 분해 접근법으로, 가능한 한 문제를 독립적으로 해결하고 설명하며 이해할 수 있는 개별 조각으로 나누었다. 예를 들어 Raft에서는 leader election, log replication, safety, membership changes로 분리했다.

 

두 번째 접근법은 고려할 상태 수를 줄여 상태 공간을 단순화하고, 시스템을 더 일관성 있게 만들며, 가능한 한 비결정성을 제거하는 것이다. 구체적으로, 로그에는 holes이 없어야 하며, Raft는 로그들이 서로 일관성이 없어지지 않도록 제한한다.

 

대부분의 경우에서 비결정론을 제거하려 했지만, 일부 상황에서는 비결정성이 오히려 이해도를 높여준다. 특히 무작위 접근법은 비결정성을 도입하지만, 모든 가능한 선택을 유사한 방식으로 처리하여 상태 공간을 줄이는 경향이 있다(choose any; it doesn’t matter). 우리는 Raft 리더 선출 과정을 더욱 단순히 하게 위해서 randomization을 도입했다.

4. Raft consensus algorithm

Raft는 먼저 뛰어난 Leader를 선출하고, 그 리더에게 replicated log 관리를 전적으로 책임지도록 해서 consensus를 구현한다. 리더는 클라이언트로부터 로그를 받고, 이를 다른 서버에 복제하며, 서버에 로그를 안전하게 적용할 수 있을 때를 서버에게 알려준다. 리더가 있으면 replicated log 관리가 더 간단해진다.

 

예를 들어, 리더는 다른 서버와 상의하지 않고도 로그에 새 항목을 어디에 배치할지 결정할 수 있으며, 리더에서 다른 서버로 데이터 흐름을 간단하게 처리할 수 있다. 리더가 실패하거나 다른 서버와 연결이 끊길 수 있으며, 이 경우 새로운 리더가 선출된다.

 

Leader Approach을 고려할 때, Raft는 consensus 문제를 3개의 비교적 독립적인 하위 문제로 분해하고 있다.

  • leader election
  • log replication
  • safety

 

4.1. Raft Basics

Raft 클러스터는 여러 서버가 포함되어 있다. 일반적으로 5개 노드로 구성되며, 시스템이 두번 정도의 고장을 견딜 수 있게 해준다. 각 서버는 언제든지 Leader, Candidate, Follower 세 가지 상태 중 하나에 있다. 정상적으로 운영하는 상태에서는 Leader가 단 한 명 뿐이고, 나머지 서버들은 모두 팔로워가 된다.

 

[상태 전이 그림]

  • Follower들은 수동적이다. 스스로 요청하지 않고 Leader와 Candidate의 요청에 그냥 응답한다.
  • Leader는 모든 클라이언트의 요청을 처리한다. (클라이언트가 팔로워에게 연락하면 팔로워가 리더에게 리디렉션하는 구조).
  • Candidate는 새 Leader를 선출하는데 사용된다.

Raft는 임의의(arbitary) term으로 나눠져 있고, 이 term은 연속된 정수로 번호가 매겨진다. 각 임기(term)는 선거로 시작되며, 한 명 이상의 candidate가 당대표가 되기 위해 도전하는 셈이다. 후보가 선거에서 승리하면 그 임기 내내 Leader로 활동한다. 어떤 경우에는 선거가 투표 분할(split vote)로 이어질 수 있다. 이 경우에는 term이 Leader 없이 끝나며, 새 *보궐*선거와 함께 term이 시작될 예정이다. Raft는 한 term 내에 최대 한 명의 Leader만 존재하도록 보장한다.

 

서로 다른 서버가 term간 전환을 서로 다른 시점에 관찰할 수 있으며, 경우에 따라서 한 서버가 투표나 전체 term을 관찰하지 못할 수도 있다. term은 Raft에서 a logical clock처럼 작동하며, 서버가 오래된 Leader와 같은 구식 정보를 감지할 수 있게 한다. 각 서버는 현재 term값을 저장하며, 시간이 지남에 따라 monotonically하게 증가한다. 서버가 통신할때마다 현재 term이 교환되면서, 더 작은 값을 만나면 큰 값으로 현재 term을 업데이트합니다. Candidate나 Leader의 term이 만료된 것을 알면 즉각적으로 follower 상태로 돌아간다. 서버가 오래된 term 번호를 가진 요청을 받으면 모두 거부한다.

 

Raft 서버는 서로 RPC를 통해 통신하며, consensus는 2개 유형의 RPC만 필요로 한다. RequestVote RPC는 투표중 Candidate에 의해서 시작되며, AppendEntries RPC는 leader가 로그를 복제하고 heartbeat 형태로 제공하기 위해 시작한다. 각 서버는 제때 응답을 받지 못하면 RPC를 재시도하며, 최상의 성능을 위해 병렬로 RPC를 발행한다.

4.2. Leader election

Raft는 heatbeat 메커니즘을 이용해서 리더 선출을 촉발(trigger)시킨다. 서버가 시작되면 팔로워로 시작하고, leader나 candidate로부터 유효한 RPC를 받는 한 계속 팔로워 상태를 유지한다. leader들은 권위를 유지하기 위해 모든 follower들에게 주기적으로 heatbeat(log entries가 없는 AppendEntries RPCs)를 보낸다. follow들이 투표전 timeout에 걸리면, 실질적인 Leader가 없다고 가정하고 새 리더를 선출하기 위한 투표를 시작한다.

 

투표를 시작하기 위해서, follower는 현재 term을 증가시키고 candidate로 전환한다. 그 후에 스스로에게 투표하고 클러스터 내의 다른 서버들과 RequestVote RPC를 병렬로 발송한다. Candidate는 세 가지중 하나가 일어날 때까지 이 상태에서 계속 활동한다.

이러한 결과들은 아래 단락에서 별도로 논의된다:

  1. 선거에서 이긴다.
  2. 다른 서버가 리더로 선출된다.
  3. 일정 기간동안 리더가 없다.
  4. candidate는 같은 term 동안 전체 클러스터 내 서버의 과반수 표를 받으면 선거에서 승리한다. 각 서버는 한 term동안 선착순으로 최대 한 명에게 투표할 수 있다. 다수결 규칙은 특정 term에서 최대 한명만이 선거에서 승리할 수 있음을 보장한다. candidate가 선거에서 승리하면 leader가 된다. 그 후 모든 서버에 heartbeat 메시지를 보내서 권한을 확립하고 새로운 선거를 막는다.
  5. 투표를 기다리는 동안, candidate는 leader라고 주장하는 다른 서버로부터 AppendEntries RPC를 받을 수 있다. 이 RPC에는 leader의 term가 포함되어 있고, candidate 자신의 term보다 크다면 이 leader를 정당한 지도자로 인정하고 follower 상태로 돌아간다. RPC의 term이 현재 term보다 작으면 candidate는 RPC를 거부하고 candidate 상태로 계속 활동한다.
  6. 세 번째로 가능한 경우는 candidate가 선거에서 승리하지도 패배하지도 않는 경우이다. 많은 follower가 동시에 candidate가 되면서 표가 분산되고, 어느 후보도 과반수를 얻지 못할 수 있다. 이 상황이 발생하면 각 candidate는 timeout을 종료하고 term를 연장하고 또다른 RequestVote RPC round를 시작하며 새로운 투표를 시작한다. 하지만 추가적인 조치가 없으면 표의 분산이 무한히 반복될 수 있다.

Raft는 무작위 선거 timeout을 통해서 표가 분산되는 경우가 거의 없게 만들고 신속하게 해결합니다. 처음부터 표 분산을 방지하기 위해 투표 timeout은 고정된 간격(ex. 150-300ms)에서 무작위로 선택됩니다. 이로 인해 서버가 분산되어 대부분의 경우 단일 서버만 timeout이 발생하며, 이 서버는 투표에서 승리하고 다른 서버가 timeout되기 전에 heartbeat를 보낸다. 동일한 메커니즘은 투표의 분산 처리에도 사용된다. 각 candidate는 투표가 시작되면 무작위 투표 timeout을 다시 시작하고서 다음 선거를 시작한다. 이로 인해 새 투표에서 또 다른 ‘표가 분산될 가능성’을 줄인다.

 

투표는 understandability가 설계 대안 중에서 선택을 어떻게 이끈 것인지의 좋은 예시이다. 처음에는 순위(unique rank) 체계를 사용할 계획이었는데, 각 candidate에게 고유한 순위가 부여되어 경쟁자들중에서 선발하는 방식이었다. 만약 후보자가 더 높은 순위의 candidate를 발견하면 다음 선거에서 높은 순위의 candidate가 더 쉽게 이길 수 있도록 follower 상태로 돌아갔다. 이 접근법은 가용상에 관한 미묘한 문제를 낳을 수 있었다. 예를 들어, 높은 순위의 서버가 실패하면 낮은 순위의 서버가 timeout하고서 다시 후보가 되어야할 수 있지만 너무 일찍 실패하면 leader 선출의 진행 상황 자체가 초기화될 수 있었다. 결국 무작위 재시도 방식이 더 명확하고 이해하기 쉽다는 결론에 도달했다.

 

4.3. Log replication

leader가 선출되면 클라이언트의 요청을 처리하기 시작한다. 각 클라이언트의 요청에는 복제된 상태 머신에서 실행할 명령어가 포함되어 있다. leader는 명령어를 로그에 새 항목으로 추가한 후, 다른 서버들과 병렬로 AppendEntries RPC를 발행해서 로그 항목을 복제한다.

 

항목이 안전하게 복제되면 leader는 해당 항목을 자신의 상태 머신에 적용하고 실행 결과를 클라이언트에 반환한다. follower가 죽거나 느리게 실행, 혹은 네트워크 패킷이 분실되면 leader는 AppendEntries RPC를 무한정 재시도하며(클라이언트에 응답한 후에도 포함) 모든 follower가 모든 로그 항목을 저장할 때까지 계속한다.

 

[로그 복제에 관한 그림]

 

로그는 순차적으로 번호가 매겨진 항목들로 구성되어 있다. 각 항목에는 생성된 index와 상태 머신에 대한 Command가 포함되어 있다. 그 항목이 상태 머신에 적용될때 commited으로 간주한다.

 

각 로그 항목은 상태 머신의 명령어와 leader가 입력받았을때의 term을 같이 저장한다. 로그 항목 내의 term은 로그간 불일치를 감지하고, 일부 속성을 보장할때 사용된다. 각 로그 항목은 로그 내 위치를 나타내는 정수 index도 같이 가진다.

 

리더는 상태 머신에 로그 항목을 적용할 수 있는 시점을 결정한다. 이 항목을 commited되었다고 하며, commited된 항목은 내구성이 있으며 모든 상태 머신에서 실행되도록 보장한다. 로그 항목은 해당 항목을 만든 leader가 과반수 이상의 서버들에게 복제하면서 commited된다. 이 경우, 이전 leader가 만든 항목을 포함해서 leader의 로그에 이전 모든 항목들이 commited된다. leader가 변경된 후 이 규칙을 적용할 때의 몇 가지 세부 사항을 논의하며, 이 commited 규칙이 안정성 있음을 보여준다. leader는 commited된 가장 높은 index를 추적하며 향후 AppendEntries RPC(heartbeats 포함)에 추가해서 다른 서버가 알도록 한다. follower가 로그 항목(log entry)이 commited되었다는 사실을 알게 되면 해당 entry를 로컬의 상태 머신에 실행시킨다.

 

우리는 서로 다른 서버의 로그간의 강한 일관성을 유지하기 위해서 Raft Log 메커니즘을 설계했다. 이는 시스템의 동작을 단순화하고 예측 가능하게 만들 뿐만 아니라, 안정성 보장에 중요한 요소이다. Raft는 다음과 같은 특성을 유지하며, 이 속성들로 로그의 매칭 속성을 구성한다:

  • 서로 다른 로그의 두 항목(entry)는 동일한 index와 term이면 동일한 command를 기록한다.
  • 서로 다른 로그의 두 항목이 동일한 index와 term을 가지면 지금까지의 모든 작업 항목들에서 로그가 동일하다.

첫 번째 속성은 leader가 주어진 term에서 log index를 가진 최대 하나의 entry를 생성하며, log enteis는 로그에서 위치가 변하지 않는다는 사실에서 도출된다. 두번째 속성은 AppendEntries가 수행하는 간단한 일관성 검사로 보장된다. AppendEntries RPC를 보낼 때, leader는 새로운 entry 바로 앞에 있는 로그에 해당 entry의 index, term을 포함한다. follower가 로그에서 동일한 index, term의 entry를 찾지 못하면 추가하지 않고 거부한다. 일관성 검사는 induction step으로서 작용한다. 초기 로그의 빈 상태는 로그 매칭 속성(Log Matching Property)를 만족하며, 일관성 검사는 로그가 확장될 때마다 이 로그 매칭 속성을 보존한다. 결과적으로, AppendEntries가 성공할때마다 leader는 follower의 로그가 새로운 entreis 전까지의 자신(leader)의 로그와 동일하다는 것을 인지한다.

 

정상적으로 운영하는 중에는 leader와 follower의 로그가 일관적이므로 AppendEntreis 검사에 실패하지 않는다. 하지만 leader가 충돌되는 경우 로그가 일정하지 않을 수 있다. 예전 leader가 로그의 entries를 완전히 복제하지 못한 경우가 이에 해당한다. 이러한 불일치는 leader와 follower간의 충돌로 인해 더욱 악화될 수 있다. follower가 leader가 없는 추가적인 entry를 놓치거나, leader에 없는 entry를 가지고 있을 수도 있고 혹은 둘 다 일수도 있다. 로그에서 누락되거나 불필요한 entries는 여러 term에 걸쳐 존재할 수 있다.

 

Raft는 leader가 follower들의 로그를 자기 로그와 중복하도록 강제해서 불일치를 해결했다. 즉, follower 로그에서 충돌하는 entries들은 leader의 것으로 덮어쓰게 된다.

 

follower의 로그를 자신의 로그와 일관되게 만들기 위해서 leader는 두 로그가 일치하는 최신 log entries를 찾아서 그 이후의 follower 로그를 삭제하고 그 이후의 모든 로그를 follower들에게 보내야 한다. 이 모든 과정은 AppendEntries RPC가 수행하는 일관성 검사에 대응하여 수행된다. leader는 각 follower마다 netxIndex를 유지하는데, 이는 leader가 해당 follower에게 보낼 다음 log entries의 index이다. leader가 처음 당선되면 모든 nextIndex 값을 현재 로그의 마지막 index 바로 다음으로 초기화한다.

 

follower와 leader간의 로그가 일치하지 않으면 다음 AppendEntries RPC에서 일관성 검사가 실패하게 된다. 거절당한 이후에는 leader가 nextIndex를 감소시키고 AppendEntries RPC를 다시 시도한다. 결국 leader와 follower간의 nextIndex가 일치하는 지점에 도달하게 되는데, 이 경우 AppendEntreis가 성공하여 follower 로그에서 상충되는 항목을 제거하고 leader 로그의 entries를 추가한다. AppendEntries가 성공하면 follower의 로그는 leader의 로그와 일치하며 그 term 내내 유지된다.

 

프로토콜은 거부당한 AppendEntreis RPC 수를 줄이도록 최적화할 수 있다. 이 메커니즘을 통해 leader는 성능에 대한 로그 일관성을 회복하기 위해서 다른 특별한 조치를 취할 필요가 없다. 정상 작동이 시작되고, AppendEntreis 일관성 검사의 실패에 따라서 로그가 자동으로 converge한다. leader는 자신의 log entries를 덮어쓰거나 삭제하지 않는다.

 

이 Log Replication 메커니즘은 바람직한 consensus의 특징을 보인다. Raft는 대부분의 서버가 정상적으로 작동하는 한 새로운 log entries를 accept, replicate, apply할 수 있다. 일반적인 경우에는 단일 round의 RPC로 클러스터 대다수의 서버에 새로운 entries를 복제할 수 있다. 그리고 작업이 느린 follower는 여기에 영향을 주지 않는다.

 

4.4. Safety

앞서 Raft가 leader를 선출하고 로그 기록을 복제하는 방법을 설명했다. 하지만 지금까지 설명한 메커니즘만으로는 각 상태 머신이 동일한 명령어를 동일한 순서로 정확히 실행하도록 보장하기에는 충분하지 않다. 예를 들어, leader가 여러 로그 항목을 기록하는 동안 follower가 사용할 수 없다면, leader가 선출되어 이 기록들을 새로 덮어쓸 수 있다. 그 결과 서로 다른 상태 머신은 서로 다른 명령 시퀀스를 실행할 수 있다.

 

이 섹션은 leader로 선출될 수 있는 서버에 제한(restriction)을 추가해서 Raft 알고리즘을 완성한다. 이 제한은 새로 선출된 leader가 이전 terms에 commited된 모든 작업 내용을 포함하도록 보장한다. 선거 제한을 고려할 때, 우리는 이 commitment를 더욱 정확하게 만든다. 마지막으로, leader의 Completeness Property에 대한 proof sketch를 제시하고 복제된 상태 머신의 올바른 동작으로 이어지는 과정을 보여준다.

 

4.4.1 Election restriction

어떤 leader 기반 consensus 알고리즘이라도, leader는 결국 모든 commited 로그 항목을 저장해야 한다. Viewstamped Replication과 같은 일부 consensus 알고리즘에서는 처음에 모든 commited 항목을 포함하지 않아도 leader를 선출할 수 있다. 이 알고리즘들은 누락된 항목을 식별하고 투표 과정중이나 그 직후에 새 leader에게 전달하는 추가 메커니즘을 포함하고 있다. 안타깝게도, 이로 인해 상당한 추가적 메커니즘과 복잡성이 발생한다. Raft는 이전 term의 모든 commited 항목이 새로운 leader 선출부터 보장받도록 더 간단한 방식을 사용한다. 즉, 로그 항목은 leader에서 follower로 흐르는 한 방향으로만 이뤄지며, leader는 로그의 기존 항목을 덮어쓰지 않는다.

 

Raft는 투표 과정을 이용해서 모든 commited 기록이 기록되지 않는 한 candidate가 선거에서 승리하지 못하도록 한다. candidate는 당선되기 위해서 클러스터의 과반수와 접촉해야 하며, 이는 모든 commited 항목이 최소 한개 이상 서버에 존재해야 함을 의미한다. candidate의 로그가 그 대다수들의 로그보다 최신 상태라면 모든 commited 항목을 포함하게 된다. ReuqestVote RPC는 이 제한을 구현한다. RPC는 candidate의 기록에 관한 정보를 포함하며, 유권자들은 자신의 기록이 candidate보다 최신 상태일 경우 투표를 거부한다.

 

[그림]

Raft는 두 로그중 어느 쪽이 최신인지 판단하기 위해 로그 내 마지막 항목들의 인덱스와 term을 비교한다. 로그의 마지막 항목이 서로 다른 term이라면, 더 높은 term가 포함된 로그가 더 최신 상태이다. 로그가 같은 term으로 끝난다면 더 많은 항목을 가진(더 긴 로그)가 더 최신 상태이다.

 

4.4.2 Committing entries from previous terms

leader는 현재 term의 작업 항목이 대다수의 서버에 저장되면 그 항목이 commited되었다는 것을 알고 있다. leader가 기록을 제출하기 전에 충돌하면, 그 이후의 leader들의 해당 작업 항목을 마무리하려고 시도한다. 하지만 leader는 이전 term의 항목이 대다수의 서버에 저장되면 그 항목이 commited되었는지 즉각적으로 확인할 수 없다.

  • 오래된 로그 항목이 대다수의 서버에 저장되어 있지만, 다음 leader가 여전히 덮어쓸 수 있는 상황 예시

이와 같은 문제를 해결하기 위해, Raft는 복제본을 세어 이전 term의 로그 항목을 절대 commited하지 않는다. leader의 현재 term에서 생성된 로그 항목 복제본의 수를 세어 commited한다. 현재 term의 항목이 commited되면 로그의 매칭 속성 때문에 이전의 모든 항목들도 간접적으로 commit된다. 해당 항목이 모든 서버에 저장된 경우처럼 leader가 이전 term의 로그 항목이 commited된걸로 결론지을 수도 있지만, Raft는 단순성을 위해서 보다 보수적인 접근법을 취한다.

 

Raft는 leader가 이전 term의 항목을 복제할때 로그 항목이 원래 term 번호를 유지하기 때문에 commitment 규칙에 추가적인 복잡성을 발생시킨다. 다른 consensus 알고리즘에서는 새로운 leader가 이전 term의 항목을 복제하면 반드시 새로운 term number와 함께 복제해야 한다. Raft의 접근법은 로그 항목이 시간과 로그간에 동일한 term 번호를 유지하기 때문에 추론을 더 쉽게 만든다. 또한 Raft의 새로운 leader는 이전 term에서 로그 항목을 다른 알고리즘들보다 적게 보낸다.

  • 다른 알고리즘들은 commited되기 전에 redundant 로그 항목을 보내서 넘버링 다시 해야한다.

 

4.4.3 Safety argument

complete Raft 알고리즘이 주어졌다면, 이제 Leader Completeness 속성이 성립한다고 더 정확히 주장할 수 있다. 이 논증은 safety proof에 기반한다. Leader Completeness 속성이 성립하지 않는다고 가정하면, 모순을 증명한다. term T의 leaderT가 자신의 term에서 로그 항목(log entry)을 제출했지만, 그 로그 항목은 다음 term의 leader에 의해 저장되지 않는다고 가정하자. leaderU가 항목을 저장하지 않는 가장 작은 term U를 고려하자.

  1. commited 항목은 선출 당시 leaderU 로그에 없어야 한다. leader는 항목을 삭제하거나 덮어쓰지 않는다.
  2. leaderT는 클러스터 과반수의 항목(Entry)을 복제했고, leaderU는 클러스터 과반수의 표를 받았다. 따라서 적어도 한 Voter는 leaderT의 입력을 수락하고 leaderU에게 투표한 것으로 나타난다.
  3. Voter는 leaderU에 투표하기 전에 leaderT로부터 commited 항목을 수락해야 한다. 그렇지 않으면 leaderT의 AppendEntries 요청을 거부했을 것이다. 현재 기간이 T보다 높았을 것이기 때문이다.
  4. Voter는 leaderU에 투표할 때도 해당 Entry를 저장하는데, 이는 지금까지의 leader들이 해당 Entry를 포함해왔기 때문이다. leader는 항목을 삭제하지 않고, follower들은 leader와 충돌할 때만 Entry를 삭제한다.
  5. Voter가 leaderU에게 투표했으므로, leaderU의 로그도 적어도 Voter들만큼 최신이어야 한다. 이것은 6번의 모순을 만든다.
  6. Voter와 leader가 가장 최신 상태의 term을 공유했다면, leaderU의 로그는 Voter의 로그만큼 길어야 한다. 따라서 로그에는 Voter의 로그에 있을 모든 항목(Entry)이 포함되어 있다. 이게 모순적인 이유가, Voter는 commited Entry를 포함하고 leaderU는 포함하지 않았기 때문이다.
  7. 그렇지 않으면 leaderU의 마지막 term의 Voter보다 클 수밖에 없다. Voter의 마지막 term이 최소 T였기 때문에 T보다 커야 한다(T term의 commited Entry 포함). leaderU의 마지막 log Entry을 만든 이전 term의 leader는 그 commited Entry을 로그에 포함해야 했다. 그럴려면 로그 매칭 속성에 따라 leaderU의 로그에도 commited Entry가 포함되어야 하는데 이는 모순이다.
  8. 8번 논제로 모순을 완성한다. 따라서 T보다 큰 모든 term의 leader는 term T에서 ‘T에 commit된 모든 항목(Entry)’을 포함해야 한다.
  9. 로그 매칭 속성은 나중에 선출된 leader의 term에도 간접적으로 commited entries을 포함하도록 보장한다.

Leader Completeness 성질이 주어지면, 상태 머신의 Safety 속성을 증명하기 쉬우며, 모든 상태 머신이 동일한 로그 항목을 동일한 순서로 적용한다는 것을 알 수 있다.

 

4.5. Follower and candidate crashes

지금까지 우리는 leader의 실패에 대해 집중해왔다. follower와 candidate간의 충돌이 발생하는 경우는 leader의 것보다 훨씬 간단하게 처리되며, 두 경우 모두 같은 방식으로 처리된다. follower나 canddiate가 충돌되면 앞으로 보내질 RequestVote 및 AppendEntries RPC가 실패할 수 있다. Raft는 이러한 실패를 무한정 재시도함으로써 처리한다. 서버가 충돌하면 RPC가 성공적으로 완료된다.

 

서버가 RPC를 완료한 후 응답하기 전에 충돌이 발생하면 재시작한 뒤에 같은 RPC가 다시 전송된다. Raft RPC는 멱둥성(idempotent)하기 때문에 영향을 주지 않는다. 예를 들어서, follower가 이미 로그에 존재하는 항목이 담긴 AppendEntries를 받으면 새 요청에서 해당 항목만 무시한다.

 

4.6. Timing and availability

Raft에 대한 우리의 요구사항 중 하나는 safety가 타이밍에 의존해서는 안된다는 점이다. 어떤 사건이 예상보다 더 빠르거나 느리게 발생한다고 해서 시스템이 잘못된 결과를 만들어서는 안된다. 하지만 시스템이 클라이언트에 신속하게 대응하는 가용성은 필연적으로 타이밍에 의존하게 된다. 예를 들어, 메시지 교환이 서버간 충돌 사이의 일반적인 시간보다 길어지면, 후보들은 선거에서 승리할만큼 오래 머무르지 못한다. steady leader가 없으면 Raft는 작업을 계속할 수 없다.

 

leader 선출은 Raft에서 타이밍이 가장 중요한 부분이다. Raft는 시스템이 다음 타이밍 요건을 충족하는 한, steady leader를 선출하고 유지할 수 있다.

broadcastTime ≪ electionTimeout ≪ MTBF

 

이 불평등한 broadcastTime은 서버가 클러스터 내 모든 서버에 병렬로 RPC를 보내고 그 응답을 받는데 걸리는 평균 시간이다. electionTimeout은 이름 그대로 선거시 발생하는 timeout이고 MTBF는 단일 서버의 평균 실패 간격이다.

 

broadcastTIme은 electionTimeout보다 한 자릿수 정도 짧아야 하며, leader들은 follower들이 선거를 시작하는걸 막기 위해서 필요한 heartbeat 메시지를 신뢰성 있게 전달할 수 있다. electionTimeout에 무작위 방식이 적용되므로, 이 불평등은 표의 분산 가능성도 낮게 만든다. electionTimeout은 MTBF보다 몇 배 정도 짧아야 시스템이 꾸준히 발전할 수 있다. leader가 다운되면 시스템은 대략 electionTime 기간 동안 사용할 수 없게 된다. 우리는 이것이 전체 시간의 아주 작은 일부로 남길 원한다. (조금 의역. 원문: we would like this to represent only a small fraction of overall time)

 

broadcastTime과 MTBF는 기본 시스템의 특성이며, electionTimeout은 우리가 조정할 값이다. Raft의 RPC는 일반적으로 수신자가 정보를 안정적인 저장소에 보존해야 하므로, 전송 시간은 저장 기술에 따라 0.5ms~20ms 사이일 수 있다. 따라서 electionTimeout은 10ms~500ms 사이일 가능성이 크다. 일반적인 서버 MTBF는 몇 달 이상 걸리며, 이는 타이밍 요구사항을 쉽게 충족 시킨다.무슨말인지 모르겠음.. months?

 

5. Cluster membership changes

지금까지 우리는 클러스터 구성(consensus 알고리즘에 참여하는 서버 집합)이 고정되어 있다고 가정했다. 실제로는 서버가 고장났을 때 교체하거나 replicaSet을 변경하는 등 구성을 변경해야 할 때가 있다. 클ㄹ스터 전체를 종료하고 configuration을 업데이트하는 재시작 방식을 이용할 수 있지만, 이 경우 전환시 클러스터가 중단된 상태로 남게 된다. 또한 수작업으로 전환하면서 엔지니어의 실수가 발생할 수 있다. 이러한 문제를 피하기 위 해서 우리는 Configuration 변경을 자동화하고 이를 Raft consensus 알고리즘에 통합하기로 했다.

 

Configuration 변경 메커니즘이 안전할려면, 전환 과정에서 두 명의 leader가 같은 term을 수행하는 시점이 없어야 한다. 안타깝게도, 서버가 기존 구성에서 새 구성으로 바로 전환하는 방식은 위험하다. 모든 서버를 한번에 원자적으로 전환하는 것은 불가능하므로 전환 과정에서 클러스터가 두 개의 독립적인 다수(majorities)로 분할될 수 있다.

 

안정성을 보장하기 위해서 configuration 변경은 2단계 방식을 사용한다. 이 두 단계로 진행되는 방법은 다양하다. 예를 들어, 일부 시스템은 첫 번째 단계에서 기존 구성을 비활성화하여 클라이언트의 요청을 처리할 수 없게 한다. 그 후에 두 번째 단계가 새로운 configuration을 가능하게 한다. Raft에서는 클러스터가 먼저 우리가 joint consensus라 부르는 전이 구성(transitional configuration)으로 전환한다. 이 joint consensus가 commited되면 시스템은 새로운 구성으로 전환된다. joint consensus는 기존 config와 새로운 config를 모두 결합한다.

  • Log entries는 두 config 모두를 모든 서버에 복제한다.

 

하나의 config에서 다른 config로 직접 전환하는 것은 서로 다른 서버가 서로 다른 시간에 전환하기 때문에 안전하지 않다. 이 예시에서 클러스터는 3대의 서버에서 5대로 증가한다. 불행하게도, 같은 term에서는 두 명의 서로 다른 leader가 선출될 수 있는데 한 명은 기존 config의 과반수를 가지는 C-old, 다른 한 명은 새로운 config의 대다수를 차지하는 경우(C-new)이다.

 

Urations.

  • 어느 Configuration이든 어떤 서버든 Leader의 역할을 할 수 있다.
  • Agreement(투표나 entry commit)는 기존/ 새로운 config 모두에서 별도의 과반수를 요구한다.

 

joint consensus는 개별 서버가 서로 다른 시간에 config간의 전환을 허용하며, 안정성을 해치지 않는다. 더 나아가서 jonit consensus는 config 변경 기간동안 클러스터가 클라이언트의 요청을 계속 처리할 수 있게 한다.

 

[그림]

클러스터의 구성은 복제된 로그의 특수 항목(special entries)를 통해서 저장되고 전달된다. 위 그림은 config 변경 과정을 보여준다. leader가 C-old에서 C-new로 config 변경을 요청받으면, joint consensus를 위한 config를 log entries로 저장하고 앞서 설명한 메커니즘을 사용해서 해당 항목(entry)를 복제한다. 서버가 새 config entry를 로그에 추가하면 그 config를 모든 향후 결정에 사용한다. 이때 서버는 로그가 commit되었는지 여부에 관계없이 항상 로그의 최신 상태 config를 사용한다.

 

즉, leader는 C-old, C-new 규칙을 사용해서 C-old, C-new 로그 항목(entry)가 언제 commit되었는지를 결정한다. leader가 충돌하면 결정적인 후보(winning candidate)가 C-old,C-new를 받았는지에 따라서 둘 중 하나에서 새로운 leader가 선택될 수 있다. 어떤 경우던 간에 C-new는 이 기간동안 일방적인(unilateral) 결정을 내릴 수 있다.

 

C-old,C-new가 commited되면 둘 모두 서로의 승인 없이는 결정을 내릴 수 없으며, the Leader Completeness는 C-old,C-new log entry를 가진 서버만이 leader로 선출될 수 있음을 보장한다. 이제 leader는 C-new를 설명하는 로그 항목(entry)를 생성하고 클러스터에 복제할 수 있다. 이 config는 각 서버에 인식되는 즉시 적용된다. 새로운 config가 C-new의 규칙을 따라 commit되면 기존 config는 무의미해지며, 새 config에 속하지 않는 서버는 종료될 수 있다. 위 그림에서 볼 수 있듯이, C-old,C-new가 모두 일방적인 결정을 내릴 수 있는 시간은 존재하지 않는다. 이걸로 안정성을 보장할 수 있다.

 

Configuration 변경, 즉 Reconfiguration에서 해결해야할 문제는 3가지나 더 있다. 첫 번째 문제는 새 서버가 처음에 log entry를 저장하지 않을 수 있다는 점이다. 이 상태로 클러스터에 추가되면 따라잡는데 상당한 시간이 걸릴 수 있으며, 그 기간동안 새 log entry를 commit하는 것이 불가능할 수 있다. 가용성의 공백(availability gaps)를 피하기 위해서 Raft는 config 변경 전에 추가적인 단계를 도입하는데, 이 Phase에서 새 서버들이 투표권이 없는 멤버로 클러스터에 합류한다. (leader가 log entries를 복제하지만 대다수는 이를 고려하지 않는다.). 새 서버가 클러스터의 나머지 부분을 따라잡으면 위에서 설명한대로 reconfiguration이 진행된다.

 

두 번째 문제는 클러스터의 leader가 새 config의 일부가 아닐 수 있다는 점이다. 이 경우 leader는 C-new 로그 항목(entry)을 commit한 후 follower 상태로 복귀한다. (논문에서는 이를 Setps down으로 표현함) 즉, leader가 자신을 포함하지 않는 클러스터를 관리하는 동안(=C-new를 commit하는 동안) 일정한 시간이 걸린다. 로그는 복제하지만 자신을 과반수로 계산하지는 않는다. leader 전환은 C-new가 commit될때 이뤄지는데, 이는 새로운 config가 독립적으로 작동할 수 있는 첫 시점이기 때문이다. (항상 C-new에서 leader를 선택할 수 있다). 이 시점 이전에는 C-old에서 오는 서버만 leader로 선출될 수 있다.

 

마지막 문제는 제거된 서버(C-new에 있지 않아서 제거된)가 클러스터를 방해할 수 있다는 점이다. 이 서버들은 heartbeat를 받지 못해서 timeout되고 새로운 투표를 시작한다. 그 후 새로운 term 번호가 포함된 RequestVote RPC를 보내고서 현재 leader를 follower 상태로 만든다. 새로운 leader가 결국 선출되지만, 이미 제거된 서버들은 다시 timeout이 되는 과정이 반복되면서 시스템의 가용성을 저하시킨다. 이를 방지하기 위해서 서버는 현재 leader가 있다고 판단되면 RequestVote RPC를 무시한다. 구체적으로는 서버가 현재 leader로부터 신호를 받은 최소 electionTimeout 내에 RequestVote RPC를 받으면 term을 갱신하거나 투표권을 부여하지 않는다.

 

이는 각 서버가 최소 electionTimeout을 기다리는 일반적인 경우에는 영향을 미치지 않는다. 하지만 이미 제거된 서버로 인한 혼란을 방지하는데 도움이 된다. leader가 자신의 클러스터에 heartbeat를 전달할 수 있따면, 더 높은 term로 인해서 축출(deposed by)당하지 않는다.

 

6. Implementation and evaluation

나머지 생략. 이 세션은 understandability, correctness와 performance라는 기준으로 Raft를 평가한다.

  • Understandability는Paxos보다 얼마나 이해하기 쉬운지에 대해 입증, Correctness도 생략

6.1. Performance:

Raft의 성능은 Paxos와 같은 기존 합의 알고리즘과 유사하다. 가장 중요한 성능 구간은 기존 리더가 새로운 로그 항목을 복제할 때이다. Raft는 최소한의 메시지 수(Leader에서 클러스터 과반수까지 한번의 왕복 이동)으로 이를 달성한다. 또한 더 높은 처리량과 낮은 지연 시간을 위해서 배치 파이프라인 요청을 쉽게 지원해서 성능을 더욱 향상시킬 수도 있다.

 

우리는 Raft 구현을 사용해서 리더 선출 과정의 성능을 측정하고 두 가지 질문을 던졌다:

  1. 선출 과정이 빠르게 수렴되는가?
  2. 리더 선출 과정에서 충돌이 발생한 뒤에 최대 다운타임은 얼마나 되는가?

[충돌한 리더를 감지하고 교체하는 시간을 나타내는 두 그래프]

상단 그래프는 선출 timeout의 무작위성 크기를 나타내고, 아래는 최소 선출 timeout의 크기를 나타낸다.

 

특히 상단 그래프는 timeout에서 약간의 무작위화만 넣어도 선출시 표 분산되는걸 피하기 충분하다는 것을 입증한다. 무작위성이 없던 경우에는 많은 표가 분산되어서 리더 선출이 10초 이상 걸리는 경우가 많았는데, 단 5ms의 랜덤성만 추가해도 크게 개선되어 중간 다운타임이 287ms가 나왔다. 여기서 더 많은 무작위성을 사용하면 최악의 경우에 대한 행동이 크게 개선된다. 50ms 무작위성 추가시, 1000회 이상 시도에서 최악의 경우 513ms가 나왔다.

 

하단의 그래프는 리더 선출시 timeout을 줄임으로써 다운타임을 줄일 수 있음을 보여준다. timeout이 12ms에서 24ms로 간주되어, 리더 선출에 평균적으로 35ms가 걸린다. 최악의 경우 152ms. 하지만 이보다 더 줄이면 Raft의 타이밍 요구사항을 위반하게 된다. 새로운 리더를 선출할 투표를 시작하기 전에 heartbeat broadcast에 어려움을 겪기 때문에 불필요한 리더 교체나 전체 시스템 가용성 저하로 이어진다. 보수적으로 timeout을 150~300ms로 권장한다.

저작자표시 비영리 변경금지 (새창열림)