分布式共识 raft算法简介
Raft 算法是Multi-Paxos，先有Paxos 后有Raft，Raft可以认为是Paxos的一个工程实现，增加了一些额外的细节限制等，也相对更容易理解。全新的系统大多选择了 Raft 算法，或者说有些是类Raft（比如 Etcd、Consul、Kafka、CockroachDB）。
## 相关资源
`https://raft.github.io/`
官网有详细的说明，一定注意到这两块内容，相关文献以及课程
!(data/attachment/forum/202212/06/224218qrhzm9c4i9rrpd9y.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/300 "image.png")
!(data/attachment/forum/202212/06/224225dg4pu33p4uuu44gp.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/300 "image.png")
在线动画教学演示：
`http://thesecretlivesofdata.com/raft/`
论文下载:
`https://raft.github.io/raft.pdf`
`https://web.stanford.edu/~ouster/cgi-bin/papers/OngaroPhD.pdf`
`https://www.usenix.org/conference/atc14/technical-sessions/presentation/ongaro`
In Search of an Understandable Consensus Algorithm(Extended Version) 译文:
`https://zhuanlan.zhihu.com/p/539715946`
`https://zhuanlan.zhihu.com/p/524885008`
对于一些经典论文的中文版,直接以英文名称搜索就会找到很多
B站视频:
`https://www.bilibili.com/video/BV1Db411w7ej/?spm_id_from=333.999.0.0&vd_source=7741be735669cf4a8d044c6942e6c0e3`
youtube:
`https://www.youtube.com/watch?v=YbZ3zDzDnrw&list=WL&index=4&ab_channel=DiegoOngaro`
视频ppt下载地址:
`https://gitee.com/crazybytex/some-documents/blob/master/Raft%20A%20Consensus%20Algorithm%20for%20Replicated%20Logs.pdf`
其名字即来自于 R{eliable|plicated|dundant} And Fault-Tolerant， 也来自于这是一艘可以帮助你逃离 Paxos 小岛的救生筏（Raft）。
名字来源：
`https://groups.google.com/g/raft-dev/c/95rZqptGpmU`
!(data/attachment/forum/202212/06/205546zxnrjaiz3auaynr0.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/300 "image.png")
## Raft
首先看下官网的简介：
Raft是一种易于理解的共识算法。
它在容错性和性能方面与Paxos相当。
不同之处在于，它被分解为相对独立的子问题，并且清晰地解决了实际系统所需的所有主要部分。
我们希望Raft将为更广泛的受众提供达成共识，并且这一更广泛的受众将能够开发出比现在更高质量的基于共识的系统。
也可以认为就是一个更接地气的Paxos变种，接地气就是更容易理解和编程实现。
学习之前，建议可以扫一遍中文译本，相对于paxos来说，raft是易于理解学习的。
Raft是一种管理复制日志（replicated log）的算法
!(data/attachment/forum/202212/07/163352rranarhxcxxkpp9x.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/300 "image.png")
图 1. 复制式状态机架构。 共识算法管理着客户端发来的状态机命令的一个日志副本 （replicated log），状态机以完全相同的顺序执行日志中的命令，因此产生完全相同的输出。
!(data/attachment/forum/202212/07/163643zp2kwipvniq66366.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/300 "image.png")
图2. Raft 一致性算法的总结（不包括成员变化和日志压缩）
关于状态机的论文:
**Implementing fault-tolerant services using the state machine approach: a tutorial** `https://dl.acm.org/doi/10.1145/98163.98167`
### 核心
Raft算法的核心主要包括三部分:
!(data/attachment/forum/202212/07/231029td9d55ze99t9eilt.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/300 "image.png")
Leader选举：如何选出Leader节点作为统筹协调者
日志复制：主从之间的同步问题
成员变更：出现网络分区或者某节点故障时，如何保障成员变更以及一致性的正确性
关于安全性
!(data/attachment/forum/202212/07/164125wes9b1me19heepww.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/300 "image.png")
图 3：Raft 保证每个属性在任何时刻都为真
Election Safety:在一个特定的任期中至多选出来一个leader
LeaderAppend-Only: leader 从不重写或删除它自己的日志条目，它只新增条目
Log Matching:如果两条日志包含相同的索引和任期的条目那么该日志在从给定索引起的所有条目中都是相同的。
Leader Completeness: 如果一个日志条目在给定的任期中提交那么该条目将出现在leader 中的所有更高序号的任期中。
如果一个服务器将给定索引的日志条目应用到其状态机State Machine Safety:那么其他服务器不会在同一索引上应用不同的日志条目。
上面几个英文图，都来自论文In Search of an Understandable Consensus Algorithm(Extended Version)
### 成员角色
!(data/attachment/forum/202212/07/111750t1q34hwchmz1d1z3.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/300 "image.png")
Leader是团队的总控，中央集权式的管理方式
Follower是听从命令的，接收处理Leader的请求命令，如果心跳超时，那么也要跳出来作为候选人参与下一轮的Leader选举；
Candidate就是如果此时Leader不存在，或者状态不可用，参与选举的状态。
显然，大多数时候是有Leader和Follower两种角色，只有选举的过程中才会有Candidate，而且每个节点的角色也都是可能发生变化的。
而且，任意某时刻，每个节点只会处于一种角色。
下图是论文中关于状态的描述。
!(data/attachment/forum/202212/07/114115truw9uwrwlppwqww.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/300 "image.png")
先抛出几个概念。
#### 任期 term
任期是一段连续的时间段，每开启一个新的任期说明进入了下一轮选举，选举Leader成功就会运行下去，如果失败就会继续开启下一个任期，继续选举，直到选择出来
#### 随机超时时间 timeout
为了解决冲突问题，采用了随机超时时间这种简单有效的方式，因为系统其实大多数时候这些节点都是一样的，选择谁都可以，重点反而是尽快的达成一致。
如果希望最早提出的就被选举为Leader，那么这就是一种比较简单快速的方案，而为了保障大概率的有那么一个先后顺序，所以采取了随机时间，每个人150ms-300ms范围内，随机，大概率不会冲突，万一冲突了，就在开启下一轮即可，不太可能随机的时间，还总是出奇的一致。
随机时间分为两种，一种是心跳超时时间，也就是超过了多久未收到心跳开始重新发起选举
还有一个是当发起投票碰巧冲突了之后，需要开启下一轮选举投票，这个时间停止-重新开始的时间也是随机的。
#### 消息类型
消息都是通过RPC调用发起的，分为两种RequestVoteRPC 以及AppendEntriesRPC
RequestVote就是选举投票请求，当你是Candidate时，想要别人给你投票，就发这个消息
AppendEntries 是心跳消息，如果携带了复制log，那就也是同步复制消息
## Leader选举
Raft算法中，Leader是非常重要的角色，因为所有的后续操作都是以Leader为主进行控制操作的。
`http://thesecretlivesofdata.com/raft/`
在选举Leader过程中的状态转换图
!(data/attachment/forum/202212/07/141714r1l3pf87qf0p5psk.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/300 "image.png")
最一般的形式：
初始时，大家都默认为Follower，但是迟迟等不到心跳，他们就都化身Candidate。（图一）
因为等待超时时间是随机的，所以就会有人开始先投自己一票，然后发起RequestVoteRPC，希望别人投自己一票。（图二）
如果其他人此时发现自己在term任期内，没有投过票，直接投票给他（图三）
然后此时获得了大多数，那就成功成为Leader，他就给其他人发送心跳消息 AppendEntries（图四）
其他人接收到心跳消息，会进行响应，这就完成了Leader选举（图五）
下图来自演示动画。
!(data/attachment/forum/202212/07/144753zao7fjn6mk6fn0aj.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/300 "image.png")
当然，这是最一般的情况，最顺利的那一种，节点A成为了Leader。
!(data/attachment/forum/202212/07/150418bmnnox7mqm9ccza5.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/300 "image.png")
这个过程就只有三种可能：
对于节点A来说，自己成功选举为Leader；
对于其他两个节点来说，别人成功选举为Leader；
还有一种可能就是大家都没有成为主，比如四个节点，其中两个同时发起，各自都只是收到额外的一票，加上自己的一票，都是两票，选举冲突，随机时间后，重新进入下一轮。
比如下图所示，发生冲突。
节点B和节点D同时发起，所以节点A、C需要接收来自B、D的消息（图一）
但是对于A、C来说，各自只有一张票，也只能先接收到一条请求（图二）
而且也只能投出来一票，A、C分别投票给了B、D（图三）
此时，对于发起者B、D都只是拿到两票，无法继续，只能重新开始下一轮，也就是四个人继续按照随机时间开始抢占发起投票请求。
!(data/attachment/forum/202212/07/152149juyi7f3k23dktxfu.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/300 "image.png")
### 细节
**term id**作为逻辑时钟（logical clock），在每个RPC消息中都会带上，用于检测过期的消息，也用于标记选举轮次。比如当超时转换为Candidate时，term+1，发起RequestVote RPC请求。
每个term最多只有一个leader，Leader选举成功后，发送的心跳会带有这个 term id，其他节点收到心跳消息后：
1. 消息中的term id比本地的 term id更大时，就更新本地的term id为消息中的；
2. 而且如果当前state为leader或者candidate时，将自己的状态切成follower。（Candidate时说明别人选举成功了，leader可能是自己刚才被网络分区了，现在又接入到大多数的网络上了，要跟随别人）；
3. 如果来的消息比本地的term id还小，那就直接拒绝；
因为逻辑时钟，就代表了时间的推移，肯定是越大越新
**投票策略**
每个节点只会在每个term中投一票，比如上面四个节点，投票冲突的场景，B、D都会给其他三个节点发，比如B，发给ACD，A、C也只会投出一票。
另外，当任期编号相同时，日志完整性高的（也就是最后一条日志项对应的任期编号值更大，索引号更大），拒绝投票给日志完整性低的Candidate。
日志完整性比较的就是下面日志复制部分说到的log index 和term，换言之其实就是实时性高的拒绝给实时性低的投票，同步的越快肯定log index越大，也就越新。
如果两份日志最后条目的任期号不同，那么任期号大的日志更新
如果两份日志最后条目的任期号相同，那么谁的日志更长，谁就更新
## 日志复制
在 Raft 算法中，副本数据是以日志的形式存在的，领导者接收到来自客户端写请求后，处理写请求的过程就是一个复制和提交日志项的过程。
日志就是一种数据格式，形式如下图所示：
!(data/attachment/forum/202212/07/172345glc8zjwuc46c3bud.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/300 "image.png")
图 6：日志由有序序号标记的条目组成。每个条目都包含创建时的任期号（图中框中的数字），和一个状态机需要执行的指令。一个条目当可以安全地被应用到状态机中去的时候，就认为是可以提交了。
| 名称 | 说明 |
| ----------------------- | -------------------------------------------------------------------------------------------------------------- |
| log index<br />索引值 | 日志项对应的整数索引值。<br />它其实就是用来标识日志项的<br />是一个连续的、单调递增的整数号码。 |
| term<br />任期编号 | 创建这条日志项的领导者的任期编号。<br />方框内上面的数字 |
| command<br />指令 | 一条由客户端请求指定的、状态机需要执行的指令。<br />可以将指令理解成客户端指定的数据。<br />方框内下面的数据 |
图中，不同的followers的进度不同，表明了复制的过程，不同的节点复制Leader节点的数据速度不一样，这很正常。
### 示例
初始时，正常运行，Leader与Follower心跳相互交互维持连接
!(data/attachment/forum/202212/07/174714vo779jtevj8ju9g8.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/300 "image.png")
此时客户端发来消息，请求更新数据，SET 5
!(data/attachment/forum/202212/07/175006s67p5cnvru6il7p7.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/300 "image.png")
Leader将SET 5 发送到所有的Follower
一旦获得大多数的响应，也就是确认大多数都收到了这条消息，自己就会进行提交（commit）
也就是图中节点A变成了5
!(data/attachment/forum/202212/07/175212aritiv18o2nh4ha5.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/300 "image.png")
然后节点A就给客户端发送消息，告诉他这条消息处理成功
!(data/attachment/forum/202212/07/175401u1e7ir3r3bxqcz0e.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/300 "image.png")
在下一次的心跳消息（或者复制命令，也就是心跳中也包含了后续的更新命令时）
Leader 会告诉Follower他们，已经提交的最大编号（commited log index）
Follower发现之前的SET 5 还没有提交，然后就会进行数据提交，最终都变成了5
!(data/attachment/forum/202212/07/175643jl5cc8chdhd055ch.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/300 "image.png")
### 步骤
1. 客户端发起请求
2. Leader将客户端的请求数据，新增日志条目，写入本地日志
3. 对Follower发送日志复制消息append entries
4. 获得了大多数的响应
5. Leader 对这条数据进行commit
6. 执行结果发送给客户端
7. 下一次的心跳或者日志复制消息发送时，会附加Leader提交的最大的log index
8. Follower发现已经提交的最大的log index自己还没有提交，所以进行提交
!(data/attachment/forum/202212/07/225326zx4ot44o771zg11j.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/300 "image.png")
上面的步骤中可以发现，Leader收到大多数Follower的响应后，没有类似两阶段提交发送commit请求，因为Leader的日志复制 RPC 消息或心跳消息，包含了当前最大的，被提交的日志项索引值。
所以通过日志复制 RPC 消息或心跳消息，跟随者就可以知道Leader的日志提交位置信息。
这减少了一次RPC请求，客户端也更早的得到了处理结果。
以上是一个整体大致的流程，那么对于日志复制来说，还有更细节的问题需要处理
对于Leader来说，只关注大多数，因为通过RPC发送消息，必然可能出现消息丢失、网络问题，也可能某机器宕机等，如何对具体的每一条日志进行处理呢？
从一个一致性的状态+严格顺序的指令，最终才能达到一致性的状态。
参照下图也就是对于每一条日志的复制，如何保障顺序？
!(data/attachment/forum/202212/07/231447lvsmkidiczill9vs.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/300 "image.png")
正常的情况下，只需要一条一条处理就好了，但是如果出现了问题有丢失或者错误问题怎么办呢？
比如下图中当前需要发送log index 7 term 4 command是x<-5
!(data/attachment/forum/202212/07/233655v6a6hg31fofgcom8.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/300 "image.png")
如何保障有序呢?
答案是根据上一个日志点的位置数据（PrevLogEntry、PrevLogTerm），递归倒推确认，直到找到准确的日志点位。
1. Leader 当前需要发送log index 是7的日志，PrevLogEntry=6，PrevLogTerm=3
2. Follower发现自己的当前是log index是6 term是4 与Leader发来的日志不一致，于是拒绝处理
3. Leader 向前递减，于是打算发送log index 是6的日志，PrevLogEntry=5，PrevLogTerm=3
4. Follower发现此时的确是log index是5 term是3，那么返回处理成功
5. 于是Leader可以确认在log index是5 term是3的日志位置，是主从同步的位置，于是就从这个位置后面开始继续，而Follower中已经存在的log index 是6，term是4 command是x<-3的日志直接被覆盖舍弃了。
简单说就是：
首先，Leader通过日志复制 RPC 的一致性检查，找到Follower节点上，与自己相同日志项的最大索引值。
这个索引值之前的日志，Leader和Follower是一致的，之后的日志是不一致的了。
然后，Leader强制Follower更新覆盖的不一致日志项，实现日志的一致。
### 网络分区
在分布式环境下，有时由于网络通讯故障，而不是服务器上的应用故障，导致节点之间被分为几块区域，比如五个节点，ABC互相连通，EF互相连通，但是他们这两块之间不能互相连通。对于客户端来说，可能客户端 1看到的是ABC，客户端2看到的是DE，导致最终系统的服务不一致。
看一下如果遇到这种情况如何处理
如下图所示，ABCDE正常运行过程中，网络可能出现了问题，节点CDE无法与主Leader节点B进行联通。
!(data/attachment/forum/202212/08/110708p0mblamm3bbal83l.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/300 "image.png")
对于节点CDE来说，他们失去了与Leader节点B的联系，所以转换为Candidate，进行选主，最终他们三个节点，也选出来了一个主节点（三个节点选一个节点，正常没问题）
最终对外部客户端来说，可能就产生了两个服务分区，一个来自于BA一个来自于CDE
!(data/attachment/forum/202212/08/111039jn5b7kxbcxxo6h6b.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/300 "image.png")
最终对外部客户端来说，可能就产生了两个服务分区，一个来自于BA一个来自于CDE
下图左中，下面的客户端，发起设置命令，很显然，无法获得大多数的响应，所以失败了，日志为uncommited状态
下图右中，上面的客户端，发起设置命令，因为此时他们有三个节点，所以满足大多数要求，设置成功，完成commited
!(data/attachment/forum/202212/08/111413akh73stwd47xannf.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/300 "image.png")
当网络恢复后，主节点C发送的心跳数据节点AB可以收到，他们会发现自己的term比别人的小（也就是逻辑时钟term 比别人早，别人的是更新的），所以就会转换身份，变成Follower
节点B发送的数据，因为自己的term 比别人的小，所以别人都会拒绝他
也就是大家都会不接受B，但是B、A反而都接受了C为Leader
对于自己未提交的日志，会直接舍弃，然后按照前面讲的日志顺序保证的逻辑，同步到最后同步的位置，重新开始同步，最终达成一致。
!(data/attachment/forum/202212/08/112532cboy0bojfzj0lzm6.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/300 "image.png")
至此，当网络出现分区时，Raft也能够正确的对外客户端提供服务，而且网络恢复后能够达成一致性。
换言之，出了问题的分区虽然接受了请求，但是未提交，请求不成功，CDE三个组成的分区，占据了大多数，所以可以 正确的提供一致性的服务。
## 成员变更
以上所有的介绍，集群整体的个数都是不变的。
如果有成员加入或者退出如何处理呢？
网络分区或者故障导致的节点看起来的变化，不属于成员变更，因为对大家来说，还是那么多个节点，只不过是暂时失联或者故障。
最简单粗暴的方式就是停机->修改配置->重启，很显然这种处理方式太过粗暴
raft也提出了相关配置的处理方式。
在
`https://raft.github.io/raft.pdf`
In Search of an Understandable Consensus Algorithm(Extended Version)中，提出了：**joint consensus**
然后在他的博士论文
`https://web.stanford.edu/~ouster/cgi-bin/papers/OngaroPhD.pdf`
CONSENSUS: BRIDGING THEORY AND PRACTICE 提出了一种新的更简化的方式：**single-server changes**
single-server changes 本的出现意是为了简化、优化joint consensus
**但是却存在bug**，尴尬
详情参见：
`https://groups.google.com/g/raft-dev/c/t4xj6dJTP6E?pli=1`
!(data/attachment/forum/202212/08/170019rd5si5jwysbbwy0y.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/300 "image.png")
> Unfortunately, I need to announce a **bug** in the dissertation version of membership changes (**the single-server changes, not joint consensus**). The bug is potentially severe, but the fix I'm proposing is easy to implement.
>
> ......
>
> ......
>
> The bug:
>
> It's essential to Raft that if one decision (vote or commitment) is made in one quorum (majority), a subsequent quorum will contain at least one server that's aware of the decision, and this is needed even across membership changes. My dissertation shows how if two configurations differ by at most one server, a majority from the first and a majority from the second will have at least one server in common. Within a single term, a single leader can easily ensure that one configuration and the next differ by at most one server. This bug shows up across term boundaries. It's possible for two concurrent, competing changes across term boundaries to have quorums that don't overlap with each other, causing a safety violation (**split brain**).
知乎上也存在一些讨论和踩坑。
《TiDB 在 Raft 成员变更上踩的坑》 `https://zhuanlan.zhihu.com/p/342319702`
《关于 Raft 算法的 Single MemberShip 算法的疑问?》`https://www.zhihu.com/question/65667634`
换句话说，还是老老实实的使用joint consensus或者修复bug。
### 联合一致（joint consensus）
!(data/attachment/forum/202212/08/172202nsouf00k91uqn5uu.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/300 "image.png")
图 10：直接从一种配置转到另一种配置是不安全的，因为各个机器会在不同的时候进行转换。
> 在这个例子中，集群从 3 台机器变成了 5 台。
>
> 不幸的是，存在这样的一个时间点，同一个任期里两个不同的 leader 会被选出。
>
> 一个获得旧配置里过半机器的投票，一个获得新配置里过半机器的投票。
PS：
上图中，进度条就是随着时间的推移，有的节点很早就接受到了新的配置，有的节点，很晚才接受到新的配置
为了保证安全性，配置变更必须采用一种两阶段方法。目前有很多种两阶段的实现。
例如，有些系统（比如，）在第一阶段停掉旧的配置所以不能处理客户端请求；然后在第二阶段在启用新的配置。
在 Raft 中，集群先切换到一个过渡的配置，我们称之为联合一致（joint consensus）；
一旦联合一致已经被提交了，那么系统就切换到新的配置上。
联合一致结合了老配置和新配置，有以下约束：
* 日志条目被复制给集群中新、老配置的所有服务器。
* 新、旧配置的服务器都可以成为 leader 。
* 达成一致（针对选举和提交）需要分别在两种配置上获得过半的支持才能提交生效。
联合一致允许独立的服务器在不妥协安全性的前提下，在不同的时刻进行配置转换过程。
此外，联合一致允许集群在配置变更期间依然响应客户端请求。
!(data/attachment/forum/202212/08/172938pkrcq0fiyfkfh3e9.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/300 "image.png")
图 11：一个配置切换的时间线。
> 虚线表示已经被创建但是还没有被提交的配置日志条目，实线表示最后被提交的配置日志条目。
>
> 领导人首先创建了 C-old,new 的配置条目在自己的日志中，并提交到 C-old,new 中（C-old 的大多数和 C-new 的大多数）。
>
> 然后他创建 C-new 条目并提交到 C-new 中的大多数。这样就不存在 C-new 和 C-old 可以同时做出决定的时间点。
上图中就是按照时间线，分成了两段：
一段是C-old,newcommited的过程，一段是C-new commited的过程
**C-old,new 是old 和new的组合（C-old∪C-new），因为最终集群变更的方向并不一定就是简单的加机器，也可能减机器，或者加一些减一些。**
!(data/attachment/forum/202212/08/193040ajqjgutthyxgxdvy.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/300 "image.png")
leader 接收到一个改变配置从 C-old 到 C-new 的请求，它就为联合一致将该配置（图中的 C-old,new）存储为一个日志记录
然后复制到其他节点（日志条目被复制给集群中新、老配置的所有服务器。）
#### 关于分别在两种配置上获得过半的支持
!(data/attachment/forum/202212/08/195418urpxi3ggeg88fg58.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/300 "image.png")
假设旧配置的大多数为、新配置的大多数为， 那么这些节点都需要复制成功
不是单纯任意的五个里面选择三个
如果Leader正常运转，Cold和Cnew中的两个多数派确认了Cold U Cnew这条日志，主节点就提交这条日志；
C-old,new提交后，就会再次开始C-new的复制提交，这个过程就可以简单的理解为提交了两次日志复制（执行了两次指令而已），最终所有的节点都使用C-new。
分两次提交日志，也被叫做**两阶段成员变更**
对于新的节点 D、E，Raft 会通过日志一致性检查来复制领导者的所有日志条目，从而保证它们同样能够保持日志完整性，因为新节点正常肯定都是空的，以这种状态加入到集群中的时，它们需要一段时间来更新自己的日志，以便赶上其他节点，在这个时间段里面它们是不可能提交一个新的日志条目的。
为了避免因此造成的系统短时间的不可用，Raft 在配置变更前引入了一个额外的阶段。在该阶段中，新的节点以没有投票权身份加入到集群中来（leader 会把日志复制给它们，但是考虑过半的时候不需要考虑它们）。 一旦新节点的日志已经赶上了集群中的其他节点，那么配置变更就可以按照之前描述的方式进行了。
#### Leader崩溃
一旦某个服务器将该新配置日志条目增加到自己的日志中，它就会用该配置来做出未来所有的决策 (服务器总是使用它日志中最新的配置，**无论该配置日志是否已经被提交**）
如果Leader节点的C-old,new尚未推送到从节点，Leader就挂了，此后选出的新主节点并不包含这条日志，此时新主节点依然使用Cold作为自己的成员配置，集群是一致的。
如果Leader节点的C-old,new推送到大部分的Follower节点后就挂了，此后选出的新Leader节点可能是Cold也可能是C-old,new。如果是Cold的节点，它会强制日志同步，恢复至Cold状态，集群变更失败；如果是C-old,new的节点，此后客户端继续执行一次改变配置为Cnew的命令即可。无论哪种情况，最终集群都是一致的。肯定是不存在C-new单独做决策的
如果Leader在推送Cnew配置的过程中挂了，很显然，此时C-old,new已经提交了，Leader 完整特性（Leader Completeness Property）保证了只有拥有 Cold,new 日志的 candidate 有可能被选为Leader。Leader就可以安全地创建一个描述 Cnew 的日志条目并将其复制给集群中的其他节点了。
如果Leader崩溃了（开始复制到其他节点之后崩溃了）
**因为一旦某个服务器将该新配置日志条目增加到自己的日志中，它就会用该配置来做出未来所有的决策**（服务器总是使用它日志中最新的配置，**无论该配置日志是否已经被提交**）
#### 其他问题
**leader 有可能不是新配置中的一员**，因为配置变更是不确定的，没有要求不可以移除原有的Leader。
在这种情况下，leader 一旦提交了 Cnew 日志条目，它就会退位为 follower（Cold,new 状态下依旧可用）。
这就意味着有这样一段时间（leader 提交 Cnew 期间）：leader 管理着一个不包括自己的集群，它会复制日志给其他节点，但是算副本数量的时候不会算上自己。
leader 转换发生在 Cnew 被提交的时候，因为这是新配置可以独立运行的最早时刻（在这个时刻之后，一定是从 Cnew 中选出新的 leader）。在这个时间点之前，有可能只能从 Cold 中选出 leader。
还有就是**被移除的节点（不处于 Cnew 状态的节点）有可能会扰乱集群**。
这些节点将不会收到心跳信息，所以当选举超时时，它们就会进行新的选举过程。它们会发送带有新任期号的 RequestVote RPCs，这样会导致当前的 leader 回到 follower 状态，然后选出一个新的 leader。但是这些被移除的节点还是会收不到心跳，然后再次超时，再次循环这个过程，导致系统的可用性很差。
为了避免这个问题，**当节点认为当前有 leader 存在时，节点会忽略 RequestVote RPCs**。具体来说，**当一个节点在最小选举超时时间内收到一个 RequestVote RPC，它不会更新它的任期或授予它的投票**。这不会影响正常的选举，每个节点在开启一轮选举之前，它会至少等待一次最小选举超时时间。相反，这有利于避免被移除的节点的扰乱：如果一个 leader 能够发送心跳给集群，那它就不会被更大的任期号废黜。
### single server changes
两阶段成员变更，之所以分为两个阶段，是因为对Cold与Cnew的关系没有做任何假设，为了避免Cold和Cnew各自形成不相交的多数派选出两个主节点，才引入了两阶段方案。
!(data/attachment/forum/202212/09/105856hpq1fjlppyj58bqf.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/300 "image.png")
上图所示，如果形成了两个不相交的majority，就可以出现AB两种不同的结果，这就出现了问题。
!(data/attachment/forum/202212/09/110124kr7u55bl255zu21n.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/300 "image.png")
如果两个majority是相交的，那么就不可能出现不一致的情况。假设相交的节点的值为X：
假设蓝色区域值为A，红色区域值为B，X既属于A，那么必然与A一致，另外X又属于B，那么必然与B一致，所以X=A=B，不存在不一致。
#### 如何确保相交
所以如果要求Cold与Cnew任意的多数派交集不为空。
这两个成员配置就无法各自形成多数派，那么成员变更方案就可能简化为一阶段。
如何确保Cold与Cnew使之任意的多数派交集不为空呢？
方法就是每次成员变更只允许增加或删除一个成员。
!(data/attachment/forum/202212/09/110519q6g8zxi78z0txdz0.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/300 "image.png")
上图中演示了：从偶数和奇数大小的集群中添加和删除单个服务器。
在每个图中，蓝色矩形显示旧集群的大部分，红色矩形显示显示了新集群的大部分。在每一次服务器成员身份更改中，都会出现重叠在任何旧集群的大部分和任何新集群的大多数之间，保障了安全所需。
例如，在（b）中，大多数旧集群必须包括两个三台服务器，大多数新集群必须包括新集群中的三台服务器集群，其中至少两个必须来自旧集群
#### 示例
如下图所示，3节点转换为5个节点
!(data/attachment/forum/202212/09/112209raoaugaiirjrorgy.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/300 "image.png")
采用单节点变更，新增的两个节点采取两轮变化形式。
!(data/attachment/forum/202212/09/113524d6opqb73bg65bqpp.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/300 "image.png")
上图是依次执行的两轮，如果出现并发变更，一次单节点变更尚未完成，新的单节点变更又在执行，其实单节点又退化了，也就是无法保障必然有交集，这就是单节点的bug
> It's possible for two concurrent, competing changes across term boundaries to have quorums that don't overlap with each other, causing a safety violation (**split brain**).
解决方法就是：
> In a typical Raft implementation, a leader appends a no-op entry to the log when it is elected. This change would mean rejecting or delaying membership change requests until the no-op entry is committed.
在领导者启动时，创建一个 NO_OP 日志项（也就是空日志项），只有当领导者将 NO_OP 日志项提交后，再执行成员变更请求。（逻辑上可以理解类似为一把锁）
换句话说就是：“如果存在未完全复制的旧配置条目（该条目存储在至少一台服务器上，当前未提交，但将来可能会提交），领导者不得开始复制新配置条目。”
## 小结
重复下本文第一段话：
Raft 算法是Multi-Paxos，先有Paxos 后有Raft，Raft可以认为是Paxos的一个工程实现，增加了一些额外的细节限制等，也相对更容易理解。
他是一种基于日志复制的共识算法，非常接近于实践，因为节点之间同步数据、共识基本上都是基于日志复制的，Raft针对日志复制提供了详尽的实现方案。
全新的系统大多选择了 Raft 算法，或者说有些是类Raft（比如 Etcd、Consul、CockroachDB）。
再比如BRAFT 是百度开源的基于 BRPC 的 Raft 一致性算法和可复制状态机的工业级 C++ 实现。
官网上列举了一些，想要copy的时候，可以参考`https://raft.github.io/#implementations`
可以看到，作者自己也实现了一个`https://github.com/logcabin/logcabin`
!(data/attachment/forum/202212/09/141928rcd17d748shuff41.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/300 "image.png")
Raft虽然相对比paxos来说，可以认为是工业级的一种实现，但是，也还是有些细节待考虑，毕竟它是一种通用的共识算法
不过他是源于multi-paxos的，很多算法也都是来源于multi-paxos，所以鉴于主题思想一致的前提下，所有的实现都会有类似性，比如一个字无论何种字体，他都还是那个字，了解raft对于后续学习各种共识算法都很有意义。
!(data/attachment/forum/202206/16/141330jha7st9soow8772i.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/300 "common_log.png")
`转载务必注明出处：程序员潇然，疯狂的字节X，https://crazybytex.com/thread-245-1-1.html `
页:
[1]