概述

分布式一致性协议应该是分布式系统中最重要的基石了，但凡涉及到分布式相关的技术都必然绕不开这个话题。根据cap理论可知分布式一致性有两种形态：

  • 最终一致性
  • 强一致性

不过分布式一致性中的一致究竟应该如何理解，我其实是一直有疑问的。最早我的理解是假定是分布式系统是一个状态机，那么所有节点中的状态时刻都一致， 这就叫做状态一致性。我尝试说服我自己就是这样的，但是分布式系统必然存在节点之间的通信，通信带来的延迟必然会导致状态的不一致，而如果状态一致 之后才对外可用，那么新的问题又来了，我怎么样知道你和我一致呢？我们知道网络中存在丢包和延迟的情况，如果真是要所有的节点达到一个一致的状态 之后才可用，那么必定会在效率上大打折扣。另外一点可用是什么意思我也一直无法理解。在翻越了大量的资料之后，也学习并查看了比较经典的分布式一致性算法诸如 ：paxos、raft，最终有了一个猜测，与其说这些算法叫做分布式一致性算法，不如说叫做分布式共识算法。分布式一致性强调的是一致性，也就是内部状态一致，是针对一个集群，而 分布式共识强调的是共识，是对外部的提议达成共识，这本身存在两个集群或者说系统（提议集群、决策集群，在极端的情况下提议集群和决策集群可以是一个集群，这就是内部的leader选举的过程）， 不过在决策集群达成共识的时候，决策集群的内部的状态可能并不是一致性的状态，只需要大部分节点的状态一致即可，这里的大部分就涉及了另外一个名词：quorum。之所以大部分一致而不是所有节点 的状态一致，原因是可以提高容错，毕竟如果集群中有一个节点不可用，就会导致集群不可用，那么和只有一个节点对外提供服务有什么区别呢？

详解

下面进入我们的正题：raft协议介绍，需要强调一下：

  • raft集群中的节点需要有一半以上可用，如果没有一半以上的节点可用，那么整个集群无法对外提供服务（这个在异常分析的时候尤其重要）。
  • 当日志复制遇到问题之后，不用改在日志复制的角度尝试解决，而是将其归入leader异常选举的情况，这样就可以顺利的化解问题。

raft协议的实现可以分为以下几个部分：

  • leader选举
  • 日志的复制

leader选举

leader的选举存在两种情况：

正常选举

在服务初始化的时候，假设还没有用户端的请求过来，这个时候，集群中的节点会自动随机完成leader的选举，不过这种情况比较简单，因为还没有涉及到客户端的日志。

异常选举

首先可以肯定的是所有的节点是都可以参与leader选举的，不过其他节点在给参与投票的节点投票的时候可以选择投或者不投，选择投不投票的原则则显得尤为重要了：

  • 如果节点已经投过了，则不可以再投
  • 在收到投票请求的时候会比对两个参数：任期term以及日志的最后一个索引的大小看，通过这种二次比较可以选择投票或者不投票给这个节点，我们知道一旦日志被应用到多数的 节点，那么必然会有一半以上的节点日志是最新的，而其他的节点在发起选举的时候，要求这个节点给他选票的时候就可以发现日志最新条件不满足了，最终这半数以上的节点会投 反对票，基线情况就是剩下的不到一半的节点全部投了赞成票，即便是这个样子，赞成票的总数也还是没有达到一半以上，因此这种决议就会失败。

上述leader选举的过程中整个服务对外是会存在一个不可用的状态的，但是，不是一直不可用（至少选举刚发出的这个时刻有可能是可用的）。

日志复制

在选出来leader之后，接下来就是对外提供服务了，raft是采用状态机的方式对外提供服务的。具体点就是：日志+状态机，日志有点类似预写日志的方式，而 状态机则是将日志中的命令执行，可以知道在初始状态一致并且按照相同的顺序执行了相同的命令的命令的话，那么分布式服务对外呈现的状态一定是一致的， 这里的一致是指用于决策的分布式对外达成了共识，并且内部也进入了一致的状态。

