区块链核心算法之——Paxos算法

比特币、以太坊、区块链基础知识、应用场景及其数学原理基本上让币爷撸了个遍。但是你币爷不是一个容易满足的人，在了解了区块链、数字货币的基础知识上，我们能不

能进一步摸索区块链的底层算法原理？币爷从今天开始，打算花几期时间来和大家一起研究一下区块链的核心算法，死磕到底！

今天我们的计算机和信息系统本质上都是分布式的。越来越多的公司进入全球化时代，它们拥有部署在不同大陆上的成千上万的计算机。数据存储在不同的数据中心，而计算机任务则运行在多台计算机上。

虽然分布式系统带来了很多好处，比如扩大存储容量和计算能力，甚至有可能连接地理空间上分离的区域，然而它也带来了一个很麻烦的协调问题（CoordinationProblems）。在分布式系统中，协调问题是很常见的。即便是一个分布式系统中的每个节点（如计算机、核、网络交换机等）几年才发生一次故障，但如果系统包含数百万个节点，那么平均每分钟都将发生一次故障。从好的方面讲，人们期待一个多节点的分布式系统可以容忍一些错误并且持续正常工作。

我们应该如何创建一个容错的分布式系统呢？本期将从一些简单的问题开始，一步步改进我们的方案，最终将得到Paxos，一个甚至可以在逆境下工作的协议。

客户端/服务器

定义1.1（节点（Node））.系统中一个工作单元被称为节点（Node）。在一个计算机网络中，所有的计算机都是节点。在经典的客户端/服务器模式下，服务器和客户端都是节点。这里，如不做另外说明，我们假设系统中节点的总数为n.

模型1.2（消息传递（MessagePassing））.我们在消息传递模式（MessagePassingModel）下研究由一组节点构成的分布式系统。每个节点都能进行本地运算，并可以向所有其他节点发送消息。

补充评论与注解：

我们从最小的分布式系统（仅包含两个节点）开始。该系统中有一个客户端节点，它希望操作（比如存储或更新）在远程服务器节点上的数据。

算法1.3朴素的客户端/服务器算法

1：客户端每次向服务器发送一条命令

模型1.4（消息丢失（MessageLoss））.

在存在消息丢失（MessageLoss）的消息传递模式下，任何一条消息都不能保证可以安全地到达消息的接受者。

补充评论与注解：

一个相关的问题是消息损坏，即收到了一条消息，但是其内容已经损坏了。实际上，与消息丢失相比，我们可以更好地处理消息损坏，比如在消息中增加校验码。

如果消息丢失，则算法1.3不能正常工作。因此我们需要一点小改进。

算法1.5带确认(Acknowledgements)的客户端/服务器算法

1：客户端每次向服务器发送一条命令

2：服务器每收到一条命令，都会发送一条确认信息

3：如果客户端没有在一个合理的时间内收到确认信息，它将重新发送命令。

补充评论与注解：

“每次发送一条命令”意味着如果一个客户端发送了一条命令c,那么在它收到服务器对c的确认信息之前，它将不会发送任何新的命令c'。

不但客户端发送的信息可能丢失，服务器发送的确认消息也可能丢失。如果一条确认信息丢失，那么客户端可能重新发送一条消息，即使该消息已经被服务器接受且执行。为了避免重复执行相同的信息，我们可以给每条消息加上序列号，这样接收者可以辨识出重复的消息。

这个看似简单的算法是很多可靠协议的基础，比如TCP。

算法可以很容易地拓展到多个服务器的场景：客户端发送一条命令给每个服务器，一旦客户端收到所有服务器的确认消息，就可以认为该命令已被成功执行。但是如何处理多个客户端的情况呢？

模型1.6（可变消息延迟（VariableMessageDelay））.在实际应用中，消息传输花费的时间是不同的。即使是在相同的一对节点间传输信息，所耗费的时间也可能不同。这里我们假定都是可变消息延迟模式。

定理1.7.如果算法1.5在多个服务器和多个客户端间运行，服务器接收到的命令顺序可能是不同的，这将导致不一致的状态。

证明.假定我们有两个客户端u1和u2，以及两个服务器s1和s2。两个服务器上都在维护同一个变量x的值，起始状态，x=0。两个客户端都在向服务器发送命令去更新x的值。u1的命令是x=x+1，而u2的命令是x=2*x。假设两个客户端同时发送它们的命令。因为有消息延迟，有可能s1先接到u1的命令，而s2先收到u2的命令。于是，在s1上执行两个命令的结果是x=(0+1)*2=2，而在s2上计算的结果则是x=(0*2)+1=1。

