In Search of an Understandable Consensus Algorithm

1. Abstract

Raft는 복제된 로그를 관리하기 위한 합의 알고리즘으로, (멀티) Paxos와 동등한 결과를 제공합니다. Paxos와 동일한 효율성을 유지하면서도 구조적으로 다르게 설계되어 있어 더 이해하기 쉽습니다. 이러한 특성 덕분에 실용적인 시스템을 구축하는 데 있어 더 나은 기반을 제공합니다.

주요 특징

1. 이해 용이성:
   Raft는 합의의 주요 요소를 명확하게 분리하여 이해하기 쉽게 설계되었습니다. 주요 요소는 다음과 같습니다:

   • 리더 선출: 분산된 시스템 내에서 리더를 선택하는 과정입니다.
   • 로그 복제: 모든 노드에 로그를 일관되게 복제하여 시스템의 일관성을 유지합니다.
   • 안전성: 시스템의 정확성을 보장하고 충돌을 방지합니다.

2. 일관성 강화:
   Raft는 더 강한 일관성을 적용하여, 시스템이 고려해야 할 상태의 수를 줄입니다. 이를 통해 시스템의 복잡성을 낮추고 안정성을 높입니다.

3. 사용자 연구 결과:
   연구 결과에 따르면, Raft는 학생들이 Paxos보다 쉽게 배울 수 있는 것으로 나타났습니다. 이는 교육적 측면에서도 Raft의 우수성을 보여줍니다.

4. 클러스터 멤버십 변경:
   Raft는 중첩된 다수결을 사용하여 안전성을 보장하는 새로운 클러스터 멤버십 변경 메커니즘을 포함하고 있습니다. 이를 통해 클러스터 구성원 변경 시에도 시스템의 안전성을 유지할 수 있습니다.

2. Introduction

Raft는 기존 합의 알고리즘과 많은 면에서 유사하지만 (특히 Oki와 Liskov의 Viewstamped Replication과 유사함), 몇 가지 새로운 특징을 가지고 있습니다:

• 강력한 리더: Raft는 다른 합의 알고리즘보다 강력한 리더십을 사용합니다. 예를 들어, 로그 항목은 리더로부터 다른 서버로만 전송됩니다. 이는 복제 로그의 관리를 단순화하여 Raft를 이해하기 쉽게 만듭니다.
• 리더 선출: Raft는 리더를 선출하기 위해 랜덤화된 타이머를 사용합니다. 이는 기존에 필요한 하트비트에 약간의 메커니즘만 추가하며, 갈등을 간단하고 빠르게 해결합니다.
• 멤버십 변경: Raft의 클러스터 내 서버 세트를 변경하는 메커니즘은 새로운 공동 합의 접근 방식을 사용합니다. 이 과정에서 두 개의 다른 구성의 과반수가 전환 중에 겹쳐집니다. 이를 통해 구성 변경 중에도 클러스터가 정상적으로 운영될 수 있습니다.

3. Replicated state machines

복제 상태 기계는 합의 알고리즘이 주로 사용되는 맥락입니다. 여러 서버에 걸쳐 있는 상태 기계들이 동일한 상태의 복제본을 유지하며, 일부 서버가 고장 나더라도 시스템이 계속 운영될 수 있도록 합니다. 이는 분산 시스템에서 다양한 내결함성 문제를 해결하는 데 핵심적인 역할을 합니다.

복제 상태 기계의 예시

대규모 시스템에서는 주로 리더를 가진 단일 클러스터가 사용됩니다. 이러한 시스템은 별도의 복제 상태 기계를 사용하여 리더 선출을 관리하고, 리더가 충돌하더라도 중요한 구성 정보를 유지합니다. 다음은 복제 상태 기계의 몇 가지 예시입니다:

• GFS (Google File System)
• HDFS (Hadoop Distributed File System)
• RAMCloud

복제 상태 기계는 주로 Chubby와 ZooKeeper와 같은 시스템을 통해 구현됩니다.

복제 로그와 합의 알고리즘

복제 상태 기계는 일반적으로 복제 로그를 사용하여 구현됩니다. 각 서버는 일련의 명령을 포함하는 로그를 저장하고, 해당 서버의 상태 기계는 이러한 명령을 순서대로 실행합니다. 모든 서버의 로그는 동일한 명령을 동일한 순서로 포함하고 있어야 하며, 이를 통해 각 상태 기계는 동일한 명령 시퀀스를 처리하고 동일한 출력을 생성합니다.

• 결정론적 처리: 상태 기계는 결정론적으로 작동하여 동일한 상태와 출력을 유지합니다.

복제 로그의 일관성을 유지하는 것이 바로 합의 알고리즘의 주요 역할입니다. 합의 모듈은 클라이언트로부터 명령을 받아 로그에 추가하고, 다른 서버와의 통신을 통해 모든 로그가 동일한 요청을 동일한 순서로 포함하도록 보장합니다. 이는 서버의 일부가 고장 나더라도 이루어집니다.

합의 알고리즘의 핵심 속성

실용적인 시스템을 위한 합의 알고리즘은 다음과 같은 중요한 속성을 갖습니다:

• 안전성 보장: 비잔틴 장애가 아닌 모든 조건 하에서 안전성을 보장하며, 네트워크 지연, 파티션, 패킷 손실, 중복, 재정렬 등을 포함합니다.

• 가용성 보장: 서버 중 과반수가 작동 가능하고 서로 및 클라이언트와 통신할 수 있는 한 시스템은 완전한 기능을 유지합니다. 예를 들어, 5대의 서버 클러스터는 최대 2대의 서버 고장을 견딜 수 있습니다.

• 타이밍에 의존하지 않음: 로그의 일관성을 보장하기 위해 타이밍에 의존하지 않으며, 결함 있는 시계와 극심한 메시지 지연은 가용성 문제만 초래할 수 있습니다.

• 효율적인 명령 처리: 일반적으로, 클러스터의 과반수가 단일 원격 프로시저 호출에 응답하면 명령이 완료될 수 있으며, 소수의 느린 서버는 시스템 전체의 성능에 영향을 미치지 않습니다.

복제 상태 기계와 합의 알고리즘은 고도 신뢰성과 효율성을 제공하여 대규모 분산 시스템의 핵심 구성 요소로 사용됩니다. 이러한 알고리즘을 통해 서버들은 단일의 신뢰할 수 있는 상태 기계를 형성합니다.

4. What’s wrong with Paxos?

