可理解的共识算法研究

(In Search of an Understandable Consensus Algorithm–Extended Version)

作者:Diego Ongaro and John Ousterhout–Stanford University

摘要

Raft是管理复制日志的共识算法, 比Paxos牛.

1. 介绍

复制状态机,如图1

图1

共识算法管理

2. Raft把共识算法分解为3个独立的子问题：

2.1 Leader选举

当前Leader挂掉后必须进入一个新Leader的选举

集群中每个节点，任意时刻处于Leader, Follower, Candidate这三个角色之一。选举特点如下：

  • 当集群初始化时候，每个节点都是Follower角色；
  • 集群中存在至多1个有效的主节点，通过心跳与其他节点同步数据；
  • 当Follower在一定时间内没有收到来自主节点的心跳，会将自己角色改变为Candidate，并发起一次选主投票；当收到包括自己在内超过半数节点赞成后，选举成功；当收到票数不足半数选举失败，或者选举超时。若本轮未选出主节点，将进行下一轮选举（出现这种情况，是由于多个节点同时选举，所有节点均未获得过半选票）。
  • Candidate节点收到来自主节点的信息后，会立即终止选举过程，进入Follower角色。

为了避免陷入选主失败循环，每个节点未收到心跳发起选举的时间是一定范围内的随机值，这样能够避免2个节点同时发起选主。

2.2 日志复制

