분산 시스템이 반드시 알아야 할 합의 알고리즘: Raft-일체 포함-php.cn

1. Raft 개요

Raft 알고리즘은 분산 시스템 개발을 위한 첫 번째 선택입니다.합의 알고리즘. 예를 들어 Etcd와 Consul이 현재 인기가 있습니다. Raft 算法是分布式系统开发首选的共识算法。比如现在流行 Etcd、Consul。

如果掌握了这个算法，就可以较容易地处理绝大部分场景的容错和一致性需求。比如分布式配置系统、分布式 NoSQL 存储等等，轻松突破系统的单机限制。

Raft 算法是通过一切以领导者为准的方式，实现一系列值的共识和各节点日志的一致。

二、Raft 角色

2.1 角色

跟随者（Follower）：普通群众，默默接收和来自领导者的消息，当领导者心跳信息超时的时候，就主动站出来，推荐自己当候选人。

候选人（Candidate）：候选人将向其他节点请求投票 RPC 消息，通知其他节点来投票，如果赢得了大多数投票选票，就晋升当领导者。

领导者（Leader）：霸道总裁

 이 알고리즘을 익히면 대부분의 장면을 쉽게 처리할 수 있습니다.<code style="Background-color: rgb(231, 243, 237); padding: 0px 3px; border-radius : 4px; Overflow-wrap: break-word; text-indent: 0px;">내결함성

및일관성 요구 사항. 예를 들어 분산 구성 시스템, 분산 NoSQL 스토리지 등은 시스템의 단일 머신 한계를 쉽게 극복할 수 있습니다.

Raft 알고리즘은 리더를 기반으로 모든 방법을 통해 각 노드의 로그에 대한 일련의 값과 일관성에 대한 합의를 달성합니다.

2. 뗏목 역할

2.1 역할

팔로워: 일반인, 리더의 하트비트 정보가 만료되면 조용히 리더로부터 메시지를 받습니다. 그는 솔선하여 자신을 후보로 추천할 것입니다.

후보: 후보는 다른 노드에게 투표 RPC 메시지를 요청하여 다른 노드에게 투표를 알리고, 투표에서 과반수를 얻으면 리더로 승격됩니다.

리더: 압도적인 대통령, 모든 것이 나에게 달려 있습니다. 쓰기 요청을 처리하고, 로그 복제를 관리하고, 지속적으로 하트비트 정보를 전송하여 교체할 새 리더를 찾을 필요 없이 "나는 리더이고 아직 살아 있지만 당신은 원하지 않습니다"라고 다른 노드에 알리고 새 선택을 시작합니다. 나.

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

Role

3. 단일 노드 시스템 분산 시스템이 반드시 알아야 할 합의 알고리즘: Raft

3.1 데이터베이스 서버

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

Database Server

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

왼쪽의 녹색 원이 클라이언트이고, 오른쪽의 파란색 원이 Node a(노드 a)입니다. 임기는 임기를 의미하며 이에 대해서는 나중에 논의합니다.

Client

🎜🎜3.3 클라이언트는 서버에 데이터를 보냅니다🎜🎜🎜클라이언트는 단일 노드 서버에 업데이트 작업을 보내고 데이터베이스에 저장된 값을 8로 설정합니다. 독립형 환경(단일 서버 노드)에서는 클라이언트가 서버로부터 얻는 값도 8입니다. 일관성을 보장하는 것은 매우 쉽습니다. 🎜🎜🎜🎜🎜클라이언트가 서버로 데이터를 보냅니다🎜🎜🎜3.4 여러 노드가 일관성을 어떻게 보장합니까? 🎜🎜🎜하지만 서버 노드가 여러 개인 경우 일관성을 보장하는 방법은 무엇입니까? 예를 들어 a, b, c라는 세 개의 노드가 있습니다. 아래 그림과 같이. 이 세 개의 노드는 데이터베이스 클러스터를 형성합니다. 클라이언트가 이 세 개의 노드에서 업데이트 작업을 수행할 때 세 개의 노드에 저장된 값이 일치하는지 어떻게 보장할 수 있나요? 이는 분산 일관성 문제입니다. Raft 알고리즘은 이 문제를 해결하기 위해 여기에 있습니다. 물론 이를 보장할 수 있는 다른 프로토콜도 있습니다. 이 기사에서는 Raft 알고리즘에만 중점을 둡니다. 🎜

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

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

4. 리더 선택 프로세스

4.1 초기 상태

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

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

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

초기 상태

4.2 후보 되기

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

Timeout

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

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

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

후보자 되기

4.3 투표

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

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

리더 선거

단계 : 노드 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가 먼저 시간 초과되고 먼저 후보가 됩니다. 이 영리한 설계를 사용하면 대부분의 경우 동시에 선거를 시작하는 대신 하나의 서버 노드만 먼저 선거를 시작하므로 투표 분할로 인한 선거 실패 횟수가 줄어듭니다.

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

후보 되기

5. 리더 실패

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

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

리더 실패

단계 : 노드 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에 결함이 있기 때문에 하트비트 정보에 응답하지 않습니다.