vlambda博客
学习文章列表

在网络时代，epoll以及基于epoll的网络框架通行天下，基于epoll封装的网络库或者框架大大减轻了程序员的工作量，程序员不需要太了解网络细节就能快速开发出一个高性能的满足业务要求的程序；在云时代，分布式、高可用成为基本要求，paxos、raft是通用的解决这一类问题的算法，需要熟练掌握。在这篇文章里，简单梳理下paxos、raft相关的流程以及知识点。

Mike Burrows, inventor of the Chubby service at Google, says that “there is only one consensus protocol, and that’s Paxos” – all other approaches are just broken versions of Paxos.

有大师曾经说过只有一个consensus protocol，所以在这篇文章里面paxos和raft一起来学习，看他们的相似与不同点。

一、多副本状态机

为了解决某个服务的单点问题，比如说一个kv的服务，单点部署的话，如果这个节点挂了，服务就不可用了。为了解决这个问题，之前传统上，一般是使用primary/backup的模式，比如说把服务部署到两个节点上，一个是主一个是从，主从之间同步或者异步的复制数据，这样当主挂了的时候，可以把服务切到从上(failover)，从就变成了主，继续提供服务。但这种primay/backup模式的一个核心缺点是无法处理脑裂的问题，主从数据的一致性也不好保证。一般primary/backup模式的服务，要么手动人工切换主从，要么依赖外部共享的存储或服务，比如说etcd/zookeeper啥的来决定哪个是主，进而规避脑裂的问题。

多副本状态机(State machine replication)也可以用来解决上述服务的单点问题，多副本状态机的核心思想是deterministic的状态机，输入同样的日志序列，状态机最终的状态是一样的，这样多个节点，每个节点保存一个副本的状态机，然后通过paxos或者raft等一致性consensus协议，协商出一个共同的日志序列，应用到每个副本的状态机上，最终状态机的状态也是一致的，这样就实现了一个高可用的服务。多副本状态机可以应对脑裂的问题，多副本状态机只要majority的节点能互相通信就能正常工作。

二、basic paxos

basic paxos用来在分布式环境中协商一个值，值协商确定之后，不会再发生变化。basic paxos协商一个值的过程是两个步骤，流程如下：

Phase 1. (a) A proposer selects a proposal number n and sends a prepare request with number n to a majority of acceptors.
(b) If an acceptor receives a prepare request with number n greater than that of any prepare request to which it has already responded, then it responds to the request with a promise not to accept any more proposals numbered less than n and with the highest-numbered proposal (if any) that it has accepted.
Phase 2. (a) If the proposer receives a response to its prepare requests (numbered n) from a majority of acceptors, then it sends an accept request to each of those acceptors for a proposal numbered n with a value v, where v is the value of the highest-numbered proposal among the responses, or is any value if the responses reported no proposals.
(b) If an acceptor receives an accept request for a proposal numbered n, it accepts the proposal unless it has already responded to a prepare request having a number greater than n.

上面的流程来自《paxos made simple》这篇paper。理解paxos的关键点是下面三点：

1. 提案编号(proposal number)：可以把提案编号看成是系统的逻辑时钟，只增不减，类似于raft中的term；

2. 什么时候什么条件下一个值被选中(chosen)：当一个值被majority的节点accept之后，这个值就被选中了(chosen)；

3. 安全性(safety)：paxos算法保证安全性(safety)，即一个值被选中之后，这个值就永远再也不会变化，后续的提案，选中的也会是同样的值。

paxos的第一步(Phase 1)是向系统中的所有节点发送一个prepare命令，告诉所有接受到prepare请求的节点，在我这个提案编号之前的所有请求都不要再管了哈，同时把你们之前已经accepted的最新的值告诉我；paxos的第二步(Phase 2)，就是把第一步中学习到的系统中已经accepted的最新的值（如果这个值不存在的话，可以指定成任意的值），然后把这个值发给所有的节点，让他们接受。majority的节点接受了这个值之后，paxos流程完毕，这个值就不会再发生变化。

