如何创造一个容错分布式系统？本章我们从简单问题开始，一步一步地改进，直到获得一个即便在不利环境下也能工作的系统，Paxos。

2.1 客户端/服务器

定义 2.1 (节点). 我们把系统中的单个参与者称为节点。在计算机网络里计算机就是节点，在经典的客户端/服务器模型里服务器和客户端都是节点，等等。如果没有特别说明，系统里的节点数都是 \(n\)。

模型 2.2 (消息传递). 在消息传递模型里我们研究由节点组成的分布式系统。每个节点可以执行本地运算，并且能向每个别的节点发送消息。

述评：

我们从两个节点组成的系统开始。我们有一个客户端节点，它要对远程的服务器节点上的数据进行操作 (存储，更新，等等)。

算法 2.3 朴素客户端/服务器算法


1: 客户端每次向服务器发送一个指令

模型 2.4 (消息丢失). 带有消息丢失的消息传递模型里，不能保证任何特定消息会安全到达接收者。

述评：

一个相关的问题是消息损坏，即消息被收到但内容受损。在实践中，与消息丢失不同，消息损坏很好处置，比如向消息添加校验码之类的额外信息。
算法 2.3 在消息丢失的情况下不能正确工作，所以我们需要改进一点点。

算法 2.5 带有确认的客户端/服务器算法


1: 客户端每次向服务器发送一条指令
2: 服务器确认每条指令
3: 如果客户端没有在一个合理的时间内收到确认，则重新发送指令

述评：

“每次发送一条指令”意味着当客户端发出指令 \(c\) 时，在收到针对 \(c\) 的确认之前不会发出下一条指令。
不止是客户端发出的消息可能丢失，服务器发回的确认也可能丢失，因此客户端有可能会重新发送已经被接收并执行的指令。为了避免相同的指令被多次执行，可以向每条消息添加一个序号，这样接收者就能识别重复消息了。
这个简单的算法是许多可靠协议的基础，比如 TCP。
可以很容易地扩展这个算法以适用于多个服务器的情况：客户端把每个指令发送到每个服务器，然后，当客户端收到每个服务器发来的确认时，就认为指令成功执行了。
多个客户端的情况呢？

模型 2.6 (可变消息延迟). 实践中，消息的传输可能需要不同的时间，即便是在同样两个节点之间传输。

述评：

本章中，我们采用可变消息延迟模型。

定理 2.7. 如果算法 2.5 被用于多个客户端和多个服务器，那么不同服务器看到的指令顺序可能不同，导致不一致的状态。

证明. 假定有两个客户端 \(u_1\) 和 \(u_2\)，两个服务器 \(s_1\) 和 \(s_2\)。两个客户端都发出指令改变服务器上的一个变量 \(x\) 的值，初值为 \(x=0\)。客户端 \(u_1\) 发出的指令是 \(x = x + 1\)，客户端 \(u_2\) 发出的指令是 \(x = 2 \cdot x\)。

如果 \(s_1\) 先收到来自 \(u_1\) 的消息，而 \(s_2\) 先收到来自 \(u_2\) 的消息 (比如有可能 \(u_1\) 与 \(s_1\) 地理上距离近，而 \(u_2\) 与 \(s_2\) 距离近)，那么，\(s_1\) 的计算结果是 \(x = (0+1)\cdot 2 = 2\)，而 \(s_2\) 的计算结果是 \(x = (0\cdot 2) + 1 = 1\)。

\(\square\)

定义 2.8 (状态复制). 如果所有节点按相同顺序执行一个指令序列 \(c_1,\ c_2,\ \ldots\) (序列可能无限长)，则我们说这些节点达成了状态复制。

述评：

状态复制是分布式系统的基本性质。
对于金融技术行业的人来说，状态复制经常就是区块链的同义词。第七章我们将会讨论的比特币区块链其实就是一种实现状态复制的方法。但是，正如我们将在其它章节看到的，还有许多值得了解的其它概念可供选择，性质各不相同。
对于单个服务器而言，状态复制是平凡的任务，因此我们可以指定一个单独的服务器作为序列器 (serializer)。通过让序列器来分发指令，我们自动地对请求排好序并且达成了状态复制！

算法 2.9 用序列器实现状态复制


1: 客户端每次发送一个指令到序列器
2: 序列器每次转发一个指令到所有其它服务器
3: 序列器收到所有的确认后告知客户端