지난 10년 동안 Leslie Lamport의 Paxos 프로토콜은 합의 알고리즘의 거의 동의어가 되었습니다. Paxos는 가장 일반적으로 교육과정에서 가르쳐지고 있으며, 대부분의 합의 구현은 Paxos를 출발점으로 사용합니다. Paxos는 하나의 복제 로그 항목과 같은 단일 결정에 대한 합의에 도달할 수 있는 프로토콜을 처음 정의했습니다. 이를 단일 명령 Paxos라고 부릅니다. 이후 Paxos는 이 프로토콜의 여러 인스턴스를 결합하여 로그와 같은 일련의 결정을 용이하게 합니다 (멀티 Paxos). Paxos는 안전성과 생존성을 모두 보장하며, 클러스터 구성 변경을 지원합니다. 그 정확성이 입증되었으며, 일반적으로 효율적입니다.

Paxos의 두 가지 주요 문제점

1. 이해하기 어려움

Paxos의 첫 번째 문제점은 이해하기 매우 어렵다는 것입니다. Paxos를 더 쉽게 설명하려는 여러 시도가 있었지만 여전히 이해하기 어렵습니다. NSDI 2012 참가자들을 대상으로 한 비공식 설문조사에서는 경험이 많은 연구자들조차 Paxos에 대해 편안하게 느끼는 사람이 거의 없었습니다. 우리도 Paxos에 어려움을 겪었으며, 여러 번의 간단한 설명을 읽고 대안 프로토콜을 설계한 후에야 완전한 프로토콜을 이해할 수 있었습니다. 이 과정은 거의 1년이 걸렸습니다.

2. 실용적 구현의 기반 부족

Paxos의 두 번째 문제점은 실용적인 구현의 기반을 잘 제공하지 않는다는 것입니다. 그 이유 중 하나는 멀티 Paxos에 대한 널리 합의된 알고리즘이 없다는 점입니다. 또한 Paxos 아키텍처는 실용적인 시스템을 구축하기에 적합하지 않습니다.

Raft의 개발

이러한 문제들로 인해 Paxos는 시스템 구축이나 교육의 기반을 잘 제공하지 못한다고 결론지었습니다. 대규모 소프트웨어 시스템에서 합의의 중요성을 고려할 때, Paxos보다 더 나은 특성을 가진 대안 합의 알고리즘을 설계할 수 있을지 알아보기로 했습니다. Raft는 그 실험의 결과물입니다.

5. Designing for understandability

Raft의 설계 목표는 다음과 같습니다:

• 실용적 기반 제공: Raft는 시스템 구축을 위한 완전하고 실용적인 기반을 제공하여 개발자가 해야 할 설계 작업의 양을 크게 줄입니다.
• 안전성과 가용성: 모든 조건에서 안전성을 보장하며, 일반적인 운영 조건에서 가용성을 유지합니다.
• 효율성: 일반적인 작업에 대해 효율적이어야 합니다.

하지만 가장 중요한 목표이자 가장 어려운 도전은 이해 가능성입니다. Raft 알고리즘은 많은 사람들이 편안하게 이해할 수 있어야 합니다. 또한 시스템 구축자가 실제 구현에서 불가피한 확장을 할 수 있도록 알고리즘에 대한 직관을 개발할 수 있어야 합니다.

6. The Raft consensus algorithm

Raft는 먼저 구별되는 리더를 선출하고, 그 리더에게 복제 로그를 관리할 완전한 책임을 부여하여 합의를 구현합니다. 리더는 클라이언트로부터 로그 항목을 수신하고, 이를 다른 서버에 복제하며, 로그 항목을 상태 기계에 적용할 수 있을 때를 서버들에게 알려줍니다. 리더가 있는 것은 복제 로그의 관리를 단순화합니다. 예를 들어, 리더는 다른 서버와 협의 없이도 로그에 새로운 항목을 배치할 위치를 결정할 수 있으며, 데이터는 리더로부터 다른 서버로 간단하게 흐릅니다. 리더가 실패하거나 다른 서버와 연결이 끊어질 경우 새로운 리더가 선출됩니다.

합의 문제의 세 가지 하위 문제

리더 접근 방식을 바탕으로 Raft는 합의 문제를 세 가지 상대적으로 독립적인 하위 문제로 나누어 처리합니다.

1. 리더 선출: 리더를 선출하고, 시스템 내에서 리더가 안정적으로 유지되도록 합니다.

2. 로그 복제: 클라이언트로부터 수신한 로그 항목을 다른 서버에 복제하고, 일관성을 유지합니다.

3. 안전성 보장: 로그 항목이 올바르게 복제되고, 모든 서버가 동일한 상태를 유지하도록 보장합니다.

주요 RPC 호출

RequestVote RPC

리더 선출을 위해 후보자가 다른 서버의 투표를 얻기 위해 호출합니다.

• 인수:
  • term: 후보자의 임기
  • candidateId: 투표를 요청하는 후보자
  • lastLogIndex: 후보자의 마지막 로그 항목의 인덱스
  • lastLogTerm: 후보자의 마지막 로그 항목의 임기
• 결과:
  • term: 후보자가 자신을 업데이트하기 위한 현재 임기
  • voteGranted: 투표를 받은 경우 true

수신자 구현:
1. term < currentTerm이면 false를 반환합니다.
2. votedFor가 null이거나 candidateId이며, 후보자의 로그가 수신자의 로그와 같거나 최신인 경우, 투표를 승인합니다.

AppendEntries RPC

리더가 로그 항목을 복제하기 위해 호출하며, 하트비트로도 사용됩니다

• 인수:
  • term: 리더의 임기
  • leaderId: 팔로워가 클라이언트를 리다이렉션할 수 있도록 함
  • prevLogIndex: 새 항목 바로 앞의 로그 항목 인덱스
  • prevLogTerm: prevLogIndex 항목의 임기
  • entries[]: 저장할 로그 항목 (하트비트의 경우 비어 있음. 효율성을 위해 하나 이상 전송할 수 있음)
  • leaderCommit: 리더의 커밋 인덱스
• 결과:
  • term: 리더가 자신을 업데이트하기 위한 현재 임기
  • success: 팔로워가 일치하는 항목을 포함한 경우 true

수신자 구현:
1. term < currentTerm이면 false를 반환합니다.
2. prevLogIndex에 일치하는 항목이 없는 경우 false를 반환합니다.
3. 기존 항목이 새로운 항목과 충돌하는 경우 (같은 인덱스지만 다른 임기), 기존 항목과 그 뒤의 항목을 모두 삭제합니다 (§5.3).
4. 로그에 아직 없는 새 항목을 추가합니다.
5. leaderCommit > commitIndex인 경우, commitIndex를 min(leaderCommit, index of last new entry)로 설정합니다.