假设某个值被选中之后，后续的任意的节点再propose的时候，在第一步的时候，肯定可以学习到这个值，然后再用这个值走paxos流程，paxos流程走完之后，协商出来的还是同样的值，保证了paxos算法的安全性(safety)。

basic paxos算法整个过程还是比较清晰易懂显而易见的，第一步prepare阶段的请求，如果被majority的接受的话，由于majority的节点已经承诺不再接受更老逻辑时钟之前的请求了，这样在这个逻辑时钟之前的状态就固定不会再有变化了。比如说如果某个节点提交了一个提案编号为10的prepare请求，并且被majority的节点返回了prepare的response，那么在10之前的那些提案要么已经被chosen，要么永远再也不会被chosen了。如果10之前的提案已经被chosen的话，逻辑时钟为10的这个prepare过程一定可以学习到，然后再用学习到的这个值来进行第二个步骤，然后其他的majority来接受（注意第一步的majority和第二步的majority可以不是同一个集合），这样就保证了paxos算法的安全性(safety)。

举个例子，如上图5个节点组成的集群，节点A发起了提案编号为10的提案：
第一步：发prepare请求给所有的节点，如果B和C响应了这个prepare请求做了promise承诺之后，再加上A，一共3个节点响应了prepare请求，满足majority的要求；这样会造成一个结果就是10之前的提案就已经固定了，比如说如果提案编号为9的提案还没有被选中，就再也不会被选中了，因为选中需要majority的节点来accept，而A、B、C都承诺不会accept了；另外如果之前的某个提案已经选中了一个值，那个这个值A、B、C中肯定至少有一个节点有这个值，所以A一定能学习到这个值；
第二步：A用第一步学习到的值（如果没有学习到值，可以取任意的值），让所有的节点来accept，如上图中的例子，D和E accept了这个值，再加上A，也满足了majority的条件，这样这个值就被选中。值被选中了之后就再也不会被改变了，因为后续的节点提提案的时候，在第一步从majority的节点中一定可以学习到这个值。

三、paxos和FLP

No determinstic algorithm for solving consensus in an asynchronous network is both safe (corrent) and live (terminates eventually)

FLP定理是说在分布式异步网络环境下，协商确定一个值，没有算法即安全正确，又能正常终止。在paxos中很容易构造一个场景，让paxos协商值的过程变成活锁，永远无法终止。比如说：节点A用10的提案编号给所有的节点发prepare请求，然后节点B用11的提案编号给所有的节点发prepare请求，然后A再去发accept指令的时候，会发现当前系统的时钟已经到11了，没有节点响应他的请求了，因此他只能用12的提案编号重新开始paxos的流程，发送prepare请求，然后节点B要发accept的时候，也看到系统的整体时钟已经到了12，没有节点响应他的请求了，他因此把提案编号增大成13，然后继续paxos的流程，一直这些循环往复，导致paxos无法进行下去。

paxos算法在任何情况下都保证了safety安全性，但是不保证liveness。liveness的问题一般都是用随机化的方法来规避，通过随机化让冲突发生的概率很低很低，即使发生了冲突，再随机化重试即可规避。

四、用paxos协商一个序列的值

朴素的paxos算法流程只协商确定了一个值，而多副本的状态机模型是要协商确定一个序列的值。要提交一个序列的值，一般都是先选一个主，然后由主来统一提交日志。一种方式是序列的每个值(log entry)都走一个单独的paxos流程：如上图所示，A提交了一个编号为10的提案协商达成一个log index为0的log entry之后，可以再按照paxos的步骤，继续用10为编号，协商log index为1的第二个log entry，流程和第一个类似，每个log entry的协商都是独立的paxos实例。

