raft 논문

  • 간단히 구글번역기를 돌린 것을 기반하고, 그중 매우 소량만 수정하였다. pull req 환영,
  • 현재 5.3까지 번역기를 돌려놓음
  • 원문: https://raft.github.io/raft.pdf

1. 소개

컨센서스 알고리즘 (Consensus Algorithm)은 기계 모음이 일부 구성원의 실패에서도 견딜 수있는 일관된 그룹으로 작동 할 수 있도록합니다. 이 때문에 신뢰할 수있는 대규모 소프트웨어 시스템을 구축하는 데 중요한 역할을합니다. Paxos [15,16]는 지난 10 년 동안 합의 알고리즘에 대한 논의를 주도 해왔다. 대부분의 구현 의 합의는 Paxos에 기초하거나 Paxos에 의해 영향을 받았으며 Paxos는 학생들에게 합의에 대해 가르치는 데 사용 된 주요 수단이되었습니다. 불행히도 Paxos는 더 쉽게 접근 할 수있는 수많은 시도에도 불구하고 이해하기가 어렵습니다. 또한 아키텍처는 실제 시스템을 지원하기 위해 복잡한 변경이 필요합니다. 결과적으로, 시스템 빌더와 학생 모두 Paxos와의 투쟁을합니다.

우리는 Paxos와의 고심 끝에 시스템 구축과 교육을위한 더 나은 토대를 제공 할 수있는 새로운 합의 알고리즘을 발견했습니다.

우리의 접근 방식은 일차 목표가 이해하기 쉽다는 점에서 특이한 것이 었습니다. 실용적인 시스템에 대한 합의 알고리즘을 정의하고 Paxos보다 훨씬 쉽게 배우는 방식으로 기술 할 수 있었습니까?

또한, 우리는 알고리즘이 직관의 개발을 촉진하기를 원했습니다. 시스템 빌더에게 필수적입니다. 알고리즘이 작동하는 것이 아니라 작동하는 이유가 명확해야한다는 것이 중요했습니다.

이 작업의 결과는 Raft라고하는 컨센서스 알고리즘입니다. Raft는 분해 (래프 트가 리더 선출, 로그 복제 및 안전을 분리) 및 상태 공간 감소 (Paxos와 관련하여 Raft는 비 결정론의 정도를 줄이고 서버가 서로 불일치 할 수있는 방식을 포함하여 이해력을 향상시키기 위해 특정 기술을 적용했습니다 ). 두 대학의 43 명의 학생을 대상으로 한 사용자 조사에 따르면 Raft은 Paxos보다 훨씬 이해하기 쉽습니다. 두 알고리즘을 모두 습득 한 후 33 명의 학생들이 Paxos에 관한 질문보다 Raft에 관한 질문에 더 잘 답할 수있었습니다. Raft은 여러 가지면에서 기존의 합의 알고리즘 (가장 주목할만한 것은 Oki and Liskov의 Viewstamped Replication [29, 22])과 유사하지만 몇 가지 새로운 기능이 있습니다.

• 강력한 리더 : Raft은 다른 합의 알고리즘보다 더 강력한 리더십을 사용합니다. 예를 들어, 로그 항목은 리더에서 다른 서버로 만 흐릅니다. 이렇게하면 복제 된 로그의 관리가 단순 해지고 Raft을 더 쉽게 이해할 수 있습니다.

• 리더 선거 : Raft은 무작위로 타이머를 사용하여 리더를 선출합니다. 이렇게하면 충돌 알고리즘을 간단하고 신속하게 해결하면서 컨센서스 알고리즘에 필요한 하트 비트에 메커니즘을 조금만 추가 할 수 있습니다.

• 멤버쉽 변경 : 클러스터의 서버 세트를 변경하기위한 Raft의 메커니즘은 전환 중에 서로 다른 두 구성의 다수가 겹치는 새로운 공동 합의 방식을 사용합니다. 이렇게하면 구성 변경 중에 클러스터가 정상적으로 작동 할 수 있습니다.

우리는 Raft이 교육 목적 및 구현을위한 기반으로서 Paxos 및 기타 합의 알고리즘보다 우수하다고 믿습니다. 다른 알고리즘보다 쉽고 이해하기 쉽습니다. 실용적인 시스템의 필요를 충족시키기에 충분할 정도로 설명되어있다.

몇 가지 오픈 소스 구현을 가지고 있으며 여러 회사에서 사용하고 있습니다. 그것의 안전 속성은 정식으로 지정되고 입증되었습니다; 그 효율성은 다른 알고리즘에 필적합니다.

이 논문의 나머지 부분에서는 복제 된 상태 머신 문제 (2 절)를 소개하고, Paxos (3 절)의 장단점에 대해 논의하고, 일반적인 이해력 접근법 (4 절)을 설명하고, Raft 컨센서스 알고리즘 (5-8 절) Raft (9 절)를 평가하고 관련 작업 (10 절)에 대해 논의합니다.

2 복제된 상태 머신

컨센서스 알고리즘은 일반적으로 복제 된 상태 머신 [37]의 맥락에서 발생한다. 이 접근법에서 서버 모음에있는 상태 시스템은 동일한 복사본을 계산합니다. 같은 상태의 서버 중 일부가 작동하지 않아도 계속 작동 할 수 있습니다. 복제 된 상태 머신은 분산 시스템에서 다양한 내결함성 문제를 해결하는 데 사용됩니다. 예를 들어, GFS [8], HDFS [38] 및 RAMCloud [33]와 같이 단일 클러스터 리더를 보유한 대규모 시스템은 일반적으로 별도의 복제 된 상태 시스템을 사용하여 리더 선거를 관리하고 생존해야하는 구성 정보를 저장합니다 지도자 충돌. 복제 된 상태 머신의 예로 Chubby [2]와 ZooKeeper [11]가 있습니다.