定义1.8（状态复制（StateReplication））.对于一组节点，如果所有节点均以相同的顺序执行一个（可能是无限的）命令序列c1,c2,c3,…,则这组节点实现了状态复制（StateReplication）。

补充评论与注解：

状态复制是分布式系统的基本性质：

对于金融科技业的从业人员来说，状态复制经常等同于区块链。

因为单个服务器可以天然实现状态复制，我们可以将单个服务器视为一个串行化器（Serializer）。通过让串行化器来分发命令，自动对请求进行排序并获得状态复制。

算法1.9借助单一串行化器实现状态复制

1：所有的客户端都向串行化器发送命令，每次发送一条

2：串行化器将命令逐条转发给所有的服务器

3：（针对某条命令）一旦串行化器收到所有的确认信息，它通知（发送该命令的）客户端该命令已被成功执行

补充评论与注解：

这个想法有时也被称为主-从复制（Master-SlaveReplication）。

但是如何处理节点故障呢？很显然，串行化器是一个潜在的单点故障（SinglePointofFailure）。

我们是否可以构造一个更分布式的方法来解决状态复制？与其直接构造一个一致的命令序列，不如换一个思路：想办法确保在任何时候最多只有一个客户端在发送命令。也就是说，我们采用互斥（MutualExclusion）和各自加锁（RespectivelyLocking）的思想。

算法1.10两阶段协议（Two-PhaseProtocol）

阶段1

1：客户端向所有的服务器请求锁

阶段2

2：if如果该客户端成功获得了所有服务器的锁then

3：该客户端以可靠的方式向每个服务器发送命令，随即释放锁

4：else

5：该客户端释放已经获得的锁

6：该客户端等待一段时间，再重新进入阶段1

7：endif

补充评论与注解：这个想法曾出现在多个领域中，也有着不同的名称，比如两段锁协议(Two-Phase-Locking)(2PL)。

另一个例子是两阶段提交协议（Two-PhaseCommit）（2PC）,典型场景是数据库系统。第一阶段被称为事物的准备阶段，第二阶段中这个事务或者提交(Committed)或者撤销（回滚)(Aborted)。两阶段提交过程并非由客户端启动，而是在一个被选定的服务器上完成，这个服务器节点通常被称为协调者；

一般认为，如果节点可以在宕机之后恢复，较之一个简单的串行化器，2PL和2PC能提供更好的一致性保证。特别对在节点宕机之前就启动的事物来说，存活的节点或许能和宕机的节点保持一致。在使用了一个额外阶段（3PC）的改进版协议中，这个有点更为明显。

2PC和3PC的问题是，他们没有很好地处理异常。

算法1.10真的能很好地应对节点崩溃吗？不是！实际上，它甚至比那个简单的序列器算法（算法1.9）更糟。算法1.9只要求一个节点必须正常工作，但是算法1.10要求所有服务器能够正常响应请求。

如果我们仅仅得到一部分服务器的锁，算法1.10能否工作？获得过半数节点的锁是否就足够了？

如果两个或更多的客户端同时企图获得大部分服务器的锁，会发生什么情况？客户端是否必须放弃它们已经获得的锁，以避免死锁？怎么做？如果客户端在释放锁之前就发生故障，又该怎么办？我们是否需要一个与锁稍微不同的概念？

Paxos

定义1.11（票（Ticket））.一张票（Ticket）是一个弱化形式的锁，具备下面的性质。

可重新发布：一个服务器可以随时发布新的票，哪怕前面发布的票还没有被释放。

票可以过期：当客户端使用一张票t来给服务器发送消息时，仅当t是最新发布的票时，服务器才会接收。

补充评论与注解：

宕机问题被顺利解决：如果一个客户端在得到一个票之后宕机了，其他的客户端不会受到影响，因为服务器会发布新的票。票可以使用计数器来实现：每当服务器收到一个（发布票的）请求时，将计数器加1。这样当客户端尝试使用某个票时，服务器可以判定该票是否已经过期。

我们如何使用票？我们能简单地将算法1.10中的锁用票代替吗？我们需要增加至少一个额外阶段，因为只有客户端知道在阶段2中是否有过半数票是有效的。

算法1.12朴素的基于票的协议

