Consistency

Paxos Consistency ACID CAP BASE

---

1.引言

数据库发展已经半个多世纪了，顾名思义，数据库是专门用于存储数据的管理单元，它分为存储和管理两个层次。

最初，人们习惯于将数据直接写入文本文件中，然后通过手动的检索文本文件中的内容来处理数据，这也就是文本数据库。

在对这些文本数据进行处理的过程中，人们发现大部分数据之间存在某种层次关系，比如家族层次结构、公司领导的层次结构，如果将这些数据结合它们的实际层次体系来进行管理的话，会方便很多，这就诞生了层次数据库。

随着处理数据越来越大，层次数据库的局限性也暴露出来了，例如，层次无法表示多个家族、多个公司之间的关系，家族或者公司内部虽然是以层次的关系出现的，但是家族之间、公司之间的这些关系却是以网状的形式出现的，因此，在层次数据库的基础上就提出了网状数据库。

但是问题又来了，网状数据库虽然表达的数据规模较之前的文本数据库、层次数据库都有了很大的提升，但是它无法掌控一些细粒度的问题，比如人与人之间的这种关系问题。

1970年，数据库理论大神 E.F.Codd 在层次数据库和网状数据库的基础上，巧妙的将现实世界的事物之间的联系通过一种关系模型表述了出来，而且还针对关系模型创造性的提出了关系运算理论，基于此理论，关系数据库应运而生。也正因如此，目前大多开源数据库的内核中，对于表、索引、大对象、视图等的描述不是用 table、index、bigobject、view，而是统一用 relation，因为关系数据库所处理的所有对象都是关系，而表、索引、大对象、视图等只是关系的具体表现形式。

2.事务ACID

提到关系数据库，就不得不提事务（Transaction），事务是关系数据库正确处理关系之间联系的最小单元，本文后续所讲解的事务，在没有特定说明的情况下，指的都是关系数据库中的事务。

在关系数据库中，对事务的定义是：一系列对数据库系统中数据进行访问、更新操作所组成的一个程序执行逻辑单元。

首先，事务在应用程序并发访问数据库系统时，为这些应用提供一个隔离方法，以防止彼此的操作互相干扰。

其次，事务为数据库操作的序列提供一种从失败中恢复到正确状态的方法。

最后，事务还提供了数据库即使在异常状态下，仍然能够保证数据一致性的方法。

2.1.四大特性

事务具有四个特性：原子性（Automicity）、一致性（COnsistency）、隔离性（Isolation）、持久性（Durability）。

• 原子性(Atomicity)

  事务中的所有操作，要么全部都执行成功，要么全都不执行。也就是说，组成事务的所有操作必须是一个原子的操作序列单元，事务所包含的各项操作在一次执行过中，只能够允许出现两种状态之一：全部成功执行、全部不执行。

• 一致性(Consistency)

  事务执行前后数据库都处于一致的状态。事务中操作序列的执行不能够破坏数据库的完整性和一致性，一个事务在执行之前和之后，数据库都必须处于一个一致性的状态。也即，事务的执行结果必须是使数据库从一个一致性状态转变到另一个一致性状态。

  举个例子，比如我卡里有1000元钱，你卡里有2000元钱，我们卡里总共有3000元钱，这是一个状态，在我向你转入200元后，我卡里必须只能够是800元，而你卡里也必须只能够为2200元，我们卡里总共必须仍然是3000元，这就是另一个状态。一定不能够出现，我向你转成功后，我卡里还有1000元，而你卡里却多出了200元，我们卡里总共有3200元，这样银行肯定不干，但是也不能够出现，成功后，我卡里有800元，而你卡里只多了100元，我们卡里总共只有2900元，这样你会不干的。

• 隔离性(Isolation)

  多个事务执行都感觉不到其它事务在执行。在关系数据库中，支持多个事务同时并发的执行，隔离性就是为了保证在这种并发环境中，不同的事务并发操纵相同的数据时，数据库仍然能够处于一个稳定的一致性状态。

• 持久性(Durability)

  一个事务一旦被提交，所有的修改将永久保存，即使系统故障也不丢失。

  比如，我给你转了200元钱，而且转成功了，那么这个转账操纵必须永久有效，即使这个银行在地震中被毁灭，我不能够在转成功后，对银行操作员说，我不想转了，请她把你卡上的200元钱给我扣回来。

2.2.隔离级别

在提出 ACID 特性后，如果数据库严格按照这些特性去实现，在并发环境中，肯定会严重影响数据库的执行性能，因此针对不同的应用场景，我们将 ACID 的隔离性进行分类，以提升数据库的并发性能，这就是数据库的隔离级别。

数据库有如下四种隔离级别：

• 读未提交（READ UNCOMMITTED）

  可能读到脏数据，因此也叫脏读，不加行锁和表锁，只对访问的页面加 Latch，Latch 保证数据的并发访问。

  举例为：事务A向某个页面写数据，事务B同时从该页面读数据，因此事务B有可能会读到事务A还未提交的脏数据。

• 读已提交（READ COMMITTED ）

  每次读到的数据可能不同，因此也叫不可重复读。加行锁或表锁，对访问的页面加 Latch，对访问的行加 Lock，读操作及时释放行锁，DML 语句事务提交时释放锁。

  举例为：A事务 Latch 住某个页面，然后对页面中的某一行加 Lock，并及时释放 Latch，B事务读取该行之前也需要对该行加 Lock，因此，此时B事务无法对该行加 Lock，也就无法读取该行，必须等到A事务写入并提交，释放 Lock 后，B事务才能对该行加 Lock，然后够读取A事务已经提交到的数据，即读已提交。

  等到B事务读取完成后，B事务立即释放该行的 Lock，此时如果C事务获取了该行的 Lock，然后修改了该行，同时提交，那么B事务如果下次读取该行时，就只能够读到C事务提交后的数据，这就造成B事务在未提交之前读不到和上一次相同的数据，也即不可重复读。

• 可重复读（REPEATABLE READ）

  第二次读到的记录会多，因此也叫幻象读，加行锁或表锁，对访问的页面加 Latch，对访问的表加意向锁，对访问的行加 Lock，事务提交时释放锁。

  举例为：A事务 Latch 住某个页面，然后对页面中的某一行加 Lock，并及时释放 Latch，然后开始读取，针对读到的行，都添加 Lock，此时B事务是无法对这些已经被A事务读到的行进行修改的，也正是由于还持有读到的行上的 Lock，因此A事务在下一次读取这些行时，就能够读到和上次相同的数据，即可重复读。

  但是，针对那些A事务还未读到的行，B事务是可以进行修改的，因此A事务在下次读取时，有可能会读到新的数据，也即出现了幻像，但是，一旦A事务读到了新的数据，B事务就无法对这些数据进行修改了。

  举个实际的例子，A事务在执行 Select * from T 操作，由于A事务对表T仅仅添加行锁，没有添加表锁，因此在A事务扫描表T的时候，B事务可以同时向表T中插入新的数据，这就会导致A事务每次执行 Select 操作时的结果不一致的现象。

• 可串行化读（SERIALIZABLE）

  加行锁或表锁，对访问的页面加 Latch，索引扫描加行锁，表扫描加表锁，事务提交时释放锁，性能低。

2.3.锁

为了实现上面的隔离级别，数据库内部维护了一系列锁，主要有三类：Latch、Pin、Lock，具体如下：

• LATCH

  将磁盘中的页面加载到内存中的过程，Latch 的持有时间很短，Latch 后，其它事务无法修改被 Latch 的页面，其控制力度较大。

• PIN

  将 Latch 到内存中的页面 Pin 住，表示该页面无法被换出。

• LOCK

  锁，分为很多种，Oracle 的锁是放到具体的页面和项目录中的，而某些数据库的锁则只是一个内存结构，记录锁住了哪些页面或者页面中的哪些项。

3.单机

数据库诞生之初，由于数据处理规模较小，单台主机通常能够满足日常需要。自上世纪六十年代大型主机被发明后，凭借其超强的计算性能和 I/O 访问速度以及其在稳定性和安全性方面的卓越表现，在很长一段时间内，它引领了计算机行业以及商业计算领域的发展，这段时间的数据库系统被称为单机数据库系统，或者单节点数据库系统。

4.集群

随着互联网时代的到来，数据呈爆炸式的快速增长，由于大型主机高昂的人才培养成本以及其超高的价格，使得大型主机的整体性价比急剧下降，这种单简单依靠对单台主机进行纵向扩展以提升其运算速度和数据容量的方式已经完全满足不了人们的日常所需，与此同时，随着 PC 机性能的不断提升以及网络技术的快速普及，因此一种将数据分布到多台廉价 PC 机上进行处理的 MPP 架构技术就越来越受到人们的关注，我们称之为集群，在提升数据处理性能的同时，降低投入成本，提升性价比，这种集群系统通常又称为分布式系统。

在《分布式系统概念与设计》一书中，对分布式系统做了如下定义：

分布式系统是一个硬件或软件组件分布在不同的网络计算机上，彼此之间仅仅通过消息传递进行通信和协调的系统。

分布式系统中的计算机在空间部署上可以随意分布，这些计算机可以放到不同的机架上，不同的机房中，甚至是不同的城市，不同的国家，这些计算机已经超越了地域的范畴，它们仅仅通过网络进行交互。

分布式系统具有如下特点：

• 分布性

  分布式系统中的各个主机都会在空间上随意分布，同时主机的分区情况也会随时变动。

