从paxos到raft

详细学习了一下分布式领域的paxos算法和raft算法，下面分别阐述。

需要解决的问题

为了让系统具有高可用性，出现了分布式系统，但分布式系统的一致性是个很难解决的问题，而这两个算法都是分布式领域的共识算法，以让整个系统保持强一致性。

Paxos算法

paxos算法是最早提出的共识算法，后面的算法也大多都是根据paxos算法演变而来。

paxos算法将系统中的角色分为了三种：

• proposer
• acceptor
• leaner

其中，proposer提出proposal，发送给acceptor，acceptor接受后完成共识，然后leaner进行学习。

推导过程

paxos的推导过程基本是以提出问题->解决方案(优化算法)的结构进行的，到最后，会呈现完整的paxos算法，所以本文也会根据这样的结构来进行。

Part1

当前结构

首先考虑单点系统，只有一个acceptor，一个proposer提出proposal，发送给acceptor，acceptor接受后完成共识。

问题

如果该acceptor发生故障，那么整个系统都无法正常运行，很显然，单点的acceptor无法满足需求。

Part2

当前结构

为了解决上述问题，考虑多acceptor系统，proposer提出proposal，交给一组acceptor，如果proposal被大多数acceptor接受，则完成共识，通过该proposal，如果有acceptor发生故障，也不影响整个系统的运行。很显然，目前的架构解决了上述的问题。

为了满足以上功能，对于acceptor来说，则有以下需求：

P1. An acceptor must accept the first proposal that it receives.

问题

考虑以上需求，存在问题，在多proposer的情况下，可能会存在同一时间多个proposal同时被提出的情况，根据P1需求，acceptor会同意自己收到的第一个proposal，这样有可能会导致没有大多数的accept的情况出现，导致proposal全部失败。

Part3

当前结构

为了解决上述问题，现在在每个proposal中增加一个编号，并提出以下需求：

P2. If a proposal with value v is chosen, then every higher-numbered proposal that is chosen has value v.

这个需求保证了如果一个proposal被接受，那么后续被接受的proposal中的v都一致，解决了可能出现没有大多数被接受的问题。

如果要求proposal被chosen，那么首先得被accepted，那么，再提出以下需求：

P2a: If a proposal with value v is chosen, then every higher-numbered proposal accepted by any acceptor has value v.

和P2不同的是，P2a需求细化到了accepted，只有先accepted，才能被chosen。

问题

考虑P1，一个从来没有accept过proposal的acceptor必须接受收到的第一个proposal，再考虑P2a，很显然存在矛盾。

Part4

当前结构

为了避免acceptor遇到上述问题，则从proposer处就要杜绝该问题，那么提出以下需求：

P2b: If a proposal with value v is chosen, then every higher-numbered proposal issued by any proposer has value v.

换种思路，如果一个proposal被提出，其value为v，number为n，那么一定有一个由大多数acceptors组成的集合，满足下面需求：

P2c: (a) no acceptor in S has accepted any proposal numbered less than n, OR (b) v is the value of the highest-numbered proposal among all proposals numbered less than n accepted by the acceptors in S .

怎么保证P2c条件呢，paxos算法采用一种promise机制来实现，即，在proposer提出proposal前，先发送一个repare request，用来得到acceptor的promise：

• acceptor不再接受number小于n的proposal
• 其已经接受的最大的proposal的number小于n

如果proposer收到大多数acceptors的答复，那么proposer就可以提出用number n和value v提出proposal，其中v是所有答复中number最大的proposal的value，如果没有这个值，那么value可以随意指定。这称为accept request。

以上都是站在proposer的角度来说的，那么站在acceptor的角度：

P1a: An acceptor can accept a proposal numbered n iff it has not responded to a prepare request having a number greater than n.

为了完成上述行为，acceptor必须记住自己accept的最大的number以及已经respond prepare的最大的number。

综上，可以得到paxos算法的流程：

