Paxos漫谈

发展史
Paxos算法是现代分布式系统中的一项重要的基础性技术，得到了广泛的应用。
Paxos的整个发展过程大概可以分为三个阶段：
第一阶段：萌芽期。大致在1988-1996年。1988年Liskov等人在PODC上发表了一篇文章，提出了一个在副本出现宕机情况下仍能工作的主从备份算法，该算法与Paxos本质上是一致的。
Lamport在1989年提出了Paxos这个名称，但他的论文因为过于艰涩，未能发表。Lamport企图用一个寓言故事来描述他的算法思想，却没有得到评委的认同。
这篇文章直到1998年才正式发表，那时分布式共识问题已引起了广泛重视。从时间上看，Liskov的论文更早一些，但是由于种种原因，特别是图灵奖得主Lampson的推崇，Lamport的工作影响力更广。
后来学界和工业届也基本都采纳了Paxos这个名称。值得一提的是，Liskov在分布式共识领域同样做出了巨大的贡献。比如目前风靡的PBFT算法就出自Liskov的研究团队。
Lampson将这两篇都归为“基础Paxos”，以与后续版本的Paxos区分开来。在这个时期，虽然陆续有不少工作改进，但整体仍处于不温不火的状态。

第二个阶段，即1996年-2007年，这个时期可以用花团锦簇来形容。Paxos引起了学者关注，涌现出一批Paxos的不同版本。
这些变种从不同的侧面完善了基础Paxos算法，提升其性能，以符合不同应用的需要。1996年，Lampson发表了一篇论文，在这篇论文中，大量引用了Lamport的工作，包括那篇尚未发表的Paxos论文。
Lampson的摇旗呐喊，直接导致了Paxos论文的正式发表。
这之后，涌现出了一系列Paxos的研究文献。1999年Prisco、Lampson和Lynch在理论计算机科学发表了一篇文章，重新描述和证明了Paxos算法，并分析了其时间开销和容错性。
Liskov等人在1999年提出了PBFT（实用的拜占庭容错算法），这实际上也是Paxos的一个变种，被Lampson称为Byzantine Paxos，该算法对基础Paxos进行了改进，使其可以处理拜占庭错误。
Gafni和Lamport在2000年提出了Disk Paxos，这可以认为是Paxos基于磁盘的版本，以支持持久化。
随后Lamport在2004年和2006年分别提出了Cheap Paxos和Fast Paxos，Cheap Paxos提升了算法的容错性，而Fast Paxos则降低了消息延迟。
2007年谷歌公司研究小组所提出的Multi-Paxos则将基础Paxos中2阶段简化为1阶段，提高了效率。
2001年，Lampson的论文“The ABCD‘s of Paxos”，对当时已有的Paxos进行了梳理，分为四类：Abstract Paxos、Classicla Paxos、Byzantine Paxos、以及Disk Paxos。
通过这些描述，我们可以看出，Paxos已经呈现出百花齐放的趋势，并且已经引起了工业界的注意。

第三个阶段，硕果累累。本阶段，Paxos开始在工业界得到了广泛应用。这一阶段可以认为是从2006年开始的。在那一年谷歌有两篇影响深远的论文发表在OSDI上。
事实上，到目前为止我们所遇到的解决异步共识问题的实用算法，其核心都是Paxos。
上述两篇论文可以说是揭开了大数据管理的序幕，而Paxos则在大数据管理的核心技术（容错）中扮演了极为重要的角色。在这之后，Paxos逐渐被工程技术人员了解，在工业界得到了越来越多的应用。

