作者：（美）Roger Wattenhofer（罗格.瓦唐霍费尔）
出版社：电子工业出版社
格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT
区块链核心算法解析试读：
The Science of the Blockchain， Roger Wattenhofer. Copyright © 2016 Roger Wattenhofer Chinese translation Copyright © 2017 by Publishing House of Electronics Industry.
本书中文简体版专有出版权由Roger Wattenhofer授予电子工业出版社，未经许可，不得以任何方式复制或者抄袭本书的任何部分。
版权贸易合同登记号 图字：01-2017-1717
图书在版编目（CIP）数据
区块链核心算法解析/（瑞士）罗格·瓦唐霍费尔（Roger Wattenhofer）著；陈晋川等译.—北京：电子工业出版社，2017.8（金融科技丛书）
书名原文：The Science of the Blockchain
ISBN 978-7-121-31328-8
Ⅰ.①区… Ⅱ.①罗…②陈… Ⅲ.①电子商务-支付方式-研究 Ⅳ.①F713.361.3
中国版本图书馆CIP数据核字（2017）第076211号
责任编辑：高洪霞
印 刷：
装 订：
出版发行：电子工业出版社
北京市海淀区万寿路173信箱 邮编100036
开 本：720×1000 1/16 印张：10.25 字数：151.2千字
版 次：2017年8月第1版
印 次：2017年8月第1次印刷
定 价：59.00元
凡所购买电子工业出版社图书有缺损问题，请向购买书店调换。若书店售缺，请与本社发行部联系，联系及邮购电话：（010）88254888，88258888。
质量投诉请发邮件至zlts@phei.com.cn，盗版侵权举报请发邮件至dbqq@phei.com.cn。
本书咨询联系方式：（010）51260888-819，faq@phei.com.cn。推荐序I
毫无疑问，互联网是20世纪最伟大的发明之一。随着信息、通信技术的蓬勃发展，互联网已渗透到生产、贸易、通信、学习、娱乐等人们生活的几乎所有方面，更使很多方面产生了革命性的变化。近十年来，在互联网的基础上，移动互联网、物联网，乃至智能互联网得到了新的发展。人工智能、深度学习、机器学习等一系列技术和理论的新发展，又促使互联网应用面临更加蓬勃发展的新局面。在众多的互联网新应用中，不得不提及区块链。
仿佛一夜之间，互联网创业圈和金融圈都在谈论区块链。坚信者认为，去中心化的、不可篡改的分布式账本，能够重构金融体系，甚至重塑整个社会。不知区块链之父当初是否曾预见到如今区块链的热度？
如今，比特币及其他虚拟货币已广泛流行，并且引起了监管当局的关注；政府、巨头和创业公司，也都积极参与到区块链的各种应用的探索中。然而，在互联网土壤上生长出的各种技术和应用中，区块链及其应用还很年轻。自2009年比特币诞生至今，也才仅7年，更不要说区块链在互联网金融领域和其他领域的应用。
作为一个一直关注新技术发展的互联网“老兵”，我曾数次应邀参加中关村区块链产业联盟的活动，和互联网领域的年轻创业者、专家、学者一起，探讨、推动区块链的发展和应用。我们的年轻人，尤其是年轻的创业者，他们的大胆探索和勇于创新，令我感到欢欣鼓舞。
目前，介绍区块链应用的书籍非常多，而从理论、技术层面介绍区块链的书比较少。很高兴看到有这样一本从理论、技术层面介绍区块链的书籍出版。希望大家能耐心读读这本书，更深入地理解区块链技术，从而有助于推动区块链技术的发展和应用。高卢麟博士中国互联网协会副理事长美国芝加哥马歇尔法学院客座教授推荐序II
区块链（Block Chain）原本只是比特币网络的一种记账技术，近几年来却在金融、知识产权、数据交易、电子证照、慈善、新能源等领域引起了广泛的关注。为什么就突然“火”起来了？究其原因，我的理解是：第一，区块链具有去中心化的特征，不以参与交易的任何一方为中心。去中心化可以带来效率的提升和成本的降低，直接增加了企业的利润。第二，区块链具有去信任的特征，也就是假定参与交易的任何一方都不是可信任的。我们通过记录交易的信息，而且是不可抵赖的，来迫使交易各方遵守诚信。因此也可以说，区块链技术很好地回应了目前互联网的痛点——诚信问题。第三，区块链作为互联网的一种基础设施，也可以看作是一种分布式数据库，其核心就是参与交易的多方如何达成共识。在分布式数据库中，为了处理并发事务，需要在不同的节点上维护一个全局一致的状态，传统的做法是通过两阶段锁协议来实现。另一方面，通常大型应用会维护多个数据库副本，以实现数据库的恢复。在多个数据库副本之间维护一致的状态也是一个经典的难题，而解决这个难题的最佳算法实践正是本书中的重点内容——Paxos算法。这个算法在大数据管理时代更是大放异彩，在BigTable，Hadoop等多个大数据计算平台上得到应用。
目前市场上关于区块链的书籍很多，但大多偏于介绍区块链的基础知识及应用前景，纯技术的书籍相对较少。本书着眼于区块链的核心问题——拜占庭共识，针对不同的应用场景，介绍了适用的分布式共识算法。书中包含了很多算法及证明，深入剖析了共识算法的核心思想。本书详细介绍了在不同应用场景下的分布式共识算法，包括单纯宕机错误（节点只可能发生宕机，但不会恶意犯错），拜占庭式错误节点（可以认为是恶意的节点，呈现任何行为），允许消息签名，仲裁系统，弱一致条件下的共识等，并介绍了分布式存储的一些基础知识（如一致性哈希）。书中提到的很多算法，特别是PBFT，目前是区块链的重要分支——联盟链的核心算法。
对于从事区块链的研究者或工程技术人员来说，共识算法是需要认真弄清楚的内容。虽然存在不少开源的共识算法或区块链框架，但不同的应用对共识算法的要求是不一样的，应该根据应用的特点选择合适的共识算法，甚至对已有的共识算法做必要的剪裁。要做到这一点，就必须理解基础的分布式共识算法。而这就是本书的最大价值。
本书译者之一，陈晋川博士，自2009年从香港理工大学毕业后加入中国人民大学，一直在我的研究团队里工作。在大数据、分布式数据管理等领域做出了不少优秀成果。晋川从去年开始关注区块链，他在查阅很多文献之后，发现关于区块链核心技术部分的资料很少，很难把握其精髓。在看到本书原著之后，他感觉这正是目前市场所缺少的干货，就决定将其翻译出来。本书内容艰深，为了准确、清晰地将内容译为中文，晋川投入了大量心血。作为一线科研工作者，能在背负巨大科研考核压力的情况下，投入如此多精力从事翻译工作，殊为不易。
其实，这本书不能算是严格意义上的翻译，译者除了原稿翻译之外，还增加了很多译者自己的注释，对书中的算法、公式进行注解（作者很多地方写得较为简略）。另外，书中还增加了两章新的内容。一章是介绍Paxos算法的发展史和在工业界的应用情况，另一章是对比分析当前主流的两个共识机制，比特币的PoW和私有链的PBFT。现在都讲究“混搭”，这本译著也是一种形式的混搭。杜小勇中国计算机学会数据库专委会主任教育部数据工程与知识工程重点实验室主任推荐序III 智能时代的区块链“身为一个智能时代的潮人，谁的口袋里还不装着几块比特币？”
近年来，比特币作为第一种数字加密货币，受到了褒贬不一的评价；其价格一路飞涨，但走向主流货币之路却是“路漫漫其修远兮”。但是，作为比特币的核心底层技术，区块链技术的受关注程度却一路飙升。自2014年以来，国内外多家著名机构在这一研究方向上已经累计投入了数百亿美元。其研发范围已经远远超越单纯的数字加密货币，遍及银行、保险、物流、物联网、资产交易、公证与鉴别、社交通信等领域。甚至有人宣称，未来的社会及政府都可以架构于区块链之上。
区块链为何会受到如此广泛的关注？究其原因，其核心特征，去中心化、去信任化、智能合约等，正好满足未来互联网持续发展所要求的信息的高度自动化和高度程序化的安全流转需求。我们知道，互联网作为一个连接媒介，连接了世界上一部分的信息、数据、交互和交易；移动互联网更是将连接范围进一步扩大至几乎所有人类活动的范围，基本完成了人类活动的数字化。
在技术驱动下，人类生活方方面面的数据量开始激增，大规模计算出现了分布化和并行化的特点。在此基础上，人工智能第三次浪潮汹涌而来，进一步衍生了对高度自动化和高度程序化的信息流转的需求：非自动化环节必然被不断削减；信息的审核和控制将不再受限于任何一个权威性的中心节点，也不应该被任何一个参与节点伪造、篡改和否认。对于上述需求，区块链技术可以相对完美地提供解决方案。因此，可以预见，区块链技术将会是智能时代数据存储、传输、分发最有竞争力的解决方案之一。
区块链作为一个分布式的数据存储、传输和分发解决方案，其核心在于如何在一个分布式、无受信节点的环境下，自动形成共识（consensus）的机制。所谓共识机制，是指分布式系统中全部节点（或者大部分节点）就某条数据的真实性或者某条交易的价值达成一致，并据此更新各节点记录的一种机制。不难看出，面对不同的场景、不同的应用需求，需要设计并实施不同的共识机制。这就需要对共识机制在理论层面、技术层面有深入的理解。在智能时代，区块链参与节点将可能是一个智能体，区块链系统也将可能是一个多智能体系统。系统中节点的数量和行为可能是基于人工智能技术自动产生和调整，而不是基于程序员所编写的固定规则。这种情况下，要想利用共识机制充分保证区块链的安全运行，需要对共识机制更为深刻的理解。
国内关于区块链的书籍已经有很多了，但大多都是在谈应用、谈理念或者在谈相关的投融资，真正涉及技术细节的书籍相对较少。《区块链核心算法解析》以共识机制为主体，系统介绍了区块链所涉及的各种关键定理和证明，也给出了相应算法。难能可贵的是，作者还结合实例讲述了不同场景下的共识机制的设计方法。这是一本关于区块链核心技术的系统论著，对于区块链科研和应用人员都具有很高的参考价值。戴斌国防科技大学机电工程与自动化学院副总工程师前 言
当你和从事金融科技（FinTech）的朋友在一起交谈时，不可避免地会注意到一个非常流行的词——区块链。听上去，它就像Internet那样重要。某些金融科技领域的朋友认为区块链是一段神奇的代码，它可以使一个分布式系统的参与者们就系统的状态达成共识，从而追踪系统的变化。区块链这个词语是从比特币借用的，然而，早在区块链或者比特币出现之前，共识技术（或协定技术）（Agreement Techniques）就已经在分布式系统领域中存在了。曾经出现过各种各样的概念和协议，各有其优点和缺点。
本书的目的是深入剖析这项当前最引人注目的技术——区块链。如果你是一名开发者（不管是否在金融科技领域），本书将帮助你更好地理解：在你研发的分布式系统中，什么是对的，什么是错的，什么是可能的，而什么是不可能的。
内容简介
本书介绍了构建容错的分布式系统所需的基础技术，以及一系列允许容错的协议和算法，并且讨论一些实现了这些技术的实际系统。
本书中的主要概念将独立成章。每一章都以一个小故事开始，从而引出该章节的内容。算法、协议和定义都将以形式化的方式描述，以便于读者理解如何实现。部分结论会在定理中予以证明，这样读者就可以明白为什么这些概念或算法是正确的，并且理解它们可以确保实现什么。其他的大部分内容将以评论的方式出现。这些评论将讨论各种各样非正式的思考，并且为后续内容做好铺垫。就算不阅读这些评论，读者们也可以掌握章节的精髓。此外，为了便于读者寻根溯源，每一章也会讨论相关技术的发展历史。
本书将介绍不同的模型（以及模型的组合），以适用于不同的场景。本书关注的是实用的协议和系统。换句话说，我们在选择概念时，不会根据这些概念是否看起来有意思，而是根据它们是否有实际的价值。
不管怎样，希望你在本书中找到乐趣！第1章 绪论1.1 分布式系统是什么
今天的计算机系统和信息系统在本质上都是分布式的。越来越多的公司进入全球化时代，它们拥有部署在不同大陆上的成千上万的计算机。数据存储在不同的数据中心，而计算任务则运行在多台计算机上。
另一方面，我们的智能手机也是一个分布式系统。这不仅因为它很可能将你的数据存储在云端，也因为它本身就包含多个处理和存储单元。
此外，计算机的发展已经经历了一个很长的过程。在20世纪70年代早期，微型集成电路芯片的时钟频率只有1MHz左右。10年之后，在20世纪80年代早期，个人电脑的主频已经达到了10MHz。到了1990年，时钟频率达到了100MHz。到了2000年，消费者们已经用上了1GHz的处理器。仅仅几年之后的2005年，家用电脑的主频已经在3GHz到4GHz之间。然而，今天我们在市场上见到的个人电脑时钟频率依旧徘徊在3GHz到4GHz，因为CPU时钟频率已经在2004年前后基本停止增长。如果不能解决一些物理上的问题，比如过热，时钟频率将无法再显著提升。
简而言之，今天几乎所有的计算系统都是分布式的，原因如下。
·地理因素：大的公司和组织必然分布在多个地方。
·并行化：我们需要使用多核处理器或计算机集群来加速计算。
·可靠性：数据需要备份在不同的机器上以避免丢失。
·可用性：数据需要复制到不同的机器上以利于快速获取，避免可能的瓶颈，并减少延迟。
虽然分布式系统带来了很多好处，比如扩大存储容量和计算能力，甚至有可能连接地理空间上分离的区域，然而它也带来了一个很麻烦的协调问题（Coordination Problems）。协调问题非常普遍，具备不同的特点，也有着不同的称谓，诸如：区块链（Blockchain）、一致性（Consistency）、协定（Agreement）、共识（Consensus）、账单（L edger）、事件溯源（Event Soucing）等。
在分布式系统中，协调问题是很常见的。即便是一个分布式系统中的每个节点（如计算机、核、网络交换机等）几年才发生一次故障，但如果系统包含数百万个节点，那么平均每分钟都将发生一次故障。从好的方面讲，人们期待一个多节点的分布式系统可以容忍一些错误并且持续正常工作。1.2 本书概览
本书的核心概念将在第2章介绍，即定义2.8中的状态复制（State Replication）。如果一个分布式系统的所有节点在一个命令序列上取得共识（即同样一组命令按同样的顺序执行），那么我们就可以得到状态复制。在金融技术领域，状态复制常常等同于区块链。状态复制可以通过不同的算法来获得，具体取决于系统能够容忍的错误类型。
在第2章中，我们将介绍基本的定义，并且介绍Paxos算法。即使系统中少部分节点崩溃（Crash），Paxos算法也可以获得状态复制。
在第3章中，我们将明白Paxos算法可能无法成功。事实上如果我们不走运，将没有一个确定性的协议（Deterministic Protocol）能解决状态复制。然而，我们也会介绍一个快速的随机共识协议。即使有崩溃性错误，该协议也能得到状态复制。
在第4章中，将目光扩展到简单的崩溃性错误之外。我们将介绍一些应对恶意行为（Malicious Behavior）的协议，它们运行在同步或异步的系统中。此外，我们将介绍对正确行为（Correct Behavior）的不同定义。
在第5章中，我们会使用一个密码学概念，消息认证（Message Authentication）。首先介绍一个简单的同步协议，接着介绍Zyzzyva协议，这是当前最好的异步协议。当消息认证可用时，这个协议能够实现状态复制。
在第6章中，我们通过研究所谓的仲裁系统（Quorum Systems）来分析可扩展性问题。当集群的算力不足，且不能靠增加新节点来解决问题时，仲裁系统或许是一个优雅的解决方案。
在第7章中，我们介绍弱一致（Weaker Consistency）的概念，并且以比特币协议为例进行详细分析。
最后，我们在第8章中介绍了一些更弱的一致性概念，并且介绍了高可扩展性分布式存储系统（Highly Scalable Distributed Storage）的解决方案。
章节说明
关于分布式系统共识问题，已有不少很好的教科书，例如［AW04，CGR11，CDKB11，Lyn96，Mul93，Ray13，TS01］。James Aspnes还编写了一个非常好的关于分布式系统的免费教材［Asp14］。与本书类似，这些教材也主要着眼于大规模分布式系统，因此和这本书在内容上有所重叠。此外，还有不少优秀的教材着眼于小型的多核系统，比如［HS08］。
一些同事在本书写作过程中提供了大量帮助，在此一并予以致谢：Pascal Bissig，Philipp Brandes，Christian Decker，Klaus-Tycho Förster，Barbara Keller，Rik Melis，以及David Stolz（以上排名按字典顺序）。
参考文献
［Asp14］James Aspnes.Notes on Theory of Distributed Systems，2014.
［AW04］Hagit Attiya and Jennifer Welch.Distributed Computing:Fundamentals，Simulations and Advanced Topics（2nd edition）.John Wiley Interscience，March 2004.
［CDKB11］George Coulouris，Jean Dollimore，Tim Kindberg，and Gordon Blair.Distributed Systems:Concepts and Design.Addison-Wesley Publishing Company，USA，5th edition，2011.
［CGR11］Christian Cachin，Rachid Guerraoui，and Lus Rodrigues.Introduction to Reliable and Secure Distributed Programming.Springer Publishing Company，Incorporated，2nd edition，2011.
［HS08］Maurice Herlihy and Nir Shavit.The Art of Multiprocessor Programming.Morgan Kaufmann Publishers Inc.，San Francisco，CA，USA，2008.
［Lyn96］Nancy A.Lynch.Distributed Algorithms.Morgan Kaufmann Publishers Inc.，San Francisco，CA，USA，1996.
［Mul93］Sape Mullender，editor.Distributed Systems（2Nd Ed.）.ACM Press/Addison-Wesley Publishing Co.，New York，NY，USA，1993.
［Ray13］Michel Raynal.Distributed Algorithms for Message-Passing Systems.Springer Publishing Company，Incorporated，2013.
［TS01］Andrew S.Tanenbaum and Maarten Van Steen.Distributed Systems:Principles and Paradigms.Prentice Hall PTR，Upper Saddle River，NJ，USA，1st edition，2001.第2章 容错问题和Paxos算法
我们应该如何创建一个容错的分布式系统呢？本章将从一些简单的问题开始，一步步改进我们的方案，最终将得到Paxos，一个甚至可以在逆境下工作的协议。2.1 客户端/服务器[1]
定义2.1（节点（Node））.系统中一个工作单元被称为节点（Node）。在一个计算机网络中，所有的计算机都是节点。在经典的客户端/服务器模式下，服务器和客户端都是节点。本文中，如果不另外说明，系统中节点的总数为n.
模型2.2（消息传递（Message Passing））.我们在消息传递模式（Message Passing Model）下研究由一组节点构成的分布式系统。每个节点都能进行本地运算，并可以向所有其他节点发送消息。
评论：
·我们从最小的分布式系统（仅包含两个节点）开始。该系统中有一个客户端节点，它希望操作（比如存储或更新）在远程服务器节点上的数据。
模型2.4（消息丢失（Message Loss））.在存在消息丢失（Message Loss）的消息传递模式下，任何一条消息都不能保证可以安全地到达消息的接收者。
评论：
·一个相关的问题是消息损坏，即收到了一条消息，但是其内容已经损坏了。实际上，与消息丢失相比，我们可以更好地处理消息损坏，比如在消息中增加校验码。
·如果消息丢失，则算法2.3不能正常工作。因此我们需要一点小改进。
评论：
·“每次发送一条命令”意味着如果一个客户端发送了一条命令c，那么在它收到服务器对c的确认信息之前，它将不会发送任何新的′命令c。
·不但客户端发送的消息可能丢失，服务器发送的确认消息也可能丢失。如果一条确认信息丢失，那么客户端可能重新发送一条消息，即使该消息已经被服务器接收且执行。为了避免重复执行相同的消息，我们可以给每条消息加上序列号，这样接收者可以辨识出重复的消息。
·这个看似简单的算法是很多可靠协议的基础，比如TCP。
·算法可以很容易地扩展到多个服务器的场景：客户端发送一条命令给每个服务器，一旦客户端收到所有服务器的确认消息，就可以认为该命令已被成功执行。
·但是如何处理多个客户端的情况呢？
模型2.6（可变消息延迟（Variable Message Delay））.在实际应用中，消息传输花费的时间是不同的。即使是在相同的一对节点间传输消息，所耗费的时间也可能不同。
评论：
·本章假定都是可变消息延迟模式。
定理2.7.如果算法2.5在多个服务器和多个客户端间运行，服务器接收到的命令顺序可能是不同的，这将导致不一致的状态。
证明.假定我们有两个客户端u和u，以及两个服务器s和s。两1212个服务器上都在维护同一个变量x的值，起始状态，x=0。两个客户端都在向服务器发送命令去更新x的值。u的命令是x=x+1，而u的命12令是x=2·x。假设两个客户端同时发送它们的命令。因为有消息延[2]迟，有可能s先接收到u的命令，而s先收到u的命令。于是，在s11221上执行两个命令的结果是x=（0+1）·2=2，而在s上计算的结果则是2x=（0·2）+1=1。
定义2.8（状态复制（State Replication））.对于一组节点，如果所有节点均以相同的顺序执行一个（可能是无限的）命令序列c，c，12c，...，则这组节点实现了状态复制（State Replication）。3
评论：
·状态复制是分布式系统的基本性质。
·对于金融科技行业的从业人员来说，状态复制经常等同于区块链。在第7章中，我们将讨论比特币区块链，这实际上是实现状态复制的一种方式。我们也将在其他章节看到，还有很多值得认识的类似概念，它们有着不同的特点。
·因为单个服务器可以天然实现状态复制，我们可以将单个服务器视为一个串行化器（Serializer）。通过让串行化器来分发命令，自动对请求进行排序并获得状态复制。
评论：
·这个想法有时也被称为主—从复制（Master-Slave Replication）。
·但是如何处理节点故障呢？很显然，串行化器是一个潜在的单点故障（Single Point of Failure）。
·我们是否可以构造一个更分布式的方法来解决状态复制？与其直接构造一个一致的命令序列，不如换一个思路：想办法确保在任何时候最多只有一个客户端在发送命令。也就是说，我们采用互斥（Mutual Exclusion）和各自加锁（Respectively Locking）的思想。
评论：
·这个想法曾出现在多个领域中，也有着不同的名称，比如两段锁协议（Two-Phase-Locking）（2PL）。
·另一个例子是两阶段提交协议（Two-Phase Commit）（2PC），典型场景是数据库系统。第一阶段被称为事务的准备阶段，第二阶段中这个事务或者提交（Committed）或者撤销（回滚）（Aborted）。两阶段提交过程并非由客户端启动，而是在一个被选定的服务器上完成，这个服务器节点通常被称为协调者。
·一般认为，如果节点可以在宕机之后恢复，较之一个简单的串行化器，2PL和2PC能提供更好的一致性保证。特别对在节点宕机之前就启动的事务来说，存活的节点或许能和宕机的节点保持一致。在使用了一个额外阶段（3PC）的改进版协议中，这个优点更为明显。
·2PC和3PC的问题是，它们没有很好地处理异常。
·算法2.10真的能很好地应对节点崩溃吗？不是！实际上，它甚至比那个简单的序列器方法（算法2.9）更糟。算法2.9只要求一个节点必须正常工作，但是算法2.10要求所有服务器能够正常响应请求。
·如果我们仅仅得到一部分服务器的锁，算法2.10能否工作？获[3]得过半数节点的锁是否就足够了？
·如果两个或更多的客户端同时企图获得大部分服务器的锁，会发生什么情况？客户端是否必须放弃它们已经获得的锁，以避免死锁？怎么做？如果客户端在释放锁之前就发生故障，又该怎么办？我们是否需要一个与锁稍微不同的概念？2.2 Paxos
定义2.11（票（Ticket））.一张票（Ticket）是一个弱化形式的锁，具备下面的性质。
·可重新发布：一个服务器可以随时发布新的票，哪怕前面发布的票还没有被释放。
·票可以过期：当客户端使用一张票t来给服务器发送消息时，仅当t是最新发布的票时，服务器才会接收。
评论：
·宕机问题被顺利解决：如果一个客户端在得到一个票之后宕机了，其他的客户端不会受到影响，因为服务器会发布新的票。
·票可以使用计数器来实现：每当服务器收到一个（发布票的）请求时，将计数器加1。这样当客户端尝试使用某个票时，服务器可以判定该票是否已经过期。
·我们如何使用票？我们能简单地将算法2.10中的锁用票代替吗？我们需要增加至少一个额外阶段，因为只有客户端知道在阶段2中是否有过半数票是有效的。
评论：[4]
·该算法是有问题的。假设u是第一个成功地在过半数服务器上1存储了命令（c）的客户端。但是u很慢，在它告知所有服务器执行11[5]命令时（第9行），另一个客户端u在部分服务器上将命令更新为c。22然后，u告诉所有的服务器执行所存储的命令。此时，部分服务器将1执行c，而另一部分将执行c。12
·如何解决这个问题呢？我们知道如果要修改u存储在服务器上1的命令，u必须使用比u更新的票。因此，当u的票在阶段2被接受211之后，u必须在u在服务器上存储命令（第4行）之后再拿到它的21
[6]票。
·一个想法：如果在阶段1中，一个服务器不但发布票，而且也发布它当前所存储的命令。那么u就知道u已经存储了命令c。u可以2112不要求服务器存储命令c，而是继续存储c。这样，两个客户端都尝21试存储和执行相同的命令，那么谁先谁后就不再是一个问题。
·但是，服务器们所存储的命令不一定相同，那么在阶段1，u就2可能从不同的服务器获知了多个不同的命令。它到底应该支持哪一个呢？
·注意到支持最新存储的命令总是安全的。只要还不存在一个过半数服务器一致支持的命令，客户端们就可以支持任何命令。然而，一旦有一个过半数服务器一致的命令，所有客户端就必须支持这个命令。
·因此，为了判定哪一个命令是最新存储的，服务器们必须记录存储命令所使用的票的编号，并且在阶段1把命令和相应的编号都告诉客户端。
·如果每个服务器使用自己的票号，最新的票号就不一定是最大[7]的。如果客户们自己来产生票号，那么这个问题可以解决！
评论：
·与前面的算法不同，这个算法中没有明确地标出在哪个位置客户端可以跳转到阶段1并且开始新的尝试。实际上这并不是必要的，因为一个客户端可以在算法的任何位置取消当前的尝试并且开始新一轮尝试。这样的方式（不明确标出何时开始新的尝试）让我们不需要操心如何选择合适的超时（timeout）值。我们现在更关心正确性，而正确性和什么时候开始新的尝试是独立的。
·在阶段1和阶段2，如果票已过期，可以让服务器发送负的反[8]馈，这样可以提高性能。
·连续两次尝试之间的等待时间可以用随机函数确定，这样可缓和不同节点之间的竞争。
引理2.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＜t*＜t。于是这就与我们的假设矛′盾：“t是所有在t之后发布的提案中最小的票号”。
定理2.15.如果一条命令c被某些服务器执行，那么所有的服务器最终都将执行命令c。
证明.根据引理2.14我们得知一旦一个关于包含c的提案被选中，后续的每个提案都将采纳c。由此可见，所有成功的提案都将采纳相同的命令c。这样，只有采纳了命令c的提案会被选中。此外，由于客户端只会在一条命令被选中之后告诉服务器执行该命令（第20行），每个客户端将最终告知所有的服务器执行命令c。
评论：
·如果拥有第一个成功提案的客户端没有宕机，它将直接告诉所有的服务器执行命令c。
·但是，如果客户端在告诉任何一个服务器执行命令之前就宕机了，服务器们将只有等到下一个客户端成功获得提案之后才可以执行
[9]命令。一旦一个服务器接收到一个请求去执行命令，它可以通知所有后面到达的客户端：已经有一条命令被选中了。这样客户端就可以避免（再向这个服务器）继续发送提案。
·如果超过一半的服务器宕机，Paxos将不能工作。因为客户端不能再取得过半数服务器认可。
·最初版本的Paxos包含三个角色：提案者、接受者，以及学习者。学习者不做任何事情，只是从其他节点学习哪个命令被选中了。
·我们只让每个节点承担一个角色。在某些场景下，一个节点可能承担多个角色。比如，在一个P2P的场景下，每个节点既是服务器又是客户端。
·上述算法必须信任客户端们（提案者们）会严格遵守协议。然而，这个假设在很多场景下并不合理。在某些场景下，提案者的角色可以被一组服务器承担，客户端们需要联络提案者，并用它们的名义来发布提案。
·到现在为止，我们仅仅讨论了如何通过Paxos来使一组节点达成一致性决议（decision）来执行一条命令。单独的一条决议被称为Paxos的一个实例（instance）。
·如果希望执行多条命令，我们可以给每个实例附加一个实例编号。在每条消息中，该实例编号都会被使用。一旦某条命令被选中，任何一个客户端都可以采用一个新的实例编号来启动一个新的实例。如果一个服务器不知道前面的一个实例已经有了一个一致决议，那么该服务器可以询问其他服务器决议的内容。
章节说明
两阶段协议已经存在了很长时间，并且不止一个原创者。在Gray的书［Gra78］中，可以找到关于这个概念的较早的描述。[10]
Leslie Lamport 在1989年提出了Paxos。但是，“Paxos”这个名称是怎么来的呢？Lamport在论文中描述了一个虚拟的希腊小岛——Paxos，并假定这个算法是为了解决在岛上的议会中的投票问题。他非常喜欢这个想法，甚至以一个印第安纳·琼斯风格的考古学家的身份做过几个报告。当论文第一次投稿的时候，大多数评委都对这个议会故事感到困惑，无法理解算法的目的和思想。论文因此被拒绝发表！Lamport拒绝修改论文，稍后他表示“不开心，因为这个领域的学者如此缺乏幽默感”。几年之后，随着应用的发展，Paxos协议的用途变得更为广泛。Lamport于是从抽屉里翻出这篇被拒绝的论文，并发给他的几位同事。这些同事们都表示很喜欢这个想法。于是Lamport决定重新投稿。和8年前的初稿相比，论文基本没改！但是这次论文被录用了。
不过，鉴于这篇论文［Lam98］确实太难懂了，Lamport后来特地写了一篇关于Paxos的说明［Lam01］。
参考文献
［Gra78］James N Gray.Notes on data base operating systems.Springer，1978.
［Lam98］Leslie Lamport.The part-time parliament.ACM Transactions on Computer Systems（TOCS），16（2）:133-169，1998.
［Lam01］Leslie Lamport.Paxos made simple.ACM Sigact News，32（4）:18-25，2001.[1]译者注：原著中将定义、模型、算法等统一编号，为保持风格一致，译文中采用了相同的编号方式。[2]比如，u和s在地理位置上距离很近，且u和s也是如此。1122[3]译者注：是的，若一个客户端节点得到过半数服务器的锁，其他节点就不能再获得大数据节点的锁了。[4]译者注:与锁不同，票只是检查服务器当前是否空闲。得到票并不意味着服务器会为客户端保留位置，客户端必须马上去竞争。另外在理解算法时，须清楚本章假定的是可变消息延迟模式（模式2.6）。与算法2.3相比，本算法引入了竞争，多个客户端需要竞争得到过半数服务器的认可（算法第8行），这样降低了服务器执行不同命令序列的可能。此外，与算法2.9相比，本算法不需要串行化器，避免了单点故障，也可以在少量服务器宕机的情况下运行。但是，本算法仍然是朴素的，还存在明显的问题。后续将通过分析本算法的问题和相应的解决方案来引出Paxos。[5]译者注：原书此处写的是第7行。错了，应是第9行。[6]译者注：如果u在u存储命令之前就得到了它的票，则u的存储行动将会失败，211因为服务器会发现u的票失效了。这样在阶段3，u就不会要求服务器执行命令。11[7]译者注：我们需要一个全局一致的票号，因此不能让每个服务器自己维护一个本地的计数器来产生票号。一个巧妙的办法是让客户端自己来决定下一个票的编号t，然后去向所有的服务器请求编号为t的票。服务器在收到请求后，先将t和它本地的计数器进行比较，只有t大于本地计数器的值时，服务器才会发布票（编号为t），同时将其本地计数器的值更新为t。这样，我们就可以得到一个符合定义2.11的要求，且全局一致的产生票号的方法。[8]译者注：按上面的算法，在第7行，客户端必须等待过半数服务器的正反馈，直到超时才启动新一轮尝试。如果服务器发送负反馈，客户端可以更容易判定是否能够收到过半数的正反馈。[9]译者注：依然是前面宕机那个客户端所存储的命令。[10]译者注：2013年度图灵奖得主，LaTeX的发明者，分布式计算领域最伟大的科学家之一。延伸阅读：Paxos漫谈
Leslie Lamport（http://www.lamport.org/）所提出的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 systems”。在第二篇论文中，特别提到“Indeed，all working protocols for asynchronous consensus we have so far encountered have Paxos at their core”（事实上，到目前为止我们所遇到的解决异步共识问题的实用算法，其核心都是Paxos）。
上述两篇论文可以说是揭开了大数据管理的序幕，而Paxos则在大数据管理的核心技术（容错）中扮演了极为重要的角色。在这之后，Paxos逐渐被工程技术人员了解，在工业界得到越来越多的应用。在下一节，我们将具体介绍Paxos在工业界的应用情况。
典型应用场景
下面主要介绍Paxos常用的应用场合，我们会简单介绍一个应用方向，然后介绍典型的实例。
数据库备份
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，本书第6章）来进行领导节点的选举。
PhxPaxos是腾讯公司微信后台团队自主研发的一个类库，基于Paxos算法思想，实现多机的状态拷贝。基于PhxPaxos，可以方便地实现将单机状态扩展到多机，达到容错的强一致性多机状态复制的目的。该类库已在腾讯内部，特别是微信系统中得到了严格的工程验证，目前已经开源。
Name Server
网络中每个节点都有一个地址，网络能根据消息的目标地址将消息准确送到对应的节点。域名服务器（Name Server）的作用就是将一个节点或服务的名称转换为对应的位置或地址。一个中心域名服务器必须位于一个众所周知的地址，且永不改变。但当这个中心域名服务器崩溃时，整个网络都将崩溃。一个中心域名服务器也需要一个极多的存储空间，并且可能导致消息过载。为了解决上述问题，我们可以采用分布式域名服务器。
通过Paxos算法来管理域名服务，则可保证系统的高可用性，将可用的服务分配给合适的客户端。
Config配置管理
通常对于小的系统，我们习惯采用手工修改配置文件的方法，这样做有两个问题，其一是容易出错；其二，若系统运行在多个节点上，手工修改难以保证多个节点的状态是一致的。因此，对于大规模的应用系统，特别是分布式的应用，我们必须采用自动化的方式来统一修改配置文件。目前一个流行的做法是采用Zookeeper（核心是Paxos），将配置文件放到Zookeeper的某个目录上，然后各个程序对这个目录节点进行监听。若配置发生改变，各个节点上的应用程序就会收到通知，并自行修改配置。
参考文献
［CGR07］Tushar D.Chandra，Robert Griesemer，and Joshua Redstone.Paxos made live:An engineering perspective.In Proceedings of the Twenty-sixth Annual ACM Symposium on Principles of Distributed Computing，PODC'07，pages 398-407，New York，NY，USA，2007.ACM.
［GL03］Eli Gafni and Leslie Lamport.Disk paxos.Distributed Computing，16（1）:1-20，2003.
［Lam96］Butler W.Lampson.How to build a highly available system using consensus，pages 1-17.Springer Berlin Heidelberg，Berlin，Heidelberg，1996.
［Lam98］Leslie Lamport.The part-time parliament.ACM Transactions on Computer Systems（TOCS），16（2）:133-169，1998.
［Lam01］Butler Lampson.The abcd's of paxos.In Proceedings of the Twentieth Annual ACM Symposium on Principles of Distributed Computing，PODC'01，pages 13-，New York，NY，USA，2001.ACM.
［Lam06］Leslie Lamport.Fast paxos.Distributed Computing，19（2）:79-103，2006.
［LM04］Leslie Lamport and Mike Massa.Cheap paxos.In 2004 International Conference on Dependable Systems and Networks（DSN 2004），28 June-1 July 2004，Florence，Italy，Proceedings，pages 307-314，2004.
［MC99］Barbara Liskov Miguel Castro.Practical byzantine fault tolerance.In OSDI，volume 99，pages 173-186，1999.
［OL88］Brian M.Oki and Barbara H.Liskov.Viewstamped replication:A new primary copy method to support highly-available distributed systems.In Proceedings of the Seventh Annual ACM Symposium on Principles of Distributed Computing，PODC'88，pages 8-17，New York，NY，USA，1988.ACM.
［PLL97］Roberto De Prisco，Butler W.Lampson，and Nancy A.Lynch.Revisiting the paxos algorithm.In Proceedings of the 11th International Workshop on Distributed Algorithms，WDAG'97，pages 111-125，London，UK，UK，1997.Springer-Verlag.
试读结束[说明：试读内容隐藏了图片]