《In Search of an Understandable Consensus Algorithm》这个论文中写的比较详细

https://raft.github.io/
https://github.com/goraft/raft
https://github.com/maemual/raft-zh_cn/blob/master/raft-zh_cn.md
http://thesecretlivesofdata.com/raft/

goraft是Raft协议的Golang版本的实现，项目地址为
https://github.com/goraft/raft

1,Raft算法的节点数量问题
Raft协议中主节点心跳失效后follower成为candidate并且在n/2个节点投票成为主节点，在RAFT协议集群中如何确认n是多少？动态增加机器如何变化n，超时多久应该认为节点为n-1?n固定好是动态调整好？

raft的 Cold+Cnew 解决方案
https://qeesung.github.io/2020/05/31/Raft-%E9%9B%86%E7%BE%A4%E6%88%90%E5%91%98%E5%8F%98%E6%9B%B4.html

领导人选举、日志复制、安全性的讨论都是基于Raft集群成员恒定不变的，然而在很多时候，集群的节点可能需要进行维护，或者是因为需要扩容，那么就难以避免的需要向Raft集群中添加和删除节点。最简单的方式就是停止整个集群，更改集群的静态配置，然后重新启动集群，但是这样就丧失了集群的可用性，往往是不可取的，所以Raft提供了两种在不停机的情况下，动态的更改集群成员的方式：

单节点成员变更：One Server ConfChange
多节点联合共识：Joint Consensus
从Cold迁移到Cnew的过程中，因为各个节点收到最新配置的实际不一样，那么肯能导致在同一任期下多个Leader同时存在。

为了解决上面的问题，在集群成员变更的时候需要作出一些限定。

单节点成员变更
所谓单节点成员变更，就是每次只想集群中添加或移除一个节点。比如说以前集群中存在三个节点，现在需要将集群拓展为五个节点，那么就需要一个一个节点的添加，而不是一次添加两个节点。

这个为什么安全呢？很容易枚举出所有情况，原有集群奇偶数节点情况下，分别添加和删除一个节点。在下图中可以看出，如果每次只增加和删除一个节点，那么Cold的Majority和Cnew的Majority之间一定存在交集，也就说是在同一个Term中，Cold和Cnew中交集的那一个节点只会进行一次投票，要么投票给Cold，要么投票给Cnew，这样就避免了同一Term下出现两个Leader。

变更的流程如下：

向Leader提交一个成员变更请求，请求的内容为服务节点的是添加还是移除，以及服务节点的地址信息
Leader在收到请求以后，回向日志中追加一条ConfChange的日志，其中包含了Cnew，后续这些日志会随着AppendEntries的RPC同步所有的Follower节点中
当ConfChange的日志被添加到日志中是立即生效（注意：不是等到提交以后才生效）
当ConfChange的日志被复制到Cnew的Majority服务器上时，那么就可以对日志进行提交了
以上就是整个单节点的变更流程，在日志被提交以后，那么就可以：

马上响应客户端，变更已经完成
如果变更过程中移除了服务器，那么服务器可以关机了
可以开始下一轮的成员变更了，注意在上一次变更没有结束之前，是不允许开始下一次变更的
可用性
可用性问题
在我们向集群添加或者删除一个节点以后，可能会导致服务的不可用，比如向一个有三个节点的集群中添加一个干净的，没有任何日志的新节点，在添加节点以后，原集群中的一个Follower宕机了，那么此时集群中还有三个节点可用，满足Majority，但是因为其中新加入的节点是干净的，没有任何日志的节点，需要花时间追赶最新的日志，所以在新节点追赶日志期间，整个服务是不可用的。

在接下来的子章节中，我们将会讨论三个服务的可用性问题：

追赶新的服务器
移除当前的Leader
中断服务器
追赶新的服务器
在添加服务器以后，如果新的服务器需要花很长时间来追赶日志，那么这段时间内服务不可用。

新加入集群中的节点可能并不是因为需要追赶大量的日志而不可用，也有可能是因为网络不通，或者是网速太慢，导致需要花很长的时间追赶日志。

