状态机，英文表示是：State Machine ，不是指一台实际机器，而是指一个数学模型，仅仅是一组约束和规范，是不同状态进行相互转换的约束和规范。状态机的数学模型包括四大部分：状态，事件，动作，转换。其中，事件来源于外界，而状态、动作和转换则与自身相关。例如，对于一扇门而言，它的状态有open和close两种。当人进门的时候，推门就是外界作用给门的一个事件，而此时门的状态从close转换为open。状态机的数学模型非常简单，理解起来毫不费力，但是落地到实际的应用却很少。原因很简单：反人性。一件十分简单的事情，仅仅通过if-else就可以搞定的事情，非要套上“状态机”这个思维枷锁，注定是失败的。不过，在分布式场景中，状态机得到了广泛的应用。但是，此时出现了倍感滑稽的一幕：此状态机非彼状态机，上文提到的四个部分都已经被扔掉了。在分布式场景中，当某个节点接受到操作指令之后，没有立即执行，而是先暂存起来，等集群大多数节点都接受到同样操作命令之后，才会执行命令。只有被执行的命令，才会作用于状态机。此时，状态机本质就变成了命令日志而已，早已经没有数学模型之说。在分布式场景下的状态机设计与实现是这个样子的：public class StateMachine<T> { //存放外界下达的命令操作 public List<Command<T>> commands = new ArrayList<>(); //执行命令操作，修改状态机的状态 protected void apply(Command<T> command){} //保存当前状态机的状态 public void saveState(DataOutputStream out){} //从文件中状态机的状态 public void loadState(DataInputStream in){} }个人认为，学习状态机的理论并没有价值，因为它的内容十分简单，只有动手实战才能理解的更透彻，我通过实现一个分布式消息中间件从而加深了对状态机的理解，更多介绍请关注：http://www.mybatis.cn/archives/2283.html
1、Raft 日志的基本内容Raft日志包含三块基本内容：（1）索引号：整数，用于标识日志所在的位置（2）任期号：创建该日志时Leader所处的当前任期号（3）可以被复制状态机执行的命令日志由有序编号（log index）的日志条目组成。每个日志条目包含：日志被创建时的任期号（term）和用于状态机执行的命令。如下图所示， 上图显示，共有 8 条日志，提交了 7 条。提交的日志都将通过状态机持久化到磁盘中，防止宕机。2、Raft 日志复制的过程Leader选出后，就开始接收客户端的请求。Leader把请求作为日志条目（Log entries）加入到它的日志中，然后并行地向Follower发起 AppendEntries RPC 复制日志条目请求。当这条日志被复制到大多数服务器上，Leader将这条日志应用到它的状态机并向客户端返回执行结果。如果Follower宕机或者运行缓慢或者丢包，Leader会不断的重试，直到所有的Follower最终都复制了所有的日志条目。 3、Raft 日志的一致性检查如上所述，Follower在接收到AppendEntries RPC消息后则会返回复制成功的回复。实际上在接收到消息后会首先进行日志的一致性检查(正常情况下Leader与Follower的日志会保持一致，所以一致性检查不会失败)，一致性检查内容如下：在Leader创建AppendEntries RPC消息时，消息中将会包含当前日志之前日志条目的任期号与索引号。Follower在接受到AppendEntries RPC消息后，将会检查之前日志的任期号与索引号是否匹配到。如果匹配则说明和Leader之前的日志是保持一致的，否则，会拒绝AppendEntries RPC消息。4、Raft 日志不一致的解决方案4.1、日志不一致的三种情况网络不可能一直处于正常情况，因为Leader或者某个Follower有可能会崩溃，从而导致日志不能一直保持一致，因此存在以下三种情况：（1）Follower缺失当前Leader上存在的日志条目。（2）Follower存在当前Leader不存在的日志条目。比如，旧的Leader仅仅将AppendEntries RPC消息发送到一部分Follower就崩溃掉，然后新当选Leader的服务器恰好是没有收到该AppendEntries RPC消息的服务器。（3）Follower即缺失当前Leader上存在的日志条目，也存在当前Leader不存在的日志条目。为了更好的说明这三种情况，请看下面的图示。 备注：（1）图中最上方是日志的索引号(1-12)，每个方块代表一条日志信息，方块内数字代表该日志所处的任期号。（2）图中当前Leader(图中最上方一行日志代表当前Leader日志)处于任期号为8的时刻。下面，以此图分析说明以上三种情况存在的原因：（1）Follower a、Follower b满足以上说明的第一种情况：Follower崩溃没有接收到Leader发送的AppendEntries RPC消息。（2）Follower c在任期为6的时刻，Follower d在任期为7的时刻为Leader，但没有完全完成日志的发送便崩溃了，满足以上说明的第二种情况：Follower存在当前Leader不存在的日志条目。（3）Follower e在任期为4的时刻，Follower f在任期为2、3的时刻为Leader，但没有完全完成日志的发送便崩溃了，同时在其他服务器当选Leader时刻也没有接收到新的Leader发送的AppendEntries RPC消息，满足第三种情况：Follower即缺失当前Leader上存在的日志条目，也存在当前Leader不存在的日志条目。备注： 如上文所示，根据日志的任期数目来判断节点是否为Leader，再次印证了任期的关键作用。4.2、日志不一致的解决方案Leader通过强迫Follower的日志重复自己的日志来处理不一致之处，这意味着Follower日志中的冲突日志将被Leader日志中的条目覆盖。这个过程如下所示：首先，Leader找到与Follower最开始日志发生冲突的位置，然后删除掉Follower上所有与Leader发生冲突的日志，最后将自己的日志发送给Follower以解决冲突。需要注意的是：Leader不会删除或覆盖自己本地的日志条目。当发生日志冲突时，Follower将会拒绝由Leader发送的AppendEntries RPC消息，并返回一个响应消息告知Leader日志发生了冲突。Leader为每一个Follower维护一个nextIndex值。该值用于确定需要发送给该Follower的下一条日志的位置索引。该值在当前服务器成功当选Leader后会重置为本地日志的最后一条索引号+1。当Leader了解到日志发生冲突之后，便递减nextIndex值，并重新发送AppendEntries RPC到该Follower，不断重复这个过程，一直到Follower接受该消息。一旦Follower接受了AppendEntries RPC消息，Leader则根据nextIndex值可以确定发生冲突的位置，从而强迫Follower的日志重复自己的日志以解决冲突问题。 情况a：如上图，服务器S1在任期为2的时刻仅将日志<index:2,term:2>发送到了服务器S2便崩溃掉。情况b：服务器S5在任期为3的时刻当选Leader(S5的计时器率先超时，递增任期号为3，高于服务器S3和S4，因此可以当选Leader)，但没来得及发送日志便崩溃掉。情况c：服务器S1在任期为4的时刻再次当选Leader(S1重启时，任期仍然为2，收到新的Leader S5发送的心跳信息后更新任期为3，而在Leader S5崩溃后，服务器S1为第一个计时器超时的，因此发起投票，任期更新为4，大于网络中其他服务器任期，成功当选Leader)，同时将日志<index:2,term:2>发送到了服务器S2和S3，但还没有通知服务器对日志进行提交便崩溃掉。情况d：情况(a->d)如果在任期为2时服务器S1作为Leader崩溃掉，S5在任期为3的时刻当选Leader，由于日志<index:2,term:2>还没有被复制到大部分服务器上，并没有被提交，所以S5可以通过自己的日志<index:2,term:3>覆盖掉日志<index:2,term:2>。情况e：情况(a->e)如果在任期为2时服务器S1作为Leader，并将<index:2,term:2>发送到S2和S3，成功复制到大多数成员服务器上。S1成功提交了该日志，那么即便S1崩溃掉，S5也无法成功当选Leader，因为S5不具备网络中最新的已被提交的日志条目，S5只有term为1的日志。原文链接： http://www.mybatis.cn/raft/1965.html
备注：本文内容节选自《全面解读Raft共识算法》，想了解更全面的Raft算法解读，请移步链接即可。在Raft论文中，成员变更属于难点，但这一部分相比于论文其他部分，确实讲解最不详细，让人读完之后很迷惑。1、什么是成员变更？成员变更指的是系统成员变化，即服务器节点的上下线，这和由于宕机故障导致的上下线是不同的。宕机或者重启导致的上下线，是不会影响系统的注册的成员数量的，也就不会影响到一致性判断所依据的“多数派”的生成，众所周知，“多数派”是所有一致性的基础。成员变更时，会修改注册的成员数量，比如在实际应用中，为了提高安全等级，就很可能出现需要把备机数量由三台扩充到五台，在这种情况下，就发生了成员变更。另外，还有一个十分需要注意的地方：成员变更意味着大家都还活着，并不像宕机那样，立即死亡，无法再做“交接工作”。被变更的成员是需要完成“交接工作”的。所谓的“交接工作”，就是下文中提到的“做决策”。2、直接变更存在的问题在成员变更时，因为无法做到在同一个时刻使所有的节点从旧配置转换到新配置，那么直接从就配置向新配置切换就可能存在一个节点同时满足新旧配置的“超过半数”原则。如下图，原集群由Server1、Server2、Server3，现在对集群做变更，增加Server4、Server5。如果采用直接从旧配置到新配置的切换，那么有一段时间存在两个不想交的“超过半数的集群”。 上图，中在中间位置Server1可以通过自身和Server2的选票成为Leader（满足旧配置下收到大多数选票的原则）；Server3可以通过自身和Server4、Server5的选票成为Leader（满足新配置线，即集群有5个节点的情况下的收到大多数选票的原则）；此时整个集群可能在同一任期中出现了两个Leader，这和协议是违背的。3、Raft的成员变更实现方案：分阶段变更Raft提出了通过一个中间过渡阶段，即联合共识（joint consensus），逐步把数据写入的新的集群中。其具体做法是2阶段提交式的：第一阶段：Leader收到C-old到C-new的配置变更请求时，创建C-old-new的日志并开始复制给其他节点，此日志和普通日志复制没有区别。此时做决策的仍然是C-old集群。第二阶段：当只有C-old-new复制到大多数节点后，Leader以这个配置做决定，这个时候处于一个共同决定的过程，因为此时做决策的是C-old-new集群。由于两阶段变更不存在一个阶段C-old和C-new可以同时根据自己的配置做出决定，所以不会出现上文描述的情况。备注：虽然自己是Leader，但是做决策的可不是Leader，它要根据多数派的原则进行拍板定方案，所以归根结底，做决策的还是集群中的其他Follower成员。4、Raft论文解读 论文里面的这张图片看起来让人头大，个人感觉有点凌乱。虚线表示已创建但尚未提交的配置项，实线表示已经提交的配置项。最难以理解的地方在于最上面的“豁口”，其表示中间过渡阶段，即联合共识（joint consensus），其开始于C-old-new复制到大多数节点后，而结束于C-new提交之后，因为C-old-new与C-new的配置内容虽不相同但是一致，两者是等价的，所以可以视为C-new能够单独做决定。当C-new被复制到大多数节点的时候，如果Leader不在C-new之内，则自己做下线处理，C-new集群开始进行新的选主操作。
Raft算法中，有三种很重要的超时设置：选举超时、最小选举超时、心跳超时。下文给大家详细的介绍一下。（1）选举超时。就是新一轮选举开始时，每个节点随机思考要不要做领导者的时间，这个时间一般100-到200ms，非常短。假设集群由3个节点组成，为了防止3个节点同时发起投票，Raft会给每个节点分配一个随机的选举超时时间（Election Timeout）。在这个时间内，节点必须等待，不能成为Candidate状态。现在假设节点a等待168ms，节点b等待210ms，节点c等待200ms。由于a的等待时间最短，所以它会最先成为Candidate，并向另外两个节点发起投票请求，希望它们能选举自己为Leader。另外两个节点收到请求后，假设将它们的投票返回给Candidate状态节点a，节点a由于得到了大多数节点的投票，就会从Candidate变为Leader。（2）最小选举超时。在分布式系统中，有时候需要对集群中的成员数量进行更新的操作。对于被下线的服务器而言，如果它们没有及时关闭，那么它们将不会接收到心跳信息和日志信息，从而不断发生超时，最后导致任期不断增加(高于集群中所有成员的任期)，然后不断向集群中发送请求投票消息。集群中的Leader将变为Follower，集群中将不断开始新的选举，从而扰乱集群的正常运行。解决方案：Raft引入了一个最小选举超时时间，意思是如果集群中存在Leader时，并且接收到心跳信息之后在最小选举超时时间内接受到请求投票消息，那么将会忽略掉该投票消息。（3）心跳超时。心跳是Leader发送心跳给Follower的时间。这个时间一旦超时，Follower会觉得Leader挂了，这样会开始新的选举周期。
在Raft共识算法中，不存在分阶段提交，所以不属于二阶段提交。在Raft共识算法中，Leader选出后，就开始接收客户端的请求。Leader把请求作为日志条目（Log entries）加入到它的日志中，然后并行地向其他服务器发起 AppendEntries RPC 复制日志条目。当这条日志被复制到大多数服务器上，Leader将这条日志应用到它的状态机并向客户端返回执行结果。
为了解决分布式问题，为了使系统尽量能够达到 CAP，涌现了很多经典的算法和协议，最著名的就是二阶段提交协议，简称 2PC。顾名思义，二阶段提交就是将事务的提交过程分成了两个阶段来进行处理。第一阶段：准备阶段（投票阶段）和第二阶段：提交阶段（执行阶段）。流程如下： 二阶段提交的优点优点：原理简单，实现方便。二阶段提交的缺点缺点：同步阻塞，单点问题，数据不一致，过于保守（1）同步阻塞。在二阶段提交的过程中，所有的节点都在等待其他节点的响应，无法进行其他操作。这种同步阻塞极大的限制了分布式系统的性能。（2）单点问题。协调者在整个二阶段提交过程中很重要，如果协调者在提交阶段出现问题，那么整个流程将无法运转，更重要的是：其他参与者将会处于一直锁定事务资源的状态中，而无法继续完成事务操作。（3）数据不一致。假设当协调者向所有的参与者发送 commit请求之后，发生了局部网络异常或者是协调者在尚未发送完所有commit请求之前自身发生了崩溃，导致最终只有部分参与者收到了 commit请求，这将导致严重的数据不一致问题。（4）过于保守。如果在二阶段提交的提交询问阶段中，参与者出现故障而导致协调者始终无法获取到所有参与者的响应信息的化，这时协调者只能依靠其自身的超时机制来判断是否需要中断事务，显然，这种策略过于保守。换句话说，二阶段提交协议没有设计较为完善的容错机制，任意一个节点是失败都会导致整个事务的失败。
1、CAP理论是什么？CAP定理，又称CAP原则，指的是在一个分布式系统中，一致性（Consistency）、可用性（Availability）、分区容错性（Partition tolerance）。CAP定理指的是，这三个要素最多只能同时实现两点，不可能三者兼顾。 2、CAP理论为什么不能同时满足？2000年的时候，加州大学伯克利分校的光头教授Eric Brewer提出了CAP猜想：CAP永远不可能同时满足，提高其中任意两者的同时，必然要牺牲第三者。这个定理告诉大家，不要再浪费时间去研究如何兼顾了，因为这根本就是不可能的，只能根据具体应用，来决定如何在三者之间进行取舍。后来，CAP猜想由麻省理工学院的两位科学家证明。CAP猜想的证明相对比较简单：采用反证法，如果三者可同时满足，则因为允许P的存在，一定存在节点之间的丢包，如此则不能保证C，证明简洁而严谨。从此，CAP理论正式在学术上成为了分布式计算领域的公认定理，并深深的影响了分布式计算的发展。3、CAP理论后记在CAP理论提出十二年之后，Eric Brewer教授又出来辟谣：“三选二”的公式一直存在着误导性，它会过分简单化各性质之间的相互关系。这三种性质都可以在某种程度上进行衡量，并不是非黑即白的有或无。可用性显然是在0%到100%之间连续变化的，一致性分很多级别，连分区也可以细分为不同含义，如系统内的不同部分对于是否存在分区可以有不一样的认知。所以，一致性和可用性并不是水火不容，非此即彼的。
2000年的时候，加州大学伯克利分校的光头教授Eric Brewer提出了CAP猜想：CAP永远不可能同时满足，提高其中任意两者的同时，必然要牺牲第三者。这个定理告诉大家，不要再浪费时间去研究如何兼顾了，因为这根本就是不可能的，只能根据具体应用，来决定如何在三者之间进行取舍。 后来，CAP猜想由麻省理工学院的两位科学家证明。CAP猜想的证明相对比较简单：采用反证法，如果三者可同时满足，则因为允许P的存在，一定存在节点之间的丢包，如此则不能保证C，证明简洁而严谨。从此，CAP理论正式在学术上成为了分布式计算领域的公认定理，并深深的影响了分布式计算的发展。但是，在CAP理论提出十二年之后，Eric Brewer教授又出来辟谣：“三选二”的公式一直存在着误导性，它会过分简单化各性质之间的相互关系。这三种性质都可以在某种程度上进行衡量，并不是非黑即白的有或无。可用性显然是在0%到100%之间连续变化的，一致性分很多级别，连分区也可以细分为不同含义，如系统内的不同部分对于是否存在分区可以有不一样的认知。所以，一致性和可用性并不是水火不容，非此即彼的。 《全面解读CAP定理》 第一节：什么是 CAP 定理？ 第二节：什么是分区？什么是分区容错性？ 第三节：为什么只能 3 选 2？ 第四节：真实的CP场景：GitHub事故：断网43秒，瘫痪24小时 第五节：CAP理论的新理解 第一节：什么是 CAP 定理？ 2000 年的时候，Eric Brewer 教授提出了CAP猜想，2年后，被 Seth Gilbert和 Nancy Lynch从理论上证明了猜想的可能性，从此，CAP定理正式在学术上成为了分布式计算领域的公认定理，并深深的影响了分布式计算的发展。CAP定理，又称CAP原则，指的是在一个分布式系统中，一致性（Consistency）、可用性（Availability）、分区容错性（Partition tolerance）。CAP 定理指的是，这三个要素最多只能同时实现两点，不可能三者兼顾。CAP定理的精髓就是要么AP，要么CP，要么AC，但是不存在CAP。因此在进行分布式架构设计时，必须做出取舍。而由于网络硬件肯定会出现延迟丢包等问题，所以分区容错性是我们必须需要实现的。所以我们只能在一致性和可用性之间进行权衡，没有任何分布式系统能同时保证这三点。 选项 描述 C（Consistence） 一致性，指数据在多个副本之间能够保持一致的特性（严格的一致性）。 A（Availability） 可用性，指系统提供的服务必须一直处于可用的状态，每次请求都能获取到正确的响应，但是不保证获取的数据为最新数据。 P（Partition tolerance） 分区容错性，分布式系统在遇到任何网络分区故障的时候，仍然能够对外提供满足一致性和可用性的服务，除非整个网络环境都发生了故障。 第二节：什么是分区？什么是分区容错性？ 在分布式系统中，不同的节点分布在不同的子网络中，由于一些特殊的原因，这些子节点之间出现了网络不通的状态，但他们的内部子网络是正常的。从而导致了整个系统的环境被切分成了若干个孤立的区域，这就是分区。分区容错性，说白了，就是指是否允许出现分区。一旦出现分区，则各个分区之间的数据副本无法达到一致性。 第三节：为什么只能 3 选 2？ 假设有一个系统如下： 整个系统由两个节点配合组成，节点之间通过网络通信，当节点 A 进行更新数据库操作的时候，需要同时更新节点 B 的数据库（满足一致性）。这个系统怎么满足 CAP 呢？C：当节点A更新的时候，节点B也要更新；A：必须保证两个节点都是可用的；P：当节点 A,B 出现了网络分区，必须保证对外可用。可见，三者根本无法同时满足，只要出现了网络分区，一致性就无法满足，因为节点 A 根本连接不上节点 B。如果强行满足一致性，就必须停止服务运行，从而放弃可用性 。所以，最多满足两个条件，并有下面几种情况： 组 合 分析 CA 满足一致性和可用，放弃分区容错。此时已经变成了单机系统，谈不上是分布式系统了。对于分布式系统而言，分区容错性是一个最基本的要求，因为分布式系统中的组件必然需要部署到不通的节点，必然会出现子网络，在分布式系统中，网络问题是必定会出现的异常。因此分布式系统只能在C（一致性）和A（可用性）之间进行权衡。放弃分区容错性，比较简单的方式就是把所有的数据都放在一个分布式节点上。那不就又成为了单机应用了吗？ CP 满足一致性和分区容错，也就是说，要放弃可用。当系统被分区，为了保证一致性，必须放弃可用性，让服务停用。放弃可用性，一旦出现网络故障，受到影响的服务需要再等待一定时间，因为系统处于不可用的状态。 AP 满足可用性和分区容错，当出现分区，同时为了保证可用性，必须让节点继续对外服务，这样必然导致失去一致性。放弃一致性，这里所指的一致性是强一致性，但是确保最终一致性。是很多分布式系统的选择。 第四节：真实的CP场景：GitHub事故：断网43秒，瘫痪24小时 2018年10月31日，GitHub技术负责人Jason Warner的一篇技术深度解析稿成为IT圈爆款。文中，Jason坦诚地对外讲述了10月21日100G光缆设备故障后，Github服务降级的应急过程以及反思总结。从Jason Warner的文章中不难看出，造成断网43秒瘫痪24小时的罪魁祸首是数据库。由于部署在两个数据中心的数据库集群没有实时同步。意外发生时，Github的工程师担心数据丢失，不敢快速将主数据库安全切换到东海岸的备份数据中心。 程序员们在GitHub这篇“忏悔录”下面留言，表达对数据库集群的“哀悼”。但更多IT从业者关心的问题是，如何避免这样的灾难事件降临到自己的公司，自己维护的系统。分布式数据库专家认为，此次Github事件是典型的城市级故障。如果系统采用的是高可用的三地五中心解决方案，就可以自如应对。原来，Github类似银行采用的传统数据库两地三中心模式，即“主库（主机房）+同城热备库（同城热备机房）+异地灾备库（异地灾备机房）”。这种方式下通常只有主机房的服务器能提供写服务。如果主城市出现城市级故障，灾备城市的数据库虽然可以工作，但由于没有同步的最新数据，因此灾备库的数据是有损的。Github表示，为了保证数据完整性，他们不得不牺牲恢复时间。其实，这个问题采用三地五中心方案可以更好的应对。城市故障时，只要活着的两个城市的三个机房两两之间能够通信，就可以正常服务，也不会有任何的数据损失。 第五节：CAP理论的新理解 有读者存在疑问：根据CAP理论，在分布式系统中一致性和可用性只能选一个，那Paxos、Raft等共识算法是如何做到在保证一定的可用性的同时，对外提供强一致性呢？这个疑问的根源在于没有明白CAP理论后期的发展。在CAP理论提出十二年之后，其作者又出来辟谣：“三选二”的公式一直存在着误导性，它会过分简单化各性质之间的相互关系。首先，由于分区很少发生，那么在系统不存在分区的情况下没什么理由牺牲C或A。其次，C与A之间的取舍可以在同一系统内以非常细小的粒度反复发生，而每一次的决策可能因为具体的操作，乃至因为牵涉到特定的数据或用户而有所不同。最后，这三种性质都可以在程度上衡量，并不是非黑即白的有或无。可用性显然是在0%到100%之间连续变化的，一致性分很多级别，连分区也可以细分为不同含义，如系统内的不同部分对于是否存在分区可以有不一样的认知。所以，一致性和可用性并不是水火不容，非此即彼的。
备注1：本系列内容由站长北侠撰写，内容来源于论文以及网上他人精品内容的参考，再此表示感谢！除此以外，站长北侠增加了很多个人的理解和思考，并在必有地方给以醒目提示，方便大家的阅读。好的架构是修改出来的，好的内容也是修改出来的，所以本系列内容不会写完了事，而是会不断地修订，提醒各位读者记得收藏和回访。一个人的理解角度总是有限的，欢迎更多的人提出自己的想法，让我们把这个系列内容构建的更完美一点，从而帮助更多的人。本系列内容的最后更新日期为：2021年6月20日。备注2：Raft是一种共识算法，其源自于论文《In Search of an Understandable Consensus Algorithm》，需要注意两点：（1）Raft属于算法，而非协议（2）共识描述的是算法过程，而一致性描述的多副本的读取结果。共识和一致性是两个不同的概念和术语。很多人存在混用。Raft是一种共识算法，其设计思路非常容易理解，但是它在容错性和性能上相当于Paxos。不同之处在于，Raft把共识难题分解成相对独立的子问题，从而分而治之，最终非常容易被人理解，并便于工程实现。Raft本意是木筏，几根原木捆扎在一起便是木筏，寓意着集群管理的简单和便捷。其logo如下所示： 《全面解读Raft共识算法》 第一节：Raft是什么？ 第二节：Raft算法论文 第三节：Raft算法应用场景 第四节：状态机复制与分布式系统的容错性 第五节：Raft共识算法的核心组件 第六节：Raft算法实现过程 第七节：Raft算法的独有特性 第八节：Raft算法的独有特性 第九节：Raft RPC简介 第十节：Raft日志复制 第十一节：Raft日志不一致的解决方案 第十二节：Raft算法中成员变更过程解析 第一节：Raft是什么？ Raft是一种共识算法，其设计非常容易理解。它在容错性和性能上相当于Paxos。不同之处在于，它被分解成相对独立的子问题，并且清晰地处理了实际系统所需的所有主要部分。Raft的作者希望Raft能够容易理解，并希望人们能够立足于Raft算法开发出比目前更高质量的共识系统。以目前的发展来看，Raft作者的初衷已然实现，在大数据生态圈子，Raft算法得到了广泛的应用。 第二节：Raft算法论文 Raft 算法的官方网站：https://raft.github.io/Raft算法论文：https://raft.github.io/raft.pdf 第三节：Raft算法应用场景 随着互联网时代数据规模的爆发式增长，传统的单机系统在性能和可用性上已经无法胜任，分布式系统具有扩展性强，可用性高，廉价高效等优点，得以广泛应用。分布式系统是指一组独立的计算机，通过网络协同工作的系统，客户看来就如同单台机器在工作。但与单机系统相比，分布式系统在实现上要复杂很多。CAP原则是分布式系统的理论基石。2000 年的时候，Eric Brewer 教授提出了 CAP 猜想，2年后被 Seth Gilbert 和 Nancy Lynch 从理论上证明了猜想的可能性，从此，CAP 理论正式在学术上成为了分布式计算领域的公认定理，并深深的影响了分布式计算的发展。CAP 理论告诉我们，一个分布式系统不可能同时满足一致性（Consistency)，可用性（Availability）和分区容错性（Partition tolerance）这三个基本需求，最多只能同时满足其中的2个。一致性（Consistence）：指数据在多个副本之间能够保持一致的特性（严格的一致性）。可用性（Availability）：指系统提供的服务必须一直处于可用的状态，每次请求都能获取到正确的响应，但是不保证获取的数据为最新数据。分区容错性（Partition tolerance）：分布式系统在遇到任何网络分区故障的时候，仍然能够对外提供满足一致性和可用性的服务，除非整个网络环境都发生了故障。对于分布式系统而言，P显然是必不可少的，那么只能在AP和CP之间权衡：（1）AP系统牺牲了强一致性，这在某些业务场景下（如金融类）是不可接受的。（2）CP系统可以满足强一致性这类需求，但是却牺牲了可用性。例如，传统的主备强同步模式虽然可以保证一致性，但一旦机器故障系统将变得不可用。Paxos和Raft等共识算法的提出，弥补了这一缺陷。它们在保证CP的前提下，只要求大多数节点可以正常互联，系统便可以一直处于可用状态，可用性上显著提高。Paxos的理论性偏强，开发者需要自己处理很多细节，这也是它有很多变种的原因，相对而言Raft更易理解和工程化，一经提出便广受欢迎。有读者存在疑问：根据CAP理论，在分布式系统中一致性和可用性只能选一个，那Paxos、Raft等共识算法是如何做到在保证一定的可用性的同时，对外提供强一致性呢？这个疑问的根源在于没有明白CAP理论后期的发展。在CAP理论提出十二年之后，其作者又出来辟谣：“三选二”的公式一直存在着误导性，它会过分简单化各性质之间的相互关系。首先，由于分区很少发生，那么在系统不存在分区的情况下没什么理由牺牲C或A。其次，C与A之间的取舍可以在同一系统内以非常细小的粒度反复发生，而每一次的决策可能因为具体的操作，乃至因为牵涉到特定的数据或用户而有所不同。最后，这三种性质都可以在程度上衡量，并不是非黑即白的有或无。可用性显然是在0%到100%之间连续变化的，一致性分很多级别，连分区也可以细分为不同含义，如系统内的不同部分对于是否存在分区可以有不一样的认知。所以，一致性和可用性并不是水火不容，非此即彼的。综之，Paxos、Raft等分布式共识算法就是在一致性和可用性之间做到了很好的平衡的见证。 第四节：状态机复制与分布式系统的容错性 1、什么是状态机？“状态机”属于计算机理论方面的专业词汇，其定义是：状态机是有限状态自动机的简称，是现实事物运行规则抽象而成的一个数学模型。“状态机”是个高大上的字眼，与之类似的还有“空间”。关于“空间”理解，我之前专门写过这样一段话：我们知道，内存分为两部分，一部分被用户占用，一部分被操作系统占用，这个道理学过计算机的人都知道。但是，内存这个概念太土了，科学家们聚到一起开会的时候，总不能你一句内存，我一句内存的讨论问题吧，这不是成了电脑维修了。为了显示清高，科学家们随后就想了一个更高大上的字眼：空间。人类的世界就是由空间和时间构成的，而在计算机世界里面，也有了“空间”之说，立马是不是觉得变得高大上了呢。同样道理，一群科学家围在一起，一口一个状态，变来变去，肯定把大家都绕晕了，使用状态机，不仅简单明了，更显得高大上。对于程序员来说，它还是一个抽象的数学模型。抽象在哪里呢？请君往下看：先来解释什么是“状态”（ State ）。现实事物是有不同状态的，例如一个自动门，就有 open 和 closed 两种状态。我们通常所说的状态机是有限状态机，也就是被描述的事物的状态的数量是有限个，例如自动门的状态就是两个 open 和 closed 。状态机，也就是 State Machine ，不是指一台实际机器，而是指一个数学模型。说白了，一般就是指一张状态转换图。例如，根据自动门的运行规则，我们可以抽象出下面这么一个图： 自动门有两个状态，open 和 closed ，closed 状态下，如果读取开门信号，那么状态就会切换为 open 。open 状态下如果读取关门信号，状态就会切换为 closed 。状态机的全称是有限状态自动机，自动两个字也是包含重要含义的。给定一个状态机，同时给定它的当前状态以及输入，那么输出状态时可以明确的运算出来的。例如，对于自动门，给定初始状态 closed ，给定输入“开门”，那么下一个状态时可以运算出来的。这样状态机的基本定义我们就介绍完毕了。重复一下：状态机是有限状态自动机的简称，是现实事物运行规则抽象而成的一个数学模型。2、状态机的四大部分状态机是一个抽象的数学模型，其分为四大部分组成。如下所示：第一个是 State 状态。一个状态机至少要包含两个状态。例如上面自动门的例子，有 open 和 closed 两个状态。第二个是 Event 事件。事件就是执行某个操作的触发条件或者口令。对于自动门，“按下开门按钮”就是一个事件。第三个是 Action 动作。事件发生以后要执行动作。例如事件是“按开门按钮”，动作是“开门”。编程的时候，一个 Action 一般就对应一个函数。第四个是 Transition 变换。也就是从一个状态变化为另一个状态。例如“开门过程”就是一个变换。编写代码的时候，有时会遇见较为复杂的swith...case...和if...else...语句。这一刻有时会想到状态机，用有限状态机替换swith...case...和if...else...3、容错性容错性是个令人容易产生歧义的术语。从字面上来看，是“容忍错误”之意，非也。请看下文来自百度百科的介绍：故障容许度（英语：Fault tolerance）也称容错、容错性，是使系统在部分组件（一个或多个）发生故障时仍能正常运作的能力。故障容许度即是Fault Tolerance，确切地说是容故障（Fault），而并非容错误（Error）。例如在双机容错系统中，一台机器出现问题时，另一台机器可以取而代之，从而保证系统的正常运行。在早期计算机硬件不是特别可靠的情况下，这种情形比较常见。现在的硬件虽然较之从前稳定可靠得多，但是对于那些不允许出错的系统，硬件容错仍然是十分重要的途径。4、状态机复制共识是分布式系统中的一个基本问题。共识就是多个服务器就某个值而言，最终达成一致的决策过程。一旦它们对一个值做出决定，这个决定就是最终决定。一般情况下，共识算法只要满足“多数存活”的原则即可，例如，一个由5台服务器组成的集群，即使有2台服务器出现故障也可以继续运行。如果有更多的服务器出现故障，它们将停止工作，但永远不会返回错误的结果。共识算法通常依赖于状态机复制，这是构建容错系统的通用做法。所谓“容错性”指的是，分布式系统在遇到任何网络分区故障的时候，仍然能够对外提供满足一致性和可用性的服务，除非整个网络环境都发生了故障。如果我们要让一个服务具有容错能力，那么最常用最直接的办法就是让一个服务的多个副本同时运行在不同的节点上。但是，当一个服务的多个副本都在运行的时候，我们如何保证它们的状态都是同步的呢，或者说，如果让客户端看起来无论请求发送到哪一个服务副本，最后都能得到相同的结果。实现这种同步方法就是所谓的状态机复制（State Machine Replication）。状态机复制的理论基础是：如果集群里的每一个节点上都运行着相同的确定性状态机S，并且所有的状态机刚开始都处于同样的初始状态s0，那么给予这些状态机相同的输入序列：{i1, i2, i3, i4, i5, i6, …, in}这些状态机必然会经过相同的状态转换路径：s0->s1->s2->s3->…->sn最终达到相同的状态sn，同时生成相同的输出序列：{o1(s1), o2(s2), o3(s3), …, on(sn)}状态机复制在实际应用中的一个例子就是MySQL集群。我们知道，MySQL集群中的master会把所有的操作记录到binlog中，这里的操作就是输入序列I，然后slave会把master上的binlog复制到自己的relaylog中，然后再把relaylog里的操作回放一遍（相当于执行了一遍输入序列I）。所以，如果master和slave里的状态机是完全相同的，并且在执行序列I之前都处于相同的状态下，那么执行完序列I后，它们的状态依旧是相同的（一致性）。在执行输入序列I的过程中，根据同步方式的不同，系统就有了强一致性和最终一致性。如果我们要求对于序列I中的每一个in， 都需要所有的服务副本确认成功执行了in，才能执行in+1，那么这个系统就是强一致性的系统。如果我们取消掉这个限制，仅仅要求所有的服务副本执行相同的输入序列I，但是完全各自独立执行，而不需要在中间同步，那么就有了最终一致性（各服务都会达到相同的最终状态，但是达到的时间不确定）。所有一致性算法都会涉及到状态机，而状态机保证系统从一个一致的状态开始，以相同的顺序执行一些列指令最终会达到另一个一致的状态。 第五节：Raft共识算法的核心组件 Raft共识算法的核心设计包括两大部分：状态机与日志。状态机的介绍，请看上文，而对于日志的理解，常常是初学者容易迷惑的地方。在Raft语境下，我们所说的“日志”并不是系统运行的警告，错误等信息等，而是指操作记录。例如，set x to 3等。每台服务器都有一个状态机和一个日志。状态机本质就是一个具有容错性的组件。在客户机看来，即使集群中的少数服务器出现故障，它们也会与单个可靠的状态机进行交互。每个状态机处理相同的命令序列，从而产生相同的结果序列并到达相同的状态序列。 第六节：Raft算法实现过程 Raft算法主要包括选举和日志同步两部分：第一阶段：选举。从集群中选出一个合适的节点作为Leader。第二阶段：日志同步。选举出的Leader接收客户端请求，将其转为Raft日志。Leader将日志同步到其他节点，当大多数节点写入成功后，日志变为Committed，一经Committed日志便不会再被篡改。Leader故障时，切换到第一阶段，重新选举。 第七节：Raft算法的独有特性 Raft算法是专门针对Paxos算法难以理解的缺陷而重新设计的新算法，为使算法容易理解，采用了模块化设计方法，将整个过程划分为若干子问题，逐一解决，这些问题包括Leader选举，日志分发，日志一致性等。Raft算法和已有的其他共识算法有很多相似之处，但也有自己独特的特性：（1）高度集权的Leader。相对其他共识算法，Raft的Leader权利更集中，例如，只有Leader可以接受客户请求，所有日志都是通过Leader分发给其他服务器。这一特性简化了日志管理，也让算法容易理解。（2）非常简单的Leader选举。Leader选举过程采用随机时间计时器，谁先完成沙漏倒计时谁就最有可能成为Leader，做法简单粗暴但异常好用，快速地解决了Leader选举过程中的各种冲突。（3）成员变化，系统不罢工。当集群的成员发生变化，例如增加或减少服务器时，Raft采用新的联合一致性方法来进行处理，可以保证成员变化过程中系统正常工作。 第八节：Raft算法的独有特性 1、选举思想在Raft算法中，充斥着“君主高度集权，立储简单明了”的思想。首先，Raft集群会选举出一个唯一的Leader，该Leader负责管理日志(日志，即操作记录日志)，并且所用对日志的添加和修改等操作都通过Leader完成。Leader接受用户的日志请求并将日志分发给系统中其他节点，并告知其他节点何时可以安全地将日志应用到状态机上。这种方式简化了多副本日志的管理，日志的数据流向是从Leader到其他节点，而其他节点不会发送日志给Leader，职责分明，非常简单。Leader宕机之后，Raft集群会选出一个新的Leader。通过采用高度集权的Leader，Raft把一致性问题分解为相互独立的3个子问题：（1）Leader选举：系统初始化时需要选出Leader，Leader当掉时选出新的Leader。（2）日志分发：Leader接受日志请求并分发给其他节点。（3）确保日志的一致性：确保所有日志副本是一致的。2、节点的状态在Raft集群中，任何一个节点在任何一个时刻都处于三种状态之一：Leader, Follower, Candidate。在系统正常运行的绝大部分时间，系统中会有一个Leader, 其他都是Follower。Follower是被动的，只接受来自Leader和Candidate的请求，自己不会发出任何请求。Candidate状态是在Leader选举过程中的临时状态。为了更好的深刻的掌握这三种状态，我将它们起名叫：群众，夺权者，当权者。下图描述了三种状态之间的转换关系： 对于初学者来说，上面的状态转换令人眼花缭乱，我给大家简单的说一下。假设集群中有一台服务器A，最初(starts up)的状态为follower，沙漏耗尽之后开始了选举，它有一个不安分的心，它想当leader，此时它的状态变为candidate，然后它向集群中其他服务器发送“选我”信息，如果收到大多数成员的同意之后，则成功当选为leader，反之，如果没有收到大多数成员的同意而收到了新leader的消息，则灰头土脸的继续当“庶民”，状态还原为follower。其实，即便当上了leader，也是高处不胜寒的，有一天也会被他人篡权夺位，而变为庶民的。3、任期的理解Raft把时间分为连续的任期(Term)，每个任期可以是任意时长，任期用连续的整数进行标号。每个任期首先进行Leader选举，选举时，多个Candidate竞争成为Leader,一旦某个节点成为Leader，其他节点则变回Follower，成为Leader的节点将在该任期内一直担任Leader，如果该Leader节点发生故障，其他节点会在新的任期内进行选举。任何一个任期内都不会有多个Leader。Raft系统中，任期是一个及其重要的概念，每个节点都维护着当前任期的值，每次节点间的通信都包含任期信息，每个节点在检测到自己的任期值低于其他节点，都会更新自己的任期值，设置为检测到的较高的值。当Leader和Candidate发现自己的任期低于别的节点，则立即把自己转换为Follower。注意：任期与计时器是绑定到一起的。任何新任期的启动，必然伴随一个新计时器的启动。4、远程调用RPCRaft节点间的通信采用RPC调用， Raft算法核心部分只需要用到两个RPC: RequestVote和AppendEntries。RequestVote RPC由Candidate发起用于Leader选举。AppendEntries RPC由Leader发起，用于心跳和日志复制。而Follower不会发起任何RPC。5、Leader选举过程Raft采用心跳机制触发Leader选举。当系统启动时，所有节点初始化为Follower状态，设置任期为0，并启动计时器，计时器超时后，Follower节点转化为Candidate节点，一旦转化为Candidate节点，立即开始做以下几件事情：（1）增加自己的任期数（2）启动一个新的计时器（3）给自己投一票（4）向所有其他节点发送RequestVote RPC请求，并等待其他节点回复。如果在计时器超时前接收到多数节点的同意投票，则转换为Leader。如果接受到其他节点的AppendEntries心跳RPC，说明其他节点已经被选为Leader, 则转换为Follower。如果计时器超时的时候还没有接受到以上两种信息中的任何一种，则重复步骤1-4，进行新的选举。节点在接受到多数节点的投票成为Leader后，会立即向所有节点发送AppendEntries 心跳RPC。所有Candidate收到心跳RPC后，转换为Follower，选举结束。每个Follower在一个任期内只能投一票，采取先到先得的策略。每个Follower有一个计时器，在计时器超时时仍然没有接受到来自Leader的心跳RPC, 则转换为Candidate, 开始请求投票。也就是在当期Leader当掉后，就会有Follower开始转换为Candidate开始投票。如果多个节点同时发起投票，每个节点都没有拿到多数票（这种情况成为Split Vote），则增加任期数，在新的任期内重新进行投票。有没有可能Split Vote反复发生，永远都选不出Leader呢？不会的。因为Raft采取随机超时时间，Raft系统有一个选举超时配置项，Follower和Candidate的计时器超时时间每次重新计算，随机选取配置时间的1倍到2倍之间。即使所有节点同时启动，由于随机超时时间的设置，各个节点一般不会同时转为Candidate，先转为Candidate的节点会先发起投票，从而获得多数票。因而在每个任期内，多个节点同时请求投票并且都只获得少数票的几率很小，连续多次发生这种情况几率更小，实际上可以认为完全不可能发生。一般情况下，基本上都在1-2个任期内选出Leader。 第九节：Raft RPC简介 通过上面的内容我们可以得知，Raft核心部分只需要用到2个RPC：RequestVote和AppendEntries。每个Raft节点将会根据自己节点的状态数据来对这两种RPC请求进行处理。RequestVote RPC是由Candidate发送给其他节点，请求其他节点为自己投票，如果一个Candidate获得了多数节点的投票，则该Candidate转变为Leader。AppendEntries RPC是由Leader节点发送给其他节点，有两个作用，当其entries域为空时，该RPC作为Leader的心跳；当entries域不为空时，请求其他节点将entries域中的日志添加到自己的日志中。 第十节：Raft日志复制 1、日志复制的过程Leader选出后，就开始接收客户端的请求。Leader把请求作为日志条目（Log entries）加入到它的日志中，然后并行地向其他服务器发起 AppendEntries RPC 复制日志条目。当这条日志被复制到大多数服务器上，Leader将这条日志应用到它的状态机并向客户端返回执行结果。客户端的每一个请求都包含被复制状态机执行的指令。Leader把这个指令作为一条新的日志条目添加到日志中，然后并行发起 RPC 给其他的服务器，让它们复制这条信息。假如这条日志被安全的复制，Leader就应用这条日志到自己的状态机中，并返回给客户端。如果Follower宕机或者运行缓慢或者丢包，Leader会不断的重试，直到所有的Follower最终都复制了所有的日志条目。 2、日志的组成日志由有序编号（log index）的日志条目组成。每个日志条目包含它被创建时的任期号（term）和用于状态机执行的命令。如果一个日志条目被复制到大多数服务器上，就被认为可以提交（commit）了。 上图显示，共有 8 条日志，提交了 7 条。提交的日志都将通过状态机持久化到磁盘中，防止宕机。3、日志复制的详细介绍当Leader接收到由客户端发送的请求(请求中包含可以被复制状态机执行的命令)时，Leader将会把该请求作为新的内容添加到日志中(任期号为当前Leader所处的任期号，索引号为当前Leader本地存储的日志集合中的日志的最高索引号加1)。然后将该日志通过AppendEntries RPC消息发送到网络中其他的服务器(以下简称Follower)，从而复制该日志。在网络中Follower接收到该日志消息后则会返回复制成功的回复。在Leader接收到网络中大部分的Follower的成功复制的回复之后，Leader便认为该日志可以被提交。此时Leader将会同时做三件事：（1）将该日志应用到Leader本地的复制状态机（2）向所有Follower发送消息通知所有接收到该日志的Follower将该日志进行提交，然后应用到各自本地的复制状态机（3）将执行结果通知客户端当该日志消息成功在网络中大部分Follower本地的复制状态机执行过后，则可认为该日志已被提交。在当前日志被提交的过程中，如果Leader先前的某些日志还没有被提交，则将会一同提交。而网络中有些Follower可能由于网络状态原因反应缓慢或者崩溃，那么Leader将会无限次地尝试重复发送AppendEntries RPC消息到该Follower。直到成功为止。4、Leader切换导致日志的不一致性 5、日志的一致性检查如上所述，Follower在接收到AppendEntries RPC消息后则会返回复制成功的回复。实际上在接收到消息后会首先进行日志的一致性检查(正常情况下Leader与Follower的日志会保持一致，所以一致性检查不会失败)，一致性检查内容如下：在Leader创建AppendEntries RPC消息时，消息中将会包含当前日志之前日志条目的任期号与索引号。Follower在接受到AppendEntries RPC消息后，将会检查之前日志的任期号与索引号是否匹配到。如果匹配则说明和Leader之前的日志是保持一致的，否则，如果没有匹配则会拒绝AppendEntries RPC消息。一致性检查是一个归纳的过程。正常情况下，网络中第一条日志一定满足日志的一致性检查，然后第二条日志中包含第一条日志的任期号与索引号，所以只要Leader与Follower的第一条日志保持一致，那么第二条日志也会满足一致性检查，从而之后的每一条日志都会满足一致性检查。从而得出了日志匹配属性:（1）如果两个不同的日志实体具有相同的索引和任期号，那么它们存储有相同的命令。（2）如果两个不同的日志实体具有相同的索引和任期号，则所有先前条目中的日志都相同。(由一致性检查结果得出) 第十一节：Raft日志不一致的解决方案 1、日志不一致的三种情况网络不可能一直处于正常情况，因为Leader或者某个Follower有可能会崩溃，从而导致日志不能一直保持一致，因此存在以下三种情况：（1）Follower缺失当前Leader上存在的日志条目。（2）Follower存在当前Leader不存在的日志条目。比如，旧的Leader仅仅将AppendEntries RPC消息发送到一部分Follower就崩溃掉，然后新当选Leader的服务器恰好是没有收到该AppendEntries RPC消息的服务器)（3）Follower即缺失当前Leader上存在的日志条目，也存在当前Leader不存在的日志条目。为了更好的说明这三种情况，请看下面的图示。 备注：（1）图中最上方是日志的索引号(1-12)，每个方块代表一条日志信息，方块内数字代表该日志所处的任期号。（2）图中当前Leader(图中最上方一行日志代表当前Leader日志)处于任期号为8的时刻。分析说明下面，以此图分析说明以上三种情况存在的原因：（1）Follower a、Follower b满足以上说明的第一种情况：Follower崩溃没有接收到Leader发送的AppendEntries RPC消息。（2）Follower c在任期为6的时刻，Follower d在任期为7的时刻为Leader，但没有完全完成日志的发送便崩溃了，满足以上说明的第二种情况：Follower存在当前Leader不存在的日志条目。（3）Follower e在任期为4的时刻，Follower f在任期为2、3的时刻为Leader，但没有完全完成日志的发送便崩溃了，同时在其他服务器当选Leader时刻也没有接收到新的Leader发送的AppendEntries RPC消息，满足第三种情况：Follower即缺失当前Leader上存在的日志条目，也存在当前Leader不存在的日志条目。备注： 如上文所示，根据日志的任期数目来判断节点是否为Leader，再次印证了任期的关键作用。2、日志不一致的解决方案Leader通过强迫Follower的日志重复自己的日志来处理不一致之处，这意味着Follower日志中的冲突日志将被Leader日志中的条目覆盖。这个过程如下所示：首先，Leader找到与Follower最开始日志发生冲突的位置，然后删除掉Follower上所有与Leader发生冲突的日志，最后将自己的日志发送给Follower以解决冲突。需要注意的是：Leader不会删除或覆盖自己本地的日志条目。当发生日志冲突时，Follower将会拒绝由Leader发送的AppendEntries RPC消息，并返回一个响应消息告知Leader日志发生了冲突。Leader为每一个Follower维护一个nextIndex值。该值用于确定需要发送给该Follower的下一条日志的位置索引。该值在当前服务器成功当选Leader后会重置为本地日志的最后一条索引号+1。当Leader了解到日志发生冲突之后，便递减nextIndex值，并重新发送AppendEntries RPC到该Follower，不断重复这个过程，一直到Follower接受该消息。一旦Follower接受了AppendEntries RPC消息，Leader则根据nextIndex值可以确定发生冲突的位置，从而强迫Follower的日志重复自己的日志以解决冲突问题。 情况a：如上图，服务器S1在任期为2的时刻仅将日志<index:2,term:2>发送到了服务器S2便崩溃掉。情况b：服务器S5在任期为3的时刻当选Leader(S5的计时器率先超时，递增任期号为3，高于服务器S3和S4，因此可以当选Leader)，但没来得及发送日志便崩溃掉。情况c：服务器S1在任期为4的时刻再次当选Leader(S1重启时，任期仍然为2，收到新的Leader S5发送的心跳信息后更新任期为3，而在Leader S5崩溃后，服务器S1为第一个计时器超时的，因此发起投票，任期更新为4，大于网络中其他服务器任期，成功当选Leader)，同时将日志<index:2,term:2>发送到了服务器S2和S3，但还没有通知服务器对日志进行提交便崩溃掉。情况d：情况(a->d)如果在任期为2时服务器S1作为Leader崩溃掉，S5在任期为3的时刻当选Leader，由于日志<index:2,term:2>还没有被复制到大部分服务器上，并没有被提交，所以S5可以通过自己的日志<index:2,term:3>覆盖掉日志<index:2,term:2>。情况e：情况(a->e)如果在任期为2时服务器S1作为Leader，并将<index:2,term:2>发送到S2和S3，成功复制到大多数成员服务器上。S1成功提交了该日志，那么即便S1崩溃掉，S5也无法成功当选Leader，因为S5不具备网络中最新的已被提交的日志条目，S5只有term为1的日志。 第十二节：Raft算法中成员变更过程解析 在Raft论文中，成员变更属于难点，但这一部分相比于论文其他部分，确实讲解最不详细，让人读完之后很迷惑。1、什么是成员变更？成员变更指的是系统成员变化，即服务器节点的上下线，这和由于宕机故障导致的上下线是不同的。宕机或者重启导致的上下线，是不会影响系统的注册的成员数量的，也就不会影响到一致性判断所依据的“多数派”的生成，众所周知，“多数派”是所有一致性的基础。成员变更时，会修改注册的成员数量，比如在实际应用中，为了提高安全等级，就很可能出现需要把备机数量由三台扩充到五台，在这种情况下，就发生了成员变更。另外，还有一个十分需要注意的地方：成员变更意味着大家都还活着，并不像宕机那样，立即死亡，无法再做“交接工作”。被变更的成员是需要完成“交接工作”的。所谓的“交接工作”，就是下文中提到的“做决策”。2、直接变更存在的问题在成员变更时，因为无法做到在同一个时刻使所有的节点从旧配置转换到新配置，那么直接从就配置向新配置切换就可能存在一个节点同时满足新旧配置的“超过半数”原则。如下图，原集群由Server1、Server2、Server3，现在对集群做变更，增加Server4、Server5。如果采用直接从旧配置到新配置的切换，那么有一段时间存在两个不想交的“超过半数的集群”。 上图，中在中间位置Server1可以通过自身和Server2的选票成为Leader（满足旧配置下收到大多数选票的原则）；Server3可以通过自身和Server4、Server5的选票成为Leader（满足新配置线，即集群有5个节点的情况下的收到大多数选票的原则）；此时整个集群可能在同一任期中出现了两个Leader，这和协议是违背的。3、Raft的成员变更实现方案：分阶段变更Raft提出了通过一个中间过渡阶段，即联合共识（joint consensus），逐步把数据写入的新的集群中。其具体做法是2阶段提交式的：第一阶段：Leader收到C-old到C-new的配置变更请求时，创建C-old-new的日志并开始复制给其他节点，此日志和普通日志复制没有区别。此时做决策的仍然是C-old集群。第二阶段：当只有C-old-new复制到大多数节点后，Leader以这个配置做决定，这个时候处于一个共同决定的过程，因为此时做决策的是C-old-new集群。由于两阶段变更不存在一个阶段C-old和C-new可以同时根据自己的配置做出决定，所以不会出现上文描述的情况。备注：虽然自己是Leader，但是做决策的可不是Leader，它要根据多数派的原则进行拍板定方案，所以归根结底，做决策的还是集群中的其他Follower成员。4、Raft论文解读 论文里面的这张图片看起来让人头大，个人感觉有点凌乱。虚线表示已创建但尚未提交的配置项，实线表示已经提交的配置项。最难以理解的地方在于最上面的“豁口”，其表示中间过渡阶段，即联合共识（joint consensus），其开始于C-old-new复制到大多数节点后，而结束于C-new提交之后，因为C-old-new与C-new的配置内容虽不相同但是一致，两者是等价的，所以可以视为C-new能够单独做决定。当C-new被复制到大多数节点的时候，如果Leader不在C-new之内，则自己做下线处理，C-new集群开始进行新的选主操作。
BASE原则BASE是Basically Available（基本可用）、Soft state（软状态）和Eventually consistent（最终一致性）三个短语的简写，含义如下所示：基本可用：保证数据的可用性。任何请求都会有响应（也可能是失败）。软状态：软状态和硬状态相对，是指允许系统中的数据存在中间状态，并认为该中间状态的存在不会影响系统的整体可用性，即允许系统在不同节点的数据副本之间进行数据传输的过程存在延时。最终一致性：强调的是系统中所有的数据副本，在经过一段时间的同步后，最终能够达到一个一致的状态。因此，最终一致性的本质是需要系统保证最终数据能够达到一致，而不需要实时保证系统数据的强一致性。BASE原则是根据CAP原则演变而来。CAP指的是在一个分布式系统中，一致性（Consistency）、可用性（Availability）、分区容错性（Partition tolerance）。CAP原则指的是，这三个要素最多只能同时实现两点，不可能三者兼顾。BASE原则是对CAP中一致性和可用性的权衡的结果，其核心思想是即使无法做到强一致性，但是每个应用根据自身的业务特点，采用适当的方式来使系统达到最终一致性。BASE原则中的 Soft State 是什么意思？BASE中的soft state指的是什么呢？在stack over flow中有个不错的解释：[soft state] is information (state) the user put into the system that will go away if the user doesn't maintain it. Stated another way, the information will expire unless it is refreshed.By contrast, the position of a typical simple light-switch is "hard-state". If you flip it up, it will stay up, possibly forever. It will only change back to down when you (or some other user) explicitly comes back to manipulate it.翻译一下就是：[软状态]是用户放入系统的信息（状态），如果用户不维护它，这些信息（状态）就会消失。换句话说，除非信息被刷新，否则它将过期。例如电商支付过程中“支付中”状态，最终的结果只有支付成功和支付失败，不会一直存在“支付中”状态的。相比之下，一个典型的简单灯光开关的位置是“硬状态”。如果你把它翻过来，它会一直翻下去，可能会一直翻下去。只有当你（或其他用户）显式地返回来操纵它时，它才会变回down。参考：https://stackoverflow.com/questions/4851242/what-does-soft-state-in-base-mean综上所述，我们可以明白，软状态指的是允许系统中的数据存在中间状态，并认为该中间状态不会影响系统的整体可用性。例如在电商支付过程中，给数据加上一个“支付中”状态。它最终要么是支付完成，要么是支付失败。支付中的状态存留的时间取决下游支付系统完成这笔支付的时间。