그림 1 : 복제 된 상태 시스템 아키텍처. 컨센서스 알고리즘은 클라이언트의 상태 머신 명령을 포함하는 복제 된 로그를 관리합니다. 상태 머신은 로그와 동일한 명령 시퀀스를 처리하므로 동일한 출력을 생성합니다.

복제 된 상태 머신은 일반적으로 그림 1과 같이 복제 된 로그를 사용하여 구현됩니다. 각 서버는 일련의 명령을 포함하는 로그를 저장합니다. 상태 기계가 순서대로 실행됩니다. 각 로그에는 동일한 명령이 동일한 순서로 포함되어 있으므로 각 상태 시스템은 동일한 명령 시퀀스를 처리합니다. 이후 상태 머신은 결정 론적이며, 각각 동일한 상태와 동일한 출력 순서를 계산합니다. 복제 된 로그의 일관성을 유지하는 것이 합의 알고리즘의 임무입니다. 서버의 합의 모듈은 클라이언트로부터 명령을 받아 로그에 추가합니다. 다른 서버의 합의 모듈과 통신하여 일부 서버가 실패하더라도 모든 로그가 동일한 순서로 같은 요청을 포함하도록합니다. 명령이 제대로 복제되면 각 서버의 상태 시스템은 로그 순서대로 처리하고 출력을 클라이언트에 반환합니다. 결과적으로 서버는 신뢰성이 높은 단일 상태 시스템을 구성하는 것처럼 보입니다. 실용적인 시스템에 대한 합의 알고리즘은 일반적으로 다음과 같은 특성을 갖는다.

• 네트워크 지연, 파티션 및 패킷 손실, 복제 및 순서 변경을 포함하여 비잔틴이 아닌 모든 조건에서 안전을 보장합니다 (잘못된 결과를 반환하지 않음).

• 대부분의 서버가 작동하고 서로 통신 할 수 있고 클라이언트와 통신 할 수있는 한 완벽하게 작동합니다 (사용 가능). 따라서 5 개의 서버로 구성된 일반적인 클러스터는 두 서버의 장애를 견딜 수 있습니다. 서버는 중지함으로써 실패합니다. 나중에 안정적인 저장소에서 상태를 복구하고 클러스터에 다시 참가할 수 있습니다.

• 로그의 일관성을 보장하는 타이밍에 의존하지 않습니다. 오류가있는 클럭 및 극단적 인 메시지 지연으로 인해 최악의 경우 가용성 문제가 발생할 수 있습니다.

• 일반적으로 클러스터의 다수가 원격 프로 시저 호출의 단일 라운드에 응답하자마자 명령을 완료 할 수 있습니다. 소수의 느린 서버는 전반적인 시스템 성능에 영향을 줄 필요가 없습니다.

3 What’s wrong with Paxos?

(잠시 생략)

4 이해 가능성을 고려한 설계

우리는 Raft 설계에있어 몇 가지 목표를 가지고있었습니다 : 시스템 구축을위한 완전하고 실질적인 기반을 제공해야하므로 개발자가 요구하는 설계 작업량을 크게 줄일 수 있습니다. 모든 조건 하에서 안전해야하며 일반적인 작동 조건 하에서 사용 가능해야합니다. 일반 작업에는 효율적이어야합니다. 그러나 우리의 가장 중요한 목표 - 그리고 가장 어려운 도전 -은 이해하기 쉽습니다.

많은 사람들이 알고리즘을 편안하게 이해할 수 있어야합니다. 또한 시스템 빌더가 실제 구현에서 필연적 인 확장을 만들 수 있도록 알고리즘에 대한 직관을 개발할 수 있어야합니다.

Raft 설계에는 다양한 접근 방식 중에서 선택해야 할 점이 많이있었습니다. 이러한 상황에서 우리는 이해력에 기반하여 대안을 평가했습니다. 각 대안을 설명하는 것이 얼마나 힘든지 (예 : 복잡한 상태 공간과 미묘한 함의가 있습니까?), 독자가 완전히 쉽게 할 수있는 방법 접근법과 그 의미를 이해하고 있습니까?

우리는 그러한 분석에서 높은 주관성이 있음을 인식합니다. 그럼에도 불구하고 일반적으로 적용 할 수있는 두 가지 기술을 사용했습니다. 첫 번째 기술은 잘 알려진 문제 해결 방법입니다. 가능한 한 문제를 비교적 독립적으로 해결하고, 설명하고 이해할 수있는 별도의 조각으로 나눕니다. 예를 들어, Raft에서는 리더 선출, 로그 복제, 안전성 및 멤버십 변경을 분리했습니다.

우리의 두 번째 접근법은 고려할 상태의 수를 줄이고 시스템을보다 일관되게 만들고 가능하면 비 결정론을 제거하여 상태 공간을 단순화하는 것이 었습니다. 특히 로그에는 구멍이있을 수 없으며 Raft은 로그가 서로 일치하지 않게하는 방식을 제한합니다. 대부분의 경우 비 결정론을 제거하려고 시도했지만 비 결정론이 실제로 이해력을 향상시키는 몇 가지 상황이 있습니다.

특히, 무작위 접근법은 비 결정론을 도입하지만 비슷한 방식으로 모든 가능한 선택을 처리함으로써 상태 공간을 줄이는 경향이 있습니다 ( "선택하십시오; 중요하지 않습니다"). 우리는 Raft 리더 선거 알고리즘을 단순화하기 위해 무작위 추출을 사용했습니다.

5 Raft 일치 알고리즘