述评：

这个想法有时被称为主-从 (master-slave) 复制。
如果发生节点故障呢？序列器是个单故障点 (single point of failure)！一旦它出故障，整个系统就都不能运作了。
我们能否有一个更加分布式的解决状态复制的方法？与其直接确立指令的一致顺序，我们可以采用一个不同的方法：我们可以保证每个时刻至多只有一个客户端在发送指令；也就是说，我们使用互斥 (mutual exclusion)，各自加锁。

算法 2.10 二步协议


第一步
1: 客户端向所有服务器请求锁
第二步
2: 如果客户端收到每个服务器的锁，那么
3:      客户端把指令发给每个服务器，并归还锁
4: 否则
5:      客户端归还收到的那些锁
6:      客户端等待，然后回到第一步再次执行

述评：

这个想法在许多场景中出现，叫法各不同，细节稍有变化，比如二步锁 (two-phase locking; 2PL)。
另一个例子是二步提交协议 (two-phase commit; 2PC)，经常在数据库环境中出现。第一步被称为交易准备，而在第二步，交易要么被提交，要么被中止。这个 2PC 过程不是由客户端发起，而是由一个指定的被称为协调器的服务器节点发起。
通常认为，如果节点可以在崩溃后恢复，那么 2PL 和 2PC 比简单的序列器提供了更好的一致性保证。特别地，对于崩溃前启动的交易而言，活着的节点或许可以与崩溃的节点保持一致。这个好处在多一个步骤的另一个协议 (3PC) 那里得到了进一步改善。
2PC 和 3PC 的问题是，在意外情况发生时，它们不是良好定义的。
算法 2.10 真的很好地处理了节点崩溃问题吗？并没有！事实上，它比算法 2.9 里那个简单的序列器更坏：相比于要求必须能访问某一个节点，算法 2.10 要求所有的服务器都能响应。
如果我们只从服务器的一部分得到锁，算法 2.10 还能工作吗？是否从服务器的多数得到锁就够了？
如果两个客户端同时试图获得大多数锁，会怎么样？客户端是否必须废弃已经获得的锁，以免出现死锁？怎么进行？如果它们在释放锁之前崩溃了又如何？我们是否需要稍微不同的概念？

2.2 Paxos

定义 2.11 (凭证; ticket). 凭证是锁的弱形式，具有如下性质：

可重发： 一个服务器可以重新发布一个凭证，即便之前发布的没有被归还。
票据过期： 如果客户端使用之前获得的凭证 \(t\) 往服务器发送一条消息，仅当 \(t\) 是最新发布的凭证时服务器才接受 \(t\)。

述评：

崩溃不导致问题：如果一个客户端在持有凭证期间崩溃了，其余的客户端不受到影响，因为服务器可以简单地发布新的凭证。
凭证可以通过一个计数器实现：每收到一次凭证请求，计数器加一。当一个客户端试图使用一个凭证时，服务器可以决定这个凭证是否过期了。
我们能对凭证做什么？我们能否简单地把算法 2.10 里的锁替换成凭证？我们需要添加至少一个额外的步骤，因为只有客户端知道在第二步中是否多数凭证是有效的。

算法 2.12 朴素凭证协议


第一步
1: 客户端向所有服务器请求凭证
第二步
2: 如果客户端收到多数服务器的回复，那么
3:      客户端把指令和凭证一起发给每个服务器
4:      服务器仅当凭证依然有效时保存指令，并且回复客户端
5: 否则
6:      客户端等待，然后回到第一步再次执行
第三步
7: 如果客户端从多数服务器收到正面回答，那么
8:      客户端请求服务器执行保存的指令
9: 否则
10:     客户端等待，然后回到第一步再次执行

述评：

