转载

State Machine Replication 技术和 PAXOS 算法

作者：刘秋杉 IBM Nov.23, 2015

State Machine Replication

分布式系统像一个社会，以社会的思维去运作，而如今我们正在为这个社会构建规则，并用这个社会来支撑我们的社会。为这些科学家和工程师点赞。

State Machine Replication是一项很有效的fault tolerance技术。在这个模型中，程序（比如一个apache server）被视为 deterministic state machine ，意思就是给程序一定顺序的 input requests ，程序执行后就会到达一定的状态（准确的说是数据结果），而replication就是在多个 nodes 中保持相同的state。当然这要求我们的SMR模型可以容忍来自node和network的failures，否则仅是理论上做到。自然我们就想到了大名鼎鼎的PAXOS算法，分布式系统的基石理论和协议，看似简单却不易实现，从理论的提出到首次实现竟然跨了十多个年头。关于PAXOS的详细细节和具体代码实现，大家可以参阅我的另一篇blog： PAXOS实现

关于SMR的“给予每个replicas的input request sequence一致，在deterministic execution的前提下，这些replicas就会 reach the same exact state”的内核，是从理论上证明了的，并且在实际应用中高可用。

SMR除了在fault tolerance领域备受青睐，在 dynamic program analysis frameworks 方面，也可以使用到它。大家先不妨想一个问题，既然SMR可以保证在多个replica nodes上保持 equivalent executions ，那在程序的analysis framework上，SMR可以带来哪些好处呢。首先得知道传统的analysis framework的bottlenect在哪里。

思考的同时，先来个小插曲，介绍一种先进的线程技术，DMT（ Deterministic Multithreading ）

DMT—— 来自美国Columbia University，如果给予每个replica nodes相同的input，在DMT的作用下，可以使得这些input的线程调度在每个nodes上都是一样的，这样就保证了即使在每个nodes上是多线程执行input，这些nodes最终的状态也是一致的，因为它们的线程调度是一致的。我们都知道多线程下程序会出现无法预测的状态，这是因为可以产生多种多样不可控的**thread

interleavings**。DMT通过维持一个logical

time（这个time是根据代码运行的先后来的）来让多个线程到达deterministic的效果，也就是说虽然看似多线程同时运行，但还是有一个logical

time在schedule它们。这项技术的overhead不是很高，大约是12.7%，这也是它的优势所在。

在SMR中，我们可以引入DMT技术。每个replica nodes会接收一致的socket operation（包含connect和send操作）序列，我们就以每个socket operation的return point作为logical time。这样的SMR系统，我们称之为M-SMR（Multi-threading State Machine Replication），因为可以进行多线程执行，而DMT的overhead又较低，因此M-SMR会获得比SMR更高的性能。

让我们回到SMR在analysis tool framework中的使用。传统的framework在运行程序的同时也会让analysis tool也运行，以便来采集程序的执行状态（如accessed memory和thread interleaving），这样就会slow down程序的执行。SMR可以提供同样程序的 multiple equivalent execution，这样的，我们就可以在一些replica nodes上运行analysis tools，而在另一些replica nodes上照常处理client请求而不slowdown。

但是挑战依然存在。一些异步analysis tool（如race detector）有时会回滚到前面的执行，我们既要做到roll back，也要做到让所有的replicas进行consistent的rollback。解决方法是，在SMR模型中，再引入一项fault tolerance的核心技术checkpoint mechanism，而这需要使用CRIU来实现。CRIU支持CPU寄存器，内存和网络的checkpoint。个人认为CRIU是目前最好最成熟的实现程序checkpoint/restore的开源技术（如今的CRIU可以支持Docker的live migration，不过依然存在practical问题）。

在framework中checkpoint也用来帮助synchronous analysis tools摆脱恶意event带来的阻碍。在SMR中，我们不必对PAXOS部分进行checkpoint，因为这部分是无状态的，我们仅需要对运行在replica nodes上的程序进行checkpoint。当analysis tool使用framework提供的checkpoint()功能时，PAXOS部分会向所有的replicas发起“请大家对最后的socket operation进行checkpoint”的提案。一旦提案获得批准，所有的replicas就会执行checkpoint。程序的状态就会被冰冻起来，成为历史档案，以后后来的查阅和恢复。

当analysis tool抓到一个恶意event，然后决定回滚到前面的checkpoint档案时，tool会调用rollback(index)功能。参数index可以指定回滚到具体的前面的哪一个档案。如果遇到恶意inputs，我们也可以在回滚的同时丢弃这些inputs。总之，让程序好好运行，让analysis tool好好运行，让需要rollback的tool可以rollback。

不过弊端显而易见，analysis tool需要调用framework提供的checkpoint API，not transparent。

瑕不掩瑜。SMR实际上是一个分布式系统，我们在利用tool采集性能信息时，可以让这个分布式系统分工协作，不如一台机器采集这个信息，另一台采集那个信息，大大提高效率，性能分析分布式化。而且SMR中有多个nodes，即使少数nodes出现故障，也不会妨碍其他nodes继续进行性能采集和分析。

最后，在SMR中我们可以在一个节点上运行一种tool，在另一个node上运行另外一种tool，而overhead不大，这就是同时运行多种analysis tool而没有大的overhead和slowdown。

