Paxos漫谈

 

上一篇币爷和大家一起探究了区块链的核心算法之一，Paxos算法。实际上，上一篇的干货不少；同样的，需要大家具备计算机语言语法和数学逻辑基础知识背景，才能更好地理解。

 

 

如题，这次给大家聊聊Paxos的发展史和典型应用场景，比较有趣味性；而且数学公式、定理证明本场缺席，也比较容易理解

发展

Paxos的整个发展历程大概可以分为三个阶段。

第一阶段，萌芽期，大致是1988-1996年。1988年，Liskov等人在PODC(ACM Symposium on Principles of Distributed Computing)上发表了一篇文章[OL88]，提出了一个在副本出现宕机情况下仍能正常工作的主从备份算法，该算法与Paxos在本质上是一致的[Lam01]。

Leslie Lamport在1989年提出Paxos这个名称，但他的论文因为过于艰涩，未能发表。Lamport企图用一个寓言故事来描述他的算法思想，却没有得到评委的认同。这篇文章直到1998年才正式发表[Lam98]，那时分布式共识问题已经引起了广泛重视。从时间上看，Liskov的论文更早一些，但是由于种种原因，特别是图灵奖得主Butler Lampson的推崇，Lamport的工作影响力更广。

 

 

后来学界和工业界也基本都采纳了Paxos这个名称。值得一提的是，Liskov在分布式共识领域同样做出了巨大的贡献。比如，目前风靡一时的PBFT算法[MC99]就出自Liskov的研究团队。Lampson将这两篇都归为“基础Paxos”[Lam01]，以与后续其他版本的Paxos区分开来。在这个时期，虽然陆续有不少工作跟进，但整体仍处于不温不火的状态。

第二个阶段，即1996-2007年，这个时期可以用百花齐放来形容。Paxos引起了很多学者关注，涌现出一批Paxos的不同版本，这些Paxos的变种从不同侧面完善了基础Paxos算法，提升其性能，以符合不同应用的需要。1996年，Butler Lampson发表一篇论文“How to Build a Highly Availability System using Consensus”[Lam96]。在这篇论文里，Lampson引用了大量Lamport的工作，包括那篇尚未发表的Paxos论文（当时还是技术报告的形式）。Lampson的摇旗呐喊，直接导致了Lamport论文的正式发表（与8年前第一次投稿相比，几乎未改）。

 

 

这之后，涌现了一系列关于Paxos的研究文献。1999年，Roberto De Prisco、Butler Lampson以及Nancy Lynch（又一个分布式计算领域的大牛）在理论计算机科学(Theoretical Computer Science)发表了一篇文章[PLL97]，重新描述和证明了Paxos算法，并分析了其时间开销及容错性。

Liskov等人在1999年提出了PBFT（实用的拜占庭容错算法）[MC99]，这实际上也是Paxos的一个变种，被Lampson称为Byzantine Paxos，该算法对基础Paxos进行了改进，使其可以处理拜占庭错误。

 

 

Eli Gafni和Lamport在2000年提出了Disk Paxos[GL03]，这可以认为是Paxos基于磁盘的版本，以支持持久化。随后，Lamport在2004年和2006年分别提出了Cheap Paxos[LM04]和Fast Paxos[Lam06]，Cheap Paxos提升了算法的容错性，而Fast Paxos则降低了消息延迟。2007年，谷歌公司研究小组所提出的Multi-Paxos[CGR07]则将基础Paxos中2阶段简化为1阶段，提高了效率。2001年，Lampson的论文“The ABCD's of Paxos”[Lam01]，对当时已有的Paxos进行了梳理，分为四类：

Abstract Paxos,Classicla Paxos,Byzantine Paxos，以及Disk Paxos。通过以上描述，我们可以看出，Paxos已经呈现出百家争鸣、百花齐放的趋势，并且引起了工业界的注意。

第三阶段，硕果累累。本阶段，Paxos开始在工业界得到了广泛应用。这一阶段可以认为是从2006年开始的。在那一年，谷歌公司有两篇影响深远的论文发表在OSDI上，一篇是“Bigtable:A Distributed Storage System for Structured Data”,另一篇是“The Chubby lock service for loosely-coupled distributed syetems”。在第二篇论文中，特别提到了“Indeed,all working protocols for asynchronous consensus we have so far encountered have Paxos at their core”（事实上，到目前为止我们所遇到的解决异步共识问题的实用算法，其核心都是Paxos）。

上述两篇论文可以说是揭开了大数据管理的序幕，而Paxos则在大数据管理的核心技术（容错）中扮演了极为重要的角色。在这之后，Paxos逐渐被工程技术人员了解，在工业界得到越来越多的应用。接下来，我们来看看Paxos具体在工业界的应用情况。

典型应用场景

1、数据库备份

Paxos最常见的应用场景是数据库备份(Database Replication),保证数据在多个节点上的一致性。工业界在这方面的典型系统包括Chubby（谷歌公司），Zookeeper（Yahoo!的Hadoop项目），Nutanix（Vmware），以及PhxPaxos（腾讯微信）。

 

 

Chubby使用了paxos来保证日志在各个副本上的一致性，Paxos算法可以确保每个副本的本地日志具有相同的内容，在这之上是高容错的分布式数据库层。Chubby被应用在谷歌的多个项目中，包括GFS和Bigtable。

Zookeeper可以看作是一个开源的Chubby实现，其设计思想类似于Paxos，但有细微差别。基于Zookeeper，Hadoop可以提供强一致性保证的分布式文件系统。Zookeeper在Yahoo!内部已经成功应用在多个项目中，包括HBase及Yahoo! Message。

 

 

Vmware开发的Nutanix分布式文件系统(NDFS)是其虚拟计算平台的核心，该系统负责管理所有的元数据和数据。NDFS具有极高的容错能力，可确保节点发生故障时数据的可用性和一致性。该系统采用Paxos来保证数据的强一致性，并采用了仲裁（Quorum）来进行领导节点的选举。

PhxPaxos是腾讯公司微信后台团队自主研发的一个类库，基于Paxos算法思想，实现多机的状态拷贝。基于PhxPaxos，可以方便地实现将单机状态扩展到多机，达到容错的强一致性多机状态复制的目的。该类库已在腾讯内部，特别是微信系统中得到了严格的工程验证，目前已经开源。

2、Name Server

网络中每个节点都有一个地址，网络能根据消息的目标地址将消息准确送到对应的节点。域名服务器（Name Server）的作用就是将一个节点或服务的名称转换为对应的位置或地址。一个中心域名服务器必须位于一个众所周知的地址，且永不改变。但当这个中心域名服务器崩溃时，整个网络都将崩溃。一个中心域名服务器也需要一个极多的存储空间，并且可能导致信息过载。为了解决上述问题，我们可以采用分布式域名服务器。

 

 

通过Paxos算法来管理域名服务，则可保证系统的高可用性，将可用的服务分配给合适的客户端。

3、Config配置管理

通常对于小的系统，我们习惯采用手工修改配置文件的方法，这样做有两个问题，其一是容易出错；其二，若系统运行在多个节点上，手工修改难以保证多个节点的状态是一致的。因此，对于大规模的应用系统，特别是分布式的应用，我们必须采用自动化的方式统一修改配置文件。

 

 

目前一个流行的做法是采用Zookeeper（核心是Paxos），将配置文件放到Zookeeper的某个目录上，然后各个程序对这个目录节点进行监听。若配置发生改变，各个节点上的应用程序就会收到通知，并自行修改配置。

                                  【全文完，觉得不错的话关注“评币”吧~】