• 对等性

  分布式系统中的主机之间没有主从之分，既没有控制整个系统的主机，也没被控制的从机，组成分布式系统的所有主机节点都是对等的。副本（Replication）是分布式系统中最常见的概念之一，指的是分布式系统对数据和服务提供的一种冗余的方式。在常见的分布式系统中，为了对外提供高可用服务，我们往往会对数据和服务进行副本处理。数据副本是指在不同的主机节点上持久化同一份数据，当某个节点数据发生丢失时，可以从副本上读到该数据，这是解决分布式系统数据丢失最为有效的手段。另一种副本是服务副本，指多个节点提供相同的服务，每个节点都有能力接收来自外部的请求并进行相应的处理。

• 并发性

  同一个分布式系统中的多个节点，有可能会并发的操作一些共享资源，比如数据库或者分布式存储等，因此，如何准确并高效地协调分布式并发操作就成为分布式架构与设计中最大的挑战之一。

• 缺乏全局时钟

  一个典型的分布式系统是由空间上随意分布的多个进程组成，具有明显的分布性，这些进程通过消息来进行相互通信。因此，在分布式系统中，很难定义两个事件究竟谁先谁后，原因就是分布式系统缺乏一个全局的时钟序列控制。关于分布式系统的时钟和事件顺序，在 Leslie Lamport 的经典论文 Time, Clocks, and the Ordering of Events in a Distributed System 中作了非常深刻的讲解。

• 故障总是会发生

  组成分布式系统的所有主机，都有可能发生任何形式的故障，任何在设计阶段考虑到的异常情况，一定会在系统实际运行中发生，并且，在系统实际运行过程中还会发生很多在设计时候未能考虑到的异常故障，因此，除非需求指标允许，在系统设计时，不能放过任何异常情况。

分布式环境中还会存在各种问题，如下是一些较为典型的问题：

• 通信异常

  分布式系统需要在各个节点之间进行网络通信，每次网络通信都伴随着网络不可用的风险，即使各个节点的网络通信能够正常进行，但相较于单机操作，会存在延时情况，因此在分布式系统中，消息丢失和消息延迟变得非常普遍。

• 网络分区

  当网络发生异常时，会导致分布式系统中部分节点之间的网络延时不断增大，最终导致只有部分节点能够进行正常通信，而另一些节点则无法通信，我们将这种现象称为网络分区，俗称脑裂。在这种情况下，分布式系统会出现局部小集群，在极端情况下，这些局部小集群会完成原来需要整个分布式系统才能够完成的功能，包括对数据的事务处理，这就对分布式一致性提出了非常大的挑战。

• 三态

  由于分布式环境中的这些异常情况，因此分布式系统的每一次请求与响应都会存在特定的三态：成功、失败、超时。当网络出现异常时，就有可能出现超时现象，具体如下：

  • 在发送阶段：由于网络原因，请求并没有成功发送到接收方，而是在发送的过程中发生了消息丢失的现象。

  • 在接收阶段：请求消息被接收方接收后，进行了处理，但是将响应反馈回去的时候，发生了消息丢失的现象。

  当出现上面这样的超时现象时，网络通信的发起方是无法确定当前请求是否被成功处理了。

• 节点故障

  组成分布式系统的主机节点有可能会出现宕机或者僵死现象，而且每个节点都有可能出现，每天都有可能发生。

5.分布式事务

随着分布式计算的快速发展，在分布式中，如何保证传统事务的 ACID 特性也就自然而然的走进了人们的研究范围。在单机数据库系统中，实现一套满足 ACID 的事务处理系统是一件十分容易的事情，但是在分布式系统中，由于主机随时会出现通信异常(消息延迟)、网络分区异常(脑裂)、三态问题(成功、失败、超时)、节点故障(宕机或僵死)，因此很难保证分布式事务也具有单机事务的 ACID 特性，尤其是对于一个高访问量、高并发的互联网分布式系统来说，如果我们严格实现一套满足 ACID 特性的分布式事务，则很有可能在系统的可用性和一致性之间出现严重的冲突，也就是说，当我们要求分布式具有严格一致性时，就有可能牺牲掉系统的可用性，降低系统的访问量和并发度，但是通常情况下，对于分布式系统来说，可用性是不得不具备的一个必备属性，反而对于一致性的需求并不是特别的严格，因此，在可用性和一致性无法同时兼得的情况下，就很有必要在单机事务的 ACID 的特性上，根据分布式系统的实际特点和常用应用场景，对分布式事务进行单独的研究，CAP 理论 和 BASE 理论 就是其中最为经典的研究成果。

6.CAP 理论

2000年7月，来自加州大学伯克利分校的 Eric Brewer教授 在 ACM PODC(ACM Principles of Distributed Computing) 会议上，首次提出了著名的 CAP猜想，此处有更详细的CAP理论介绍，两年后，来自 MIT 的 Seth Gilbert 和 Nancy Lynch 从理论上证明了 CAP 猜想，从此 CAP 理论正是成为了分布式计算领域的公认定理，并深深的影响了分布式计算的发展。根据 CPA 理论中的描述：

一个分布式系统不可能同时满足一致性（C: Consistency）、可用性（A: Availability）和分区容错性（P: Partition torerance）三项需求，最多只能够同时满足其中两项。

6.1.一致性

在分布式环境中，一致性是指数据在多个副本之间是否能够保证一致的特性。在一致性的需求下，当一个系统在数据一致的状态下执行写操作后，应该保证系统的数据仍然处于一个一致性状态。

在分布式系统中，通常情况下，为了对数据进行容灾处理，同时提升数据的并发访问效率，通常的做法是对同一份数据存储多个副本，同时对数据进行读写分离，如果在某个节点上执行了写操作，成功后，却没有在其它节点上进行同步，于是在这些节点上进行读操作时，就无法读取到最新的数据，甚至还会读到错误的数据，这就是典型的分布式数据不一致的情况。反之，如果能够做到针对某个节点执行写入操作后，在其它节点能够读到最新的正确值，这样的系统就被认为具有强一致性或者严格一致性。

6.2.可用性

可用性是指分布式系统所提供的服务一致处于可用状态，对于用户所发出的每一个操作请求，都能够在有限的时间内返回请求结果。这句话有两层含义：有限的时间内、返回结果。

• 有限的时间内

  是指系统必须在规定的响应时间内返回对应的处理结果，如果超时，则系统被认为是不可用。对于不同的系统，这个时间间隔可能不同，但是都必须有一个合理的响应时间。

• 返回结果

  是指系统在完成对用户请求的处理后，返回一个正常的响应结果。此结果通常能够明确的反应出系统对请求处理的结果，即成功或者失败，而不是一个让用户感到困惑的返回结果，比如 OutOfMemoryError。

6.3.分区容错性

分区容错性要求分布式系统具有如下特性：分布式系统在遇到任何网络分区故障的时候，仍然需要能够保证对外提供满足一致性和可用性的服务，除非是整个网络环境发生了故障。

网络分区是指在分布式系统中，不同节点分布在不同的子网络中(机房或者异地网络)，由于一些特殊的原因，这些子网络之间出现网络不连通的状况，但各个子网络内部是正常的，从而导致整个分布式系统的网络环境被切分成若干孤立的区域。需要注意的是，组成一个分布式系统的每个节点的加入与退出都可看做是一个特殊的网络分区。

6.4.CAP 抉择

既然分布式系统无法同时满足 CAP 三项需求，因此在实际的应用过程中，通常选择抛弃其中一项：

• 抛弃 P

  如果抛弃分区容错性后，仍然希望能够避免系统出现分区容错性问题，一种较为简单的做法是将所有的数据，或者仅仅是那些与事务相关的数据，都放在一个分布式节点上。这样做虽然无法100%保证系统不会出错，但至少不会碰到由于网络分区而带来的负面影响。但需要注意的是，放弃P的同时也就意味着放弃了整个分布式系统的可扩展性。

• 抛弃 A

  如果放弃可用性，则一旦系统遇到网络分区或者其它故障时，那么受影响的服务就需要等待一定的时间，在此时间段中，系统无法对外提供正常服务，也即系统不可用。

• 抛弃 C

  如果完全放弃一致性，那么整个分布式系统的数据就会变得毫无意义，整个系统也就失去了其应有的价值，因此可以折中一下，放弃系统数据的强一致性（实时一致性），但是保证数据的最终一致性。因此，这样的系统虽然无法保证数据实时一致，但是能够承诺数据最终会达到一个一致的状态，而具体需要多长时间才能够达到一致性状态，这取决于系统的具体设计，主要影响因素有数据在不同节点之间复制所需要的时间以及各个节点执行相同的事务操作所需要的时间。

但是，对于一个分布式系统，分区容错性是一个最为基本的属性，因为既然是分布式系统，则其各个组件必然会部署到不同的节点上，因此必然会出现子网络，既然有网络，就一定会出现网络异常，因此，分区容错性就成为分布式系统必须要面对和解决的一个问题，而同时，分布式系统往往又要求持续不断的对外提供稳定的服务，更为甚者，针对某些分布式系统而言，可用性是其必须满足的一个刚性需求，基于此种原因，系统架构师们通常需要根据业务具体特点在一致性和可用性之间寻求平衡，大多数情况是选择满足分区容错性和可用性，放弃实时一致性，保证最终一致性。

7.BASE 理论