analysis framework最好能做到analysis和execution的decouple，SMR是good choice。

总结：SMR进过几十年的发展，已经获得工业界和学术界的共同认可，并逐渐成为一种在云计算和分布式系统领域非常有力的fault-tolerance技术。一般SMR使用PAXOS算法作为一致性协议来保证所有nodes看到的是一样的input request sequence（nodes先“agree”一个total order的input request序列，然后“execute”）。SMR已经出现在工业界中了，像大家熟知的，大名鼎鼎的Google Chubby 和 ZooKeeper。一般SMR的场景并不针对各种各样的应用，都是针对某种特定的应用构建的SMR系统，像分布式锁服务。

PAXOS

下面是PAXOS在SMR中的实现细节，可能会有点晦涩，大家多担待:)

可以阅读另外两篇来辅助理解：

理解Paxos Made Practical
PAXOS实现

提案（proposal）是PAXOS算法一个重要的组成部分。先来看一下用于在分布式节点间传递提案（accept_req）的数据结构：

struct accept_req {  node_id_t node_id;  view_stamp msg_vs;  view_stamp req_canbe_exed; }; struct view_stamp {  view_id_t view_id;  req_id_t req_id; }; typedef uint32_t view_id_t;

对应它，我们还需要在节点上维护几个变量：

highest_committed_vs

highest_seen_vs

highest_to_commit_vs

我们的分布式系统使用的是三个节点，其中一个是leader，其余两个是secondary node。

highest_seen_vs表示该节点目前接收到的请求中提案号最大的。

在leader上，highest_seen_vs用于产生一个请求的 提案号 （也就是上面提到的view_stamp这个数据结构）：

view_stamp next = get_next_view_stamp(comp);  view_stamp_inc(comp->highest_seen_vs);

leader每从client接收一个请求（准确地说，应该是一个socket operation，包括connect, send, close三种），就将next与这个请求绑定，按照到来的顺序依次加1。leader节点上的highest_seen_vs可以代表目前已接收请求中编号最大的那个。在secondary节点上，highest_seen_vs的更新要根据来自leader的提案（一开始提到的accept_req）。这个提案代表一个请求，所以它包含这个请求的提案编号 msg_vs。当secondary节点接收到这个提案后，会将提案的msg_vs和这个节点上维护的highest_seen_vs进行比较，如果前者比后者大，就将后者更新为前者：

// update highest seen request if(view_stamp_comp(&msg->msg_vs,comp->highest_seen_vs)>0){     *(comp->highest_seen_vs) = msg->msg_vs; }

再回到leader上，看看这个提案是如何构造的。一个提案代表一个请求。通过上面的介绍，我们已经知道提案中的msg_vs就是leader分配给这个提案的编号，那req_canbe_exed代表什么呢？先介绍一下highest_to_commit_vs：

highest_to_commit_vs表示该节点即将要提交的请求。

提交请求指的是这个请求已经获得三个节点大多数（两个或三个节点）认可，可以把它提交给真正的服务器进行处理。这是PAXOS用来将一个请求在三个节点间达成一致的方式。

highest_committed_vs 表示已经提交的请求中最大编号。

也就是说，请求可以分成三种类型：已被接收但未被认可，已认可但未被提交，已提交。

再回到leader上的req_canbe_exed，在leader构造一个请求的提案时，有：

msg->req_canbe_exed.view_id = comp->highest_to_commit_vs->view_id; msg->req_canbe_exed.req_id = comp->highest_to_commit_vs->req_id;

可见req_canbe_exed传达的是leader节点上即将要提交的请求的提案号。当这个提案发给secondary节点时，secondary节点会把该提案中的req_canbe_exed与自身的highest_to_commit_vs进行比较，如果前者大，就将后者更新为前者：

if(view_stamp_comp(&msg->req_canbe_exed,  comp->highest_to_commit_vs)>0){  // 如果前者大于后者  *(comp->highest_to_commit_vs) = msg->req_canbe_exed;  SYS_LOG(comp,"Now Node %d Can Execute Request %u : %u ./n",  comp->node_id,  comp->highest_to_commit_vs->view_id,  comp->highest_to_commit_vs->req_id); }

可见，leader会和secondary节点时刻保持状态一致：leader更新了highest_seen_vs和highest_to_commit_vs，会通过发送给secondary节点的提案（accept_req）告诉secondary该更新了。

还有一个概念，先看一下figure：

State Machine Replication 技术和 PAXOS 算法

还剩下msg_vs到highest_committed_vs的箭头。下面将涉及PAXOS的核心思想。提案到达secondary节点后，该节点发现这个提案的编号小于或等于该节点已经提交的最大编号highest_committed_vs。这说明，这个新到的提案所代表的请求在该节点上已经被提交给真正服务器去处理了，此时该节点会忽略这个请求：

if(view_stamp_comp(&msg->msg_vs,comp->highest_committed_vs)<=0){ // we have committed the operation, safely ignore it     SYS_LOG(comp, "I've already committed the operation.                                I'll ignore this one./n");     goto handle_accept_req_exit; }

最后大家可以思考一下这个问题：

什么情况下会令secondary节点忽略来自leader的提案？