Paxos Made Practical

当一个组中一台机器提出一个值时，其它成员机器通过PAXOS算法在这个值上达成一致。

Paxos分三个阶段。

第一阶段：

提出者会选出一个提议编号n（n>0，n的低位应当包括提出者的唯一标识。这样两台机器就不会产生同样的编号），然后会向组内其它成员发送信息PREPARE（n）。成员假设已经见到过PREPARE信息大于n，就会拒绝它；假设已经见到的PREPARE信息n‘ < n（这个提议n’的值假设为v‘），就会回复信息PREPARE-RESULT(n’, v’)。假设这个成员还没有见过不论什么提议。就会回复信息PREPARE-RESULT(0, nil)。假设组内大多数成员（majority）都接受了这个PREPARE（n）信息，就进入PAXOS算法的第二阶段。

第二阶段：

It sets v to the value in the highest-numbered prepare-result it received. If v is nil, it selects any value it wishes for v.（没看懂）


接下来提议者会向其它成员广播消息PROPOSE（n。v）。相同，假设成员已经见过的PREPARE（n‘’）（确定是PREPARE而不是PROPOSE）。n‘’ > n。就会拒绝这个消息；否则，就会接受这个消息，并给提议者一个回复。

假设组内多数（包含提议者自己）都接受了这个PROPOSE消息，提议者会广播消息DECIDE（n，v），这就表示这个组在提议的值v上已经达成一致了。

第三阶段哪里去了？

以下是PAXOS算法在实际中是怎样实现的。

先来了解一下什么是状态机（state machine）：是一个能接收请求产生回复的可确定性服务（deterministic service），可确定性服务意思是假设两个状态机拥有同样的初始状态。那么当它们接收到同样序列的请求时会产生同样的回复。

首先。我们要清楚一个复制系统（replication system），如Columbia University的M-SMR。会提供两套库，服务器端（server-side）库和client（client-side）库。前者负责状态机的实现，后者是让client发送请求给状态机然后得到回复。

让我们详细看看服务器端（server-side）库提供的三个函数：




这里说一下run函数的第三个參数

buf execute (buf request);

这是状态机里一个非常重要的组成函数。它负责将请求带给状态机并返回回复。

之前我们说过client库负责用户请求的提交和得到回复（这怎么和server端函数run的參数execute函数的功能一致呢？），假如这时有多个用户请求同一时候到来。client库就须要对这些请求达成一个统一的运行顺序让组内成员去运行，来保证一致性。这里就涉及与组内成员的通信问题。client库是怎样来联系组内各个成员的？也许是RPC。


不幸的是并非全部的RPCserver都是确定性的（deterministic）。举个样例，一个文件server会在一个文件发生写操作后将改动时间记录在文件的inode中。这样即使两个成员机器运行同样的文件server程序并运行同样的写请求，可是它们在运行写操作的时间却无法保证同样，比方都是2014／11／14 23：06。

这样就会在成员之间出现分歧状态。为什么你记录的改动时间比我早十分钟？解决方法是让一个机器记录下自己的改动时间，然后广播给大家。告诉大家都来记录这个时间。

事实上这里改动时间就是一个不确定性值（non-deterministic
value）。还是那个问题client库是通过什么手段来联系组内各个成员的？

看来这个问题是无法解答了。解析来切入正题： Normal-case operation

Normal-case Operation

在一个组里，有一个primary。其它的称作backups，这里有一个术语：view，表示一个拥有primary机器的处于活动状态的机器集合。每个view会有一个view-id来唯一标识，并且view-id是单调递增的，随着每一次view的改变。

上图展示了在正常情况（没有机器增加，没有机器故障）下信息的流动。

这里再引入一个术语：viewstamp，由view-id和timestamp结合而来，primary会给每个到来的请求一个timestamp。这个timestamp就指明了请求被运行的顺序。

相同加强版的viewstamp也表示请求的运行顺序。