本文来自论文：Paxos Made Practical

Paxos在实现上有三步：

1）proposer S1 选择一个提案编号n，这个编号要包含提议者机器的唯一标识，这样两个不同的机器就不会有相同的提案编号。proposer将信息PREPARE(n)广播出去。收到这个信息的机器会要么拒绝（已经收到大于n的PREPARE信息），要么回复PREPARE-RESULT(n‘, v‘)（已经收到的信息最大编号n‘ < n，且value为v‘），要么回复PREPARE-RESULT(0, nil)（该机器在收到这个信息之前没有收到任何提议）。如果多数派接受这个PREPARE信息，提案者进入第二步。

2）如果回复的是PREPARE-RESULT(n‘, v‘)，S1将提案的value设置成v‘；如果回复的是PREPARE-RESULT(0, nil)，那么value可以随便定。然后提案者S1会广播信息PROPOSE(n, v)，跟第一步一样，收到这个信息的机器要么拒绝（已经收到信息PREPARE(n‘‘)，其中n‘‘ > n），要么接受。

3）如果多数派（包括提案者）接受这个PROPOSE信息，提案者S1会广播DECIDE(n, v)来表示group已经在这个提议上达成一致。

其实这里有个问题，在fault-tolerant系统里，新机器来旧机器去。这样我们之前所提的多数派是指旧的机器集，还是新的机器集，还是两者都包含？ 新的集合是如何保证安全的？ 如果机器出错了，并且没有新的机器收到DECIDE信息该怎么办？

在介绍使用Paxos算法的论文中，有一篇是Viewstamped Replication，但是它有两个问题：1）很难搞懂如何去复制一个简单的系统：2）它假设机器集是固定的，未考虑动态的加入和退出。接下来我们的论文就是要详细阐述如何使用Paoxs，并去解决Viewstamoed Replication的局限。

首先我们来看一下状态机，在这里它是确定性的（deterministic），所以如果有两个相同的状态机从一个相同的初始状态开始，并接受相同的请求序列，那么他们就会生成相同的回复。一个复制系统要有两套库，服务端的和客户端的。在服务端提供三个函数：

id_t  newgroup (char *path);

id_t  joingroup (id_t group, char *path);

int  run (char *path, sockaddr *other_cohort, buf (*execute) (buf));

newgroup函数用来创建状态机。如果想加入一个组，就调用joingroup。run的第三个参数execute就是状态机的实现。

在客户端会有一个与execute相对应的函数invoke：

buf  invoke (id_t group, sockaddr *cohort, buf request);

一般借助RPC来实现execute。不幸的是，并不是所有的RPC服务器都是确定性的。例如，当文件服务器收到写文件请求，它就会设置文件节点的修改时间，这样即使两台机器运行同样的文件服务器代码，并实行同样的写请求，然而最终它们在这个相同的写操作上却具有不同的时间值，于是就出现了分歧状态。我们可以这样来解决：让一台机器去定下这个不确定的时间值，然后再让其他机器按照这台机器的标准去执行。为此我们引进一个新的函数choose：

buf choose (buf request);

它联合新的execute函数：

buf  execute (buf request, buf extra);

在我们这个文件服务例子中，首先让一台机器执行choose，选出一个修改时间，放入buffer中，choose函数返回这个buffer，之后执行execute，它的第二个参数extra就是buffer中的内容（即修改时间）。也就是说，对一个请求，先调用choose，在一台机器上选出那些会引起分歧的值作为结果返回，之后便将这个结果广播给其他机器作为execute的参数去执行，这样便做到了一致性。

?Normal-case operation

在服务器组中有一台机器是primary，而其它的都标记为backup，术语view用来表示一个有着指定primary的处于活动中的cohort的集合（cohort是指机器组中的一台机器），我们的系统为每一个view分配一个独一无二的view-id，每当发生view changes（即生成新的view），view-id都会自动增加。先来看一个流程图：

Client发送请求给primary，primary会记录请求，并将请求广播给其它的backups，backups记录操作OP并给primary返回一个确认信息。如果primary知道多数派（包括它自己）都已经记录了操作OP，它会执行操作OP，并将结果返回给client。下面详细谈一下：

在开始发送请求前，client一定要知道服务器组当前的primary和view-id，要知道这些信息需要client知道服务器组中每一个cohort的身份，这里不做讨论。下面是client发送给primary的请求：

这里看一看vid，它是当前cohort集的view-id，它的存在是为了当发生view changes时，避免新的primary重新执行该请求。Primary在接受到请求后，会给每个请求附一个时间戳，到时在一个view中的请求序列就按时间的先后依次执行。如果将view-id和时间戳结合成viewstamp就能给所有请求（不论是否在一个view）标记执行顺序。在primary发给backups的信息replicate_arg中，会存在这个viewstamp用来标识这个请求的执行顺序，此外还有一个viewstamp叫committed，比它小的viewstamp，都已经执行完请求并返回给clients，这样当primary返回给client的信息丢失或primary突然出故障时，只需从committed之后开始重新执行。

Backups会记录下primary发过来的请求，而之前我们提到的时间戳会帮助backups避免遗漏掉操作，当请求被记录下后，backups才会发送确认信息。之后当primary接受到多数派的确认信息后，就会去执行请求，并将结果返回给client。但这里有一个疑问：backups不用执行请求吗？

?View-change protocol

因故障进行view changes创建新view的过程类似Paxos，都是首先提出一个新的view-id，然后提出新的view。下面的Figure 4就是这个view-change协议的过程：

当view manager（提出view-id的cohort）选出新的view-id时，它会给其它的cohorts发送一个view_change_arg信息，之后就是通过你发我回来选出新的view和primary。

?Optimizations

文章提出模型的一个优化是：协议要求所有的请求都要广播给backups，其中包括只读操作，不过本文采取的优化是如果backups中的多数派承诺60秒不形成新的view，primary会暂时答复只读请求，而不用再广播给backups。另一个优化是：如果要检测出一个故障，至少需要三台replicas，我们可以减少到两台replicas，而让第三台机器充当一个观察者的角色，即正常情况不会参与执行请求，只有当出现故障或network partition时再加入一致性协议来跟其他两台机器形成一个view。

Paxos Made Practical