BASE 理论是 Basically Available（基本可用）、Soft state（软状态）、Eventually consistent（最终一致性）三个词组首字母的简写，是 eBay 工程师 Dan Pritchett 在其文章 BASE:An Acid Alternative 中提出，该理论是对 CAP 中一致性和可用性权衡的结果，BASE 理论是大规模互联网分布式系统实践的总结，是基于 CAP 理论逐渐演化而来的，其核心思想是：即使无法做到强一致性（Strong Consistency），但每个应用都可以根据自身的业务特点，采用适当的方式达到最终一致性（Eventual Consistency）。

7.1.基本可用

基本可用是指分布式系统在出现不可预知的故障时，允许损失部分可用性，但决不允许出现系统不可用的状态：

• 响应时间上的损失

  通常情况下，某个系统会在 0.5s 之内返回给用户一个期望的结果值，但是由于出现不可预知的系统故障(断电、网络故障、地震等)，响应时间有可能会增加到 1~2s，比如搜索引擎系统。

• 功能上的损失

  正常情况下，某个大型电子商务网站的购物系统中，消费者几乎能够顺利完成每一笔订单，但是到了双十一这样的高峰购物节时，由于消费者购物行为暴增，为了保证购物系统的稳定性，部分消费者可能会被引导到一个降级页面中。

7.2.软状态

软状态又被称为弱状态，它与硬状态相对应，是指允许系统中的数据存在中间状态，同时认为中间状态的存在不会对系统的可用性造成负面影响，最为典型的情况是，允许系统在不同节点的数据副本之间进行数据同步的过程中存在网络延时。

7.3.最终一致性

最终一致性是指系统中的所有数据副本，在经过一段时间的同步后，最终能够达到一致的状态。因此，最终一致性的本质是需要系统保持最终数据能够达到一致，而没必要实时要求系统数据的强一致性。

Amazon 的首席技术官 Werner Vogels 在2008年发表的一篇经典论文 Eventually Consistent-Revisited，还有一篇于2007年发表的 Eventually Consistent-Revisited，其中对一致性进行了非常详细的介绍。

Werner Vogels 先生认为，最终一致性是一种特殊的弱一致性，系统能够保证在没有其它写入操作的情况下，数据最终能够达到一致的状态，因此所有客户端对系统的数据访问都能够获取到最新的数据值。同时，在无故障的前提下，数据达到一致状态的时间延迟，取决于网络延迟、系统负载和数据复制方案等因素。

在实际的实践中，最终一致性又存在如下几类变种：

• 因果一致性（Causual Consistency）

  因果一致性是指，如果进程A在更新完某个数据项之后，通知了进程B，那么进程B在之后对该数据项的访问都能够获取到进程A更新后的最新值，并且进程B对该数据项进行更新的话，务必基于进程A更新后的最新值，即不能发生丢失更新的情况。但是，与进程A无因果关系的进程C对数据的访问则没有这样的限制。

• 读己所写（Read your writes）

  进程A更新某个数据项之后，它总是能够访问到更新过的最新值，而不会看到旧值。也即，对于单个数据的获得者来说，其读到的数据一定不会比自己上次写入的数据旧。因此，读己所写也可看做是一种特殊的因果一致性。

• 会话一致性（Session Consistency）

  会话一致性将对系统数据的访问框定在一个会话当中：系统能够保证在同一个有效的会话中实现读己所写的一致性，也即，执行更新操作之后，客户端能够在同一个会话中始终读到该数据项的最新值。

• 单调读一致性（Monotonic read consisitency）

  单调读一致性时值，如果一个进程从系统中读取到一个数据项的某个值后，那么系统对于该进程后续的任何数据访问都不应该返回更旧的值。

• 单调写一致性（Monotonic write consistency）

  单调写一致性是指，一个系统需要能够保证来自同一个进程的写操作能够被顺序的执行。

在实际的系统实践中，通常是将上述若干变种互相结合起来，用以构建一个具有最终一致性的特殊分布式系统。事实上，最终一致性并不是只有那些大型分布式系统才涉及的特性，许多现代的分布式关系数据库系统都采用了最终一致性模型。

在现代的分布式关系数据库系统中，为了提升系统的整体读写性能，同时提升系统的并发度，大多都会采用同步或者异步的方式来实现主备数据复制技术，在增强系统容错能力的同时实现读写分离。在同步的方式中，数据的复制过程通常就是更新事务的一部分，因此在事务完成后，主备数据库的数据就会达到一致。而在异步方式中，备库的更新往往存在延迟，这取决于事务日志在主备数据库之间的传输时间长短，如果传输日志时间过长，或者日志在传输过程中出现了异常，无法及时将事务应用于备库上，那么从备数据库上读到的数据就是旧值，也就出现了主备数据不一致的情况，在这种情况下，比较常见的解决方案是多次重试或者人为数据订正，以保证关系数据库中数据的最终一致性。

总体来说，BASE 理论是面向大型高可用可扩展的分布式系统，和传统事务的 ACID 特性是相反的，它通过牺牲强一致性模型来获得高可用性，并允许数据在一段时间内存在中间值，处于不一致状态，但最终会达到一致状态。在实际的分布式场景中，不同业务单元对数据一致性的要求是不同的，因此在具体的分布式系统架构设计过程中，ACID 特性和 BASE 理论往往又会结合在一起使用。

为解决分布式的一致性问题，在长期的探索研究过程中，涌现了一大批经典的一致性协议和算法，其中最为著名有：二阶段提交协议、三阶段提交协议、Paxos 算法。

在分布式系统中，每一个节点都能够明确知道本机事务的执行状态，成功或者失败，但却无法直接获取到其它分布式节点的操作结果。因此，当一个事务操作需要跨越多个分布式节点时，为了保证事务的 ACID 特性，通常的做法是，引入一个协调者（Coordinator）的组件来统一调度所有分布式节点的执行逻辑，与之对应，这些被调度的分布式节点则被称为参与者（Participant）。协调者负责调度参与者的行为，并最终决定这些参与者是否要把事务真正进行提交。基于此种思想，衍生出来二阶段提交协议（Two-Phase Commit）和三阶段提交协议（Three-Phase Commit）。

8.二阶段提交

2PC，是 Two-Phase Commit 的缩写，即二阶段提交，是计算机网络尤其是在数据库领域内，为了使基于分布式系统架构下的所有节点在进行事务处理过程中能够保持原子性和一致性而设计的一种算法。通常，二阶段提交协议也被认为是一种一致性协议，用以保证分布式系统数据的一致性。目前，绝大部分关系数据库都是采用二阶段提交协议来完成分布式事务处理的，利用该协议能够非常方便的完成所有分布式事务参与者的协调，统一决定事务的提交或者回滚，从而能够有效的保证分布式数据的一致性。因此，二阶段提交协议被广泛的应用在许多分布式系统中。

顾名思义，二阶段提交协议就是将事务的提交过程分为两个阶段来进行处理：提交事务请求、执行事务提交。

8.1.阶段一：提交事务请求

提交事务请求为二阶段提交协议的第一个阶段，主要有如三个步骤：

1. 事务询问

   协调者向所有参与者发送事务内容，询问是否可以执行事务提交操作，并开始等待各个参与者的响应。

2. 执行事务

   各个参与者节点执行事务操作，并将 Undo 和 Redo 日志信息记入事务日志中。

3. 响应询问

   如果参与者成功执行了事务操作，那么就反馈给协调者 Yes 响应，表示事务可以执行；如果参与者没有成功执行事务，那么就反馈给协调者 No 响应，表示事务不可执行。

由于此过程在形式上类似于协调者组织各个参与者对一次事务操作进行一次投票过程，因此二阶段提交协议的第一个阶段也被称为投票阶段，即各个参与者投票表明是否需要继续执行接下来的事务提交操作。

8.2.阶段二：执行事务提交

执行事务提交是二阶段提交协议的第二个阶段，在此阶段中，协调者会根据各个参与者的反馈情况来决定最终是否可进行事务提交操作，协调者最终只有可能作出两种决定：执行事务提交、执行事务中断。

1. 执行事务提交

   如果协调者从所有参与者获得的反馈都是 Yes 响应，那么就会执行事务提交操作，此过程有如下几个步骤：

   • 发送事务请求

     协调者向所有参与者节点发送 Commit 请求。

   • 事务提交

     参与者收到 Commit 请求后，会正式执行事务提交操作，并在完成事务提交之后，释放其在整个事务执行期间所占用的事务资源。

   • 反馈事务提交结果

     参与者在完成事务提交之后，向协调者发送 Ack 消息。

   • 完成事务

     协调者接收到所有参与者反馈的 Ack 消息后，完成事务。

2. 执行事务中断

   如果任何一个参与者向协调者反馈了 No 响应，或者在等待超时之后，协调者上无法接收到所有参与者的反馈响应，那么就会执行事务中断，此过程有如下几个步骤：

   • 发送回滚请求

     协调者向所有参与者节点发送 Rollback 请求。

   • 事务回滚

     参与者接收到 Rollback 请求后，会利用其在阶段一中记录的 Undo 日志信息来执行事务回滚操作，并在完成回滚之后，释放其在整个事务执行期间所占用的事务资源。

   • 反馈事务回滚结果

     参与者在完成事务回滚操作之后，向协调者发送 Ack 消息。

   • 中断事务

     协调者接收到所有参与者反馈的 Ack 消息后，完成事务中断操作。

由上可以看出，二阶段提交协议将一个分布式事务的处理过程拆分为投票阶段和执行阶段，其核心思想是对每个事务都采取先尝试后提交的处理方式，因此也可以将二阶段提交看作一个强一致性算法。

