뗏목(알고리즘)

Raft (algorithm)
뗏목
Raft Consensus Algorithm Mascot on transparent background.svg
뗏목 컨센서스 알고리즘마스코트
학급컨센서스 알고리즘

뗏목은 팍소스 계열 알고리즘의 대안으로 설계된 합의 알고리즘입니다.이것은 논리 분리에 의해 팍소스보다 이해하기 쉽도록 의도되었지만, 그것은 또한 공식적으로 안전하다는 것이 증명되었고 몇 가지 추가 [1]기능을 제공한다.Raft는 컴퓨팅 시스템 클러스터 전체에 상태 머신을 분산하는 일반적인 방법을 제공하여 클러스터 내의 각 노드가 동일한 일련의 상태 이행에 동의하도록 합니다.Go, C++, Java 및 Scala에 [2]풀 사양 구현된 오픈 소스 참조 구현이 다수 있습니다.Reliable, Replicated, Redundant 및 [3]Fault Tolerance의 이름을 따서 명명됩니다.

Raft는 비잔틴의 폴트 톨러런스 알고리즘이 아닙니다.노드는 선출된 [1]리더를 신뢰합니다.

기본

뗏목은 선출된 지도자를 통해 합의를 이끌어냅니다.뗏목 클러스터 내의 서버는 리더 또는 팔로워 중 하나이며, 선거의 정확한 경우 후보가 될 수 있습니다(리더를 사용할 수 없습니다).리더는 팔로워에 대한 로그 복제를 담당합니다.그것은 정기적으로 하트비트 메시지를 보내 팔로워들에게 그것의 존재를 알린다.각 팔로어에는 리더로부터의 하트비트가 예상되는 타임아웃(통상은 150~300밀리초)이 있습니다.하트비트를 수신하면 타임아웃이 리셋됩니다.하트비트가 수신되지 않으면 팔로어는 자신의 상태를 후보로 변경하고 리더 [1][4]선출을 시작합니다.

뗏목에서의 합의문제의 접근법

뗏목은 리더의 접근법에 의해 합의를 이끌어냅니다.클러스터에는 클러스터의 다른 서버에서 로그 복제 관리를 전적으로 담당하는 선택된 리더가 한 명만 있습니다.즉, 리더는 다른 서버와 상의하지 않고 새로운 엔트리의 배치와 다른 서버 간의 데이터 흐름 확립을 결정할 수 있습니다.리더는 실패하거나 연결이 끊어질 때까지 리드합니다.이 경우 새로운 리더가 선출됩니다.

합의 문제는 Raft에서 아래 나열된 두 개의 비교적 독립적인 하위 문제로 분해됩니다.

리더 선거

기존 리더가 실패하거나 알고리즘이 초기화되면 새 리더를 선택해야 합니다.

이 경우 클러스터에서 새 용어가 시작됩니다.용어는 새로운 리더를 선출해야 하는 서버상의 임의의 기간입니다.각 학기는 리더 선거로 시작한다.선거가 성공적으로 완료되면(즉, 단일 리더가 선출됨) 새 리더에 의해 조정된 정상적인 운영으로 계속됩니다.선거가 실패하면 새로운 선거와 함께 새 임기가 시작됩니다.

리더 선출은 후보 서버에 의해 개시된다.서버는 선거 타임아웃이라고 불리는 기간 동안 리더의 통신을 수신하지 않으면 후보가 되기 때문에 더 이상 리더가 대행하지 않는 것으로 간주됩니다.용어 카운터를 늘려 새로운 리더로서 투표하고 다른 모든 서버에 투표를 요구하는 메시지를 보내는 것으로 선거를 시작합니다.서버는 한 학기당 한 번만 선착순으로 투표합니다.후보자가 현재 임기보다 용어 번호가 큰 메시지를 다른 서버로부터 수신하면 후보의 당선이 패배하고 후보가 팔로워로 바뀌어 리더를 합법으로 인식한다.만약 후보자가 과반수의 표를 얻으면, 그 후보가 새로운 지도자가 된다.예를 들어 분할 투표로 인해 어느 쪽도 발생하지 않으면 새 임기가 시작되고 새 선거가 [1]시작됩니다.

Raft는 무작위 선거 타임아웃을 사용하여 분할 투표 문제를 신속하게 해결합니다.이렇게 하면 서버가 동시에 후보가 되는 것은 아니기 때문에 분할 투표의 가능성을 줄일 수 있습니다.즉, 1대의 서버가 타임아웃 되어 선거에서 승리하고 나서 리더가 되어 팔로워가 후보가 [1]되기 전에 다른 서버에 하트비트 메시지를 보냅니다.

로그 리플리케이션

리더는 로그 복제를 담당합니다.클라이언트의 요구를 받아들입니다.각 클라이언트 요청은 클러스터 내의 복제된 상태 시스템에서 실행하는 명령으로 구성됩니다.리더의 로그에 새 항목으로 추가된 후 각 요청은 AppendEntries 메시지로 팔로어에게 전달됩니다.팔로워를 사용할 수 없는 경우 리더는 로그 엔트리가 모든 팔로워에 의해 최종적으로 저장될 때까지 AppendEntries 메시지를 무기한 재시도합니다.

리더는 엔트리가 복제되었음을 대부분의 팔로워로부터 확인받으면 해당 엔트리를 로컬스테이트 머신에 적용하고 요구는 [1][4]커밋된 것으로 간주됩니다.이 이벤트는 리더의 로그에 있는 모든 이전 항목도 커밋합니다.팔로어는 로그 엔트리가 커밋되었음을 알게 되면 해당 엔트리를 로컬스테이트 머신에 적용합니다.이렇게 하면 클러스터를 통해 모든 서버 간에 로그의 일관성이 보장되므로 로그 매칭의 안전 규칙이 준수됩니다.

