분산 시스템이 반드시 알아야 할 합의 알고리즘: Raft

2. 뗏목 역할

2.1 역할

아래 그림과 같이 추종자, 후보자, 지도자를 나타내는 데 세 가지 유형의 도형이 사용됩니다.

3. 단일 노드 시스템

이제 이 노드가 데이터베이스 서버 역할을 하며 X 값을 저장한다고 가정해 보겠습니다.

Database Server

3.2 Client

Client

다중 노드 클러스터에서 Raft 알고리즘은 노드 장애, 파티션 오류 등 비정상적인 상황에서 클러스터에 동시에 리더가 하나만 존재하도록 어떻게 보장합니까? Raft 알고리즘에 의한 리더 선출 과정을 설명해보자.

4. 리더 선택 프로세스

4.1 초기 상태

초기 상태에서는 클러스터의 모든 노드가 팔로어입니다.

아래 그림과 같이 3개의 노드(Node) a, b, c가 있고 항(Term)은 0입니다.

초기 상태

4.2 후보 되기

Raft 알고리즘은 랜덤 타임아웃 기능을 구현하며, 각 노드가 리더 노드의 하트비트 정보를 기다리는 타임아웃 간격은 랜덤입니다. 예를 들어, 노드 A의 대기 시간 초과 간격은 150ms이고, 노드 B의 대기 시간 초과 간격은 200ms, 노드 C의 대기 시간 초과 간격은 300ms입니다. 그런 다음 먼저 타임아웃됩니다. 먼저 리더의 하트비트 정보를 기다리지 않기 때문에 타임아웃됩니다. 아래 그림과 같이 3개 노드에 대한 타임아웃 타이머가 실행되기 시작합니다.

Timeout

노드 A의 시간 초과가 만료되면 노드 A는후보가 되어 용어 수를 늘리고 용어 값을 0에서 1로 업데이트한 후 자신에게 투표합니다.

• 노드 A: 기간 = 1, 투표 수 = 1.
• 노드 B: 용어 = 0.
• 노드 C:용어=0.

후보자 되기

4.3 투표

후보자가 어떻게 리더가 되는지 살펴보겠습니다.

리더 선거

• 단계: 노드 A가 후보가 된 후 다른 노드에 RPC 투표 요청 메시지를 보내 자신을 리더로 선출하도록 요청합니다.
• 2단계: 노드 A가 보낸 투표 요청 정보를 받은 후 노드 B와 노드 C는 1번 기간 동안 투표 없이 노드 A에 투표하고 자신의 기간 번호를 추가합니다.
• 3단계: 노드 A는 3표를 받고, 노드 과반수의 표를 얻어 이번 임기 동안 후보로부터새로운 리더가 되었습니다.
• 4단계: 리더인 노드 A는 고정된 간격으로 노드 B와 노드 C에 하트비트 정보를 전송하여 노드 B와 C에 내가 리더임을 알리고 다른 추종자를 조직하여 새로운 선거를 시작합니다.
• 5단계: 노드 B와 노드 C는 노드 A에 응답 정보를 보내 노드 A에게 내가 정상임을 알립니다.

4.4 Term

영어로 Term이고, 리더에게는 임기가 있습니다.

