06.分布式共识算法-可信

约 3146 字大约 10 分钟...

基本概念：

容错：代表了在异常情况下仍然具有可用性和正确性。（前提是大部分节点正常）
共识：代表的是数据的一致性，它意味着即便是在并发、异常等情况下也能达成共识（前提是没有叛徒）

Paxos：

角色：

提议者（proposer）：提出提案的节点
接收者（acceptor）：接受并投票提案的节点
学习者（learner）：接收来自接受者的Accept通知，了解最终被接受的提案

核心思想：多轮投票

通过让proposer 与大多数 acceptor 提前进行一次交流，让 proposer 感知到当前提出的值是否可能被大多数 acceptor 接收
如果不能被接收，proposer 可以改变策略之后（例如增加提议编号，或接收某一个 proposer 已经提出的值）再继续进行协调，最终让大多数acceptor就某一个值达成共识
通过提议编码保证了后面被接收的值一定是编号更大的值，从而实现了写操作的线性一致性

达成共识过程：（先测试是否能通过、调整后再真正提议）

Prepare 准备阶段：
- 提议者：选择一个新的提案，编号为N，并向所有接受者发送该Prepare请求
Promise 承诺阶段：
- 接受者：收到Prepare请求后：
  - 如果提案 编号N > 之前收到的所有提案编号：
    - 承诺不再接受编号小于N的提案（只接受到比本地编号大的提案）
    - 返回Promise响应，响应内容：接收到的最高编号的提案和提案内容（此时可能返回的是其他提议者编号）
  - 如果提案 编号N <= 之前收到的所有提案编号：
    - 不会给出承诺，并且拒绝提案，返回Nack响应（拒绝响应）
Propose 提议阶段：
- 提议者：
  - 收到大多数接受者的Promise响应后，进入提议阶段
  - 根据接受者返回的提案，选择一个提案值V，并向所有接受者发送Propose请求，包含提案编号N和提案值V。
  - 如果所有Promise响应中没有任何提案值，提议者可以选择任意值V作为提案值。
Accept 接受阶段：
- 接受者：收到Propose请求后，如果此次提案编号N大于或等于之前承诺的提案编号，则接受该提案，并通知提议者和学习者。
- 提议者：收到大多数接受者的Accept响应，认为提案已经被接受，并通知所有学习者该提案已经被选定。
图解：
容错的实现：
- 不需要所有接受者响应，满足大部分即可，（多数派（quorum）原则，至少一半）

Raft 算法：

具体应用场景：

etcd、tidb、consul、nacos

重要！：

将每一个对Raft集群的操作称为一个提案，希望Raft集群对外屏蔽内部的网络或节点异常，依次对每一个提案作出响应，提交成功的提案可以在后续操作中持续可见。
这里的提案需要是幂等的，即重复执行不会导致集群状态不同。

角色：

领导者（Leader）：
- 集群中的管理者
- 所有client的流量都从leader这里经过；负责日志复制；
- 周期性的向follower发出心跳维持统治；
- 当发现自己不是leader的时候会转为follower
候选人（Candidate）：
- 集群的候选者，会发起投票试图当选leader
跟随者（Follower）：
- 集群中的被管理者，只会对其它服务器的命令做出响应。
- 在长时间得不到leader响应之后会转为candidate
任期（term）：
- 在raft协议中实际是作为逻辑时钟，系统中处于最新term的节点才是安全有效的。

核心思想：

Raft算法通过领导者选举和日志复制两个主要机制，进而保证所有节点的最终状态是一致的
Raft将共识问题分解为以下三个子问题：
- 领导者选举（Leader Election）：在集群启动或领导者故障时，选举出一个新的领导者。
- 日志复制（Log Replication）：领导者将客户端请求作为日志条目追加到本地日志中，并将其复制到所有跟随者（Followers）。
- 安全性（Safety）：确保所有节点最终达成一致，即所有节点的日志内容相同。

节点间通讯：

基于RPC：
- 请求投票（RequestVote）RPC
  - 由候选人在选举期间发起，通知各节点进行投票
- 日志复制（AppendEntries）RPC
  - 由领导者发起，用来复制日志和提供心跳消息

选举过程：

选举超时：

如果跟随者在选举超时时间内没有收到领导者的心跳消息，它会变成候选者并开始发起选举
每个跟随者都有一个随机的选举超时时间。
注意： RAFT的选举超时时间是随机超时时间间隔，确保不会有大量候选者同时发起选举，在超时之后重试即可重新选举成功

发起选举：

候选者递增自己的任期号（term），并向集群中的其他节点发送请求投票（RequestVote）消息。

请求投票（RequestVote）