서버 상태

모든 서버:

• commitIndex > lastApplied이면 lastApplied를 증가시키고 log[lastApplied]를 상태 기계에 적용합니다.
• RPC 요청이나 응답이 term T > currentTerm을 포함하면 currentTerm = T로 설정하고 팔로워로 전환합니다.

팔로워:

• 후보자와 리더로부터의 RPC에 응답합니다.
• 현재 리더로부터 AppendEntries RPC를 받거나 후보자에게 투표를 승인하지 않고 선출 타임아웃이 만료되면 후보자로 전환합니다.

후보자:

• 후보자로 전환 시, 선거를 시작합니다:
  • currentTerm을 증가시킵니다.
  • 자신에게 투표합니다.
  • 선거 타이머를 재설정합니다.
  • 모든 다른 서버에 RequestVote RPC를 보냅니다.
  • 서버의 과반수로부터 투표를 받으면 리더가 됩니다.
  • 새로운 리더로부터 AppendEntries RPC를 받으면 팔로워로 전환합니다.
  • 선출 타임아웃이 만료되면 새로운 선거를 시작합니다.

리더:

• 선출 시: 초기 빈 AppendEntries RPC(하트비트)를 각 서버에 보내고, 유휴 기간 동안 반복하여 선출 타임아웃을 방지합니다.
• 클라이언트로부터 명령을 받으면 로컬 로그에 항목을 추가하고, 상태 기계에 항목이 적용된 후 응답합니다.
• 팔로워의 마지막 로그 인덱스가 nextIndex 이상이면, nextIndex부터 시작하는 로그 항목과 함께 AppendEntries RPC를 보냅니다.
• 성공하면 팔로워의 nextIndex와 matchIndex를 업데이트합니다.
• 로그 불일치로 인해 AppendEntries가 실패하면 nextIndex를 감소시키고 다시 시도합니다.
• N > commitIndex인 N이 존재하고, 과반수의 matchIndex[i] ≥ N이며, log[N].term == currentTerm인 경우 commitIndex = N으로 설정합니다.

Raft의 주요 속성

• 선거 안전성: 주어진 임기에는 최대 한 명의 리더만 선출될 수 있습니다 .
• 리더 추가 전용: 리더는 로그의 항목을 덮어쓰거나 삭제하지 않으며, 새로운 항목만 추가합니다.
• 로그 일치: 두 로그가 같은 인덱스와 임기를 가진 항목을 포함하면, 그 인덱스까지의 모든 항목이 동일합니다.
• 리더 완전성: 특정 임기에서 커밋된 로그 항목은 이후 모든 리더의 로그에 존재합니다.
• 상태 기계 안전성: 특정 인덱스의 로그 항목이 상태 기계에 적용되면, 다른 서버는 동일한 인덱스에 대해 다른 로그 항목을 적용할 수 없습니다.

7. Raft basics

Raft는 여러 서버로 구성된 클러스터로 운영됩니다. 보통 다섯 대의 서버로 구성되어 있으며, 이는 두 대의 서버 고장을 허용할 수 있는 구성입니다. 각 서버는 다음 세 가지 상태 중 하나에 속합니다: 리더(leader), 팔로워(follower), 후보자(candidate). 일반적으로 클러스터에는 한 명의 리더가 있으며, 나머지 서버는 팔로워입니다.

서버 상태

1. 팔로워(Follower):

   • 팔로워는 수동적으로 동작하며, 스스로 요청을 생성하지 않고 리더나 후보자로부터의 요청에만 응답합니다.
   • 클라이언트가 팔로워에게 요청을 보내면, 팔로워는 이를 리더에게 리다이렉트합니다.

2. 리더(Leader):

   • 리더는 모든 클라이언트 요청을 처리합니다.
   • 리더는 클러스터를 관리하며, 로그 항목을 다른 서버에 복제합니다.

3. 후보자(Candidate):

   • 리더를 선출하기 위해 후보자 상태로 전환됩니다.
   • 후보자가 과반수의 투표를 얻으면 새로운 리더가 됩니다.

시간의 구분: 임기(Term)

• Raft는 시간을 임기로 나누며, 각 임기는 순차적으로 증가하는 정수로 번호가 매겨집니다.
• 각 임기는 선거로 시작하며, 하나 이상의 후보자가 리더가 되기 위해 경쟁합니다.
• 선거가 성공적으로 끝나면 해당 임기 동안 리더가 클러스터를 관리합니다.
• 경우에 따라 선거가 무승부로 끝날 수 있으며, 이 경우 해당 임기는 리더 없이 종료됩니다.
• 새로운 임기가 시작되면 새로운 선거가 시작됩니다.

임기의 역할

• 임기는 Raft에서 논리적 시계의 역할을 하며, 서버들이 낡은 정보(예: 오래된 리더)를 감지하는 데 도움을 줍니다.
• 각 서버는 현재 임기 번호를 저장하며, 이는 시간이 지남에 따라 증가합니다.
• 서버들은 통신할 때마다 현재 임기를 교환합니다. 만약 한 서버의 현재 임기가 다른 서버보다 작다면, 그 서버는 임기를 더 큰 값으로 업데이트합니다.
• 후보자나 리더가 자신의 임기가 오래된 것을 발견하면 즉시 팔로워 상태로 돌아갑니다.
• 서버가 오래된 임기 번호를 포함한 요청을 받으면, 해당 요청을 거부합니다.

통신 방식: 원격 프로시저 호출(RPC)

• Raft 서버들은 원격 프로시저 호출(RPC)을 통해 통신합니다.
• 기본 합의 알고리즘에는 두 가지 종류의 RPC만 필요합니다:
  1. RequestVote RPC: 후보자가 선거 기간 동안 투표를 요청할 때 사용됩니다.
  2. AppendEntries RPC: 리더가 로그 항목을 복제하거나 하트비트를 제공할 때 사용됩니다.
• 서버는 응답을 제때 받지 못하면 RPC를 재시도하며, 최상의 성능을 위해 RPC를 병렬로 발행합니다.

8. Leader election