Raft은 2 절에서 설명한 양식의 복제 된 로그를 관리하기위한 알고리즘입니다. 그림 2는 요약을 위해 요약 된 알고리즘을 요약하고 그림 3은 알고리즘의 주요 특성을 나열합니다. 이 숫자들의 요소들은이 절의 나머지 부분에 걸쳐 조각별로 논의됩니다.

Raft은 먼저 탁월한 리더를 선출 한 다음 리더에게 복제 된 로그 관리에 대한 완전한 책임을 부여함으로써 합의를 구현합니다. 지도자가 받아 들인다. 클라이언트의 항목을 기록하고, 다른 서버에서 해당 항목을 복제하며, 상태 항목에 로그 항목을 적용하는 것이 안전 할 때 서버에 알려줍니다. 리더를 가짐으로써 복제 된 로그를 간단하게 관리 할 수 있습니다. 예를 들어, 리더는 다른 서버를 참조하지 않고 로그에 새 항목을 배치 할 위치를 결정할 수 있으며 리더에서 다른 서버로 데이터가 간단한 방식으로 흐릅니다. 리더가 실패하거나 다른 서버와 연결이 끊어 질 수 있으며,이 경우 새로운 리더가 선출됩니다.

리더의 접근법을 감안할 때 Raft는 합의 문제를 상대적으로 독립적 인 세 가지 하위 문제로 분해합니다. 하위 문제는 다음 하위 절에서 설명합니다.

• 리더 선거 : 기존 리더가 실패 할 경우 새로운 리더가 선발되어야합니다 (5.2 절). • 로그 복제 : 리더는 클라이언트의 로그 항목을 받아 들여 클러스터를 통해 복제하여 다른 로그가 자체 로그와 일치하도록해야합니다 (5.3 절). • 안전성 : Raft의 핵심 안전 속성은 그림 3의 State Machine Safety 속성입니다. 서버가 특정 상태를 상태 머신에 적용한 경우 다른 서버가 동일한 로그 인덱스에 대해 다른 명령을 적용 할 수 없습니다. 5.4 절은 Raft이이 속성을 보장하는 방법을 설명합니다. 해결책은 섹션 5.2에 설명 된 선거 메커니즘에 대한 추가 제한을 포함합니다.

합의 알고리즘을 제시 한 후에,이 절에서는 가용성 문제와 시스템에서 타이밍의 역할에 대해 논의합니다.

5.1 Raft 기본 사항

Raft 클러스터에는 여러 개의 서버가 있습니다. 5는 일반적인 숫자이므로 시스템에서 두 가지 오류를 허용 할 수 있습니다. 주어진 시간에 각 서버는 세 가지 상태 중 하나에 있습니다. 지도자, 추종자 또는 후보자. 정상적인 작동에는 정확히 하나의 리더가 있고 다른 모든 서버는 추종자입니다. 팔로어는 수동적입니다. 그들 만의 것이 아니라 지도자와 후보자의 요청에 간단하게 응답합니다. 리더는 모든 클라이언트 요청을 처리합니다 (클라이언트가 팔로워에 연결하면 팔로워가 리더에게 리디렉션됩니다). 제 3 국가 (후보자)는 5.2 절에서 설명한대로 새로운 지도자를 선출하는 데 사용됩니다. 그림 4는 상태와 전환을 보여줍니다. 전환에 대해서는 아래에서 설명합니다.

Raft은 시간을 그림 5에서와 같이 임의의 길이로 나눕니다. 용어는 연속적인 정수로 번호가 매겨져 있습니다. 각 용어는 하나의 선거에서 시작됩니다. 또는 더 많은 후보자가 섹션 5.2에서 설명한대로 리더가 되려고합니다. 후보자가 선거에서 승리하면 남은 기간 동안 리더 역할을합니다. 어떤 상황에서는 선거가 분할 투표가됩니다. 이 경우이 용어는 리더없이 끝납니다. 새로운 선거 (새로운 선거와 함께)가 곧 시작될 것입니다. Raft은 주어진 기간에 최대 하나의 리더가 있음을 보장합니다.

서로 다른 서버는 서로 다른 시간에 용어 간의 전환을 관찰 할 수 있으며 경우에 따라 서버가 선거 또는 전체 용어를 준수하지 않을 수도 있습니다.

"용어"는 Raft에서 논리적 인 시계 역할을하며, 서버는 오래된 리더와 같이 오래된 정보를 감지 할 수 있습니다. 각 서버는 현재 용어 번호를 저장하며, 시간이 지남에 따라 단조롭게 증가합니다. 서버가 통신 할 때마다 현재 용어가 교환됩니다. 한 서버의 현재 용어가 다른 용어보다 작 으면 현재 용어를 더 큰 값으로 업데이트합니다. 후보자 또는 지도자가 임기가 만료되었다는 사실을 발견하면 즉시 추종자 상태로 돌아갑니다. 서 v가 오래된 용어 x 호와 함 2 요청을 수신하면 서 v는 요청을 거부합니다.

Raft 서버는 원격 프로 시저 호출 (RPC)을 사용하여 통신하며 기본 합의 알고리즘에는 두 가지 유형의 RPC 만 필요합니다. RequestVote RPC는 선거에서 후보에 의해 시작되며 (섹션 5.2) AppendEntries RPC는 리더가 로그 항목을 복제하고 하트 비트 형식을 제공하기 위해 시작됩니다 (5.3 절). 섹션 7에서는 서버간에 스냅 샷을 전송하기위한 세 번째 RPC를 추가합니다. 적시에 응답을받지 못하면 서버가 RPC를 다시 시도하고 최적의 성능을 위해 RPC를 병렬로 실행합니다.

요약 페이지?

State

