前言

衷心感谢《The Science of the Blockchain》一书的作者Roger Wattenhofer。《The Science of the Blockchain》一书较为严谨地介绍了一种基础技术——容错分布式系统（faulttolerant distributed system）。

在容错分布式系统中，数据存储在多台服务器上，并且多台服务器协同完成一项计算操作。这里面，最大的问题便是如何进行协调（coordination problem）。围绕协调问题，研究人员提出了诸多算法与模型，如：区块链，一致性协议，电子合同，共识机制，电子账本，溯源系统，等。

容错分布式系统具有许多重要作用：
（1）同一份数据在多台服务器上进行备份，当一台服务器宕机或遭到黑客恶意攻击时，仍可从其它正常服务器获取或恢复数据（从另一角度出发，多中心化防止了一台服务器的腐败，message corruption一词用的很有意思）。
（2）客户端 C 1 C_1 C1​离 S a S_a Sa​较近而离 S b S_b Sb​较远，客户端 C 2 C_2 C2​则相反，且 S a S_a Sa​和 S b S_b Sb​提供相同的服务。但只有一台服务器时，总有一个客户端的响应时间较长，而有多台服务器时，客户端可就近获取服务，减少响应时长。

Fault-Tolerance & Paxos

这里不再赘述基本概念。现约定：分布式系统中所有节点（即所有服务器和客户端）都是诚实可靠的，服务器收到客户端的命令 m m m后立刻执行。

先考虑一台服务器 S S S、一个客户端 C C C的应用场景。 C C C发送一份消息（命令） m m m给 S S S，为了解决消息污染（消息被黑客恶意篡改、因硬件等因素导致比特翻转等）和消息丢失问题，需要采用消息验证码、数字签名和消息确认（acknowledgment，即ack）等算法。

1. C C C发送 m m m给 S S S，并利用消息验证码或数字签名附上校验码 τ \tau τ；
2. S S S根据 τ \tau τ判断 m m m是否安全（具体看密码学安全性定义），若安全则回复一个消息确认ack，并执行相关命令 m m m（为避免重复执行同一命令， S S S可自己存储一张历史列表以进行核对检查）；
3. 若 C C C在规定时间内没有收到相应的ack，重新发送 ( m , τ ) (m, \tau) (m,τ)。

讨论. 在具体实现中如何建立可靠连接请参考：TCP 为什么是三次握手，而不是两次或四次？ - 山尽的回答 - 知乎。注意，是建立可靠连接而非实现共识算法，网络上很多其它解释是错误的，他们所举例子与共识算法例子混淆了，《The Science of the Blockchain》学到下一章节便会证明：三次沟通依旧无法达成共识。

再考虑多台服务器、一个客户端的应用场景。易知，客户端仅需要群发 ( m , τ ) (m, \tau) (m,τ)即可实现分布式系统。

接着考虑一台服务器、多个客户端的应用场景。多个客户端可能同时发送不同命令，这多条命令之间存在冲突（服务器一次仅能处理一条命令），所幸仅有一台服务器，它可以*决定多条命令的执行序列。

最后考虑多台服务器、多个客户端的应用场景。该场景十分复杂，例如， C 1 C_1 C1​发送 m 1 m_1 m1​给 S a S_a Sa​和 S b S_b Sb​，同时间， C 2 C_2 C2​发送 m 2 m_2 m2​给 S a S_a Sa​和 S b S_b Sb​，由于网络延迟（具体参考计算机网络知识）， S a S_a Sa​可能先收到 m 1 m_1 m1​再收到 m 2 m_2 m2​，而 S b S_b Sb​可能先收到 m 2 m_2 m2​再收到 m 1 m_1 m1​，这就导致两台服务器执行命令后的状态不一致，失去了分布式系统的最初功能。

为保证所有服务器的状态一致，我们要确保它们的命令执行序列相同，即所有服务器第 i i i次命令操作都一样。先简化模型，仅考虑序列中的索引 i i i，问题演化成：在一次选举中，多个客户端分别提出各自的议案 m 1 m_1 m1​， m 2 m_2 m2​， … \dots …，众多服务器需要从中协调选取出一个大家都认可的议案。

最简单的方法便是指定一台串行器（serializer），所有客户端将各自的议案发送给串行器，由串行器决定第 i i i次命令为哪一个，然后群发给所有服务器（即先一台服务器多个客户端，再多台服务器一个“客户端”）。但该主从（master-slave）方法弊端较为明显，即当串行器死机时整个分布式系统便会彻底崩溃。

另一种可尝试的方法便是两段互斥锁协议（借用计算机操作系统的相关思想），设计如下简单协议：