在Raft中提供了两种解决方案：

在集群中加入新的角色Leaner，Leaner只对集群的日志进行复制，并不参加投票和提交决定，在需要添加新节点的情况下，添加Leaner即可。
加入一个新的Phase，这个阶段会在固定的Rounds（比如10）内尝试追赶日志，最后一轮追赶日志的时间如果小于ElectionTimeout, 那么说明追赶上了，否则就抛出异常
下面我们就详细讨论一下第二种方案。

在固定Rounds内追赶日志
如果需要添加的新的节点在很短时间内可以追赶上最新的日志，那么就可以将该节点添加到集群中。那要怎么判断这个新的节点是否可以很快时间内追赶上最新的日志呢？

Raft提供了一种方法，在配置变更之前引入一个新的阶段，这个阶段会分为多个Rounds（比如10）向Leader同步日志，如果新节点能够正常的同步日志，那么每一轮的日志同步时间都将缩短，如果在最后一轮Round同步日志消耗的时间小于ElectionTimeout，那么说明新节点的日志和Leader的日志已经足够接近，可以将新节点加入到集群中。但是如果最后一轮的Round的日志同步时间大于ElectionTimeout，就应该立即终止成员变更

https://segmentfault.com/a/1190000022796386

领导人选举
https://qeesung.github.io/2020/04/14/Raft-%E7%AE%97%E6%B3%95%E4%B9%8B%E9%A2%86%E5%AF%BC%E4%BA%BA%E9%80%89%E4%B8%BE.html

Raft中的节点有三种状态：

领导人状态：Leader
跟随者状态：Follower
候选人状态：Candidate
每一个节点都是一个状态机，Raft会根据当前的心跳，任期等状态来进行状态的迁移转化

首先，在Raft节点启动的时候，所有任务都是Follower状态， 因为此时没有Leader，所有Follower都在固定的超时时间内都收不到来自Leader的心跳，从而变成了Candidate状态，开始选举Leader

当节点处于Candidate状态的时候，会并发的向所有的节点发出请求投票请求RequestVote（后面章节会向详细介绍），在Candidate状态下，节点可能会发生三种状态的迁移变化：

开始下一轮新的选举：发出的投票请求在固定时间内没有收到其他节点的响应，或者是收到响应（或者同意投票）的节点数量没有达到 N/2+1，那么选取超时，进入下一轮选举
选举成功，成为新的Leader：如果选举过程中收到大于N/2+1数量的节点的投票，那么选举成功，当前的节点成为新的Leader
成为Follower：如果选举过程中收到来及其他节点的Leader心跳，或者是请求投票响应的Term大于当前的节点Term，那么说明有新任期的Leader
如果节点选举成功，成为了Leader，那么Leader将会在固定周期内发送心跳到所有的节点，但是如果心跳请求收到的响应的Term大于当前节点的Term，那么当前节点的就会成为Follower。比如Leader节点的网络不稳定，掉线了一段时间，网络恢复的时候，肯定有其他节点被选为了新的Leader，但是当前节点在掉线的时候并没有发现其他节点选为Leader，仍然发送心跳给其他节点，其他节点就会把当前的新的Term响应给已经过时的Leader，从而转变成Follower

https://zhuanlan.zhihu.com/p/29130892?from_voters_page=true

https://blog.csdn.net/chicm/article/details/41794475

https://www.cnblogs.com/cbkj-xd/p/12150282.html

https://www.cnblogs.com/hzmark/p/raft.html

日志复制
https://qeesung.github.io/2020/04/19/Raft-%E7%AE%97%E6%B3%95%E4%B9%8B%E6%97%A5%E5%BF%97%E5%A4%8D%E5%88%B6.html

领导人必须从客户端接收日志然后复制到集群中的其他节点，并且强制要求其他节点的日志保持和自己相同。

复制状态机通常都是基于复制日志实现的，每一个服务器存储一个包含一系列指令的日志，并且按照日志的顺序进行执行。