8.3.优缺点

二阶段提交协议的优点是：原理简单，实现方便。

二阶段提交的缺点：同步阻塞、单点问题、脑裂、太过保守。

• 同步阻塞

  二阶段提交协议存在的最为明显也是最大的一个问题就是同步阻塞，这会极大地限制分布式系统的性能。在二阶段提交的执行过程中，所有参与该事务操作的逻辑都处于阻塞状态，也就是说，各个参与者在等待其它参与者节点的响应过程中，将无法进行任何其他操作。

• 单点问题

  在二阶段提交协议中，协调者的角色尤为重要，因此，一但协调者出现问题，那么整个二阶段提交流程将无法运转，更为严重的是，如果协调者在阶段二中出现问题的话，那么其它参与者将会一直处于锁定事务资源的状态中，而无法继续完成事务操作。

• 数据不一致

  在阶段二执行事务提交的时候，当协调者向所有参与者发送 Commit 请求之后，如果发生了局部网络异常或者是协调者在尚未发送完 Commit 请求之前自身发生了崩溃，此时会导致最终只有部分参与者收到 Commit 请求，于是这部分收到 Commit 请求的参与者将会执行事务提交操作，而其它没有收到 Commit 请求的参与者则无法执行事务提交操作，于是整个分布式系统便出现了数据不一致的现象。

• 太过保守

  如果协调者指示参与者进行事务提交询问的过程中，如果参与者出现故障导致协调者始终无法获取到所有参与者的响应信息，此时协调者只能依靠自身提供的超时机制来判断是否需要中断事务，这样的策略显得比较保守。换句话说，二阶段提交协议没有设计较为完善的容错机制，任意节点的失败都会导致整个事务的失败。

针对二阶段提交协议的上述缺点，在实际的实践过程中，在二阶段提价协议的基础上，又衍生出了三阶段提交协议。

9.三阶段提交

3PC，是 Three-Phase Commit 的缩写，即三阶段提交，是 2PC 的改进版本，它将二阶段提交协议的第一个阶段“提交事务请求”的过程一分为二，最终形成了由 CanCommit、PreCommit、DoCommit 三个阶段组成的事务处理协议。

9.1.阶段一：CanCommit

1. 事务询问

   协调者向所有参与者发送一个包含事务内容的 CanCommit 请求，询问是否可以执行事务提交操作，并开始等待各个参与者的响应。

2. 各个参与者向协调者反馈询问响应

   参与者在接收到来自协调者的 CanCommit 请求后，正常情况下，如果其自身认为可以顺利执行事务，那么会反馈 Yes 响应，并进入预备状态，否则反馈 No 响应。

9.2.阶段二：PreCommit

在第二阶段中，协调者会根据各个参与者的反馈情况来决定是否可以进行事务的 PreCommit 操作，正常情况下包含两种可能性：

1. 执行事务预提交

   假如协调者从所有参与者获得的反馈请求都是 Yes 响应，则会执行事务预提交操作，其具体步骤如下：

   • 发送预提交请求

     协调者向所有参与者节点发送 PreCommit 请求，并请入 Prepared 阶段。

   • 事务预提交

     参与者收到 PreCommit 请求后，会执行事务操作，并将 Undo 和 Redo 信息记录到事务日志中。

   • 各个参与者向协调者反馈事务执行的响应

     如果参与者成功执行了事务操作，那么就会反馈给协调者 Ack 响应，同时等待最终的指令：提交（Commit）或者中止（Abort）。

2. 中断事务

   如果任意一个参与者向协调者反馈了 No 响应，或者在等待超时之后，协调者尚未接收到参与者的反馈响应，那么就会中断事务，其具体步骤如下：

   • 发送中断请求

     协调者向所有参与者发送 Abort 请求。

   • 中断事务

     无论是收到来自协调者的 Abort 请求，还是在等待协调者请求过程中出现了超时，参与者都会中断事务。

9.3.阶段三：DoCommit

此阶段将进行真正的事务提交操作，会存在如下两种可能的情况：

1. 执行提交

   执行提交的步骤如下：

   • 发送提交请求

     进入这一阶段，假设协调者处于正常工作状态，并且它收到了来自所有参与者的 Ack 响应，那么它将从“预提交”状态转换到“提交”状态，并向所有参与者节点发送 DoCommit 请求。

   • 事务提交

     参与者接收到 DoCommit 请求后，会正式执行事务提交操作，并在完成提交之后释放其在整个事务执行期间所占用的事务资源。

   • 反馈事务提交结果

     参与者在完成事务提交之后，向协调者发送 Ack 消息。

   • 完成事务

     协调者在接收到所有参与者反馈的 Ack 消息后，完成事务。

2. 中断事务

   进入注意阶段，假设协调者处于正常工作状态，如果任意一个参与者向协调者反馈了 No 响应，或者在等待超时之后，协调者尚未接收到所有参与者的反馈响应，就会中断事务，其具体步骤如下：

   • 发送中断请求

     协调者向所有参与者节点发送 Abort 请求。

   • 事务回滚

     参与者收到协调者的 Abort 请求后，会利用其在 PreCommit 阶段中记录的 Undo 日志信息来执行事务回滚操作，并在完成回滚之后释放弃其在整个事务执行期间所占用的资源。

   • 返回事务回滚结果

     参与者在完成事务回滚之后，向协调者发送 Ack 消息。

   • 中断事务

     协调者在接收到所有参与者的 Ack 消息后，中断事务。

值得注意的是，一旦进入阶段三，可能会出现以下两种故障：

• 协调者出现问题。
• 协调者和参与者之间的网络出现故障。

无论出现那种情况，最终都会导致参与者无法及时接收到来自协调者的 DoCommit 或者 Abort 请求，针对这样的异常情况，参与者都会在等待超时之后，继续进行事务提交。

9.3.优缺点

优点：相较于二阶段提交协议，三阶段提交协议最大的优点是降低了参与者的阻塞范围，并且能够在出现单点故障后继续达成一致。

缺点：三阶段提交协议在去除阻塞的同时也引入了新的问题，那就是在参与者接收到 PreCommit 消息后，如果网络出现了分区，此时协调者所在的节点和参与者无法进行正常的网络通信，在这种情况下，参与者依然会进行事务的提交，这就有可能导致数据不一致。

10.Paxos

虽然两阶段提交协议和三阶段提交协议都能够解决分布式数据的事务一致性问题，但是它们都有明显的缺点，本节我们着重介绍另一种分布式系统一致性算法：Paxos 算法，它是 Leslie Lamport 于1990年提出的一种基于消息传递且具有高度容错机制的一致性算法，是目前公认的解决分布式一致性问题最有效的算法之一。

在分布式系统中，总会发生诸如宕机或者网络异常等情况，Paxos 算法需要解决的问题就是如何在一个可能发生上述异常的分布式系统中，快速且正确地在系统内部对某个数据的值达成一致，并且保证不论发生以上任何异常，都不会破坏整个系统的一致性。

1982年，Leslie Lamport 与另两人共同发表论文描述了一种计算机容错理论 The Byzantine Generals Problem，在理论描述的过程中，为了将所要描述的问题形象的表达出来，Lamport 设想出了一种场景：

拜占庭帝国有许多支军队，军队的将军们必须制订一个统一的行动计划——进攻或者撤退。将军们在地理上是分隔开来的，只能靠通讯员进行通讯。但是在这些通信员中存在叛徒，叛徒可以任意篡改消息，从而达到欺骗将军的目的。

这就是著名的拜占庭将军问题。理论研究显示，在一个 3N+1 的系统中，只有叛徒数目小于等于 N 的情况下，才有可能设计出一种协议，使得不管叛徒怎样作梗也能达成一致。在分布式计算领域，试图在异步系统和不可靠的通道上来达到一致性状态是不可能的，因此，对一致性研究的过程中，都往往假设信道是可靠地，不会发生消息篡改。在实际生产环境中，大多数系统在同一局域网中，消息被篡改的情况很罕见，即便因硬件和网络造成的消息不完整，只需简单的校验，丢弃不完整的消息即可。因此可以假设不存在拜占庭问题，也即假设所有消息都是完整的，没有被篡改的。在这种情况下需要什么样的算法保证一致性呢？

Leslie Lamport 在1990年提出了理论上的一致性解决方案，并给出了严格的数学证明。介于阐述拜占廷将军问题时这种类比方式的成功，Lamport 同样用心良苦地设想出了一种场景来描述这种算法面对的问题和解决的过程：

在古希腊有一个 Paxos 小岛，岛上以议会的形式通过法令。议会中的议员通过信使传递消息，议员和信使都是兼职的，随时可能离开议会厅，并且信使可能重复投递消息，也可能一去不复返。议会协议要保证在这种情况下法令仍然能够正确的产生，并且不会出现冲突。

这也是Paxos算法名称的由来。于是有了 The Part-Time Parliament 这篇论文。但是论文中压根没有说 Paxos 小岛是虚构出来的，而是煞有介事的说是考古工作者发现了 Paxos 议会事务的手稿，从这些手稿猜测 Paxos 人议会的做法。因此，在此论文中，从问题的提出到算法的推演论证，通篇贯穿了对 Paxos 议会历史的描述。