阶段1

1：客户端向所有的服务器请求一张票

阶段2

2：if收到过半数服务器的回复then

3：客户端将获得的票和命令一起发送给每个服务器

4：服务器检查票的状态，如果票仍然有效，则存储命令并给该客户端一个正反馈消息

5：else

6：客户端等待，并重新进入阶段1

7：endif

阶段3

8：if客户端从过半数服务器处得到了正反馈then

9：客户端告诉所有的服务器执行之前存储的命令

10：else

11：客户端等待，然后重新进入阶段1

12：endif

补充评论与注解：

该算法是有问题的。假设u1是第一个成功地在过半数服务器上存储了命令（c1）的客户端。但是u1很慢，在它告知所有服务器执行命令时（第9行），另一个客户端u2在部分服务器上将命令更新为c2。然后，u1告诉所有的服务器执行所存储的命令。此时，部分服务器将执行c1，而另一部分将执行c2。

如何解决这个问题呢？我们知道如果要修改u1存储在服务器上的命令，u2必须使用比u1更新的票。因此，当u1的票在阶段2被接受后，u2必须在u1在服务器上存储命令（第4行）之后再拿到它的票。

一个想法：如果在阶段1中，一个服务器不但发布票，而且也发布它当前所存储的命令。那么u2就知道u1已经存储了命令c1。u2可以不要求服务器存储命令c2，而是继续存储c1。这样，两个客户端都尝试存储和执行相同的命令，那么谁先谁后就不再是一个问题。

但是，服务器们所存储的命令不一定相同，那么在阶段1，u2就可能从不同的服务器获知了多个不同的命令。它到底应该支持哪一个呢？

注意到支持最新存储的命令总是安全的。只要还不存在一个过半数服务器一致支持的命令，客户端们就可以支持任何命令。然而，一旦有一个过半数服务器一致的命令，所有客户端就必须支持这个命令。

因此，为了判定哪一个命令是最新存储的，服务器们必须记录存储命令所使用票的编号，并且在阶段1把命令和相应的编号都告诉客户端。

如果每个服务器使用自己的票号，最新的票号就不一定是最大的。如果客户们自己来产生票号，那么这个问题可以解决！

算法1.13Paxos

客户端（提案者）服务器（接收者）

初始化.........................................................................

c#等待执行的命令#Tmax=0#当前已发布的最大票号

t=0#当前尝试的票号#

C=⊥#当前存储的命令#

Tstore=0#用来存储命令C的票

阶段1...............................................................................

1:t=t+1

2:向所有的服务器发消息，请求得到编号为t的票

3:ift>Tmaxthen

4:Tmax=t

5:回复：ok(Tstore,C)

6:endif

阶段2...............................................................................

7:if过半数服务器回复okthen

8:选择Tstore值最大的（Tstore,C）

9:ifTstore>0then

10:c=C

11:endif

12:向这些回复了ok的服务器发送消息：propose(t,c)

13:endif

14:ift=Tstorethen

15:C=c

16:Tstore=t

17:回复：success

18:endif

阶段3...............................................................................

19:if过半数服务器回复successthen

20:向每个服务器发送消息：excute（c）

21:endif

补充评论与注解：

与前面的算法不同，这个算法中没有明确地标出在哪个位置客户端可以跳转到阶段1并且开始新的尝试。实际上这并不是必要的，因为一个客户端可以在算法的任何位置取消当前的尝试并且开始新一轮尝试。这样的方式（不明确标出何时开始新的尝试）让我们不需要操心如何选择何时的超时（timeout）值。我们现在更关心正确性，而正确性和什么时候开始新的尝试是独立的。

在阶段1和阶段2，如果票已过期，可以让服务器发送负的反馈，这样可以提高性能。

连续两次尝试之间的等待时间可以用随机函数确认，这样可缓和不同节点之间的竞争。

引理1.14.我们将客户端发送的一条消息propose（t,c）（第12行）称为一个内容是（t,c）的提案。如果一项提案（t,c）被存储在过半数服务器上（第15行），则称该提案被选中。如果已经存在一个被选中的propose（t,c），则对于后续每一个propose（t',c'），c'=c将始终成立（t'>t）。

证明。对于每一个票号α，最多只能有一个提案。根据算法（第2行），客户端先向所有服务器发送消息，请求编号为α的票。而只有在收到过半数服务器对编号α的这张票的ok回复之后，客户端才会发送一个提案（第7行）。因此每个提案都可以用它对应的票号α来唯一标识。