另外，可以把多个paxos实例的第一步的流程合并，比如说：第一步某个节点选取一个提案编号逻辑时钟，发给系统中的所有节点prepare，告诉他们不要再接收老的消息了，同时把两个槽位的accepted值返回；这样在一个步骤里面就可以prepare多个paxos实例，完成了多个paxos实例的第一步骤，然后这个节点后续收到client发的请求后，选择空闲的槽位，让所有节点accpet这个槽位的值就可以了。因为针对这个槽位来说，这个槽位的paxos实例的第一步已经完成过了。

从上面的流程可以看到，paxos算法只是从整体宏观上来讲，如何协商一个log entry，以及在此之上实现多副本状态机的大体流程，但其他部分都讲的很不详细，可以说paxos只是相当于一个项目的可行性分析，和工程实现差距非常大。

五、raft基本算法流程

raft为了实现多副本状态机，对比paxos，采用了一种不同的方式：raft为了可理解性来设计。raft把实现多副本状态机这个问题拆成了多个子问题(decomposition)，分别是选主(leader election)、日志复制(log replication)和安全性(safety)。

raft集群一般有奇数个节点组成，第一步是先选主，所有的写入操作都通过leader来进行，如果请求发到follower，由follower转发到leader，或者follower告诉leader的位置，然后client重连；每个leader都一个term，每个term里也最多只有一个leader，有的term可能没有leader，由于没有选到主。raft的日志log entry只会从主向follower流动，raft通过限制含有最长日志的节点才能被选成主，来保证安全性。另外raft专门为了可理解性来设计，节点只有follower、candidate、leader三种状态、日志只会从leader向follower流动，通过随机化的方式来选主，只有2个核心RPC等手段来降低复杂性。另外raft的RPC是幂等的(idempotent)（思考：什么是幂等操作，本质是什么？对所有的x，如果y=f(x)=f(f(x))，则f操作是幂等的）。

raft算法流程演示：
http://thesecretlivesofdata.com/raft/

raft选主(leader election)

如上图所示，所有节点一起动的时候，就是follower状态，然后有election timeout，超过了election timeout之后，进入candidate状态，发起选主的流程。raft选主有几个特点：每个term最多只有一个leader，有的term可能没有leader；为了应对split vote的问题，加快选主的速度，使用随机化的方法。

日志复制(log replication)

raft的日志复制是通过AppendEntries这个rpc接口来实现的，raft的日志只从leader向follower流动，日志以leader的为准，如果follower与主不一致的话，会用主的覆盖本地的日志。appendEntry这个rpc接口实现了Log Matching Property的特性：

log matching: if two logs contain an entry with the same index and term, then the logs are identical in all entries up through the given index.

安全性(safety)

Election Safety: at most one leader can be elected in a given term.
Leader Append-Only: a leader never overwrites or deletes entries in its log; it only appends new entries.
Log Matching: if two logs contain an entry with the same index and term, then the logs are identical in all entries up through the given index.
Leader Completeness: if a log entry is committed in a given term, then that entry will be present in the logs of the leaders for all higher-numbered terms.
State Machine Safety: if a server has applied a log entry at a given index to its state machine, no other server will ever apply a different log entry for the same index.

Election Safety: 一个term逻辑时钟里只会有一个leader，并且在选主的时候有限制，只有日志最长的节点才有可能被选成主，通过这种限制，其实是可以和paxos做对比，由于leader含有最长的日志，所以相当于paxos的第一个步骤就不需要；或者说paxos的第一个步骤就类似于raft的选主，只是raft限制主的数据最新，paxos则是通过学习通过数据拷贝的方式，来保证发起提案的节点有最新的数据。

Leader Append-Only: 所有的写入请求都是经过leader；

Log Matching: 日志从leader向follower单向流程，并且以leader的日志为准。

State Machine Safety是说如果一个log entry被applied，这个log entry就不会再变，这个safety其实和paxos的safety是一致的。

为了理解raft的安全性，这里学习下paper中的一个例子：