虽然 Lamport 早在1990就已经将 Paxos 算法的论文 The Part-Time Parliament 提交给了 ACM TOCS 的评审委员会了，但是由于论文创造性的使用了故事的方式来进行算法描述，导致当时委员会的工作人员没有一个能够正确的理解其对算法的描述，时任主编要求 Lamport 使用更严谨的数据证明的方式来描述该算法，否则他们讲不考虑接受这篇论文。遗憾的是，Lamport 觉得这些人太没幽默感了，拒绝修改，并撤销了对这篇论文的提交。

直到1996年，来自微软的 Bulter Lampson 在 WDAG'96 上提出了重新审视这篇分布式论文的建议，在次年 WDAG'97 上，MIT 的 Nancy Lynch 也公布了其根据 Lamport 的原文重新修改后的 Revisiting the Paxos Algorithm，帮助 Lamport 用数学的形式化术语定义并证明了 Paxos 算法，Lamport 觉得时机成熟了，于是再次发表这篇论文。这次编辑同意了，并且一本正经的说：“作者貌似是个对计算机科学偶尔感兴趣的考古学家，现在正在希腊小岛 Paxos 上进行野外考古作业，委托我来发表它”，也算是配合 Lamport 幽默了一把，于是在1998年，这篇延迟9年的论文终于被接受了。

后来在2001年，Lamport 本人也作出了让步，这次他放弃了故事的描述方式，而是使用通俗易懂的语言重新讲述了原文，并发表了 Paxos Made Simple。

Paxos 算法用来解决通信不可靠的分布式系统中的一致性问题。通信不可靠包括：消息会延迟、重复投递甚至丢失，但是消息不会被篡改（没有拜占庭问题）。下面让我们从源头出发，一步一步深入 Paxos，去探究隐藏在其中的奥秘。

10.1.问题描述

假设有一组可以提出提案的进程集合，那么对于一个一致性算法来说，需要保证如下几点：

• 在这些被提出的提案中，只有一个会被选定。
• 如果没有提案被提出，那么就不会有被选定的提案。
• 当一个提案被选定后，进程应该可以获取被选定提案的信息。

一个分布式的算法有两个重要的属性：安全性（Safety）和活性（Liveness）。安全性是指那些需要保证永远都不会发生的事情，活性是指那些一定会发生的事情。对于一致性来说，安全性的需求如下：

• 只有被提出的提案才能够被选定。
• 只能够有一个提案被选定。
• 如果某个进程认为某个提案被选定了，那么这个提案必须是真的被选定的那个。

对于 Paxos 算法，它的目标是要保证在众多的提案中最终只有一个提案被选定，当提案选定后，进程最终也能够获取到被选定的提案。在具体的实现中，一个进程可能充当多重角色，本文并不关心进程与角色之间进是如何进行相互映射的。

Paxos 算法将提案选取过程的参与者分为三类角色：Proposer、Acceptor、Learner。Proposers 提出提案，提案信息包括提案编号和提案的 Value，Acceptor 收到提案后可以接受（accept）提案，若提案获得多数 Acceptors 的接受，则称该提案被批准（chosen），Learners 只能学习被批准的提案。划分角色后，上述安全性需求就可以更精确的定义为如下三个约束：

• 决议（Value）只有在被 Proposers 提出后才能被批准，未经批准的决议称为提案（proposal）。
• 在一次 Paxos 算法的执行实例中，只批准（chosen）一个 Value。
• Learners 只能获得被批准（chosen）的 Value。

本文后续会讲解：Paxos 算法通过不断加强上述3个约束(主要是第二个)来获得最终一致性。

我们假设不同参与者之间可以通过收发消息来进行通信，因此 Poxos 算法有如下两个前提条件：

• 由于每个参与者以任意速度执行，可能会因为出错而停止，也可能会重启，同时，即使一个提案被选定后，所有的参与者也都有可能失败或者重启，因此，除非那些失败或者重启的参与者可以记录某些信息，否则将无法确定提案最终值。
• 消息在传输过程中可能会出现不可预知的延迟，也可能会重复或者丢失，但是消息不会损坏，即消息内容不会被篡改，不会出现拜占庭将军问题。

10.2.提案选定

要选定一个唯一提案最为简单的方式是只允许一个 Acceptor 存在，这样，Proposer 只能够发送提案给该 Acceptor，Acceptor 会选择它接收到的第一个提案作为被选择的提案，这种解决方案实现起来非常简单，但是容易因为 Acceptor 出现单点故障。

因此，可以使用多个 Acceptor 来避免此单点问题：Proposer 向一个 Acceptor 集合发送提案，集合中的每个 Acceptor 都可能会 Accept 该提案，当有足够多的 Acceptor 批准该提案时，我们就认为提案被选定了。那么，足够多是个什么概念呢？我们假设足够多的 Acceptor 是整个 Acceptor 集合的一个子集，该子集大得能够包含 Acceptor 集合中的大多数成员，因为任意两个包含大多数 Acceptor 的子集至少有一个公共成员。同时，我们再规定：每一个 Acceptor 最多只能够批准一个提案，那么就能够保证只有一个提案被选定了。

10.3.推导过程

在没有传送失败和消息丢失的情况下，如果我们希望即使在只有一个提案被提出的情况下，仍然可以选出一个提案，这就暗示了如下需求：

$P1$： 一个 Acceptor 必须批准它收到的第一个提案。

但是随之也带来了一个问题：如果有多个不同的提案被多个 Proposer 同时提出，就会出现这样的情况，虽然每个 Acceptor 都批准了它收到的第一个提案，但是没有一个提案是由多数 Acceptor 都批准的，因此也就无法选择最终的提案值，如下图所示：

另外，即使只有两个提案被提出，如果每个提案都被差不多一半的 Acceptor 批准了，此时如果某个或者某些 Acceptor 出错，则仍然会导致无法选择最终的提案值，如下图所示：

上图是一个典型的在任意一个 Acceptor 出现故障的情况下，无法确定提案的情况。在此例子中，总共有5个 Acceptor，其中两个批准了提案 $V_1$，另外三个批准了提案 $V_2$，此时如果批准 $V_2$ 的三个 Acceptor 中有一个（例如上图中的 5 号 Acceptor）出现了故障，那么 $V_1$ 和 $V_2$ 的批准者都变成了2个，此时就无法确定最终提案了。

也就是说，$P1$ 在某些情况下是无法选择出一个超过半数 Acceptor 都批准的提案，因此，在 $P1$ 的基础上，还需要添加一些其它的约束条件，才能够确定最终提案，在为 $P1$ 添加约束条件之前，我们回头再仔细阅读一下 Paxos 三个约束的第2个约束：

在一次 Paxos 算法的执行实例中，只批准（chosen）一个 value。

此约束并不要求 Acceptor 只能批准一个提案，也就是说 Acceptor 可以批准多个提案，只要提案的 Value 值是一样的，就不会违背上述约束；与此同时，我们使用一个全局的编号来唯一标识每一个被 Acceptor 批准的提案，也即，后续 Proposer 所提出的提案都是以 [编号，值] 的形式出现，当一个具有某 Value 值的提案被半数以上的 Acceptor 批准后，我们就认为该提案被选定了，值得说明一点的是，Paxos 并不关心如何生成这种全局编号，基于这种思路，我们在 $P1$ 的基础上，为之添加如下约束条件 $P2$：

$P2$：如果有编号为 $M_0$，Value 值具有 $V_0$ 的提案 [$M_0$, $V_0$] 被选定了，那么所有比编号 $M_0$ 大，且被选定的提案，其 Value 值必须具有 $V_0$。

约束 $P2$ 也可被描述成如下方式：

$P2$：一旦一个具有 value v 的提案被批准（chosen），那么之后批准（chosen）的提案必须具有 value v。这里所谓之后的提案是指所有编号更大的提案。

由于提案编号是全序不重复的，因此上述 $P2$ 一定能够保证只有一个 Value 最终选定这一重要的安全属性。

这里，我们仔细体会一下 $P2$ 中所描述的两句话：1.“所有比编号 $M_0$ 大，且被选定的提案”、2.“之后被批准（chosen）的提案”，这两句话虽然表述方式不同，但是都同时强调了两层含义：之后、被批准；其中的“之后”很好理解，那么我们怎么去理解“被选定”或者“被批准（chosen）”的含义呢？

某个具有 value v 的提案要“被选定”，其首先必须被至少一个 Acceptor 批准，基于这种理解，我们可以对 $P2$ 进一步加强得到如下 $P2^a$，通过 $P2^a$ 来满足 $P2$：

$P2^a$：如果有编号为 $M_0$，Value 值具有 $V_0$ 的提案 [$M_0$, $V_0$] 被选定了，那么所有比编号 $M_0$ 大，且被 Acceptor 批准的提案，其 Value 值必须具有 $V_0$。

$P2^a$ 也可按如下描述：

$P2^a$：一旦一个具有 value v 的提案被批准（chosen），那么之后任何 Acceptor 再次接受（accept）的提案必须具有 value v。

至此，我们将 $P1$ 的附加约束从 $P2$ 演变成了 $P2^a$，但是，在某些情况下，$P1$ 和 $P2^a$ 本身就有可能会出现冲突，如下图所示：

在上图中，由于通信是异步发起的，因此有可能出现这种情况：在 $Acceptor_1$ 由于网络等原因还没有收到任何提案时，其它4个 Acceptor 已经批准了来自 $Proposer_2$ 所提交的提案 [$M_0$, $V_0$]，这时网络通信又恢复正常了， $Proposer_1$ 产生的一个具有其它 Value 值 $V_1$，且编号更高的提案 [$M_1$, $V_1$]，并发送给了 $Acceptor_1$，那么问题来了：