典型应用场景
下面主要介绍Paxos常用的应用场合，我们会简单介绍一下应用方向，然后介绍典型的案例。
数据库备份
Paxos最常见的应用场景是数据库备份，保证数据在多个节点的一致性。工业界在这方面的典型系统包括Chubby（谷歌）、ZooKeeper（yahoo！的Hadoop项目）、Nutanix（Vmware）、以及PhxPaxos（腾讯微信）
Chubby使用paxos来保证日志在每个副本的一致性，Paxos算法可以确保每个副本的本地日志具有相同的内容，在这之上是高容错的分布式数据库层，Chubby被应用在谷歌的多个项目中，包括GFS和Bigtable。
ZooKeeper可以看做是一个开源的Chubby实现，其设计思想类似于Paxos，但有细微差别。基于ZooKeeper，Haddop可以提供强一致保证的分布式文件系统。ZooKeeper在雅虎内部应用在多个项目中，包括HBase。
Vmware开发的Nutanix分布式文件系统，是其虚拟计算平台的核心，该系统负责管理所有的元数据和数据。NDFS具有极高的容错能力，可以确保节点发生故障时数据的可用性和一致性。
该系统采用Paxos来保证数据的强一致性，并采用了仲裁来进行领导节点的选举。
PhxPaxos是微信后台团队自主开发的一个类库，基于Paxos算法思想，实现多机的状态拷贝。基于PhxPaxos，可以方便的实现将单机状态扩展到多机，达到容错的强一致性多机状态复制的目的。
该类库已在腾讯内部，特别是微信系统中得到了严格的工程验证，目前已经开源。

NameServer
网络中每个节点都有一个地址，网络能根据消息的目标地址将消息准确送到对应的节点。域名服务器的作用就是将一个节点或服务的名称转换为对应的位置或地址。
一个中心域名服务器，必须位于一个众所周知的地址，且永不改变。但当这个中心域名服务器崩溃时，整个网络都崩溃。
一个中心域名服务器，也需要一个极多的存储空间，并且可能导致消息过载。为了解决上述问题，我们可以采用分布式域名服务器。
通过Paxos算法来管理域名服务，则可保证系统的高可用性，将可用的服务分配给合适的客户端。

Config配置管理
通常对于小的系统，我们习惯采用手工修改配置文件的方法，这样做有两个问题，其一是容易出错；其二，若系统运行在多个节点上，手工修改难以保证多个节点的状态是一致的。
因此对于大规模的应用系统，特别是分布式的应用，我们必须采用自动化的方式来统一修改配置文件。
目前一个流行的做法，是采用ZooKeeper（核心是Paxos），将配置文件放到ZooKeeper的某个目录上，然后各个程序对这个目录节点进行监听。若配置发生改变，各个节点上的应用程序会收到通知，自动修改配置。

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

客户端/服务器