Raft는 하트비트(heartbeat) 메커니즘을 사용하여 리더 선출을 트리거합니다. 서버가 시작할 때, 모두 팔로워 상태로 시작합니다. 서버는 리더나 후보자로부터 유효한 RPC를 받는 동안 팔로워 상태를 유지합니다. 리더는 정기적으로 팔로워에게 하트비트(AppendEntries RPCs, 로그 항목을 포함하지 않음)를 보내 자신의 권한을 유지합니다. 만약 팔로워가 일정 시간 동안 통신을 받지 못하면, 이를 선출 타임아웃(election timeout)이라 부르며, 유효한 리더가 없다고 가정하고 새로운 리더를 선택하기 위해 선거를 시작합니다.

선거 과정

1. 팔로워에서 후보자로 전환:

   • 팔로워가 선거를 시작하기 위해 현재 임기를 증가시키고 후보자 상태로 전환합니다.
   • 자신에게 투표한 후, 클러스터 내 다른 서버들에 RequestVote RPC를 병렬로 보냅니다.

2. 선거 결과:

   • 선거 승리: 후보자가 클러스터의 과반수 서버로부터 투표를 받으면 선거에서 승리하고, 새로운 리더가 됩니다. 리더가 되면 다른 서버들에게 하트비트를 보내 자신의 권한을 확립하고 새로운 선거가 발생하지 않도록 합니다.
   • 다른 서버가 리더로 확립: 후보자는 다른 서버로부터 자신이 리더라고 주장하는 AppendEntries RPC를 받을 수 있습니다. 이때 해당 리더의 임기가 후보자의 현재 임기보다 크거나 같다면 후보자는 리더를 합법적인 리더로 인식하고 팔로워 상태로 돌아갑니다.
   • 무승부: 많은 팔로워가 동시에 후보자가 되면, 투표가 나뉘어 어떤 후보자도 과반수를 얻지 못할 수 있습니다. 이런 경우 각 후보자는 타임아웃이 지나면 임기를 증가시키고 새로운 선거를 시작합니다.

무승부 해결: 랜덤화된 선거 타임아웃

• 무승부 방지: Raft는 무승부를 방지하기 위해 랜덤화된 선거 타임아웃을 사용합니다. 선거 타임아웃은 고정된 간격(예: 150–300ms) 내에서 무작위로 선택됩니다. 이렇게 하면 대부분의 경우 하나의 서버만 타임아웃이 발생하고, 그 서버가 선거에서 승리하여 다른 서버가 타임아웃이 되기 전에 하트비트를 보냅니다.
• 무승부 해결: 각 후보자는 선거가 시작될 때 랜덤화된 선거 타임아웃을 다시 시작하며, 다음 선거를 시작하기 전까지 타임아웃이 끝날 때까지 기다립니다. 이렇게 하면 새로운 선거에서 무승부가 다시 발생할 가능성이 줄어듭니다.

9. Log replication

리더의 역할

1. 클라이언트 요청 처리:

   • 리더가 선출되면 클라이언트의 요청을 처리합니다.
   • 각 요청은 상태 기계가 실행할 명령을 포함합니다.
   • 리더는 요청을 로그에 새로운 항목으로 추가하고, 각 팔로워에게 AppendEntries RPC를 통해 이를 복제합니다.

2. 로그 항목의 커밋:

   • 로그 항목이 안전하게 복제되면, 리더는 이를 상태 기계에 적용하고 클라이언트에게 결과를 반환합니다.
   • 팔로워가 충돌하거나 느리게 실행되거나 네트워크 패킷이 손실될 경우, 리더는 AppendEntries RPC를 계속해서 시도하여 결국 모든 팔로워가 모든 로그 항목을 저장하도록 합니다.

로그의 구조

• 각 로그 항목은 상태 기계 명령과 리더가 해당 항목을 받은 임기를 저장합니다.
• 로그 항목의 임기는 로그 간의 불일치를 감지하고, Raft의 여러 속성을 보장하는 데 사용됩니다.
• 각 로그 항목은 로그 내에서 위치를 식별하는 정수 인덱스를 가집니다.

커밋의 정의와 보장

• 로그 항목은 리더가 해당 항목을 과반수의 서버에 복제한 후에 커밋됩니다.
• 리더는 커밋된 로그 항목의 가장 높은 인덱스를 추적하며, 향후 AppendEntries RPC(하트비트 포함)에 이 인덱스를 포함시켜 다른 서버들이 이를 알도록 합니다.
• 팔로워가 로그 항목이 커밋된 것을 알게 되면, 해당 항목을 로컬 상태 기계에 적용합니다.

로그 일치 속성

Raft는 다른 서버의 로그와의 일관성을 유지하기 위해 다음 속성을 보장합니다:

• 서로 다른 로그에서 같은 인덱스와 임기를 가진 두 항목은 동일한 명령을 저장합니다.
• 같은 인덱스와 임기를 가진 두 항목이 있는 경우, 이전 항목은 모두 동일합니다.

불일치 해결

• 리더는 AppendEntries RPC를 사용하여 팔로워 로그의 불일치를 해결합니다.
• 리더는 자신의 로그와 일치하는 지점을 찾고, 그 이후의 팔로워 로그 항목을 삭제한 후, 자신의 로그를 보냅니다.
• AppendEntries RPC가 성공하면, 팔로워의 로그는 리더의 로그와 일치하게 됩니다.

최적화

• AppendEntries 요청이 거부될 때, 팔로워는 충돌하는 항목의 임기와 해당 임기의 첫 인덱스를 포함하여 보낼 수 있습니다.
• 이를 통해 리더는 nextIndex를 조정하여 충돌하는 항목을 우회할 수 있습니다.

성능 및 일관성

• Raft는 과반수의 서버가 작동하는 한 새로운 로그 항목을 수용, 복제, 적용할 수 있습니다.
• 일반적으로 새로운 항목은 과반수의 클러스터에 대한 단일 RPC 라운드로 복제됩니다.
• 느린 팔로워 한 명이 성능에 영향을 미치지 않습니다.

10. Safety

이전 섹션에서는 리더를 선출하고 로그 항목을 복제하는 방법을 설명했습니다. 하지만 상태 기계가 동일한 명령을 동일한 순서로 정확히 실행하도록 보장하기 위해서는 추가적인 메커니즘이 필요합니다. 예를 들어, 팔로워가 여러 로그 항목이 커밋되는 동안 사용 불가능 상태였다가 리더로 선출되면서 기존 로그를 덮어쓰는 경우, 서로 다른 상태 기계가 다른 명령 시퀀스를 실행할 수 있습니다.

리더 선출에 대한 제한