所谓日志复制，是指Leader将每次操作形成日志条目，并持久化到本地磁盘，然后通过网络IO发送给其他节点。其他节点根据日志的逻辑时钟(TERM)和日志编号(INDEX)来判断是否将该日志记录持久化到本地。 当Leader收到包括自己在内超过半数节点成功返回，那么认为该日志是可提交的(committed），并将日志输入到状态机，将结果返回给客户端。

这里需要注意的是，每次选Leader都会形成一个唯一的TERM编号，相当于逻辑时钟。每一条日志都有全局唯一的编号。

Leader通过网络IO向其他节点追加日志。若某节点收到日志追加的消息，首先判断该日志的TERM是否过期，以及该日志条目的INDEX是否比当前已经提交的日志的INDEX更早。若已过期，或者比提交的日志更早，那么就拒绝追加，并返回该节点当前的已提交的日志的编号。否则，将日志追加，并返回成功。

当Leader收到其他节点关于日志追加的回复后，若发现有拒绝，则根据该节点返回的已提交日志编号，发送其编号下一条日志。

Leader向其他节点同步日志，还作了拥塞控制。具体地说，主节点发现日志复制的目标节点拒绝了某次日志追加消息，将进入日志探测阶段，一条一条发送日志，直到目标节点接受日志，然后进入快速复制阶段，可进行批量日志追加。

按照日志复制的逻辑，我们可以看到，集群中慢节点不影响整个集群的性能。另外一个特点是，数据只从Leader复制到Follower，这样大大简化了逻辑流程。

2.3 安全性

Leader不会删除或复写log entries；只增加新的entries

选主以及日志复制并不能保证节点间数据一致。试想，当一个某个节点挂掉了，一段时间后再次重启，并当选为主节点。而在其挂掉这段时间内，集群若有超过半数节点存活，集群会正常工作，那么会有日志提交。这些提交的日志无法传递给挂掉的节点。当挂掉的节点再次当选主节点，它将缺失部分已提交的日志。在这样场景下，按Raft协议，它将自己日志复制给其他节点，会将集群已经提交的日志给覆盖掉。

这显然是不可接受的。

其他协议解决这个问题的办法是，新当选的主节点会询问其他节点，和自己数据对比，确定出集群已提交数据，然后将缺失的数据同步过来。这个方案有明显缺陷，增加了集群恢复服务的时间（集群在选举阶段不可服务），并且增加了协议的复杂度。

Raft解决的办法是，在选主逻辑中，对能够成为主的节点加以限制，确保选出的节点已定包含了集群已经提交的所有日志。如果新选出的主节点已经包含了集群所有提交的日志，那就不需要从和其他节点比对数据了。简化了流程，缩短了集群恢复服务的时间。

这里存在一个问题，加以这样限制之后，还能否选出主呢？答案是：只要仍然有超过半数节点存活，这样的主一定能够选出。因为已经提交的日志必然被集群中超过半数节点持久化，显然前一个主节点提交的最后一条日志也被集群中大部分节点持久化。当主节点挂掉后，集群中仍有大部分节点存活，那这存活的节点中一定存在一个节点包含了已经提交的日志了。

3. Raft 节点

一般来说，Raft集群节点个数为5个，此时可以容忍两个失效。

3.1 节点角色

Leader, Follower, Candidate，一般来说，只有一个Leader，其余都是Follower。

图4 图4：各节点的状态。

3.1.1 Followers

只响应来自其他节点的请求【只对Leader和Candidate做出响应】，如果没有收到其他节点的信息，则会变成Candidate并且初始化一个选举过程。若该节点收到了客户端的请求，则会重定向至leader节点。

3.1.2 Candidate

用来选举新的Leader。如果收到大多数节点的投票，则会变成Leader。

3.1.3 Leader

会一直工作到失败。其接受所有客户的请求，当Leader发现自己的任期ID比其他节点的任期ID小时，自动放弃Leader的位置，转为Follower

3.2 Leader节点任期

任期号单调递增，从0开始

term

图5:任期

从图中可以看出，每个任期从选举开始。选举成功后该任Leader管理整个集群直到任期结束。

任期结束会有新的Leader的生成，也有可能选举失败即本轮未选出主节点，将进行下一轮选举（出现这种情况，是由于多个节点同时选举，所有节点均未获得过半选票）。

3.3 节点崩溃

Leader崩溃： 触发新的选举过程， Follower和Candidate崩溃：比Leader崩溃简单，并且处理方法都一样，即：崩溃后的投票请求和日志复制请求会一直重试直到节点从崩溃状态恢复。

4. 时间和可用性

Leader选举是Raft中最为依赖时间的一个方面。只要如下条件满足，Raft就可以完成选举和维持一个较为稳定的Leader状态：

广播时间 « 选举超时 « MTBF

广播时间：服务器同时向其他集群中的节点发送RPC请求并收到响应所用时间的平均值。一般为0.5ms到20ms之间，取决于存储技术（Raft的RPC需要保存信息到存储设备上） 选举超时：经过一段时间，Follower未收到从Leader发来的心跳报文，则这个时间即为选举超时时间，此后，Follower便会触发一个新一轮的选举。 MTBF：节点两个崩溃时间之间值的平均值。即节点某次崩溃与下次崩溃前所需时间的平均值。一般来说以月为单位

5. 集群成员变化（很迷）

例如替换掉崩溃掉的节点，采用手工的方式进行操作难免会有操作失误的时候。所以Raft采用了自动化的方式。

为了使集群配置（集群节点的个数）安全的变更，不能有两个节点同时被选为Leader。此外，也做不到在保证安全的情况下，各节点直接由旧集群配置变成新集群配置状态。各个节点会在不同时间进行切换，所以集群可能在配置过度的阶段分裂成两个独立的部分，如图10。

图10

在图10的例子中，集群的节点数从3变成5，在某个时间点，可能有两个Leader同时被选举出来，且任期相同。一个节点拥有大部分的C(old)集群配置信息，而另一个节点拥有大部分的C(new)集群配置信息。

为了确保安全的过度，变更需分为两个阶段：

  1. 集群首先切换到过渡配置阶段（叫联合共识joint consensus）；
  2. 联合共识被提交后集群系统切换到新的配置状态

此时联合共识包含新老两种配置

  • 日志信息会同步给所有节点中，新老集群配置都会同步
  • 新老集群配置中的任意一个节点都可以当Leader。
  • 共识（选举和日志提交）需要旧集群配置中的大多数和新集群配置中的大多数

联合共识允许节点在不同的时间加入且不会丧失安全性。此外也不会在配置变更期间影响客户端的服务。

集群配置通过特殊的log来进行变更。如图11，当Leader得到通知需要从C(old)配置状态更改为C(new)配置状态，它会将集群新C(old)配置状态保存起来（通过log）。一旦一个节点添加了C(new)集群配置信息到log中，那么今后它便会使用这个C(new)配置信息，不管该log是否被提交。这也就意味着Leader在C(old、new)配置提交后会同时使用C(old、new)配置。但如果这时候Leader崩溃了，新选中的Leader可以从C(old)和C(old、new)配置来进行选择，当然这取决于这个被选中的Leader是否已经拿到了C(old、new)配置信息。 在任何情况下，C(new)配置都不会单方面的做出决定。

一旦C(old、new)被提交,C(old)和C(new)做任何决定都需要其他节点的同意, Leader Completeness Property(LCP属性)确保只有拥有C(old、new)配置的节点才能被选举为Leader.

参考

https://developer.aliyun.com/article/11035?spm=a2c6h.13813017.content3.1.1c04323dv3RDy1