모든 서버의 영구 상태 : 모든 서버의 영구 상태 : (RPC에 응답하기 전에 안정적인 저장소에서 업데이트 됨)

  • currentTerm : 최신 텀 서버 (처음 부팅시 0으로 초기화되고 단조롭게 증가 함)
  • voteFor : 커렌트 텀에 투표를 한 candidateId (없는 경우 null)
  • log [] 로그 항목; 각 엔트리는 상태 머신에 대한 명령을 포함하고 엔트리가 리더에 의해 수신 된 텀 (첫 번째 인덱스는 1 임)

모든 서버의 휘발성 상태:

  • commitIndex: 커밋 된 것으로 알려진 가장 높은 로그 항목 인덱스 (0으로 초기화되고 단조롭게 증가 함)
  • lastApplied: 상태 머신에 적용된 가장 높은 로그 항목 인덱스 (0으로 초기화되고 단조롭게 증가 함)

리더의 휘발 상태 ( (선거 후 재 초기화) ) nextIndex: 각 서버에 대해 해당 서버에 보낼 다음 로그 항목의 인덱스 (리더 마지막 로그 인덱스 + 1로 초기화 됨)

AppendEntries RPC

리더에 의해 로그 항목을 복제하기 위해 호출됩니다 (5.3 절). 하트 비트 (§5.2)로도 사용됩니다.

Argument

  • term: leader’s term
  • leeaderId: 팔로워가 고객을 리디렉션 할 수 있습니다.
  • preveLogIndex :새로운 로그 항목 바로 앞의 로그 항목 인덱스
  • prevLogTerm : prevLogIndex 엔트리의 텀
  • entries[]: 저장할 로그 항목 (하트 비트는 비어 있고 효율성을 위해 둘 이상을 보낼 수 있음)
  • leader’s commit: 리더의 커밋 인덱스

결과

  • term: 지도자가 스스로를 업데이트하기위한 currentTerm
  • success: follower가 prevLogIndex 및 prevLogTerm과 일치하는 항목을 포함하는 경우 true

수신자 구현

  1. term <currentTerm (§5.1) 인 경우 false로 응답합니다.
  2. log가 prevLogTerm (§5.3)과 일치하는 항목을 prevLogIndex에 포함하지 않으면 false로 응답하십시오.
  3. 기존 항목이 새 항목 (동일한 색인이지만 다른 용어)과 충돌하는 경우 기존 항목과 그 뒤에 오는 모든 항목을 삭제하십시오 (§5.3)
  4. 아직 로그에없는 새 항목을 추가하십시오
  5. leaderCommit> commitIndex 인 경우 commitIndex = min (leaderCommit, 마지막 새 항목의 인덱스)을 설정합니다.

RequestVote RPC

Arguments:

  • term
  • candidateId
  • lastLogIndex
  • lastLogTerm

Results:

  • term
  • voteGranted

Rules for Servers

모든 서버 : • commitIndex> lastApplied 인 경우 : lastApplied를 증가시키고 log [lastApplied]를 상태 시스템 (§5.3)에 적용합니다. • RPC 요청 또는 응답에 T> currentTerm이라는 용어가 포함 된 경우 set currentTerm = T, follower (§5.1)로 변환합니다.

추종자 (§5.2) : • 후보자와 리더의 RPC에 응답 • 현재 리더의 AppendEntries RPC를받지 않거나 후보자에게 투표를 부여하지 않고 선거 시간 제한이 경과 한 경우 : 후보로 전환하십시오

후보자 (§5.2) :

• 후보자로 전환 할 때, 선거를 시작하십시오 : • 현재 항목 증가 • 스스로 투표하십시오. • 선거 타이머 재설정 • 다른 모든 서버에 RequestVote RPC 보내기 • 대다수 서버에서 득표를 얻은 경우 : 리더가됩니다. • AppendEntries RPC가 새 리더에서받은 경우 : 팔로워로 변환합니다. • 선거 시간이 초과 된 경우 : 새 선거를 시작합니다.

지도자 : • 선출시 : 초기 빈 AppendEntries RPC (하트 비트)를 각 서버에 보냅니다. 선거 시간 초과를 방지하기 위해 유휴 기간 동안 반복 (§5.2) • 클라이언트로부터 명령을 수신 한 경우 : 로컬 로그에 항목을 추가하고 상태 시스템에 항목을 적용한 후에 응답합니다 (§5.3) • 추종자의 마지막 로그 인덱스 ≥ nextIndex 인 경우 : nextIndex에서 시작하는 로그 항목이 포함 된 AppendEntries RPC를 보냅니다. • 성공한 경우 : follower (§5.3)의 nextIndex 및 matchIndex를 업데이트합니다. • 로그 불일치로 인해 AppendEntries가 실패한 경우 : nextIndex를 줄이고 다시 시도하십시오 (§5.3) • N> commitIndex, matchIndex [i] ≥ N 및 log [N] .term == currentTerm : commitIndex = N (§5.3, §5.4)을 설정하는 N이 존재하는 경우.

수많은 피겨들

그림 2 : Raft 일치 알고리즘 요약 (회원 변경 및 로그 압축 제외). 왼쪽 위 상자의 서버 비헤이비어는 독립적으로 반복적으로 트리거되는 규칙 집합으로 설명됩니다. §5.2와 같은 섹션 번호는 특정 기능이 논의되는 곳을 나타냅니다. 공식 사양 [31]은 알고리즘을보다 정확하게 설명합니다.

그림 3 : Raft은 이러한 속성 각각이 항상 참이라는 것을 보장합니다. 섹션 번호는 각 속성에 대해 설명합니다.

그림 4 : 서버 상태. 추종자는 다른 서버의 요청에만 응답합니다. 추종자가 아무런 연락도받지 못하면, 후보자가되어 선거를 시작합니다. 전체 클러스터의 다수에서 투표를받는 후보가 새로운 리더가됩니다. 리더는 일반적으로 실패 할 때까지 작동합니다.