• 由于 $Acceptor_1$ 之前尚未接受（accept）过任何提案，[$M_1$, $V_1$] 是发送给它的第一个提案，因此，按照 $P_1$ 的要求，此时 $Acceptor_1$ 必须接受提案 [$M_1$, $V_1$]。

• 但是，由于 Acceptor 集合中有4个已经批准了提案 [$M_0$, $V_0$]，按照 $P2^a$ 的要求，此时 $Acceptor_1$ 所能够接受的编号比 $M_0$ 更高的提案当中必须具有 $V_0$，否则 $Acceptor_1$ 不能够接受之，也即，按照 $P2^a$ 的要求，此时 $Acceptor_1$ 不能够接受提案 [$M_1$, $V_1$]。

针对这样的冲突，我们需要对 $P2^a$ 进一步加强，以解决之。考虑到 $P1$、$P2$、$P2^a$ 都是站在 Acceptor 的角度所提出的，我们不妨换个思路，转而对 Proposer 的行为进行约束，于是得出了如下约束：

$P2^b$：如果有编号为 $M_0$，Value 值具有 $V_0$ 的提案 [$M_0$, $V_0$] 被选定了，那么之后任何 Proposer 产生的编号更高的提案，其 Value 值必须具有 $V_0$。

$P2^b$ 也可按如下描述：

$P2^b$：一旦一个具有 value v 的提案被批准（chosen），那么以后任何 Proposer 提出的提案必须具有 value v。

因为一个提案必须被 Proposer 提出后才能够被 Acceptor 批准，因此 $P2^b$ 是一个更强的约束，它包含了 $P2^a$，进而也就间接包含了 $P2$。

虽然 $P2^b$ 不会和 $P1$ 产生冲突，但是它在具体实现上却很难找到一个较好的方案，那么我们是否能够再进一步对 $P2^b$ 加强，找到另外一个既包含 $P2^b$，又不会和 $P1$ 产生冲突，同时在具体实现上还比较简单的的约束呢？

这里，我们假设一个编号为 m 的 value v 已经获得批准（chosen），来看看在什么情况下对任何编号为 n（n > m）的提案都含有 value v。因为 m 已经获得批准（chosen），显然存在一个 Acceptor 的多数派集合 C，它们都接受（accept）了 v。考虑到任何多数派都和 C 具有至少一个公共成员，基于这种思路，我们可以找到一个蕴涵 $P2^b$ 的约束 $P2^c$：

$P2^c$：对于任意的 $M_n$ 和 $V_n$，如果提案 [$M_n$, $V_n$] 能够被 Proposer 提出，那么肯定存在一个多数派的 Acceptor 集合 S，要么 S 中所有 Acceptor 都没有批准过编号小于 $M_n$ 的任何提案，要么 S 中所有 Acceptor 批准的编号小于 $M_n$ 的提案中编号最大的那个提案的 Value 值具有 $V_n$。

$P2^c$ 也可按如下描述：

$P2^c$：如果一个编号为 n 且具有 value v 的提案能够被 Proposer 提出，那么存在一个多数派的 Acceptor 集合 S，要么它们中所有 Acceptor 都没有接受（accept）编号小于 n 的任何提案，要么它们已经接受（accept）的所有编号小于 n 的提案中编号最大的那个提案具有 value v。

下面，我们可以通过数学归纳法来证明，只要保持了 $P2^c$ 的不变性，那么 $P2^b$ 一定是成立的，也即 $P2^c$ 蕴含了 $P2^b$。

10.4.数学证明

本节，我们需要用第二数学归纳法证明 $P2^c$ 蕴含了 $P2^b$，也即，我们需要证明的是：

在 $P2^c$ 的前提下，一旦一个具有 value v 的提案被批准（chosen），那么以后任何 Proposer 提出的提案必须具有 value v。

在证明之前，我们首先回顾一下第二数学归纳法的证明步骤：

对于某个与自然数有关的命题 P(n)，
  1.假设 n = n0 时，P(n) 成立，验证 n = n1 时 P(n) 也成立；
  2.假设 n ≤ k 时命题成立，并在此基础上，推出 n = k + 1 命题也成立。
综合 1、2，对一切自然数 n(n ≥ n0)，命题 P(n) 都成立。

• 第一步：我们假设具有 value v 的提案 m 获得批准，我们需要证明的是，在 $P2^c$ 的前提下 ，当 n = m + 1 时，被 Proposer 所提出的该提案必须具有 value v；采用反证法，假设被 Proposer 提出的编号为 n 的提案不具有 value v，而是具有 value w，根据 $P2^c$，则存在一个多数派的 Acceptor 集合 $S_1$，要么它们中所有的 Acceptor 都没有接受编号小于 n 的任何提案，要么它们已经接受的所有编号小于 n 的提案中编号最大的那个提案（也即提案 m）具有 value w。由于 $S_1$ 和批准提案 m 时的多数派的 Acceptor 集合 C 之间至少有一个公共的 Acceptor，该 Acceptor 肯定接受了具有 value v 的提案 m，所以以上两个条件都不成立，导出矛盾从而推翻新提案 n 不具有 value v 的假设，证明了提案 n 必须具有 value v；

• 第二步：我们假设编号在 [m + 1, N - 1] 中的所有提案都具有 value v，我们需要证明的是，在 $P2^c$ 的前提下，被 Proposer 所提出的提案 N 也必须具有 value v；同样采用反证法，假设被 Proposer 提出的新提案 N 不具有 value v，而是具有 value w', 根据 $P2^c$，则存在一个多数派的 Acceptor 集合 $S_2$，要么它们中所有的 Acceptor 都没有接受过编号在 [m, N - 1] 中的任何提案，要么它们已经接受的所有编号小于 N 的提案中编号最大的那个提案（也即 [m + 1, N - 1] 区间中已经出被提出过的最大编号）具有 value w'。由于 $S_2$ 和批准 m 时的多数派 C 之间至少有一个公共的 Acceptor，所以至少有一个 Acceptor 曾经接受了 m，从而也可以推出 $S_2$ 中已接受的所有编号小于 n 的提案中编号最大的那个提案的编号范围在 [m, N - 1] 之间，而根据初始假设，[m, N - 1] 之间的所有提案都具有 value v，所以 $S_2$ 中已接受的所有编号小于 n 的提案中编号最大的那个提案肯定具有 value v，导出矛盾从而推翻新提案 N 不具有 value v 的假设。

根据第二数学归纳法，我们证明了若满足 $P2^c$，则 $P2^b$ 一定满足。至此，证明完毕。

$P2^c$ 是可以通过消息传递模型实现的。另外，引入了 $P2^c$ 后，也解决了 $P1$ 不完备的问题。

10.5.生成提案

为了维持 $P2^c$ 的不变性，Proposer 在生成一个编号为 $M_n$ 的提案时，需要和足以形成多数派的 Acceptor 集合的每个成员进行通信，获取它们即将接受（accept）或者已经接受的编号小于 $M_n$ 的提案中编号最大的那个提案（此过程被称为 Prepare 过程），之后 Proposer 根据从 Acceptor 集合的反馈回收的信息决定提案 $M_n$ 的 Value 值，形成提案开始投票。

此时，如果某 Acceptor 最近一次接受的提案编号为 m，它在上述 Prepare 过程中回答了 Proposer 针对提案 n （n > m）的问题，但是在开始对 n 进行投票前，又接受（accept）了编号小于 n 的由另一个 Proposer 提出的提案 k（例如 k = n - 1），如果提案 k 和提案 m 具有不同的 Value 值，这次投票就会违背 $P2^c$ 约束：

编号为 n 的提案被提出了，但是存在超过半数的 Acceptor 集合批准了编号小于 n 的提案 k，而且两个提案具有不同的 Value 值。

Acceptor 的这种行为对 Proposer 来说是很难预测的，而 Proposer 获取那些已经被通过提案远比预测未来可能会被通过的提案要简单得多，基于此种原因，为了避免上述这种很难预测的未来情况发生，Proposer 会要求 Acceptor 在回应由 Proposer 发起的提案 $M_n$ 的 Prepare 请求时，向 Proposer 承诺：不会再接受（accept）编号小于 $M_n$ 的任何提案。于是就引出了如下提案生成算法：

1. Proposer 选择一个新的提案编号 $M_n$，然后向某 Acceptor 集合中的每个成员发送请求（此请求称为编号 $M_n$ 提案的 Prepare 请求），要求它们作出如下回应：

   • 向 Proposer 承诺，保证不会批准编号小于 $M_n$ 的任何提案。
   • 如果 Acceptor 已经批准过任何提案，那么其就向 Proposer 反馈该 Acceptor 已经批准的编号小于 $M_n$ 但为最大编号的那个提案。

2. 如果 Proposer 收到了来自半数以上的 Acceptor 的响应结果，那么它就可以产生编号为 $M_n$，Value 值具有 $V_n$ 的提案，这里的 $V_n$ 是所有响应中编号最大的提案所具有的 Value 值。还有另一种情况，就是半数以上的 Acceptor 都没有批准过任何提案，即响应中不含有任何提案，那么 $V_n$ 的值就可以由 Proposer 任意选择。

在确定提案之后，Proposer 会将该提案再次发送给某个 Acceptor 集合，并期望获得它们的批准，我们称此请求为 Accept 请求，不过此时的 Acceptor 集合不必与之前响应 Prepare 请求的 Acceptor 集合相同。