Raft는 어떤 서버가 리더로 선출될 수 있는지에 대한 제한을 추가하여 이 문제를 해결합니다. 이 제한은 주어진 임기의 리더가 이전 임기의 모든 커밋된 항목을 포함하도록 보장합니다. 이를 통해 리더의 완전성 속성(Leader Completeness Property)이 유지됩니다.

1. 리더 완전성 속성:

   • 모든 새로운 리더는 선출될 때 이전 임기의 모든 커밋된 항목을 포함해야 합니다.
   • 로그 항목은 리더로부터 팔로워로만 전달되며, 리더는 기존 항목을 덮어쓰지 않습니다.

2. 투표 과정:

   • 후보자가 선출되기 위해서는 클러스터의 과반수와 접촉해야 하며, 이는 모든 커밋된 항목이 과반수 서버에 존재해야 함을 의미합니다.
   • RequestVote RPC는 후보자의 로그에 대한 정보를 포함하고, 만약 투표자의 로그가 더 최신이면 투표를 거부합니다.

3. 로그의 최신성 판단:

   • 두 로그 중 하나가 더 최신인지 판단하려면 마지막 항목의 인덱스와 임기를 비교합니다.
   • 만약 로그의 마지막 항목이 다른 임기를 가진다면, 임기가 더 나중인 로그가 더 최신입니다.
   • 로그가 동일한 임기로 끝나면, 로그의 길이가 긴 쪽이 더 최신입니다.

이전 임기에서의 로그 항목 커밋

• 리더는 자신의 임기에서 로그 항목이 과반수의 서버에 저장되면 그 항목이 커밋되었다고 간주합니다.
• 리더가 항목을 커밋하기 전에 충돌하면, 이후 리더들이 해당 항목의 복제를 완료하려고 시도합니다.
• 그러나 이전 임기의 항목은 과반수 서버에 저장되었더라도 즉시 커밋되었다고 간주할 수 없습니다.

안전성 주장

리더의 완전성 속성이 유지된다는 것을 논리적으로 설명할 수 있습니다.

1. 모순 가정:

   • 임기 T의 리더가 그 임기의 로그 항목을 커밋했지만, 나중의 어떤 임기 U의 리더가 그 항목을 저장하지 않았다고 가정합니다.

2. 리더의 행동:

   • 임기 T의 리더는 그 항목을 클러스터의 과반수에 복제했으며, 임기 U의 리더는 과반수의 투표를 받았습니다.
   • 따라서 최소한 하나의 서버는 임기 T의 항목을 받아들였고, 임기 U의 리더에게 투표를 했습니다.

3. 투표 서버의 상태:

   • 투표 서버는 임기 U의 리더에게 투표하기 전에 임기 T의 항목을 받아들였어야 합니다.
   • 투표 서버는 임기 U의 리더에게 투표할 때 그 항목을 여전히 저장하고 있어야 합니다.

4. 모순 해결:

   • 임기 U의 리더의 로그가 투표 서버의 로그와 동일하거나 더 최신이어야 합니다.
   • 이는 임기 U의 리더가 임기 T의 항목을 포함해야 한다는 것을 의미하며, 초기 가정과 모순됩니다.

5. 결론:

   • 임기 T 이후의 모든 리더는 임기 T에서 커밋된 모든 항목을 포함해야 합니다.

상태 기계의 안전성

• 상태 기계 안전성 속성은 서버가 주어진 인덱스의 로그 항목을 상태 기계에 적용할 때, 다른 서버가 동일한 인덱스에 대해 다른 로그 항목을 적용하지 않도록 보장합니다.
• 로그 인덱스 순서대로 항목을 적용하도록 함으로써 모든 서버가 동일한 순서로 동일한 로그 항목을 상태 기계에 적용하게 됩니다.

11. Follower and candidate crashes

이전까지는 리더의 장애에 대해 중점적으로 다루었지만, 팔로워와 후보자의 장애는 훨씬 간단하게 처리할 수 있습니다. Raft에서는 팔로워와 후보자가 충돌했을 때 이를 처리하는 방법은 동일합니다.

팔로워 및 후보자 장애 처리

1. RPC 재시도:

   • 팔로워나 후보자가 충돌하면, 해당 서버로 보내는 RequestVote와 AppendEntries RPC가 실패합니다.
   • Raft는 이러한 실패를 무한히 재시도하여 충돌한 서버가 다시 시작되면 RPC가 성공적으로 완료됩니다.

2. 서버 재시작:

   • 서버가 RPC를 완료한 후 응답하기 전에 충돌하면, 서버가 재시작된 후에 동일한 RPC를 다시 수신하게 됩니다.
   • Raft RPC는 멱등성(idempotent)을 가지므로, 동일한 RPC를 여러 번 받아도 문제가 발생하지 않습니다.

3. 예시:

   • 팔로워가 AppendEntries 요청을 받았을 때, 이미 로그에 있는 항목이 요청에 포함되어 있으면 새로운 요청에서는 해당 항목을 무시합니다. 이는 멱등성을 통해 가능해지며, 시스템의 일관성을 유지할 수 있도록 돕습니다.

멱등성(Idempotency)

• 멱등성은 같은 작업을 여러 번 수행하더라도 결과가 동일하게 유지되는 특성을 의미합니다.
• Raft의 RPC는 멱등성을 보장하여, 서버가 충돌하고 다시 시작하더라도 요청을 안전하게 처리할 수 있도록 합니다.

결론

• 리더 장애에 비해 팔로워와 후보자의 장애는 처리하기가 간단합니다.
• Raft는 RPC의 멱등성을 활용하여 서버 충돌로 인한 일관성 문제를 해결하고, 시스템 안정성을 높입니다.

12. Timing and availability

Raft의 요구사항 중 하나는 안전성이 타이밍에 의존하지 않아야 한다는 것입니다. 시스템은 어떤 이벤트가 예상보다 빠르거나 느리게 발생하더라도 잘못된 결과를 초래하지 않아야 합니다. 그러나 가용성(클라이언트 요청에 대한 시스템의 응답 능력)은 불가피하게 타이밍에 의존합니다. 예를 들어, 메시지 교환이 서버 충돌 간의 평균 시간보다 오래 걸리면 후보자가 선출될 만큼 충분히 오래 지속되지 못할 수 있으며, 안정적인 리더가 없으면 Raft는 진행할 수 없습니다.

리더 선출과 타이밍