客户端请求服务器，请求的信息就是一系列的指明，比如PUT KEY VALUE
服务器在收到请求以后，将操作指令同步到所有的服务器中
服务器收到同步的指令以后，就将指令应用到状态机中
最后响应客户端操作成功

安全性
https://qeesung.github.io/2020/04/25/Raft-%E7%AE%97%E6%B3%95%E4%B9%8B%E5%AE%89%E5%85%A8%E6%80%A7.html

必须保证候选人的日志必自己的日志新
我们在领导选举这一文中知道，不是任何节点都可以成为领导人的，被选举出来的领导人必须要包含所有已经提交的日志，否则将会无法保证状态机的一致性。

换句话说，在其他服务器节点给候选人投票时，需要对候选人的“资格”做一些校验，这里的“资格”就是必须保证候选人的日志必须必自己“新”，即当前的任期和候选人的任期相同，且候选人的日志长度比当前的日志长度 或者 候选人的任期比比当前节点的任期高。

提交之前任期内的日志
领导人只能提交当前任期的日志
有这样一种情况，如果领导人在将日志复制到大多数(N/2+1)的服务器以后，还没有来的机提交之前就奔溃了，经过了一系列的奔溃重启，原先奔溃的领导人又被重新选举为新任期的新领导人，如果此时新领导人将之前尚未提交的老任期的日志进行了提交，那么将会是非常危险的，因为可能在日志提交以后，其他节点再次被选举为领导人，然后将当前的已经提交的日志覆盖

客户端交互
包括客户端如何发现领导人和 Raft 是如何支持线性化语义的
Raft 中的客户端发送所有请求给领导人。当客户端启动的时候，他会随机挑选一个服务器进行通信。如果客户端第一次挑选的服务器不是领导人，那么那个服务器会拒绝客户端的请求并且提供他最近接收到的领导人的信息（附加条目请求包含了领导人的网络地址）。如果领导人已经崩溃了，那么客户端的请求就会超时；客户端之后会再次重试随机挑选服务器的过程。

我们 Raft 的目标是要实现线性化语义（每一次操作立即执行，只执行一次，在他调用和收到回复之间）。但是，如上述，Raft 是可以执行同一条命令多次的：例如，如果领导人在提交了这条日志之后，但是在响应客户端之前崩溃了，那么客户端会和新的领导人重试这条指令，导致这条命令就被再次执行了。解决方案就是客户端对于每一条指令都赋予一个唯一的序列号。然后，状态机跟踪每条指令最新的序列号和相应的响应。如果接收到一条指令，它的序列号已经被执行了，那么就立即返回结果，而不重新执行指令。

https://github.com/maemual/raft-zh_cn/blob/master/raft-zh_cn.md#7-%E6%97%A5%E5%BF%97%E5%8E%8B%E7%BC%A9

理解算法时候的注意点：

1.在leader出问题之前，可以保证大多数的server其term是相等的

2.在leader出问题后，leader如果还是leader，则其term不会变。剩余的server在选举leader的时候，大多数-1(减去leader的那台)的term是和leader挂的时候一样的，所以新选出的leader如果要获取大多数的vote，则其term必然大于老leader出问题的时候的term，所以之后如果老的leader活过来了那么也没关系，因为其小的term此时已经不能让其成为leader了。

3.某个一leader真正成为leader的时候，其只有唯一的term。因此一个term只可能有一个leader。也就是说如果同一时间存在两个term，那么就可能存在两个leader，但是其中的一个leader永远不可能成功的commit。另外，真正活着的leader是最大的term的那个。

4.当一个新的leader产生后，其会的将每个follower的next index设置为其自己next index，然后发送心跳包给各个follower。如果follower发现这两个index不一样，则拒绝。leader如果发现follower拒绝了，则发送其next index的前一个index作为next index，直到follower接受。这样的话要保证两个事情：

a.如果term和index一样，那么内容一样

b.如果term和index一样，那么之前的日志内容一样