10.6.批准提案

针对 Acceptor，它可能会收到来自 Proposer 的两种请求：Prepare 请求和 Accept 请求，它们的响应情况如下：

• Prepare 请求：Acceptor 可以在任何时候响应一个 Prepare 请求。
• Accept 请求：在不违背 Acceptor 在 Prepare 阶段所做出的承诺的前提下，可以任意响应 Accept 请求。

换句话说，对 Acceptor 的 Accept 请求处理逻辑有如下约束：

$P1^a$：一个 Acceptor 只要尚未回应过任何编号大于 $M_n$ 的 Prepare 请求，则此 Acceptor 就可接受（accept）这个编号为 $M_n$ 的提案。

这可以看作是对 $P1$ 约束的加强，也就是说，$P1^a$ 蕴含 $P1$，我们只要同时保证了 $P1^a$ 和 $P2^c$ 就一定能够同时满足 $P1$ 和 $P2$，也就一定能够生产一个最终提案。

值得注意的是，Paxos 算法允许 Acceptor 忽略任何请求而不用担心破坏其算法的安全属性。

10.7.算法优化

在一个 Paxos 实例中，每个提案需要有不同的编号，且编号间要存在全序关系。可以用多种方法实现这一点，例如将序数和 Proposer 的名字拼接起来，如何做到这一点不在 Paxos 算法讨论的范围之内。接下来我们需要对 Paxos 算法进行一个小小的优化。

假设一个 Acceptor 收到了一个编号为 $M_n$ 的 prepare 请求，但此时该 Acceptor 已经对编号大于 $M_n$ 的 Prepare 作出了响应，因此它肯定不会再批准任何新的编号为 $M_n$ 的提案，它也就没有必要对这个 Prepare 请求做出响应，于是 Acceptor 可以选择忽略这样的 Prepare 请求。同时，Acceptor 也可以用忽略掉那些它已经批准过的提案的 Prepare 请求。

通过这个优化，每个 Acceptor 只需要记住它已经批准过的编号最大的那个提案，以及它已经做出 Prepare 请求响应的提案的最大编号，以便在出现故障或者节点重启的情况下，也能够保证 $P2^c$ 的不变性。而对于 Proposer 来说，它只需要保证不产生相同编号的提案，它就可以丢弃任意的提案以及它所有的运行时状态信息。

10.8.算法陈述

结合 Proposer 和 Accept 对提案的处理逻辑，可以将优化后的 Paxos 算法的处理流程划分为如下两个阶段：

• 阶段一

  1. Proposer 选择一个提案编号 $M_n$，然后向某个超过半数的 Acceptor 集合中的每个成员发送编号为 $M_n$ 的 Prepare 请求。

  2. 如果一个 Acceptor 收到一个编号为 $M_n$ 的 Prepare 请求，且 $M_n$ 大于该 Acceptor 已经响应的所有 Prepare 请求的编号，那么它就会将它已经批准过的编号最大的提案作为响应反馈给 Proposer，同时对 Proposer 承诺不会再批准任何编号小于 $M_n$ 的提案。

     比如，某个 Acceptor 已经响应过的 Prepare 请求对应的提案编号分别是 1、3、5、7，当该 Acceptor 接收到一个编号为 8 的 Prepare 请求后，就会将编号为 7 的提案作为响应反馈给 Proposer，并向 Proposer 承诺，不会再批准任何编号小于 8 的提案。

• 阶段二

  1. 如果 Proposer 收到来自半数以上的 Acceptor 对于其发出的编号为 $M_n$ 的 Prepare 请求的响应，那么它就会发送一个针对 [$M_n$, $V_n$] 提案的 Accept 请求给 Acceptor。这里的 $V_n$ 是收到的所有响应中编号最大的提案所具有的 Value 值，如果响应中不包含任何提案，那么它就是任意值。

     上面这段话在 Paxos Made Simple 中的原文如下：

     If the proposer receives a response to its prepare requests
     (numbered n) from a majority of acceptors, then it sends an accept request to each of those acceptors for a proposal numbered n with a value v, where v is the value of the highest-numbered proposal among the responses, or is any value if the responses reported no proposals.

  2. 如果某个 Acceptor 收到针对 [$M_n$, $V_n$] 提案的 Accept 请求，只要该 Acceptor 尚未对编号大于 $M_n$ 的 Prepare 请求做出响应，它就可以批准这个提案。

在实际运行过程中，每个 Proposer 都有可能生成多个提案，但只要每个 Proposer 都按照如上所述的算法运行，就一定能够保证算法执行的正确性。值得一提的是，每个 Proposer 都可以在任意时刻丢弃一个提案，哪怕针对该提案的请求和响应在提案丢弃后会到达，根据 Paxos 算法的一系列规约，依然可以保证其在提案选定上的正确性。事实上，如果某个 Proposer 已经在试图生成编号更大的提案，那么丢弃一些旧的提案未尝不是一个好的选择。因此，如果一个 Acceptor 由于已经收到过更大编号的 Prepare 请求而忽略某个编号更小的 Prepare 或者 Accept 请求，那么它也应当通知其它 Proposer，以便该 Proposer 也能够将该提案丢弃。这是一个不影响正确性的性能优化措施。

10.9.提案获取

下面我们讨论一下，提案生成后，如何让 Learner 获取提案，大致有如下几种方案：

• 方案一

  Learner 获取一个已经被选定的提案的前提是，该提案已经被半数以上的 Acceptor 批准，因此，最简单的做法就是一旦 Acceptor 批准了一个提案，就将该提案发送给所有 Learner。

  这种做法虽然可以让 Learner 尽快的获取被选定的提案，但是区需要让每个 Acceptor 与所有 Learner 逐个进行一次通信，通信的次数至少为二者的乘积。

• 方案二

  由于上述方案通信次数较多的缺陷，我们让所有的 Acceptor 将它们对提案的批准情况统一发送给某个特定的 Learner，我们称这样的 Learner 为主 Learner，在不考虑拜占庭将军问题的前提下，我们假定 Learner 之间可以通过消息互通来感知提案的选定情况。基于这样的前提，当主 Learner 被通知一个提案已经被选定时，它会负责通知其它 Learner。

  这此方案中，Acceptor 会首先将得到批准的提案发送给主 Learner，再由其同步给其它 Learner，相较于方案一而言，此方案需要多一个步骤才能够将提案通知到所有的 Learner，但是却大大降低了通信次数，通常只是 Acceptor 和 Learner 的个数总和。但同时，该方案引入了一个新的不稳定因素：主 Learner 随时可能出现故障。

• 方案三

  根据方案二的缺陷，我们对之稍加改进，将主 Learner 的范围扩大，让 Acceptor 将批准的提案发送给一个特定的 Learner 集合，该集合中的每个 Learner 都可以在一个提案被选定后通知其它所有 Learner。这个集合中的 Learner 个数越多，可靠性就越好，但是网络通信的复杂度就会越高。

但是，在实际的网络环境中，还有可能会出现一种比较极端的情况：在一个提案被选定后，由于网络信息丢失的原因， 没有任何 Learner 能够获取到这个被选定的提案；于是 Learner 就需要主动向 Acceptor 集合询问它们所批准的提案， 但此时有可能会因为某个或者某些 Acceptor 出现故障，而无法判断是否存在某个被多数 Acceptor 集合批准的提案，在这种情况下，Learner 只有在一个新的提案被批准后才能够获得一个具体的提案。此外，Learner 可以通过扮演 Proposer 角色，按照上面的算法，向 Acceptor 提出一个提案的方式判断是否有被批准的提案。

10.10.可进展性

可以很容易都在出这样一个场景，两个 Proposer 依次提出了一系列编号递增的提案，但是它们最终都无法被选定，具体过程如下：

Proposer $P_1$ 提出了一个编号为 $M_1$ 的提案，并完成了阶段一的流程，此时另一个 Proposer $P_2$ 提出了一个编号为 $M_2$ （$M_2$ > $M_1$）的提案，同样也完成了阶段一的流程，于是 Acceptor 向 $P_2$ 承诺不再批准任何编号小于 $M_2$ 的提案。因此，当 $P_1$ 进入阶段二后，其发出的 Accept 请求将被 Acceptor 忽略，此时 $P_1$ 会重新进入阶段一，并提出一个编号为 $M_3$ （$M_3$ > $M_2$）的提案，而这又会导致 Acceptor 忽略 $P_2$ 在第二阶段提出的 Accept请求，以此类推，提案的选定过程将会陷入死循环。

为了保证 Paxos 算法流程的可进展性，避免出现上述场景，就必须选择一个 Proposer 作为主 Proposer，并规定，只有主 Proposer 才能够提出提案。这样，只要主 Proposer 和过半的 Acceptor 能够进行正常的网络通信，那么但凡主 Proposer 提出一个编号更高的提案，该提案最终将会被批准。当然，如果主 Proposer 发现当前算法流程中已经有一个编号更大的提案被提出或者正在接受批准，那么它会丢弃当前这个编号较小的提案，并进行重试，最终也能够选择出一个编号足够大的提案。因此，只要系统中有足够多的组件（Proposers、Acceptors、Communication networks）能正常工作，那么通过选择一个主 Proposer，就能够保证整套 Paxos 算法流程的活性。依据 Fischer、Lynch 和 Patterson 在他们的论文 Impossibility of distributed consensus with one faulty process 中的描述，对主 Proposer 的选举要么具有随机性，要么具有实时性（可以通过引入超时机制来保证实时性）。然而，无论选举是否成功，安全性都可以保证。