候选者先投自己一票，并发送RequestVote消息给其他节点，RequestVote消息包含以下信息（其他节点投票依据）：
- 候选者的任期号（term）
- 候选者的ID（candidateId）
- 候选者日志中最后一个日志条目的索引（lastLogIndex）
- 候选者日志中最后一个日志条目的任期号（lastLogTerm）

投票规则：

`任期号检查`：

如果 请求投票任期号 < 当前任期号，那么拒绝投票，并返回当前的Term
否则，将请求投票任期号作为当前任期号，并将自身状态切换成Follower，并重置投票状态

`检测当前节点的投票状态`：

规则：每个节点在一个任期内只能投票给一个候选者
如果节点没有给任何其他候选者投过票，或者是已经给该候选者投过票，那么继续日志检查
如果当前节点自己也是候选者，且选举超时时间内，收到其他候选者的请求投票，则比较自己任期号和日志新旧，如果别人的新，则更新自己的任期号，并回到跟随者状态
否则，拒绝投票

`日志新旧检查`（在任期号相等时的进一步比较）

检测候选者的日志是否至少比当前节点的日志新，从而确保新选举出来的Leader不会丢失已经提交的日志：
- 日志新、旧比较标准：
  - 首先比较最后一个日志条目的任期号（lastLogTerm），任期号大的，日志新
  - 如果两者任期号相同，则比较最后一个日志条目的索引（lastLogIndex），索引大的，日志新
如果候选者日志新，则投票给候选者
否则，那么就拒绝投票

投票结果（选举超时时间内）：

结果1：自己选举成功：
- 候选者收到大多数节点的赞成票后，当选为领导者。（多数派（quorum）原则，至少一半）
- 当选领导者后，开始发送心跳消息给所有跟随者，宣布自己成为领导者，中指选举，保持自己领导者状态
结果2：期间其他节点成为领导者：
- 选举期间收到其他候选者的RequestVote，并且Term和日志都比自己大，则自己变成跟随者
结果3：选举超时或者没有节点选举成功：
- 超时后重新发起选举

日志复制：

概念：

日志条目（Log Entry）：每个日志条目包含一个客户端请求和相关的元数据（如索引和任期号）。
日志索引（Log Index）：日志条目在日志文件中的位置。日志项对应的整数索引值。它其实就是用来标识日志项的，是一个连续的、单调递增的整数号码
任期号（Term）：创建这条日志项的领导者的任期编号。
指令：一条由客户端请求指定的、状态机需要执行的指令。即客户端指定的数据。

日志复制过程：（优化后的二阶段提交）

领导者接收请求：

领导者节点接收到客户端的写请求，将请求作为新的日志条目追加到本地日志中

领导者发送AppendEntries RPC 给所有追随者：

领导者将新的日志条目复制到所有跟随者，发送AppendEntries消息

跟随者处理AppendEntries RPC：

跟随者收到AppendEntries消息后，首先验证prevLogIndex和prevLogTerm是否匹配。如果匹配，则将新的日志条目追加到本地日志中
- 怎么理解验证prevLogIndex和prevLogTerm是否匹配？见下方：日志的一致性保证
跟随者将处理结果（成功或失败）返回给领导者

日志确认和提交：

领导者收到大多数跟随者的AppendEntries响应后，认为日志条目已经被复制到大多数节点。
领导者将这条日志项应用到它的状态机中，更新已提交日志索引，并将提交的信息发送给所有跟随者

跟随着提交并应用到状态机：

跟随者收到提交信息后，将日志条目标记为已提交，并应用到状态机

个人理解：

领导者先写日志，通知跟随者写日志
大多数跟随者写日志成功，领导者将日志改为提交状态，并应用到状态机，响应客户端。
跟随者收到领导者的消息，也提交状态并应用到状态机

日志一致性保证：

准则：

领导者通过强制跟随者直接复制自己的日志项，处理不一致日志。Raft日志是以领导者的日志为准。
Raft中日志必须是连续的，Paxos没这个要求

具体：

找到差异日志项起始Entry：
- 领导者通过日志复制 RPC消息，发送自己当前最新日志项给某个跟随者，消息包含PrevLogEntry和PrevLogTerm
- 如果跟随者在它的日志中找不到PrevLogEntry：
  - 那么日志复制 RPC 返回失败，跟随者就会拒绝接收这个新的日志项的写入
  - 也就是说它的日志和领导者的不一致了，并返回失败信息给领导者
- 失败时领导者会递减要复制的日志项的索引值，并发送新的日志项到跟随者
- 直到跟随者在它的日志中找到某个PrevLogEntry：
  - 那么日志复制 RPC 返回成功，这样领导者就知道跟随者的日志项与自己相同的起始位置。
覆盖更新起始Entry后的所有Entry：
- 领导者通过日志复制RPC，复制并更新覆盖起始Entry之后的日志项，最终实现了集群各节点日志的一致。
图解：
视频介绍：
- http://thesecretlivesofdata.com/raft/