그림 5 : 시간은 용어로 나뉘며 각 용어는 선거로 시작됩니다. 성공적인 선거 후에 한 명의 리더가 임기가 끝날 때까지 클러스터를 관리합니다. 일부 선거는 실패하며,이 경우 선거를 선택하지 않고 임기가 끝납니다. 용어 간 전환은 여러 서버에서 서로 다른 시간에 관찰 될 수 있습니다.

5.2 리더 선거

Raft은 하트 비트 메커니즘을 사용하여 리더 선거를 시작합니다. 서버가 시작되면 추종자로 시작됩니다. 서버는 리더 또는 후보로부터 유효한 RPC를 수신하는 한 팔로워 상태로 유지됩니다. 리더는 권한을 유지하기 위해 모든 팔로워에게 정기적 인 하트 비트 (로그 항목이없는 AppendEntries RPC)를 보냅니다. 추종자가 선거 시간 제한이라고하는 일정 기간 동안 아무런 연락도받지 못하면 실행 가능한 지도자가 없다고 가정하고 새로운 지도자를 선출하기 위해 선거를 시작합니다.

선거를 시작하기 위해 추종자는 현재의 임기를 증가시키고 후보자 상태로 전환합니다. 그런 다음 자체적으로 투표하고 RequestVote RPC를 클러스터의 다른 서버 각각에 병렬로 발행합니다. 후보자는 다음 세 가지 중 하나가 발생할 때까지 후보자가 계속됩니다. (a) 선거에서 승리합니다. (b) 다른 서버가 리더로 자리 매김합니다. (c) 승자가없는 상태로 일정 기간 지속됩니다. 이러한 결과는 아래 단락에서 별도로 논의됩니다.

후보자는 동일한 기간 동안 전체 클러스터에있는 서버의 대다수로부터 투표를 받으면 선거에서 승리합니다. 각 서버는 최대 하나의 후보자에게 투표 할 것입니다. 주어진 기간을 선착순으로 (참고 : 5.4 절에 추가 투표 제한이 추가됨). 다수 규칙은 최대 한 명의 후보자가 특정 기간의 선거에서 승리 할 수 ​​있도록합니다 (그림 3의 선거 안전 재산). 후보자가 선거에서 승리하면 리더가됩니다. 그런 다음 모든 서버에 하트 비트 메시지를 보내 권한을 설정하고 새로운 선거를 방지합니다.

투표를 기다리는 동안 후보자는 리더가 될 것이라고 주장하는 다른 서버로부터 AppendEntries RPC를 수신 할 수 있습니다. 리더의 임기 (RPC에 포함)가 후보자의 현재 임기와 적어도 같을 경우 후보자는 리더를 합법적 인 것으로 인정하고 추종자 상태로 돌아갑니다. RPC의 용어가 후보자의 현재 용어보다 작 으면 후보자는 RPC를 거부하고 후보 국가에서 계속됩니다.

세 번째 가능한 결과는 후보자가 선거에서도 이기지도 잃지도 않는다는 것입니다. 많은 추종자가 동시에 후보자가되는 경우 투표를 분할하여 후보자가 다수를 얻지 못하도록 할 수 있습니다. 이 경우 각 후보자는 임기를 연장하고 Request-Vote RPC 라운드를 다시 시작하여 새로운 선거를 시한하고 시작합니다. 그러나 별도의 조치없이 분리 투표가 무기한 반복 될 수 있습니다.

Raft은 무작위 선거 시간 초과를 사용하여 분할 투표가 드물고 신속하게 해결됩니다. 먼저 분열을 방지하기 위해 선거 타임 아웃은 고정 간격 (예 : 150-300ms)에서 무작위로 선택됩니다. 이렇게하면 대부분의 경우 단일 서버 만 시간이 초과되도록 서버가 분산됩니다. 다른 서버가 시간을 초과하기 전에 선거에서 승리하고 하트 비트를 보냅니다. 분할 투표를 처리하는데도 동일한 메커니즘이 사용됩니다. 각 후보자는 선거가 시작될 때 무작위 선거 시간 제한을 다시 시작하고 다음 선거를 시작하기 전에 시간 초과가 경과 할 때까지 기다립니다. 이것은 새로운 선거에서 또 다른 분할 투표의 가능성을 줄입니다. 9.3 절에서는이 접근법이 리더를 신속하게 선출한다는 것을 보여준다.

선거는 어떻게 설계 대안간에 우리의 선택을 이끌 었는지 이해할 수있는 방법의 한 예입니다. 처음에는 순위 시스템을 사용할 계획이었습니다. 각 후보에는 경쟁 순위를 매기는 데 사용 된 고유 한 순위가 지정되었습니다. 후보자가 더 높은 순위의 다른 후보를 찾으면 추종자 상태로 돌아가므로 순위가 높은 후보가 다음 선거에서 더 쉽게 승리 할 수 있습니다. 우리는이 접근법이 가용성과 관련하여 미묘한 문제를 야기했다는 것을 발견했습니다 (순위가 낮은 서버는 더 높은 순위의 서버가 실패하면 시간이 초과되어 다시 후보가 될 수 있지만 너무 빨리 수행하면 리더를 선출하는 방향으로 재설정 할 수 있음) ). 우리는 알고리즘을 여러 번 조정했지만 각 조정 후에 새로운 코너 케이스가 나타났습니다. 결국 우리는 무작위로 재 시도하는 방법이 더 분명하고 이해할 수 있다고 결론을 내렸다.