上图是一个时间序列来说明为什么主不能用之前的term来提交日志。在(a)中term 2的时候，S1是leader，并且部分复制了日志；在(b)中term 3的时候，S5通过S3、S4和S5的投票选成了主，然后只写了本地的的log entry还没有来得及复制S5就挂了；在(c)中term 4的时候，S1成为了leader(可能是来自S1、S2、S3的投票)，然后S1发现之前term 2的时候有条日志还没有commit，因此他把这条日志复制到大多数节点(S1、S2、S3)之后commit了这条日志；在(d)中会发现，S1挂掉之后S5可以重新被选为leader(可能是来自S3、S4、S5的投票)，然后S5就会把(c)中S1 commit的日志给刷掉。这个例子说明了在(c)中，S1不能一共之前的term来提交日志，这样是不安全的。正确的行为，应该是按照(e)中所示，用S1自己的term来顺带提交之前的日志。只有用最新的term提交日志，才能保证安全。

To eliminate problems like the one in Figure 8, Raft never commits log entries from previous terms by counting replicas. Only log entries from the leader’s current term are committed by counting replicas; once an entry from the current term has been committed in this way, then all prior entries are committed indirectly because of the Log Matching Property.

对比paxos，paxos第一步骤也是只学习值，然后用自己的提案编号来让大家accept。

六、raft与FLP

raft类似于paxos在任何情况下都保证safety，但不保证liveness，主要体现在选主上(split vote)，也是通过随机化的方式来解决。

七、paxos和raft对比分析

paxos比较宏观、raft比较细致。
paxos类似一个项目可行性设计、raft类似于详细设计。
paxos两个步骤，第一个步骤通过学习的方式来copy最新的数据，然后用自己的提案编号来提交、raft通过限制日志最长的节点才能成为主，来保证数据最新，也是通过leader的term来提交所有的日志。

八、raft集群增删节点

raft集群如何来安全的增删节点，比如说原来3个节点，要增加2个变成5个，怎么样做才安全呢？下面是一个反例：

如上图所示，直接从3个节点变成5个节点的话，如果中间发生了脑裂，有可能Server 1、Server 2组成了一个集群，然后Server 3、Server 4、Server 5组成了另外一个集群，导致产生两个leader。

正确的方式是，通过一个joint concensus来解决，先从Cold到Cold,new再到Cnew，保证任意时刻只会有一个leader。Cold，new这个表示的含义是，在这个节点配置的情况下，协议的达成同时需要Cold里面的majority同意和Cnew里面的majority也同意。

Once a given server adds the new configuration entry to its log, it uses that configuration for all future decisions (a server always uses the latest configuration in its log, regardless of whether the entry is committed).

思考：为什么cluster membership changes的日志，follower不需要管有没有提交(committed)？

raft里面的safety指的是状态机的safety，cluster membership changes要保证任意时刻只会有一个leader；Cluster membership changes 的log entry并不会应用到状态机里面，不是状态机的流程；这个log entry只是为了修改集群的配置，这个cluter membership changes只是顺便走的appendEntry的通道，复用的协议，这里要注意区分清楚。

九、raft常见优化方法

prevote解决异常节点对集群可用性的干扰

如上图所示A、B、C三个节点组成的集群，如果发生了脑裂C于A、B不通的话，A、B两个节点可以正常提供对外的服务，而C由于不能收到集群leader的心跳，将进入candidate状态，增加term，然后开始选主，然后选不上，再增加term，重新开始选主。。。然后就这样term会一直增加，直到网络恢复。网络恢复的时候，由于节点C的term比较大，A、B节点比它大的term的时候，会把自己的term置成最新的，然后进入follower状态，然后等待election timeout。节点C由于日志比较短，不可能被选成主，主只能在A和B中产生。A和B的election timeout触发之后，开始选主。可以看到，一个网络异常的节点在重新加入集群之后，会导致集群的波动，影响集群的可用性。