对于a，只要leader是唯一的，那么就能保证(因为一个唯一的leader对应唯一的term，同时其自身可以保证index的唯一)。对于b，每次发送AppendEntries的时候提供前一个日志的term和id，follower保证其和当前的term、index一致才接受，通过数学归纳可以知道这是可以保证b的。

在a、b的前提下，如果leader落后太多，那么其可能会清理follower上已经commit的日志。因此还需要额外的条件：在选举leader的时候，一个candidate如果其自己的term、id比另一个candidate发来的请求要新，那么就拒绝。

5.在leader宕了的情况下，集群里至少有大多数-1的主机是拥有所有commit日志的。

6.对于figure 8的问题，要注意的是对于c图，term为4的leader是不会去commit老的term为2的日志的，对于index为2的日志，一种情况是和d一样被overwrite了(此时term 2的日志从来就没有被commit过)，另一个情况是和e一样，由S1在Log Matching Property的前提下被commit(收到term 4的AppendEntries的时候，发现S1已经提交到了term 4的日志，所以其follower也提交到这一步)。这里的关键在于，commit指的是重做事物日志，当leader广播的日志内容到了大多数服务器的时候，这些服务器(包括leader自己)都可能只是有这个日志，但是没有commit过。老的日志如果要被commit，前提是follower收到AppendEntries的时候，其包含的leader的最新提交term+index大于这个老的日志的term+index，此时才会被commit。

7.follower收到candidate的请求，且candidate的term大于follower的term的时候，此时follower会立刻认新的leader。

理解集群配置替换时候的注意点：

1.在集群配置变化的时候(主要是添加和减少主机)，要避免的是新老两种配置同时生效(如果存在这种情况，按照figure 10可以看到可能存在同一个term中有两个leader的情况)，换句话说就是要保证leader挂了的时候不会选出两个leader。为了解决这种问题，raft中采用配置同样依靠leader广播，且增加一种old-new的配置来解决这个问题。具体操作和原理如下(新加入的主机启动的时候对于集群的其他服务器信息一点配置都没有，因此其就是在等)：

a.leader收到一个新的集群配置

b.leader广播一个old-new配置信息，这个信息被commit的前提是新集群和老集群中的多数follower都收到了这个信息

c.如果此时leader挂了，且b中的信息还没有被commit，此时集群中只有两种新的配置，一种是Cold，一种是Cold-new。Cold能正常commit或选举的前提是老集群中大多数服务器ok，Cold-new能正常commit或选举的前提是老集群中其大部分服务器ok，且新集群中其大部分服务器ok。如果说Cold-new中的某个服务器要成为leader，根据前提条件其需要老集群中的大部分服务器投票给他，这就保证了老集群中处于Cold的大部分服务器不会成为leader。如果老集群中的一个Cold服务器想成为leader，则Cold-new就没法投票成功(因为其得到不老集群中的多数投票)。当Cold中的一个服务器成为leader后，其再次发起投票即可(这次投票会的将得到上一轮Cold-new的日志overwrite掉)。

如果leader挂了的时候b中的信息已经被commit了，那么新的leader肯定是Cold-new的，这样就比较简单了。

d.当Cold-new已经被commit后，此时的leader就会发起包含新配置的Cnew信息。这个其实就是上面过程的翻转(Cold变成Cnew)，成功的前提是老集群中的大部分和新集群的大部分都收到了Cnew消息。

2.总的来说，集群配置替换由于Cold-new的引入，保证了同一时刻Cold和Cnew不可能同时生效(因为Cold-new其实潜在要求了只有Cnew生效，Cold不生效。而c中另一种情况就是Cold，因此Cnew和Cold不能同时生效。)，当Cnew和Cold不同时生效的时候，可能会处于中间的Cold-new或Cold或Cnew状态，其中处于Cold或Cold-new的时候，按照规定步骤继续向着Cnew前进即可。

3.在上面第一步的c中，如果Cold成了leader，其需要发起一次Cnew-old的广播，否则可能会由于收到新集群主机的选举信息而变成follower，并再次发起选举