리더 선출은 Raft에서 타이밍이 가장 중요한 부분입니다. 시스템이 다음과 같은 타이밍 요구 사항을 만족하는 한, Raft는 리더를 선출하고 유지할 수 있습니다:

• broadcastTime: 서버가 클러스터 내 모든 서버에게 RPC를 병렬로 보내고 응답을 받는 데 걸리는 평균 시간입니다.
• electionTimeout: 선거 타임아웃으로, 리더가 없을 때 새로운 리더를 선출하기 위해 후보자가 기다리는 시간입니다.
• MTBF (Mean Time Between Failures): 단일 서버의 평균 고장 간격입니다.

중요한 2가지 사항

• broadcastTime은 선거 타임아웃보다 훨씬 짧아야 합니다. 이렇게 하면 리더가 팔로워가 선거를 시작하지 않도록 필요한 하트비트를 안정적으로 보낼 수 있습니다. 또한 랜덤화된 선거 타임아웃을 사용하여 무승부 가능성을 줄입니다.
• electionTimeout은 MTBF보다 몇 배 더 짧아야 합니다. 이렇게 하면 시스템이 안정적으로 진행할 수 있습니다. 리더가 실패할 경우 시스템은 약간의 선거 타임아웃 동안 사용 불가능한 상태가 되지만, 이는 전체 시간 중 작은 부분에 불과해야 합니다.

13. Cluster membership changes

Raft는 클러스터 구성이 고정되어 있다고 가정하지만, 실제로는 서버를 교체하거나 복제 수준을 변경하기 위해 구성을 변경해야 할 때가 있습니다. 클러스터를 오프라인 상태로 두고 구성 파일을 업데이트한 후 클러스터를 다시 시작할 수 있지만, 이는 변경 중에 클러스터를 사용할 수 없게 만들고 수동으로 작업할 경우 운영자의 실수 위험이 있습니다. 이러한 문제를 피하기 위해, Raft는 구성 변경을 자동화하고 이를 합의 알고리즘에 통합했습니다.

안전한 구성 변경을 위한 두 단계 접근법

구성 변경 메커니즘이 안전하려면, 전환 중에 동일한 임기에 두 리더가 선출될 가능성이 없어야 합니다. 서버가 직접 이전 구성에서 새 구성으로 전환하는 방법은 안전하지 않습니다. 모든 서버를 한 번에 원자적으로 전환할 수 없기 때문에, 클러스터가 전환 중에 두 개의 독립적인 과반수로 분할될 수 있습니다.

안전성을 보장하기 위해, 구성 변경은 두 단계 접근법을 사용해야 합니다:

1. 공동 합의 단계:

   • 첫 번째 단계에서는 이전 구성과 새 구성 모두를 포함하는 중간 구성을 사용합니다.
   • 로그 항목은 두 구성의 모든 서버에 복제됩니다.
   • 이전 구성과 새 구성의 별도 과반수가 선거와 항목 커밋에 필요합니다.
   • 공동 합의를 통해 서버들이 서로 다른 시간에 전환할 수 있도록 하면서도 안전성을 보장합니다.
   • 이 과정 동안 클러스터는 클라이언트 요청을 계속 처리할 수 있습니다.

2. 새 구성으로 전환:

   • 리더가 요청을 받아 구성 변경을 시작하면, 공동 합의 구성을 로그 항목으로 저장하고 이를 복제합니다.
   • 공동 합의가 커밋되면, 리더는 새 구성을 설명하는 로그 항목을 만들어 클러스터에 복제합니다.
   • 새 구성이 Cnew 규칙에 따라 커밋되면, 이전 구성은 더 이상 중요하지 않으며 새로운 구성에 포함되지 않은 서버는 종료될 수 있습니다.

구성 변경 시 고려 사항

1. 새 서버 추가:

   • 새 서버는 초기 로그 항목을 저장하지 않을 수 있습니다. 이 경우, 클러스터에 추가되면 따라잡는 데 시간이 걸릴 수 있으며, 이 동안 새로운 로그 항목을 커밋하지 못할 수 있습니다.
   • Raft는 새로운 서버를 투표하지 않는 멤버로 클러스터에 먼저 추가하는 단계를 도입하여 이 문제를 해결합니다. 이들은 로그 항목을 복제받지만 과반수로 고려되지 않습니다.

2. 리더의 포함 여부:

   • 리더가 새 구성에 포함되지 않을 경우, Cnew 로그 항목을 커밋한 후 팔로워 상태로 돌아갑니다.
   • 리더 전환은 Cnew가 커밋될 때 발생하며, 이때 새로운 구성은 독립적으로 작동할 수 있습니다.

3. 제거된 서버의 방해:

   • 제거된 서버는 하트비트를 받지 않으므로 타임아웃이 발생하고 새로운 선거를 시작할 수 있습니다. 이들은 새로운 임기로 RequestVote RPC를 보내어 현재 리더를 팔로워 상태로 되돌릴 수 있습니다.
   • 이러한 문제를 방지하기 위해, 서버는 현재 리더가 존재한다고 생각할 때 RequestVote RPC를 무시합니다. 구체적으로, 서버가 현재 리더로부터 하트비트를 받은 후 최소 선거 타임아웃 내에 RequestVote RPC를 받으면 임기를 업데이트하거나 투표하지 않습니다.

14. Log compaction

Raft의 로그는 정상적인 운영 동안 클라이언트 요청을 수용하면서 성장하지만, 시스템이 계속해서 운영되려면 로그가 무한정 커질 수는 없습니다. 로그가 길어지면 공간을 많이 차지하고 재생하는 데 시간이 오래 걸리며, 결국 가용성 문제를 일으킬 수 있습니다. 이를 해결하기 위해 Raft는 오래된 정보를 삭제하는 메커니즘이 필요합니다.

스냅샷(Snapshotting) 방법

스냅샷은 로그 압축의 가장 간단한 방법입니다. 스냅샷은 시스템의 현재 상태를 안정적인 저장소에 기록한 다음 해당 시점까지의 전체 로그를 삭제하는 것입니다. Chubby와 ZooKeeper에서도 스냅샷 방식을 사용합니다. Raft에서의 스냅샷 작동 방식을 설명하면 다음과 같습니다:

• 스냅샷의 개념:
  • 각 서버는 독립적으로 스냅샷을 생성하며, 로그의 커밋된 항목만 포함합니다.
  • 스냅샷에는 상태 기계의 현재 상태와 로그의 마지막 포함 인덱스 및 임기 등의 메타데이터가 포함됩니다.
  • 서버가 스냅샷 작성을 완료하면, 마지막 포함 인덱스까지의 로그 항목과 이전 스냅샷을 삭제할 수 있습니다.