그림 4 : 서버 상태. 추종자는 다른 서버의 요청에만 응답합니다. 추종자가 아무런 연락도받지 못하면, 후보자가되어 선거를 시작합니다. 전체 클러스터의 다수에서 투표를받는 후보가 새로운 리더가됩니다. 리더는 일반적으로 실패 할 때까지 작동합니다.

5.3 로그 복제

그림 6 : 로그는 순차적으로 번호가 매겨지는 항목으로 구성됩니다. 각 항목에는 작성된 용어 (각 상자의 번호)와 상태 시스템에 대한 명령이 들어 있습니다. 해당 항목이 상태 시스템에 적용되는 것이 안전 할 경우 항목이 커미트 된 것으로 간주됩니다.

리더가 선출되면 클라이언트 요청을 처리하기 시작합니다. 각 클라이언트 요청에는 복제 된 상태 시스템에서 실행할 명령이 들어 있습니다. 리더는 명령에 로그에 새로운 항목을 추가 한 다음 AppendEntries RPC를 다른 서버와 병렬로 발행하여 항목을 복제합니다. 항목이 안전하게 복제 된 경우 (아래 설명 참조) 리더는 항목을 상태 시스템에 적용하고 해당 실행 결과를 클라이언트에 반환합니다. 추종자가 추락하거나 느리게 실행되거나 네트워크 패킷이 손실되면 리더는 모든 추종자가 결국 모든 로그 항목을 저장할 때까지 AppendEntries RPC를 무기한으로 재 시도합니다 (클라이언트에 응답 한 후에도).

로그는 그림 6과 같이 구성됩니다. 각 로그 항목은 항목이 리더에 의해 수신되었을 때 용어 번호와 함께 상태 시스템 명령을 저장합니다. 로그 항목의 용어 숫자는 로그 간의 불일치를 감지하고 그림 3의 일부 속성을 보장하는 데 사용됩니다. 각 로그 항목에는 로그의 위치를 식별하는 정수 인덱스도 있습니다.

리더는 상태 머신에 로그 항목을 적용하는 것이 안전 할 때를 결정합니다. 이러한 항목을 확약이라고합니다. Raft는 커밋 된 항목이 내구성이 있으며 사용 가능한 모든 상태 시스템에서 결국 실행됩니다. 엔트리를 생성 한 리더가 다수의 서버 (예 :도 6의 엔트리 (7))에 그것을 복제하면 로그 엔트리는 커밋된다. 또한 이전 리더가 작성한 항목을 포함하여 리더의 로그에있는 모든 이전 항목을 커밋합니다. 5.4 절에서는 리더가 변경된 후에이 규칙을 적용 할 때의 몇 가지 미묘한 점에 대해 설명하고,이 헌신의 정의가 안전한. 리더는 알고있는 가장 높은 인덱스를 추적합니다. 커밋 될 것이며 향후 AppendEntries RPC (하트 비트 포함)에 해당 인덱스가 포함되므로 다른 서버가 결국 알아낼 수 있습니다. 추종자는 로그 항목이 커밋되었음을 알게되면 로그 상태로 해당 항목을 로컬 상태 시스템에 적용합니다.

우리는 서로 다른 서버의 로그간에 높은 수준의 일관성을 유지하기 위해 Raft 로그 메커니즘을 설계했습니다. 이렇게하면 시스템의 동작이 단순 해지고 예측이 가능해질뿐만 아니라 안전을 보장하는 중요한 구성 요소입니다. Raft는 그림 3에서 Log Matching Property를 구성하는 다음 속성을 유지 관리합니다.

그림 7 : 상단의 리더가 전원을 켜면 추종자 로그에 시나리오 (a-f)가 발생할 수 있습니다. 각 상자는 하나의 로그 항목을 나타냅니다. 상자에있는 숫자는 그 용어입니다. 팔로워는 항목이 누락되었거나 (a-b) 추가 미확인 항목이있을 수 있습니다 (c-d) 또는 둘 다 (e-f). 예를 들어 시나리오 (f)는 해당 서버가 2 기의 리더이고 로그에 여러 항목을 추가 한 다음 해당 항목을 커밋하기 전에 중단 될 수 있습니다. 신속하게 재시작하고, 용어 3의 리더가되었고, 로그에 몇 가지 항목을 추가했습니다. 기간 2 또는 기간 3의 항목 중 일부가 커밋되기 전에 서버가 다시 충돌하고 몇 가지 용어로 계속 남아 있습니다.

• 서로 다른 로그의 두 항목이 동일한 색인과 용어를 갖는 경우 동일한 명령을 저장합니다. • 서로 다른 로그의 두 항목이 동일한 인덱스와 용어를 갖는 경우 로그는 모든 이전 항목에서 동일합니다.

첫 번째 속성은 주어진 용어에서 지정된 로그 인덱스를 사용하여 리더가 최대 하나의 항목을 만들고 로그 항목이 로그에서 절대 위치를 변경하지 않는다는 사실에서 따릅니다. 두 번째 속성은 AppendEntries가 수행하는 간단한 일관성 검사로 보장됩니다. AppendEntries RPC를 전송할 때, 리더는 새로운 항목 바로 앞에 오는 로그의 항목 및 용어를 포함합니다. 추종자가 동일한 색인 및 용어로 로그에서 항목을 찾지 못하면 새 항목을 거부합니다. 일관성 검사는 유도 단계의 역할을합니다. 로그의 초기 빈 상태는 로그 일치 특성을 충족하며 일관성 검사는 로그가 확장 될 때마다 로그 일치 특성을 보존합니다. 결과적으로 AppendEntries가 성공적으로 반환 할 때마다 리더는 팔로워의 로그가 새 항목을 통한 자체 로그와 동일하다는 것을 알고 있습니다.

