几天前更新的文章里降到了一致性算法，也详细地写了 Paxos 算法的内部原理，今天我们继续学习分布式一致性算法的其他两种，由于篇幅有限，所以一篇博客写一个算法。

关于 Raft 算法

Raft 是工程上使用较为广泛的强一致性、去中心化、高可用的分布式协议。在这里强调了是在工程上，因为在学术理论界，最耀眼的还是大名鼎鼎的 Paxos。

Paxos 算法是分布式系统领域最重要的一致性算法，同时也是公认的极为艰深难懂的算法。为了解决这个晦涩难懂的问题，斯坦福大学的Diego Ongaro、John Ousterhout教授以容易理解（Understandability）为目标设计了这个新的一致性算法：Raft，并在2013年发布了论文：《In Search of an Understandable Consensus Algorithm》。为了验证这个容易理解的特性，他们分别在斯坦福大学和加州大学伯克利分校的分布式计算课程上，使用了Raft和Paxos两种算法，采用视频教学的方式来传授给学生，之后采用小测验的方式来验证。结果表明 Raft 比 Paxos 容易理解很多。

Raft 和 Paxos 一样只要保证 n/2+1 节点（即超过半数节点）正常工作就能够提供服务。在设计层面，Raft 把算法流程分为三个子问题：领导选举（Leader election）、日志复制（Log replication）、安全性（Safety）。 Raft 开始时在集群中选举出 Leader 负责日志复制的管理，Leader 接受来自客户端的事务请求（日志），并将它们复制给集群的其他节点，然后负责通知集群中其他节点提交日志，Leader 负责保证其他节点与他的日志同步，当 Leader 宕机后集群其他节点会发起选举选出新的 Leader。

Raft 算法使用场景

一般用作两种场景：元数据管理：比如 etcd，特点是数据规模小，主要保证数据一致性和集群的高可用（Raft选主），所以一套 Raft 集群就够了，分布式数据库：这种会用 parttion group，每个 group 有一个 Raft 集群，当数据变大的时候会做拓展。

Raft只是个共识算法来保证数据的一致性，与数据库客户端、事务没有关系

算法基础

Reft 算法流程分为三个子问题：领导选举（Leader election）、日志复制（Log replication）、安全性（Safety）。

角色

  • 领导者 Leader：接收处理客户端请求、向 Follower 进行日志同步、同一时刻最多只能有一个可行的 Leader。
  • 追随者 Follower：接受并持久化 Leader 同步的日志，在 Leader 告之日志可以提交之后，提交日志，处在完全被动状态。
  • 候选人 Candidate：临时角色，处于 Leader 和 Follower 之间的暂时状态。

img

Raft算法中在任意时刻最多只有一个Leader，正常工作期间只有Leader和Followers。

状态转换

img

状态切换流程：

  1. Raft 刚启动的时候，所有节点初始状态都是 Follower
  2. 超时时间内如果没有收到 Leader 的请求，则转换为 Candidate 角色并发起 Leader 选举
  3. 如果 Candidate 收到了多数节点的选票则转换为 Leader
  4. 如果在发起选举期间发现已经有 Leader 了，或者收到更高任期的请求则转换为 Follower
  5. Leader 在收到更高任期的请求后转换为 Follower

任期

可以理解为是节点担任 Leader 职务的时间期限。

Raft 将时间划分为一个一个的任期（term），每个任期由单调递增的数字（人气编号）标识，工作期可长可短可能不存在。

任期时间 = 选举时间 + 正常运行时间

img

通信

Raft 中服务器节点之间通信通过两个 RPC 调用：

  • 请求投票 RequestVote：候选人(Candidate) 选举期间发起
  • 日志复制 AppendEntries：领导人(Leader)发起，用于复制 log 和发送心跳

img

Leader 选举

初始状态

初始状态时，每个节点的角色都是 Follower (跟随者)，Term 任期编号为 1 (假设任期编号从1开始)

img

不过这两种情况会触发选举：

  • Raft 初次启动时，不存在 Leader，这时候会触发 Leader 选举
  • Follower 在自己的超时时间内没有接收到 Leader 的心跳 heartBeat，触发选举超时，从而 Follower 的角色切换成 Candidate，Candidate 会发起选举