스냅샷 전송

리더는 때때로 뒤처진 팔로워에게 스냅샷을 전송해야 할 필요가 있습니다. 이는 리더가 팔로워에게 보내야 할 다음 로그 항목을 이미 삭제했을 때 발생합니다. 이 문제를 해결하기 위해 리더는 InstallSnapshot RPC를 사용하여 스냅샷을 전송합니다.

• InstallSnapshot RPC:
  • 리더는 스냅샷을 청크로 나누어 팔로워에게 전송합니다.
  • 팔로워가 스냅샷을 받으면 기존 로그 항목을 처리하는 방법을 결정해야 합니다.
  • 일반적으로 스냅샷이 새로운 정보를 포함하면 팔로워는 전체 로그를 삭제합니다.
  • 스냅샷이 로그의 접두사를 설명할 경우, 해당 로그 항목은 삭제되지만 스냅샷 이후의 항목은 유지해야 합니다.

스냅샷 관리

Raft의 스냅샷 방식은 강력한 리더 원칙에서 벗어납니다. 왜냐하면 팔로워가 리더의 승인 없이 스냅샷을 생성할 수 있기 때문입니다. 하지만 스냅샷이 이미 합의된 데이터를 포함하기 때문에 데이터의 일관성을 해치지 않습니다.

• 팔로워 주도 방식의 이점:
  • 팔로워가 자신의 로컬 상태를 바탕으로 스냅샷을 생성하는 것이 네트워크 대역폭을 절약하고 더 효율적입니다.
  • 리더가 스냅샷을 생성하고 팔로워에게 전송하는 것은 네트워크 대역폭 낭비와 구현 복잡성을 초래할 수 있습니다.

성능 고려사항

1. 스냅샷 빈도 결정:

   • 너무 자주 스냅샷을 생성하면 디스크 대역폭과 에너지를 낭비합니다.
   • 너무 드물게 생성하면 스토리지 용량을 초과하거나 재시작 시 로그 재생 시간이 증가할 수 있습니다.
   • 간단한 전략은 로그가 특정 크기에 도달할 때마다 스냅샷을 생성하는 것입니다.

2. 스냅샷 생성 중 운영 지속:

   • 스냅샷 작성은 시간이 걸릴 수 있으며, 이로 인해 정상적인 운영이 지연되지 않도록 해야 합니다.
   • 새로운 업데이트가 스냅샷 작성에 영향을 주지 않도록 카피 온 라이트(Copy-on-write) 기술을 사용합니다.
   • 예를 들어, 운영 체제의 카피 온 라이트 지원(fork와 같은)을 사용하여 전체 상태 기계의 메모리 내 스냅샷을 생성할 수 있습니다.

15. Client interaction

이 섹션에서는 Raft와 클라이언트 간의 상호작용, 클라이언트가 클러스터 리더를 찾는 방법을 설명합니다.

리더 찾기

1. 초기 연결:

   • 클라이언트는 모든 요청을 리더에게 보냅니다.
   • 클라이언트가 처음 시작하면 무작위로 선택한 서버에 연결합니다.
   • 만약 첫 번째 선택이 리더가 아니라면, 해당 서버는 클라이언트의 요청을 거부하고 최근에 들은 리더에 대한 정보를 제공합니다(리더의 네트워크 주소가 포함된 AppendEntries 요청을 통해).

2. 리더 장애:

   • 리더가 충돌하면 클라이언트 요청은 시간 초과됩니다. 그런 다음 클라이언트는 무작위로 선택한 서버와 다시 시도합니다.

16. Implementation and evaluation

Raft는 RAMCloud의 구성 정보 저장 및 코디네이터 장애 조치를 지원하는 복제 상태 기계의 일부로 구현되었습니다. Raft 구현은 약 2000줄의 C++ 코드로 구성되어 있으며, 테스트, 주석, 빈 줄은 포함하지 않습니다. 소스 코드는 자유롭게 사용할 수 있으며, 약 25개의 독립적인 서드파티 오픈 소스 Raft 구현이 다양한 개발 단계에 있습니다. 여러 회사에서도 Raft 기반 시스템을 배포하고 있습니다.

Raft를 평가하기 위해 다음 세 가지 기준을 사용했습니다: 이해 용이성, 정확성, 성능.

이해 용이성

Raft의 이해 용이성을 Paxos와 비교하기 위해, 우리는 스탠포드 대학교의 고급 운영 체제 과정과 U.C. 버클리의 분산 컴퓨팅 과정에 참여한 상급 학부 및 대학원생을 대상으로 실험적 연구를 수행했습니다. 우리는 Raft와 Paxos에 대한 강의 영상을 녹화하고, 각각의 퀴즈를 만들었습니다. Raft 강의는 로그 압축을 제외한 논문의 내용을 다뤘으며, Paxos 강의는 단일 명령 Paxos, 다중 명령 Paxos, 재구성 및 몇 가지 실용적인 최적화를 포함한 내용으로, 동등한 복제 상태 기계를 생성할 수 있도록 하였습니다.

참가자들은 각 영상 시청 후 대응되는 퀴즈를 풀었으며, 절반은 Paxos를 먼저 배우고 나머지 절반은 Raft를 먼저 배우도록 하여 개인의 성과 차이와 학습 경험의 영향을 고려했습니다. 우리는 참가자들의 점수를 비교하여 Raft에 대한 이해도가 Paxos보다 높은지 확인했습니다.

평가 결과:

• 참가자들은 Raft 퀴즈에서 평균 4.9점 더 높은 점수를 받았습니다(60점 만점). Raft의 평균 점수는 25.7점, Paxos는 20.8점이었습니다.
• 쌍체 t-검정 결과 95% 신뢰 수준에서 Raft 점수의 평균이 Paxos 점수보다 최소 2.5점 이상 높다는 결과를 보였습니다.
• 회귀 모델은 Raft와 Paxos의 퀴즈 선택이 12.5점 차이를 예측했습니다. 실제 차이는 4.9점이었으며, 이는 Paxos에 대한 사전 경험이 있는 학생들이 Paxos 점수를 높인 결과입니다.

참가자 의견:

• 참가자들의 대다수(41명 중 33명)는 Raft가 구현과 설명이 더 쉽다고 답변했습니다. 그러나 이러한 의견은 참가자들의 퀴즈 점수보다는 덜 신뢰할 수 있습니다.