10.11.算法实现

在具体编码实现的过程中，Paxos 算法具体会涉及到一系列网络进程：

• 其中每个进程分别扮演不同的角色（Proposer、Acceptor、Learner），算法会选择出作为主 Proposer 和主 Learner 的 Leader；
• 算法所涉及的请求和响应都是按照普通的网络消息进行传递；
• 为了避免混淆，会将 Response 消息用与之对应提案编号进行标记；
• 使用可靠性的存储设备来存储 Acceptor 需要记住的信息以防止出错；Acceptor 在真正送出响应之前，会将它们记录在可靠性存储设备中。

Paxos 通过如下机制来保证提案编号的唯一性：

• 不同的 Proposer 会从不相交的编号集中选择提案编号，因此，两个不同的 Proposer 永远不会选择出相同的编号。
• 每个 Proposer 需要将它目前生成的最大编号的提案记录在可靠性存储设备中，并在阶段一选出一个比它已经使用过的最大编号还要大的编号。

10.12.状态机

实现一个分布式系统最为简单的方法是由一系列客户端集合向一个中心服务器提交命令请求，可以将此中心服务器当成一个确定性状态机，它按某个顺序去执行客户端所发送的命令。状态机有一个当前的状态，它将命令作为输入，经过一些列步骤的处理，产生输出和一个新的状态。比如，一个分布式银行系统的客户端可能是一些出纳员，状态机状态由所有用户的账户余额组成，当发生取款操作时，就可以执行一个减少用户的账户余额的状态机命令，但是当且仅当用户账户余额大于取款额时，才能够执行此操作，如果执行成功，状态机会将会输出旧的余额和新的余额，同时也就从一个旧的状态切换到了一个新的状态。

使用中央服务器的系统在该服务器失败的情况下，整个系统就失败了，因此，通常情况下，我们会使用一个服务器集合来替代它，集合中的每个服务器都会独立的实现一个状态机。由于状态机本身具有确定性，如果它们都按照相同的命令序列执行，那么就会产生相同的状态机状态和输出。一个产生命令的客户端，就可以使用任意服务器为它产生的输出。

为了保证所有的服务器都执行相同的状态机命令序列，我们需要实现一系列独立的 Paxos 一致性算法实例，其中第 $i$ 个实例所选定的值就是状态机命令序列当中的第 $i$ 个命令。换句话说，每个 Paxos 一致性算法实例都会和状态机命令序列当中的某个命令呈一对一的对应关系。在每个算法实例执行的过程中，每台服务器都会在不同的角色（Proposer、Acceptor、Learner）之间来回转换，我们假设服务器集合是固定的，这样所有的一致性算法实例都具有相同的参与者集合。

在正常执行中，会选择出唯一能尝试提出提案的 Server 作为主 Proposer 来充当 Leader 的角色，客户端向该 Leader 发送命令，然后由 Leader 来决定每个命令被安排在序列中的何处。如果Leader决定某个客户端命令应该是第 135 个命令，它会尝试让该命令成为第 135 个一致性算法实例选定的 Value 值，通常，这都会成功，但是由于出错或者存在另外一个 Server 也认为自己是 Leader，而它对第 135 个命令应该具有的值持有异议，此时就会导致上述批准失败。但是一致性算法会保证，最多只有一个命令会被选定为第 135 个命令。

此方法的关键在于，在 Paxos 一致性算法中，只有进行到阶段二时，被提出的 Value 才会被选定，回忆一下，当 Proposer 完成阶段一后，要么提案的 Value 已确定，要么 Proposer 可以自由地提出一个值。

我们阐述了在正常情况下，Paxos 状态机实现是如何工作的，接下来，我们讨论下出错的情况，看下当上一个 Leader 出现故障，新 Leader 被选出时会发生些什么。(系统启动是一种特殊情况，此时还没有命令被提出)。

新的 Leader 选出来后，首先要成为所有一致性算法执行实例的 Learner，它必须知道目前已经选定的大部分命令。假设它知道命令 1-134，138 及 139 —— 也就是一致性算法实例 1-134，138 及 139 选定的值（稍后，我们会看下命令间的缺口是如何形成的）。然后，它需要对编号在 135-137 之间以及所有其它大于 139 的算法实例执行阶段一（下面会描述如何来做）。假设执行结果表明，在执行实例 135 和 140 中被提出的提案值已经确定，但是其它执行实例的提案值是没有限制的，那么现在该 Leader 就可以对实例 135 和 140 执行阶段二，进而选出第 135 和 140 号命令。

Leader 以及其它所有已经获取该 Leader 所已知命令的服务器，现在可以执行命令 1-135 了，然而它还不能执行它已经知道的 138-140 ，因为命令 136 和 137 还未选定。Leader 可以将接下来的两个由客户端发起的请求命令作为 136 和 137。但是我们也可以提出一个特殊的 noop 命令作为 136 和 137 号命令来填补这个空缺以保证状态的不变性(通过执行一致性算法实例 136 和 137 的阶段二来完成) 。一旦该 noop 命令被选定，命令 138-140 就可以执行了。

命令 1-140 目前已被选定了。Leader 也已经完成了所有大于 140 的一致性算法实例的阶段一，而且它们可以在阶段二中自由的提出任何值。Leader 会将下一个客户端的请求命令作为第 141 个命令，并且在阶段二中将它作为第 141 个一致性算法实例的value值，然后将下一个客户端的请求命令作为第 142 个命令，以此类推。

Leader 可以在它提出的命令 141 被选定前提出命令 142。它发送的关于命令 141 的消息有可能全部丢失，因此在所有其它服务器在获知 Leader 选定了谁作为命令 141 之前，命令 142 就可能已被选定。当 Leader 无法收到实例 141 在阶段二反馈给它所期望的响应后，它会重传这些信息，如果一切正常，它所提出的命令就会被选定，但是仍然可能会失败，这样就会在被选定的命令序列中出现缺口。假设一个 Leader 可以提前确定 $\alpha$ 个命令，这意味着在 $i$ 被选定之后，它就可以提出从 $i + 1$ 到 $i + \alpha$ 的命令了，这样就可能形成一个长达 $\alpha - 1$ 的命令缺口。

一个新选择的 Leader 需要为无数个一致性算法实例执行阶段一 —— 在上面的情景中，就是 135-137 以及所有大于 139 的实例。只要向其它的服务器发送一个合适的短消息，就可以让所有的实例使用同一个的提案编号计数器。在阶段一，只要一个 Acceptor 已经收到来自某个 Proposer 的阶段二消息，那么它就可以为不止一个的执行实例做出承诺（在上面的场景中，就是针对 135 和 140 的情况）。因此一个服务器（作为 Acceptor 角色时）通过选择一个适当的短消息就可以对所有实例做出响应，那么执行这样无限多个实例的阶段一也就不会有问题。

因为 Leader 的失败和新 Leader 的选举都是很少见的情况，因此执行一个状态机命令——即在命令值上达成一致性的代价就是执行该一致性算法的阶段二的代价 。可以证明，在允许失效的情况下，在所有的一致性算法中，Paxos 算法的阶段二所消耗的代价是最低的。因此 Paxos 算法基本就是最优的。

在系统正常执行情况下，我们假设总是只有一个 Leader，只有在当前 Leader 失效及选举出新 Leader 的较短时期内才会违背这个假设。在特殊情况下，Leader 选举可能失败。如果没有服务器担任 Leader，那么就没有新命令被提出。如果同时有多个服务器认为自己是 Leader，它们在一个一致性算法执行实例中可能提出不同的 Value，这可能会导致一个 Value 也无法选出。但是，安全性可以保证——即不可能同时会有两个命令被选定为第 $i$ 个状态机命令。Leader 的选举只是为了保证系统的可进展性。

如果服务器集合是可变的，那么必须有某种方式来决定哪些服务器来实现哪些一致性算法实例。最简单的方式就是通过状态机本身来完成。当前的服务器集合可以作为状态的一部分，同时可以通过某些状态机命令来改变。同时通过用执行完第 $i$ 个状态机命令后的状态来描述执行一致性算法实例 $i + \alpha$ 的服务器集合，我们就能让 Leader 在执行完第 i 个状态机命令后可以提前获取 $\alpha$ 个状态机命令。这就提供了一种支持任意复杂度的重配置算法的简单实现。

11.References

[1] 维基百科——Paxos算法
[2] 分布式系统：概念与设计
[3] Time, Clocks, and the Ordering of Events in a Distributed System
[4] Dr. Eric A. Brewer：CAP
[5] Brewer's CAP Theorem
[6] How to beat the CAP theorem
[7] CAP Confusion: Problems with ‘partition tolerance’
[8] Deconstructing the `CAP theorem' for CM and DevOps
[9] Errors in Database Systems, Eventual Consistency, and the CAP Theorem
[10] Perspectives on the CAP Theorem
[11] BASE: An Acid Alternative
[12] Eventually Consistent-Revisited
[13] The Byzantine Generals Problem
[14] The Part-Time Parliament
[15] Revisiting the Paxos Algorithm
[16] Paxos Made Simple
[17] 大规模分布式存储系统：原理解析与架构实战
[18] Architecture and Design of Large Scale Distributed
[19] 从paxos到zookeeper：分布式一致性原理与实践
[20] Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services