정상적으로 작동하는 동안 리더와 팔로어의 로그는 일관되게 유지되므로 AppendEntries 일관성 검사가 실패하지 않습니다. 그러나 리더 충돌로 인해 로그가 일치하지 않을 수 있습니다 (예전 리더가 로그의 모든 항목을 완전히 복제하지 않았을 수 있음). 이러한 불일치는 일련의 리더 및 팔로어 크래시에서 복합적으로 나타날 수 있습니다. 그림 7은 추종자의 기록이 새로운 기록의 기록과 다를 수있는 방법을 보여줍니다. 팔로워는 리더에있는 항목이 누락되었을 수 있으며 리더에없는 항목이 추가로 있거나 둘 다있을 수 있습니다. 로그에 누락되거나 관계없는 항목이 여러 용어로 나타날 수 있습니다.

Raft에서 리더는 추종자의 로그를 강제로 복제하여 불일치를 처리합니다. 즉, 팔로워 로그의 충돌하는 항목은 리더의 로그 항목으로 덮어 쓰게됩니다. 5.4 절은 하나의 제한 사항과 결합 할 때 이것이 안전함을 보여줍니다. 추종자의 기록을 자신의 기록과 일관성있게 유지하려면 지도자는 최신 기록을 찾아야합니다. 로그가 동의하면 해당 지점 이후에 팔로워의 로그에있는 항목을 모두 삭제하고 그 지점 이후에 모든 리더의 항목을 팔로워에게 보냅니다. 이러한 모든 작업은 AppendEntries RPC가 수행하는 일관성 검사에 대한 응답으로 발생합니다. 리더는 각 팔로워에 대해 nextIndex를 유지합니다. 리더는 해당 팔로워에게 보낼 다음 로그 항목의 색인입니다. 리더가 처음으로 전원을 켜면 모든 nextIndex 값이 로그의 마지막 인덱스 바로 뒤에있는 인덱스로 초기화됩니다 (그림 7의 11). 팔로워의 로그가 리더와 일치하지 않으면 다음 AppendEntries RPC에서 AppendEntries 일관성 검사가 실패합니다. 거부 된 후 리더는 nextIndex를 감소시키고 AppendEntries RPC를 다시 시도합니다. 결국 nextIndex는 리더 및 팔로어 로그가 일치하는 지점에 도달합니다. 이 경우 AppendEntries가 성공하고 추종자의 로그에서 충돌하는 항목이 제거되고 리더의 로그 (있는 경우)에 항목이 추가됩니다. AppendEntries가 성공하면 팔로워의 로그는 리더의 로그와 일치하며, 나머지 기간 동안 그 방법으로 남을 것입니다.

원하는 경우 거부 된 AppendEntries RPC 수를 줄이기 위해 프로토콜을 최적화 할 수 있습니다. 예를 들어 AppendEntries 요청을 거부하면 팔로 우어는 충돌하는 항목의 용어와 해당 용어에 대해 저장하는 첫 번째 인덱스를 포함 할 수 있습니다. 이 정보를 사용하여 리더는 nextIndex를 감소시켜 해당 용어에서 충돌하는 항목을 모두 무시할 수 있습니다. 하나의 AppendEntries RPC는 항목 당 하나의 RPC가 아닌 각 용어에 대해 충돌하는 항목이 필요합니다. 실제로는 실패가 자주 발생하지 않고 일치하지 않는 항목이 많기 때문에 이러한 최적화가 필요하다고 생각합니다.

이 메커니즘을 사용하면 리더는 전원 일관성을 유지하기 위해 로그 일관성을 복원하기 위해 특별한 조치를 취할 필요가 없습니다. 단지 정상 작동을 시작하고 AppendEntries 일관성 검사 실패에 대한 응답으로 로그가 자동으로 수렴됩니다. 리더는 자체 로그의 항목을 덮어 쓰거나 삭제하지 않습니다 (그림 3의 리더 추가 전용 속성).

이 로그 복제 메커니즘은 2 절에서 설명하는 바람직한 합의 속성을 나타냅니다. 서버의 다수가 작동하는 한 Raft는 새로운 로그 항목을 받아들이고 복제하고 적용 할 수 있습니다. 정상적인 경우 클러스터의 대다수에 단일 라운드의 RPC로 새로운 항목을 복제 할 수 있습니다. 느린 단일 팔로어는 성능에 영향을 미치지 않습니다.

5.4 안전성

이전 절에서는 Raft이 리더를 선출하고 로그 항목을 복제하는 방법에 대해 설명했습니다. 그러나 지금까지 설명한 메커니즘은 각 상태 시스템이 동일한 순서로 정확히 동일한 명령을 실행하는 것을 보장하기에 충분하지 않습니다. 예를 들어, 리더가 여러 로그 항목을 커밋하는 동안 팔로워를 사용할 수없는 경우 리더로 선출되고 이러한 항목을 새로운 로그 항목으로 덮어 쓸 수 있습니다. 결과적으로 다른 상태 시스템은 다른 명령 순서를 실행할 수 있습니다.

이 섹션에서는 리더가 선출 될 서버에 대한 제한을 추가하여 Raft 알고리즘을 완료합니다. 이 제한은 주어진 용어의 리더가 이전 용어로 작성된 모든 항목 (그림 3의 리더 완전성 속성)을 포함하도록합니다. 선거 제한을 감안할 때, 우리는 약속에 대한 규칙을보다 정확하게 작성합니다. 마지막으로 Leader Completeness Property에 대한 증명 스케치를 제시하고 복제 된 상태 시스템의 올바른 동작을 유도하는 방법을 보여줍니다.