정확성

Raft의 합의 메커니즘에 대해 공식 명세와 안전성 증명을 개발했습니다. 공식 명세는 TLA+ 명세 언어를 사용하여 약 400줄로 이루어져 있으며, 구현을 위한 유용한 자료입니다. TLA 증명 시스템을 통해 로그 완전성 속성을 기계적으로 증명했지만, 타입 안전성과 같은 불변량은 기계적으로 검증되지 않았습니다. 우리는 상태 기계 안전성에 대한 비공식적인 증명도 작성했으며, 이는 3500단어 길이로 상대적으로 정밀합니다.

성능

Raft의 성능은 Paxos와 같은 다른 합의 알고리즘과 유사합니다. 성능 측면에서 가장 중요한 경우는 리더가 새로운 로그 항목을 복제하는 경우입니다. Raft는 클러스터의 절반에 대한 리더와의 단일 왕복 메시지로 이 작업을 최소한의 메시지로 수행합니다.

성능 평가:

• 리더 선출 프로세스가 빠르게 수렴하는지와 리더 충돌 후 최소 다운타임을 측정하기 위해 Raft 구현을 사용했습니다.
• 리더가 충돌할 때까지 반복적으로 클러스터의 리더를 충돌시켜 충돌을 감지하고 새로운 리더를 선출하는 데 걸리는 시간을 측정했습니다.
• 랜덤성이 없는 경우 선출이 10초 이상 걸렸으나, 5ms의 랜덤성을 추가하면 다운타임의 중앙값이 287ms로 감소했습니다.
• 선출 타임아웃을 줄이면 다운타임도 감소했습니다. 12–24ms의 타임아웃에서는 평균 35ms, 가장 긴 경우 152ms가 소요되었습니다. 그러나 타임아웃을 지나치게 줄이면 불필요한 리더 변경과 시스템 가용성 저하를 초래할 수 있습니다.

추천 타임아웃:

• 150–300ms의 보수적인 선출 타임아웃을 추천하며, 이는 불필요한 리더 변경을 방지하고 양호한 가용성을 제공합니다.

17. Related work

Raft와 관련된 여러 연구 및 알고리즘이 있습니다. 이들은 주로 다음과 같은 범주로 나눌 수 있습니다.

1. Paxos의 설명과 개선:

   • Lamport의 Paxos 원래 설명과 이를 명확히 설명하려는 시도들이 있습니다.
   • Paxos를 보완하여 구현의 기초를 제공하려는 다양한 시도들이 있습니다.

2. 합의 알고리즘을 구현한 시스템:

   • Chubby, ZooKeeper, Spanner 등은 합의 알고리즘을 구현한 시스템들입니다. Chubby와 Spanner는 Paxos를 기반으로 하지만, 자세한 알고리즘이 공개되지 않았습니다. ZooKeeper의 알고리즘은 Paxos와 상당히 다릅니다.

3. Paxos의 성능 최적화:

   • Paxos의 성능을 향상시키기 위한 여러 최적화 방법들이 제안되었습니다.

4. Oki와 Liskov의 Viewstamped Replication (VR):

   • Paxos와 비슷한 시기에 개발된 합의 알고리즘으로, 리더 기반 접근 방식을 사용하며 Raft와 많은 유사점을 가집니다.

Raft와 다른 알고리즘의 비교

• 강력한 리더십:

  • Raft의 가장 큰 특징은 강력한 리더십으로, 리더 선출이 합의 프로토콜의 필수 부분으로 포함되어 있습니다. 리더가 가능한 많은 기능을 집중적으로 수행합니다.
  • Paxos는 리더 선출이 기본 합의 프로토콜과 독립적이며, 성능 최적화에 불과합니다. Paxos는 기본 합의와 리더 선출을 위한 별도의 메커니즘을 포함하여 더 복잡합니다.

• 다른 리더 기반 시스템과의 비교:

  • VR과 ZooKeeper도 리더 기반이지만, Raft는 비리더 기능을 최소화하여 메커니즘을 단순화합니다.
  • VR과 ZooKeeper는 로그 항목이 리더와 팔로워 간에 양방향으로 전달되는 반면, Raft는 단방향(리더에서 팔로워로)으로만 전달됩니다.

• 메시지 유형:

  • Raft는 알려진 다른 합의 기반 로그 복제 알고리즘보다 적은 메시지 유형을 사용합니다. VR과 ZooKeeper는 각각 10개의 메시지 유형을 정의하는 반면, Raft는 4개(두 개의 RPC 요청과 그에 대한 응답)만 사용합니다.

성능 최적화

• EPaxos:
  • EPaxos는 리더 없이 작동하여 특정 조건에서 더 높은 성능을 달성할 수 있습니다. 하지만 이는 Paxos의 복잡성을 증가시킵니다.

클러스터 멤버십 변경

• 다양한 접근 방식:
  • Lamport의 원래 제안, VR, SMART 등 다양한 접근 방식이 제안되었습니다.
  • Raft는 합의 프로토콜의 나머지 부분을 활용하여 공동 합의 접근 방식을 채택했습니다. 이는 멤버십 변경을 위한 추가 메커니즘이 거의 필요 없습니다.
  • VR은 구성 변경 중에 모든 정상 처리 작업을 중지하며, SMART는 대기 중인 요청 수에 제한을 둡니다. Raft는 이러한 제한 없이 멤버십 변경을 처리할 수 있습니다.

18. Conclusion

알고리즘은 주로 정확성, 효율성, 간결성을 목표로 설계됩니다. 이러한 목표들은 중요하지만, 우리는 이해 가능성도 그에 못지않게 중요하다고 믿습니다. 다른 목표들은 개발자가 알고리즘을 실용적인 구현으로 변환할 때까지 달성될 수 없으며, 이 과정에서 구현은 출판된 형태와 다소 차이가 생기고 확장될 것입니다. 개발자가 알고리즘을 깊이 이해하고 직관적으로 활용할 수 없다면, 구현에서 알고리즘의 바람직한 속성을 유지하기 어렵습니다.

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

이해 가능성을 주된 설계 목표로 삼으면서 Raft 설계를 접근한 방식이 달라졌습니다. 설계가 진행됨에 따라 문제를 분해하고 상태 공간을 단순화하는 몇 가지 기법을 반복적으로 사용하게 되었습니다. 이러한 기법은 Raft의 이해 가능성을 높였을 뿐만 아니라, 알고리즘의 정확성을 확신하는 데에도 기여했습니다.