日志的处理过程分为以下几个阶段：

  • leader接收客户端的请求（如果是follower接收到请求的话，会将这个请求路由转发到leader）
  • 在leader记录日志之后（uncommitted），将该请求转发到所有的follower节点
  • follower在收到leader发过来的请求的时候会同样记录到日志中（uncommitted），同时会给leader发出响应
  • leader在接收到客户端的响应之后会判断quorum个数的节点是否都响应了，如果响应的话，此时leader中的消息会进入committed状态，同时 leader会通过消息告诉其他的follower节点，你们可以提交了。

上述整个流程执行下来尤其和2pc提交相似，不过不同的是，上述过程并不要求所有节点都成功复制日志，只要有半数以上的节点即可。 需要强调一点只有committed后的消息才会被应用到状态机。接下来我们分析一下上述过程中可能存在的问题：

  • leader在接收到请求后直接挂了，此时会进入选举leader的状态，因此这个过程我们将会统一归入到leader选举中
  • leader在接收到消息之后，并将请求转发到对应的follower上，此时follower可能由于某种原因没有办法给到服务端的响应，如果 异常的follower个数未达到半数，此时服务可以继续对外提供（牢记半数以上的节点对外可用这个条件是整个服务可用的基础）； 如果异常的follower达到半数，则直接返回失败给客户端。那已经被记录的消息将会 一直存在于集群中，不过由于follower的消息是uncommitted的状态，因此消息不会被应用到状态机，整个系统对外一致。 （再次出现leader选举也不会应用这种uncommitted的日志）
  • leader在接收到半数的服务发过来的响应之后，就会将对应的消息进行committed，并返回客户端成功commit的消息，如果此时leader发生了宕机， 或者说leader在发出了部分（少于半数）follower的commit消息之后就出现了宕机：
    • leader应用了日志到状态机中，但是没有给客户端成功发送响应，此时客户端会等待服务端重新选举出来leader，要么由新的leader告知其结果，要么进入fast fail状态
    • leader应用日志到状态机中，并且返回客户端成功的响应，但是在leader给follower commit消息的时候挂了此时会进入leader的选举中：
      • leader在选举中忽然复活了
      • leader在新的节点成为新的leader的过程中一直处于死亡状态

最后一种情况是比较复杂的，不过出现这种情况意味着leader需要重新选举，我们只需要保障leader的选举是安全的，就可以保证最终的状态是一个可预知并且是正确的。

上面的情况可以分析得知leader的安全选举才是真正的核心

异常问题

脑裂

当集群所在的网络出现分区之后，主节点形成一个小的集群，其他的节点形成一个大的集群的时候，大的集群会通过选主选出来新的leader， 不过由于原来的leader还在运行（leader不会主动下线），这样就会导致整个集群出现两个leader， 两个leader由于网络故障，互相之间不知道彼此存在，不过客户端和两个leader之间可能是可以联通的， 这样形成的整体上的非对称网络分区就会导致客户端看起来有两个leader，在执行一些操作的时候，会发现由于leader的闪烁导致结果不可预测。 出现这种问题的之后可以通过下掉旧的leader的方式来解决（需要在节点的程序自己实现，记录最近是不是还有follower心跳是ok的）

日志复制异常

当选出来的leader提交了不是自己任期的日志的时候（这里的提交是commited，集群中大多数都有某个日志条目）， 可能会在提交的过程中down机，最终新出来的leader会把这些认为是提交了的日志给覆盖掉，最终会导致集群可能已经被应用到状态机的 日志又被删除，最终集群中的这么多节点之间出现不一致，这种问题的解决方案是，本任期的leader只提交当前任期的日志信息， 其他的则通过递归的方式提交上去，只有在其他的日志都提交上去之后，当前任期的日志才最终提交上去，这种模式尤其类似于 线程的join机制，让本任期的日志提交阻塞在提交其他任期的日志。这样就可以解决日志复制异常存在的问题。

节点的动态变迁

TODO

小结

raft是简化版的paxos，原因是paxos的每一个过程都包含了类似于leader选举、达成共识两个阶段，而raft在leader选举完成之后，下一次服务不会再次进行 leader选举，这样就把每个提议都要执行的两个步骤优化成了一个步骤了。另外我们经常听到的：DNS服务器就可以认为是采用最终一致性的模式来解释分布式一致性（共识）协议， 我认为这种说法是不对的。