1. 阶段A，客户端向所有服务器申请锁。
2. 阶段B，若规定时间内所有服务器都将锁给了客户端，则客户端将消息 m m m发送给所有服务器；否则，客户端将当前占有的锁还给服务器，等待一段时间并返回阶段A。

上述协议耗时较长，且不具备容错能力（万一1台服务器宕机了，那么整个系统崩溃），可以进行改进，即将申请所有的锁改成申请半数以上的锁。

但两段上锁协议存在死锁问题，假想有4台服务器，客户端 C 1 C_1 C1​和 C 2 C_2 C2​分别占有了半数的锁，在阶段B时， C 1 C_1 C1​本来想释放它占有的锁，但突然 C 1 C_1 C1​宕机了，那整个系统就彻底陷入僵死状态。一个看似可解的方法就是让服务器为锁设置占有时长（开始有Paxos的影子）。思考如下案例：

C 1 C_1 C1​占有了锁 L 1 L_1 L1​和 L 2 L_2 L2​， C 2 C_2 C2​占有了锁 L 3 L_3 L3​和 L 4 L_4 L4​， C 1 C_1 C1​宕机而 C 2 C_2 C2​正常运作，超过一定时长，服务器自认为收回了 C 1 C_1 C1​和 C 2 C_2 C2​的锁并其锁 ( L 1 , L 2 , L 3 ) (L_1, L_2, L_3) (L1​,L2​,L3​)给了 C 2 C_2 C2​， C 2 C_2 C2​提交命令 m 2 m_2 m2​，碰巧的是同时间， C 1 C_1 C1​恢复工作并占有了锁 L 4 L_4 L4​且由于操作系统错误 C 1 C_1 C1​仍认为它持有锁 L 1 L_1 L1​和 L 2 L_2 L2​， C 1 C_1 C1​也提交命令 m 1 m_1 m1​，这就产生了命令冲突。

由上述例子可知，不宜仅让服务器来维护锁的状态（是否归还），而应该由客户端和服务器 S i S_i Si​二者共同记录锁 L i L_i Li​的状态。并且，二者还应该为锁加上一个编号，当服务器看到两者持有的锁编号不一致时可判断出这把锁是无效的（服务器已收回该锁但客户端误认为自己还持有该锁）。

如何制定锁的编号？需要遵循一条原则：先发的锁无法覆盖后发的锁（因为当服务器产生后发的锁时它已认为新发的锁被“收回”了）。既然这里有个优先级且随时间增长优先级变大，那么就可以拿这个优先级来做锁的编号。

由谁来决定锁的编号？如果让服务器来决定锁的编号，那么有如下问题：有4台服务器，一个客户端向整个网络系统申请4把锁，需要维护一个数值列表 ( L 1 , L 2 , L 3 , L 4 ) (L_1, L_2, L_3, L_4) (L1​,L2​,L3​,L4​)，存储开销较大（注意：4台服务器的时钟步长不一定一样，这会导致该办法中的 L i L_i Li​是不同步的）。相反，如果由客户端来决定锁的编号，那么就没有该问题。

如何制定锁的占有时长？时长数值设置太大容易导致系统响应时间较长，时长数值设置太小有可能导致命令还没来得及发送锁就被“收回”。Paxos协议利用客户端的通信速度来自适应决定锁的占有时长。

一个不完善的粗糙协议被制定如下（上述符号 m m m接下来用 c c c代替）：

注意，上述协议无法被严格证明是安全的（安全指不存在状态不一致问题）。假想， C 1 C_1 C1​在阶段3发送了execute(c)，但不幸由网络延迟导致发送过程较慢，碰巧更不幸的是 C 2 C_2 C2​快速完成了半数以上锁的申请并发送了另外一条execute(c’)，这时整个系统就炸了。

为解决上述问题，我们可以想办法通知 C 2 C_2 C2​让它主动把c’ 变成 c c c，于是就有了Paxos协议。

好了，现在所有服务器执行的便都是命令 c c c。为防止重复执行（先收到 C 1 C_1 C1​发送的execute(c)，又收到 C 2 C_2 C2​发送的execute(c)），服务器可以维护一张命令执行记录。

本文详细地介绍了Paxos协议的设计思路，我们研究人员在设计一份可靠协议时需要有一个完整清晰的思路。这里不再赘述安全性证明，若想深入研究Paxos的理论证明，请购买《The Science of the Blockchain》正版书籍进行研读。这里仅介绍如何在第 i i i次协商中挑选出唯一的命令 c c c，对执行多个命令，读者可进行自己思考（Tips. 为选举也打上一个编号标签）。