为了解决这个问题，在选主的时候，增加prevote的流程，在prevote阶段，先预投票，看自己能否有可能被选成主，只有在可能被选成主的情况下，在真正增加term，开始真正的选主的流程。

日志提交流程优化

raft日志提交流程常见的有batching和pipeline两种优化方法。

batching: 一个常见的优化方式是batching，把client提交过来的请求攒一攒，一起走raft的流程，提升整体的吞吐。

pipeline: raft的提交日志的流程大体上分为如下的步骤：
(a)、leader收到client的请求；
(b)、leader追加请求的log entry到本地日志；
(c)、leader把请求的log entry复制到followers，导致follower把log entry分别追加到他们的本地日志；
(d)、leader等待所有的followers返回，如果majority的节点返回成功，leader提交这个日志，并且把日志应用到状态机里；
(e)、leader把结果发给client，然后再继续处理后续的请求。

应用pipeline上述步骤可优化成：

(a)、leader收到client的请求；
(b)、leader追加请求的log entry到本地日志，同时并行的给follower复制日志；
(c)、leader继续接受新的请求，并重复(b)；
(d)、leader收到follower的返回，满足majority的条件之后，commit这个log entry，然后异步的在另外的一个线程里面apply应用到状态机里面；
(e)、leader把结果发给client。

十、线性一致性

线性一致性的定义如下：

If operation B started after operation A successfully completed, then operation B must see the the system in the same state as it was on completion of operation A, or a newer state.

线性一致性用一句话来概括就是：所有的事件可以按照时间的先后顺序连成一条线。

举例：

如上图所示，bal原始的值是1，然后set bal=2的请求把这个值设置成了2，在t4之后，如果有请求来获取bal的值，读取到的是2的话，说明是线性一致性的；另外，如果t2到t3的请求读到的bal的值也是2的话，那么在t3之后发起的请求，读取到的bal的值也至少是2。

下面是一个反例，不满足线性一致性的要求(这个例子来自于：https://martin.kleppmann.com/2015/05/11/please-stop-calling-databases-cp-or-ap.html)：

如上图，Alice已经看到了Germany赢了世界杯，但是在这个之后开始的请求，看到比赛还在进行，这两个事件没办法按照时间的顺序来连成一条线，因此不符合线性一致性的要求。

思考：线性一致性和强一致性的区别？
线性一致性只保证事件的先后顺序，不管事务呀、读写冲突啥的。

十一、常见的实现线性一致性的几种方法

基于raft实现线性一致性常见的有如下几种方法：
read index: leader收到读请求之后，记录当前的commit index为read index，然后给所有的follower发送心跳保证自己的权威，然后等待read index应用到状态机之后，读取状态机的内容返回给client。这种方法核心有下面几点：1、read index等于commit index，确保能读到最新commit的数据；2、要确保自己还是主(说明数据最新，不会返回老的状态数据)；3、状态机可能是异步apply的，要等待read commit都apply到状态机之后再返回。

lease read: lease租约是一个协议，大家约定好，在lease租约时间的范围内，保证leader不会发生变化。

follower read: follower收到client的请求后，向leader请求commit index，本地的apply index大于commit index就可以了。(本地的状态机可能不是最新的，但这没关系，不会违背线性一致性，只要状态机比这个请求的开始的时间新可以)。

思考：为什么不能直接读leader的状态机然后返回client的请求呢？

十二、raft与CAP

Please stop calling databases CP or AP
https://martin.kleppmann.com/2015/05/11/please-stop-calling-databases-cp-or-ap.html

主要的原因在于CAP中的A指的是100% availability。

参考资料

Paxos Made Simple
TiDB: A Raft-based HTAP Database
In Search of an Understandable Consensus Algorithm (Extended Version)
CONSENSUS: BRIDGING THEORY AND PRACTICE
https://martin.kleppmann.com/2015/05/11/please-stop-calling-databases-cp-or-ap.html
http://thesecretlivesofdata.com/raft/