리더 크래시의 경우 이전 리더의 일부 로그가 클러스터를 통해 완전히 복제되지 않아 로그가 일관되지 않은 상태로 유지될 수 있습니다.그러면 새 리더는 팔로어가 자신의 로그를 복제하도록 강제함으로써 불일치를 처리합니다.이를 위해 각 팔로워에 대해 리더는 자신의 로그를 팔로워의 로그와 비교하여 동의한 마지막 엔트리를 찾은 후 팔로워 로그에서 이 중요한 엔트리 뒤에 오는 엔트리를 모두 삭제하고 자신의 로그엔트리로 바꿉니다.이 메커니즘은 장애가 발생할 수 있는 클러스터의 로그 일관성을 복원합니다.

안전.

뗏목 안전 수칙

뗏목은 다음과 같은 각각의 안전 특성을 보장합니다.

  • 선거 안전: 최대 한 명의 지도자를 한 임기 동안 선출할 수 있습니다.
  • 리더 추가 전용: 리더는 로그에 새 엔트리만 추가할 수 있습니다(엔트리를 덮어쓰거나 삭제할 수 없습니다).
  • 로그 매칭: 2개의 로그에 인덱스와 용어가 같은 엔트리가 포함되어 있는 경우 지정된 인덱스를 통해 모든 엔트리에서 로그가 동일합니다.
  • 리더 완전성: 특정 기간 내에 로그 엔트리가 커밋된 경우 해당 기간 이후 리더의 로그에 로그 엔트리가 표시됩니다.
  • 스테이트 머신의 안전성: 서버가 특정 로그엔트리를 스테이트 머신에 적용했을 경우, 다른 서버는 같은 로그에 다른 명령어를 적용할 수 없습니다.

첫 번째 4가지 규칙은 이전 섹션에서 설명한 알고리즘의 상세 내용에 의해 보증됩니다.스테이트 머신의 안전은, 선택 프로세스의 제한에 의해서 보증됩니다.

국가 기계 안전

이 규칙은 단순한 제한으로 보증됩니다.로그에 커밋된 엔트리가 모두 포함되어 있지 않으면 후보가 선거에서 이길 수 없습니다.당선되려면 후보자가 클러스터의 대부분에 접속해야 하며 커밋되는 로그 규칙을 지정하면 모든 커밋된 엔트리가 후보자가 접촉하는 서버 중 하나 이상에 존재해야 합니다.

Raft는 로그의 마지막 엔트리의 인덱스 조건을 비교하여 두 개의 로그 중 어느 것이 더 최신인지 판단합니다(2개의 다른 서버에 의해 전송됨).로그에 용어가 다른 마지막 엔트리가 있는 경우 이후 용어의 로그가 더 최신입니다.로그가 같은 용어로 끝나는 경우, 길이가 긴 로그가 보다 최신이 됩니다.

뗏목에서 후보자가 유권자에게 요청하는 내용에는 후보 로그에 대한 정보가 포함됩니다.자신의 로그가 후보 로그보다 더 최신일 경우, 유권자는 후보에게 투표한 것을 거부합니다.이 구현에 의해 State Machine Safety 규칙이 보증됩니다.

팔로워 크래시

팔로어가 크래시하면 다른 서버에서 전송된 AppendEntries 및 투표 요청은 실패합니다.이러한 장애는 다운된 팔로어에 무기한 도달하려고 하는 서버에 의해 처리됩니다.팔로어가 재시작되면 보류 중인 요청이 완료됩니다.장애가 발생하기 전에 요구가 이미 고려된 경우 재시작된 팔로어는 이를 무시합니다.

타이밍과 가용성

Raft에서는 클러스터의 완벽한 가용성을 확보하기 위해 시간이 지남에 따라 안정된 리더를 선택하고 유지하는 것이 타이밍입니다.알고리즘의 타이밍 요건을 고려하여 안정성을 확보합니다.

브로드캐스트시간 << 선택타임아웃 << MTBF

  • 브로드캐스트시간은 서버가 클러스터의 모든 서버에 요청을 보내고 응답을 수신하는 데 걸리는 평균 시간입니다.사용되는 인프라스트럭처에 비례합니다.
  • MTBF(Mean Time Between Failures)는 서버의 평균 장애 간격입니다.또한 인프라와도 관련이 있습니다.
  • 선출.타임아웃은 "리더 선택" 섹션에서 설명한 것과 동일합니다.그것은 프로그래머가 선택해야 하는 것이다.

브로드캐스트의 경우 이들 값의 일반적인 수치는 0.5 ~20 밀리초입니다시간: 프로그래머가 선택을 설정하는 것을 의미합니다.타임아웃은 10밀리초에서 500밀리초 사이입니다.단일 서버 장애 사이에 몇 주 또는 몇 달이 걸릴 수 있습니다. 즉, 안정된 클러스터에 충분한 값입니다.

레퍼런스

  1. ^ a b c d e f Ongaro, Diego; Ousterhout, John (2013). "In Search of an Understandable Consensus Algorithm" (PDF).
  2. ^ "Raft Consensus Algorithm". 2014.
  3. ^ 왜 "초안" 이름일까요?
  4. ^ a b Ben B. Johnson. "Raft: Understandable Distributed Consensus". The Secret Lives of Data website. Retrieved August 4, 2021.

외부 링크