• Phase 1
  • 一个proposer提出一个number为n的proposal并发送prepare request给大多数的acceptor
  • 如果acceptor收到的prepare request中的number大于其已响应的任何prepare request的number，则响应当前请求，并进行承诺
• Phase 2
  • 如果一个proposer收到大多数acceptor对于自己number为n的prepare request的答复，就发送accept request给每个答复的acceptor，number为n，value为v，其中v是答复中number最大的proposal的value，如果没有，则该值可任意指定
  • 如果一个acceptor收到一个number为n的accept request，除非已经响应过number大于n的prepare request，否则将接受该proposal

对于leaner，论文提出了一些参考的学习方案，可以是选出一些distinguished leaner，组成set，然后当acceptor接受proposal时，向leaner报告，由leaner判断是否为大多数accept，从而进行学习。

问题

考虑上述流程，存在这样一个问题，如果有两个proposer，称为a和b，进行下述流程：

1. a发布一个number为n的proposal，先发送prepare request给acceptor，acceptor表示接受，等待accept request
2. b发布一个number为n+1的proposal，先发送prepare request给acceptor，由于此时number大于n，所以acceptor接受并进行承诺
3. a发现acceptor不接受自己的number为n的proposal，就发布一个number为n+2的prepare request
4. …

可以发现，这样的流程可能会一直持续下去，这就是原始paxos算法的活锁问题。

Part 5

针对上述问题，paxos算法存在mutil-paxos版本，来解决这个问题，即在proposer中选出一个leader，raft算法就是根据此思想演变而来。

Raft算法

相比于paxos算法，raft算法设计的初衷就是易于教学，易于理解，易于实现。

Raft算法将算法拆分为下面几个部分：

• leader election
• log replication
• safety

Raft算法将系统中的角色分为三种：

• leader（每个系统只存在一个leader）
• follower（不主动发出请求，只是简单回应请求）
• candidate（当leader挂掉时会有follower转为candidate状态竞选leader）

算法流程

Term

term的概念在Raft算法中非常重要，Raft将时间分为一段一段的term，每段term可以是任意长的时间，但都以leader竞选开始。

如下图所示：

系统中的每台server都会存储一个current term，该编号随着时间单调增加，只要server之间通信，就会交换该值，较小的则会更新自己的term，如果leader或者candidate发现自己的term过时，则会恢复成follower状态，如果server收到一个带有过时term的请求，则会拒绝请求。

Leader Election

Raft算法使用heartbeat机制来触发leader选举，当server启动时，默认都为follower。只要server从leader或者candidate处收到rpc，则保持follower状态，一段election timeout时间内没有收到rpc消息，则会转变为candidate状态并进行leader选举，所以作为leader需要定时给follower发送heartbeat。

在进行leader选举时，follower增加当前的current term，然后转变为candidate状态，并发送rpc给别的server，直到（1）赢得选举，（2）另外一个server成为leader，（3）一段时间没有server赢得选举；三种情况下这一次竞选活动结束。

投票机制是first-come-first-served，对于（1）的情况，candidate成为leader，发送rpc心跳给别的server，以让他们转为follower状态；对于（2）的情况，在等待投票时，可能收到另外一个声称自己是leader的server的心跳rpc，如果其term不小于当前自己的term，则自己转为follower状态；对于（3）的情况，所有的candidate都需要暂停选举过程，增加自己的term，等待150-300ms的随机时间进行新一轮选举。

Log Replication

整个系统，由leader与client进行交互，当client发送request，可能是set 5，等等，称为日志，leader会将日志以rpc的形式发送给follower，如果大多数follower成功收到，则leader向client返回该request的状态，否则将一直进行重试，直到所有follower成功收到。

关于log entry的提交，具体的提交过程为：

• client发送请求给leader，leader收到后添加到自己的日志中，此时为uncommitted状态，所以还不能通过这个log来执行具体操作比如更改值
• leader将其通过rpc的方式发送给follower，如果收到大部分follower的回复，leader将其置为committed状态，并完成操作，然后返回给client
• 然后leader在下一次心跳rpc通知follower该log entry已经提交
• 共识完成