下面我们用反证法来证明。假设至少存在一个提案propose（t',c'），满足t'>t且c'≠c。对于这样的提案，我们不妨只考虑那个拥有最小票号的提案，并假设编号为t'。因为propose（t,c）和propose（t',c'）都已经被送达了过半数服务器，那么这两个过半数服务器集合之间必然存在一个非空交集S,在S中的服务器都收到了这两个提案。由于propose（t,c）已经被选中，则至少有一个在S中的服务器s已经存储了命令c。注意到当命令c被存储时，票号t仍然是有效的。因此，s必然是存储propose（t,c）之后才收到了关于票号t'的请求，而且该请求使得票号t失效。

于是，发出propose（t',c'）的客户端必然已经从s处得知：某个客户端之前已经存储了propose（t,c）。根据算法第8行，每个客户端必须采纳已经存储且具有最高票号的命令，于是该客户端将提议c而不是c'。根据算法，只有一种可能使得该客户端不采纳c:如果该客户端从某个服务器得知另一个提案propose（t*,c*）已经被存储，且c*≠c、t*>t。但是，在这种情况下，一定存在一个客户端已经发送提案propose（t*,c*），且t

定理1.15.如果一条命令c被某些服务器执行，那么所有的服务器最终都将执行命令c。

证明。根据引理1.14我们得知一旦一个关于包含c的提案被选中，后续的每个提案都将采纳c。由此可见，所有成功的提案都将采纳相同的命令c。这样，只有采纳了命令c的提案会被选中。此外，由于客户端只会在一条命令被选中之后告诉服务器执行该命令（第20行），每个客户端将最终告知所有的服务器执行命令c。

补充评论与注解：

如果拥有第一个成功提案的客户端没有宕机，它将直接告诉所有的服务器执行命令c。

但是，如果客户端在告诉任何一个服务器执行命令之前就宕机了，服务器们将只有等到下一个客户端成功获提案之后才可以执行命令。一旦一个服务器接收到一个请求去执行命令，它可以通知所有后面到达的客户端：已经有一条命令被选中了。这样客户端就可以避免（再向这个服务器）继续发送提案。

如果超过一半的服务器宕机，Paxos将不能工作。因为客户端不能再取得过半数服务器认可。

最初版本的Paxos包含三个角色：提案者、接受者，以及学习者。学习者不做任何事情，只是从其他节点学习哪个命令被选中了。

我们只让每个节点承担一个角色。在某些场景下，一个节点可能承担多个角色。比如，在一个P2P的场景下，每个节点既是服务器又是客户端。

上述算法必须信任客户端们（提案者们）会严格遵守协议。然而，这个假设在很多场景下并不合理。在某些场景下，提案者的角色可以被一组服务器承担，客户端们需要联络提案者，并用它们的名义来发布提案。

到现在为止，我们仅仅讨论了如何通过Paxos来使一组节点达成一致性决议（decision）来执行一条命令。单独的一条决议被称为Paxos的一个实例（instance）。

如果希望执行多条命令，我们可以给每个实例附加一个实例编号。在每条消息中，该实例编号都会被使用。一旦某条命令被选中，任何一个客户端都可以采用一个新的实例编号启动一个新的实例。如果一个服务器不知道前面的一个实例已经有了一个一致决议，那么该服务器可以询问其他服务器决议的内容。

【延伸阅读】Paxos算法的来历

LeslieLamport在1989年提出了Paxos。但是，“Paxos”这个名字是怎么来的呢？Lamport在论文中描述了一个虚拟的希腊小岛——Paxos，并假定这个算法是为了解决在岛上的议会中的投票问题。他非常喜欢这个想法，甚至以一个印第安纳·琼斯风格的考古学家的身份做过几个报告。当论文第一次投稿的时候，大多数评委都对这个议会故事感到困惑，无法理解算法的目的和思想。论文因此被拒绝发表！

Lamport拒绝修改论文，稍后他表示“不开心，因为这个领域的学者如此缺乏幽默感”。

几年之后，随着应用的发展，Paxos协议的用途变得更加广泛。Lamport于是从抽屉里翻出这篇被拒绝的论文，并发给他的几位同事。这些同事们都表示很喜欢这个想法。于是Lamport决定重新投稿。和8年前的初稿相比，论文基本没改！但是这次论文被录用了。

浏览过的版块