这个算法有些问题：假设客户端 \(u_1\) 第一个将其指令 \(c_1\) 保存在多数服务器上。假定 \(u_1\) 刚好在通知服务器之前 (第三步刚要开始之前) 变得很慢，而另一个客户端 \(u_2\) 将某些服务器上存储的指令更新为 \(c_2\)。之后，\(u_1\) 请求服务器执行存储的指令。现在，有些服务器执行 \(c_1\)，有些执行 \(c_2\)！
怎么解决这个问题？我们知道每个在 \(u_1\) 之后更新存储指令的客户端 \(u_2\) 必定比 \(u_1\) 使用了更新的凭证。既然在第二步 \(u_1\) 的凭证被接收，\(u_2\) 必定是在 \(u_1\) 往相应的服务器上存储指令之后才获取它的凭证的。
想法：如果在第一步中服务器不是只分发凭证，同时也把当前存储的指令告知客户端，会怎么样？这样，\(u_2\) 会知道 \(u_1\) 已经存储了 \(c_1\)，因此 \(u_2\) 可以支持 \(u_1\)，也存储 \(c_1\)，而不是 \(c_2\)。既然两个客户端试图存储和执行相同的指令，顺序就不成问题了。
可如果不是所有的服务器都保存了相同的指令，并且 \(u_2\) 在第一步发现了多个存储的指令，\(u_2\) 应该支持哪个？
注意到，支持最新存储的指令总是安全的。只要不存在多数派，客户端就可以支持任何指令。但是，当出现多数派之后，客户端需要支持这个值。
所以，为了决定哪个指令是最新存储的，服务器可以记下用来存储每个指令的凭证号码，之后在第一步把这个号码告诉客户端。
如果每个服务器使用其自身的凭证号，那么最新的凭证未必拥有最大的数字。这个问题可通过客户端自己对凭证号给出建议来解决。

算法 2.13 Paxos




    客户端 (申请者)
    服务器 (接收者)


    初始化


    c  -- 待执行指令
    Tmax = 0  -- 发布的最大的凭证号


    t = 0  -- 待尝试的凭证号
    C = NULL  -- 存储的指令


    
    Tstore = 0  -- 用于存储 C 的凭证


    第一步


    1: t = t + 1 


    2: 向所有服务器索取凭证 t 


    
    3: 如果 t > Tmax，那么


    
    4:     Tmax = t


    
    5:     以 ok(Tstore, C) 回应


    第二步


    6: 如果多数回答 ok，则 


    7:      选取具有最大 Tstore 的 (Tstore, C) 


    8:      如果 Tstore > 0，那么 


    9:          c = C 


    10:     发出请求 propose(t,c) 给相同的多数派 


    11: 如果 t = Tmax，那么


    12:     C = c


    13:     Tstore = t


    14:     以 success 作为回答


    第三步


    15: 如果多数回答 success，那么 


    16:     发送 execute(c) 给每个服务器

客户端 (申请者)	服务器 (接收者)
初始化
c -- 待执行指令	Tmax = 0 -- 发布的最大的凭证号
t = 0 -- 待尝试的凭证号	C = NULL -- 存储的指令
	Tstore = 0 -- 用于存储 C 的凭证
第一步
1: t = t + 1
2: 向所有服务器索取凭证 t
	3: 如果 t > Tmax，那么
	4: Tmax = t
	5: 以 ok(Tstore, C) 回应
第二步
6: 如果多数回答 ok，则
7: 选取具有最大 Tstore 的 (Tstore, C)
8: 如果 Tstore > 0，那么
9: c = C
10: 发出请求 propose(t,c) 给相同的多数派
	11: 如果 t = Tmax，那么
	12: C = c
	13: Tstore = t
	14: 以 success 作为回答
第三步
15: 如果多数回答 success，那么
16: 发送 execute(c) 给每个服务器

述评：

与之前提及的算法不同，这里并没有客户端显式决定开启一个新请求并跳回第一步的步骤。注意到，这样的步骤是不必要的，因为客户端可以在算法的任何地方终止当前请求并启动新请求。这样做的好处是，我们不需要小心选取“好的”超时时间，因为正确性与何时开启新请求的决定无关。
可以通过在凭证过期的情况下让服务器在第一和第二步发送负面回复的方法提高性能。
不同客户端之间的冲突可以通过随机化接连尝试的等待时间缓解。

定理 2.14. 我们把第 10 行客户端发出的消息 propose(t,c) 称为对 (t,c) 的申请。如果一个申请被多数服务器保存 (第 12 行)，则称这个申请被选中。对于每个发布的 propose(t',c')，如果 t' > t，且存在被选中的 propose(t,c)，则 c' = c。

证明. 注意到，对每个凭证号 \(\tau\) 最多存在一个申请，因为客户端仅在收到对应 \(\tau\) 的多数服务器的回复时才发出申请 (第 6 行)。因此，每个申请由凭证号 \(\tau\) 唯一标识。