如图所示，每个log都包含一个编号，这个编号是非常重要的：

Raft算法保证log的顺序，如果两个log完全一致，那么该日志前面的序列也完全一致。如何保证该特性，Raft算法通过consistency check来完成，当leader发送rpc增加日志时，会发送当前最新的log的term，index，follower收到后，如果在自己的序列中没有找到对应log，则拒绝这次rpc。

问题

理想状态下，leader每次增加日志的rpc都被follower接受，系统不会出现问题，但是如果leader崩溃，可能有log没有发送给follower，而此时follower进行竞选成为新一任leader，可能会造成一些log的丢失。

解决方案

在Raft算法中，leader通过强行复制自己的log到follower上来解决这个问题，leader会维护一个nextIndex，表示下一个要发送的log的index是什么，考虑上述故障情况，如果在进行rpc时，发现follower的日志与leader的日志不一致，一致性检查会失败，leader将自己的nextIndex递减，再次进行此过程，直到成功，成功时，follwer删除所有冲突的日志，在这个term内，follower都将与leader保持一致。

Safety

选举限制

问题

考虑这样一个问题，有可能一个日志很残缺的follower赢得选举，成为新一任leader，然后强行同步自己的日志，如果该follower缺失某些被大多数follower通过的日志，那么系统将出现问题。

解决方案

为了解决这个问题，Raft规定candidate的日志必须包含大多数follower的日志，如果follower发现本身的log比当前发送rpc的candidate的log更新，则拒绝投票。

提交以前任期内的log

问题

考虑一个问题，如下图：

（S1-S5代表server，颜色代表日志，方块内数字代表term）

1. 在a阶段，S1是leader，收到一个log，将其复制到S2中后宕机
2. 在b阶段，S5凭借S3，S4以及自己的选票当选leader，此时term为3，随后宕机
3. 在c阶段，S1凭借S2，S3以及自身的选票当选leader，此时term为4，但如果允许提交以前任期的log，就会以term为2提交黄色log到S3中，考虑此时发生宕机
4. 在d阶段，S5凭借S2，S3，S4以及自身票数当选leader，随后同步自身状态到别的follower中

在上述流程中，黄色方块的log被覆盖了，违背了安全性原则。

解决方案

Raft算法从不通过计算副本来提交以前任期的log，只提交当前任期的log，考虑上述流程，如下图：

在c阶段，S1为leader，不主动提交以前任期的log，即黄色方块，而是在提交当前任期的红色方块的时候，顺带复制以前任期的log，以达到e阶段的效果，可以是当选后立即同步一条空操作log。

集群成员变更

很多时候，需要对整个集群进行配置变更，比如添加server等。

问题

考虑这样一个问题，添加server从3台到5台，配置变更后，在某时间点，可能存在两个leader，这是分布式领域的脑裂问题。

解决方案

Raft算法采用了一种两阶段的方法，集群先切换到一个过渡的配置称为joint consensus，首先leader发起$C_{old,new}$，使整个集群进入joint consensus状态，这时，所有rpc都要在新旧两个配置中都达到大多数才算成功；然后，leader发起$C_{new}$，使整个集群进入新配置状态，配置切换过程结束。

日志压缩

Raft使用快照来进行日志压缩，如果一个follower落后leader很多，leader的同步日志方式是直接向follower发送自己的快照。

参考文献

[1] LamportL.PaxosmadesimpleJ.ACMSIGACTNews(DistributedComputingColumn)32,4(WholeNumber121,December2001),2001:51-58.

[2] Ongaro D, Ousterhout J. In search of an understandable consensus algorithm[C]//2014 USENIX Annual Technical Conference (Usenix ATC 14). 2014: 305-319.

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

[4] http://thesecretlivesofdata.com/raft/

[5] https://raft.github.io/