定义2.1节点Node：系统中一个工作单元被称为节点（Node）。在一个计算机网络中，所有的计算机都是节点。在经典的客户端/服务器模式下，服务器和客户端都是节点。在本文中，系统的节点总数为n。
模型2.2消息传递Message Passing，我们在消息传递模式下研究由一组节点构成的分布式系统。每个节点都能进行本地运算，并可以向所有其他节点发送消息。
我们从最小的分布式系统（仅包含两个节点）开始。该系统中有一个客户端节点，它希望操作（比如存储或更新）在远程服务器节点上的数据。
算法2.3朴素的客户端/服务器算法：客户端每次向服务器发送一条命令。
模型2.4消息丢失Message Loss，在存在消息丢失的消息传递模式下，任何一条消息都不能保证可以安全地到达消息接收者。
一个相关的问题是消息损坏，即收到了一条消息，但是其内容已经损坏了。实际上，与消息丢失相比，我们可以更好的处理消息损坏，比如在消息中增加校验码。
如果消息丢失，则算法2.3不能正常工作。因此我们需要一点小改进。
算法2.5 带确认的客户端/服务器算法：1、客户端每次向服务器发送一条命令；2、服务器每收到一条命令，都会发送一条确认信息；3、如果客户端没有在一个合理的时间内收到确认信息，将重新发送命令。
每次发送一条命令，意味着如果一个客户端发送了一条命令c，那么在它收到服务器对c的确认信息之前，它将不会发送任何新的命令c`
不但客户端发送的消息可能丢失，服务器发送的确认消息也可能丢失。如果一条确认消息丢失，那么客户端可能重新发送一条消息，即使该消息已经被服务器接收且执行。
　　为了避免重复执行相同的消息，我们可以给每条消息加上序列号，这样接收者可以辨识出重复的消息。
这个看似简单的算法，是很多可靠协议的基础，比如TCP。
算法可以很容易的扩展到多个服务器的场景：客户端发送一条命令给每个服务器，一旦客户端收到所有服务器的确认信息，就可以认为该命令已被成功执行。
但是如何处理多个客户端的情况呢？

模型2.6可变消息延迟，在实际应用中，消息传输花费的时间是不同的，即使在相同的一对节点间传输消息，所花费的时间也可能不同。
本章假定都是可变消息延迟。
定理2.7如果算法2.5在多个服务器和多个客户端间运行，服务器接收到的命令顺序可能是不同的，这将导致不一致的状态。
证明：如果我们有两个客户端u1和u2，以及两个服务器s1和s2。两个服务器都在维护同一个变量x的值，起始状态x=0。两个客户端都在向服务器发送命令更新x的值。
u1的命令是x=x+1，而u2的命令是x=2x，假设两个客户端同时发送他们的命令，因为有消息延迟，有可能s1先收到u1的命令，而s2先收到u2的命令。
于是在s1上执行两个命令的结果是x=（0+1）2=2，而在s2上计算的结果则是x=02+1 = 1
定义2.8状态复制State Replication，对于一组节点，如果所有的节点均以相同的顺序执行一个命令序列（可能是无限的）c1、c2、c3...，则这组节点实现了状态复制。
状态复制是分布式系统的基本性质。
对于金融科技行业的从业人员来说，状态复制经常等同于区块链。在第7章中，我们将讨论比特币区块链，这实际上是实现状态复制的一种方式。我们也将在其他章节看到，还有很多值得认识的类似概念，他们有着不同的特点。
因为单个服务器可以天然实现状态复制，我们可以将单个服务器视为一个串行化器。通过让串行化起来分发命令，自动对请求排序并获得状态复制。

算法2.9借助单一串行化器实现状态复制。1所有的客户端都向串行化器发送命令，每次发送一条；2、串行化器将所有命令逐条转发给所有服务器；
3、针对某条命令，一旦串行化器收到所有的确认信息，它通知发送该命令的客户端命令已被成功执行。
这个想法有时也被称为主从复制Master-Slave Replication。但是如何处理节点故障呢？很显然串行化器是一个潜在的单点故障。
我们是否可以构造一个更分布式的方法来解决状态复制？与其直接构造一个一致的命令序列，不如换一个思路，想办法确保在任何时候最多只有一个客户端在发送命令。也就是采用互斥和各自加锁的思想。
算法2.10两阶段协议。阶段1：客户端向所有服务器请求锁。阶段2：如果该客户端成功获得了所有服务器的锁，则该客户端以可靠的方式向每个服务器发送命令，随即释放锁。
否则，该客户端释放已获得的锁，该客户端等待一段时间，再重新进入阶段1。
这个想法曾出现在多个领域中，也有着不同的名称，比如两段锁协议2PL。
另一个例子是两阶段提交协议2PC，典型场景是数据库系统。第一阶段被称为事务的准备阶段，第二阶段中这个事务或提交，或撤销。
两阶段提交过程并非由客户端启动，而是在一个被选定的服务器上执行，这个服务器节点通常被称为协调者。
一般认为，如果节点可以在宕机之后恢复，较之一个简单的串行化器，2PL和2PC能够提供更好的一致性保证。特别对在节点宕机之前就启动的事务来说，存活的节点或许能和宕机的节点保持一致。
在使用了一个额外阶段（3PC）的改进协议中，这个优点更为明显。
2PC和3PC的问题是，它们没有很好的处理异常。
算法2.10真的能很好的应对节点崩溃吗？不是！实际上它甚至比那个简单的序列器方法更糟。算法2.9只要求一个节点必须正常工作，但是算法2.10要求所有服务器都能正常响应请求。
如果我们仅仅得到了一部分服务器的锁，算法2.10能否正常工作？获得过半数节点的锁是否就足够了？
如果两个或更多的客户端同时企图获得大部分的锁，会发生什么情况？客户端是否必须放弃他们已经获得的锁，以避免死锁？怎么做？如果客户端在释放锁之前就发生故障，又该怎么办？我们是否需要一个与锁稍微不同的概念？

Paxos（基于消息传递的一致性算法）

定义2.11票ticket 一张票ticket是一个弱化形式的锁，具有下面的性质：1、可重新发布：一个服务器可以随时发布新的票，哪怕前面发布的票还没有被释放。
2、票可以过期：当客户端使用一张票t来给服务器发送消息时，仅当t是最新发布的票时，服务器才会接收。
评论：宕机问题被顺利解决，如果一个客户端在得到一个票之后宕机了，其他的客户端不会受到影响，因为服务器会发布新的票。
票可以使用计数器来实现，每当服务器收到一个发布票的请求时，将计数器加1.这样当客户端尝试使用某个票时，服务器可以判定该票是否已经过期。
我们如何使用票？我们能简单的将算法2.10中的锁用票代替吗？我们需要增加至少一个额外阶段，因为只有客户端知道在阶段2中是否有半数票时有效的。
该算法是有问题的，假设u1是第一个成功地在过半服务器上存储了命令c1的客户端。但是u1很慢，在它告知所有服务器执行命令时，另一个客户端u2在部分服务器上将命令更新为c2.
然后u1告诉所有的服务器执行所存储的命令。此时部分服务器执行了c1，而另一部分执行了c2。
注：与锁不同，票只是检查服务器当前是否空闲。得到票并不意味着服务器会为客户端保留位置，客户端必须马上去竞争。

算法2.12朴素的基于票的协议，阶段1：客户端向所有的服务器请求一张票。
阶段2：如果收到过半数服务器的回复，客户端将获得的票和命令一起发送给每个服务器。服务器检查票的状态，如果票仍然有效，则存储命令并给该客户端一个正反馈信息。否则客户端等待，并重新进入阶段1。
阶段3：如果客户端从过半服务器得到了正反馈，那么客户端告诉所有的服务器执行之前存储的命令。否则客户端等待，并重新进入阶段1.
如何解决这个问题呢？我们知道如果要修改u1存储在服务器上的命令，u2必须使用比u1更新的票。因此当u1的票在阶段2被接收之后，u2必须在u1在服务器上存储命令之后再拿到它的票。
注：如果u2在u1存储命令之前就得到了它的票，则u1的存储行动会失败，因为服务器会发现u1的票失效了，这样在阶段3，u1就不会要求服务器执行命令。
一个想法，如何在阶段1，一个服务器不但发布票，而且也发布它当前存储的命令，那么u2就知道u1已经存储了命令c1，u2可以不要求服务器存储命令c2，而是继续存储c1.
这样两个客户端都尝试存储和执行相同的命令，那么谁先谁后就不再是个问题。
但是服务器所存储的命令不一定相同，那么在阶段1，u2就可能从不同的服务器获知了多个不同的命令，它到底应该支持哪个呢？
注意到支持最新存储的命令总是安全的。只要还不存在一个过半服务器支持的命令，客户端们就可以支持任何命令。然后一旦有一个过半支持的命令，所有客户端都必须支持这个命令。
因此为了判定哪个命令是最新存储的，服务器们必须记录存储命令所使用的票的编号，并且在阶段1把命令和响应的编号告诉客户端。
如果每个服务器都使用自己的票号，最新的票号就不一定是最大的。如果客户端们自己来产生票号，那么这个问题可以解决！
注：我们需要一个全局一致的票号，因此不能让每个服务器自己维护一个本地的计数器来产生票号。一个巧妙的办法是让客户端自己来决定下一个票的编号t，然后去向所有服务器请求票号为t的票。
服务器在收到请求后，先将t和本地计数器比较，只有t大于本地计数器的值时，服务器才会发布票，同时将本地计数器更新为t。这样我们就可以得到一个符合2.11定义的要求，且全局一致的产生票号的方法。

算法2.13
初始化：客户端，等待执行的命令c，当前尝试的票号c=0；服务器，当前已发布的最大票号Tmax=0，当前存储的命令C，用来存储命令C的票号Tstore
阶段1: 客户端，t=t+1，向所有服务器发送消息，请求编号为t的票号；服务器，如果t>Tmax，则Tmax=t，回复OK（Tstore，C）
阶段2：客户端，如果过半服务器回复ok，选择Tstore值最大的（Tstore，C），c=C，向这些回复了ok的服务器发送消息propose(t, c)；
　　服务器，如果t=Tmax，则执行C=c，Tstore=t，回复success
阶段3：客户端，如果过半服务器回复success，向每个服务器发送消息execute（c）
与前边的算法不同，这个算法没有明确标出在哪个位置，客户端可以跳转到阶段1并且开始新的尝试。实际上，这并不是必要的，因为一个客户端可以在算法的任何位置取消当前的尝试，并且开始新一轮尝试。
这样的方式，不明确标出何时开始新的尝试，让我们不需要操心如果选择合适的超时值。我们现在更关心正确性，而正确性和什么时候开始新的尝试是独立的。
在阶段1和阶段2，如果票已过期，可以让服务器发送负的反馈，这样可以提高性能。
连续两次尝试之间的等待时间可以用随机函数确定，这样可缓和不同节点之间的竞争。

引理2.14 我们将客户端发送的一条消息propose（t，c）称为一个内容是(t,c)的提案。如果一个提案(t,c)被存储在过半服务器上，则该提案被选中。
　　如果已经存在一个被选中的propose(t,c)，则对于后续每个propose(t', c')，c'=c将始终成立(t'>t)
证明，对于每一个票号t，最多只能有一个提案。根据算法，客户端先向所有服务器发送消息，请求编号为t的票。而只有在收到过半服务器对编号为t的这张票的ok回复之后，客户端才会发送一个提案。
　　因此每个提案，都可以用它对应的票号t来唯一标识。
下面我们用反证法来证明，假设至少存在一个提案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)，根据算法，每个客户端必须采纳已经存储且票号最高票号的命令，于是该协议将提议c而不是c’。
根据算法，只有一种可能使得该客户端不采纳c，如果该客户端从某服务器得知另一个提案propose(t,c)已经被存储，且c不等于c，且t>t。
但是在这种情况下，一定存在一个客户端已经发送了提案propose(t,c)，且t<t*<t'。于是这就与我们的假设矛盾，t'是所有t之后发布的提案中最小的票号。

定理2.15 如果一条命令c被某些服务器执行，那么所有服务器最终都将执行c。
根据引理2.14，我们得知一旦一个关于包含c的提案被选中，后续的每个提案都采纳c。由此可见，所有成功的提案都将采纳相同的命令c。
这样只有采纳了命令c的提案会被选中。此外，由于客户端只会在一条命令被选中后，告诉服务器执行该命令，因此每个客户端将最终告知所有的服务器执行命令c。
如果拥有第一个成功提案的客户端没有宕机，它将直接告诉所有的服务器执行命令c。
但是，如果客户端在告诉任何一个服务器执行命令之前就宕机了，服务器们将只有等到下一个客户端成功获得提案之后才可以执行命令。
一旦一个服务器接收到一个请求去执行命令，它可以通知所有后边到达的客户端：已经有一条命令被选中了，这样客户端可以避免继续发送提案。
如果超过一半的服务器宕机，Paxos将不能工作，因为客户端不能再取得过半数服务器的认可。
最初版本的Paxos包含三个角色，提案者、接受者、以及学习者。学习者不做任何事情，只是从其他节点学习哪个命令被选中了。
我们只让每个节点承担一个角色，在某些场景下，一个节点可以承担多个角色。比如在一个P2P的场景下，每个节点既是服务器，又是客户端。
上述算法，必须信任客户端们（提案者们）会严格遵守协议。然而这个假设在很多场景下并不合理。在某些场景下，提案者的角色可以被一组服务器承担，客户端们需要联络提案者，并用他们的名义来发布提案。
到现在为止，我们仅仅讨论了如何通过Paxos来使一组节点达成一致性决议，来执行一条命令。单独一条决议，被称为Paxos的一个实例（instance)。

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

说明

两阶段协议已经存在了很长时间，并且不止一个原创者。在Gray的书中，可以找到关于这个概念的较早的描述。
Lamport在1989年提出了Paxos。但是这个名称是怎么来的呢？Lamport在论文中描述了一个虚拟的希腊小岛-Paxos，并假定为了解决在岛上的议会中的投票问题。
他非常喜欢这个想法。甚至以一个印第安纳的考古学家的身份做过几个报告。当论文第一次投稿的时候，大多数评委都对这个议会故事感到困惑，无法理解算法的目的和思想。
论文因此被拒绝发表！Lamport拒绝修改论文，稍后它表示不开心，因为这个领域的学者如此缺乏幽默感。
几年之后，随着应用的发展，Paxos协议的用途变得更为广泛。Lamport于是从抽屉里翻出这篇被拒绝的论文，并发给他的几位同事。
这些同事们都表示很喜欢这个想法，于是Lamport决定重新投稿，和8年前相对，论文基本没改。
不过鉴于这篇论文确实太难懂了，Lamport后来特地写了一篇关于Paxos的说明。