• 자동 증가: 팔로어가 리더의 하트비트 정보가 타임아웃될 때까지 기다린 후 자신을 후보로 추천하면 위 그림과 같이 노드 A의 기간이 0이 됩니다. 팔로어가 자신을 후보로 추천하면 해당 용어의 숫자는 1로 증가합니다.
• 더 큰 값으로 업데이트: 노드가 자신의 항 번호가 다른 노드의 항 번호보다 작은 것을 발견하면 더 큰 값으로 업데이트됩니다. 예를 들어, 노드 A의 임기는 1이고 투표를 요청합니다. 투표 메시지에는 노드 A의 임기 번호가 포함되어 있으며 그 숫자는 1입니다. 노드 B는 메시지를 받은 후 임기 번호를 1로 업데이트합니다.
• 팔로어로 되돌리기: 후보자나 리더가 자신의 임기가 다른 노드의 임기 수보다 적다는 것을 알게 되면 즉시 팔로어 상태로 되돌아갑니다. 이 시나리오는 파티션 오류가 복구되고 용어 3의 리더가 용어 4의 하트비트 메시지를 받은 후 전자가 즉시 팔로어 상태로 돌아갈 때 발생합니다.
• 거부 메시지: 노드가 더 작은 기간 번호 값에 대한 요청을 받으면 해당 요청을 직접 거부합니다. 예를 들어 기간 번호 6인 노드 A는 기간 번호 5인 노드 B로부터 투표 요청을 받습니다. RPC 메시지가 나타나면 노드 A는 메시지를 거부합니다.

4.5 선거 규칙

• 임기 동안 문제(예: 다운타임) 또는 네트워크 문제(지연)가 발생하고 다른 노드가 새로운 선거를 시작할 때까지 리더는 항상 리더가 됩니다.
• 선거에서 각 서버 노드는 한 임기 번호에 대해 최대 한 번 투표하며 투표가 완료된 후에는 사라집니다.

4.6 대부분

클러스터가 N개의 노드로 구성되어 있다고 가정하면 대다수는 최소한 N/2+1입니다. 예를 들어 노드가 3개 있는 클러스터의 경우 대부분은 2개입니다.

4.7 하트비트 시간 초과

여러 노드가 동시에 투표를 시작하는 것을 방지하기 위해 각 노드에는 무작위 선택 시간 초과가 할당됩니다. 이 시간 동안 노드는 후보가 될 수 없으며 시간이 초과될 때까지만 기다릴 수 있습니다. 예를 들어, 위의 예에서 노드 A가 먼저 시간 초과되고 먼저 후보가 됩니다. 이 영리한 설계를 사용하면 대부분의 경우 동시에 선거를 시작하는 대신 하나의 서버 노드만 먼저 선거를 시작하므로 투표 분할로 인한 선거 실패 횟수가 줄어듭니다.

후보 되기

5. 리더 실패

리더 노드가 실패하면 새로운 라운드의 선거가 시작됩니다. 아래 그림과 같이 리더 노드 A가 실패하면 노드 B와 노드 C가 리더를 다시 선택합니다.

리더 실패

• 단계: 노드 A에failure가 발생하고 노드 B와 노드 C가 리더 노드 A의 하트비트 정보를 수신하지 못하며 대기 시간이 초과됩니다.
• 두 번째 단계: 노드 C가 먼저 시간 초과되고 노드 C가후보가 됩니다.
• 3단계: 노드 C는 노드 A와 노드 B에 투표 정보 요청을 시작합니다.
• 4단계: 노드 C는 투표에 응답하여 C에게 투표했지만, 노드 A는 실패로 인해 C의 투표 요청에 응답할 수 없었습니다.
• 5단계: 노드 C는 2표(과반수 투표)를 받고리더가 됩니다.
• 6단계: 노드 C는 노드 A와 B에 하트비트 정보를 보냅니다. 노드 B는 하트비트 정보에 응답합니다. 노드 A는 A에 결함이 있기 때문에 하트비트 정보에 응답하지 않습니다.

요약

Raft 알고리즘은 다음과 같은 방법을 사용하여 리더십 선거를 수행하여 한 임기 동안 리더가 한 명만 있도록 하여 선거 실패 횟수를 크게 줄입니다.

• Term
• 리더 하트비트 정보
• 무작위 선거 시간 초과
• 선착순 투표 원칙
• 다수 투표 원칙

이 글에서는 Raft 알고리즘이 애니메이션을 통해 리더를 선출하는 방법을 더 쉽게 이해하고 소화할 수 있습니다.

위 내용은 분산 시스템이 반드시 알아야 할 합의 알고리즘: Raft의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!