4.Cold-new的比较简单的理解是，Ca-b要求a中的大多数、b中的大多数都投赞成票才算成功

理解快照时候的注意点：

1.快照最简单的理解就是按照figure 12的那样，把commit的当前内容及一些基本信息记录下。

2.在follower新加入集群的时候，由于其什么日志都没有，因此leader获取到期next index是一个已经由于快照而删除了的值。此时leader既要发送快照给这个follower。

https://www.jianshu.com/p/866ede94e9ac
http://thesecretlivesofdata.com/raft/

https://github.com/maemual/raft-zh_cn/blob/master/raft-zh_cn.md

https://www.cnblogs.com/aibabel/p/10973585.html

https://zhuanlan.zhihu.com/p/32052223

https://www.jianshu.com/p/4711c4c32aab?tdsourcetag=s_pcqq_aiomsg

https://www.cnblogs.com/WithLin/p/9947631.html

通过 raft 的 leader lease 来解决集群脑裂时的 stale read 问题

问题： 当 raft group 发生脑裂的情况下，老的 raft leader 可能在一段时间内并不知道新的 leader 已经被选举出来，这时候客户端在老的 leader 上可能会读取出陈旧的数据（stale read）。 比如，我们假想一个拥有 5 个节点的 raft group:

其中 Node 5 是当前的 raft leader，当出现网络分区时，在 Node 5 的 raft lease 任期还没结束的一段时间内，Node 5 仍然认为自己是当前 term 的 leader，但是此时，另外一边分区已经在新的 term 中选出了新的 leader。

如果此时，客户端在新的 leader 上更新了某个值 x，此时是可以更新成功的（因为还是可以复制到多数派）。但是在分区的另一端，此时一个客户端去读取 x 的值，Node 5 还会返回老的值，这样就发生了 stale read。

解决方案

引入一个新的概念, region leader。region leader 是一个逻辑上的概念, 任意时刻对于某一个 region 来说, 一定只拥有一个 region leader, 每个 region leader 在任期之内尝试每隔 t 时间间隔, 在 raft group 内部更新一下 region leader 的 lease. 所有的读写请求都必须通过 region leader 完成， 但是值得注意的是， region leader 和 raft leader 可能不是一个节点，当 region leader 和 raft leader 不重合的时候，region leader 会将请求转发给当前的 raft leader，当网络出现分区时，会出现以下几种情况：

region leader 落在多数派，老 raft leader 在多数派这边
region leader 落在多数派，老 raft leader 在少数派这边
region leader 落在少数派，老 raft leader 在多数派这边
region leader 落在少数派，老 raft leader 在少数派这边
用开篇的例子来分情况讨论：

对于第一种情况，region leader 的 lease 不会过期，因为 region leader 的心跳仍然能更新到多数派的节点上，老的 raft leader 仍然能同步到大多数节点上，少数派这边也不会选举出新的 leader， 这种情况下不会出现 stale read。

第二种情况，就是开篇提到会出现 stale read 的典型情况，老的 raft leader 被分到了少数派这边，多数派这边选举出了新的 raft leader ，如果此时的 region leader 在多数派这边。

因为所有的读写请求都会找到 region leader 进行，即使在原来没有出现网络分区的情况下，客户端的请求也都是要走 node 1 ，经由 node 1 转发给 node 5，客户端不会直接访问 node 5，所以此时即使网络出现分区，新 leader 也正好在多数派这边，读写直接就打到 node 1 上，皆大欢喜，没有 stale read。

第三种情况，region leader 落在少数派这边，老 raft leader 在多数派这边，这种情况客户端的请求找到 region leader，他发现的无法联系到 leader（因为在少数派这边没有办法选举出新的 leader），请求会失败，直到本次 region leader 的 lease 过期，同时新的 region leader 会在多数派那边产生（因为新的 region leader 需要尝试走一遍 raft 流程）。因为老的 region leader 没办法成功的写入，所以也不会出现 stale read。但是付出的代价是在 region leader lease 期间的系统的可用性。