5.4.1 선거 제한 리더 기반 컨센서스 알고리즘에서 리더는 결국 모든 커밋 된 로그 항목을 저장해야합니다. Viewstamped Replication [22]와 같은 일부 합의 알고리즘에서, 리더는 처음에 커밋 된 모든 항목을 포함하지 않더라도 선출 될 수 있습니다. 이러한 알고리즘에는 누락 된 항목을 식별하고이를 선거 과정 또는 직후에 새로운 리더에게 전송하는 추가 메커니즘이 포함되어 있습니다. 불행히도 이것은 상당한 메카니즘과 복잡성을 초래합니다. Raft은 이전 조건의 모든 커밋 된 항목이 선출 된 순간부터 리더에게 전달할 필요없이 새로운 리더에게 제공된다는 간단한 접근 방식을 사용합니다. 즉, 로그 항목은 리더에서 팔로어로 한 방향으로 만 흐르고 리더는 로그의 기존 항목을 덮어 쓰지 않습니다. Raft은 투표 프로세스를 사용하여 로그에 커밋 된 모든 항목이 포함되어 있지 않으면 후보자가 선거에서 이기지 못하도록합니다. 후보자는 선출되기 위해 대다수의 클러스터에 연락해야하며, 이는 모든 커밋 된 항목이 해당 서버 중 하나 이상에 있어야 함을 의미합니다. 응시자의 로그가 적어도 그 대다수의 다른 로그와 같이 최신 상태 인 경우 ( "최신"이 정확하게 아래에 정의 된 경우), 모든 커밋 된 항목이 보관됩니다. RequestVote RPC는이 제한 사항을 구현합니다. RPC에는 응시자의 로그에 대한 정보가 포함되어 있으며 유권자는 자신의 로그가 응시자의 로그보다 최신 인 경우 투표를 거부합니다. Raft은 로그의 마지막 항목의 색인과 용어를 비교하여 두 개의 로그 중 어느 것이 최신인지를 판별합니다. 로그의 용어가 다른 마지막 항목이있는 경우 나중 용어가있는 로그가 더 최신입니다. 로그가 같은 용어로 끝나면 더 긴 로그가 더 최신입니다.

그림 8 : 리더가 이전 용어의 로그 항목을 사용하여 커밋을 결정할 수없는 이유를 보여주는 시간 순서. (a)에서 S1은 리더이며 인덱스 2의 로그 항목을 부분적으로 복제합니다. (b) S1에서 충돌이 발생합니다. S5는 S3, S4 및 그 자신으로부터의 투표로 3 학기의 리더로 선출되고 로그 인덱스 2에서 다른 항목을 승인합니다. (c) S5에서 충돌이 발생합니다. S1이 다시 시작되고 리더로 선출되며 복제가 계속됩니다. 이 시점에서, 용어 2의 로그 항목이 대다수의 서버에서 복제되었지만 커밋되지 않았습니다. (d)에서와 같이 S1이 충돌하면 S5가 리더 (S2, S3 및 S4에서 투표)로 선출 될 수 있으며 항목 3에서 자체 항목으로 덮어 씁니다. 그러나 S1이 현재 용어에서 엔트리를 복제하면 (e)와 같이 부서지기 전에 대다수의 서버에서이 항목이 커밋됩니다 (S5는 선거에서 이길 수 없음). 이 시점에서 로그의 모든 선행 항목도 커밋됩니다.

5.4.2 이전 용어의 항목 커밋 5.3 절에서 설명한 바와 같이 리더는 서버의 대다수에 항목이 저장되면 현재 용어의 엔트리가 커밋된다는 것을 알고 있습니다. 항목을 커밋하기 전에 리더가 충돌하면 미래의 리더가 항목 복제를 완료하려고 시도합니다. 그러나 리더는 대다수의 서버에 저장되면 이전 용어의 항목이 커밋된다는 결론을 즉시 내릴 수 없습니다. 그림 8은 오래된 로그 항목이 대다수의 서버에 저장되지만 미래의 리더가 여전히 덮어 쓸 수있는 상황을 보여줍니다. 그림 8의 문제를 제거하기 위해 Raft는 복제본을 계산하여 이전 용어의 로그 항목을 절대 작성하지 않습니다. 리더의 현재 임기 중 로그 항목 만 복제본을 계산하여 커밋됩니다. 현재 용어의 항목이 이러한 방식으로 커밋되면 Log Matching Property로 인해 모든 이전 항목이 간접적으로 커밋됩니다. 리더가 오래된 로그 엔트리가 완료되었다고 (예를 들어, 해당 엔트리가 특정 서버에 저장되는 경우) 안전하게 결론을 내릴 수있는 상황이 있지만 Raft는 단순성을 위해보다 보수적 인 접근 방식을 사용합니다.

리더가 이전 용어의 항목을 복제 할 때 로그 항목이 원래의 용어 수를 유지하기 때문에 Raft은 이러한 확약 규칙에서의 추가 복잡성을 초래합니다. 다른 합의 알고리즘에서 새로운 리더가 이전 "용어"의 항목을 다시 복제하는 경우 새로운 "용어 번호"를 사용해야합니다. Raft의 접근 방식은 동일한 항목 번호를 유지하므로 로그 항목에 대해 쉽게 추론 할 수 있습니다 시간 및 로그 전반에 걸쳐 또한, Raft의 새로운 리더는 다른 알고리즘보다 이전 용어에서 적은 로그 항목을 전송합니다 (다른 알고리즘은 커밋되기 전에 더 많은 로그 항목을 보내어 번호를 다시 지정해야합니다).

그림 9 : S1 (기간 T의 리더)이 해당 기간에서 새 로그 항목을 커밋하고 S5가 이후 기간 U 일 때 리더로 선출되면 로그 항목을 수락하고 S5에 대해 투표 한 서버가 하나 이상 있어야합니다.

results matching ""

    No results matching ""