选举

既然有两种情况下会触发选举，一个是初次启动，一个是Leader故障未发送心跳给Follower，那么我们假设有五个节点，然后分别用图来看下是如何选举的！

初始启动时：

初次启动节点都是正常流程如下：

img

Leader 故障时：

Node2此时是Leader 节点，结果故障了，剩下四个节点参与选举：

img

当选条件

在一个任期（Term）内只可以投票给一个结点，得到超过半数的投票才可成为 Leader，从而保证了一个任期内只会有一个 Leader 产生。

日志同步

概括成一句话就是：保证Leader上日志能完全相同地复制到多台Follower服务器上。

OK！我们看下是如何进行同步的。

日志结构

Raft算法中，每个节点维护着一份日志，其中包含了系统中所有状态变更的记录，每一次状态变更被称为一个日志条目。

我们先看日志结构和右侧说明：

img

图中每个节点存储自己的日志副本(log[])，每条日志记录包含：

  • 索引 (log index)：记录在日志中的位置，是一个连续单调递增整数
  • 任期号 (term)：日志记录被创建时Leader的任期号，上图中有三个任期
  • 命令 (command)：客户端请求指定的、状态机需要执行的指令

执行流程

了解完日志结构后，我们来看日志是如何发起同步的。

日志持久化存储的条件

Follower节点必须先将记录安全写到磁盘，才能向Leader节点返回写入成功响应。

如果一条日志记录被存储在超过半数的节点上，我们认为该记录已提交(committed)——这是 Raft 非常重要的特性！如果一条记录已提交，意味着状态机可以安全地执行该记录

流程如下图：

img

  1. 客户端向 Leader 发送命令，希望该命令被所有状态机执行；
  2. Leader 先将该命令追加到自己的日志中；
  3. Leader 并行地向其它节点发送AppendEntries RPC，等待响应；
  4. 收到超过半数节点的响应，则认为新的日志记录是被提交的：
  5. Leader 将命令传给自己的状态机，然后向客户端返回响应
  6. 此外，一旦 Leader 知道一条记录被提交了，将在后续的AppendEntries RPC中通知已经提交记录的 Followers
  7. Follower 将已提交的命令传给自己的状态机
  8. 如果 Follower 宕机/超时：Leader 将反复尝试发送 RPC；

Leader 不必等待每个 Follower 做出响应，只需要超过半数的成功响应（确保日志记录已经存储在超过半数的节点上），一个很慢的节点不会使系统变慢，因为 Leader 不必等待。

一致性检查

Raft 通过 AppendEntries RPC 消息来检测。

  • 每个AppendEntries RPC包含新日志记录之前那条记录的索引 (prevLogIndex) 和任期 (prevTerm)；
  • Follower接收到消息后检查自己的 log index 、 term 与 prevLogIndex 、 prevTerm 进行匹配
  • 匹配成功则接收该记录，添加最新log，匹配失败则拒绝该消息

img

img

日志一致性

Raft算法的目的是保证所有节点的一致性，即一个日志条目在某个节点被提交，那么这个日志条目也必须在所有节点上被提交。

通过【一致性检查】就保证了日志一致性的这两点内容。

  • 如果两个节点的日志在相同的索引位置上的任期号相同，则认为他们具有一样的命令，从头到这个索引位置之间的日志完全相同
  • 如果给定的记录已提交，那么所有前面的记录也已提交

安全性

Raft增加了如下两条限制以保证安全性:

  • 拥有最新的已提交的 log entry 的 Follower才有资格成为Leader。

    这个保证是在 RequestVote RPC中做的，Candidate 在发送RequestVote RPC时，要带上自己的最后一条日志的term和log index，其他节点收到消息时，如果发现自己的日志比请求中携带的更新，则拒绝投票。日志比较的原则是，如果本地的最后一条log entry的term更大，则term大的更新，如果term一样大，则log index更大的更新。

  • Leader只能推进commit index来提交当前 term 的已经复制到大多数服务器上的日志，旧term日志的提交要等到提交当前term的日志来间接提交(log index 小于 commit index的日志被间接提交)。