第四种情况和第三种情况类似，多数派这边会产生新的 raft leader 和 region leader。

总体来说，这种方法牺牲了一定的可用性（在脑裂时部分客户端的可用性）换取了一致性的保证。

https://segmentfault.com/a/1190000022796386
https://zhuanlan.zhihu.com/p/66047414

https://www.jianshu.com/p/b03569745e72

https://www.cnblogs.com/twoheads/p/12804049.html
https://edu.csdn.net/course/play/25693
https://www.bilibili.com/video/BV1RJ411D7dQ/?spm_id_from=trigger_reload

https://github.com/apache/incubator-brpc

https://my.oschina.net/pingpangkuangmo/blog/782702

https://www.liankexing.com/notetwo/14437

https://blog.csdn.net/chenhaifeng2016/article/details/54426397

https://github.com/ongardie/raftscope
https://raft.github.io/raft.pdf
https://blog.csdn.net/codehole_/article/details/100892357
https://blog.csdn.net/qq_40994017/article/details/90749940

https://blog.csdn.net/feeltouch/article/details/90420485

cnblogs.com/cbkj-xd/p/12150282.html
消息重复
客户端消息处理最困难的一点在于消息可能会重复。比如客户端向Leader发送了一条指令，Leader收到了这条指令并执行了，但是连接在响应返回之前断开了。客户端没有收到回复，所以接下来会重连然后重新发送这条指令。这时服务器就必须想办法去重。

消息去重
去重意味着客户端的消息必须有编号，服务器会记录这些编号，以便重复消息过来的时候，可以判断是否已经处理过了。 如果已经处理过了，会缓存响应内容。这时重复消息过来了，可以直接将响应内容返回给客户端而不需要进行重复处理。如果消息正在处理中，那么等消息处理结束，直接一块响应即可。

回话
服务器会为每个客户端连接维持一个回话session，记录客户端的交互状态。每个客户端回话会被赋予一个唯一ID。当连接不小心断开，通过重连还可以挂接到之前的session对象，因为客户端会将回话的ID记录在内存中。如果断开的时间较久，服务器的回话会过期，客户端带着回话ID进行再重连交互时，服务器会返回回话过期异常。这时客户端需要再注册一个新回话，并抛弃之前回话中的所有消息，重新进行交互。

回话期间的消息采用序列号进行唯一标识，序列号相同的消息是重复的消息，每生成一个新的消息，序列号递增。

会话过期
回话不可能永远持续下去，考虑到内存的上限，回话是需要过期的。回话的过期也必须通过日志协商，否则系统的一致性就很难满足。比如在一个特定的时间点，某个客户端的回话对象在一个节点上是活的，在另一个节点上是过期的。没有过期的回话对象内部还存储了最近客户端的指令ID。这个时候需要将已经提交的日志apply到状态机。这个apply的过程要检查指令的重复与否。这个重复检查的结果在两个节点上就可能是不一样的，紧接着会导致两节点的状态机数据出现不一致。

回话的过期一般有两种策略。第一种是限定session的数量，通过LRU算法来淘汰陈旧的session。另外一种是通过协商一致的时间源来过期。不同的节点需要在日志的时间上达成一致，这样才可以在apply相同的日志时有相同的时间，回话过期也就会有相同的结果。在时间上达成一致一般是以Leader在日志里放入自身的当前时间戳做到的，其它节点就是通过这个时间戳来作为时间源来决定回话的过期与否。

标准raft协议里没有提到回话的主动过期，比如客户端主动退出，此时应该可以允许客户端在连接断开之前发送一个RemoveClient的指令，注销当前的回话，及时给服务器腾出空间来。

https://www.pianshen.com/article/54701071957/

http://www.voidcn.com/article/p-reztzpsz-kd.html
https://blog.csdn.net/xiongwenwu/article/details/79981804

https://blog.csdn.net/qihoo_tech/article/details/104787823

https://blog.csdn.net/qihoo_tech/article/details/105002303