之所以要这样，是因为可能会出现已提交的日志又被覆盖的情况:

img

在阶段a，term为2，S1是Leader，且S1写入日志(term, index)为(2, 2)，并且日志被同步写入了S2；

在阶段b，S1离线，触发一次新的选主，此时S5被选为新的 Leader，此时系统 term 为3，且写入了日志(term, index)为(3， 2);

S5尚未将日志推送到 Followers 就离线了，进而触发了一次新的选主，而之前离线的S1经过重新上线后被选中变成Leader，此时系统term为4，此时S1会将自己的日志同步到Followers，按照上图就是将日志(2， 2)同步到了S3，而此时由于该日志已经被同步到了多数节点(S1, S2, S3)，因此，此时日志(2，2)可以被提交了。；

在阶段d，S1又下线了，触发一次选主，而S5有可能被选为新的Leader(这是因为S5可以满足作为主的一切条件: 1. term = 5 > 4，2. 最新的日志为(3，2)，比大多数节点(如S2/S3/S4的日志都新)，然后S5会将自己的日志更新到Followers，于是S2、S3中已经被提交的日志(2，2)被截断了。

增加上述限制后，即使日志(2，2)已经被大多数节点(S1、S2、S3)确认了，但是它不能被提交，因为它是来自之前term(2)的日志，直到S1在当前term(4)产生的日志(4， 4)被大多数Followers确认，S1方可提交日志(4，4)这条日志，当然，根据Raft定义，(4，4)之前的所有日志也会被提交。此时即使S1再下线，重新选主时S5不可能成为Leader，因为它没有包含大多数节点已经拥有的日志(4，4)。

日志压缩

在实际的系统中，不能让日志无限增长，否则系统重启时需要花很长的时间进行回放，从而影响可用性。Raft采用对整个系统进行snapshot来解决，snapshot之前的日志都可以丢弃。

每个副本独立的对自己的系统状态进行snapshot，并且只能对已经提交的日志记录进行snapshot。

Snapshot中包含以下内容:

  • 日志元数据。最后一条已提交的 log entry的 log index和term。这两个值在snapshot之后的第一条log entry的AppendEntries RPC的完整性检查的时候会被用上。
  • 系统当前状态。

当Leader要发给某个日志落后太多的Follower的log entry被丢弃，Leader会将snapshot发给Follower。或者当新加进一台机器时，也会发送snapshot给它。发送snapshot使用InstalledSnapshot RPC。

做snapshot既不要做的太频繁，否则消耗磁盘带宽， 也不要做的太不频繁，否则一旦节点重启需要回放大量日志，影响可用性。推荐当日志达到某个固定的大小做一次snapshot。

做一次snapshot可能耗时过长，会影响正常日志同步。可以通过使用copy-on-write技术避免snapshot过程影响正常日志同步。

成员变更

成员变更是在集群运行过程中副本发生变化，如增加/减少副本数、节点替换等。

成员变更也是一个分布式一致性问题，既所有服务器对新成员达成一致。但是成员变更又有其特殊性，因为在成员变更的一致性达成的过程中，参与投票的进程会发生变化。

如果将成员变更当成一般的一致性问题，直接向Leader发送成员变更请求，Leader复制成员变更日志，达成多数派之后提交，各服务器提交成员变更日志后从旧成员配置(Cold)切换到新成员配置(Cnew)。

因为各个服务器提交成员变更日志的时刻可能不同，造成各个服务器从旧成员配置(Cold)切换到新成员配置(Cnew)的时刻不同。

成员变更不能影响服务的可用性，但是成员变更过程的某一时刻，可能出现在Cold和Cnew中同时存在两个不相交的多数派，进而可能选出两个Leader，形成不同的决议，破坏安全性。

img

由于成员变更的这一特殊性，成员变更不能当成一般的一致性问题去解决。

为了解决这一问题，Raft提出了两阶段的成员变更方法。集群先从旧成员配置Cold切换到一个过渡成员配置，称为共同一致(joint consensus)，共同一致是旧成员配置Cold和新成员配置Cnew的组合Cold U Cnew，一旦共同一致Cold U Cnew被提交，系统再切换到新成员配置Cnew。

img

Raft两阶段成员变更过程如下:

  • Leader收到成员变更请求从Cold切成Cnew；
  • eader在本地生成一个新的log entry，其内容是Cold∪Cnew，代表当前时刻新旧成员配置共存，写入本地日志，同时将该log entry复制至Cold∪Cnew中的所有副本。在此之后新的日志同步需要保证得到Cold和Cnew两个多数派的确认；
  • Follower收到Cold∪Cnew的log entry后更新本地日志，并且此时就以该配置作为自己的成员配置；
  • 如果Cold和Cnew中的两个多数派确认了Cold U Cnew这条日志，Leader就提交这条log entry；
  • 接下来Leader生成一条新的log entry，其内容是新成员配置Cnew，同样将该log entry写入本地日志，同时复制到Follower上；
  • Follower收到新成员配置Cnew后，将其写入日志，并且从此刻起，就以该配置作为自己的成员配置，并且如果发现自己不在Cnew这个成员配置中会自动退出；
  • Leader收到Cnew的多数派确认后，表示成员变更成功，后续的日志只要得到Cnew多数派确认即可。Leader给客户端回复成员变更执行成功。

异常分析:

  • 如果Leader的Cold U Cnew尚未推送到Follower，Leader就挂了，此后选出的新Leader并不包含这条日志，此时新Leader依然使用Cold作为自己的成员配置。
  • 如果Leader的Cold U Cnew推送到大部分的Follower后就挂了，此后选出的新Leader可能是Cold也可能是Cnew中的某个Follower。
  • 如果Leader在推送Cnew配置的过程中挂了，那么同样，新选出来的Leader可能是Cold也可能是Cnew中的某一个，此后客户端继续执行一次改变配置的命令即可。
  • 如果大多数的Follower确认了Cnew这个消息后，那么接下来即使Leader挂了，新选出来的Leader肯定位于Cnew中。
  • 两阶段成员变更比较通用且容易理解，但是实现比较复杂，同时两阶段的变更协议也会在一定程度上影响变更过程中的服务可用性，因此我们期望增强成员变更的限制，以简化操作流程。

两阶段成员变更，之所以分为两个阶段，是因为对Cold与Cnew的关系没有做任何假设，为了避免Cold和Cnew各自形成不相交的多数派选出两个Leader，才引入了两阶段方案。

如果增强成员变更的限制，假设Cold与Cnew任意的多数派交集不为空，这两个成员配置就无法各自形成多数派，那么成员变更方案就可能简化为一阶段。

那么如何限制Cold与Cnew，使之任意的多数派交集不为空呢? 方法就是每次成员变更只允许增加或删除一个成员。

可从数学上严格证明，只要每次只允许增加或删除一个成员，Cold与Cnew不可能形成两个不相交的多数派。

一阶段成员变更:

  • 成员变更限制每次只能增加或删除一个成员(如果要变更多个成员，连续变更多次)。
  • 成员变更由Leader发起，Cnew得到多数派确认后，返回客户端成员变更成功。
  • 一次成员变更成功前不允许开始下一次成员变更，因此新任Leader在开始提供服务前要将自己本地保存的最新成员配置重新投票形成多数派确认。
  • Leader只要开始同步新成员配置，即可开始使用新的成员配置进行日志同步。

Raft 和 Multi-Paxos对比

Raft与Multi-Paxos都是基于领导者的一致性算法，乍一看有很多地方相同，下面总结一下Raft与Multi-Paxos的异同。

Raft与Multi-Paxos中相似的概念:

img

Raft与Multi-Paxos的不同:

img

总结

没更新的几天去干嘛了，有在学习，只是没去学习全新的东西，回过头去看了看之前没注意的一些知识点，收获非常大。不过不打算写博客来记录了，学到最多的还是一些关于 Go 底层实现的一些东西，我也是在看别人写的书，没有什么实际收获，只是去理解了一下，所以觉得没有再写博客的必要。

学习使我快乐，学习使我快乐，学习是我快乐。幸亏最近几天有去做算法题，才不至于在做笔试的时候手忙脚乱的。老规矩，祝我面试顺利！！！