参考文献(文章内容几乎全部来自下面的参考文献，强烈建议看看原文)

分布式系统的一致性与共识算法-基础理论

分布式系统的一致性与共识算法-Paxos

一、分布式系统下的一致性问题

        定义：一致性为在分布式系统领域中对于多个服务节点，给定一系列操作，在约定协议的保障下，使得它们对处理结果达成某种程度的协同。

        分布式系统中的节点通信存在两种模型：共享内存（Shared memory）和消息传递（Messages passing）。基于消息传递通信模型的分布式系统，不可避免的会发生以下错误：进程可能会响应慢、被杀死或者重启，对应消息可能会延迟、丢失、重复；发生上面任意一种异常都会对分布式系统中各个节点对某一个值达成一致性产生问题。

一致性的要求：

• 可终止性（Termination）：一致的结果在有限时间内能完成（可以保障提供服务的（Liveness））
• 约同性（Agreement）：不同节点最终完成决策的结果是相同的（意味着算法要么不给出结果，任何给出的结果必定是达成了共识的，即安全性（Safety））
• 合法性（Validity）：决策的结果必须是某个节点提出的提案（即达成的结果必须是节点执行操作的结果）

解决一致性问题的核心在于对不同空间发生的事件进行全局唯一排序。关于全局排序概念，强烈建议另一个系列的博客：分布式栏目。

一致性模型：

• 强一致性模型：(1) 顺序一致性：所有操作都以某种顺序原子执行，该顺序与各个节点上看到的顺序一致，并且在所有节点上都相等；可以基于Lamport timestamp 即逻辑时钟进行实现。(2) 线性一致性：所有操作都按照操作的全局实时顺序一致的顺序自动执行；在顺序一致性前提下加强了进程间的操作排序，形成唯一的全局顺序；依赖于全局的时钟或锁，有很强的原子性保证，但是比较难实现。
• 弱一致性模型：(1)最终一致性：在未来的某个时间点进行冲突检测和修正，如DNS。(2)客户端为中心型一致性：通过在client端库中建立额外的缓存来实现，如亚马逊Dynamo。(3)在上面的分布式专栏中，实际上还存在一种叫因果一致性，这是一种比弱一致性强，但比顺序一致性弱的一致性概念。

二、拜占庭将军问题

        拜占庭将军问题是 Leslie Lamport 在《The Byzantine Generals Problem》论文中提出的分布式对等网络通信容错问题，为分布式领域中最复杂、最严格的容错模型；拜占庭将军问题讨论的是允许存在少数节点作恶（消息可能被伪造）场景下的如何达成共识问题。(有人说，如果你只能选择分布式领域一篇文章阅读，那么最好选择这一篇文章，不过这篇原文据说非常的晦涩难懂)

        拜占庭是古代东罗马帝国的首都，由于地域宽广，守卫边境的多个将军（类比系统中的多个节点）需要通过信使来传递消息，达成某些一致决定。但由于将军中可能存在叛徒（类比系统中节点出错），这些叛徒将向不同的将军发送不同的消息，试图干扰共识的达成；拜占庭问题即讨论在此情况下，如何让忠诚的将军们能达成行动的一致。

        例如：有9位将军投票，其中1名叛徒。8名忠诚的将军中出现了4人投进攻，4人投撤离的情况。这时候叛徒可能故意给4名投进攻的将领送信表示投票进攻，而给4名投撤离的将领送信表示投撤离。这样一来在4名投进攻的将领看来，投票结果是5人投进攻，从而发起进攻；而在4名投撤离的将军看来则是5人投撤离，军队的一致协同就遭到了破坏。

       在该模型下的系统不会对集群中的节点做任何的限制，它们可以向其他节点发送随机数据、错误数据，也可以选择不响应其他节点的请求，这些无法预测的行为使得容错这一问题变得更加复杂。在分布式场景下，拜占庭需求并不多见，一般存在于容易匿名参与的系统（如虚拟币），或者伪造信息会造成巨大损失的情况（如金融系统）。

        通过上面的示例，拜占庭将军的问题大致可以归结为：假如有n个节点，每个节点都会向其他节点传递消息，其中m个节点可能是"叛徒"，就是说，“叛徒”可能会向其余节点传递错误的消息，也可能不给他们发送消息(这里“叛徒”节点可能对每个节点作出的选择不一样，比如对1节点发送数据a，对2节点发送数据b，对3节点不给予回应)，拜占庭将军解决的问题是如何使得“忠诚”的将军彼此之间得到每个节点正确的消息(这个正确是指获得“忠诚”节点之间达成一致的消息)。

       这里其实在上面那个专栏中，仔细讨论过平时说的一致性和共识的区别，一致的英文是consistency，而共识的英文是consensus，实际上，这两个概念有区别，但没有特别明显的区别，但是我个人对这个的理解是：共识更强调对一个“提案”达成一致，而一致性似乎更偏向于对数据达成一致。所谓的“提案”可可以是数据，也可以是策略，或者说，把不同的计算机看作一种状态机，没执行一条指令，都是状态机状态发生变化，假如所有状态机处于同一状态，而需要进行状态变换的时候，需要所有状态机变换到同一状态，实际上并不需这么强的状态统一，而是感觉更宏观的状态，对外界的响应是统一的，就是从外界看来，这些分布式的计算机如同一个计算机一样。而一致性更偏向于对数据的一致，但是，如果共识算法是对数据达成共识，实际上也保证了数据的一致性。

早期解决办法

        在《The Byzantine Generals Problem》论文中提过几个解决方案，方案中把问题往下拆解，认为在在“拜占庭将军”的问题可以在“军官与士官的问题”里解决，以降低将军问题的发生。而所谓的“军官与士官的问题”，就是探讨军官与他的士官是否能忠实实行命令。

        解决方案1：即使出现了伪造或错误的消息。只要有问题的将军的数量不到三分之一，仍可以达到“拜占庭容错”。比如有军官A，士官B与士官C。当A要求B进攻，却要求C撤退时。就算B与C交换所收到的命令，B与C仍不能确定是否A有问题，因为B或C可能将窜改了的消息传给对方。以函数来表示，将军的总数为n，n里面背叛者的数量为 t，则只要 n > 3t 就可以容错。这实际上是将这体问题简化为子问题，就是说如果通过信息交换，单个节点可以判断出信息的准确性，那么所有忠诚的节点采用同一算法可以解决这个问题，但是这要求背叛者的数量小于1/3。

        解决方案2：通过如数字签名的方式来实现拜占庭容错，并以此来找到有问题的将军。如果保证传递的信息都是正确的，那么背叛这小于n-1就行。

实用拜占庭容错算法

        Practical Byzantine Fault Tolerance，PBFT（实用拜占庭容错算法），由 Castro 和 Liskov 于论文《Practical Byzantine Fault Tolerance and Proactive Recovery》中提出。该算法基于Paxos相关算法进行了优化，将拜占庭容错算法复杂度从指数级降低到了多项式（平方）级，可以在恶意节点不超过总数 1/3 的情况下同时保证 Safety 和 Liveness，得到广泛应用。

PBFT算法采用密码学相关技术（RSA 签名算法、消息验证编码和摘要）确保消息传递过程无法被篡改和破坏。

三、共识算法

3.1 共识（Consensus）与一致性（Consistency）

        一致性：含义比共识宽泛，在不同场景（基于事务的数据库、分布式系统等）下意义不同。在分布式系统场景下，一致性指的是多个副本对外呈现的状态。如之前提到的顺序一致性、线性一致性，描述了多节点对数据状态的共同维护能力。

        共识：特指在分布式系统中多个节点之间对某个事情达成一致看法的过程。需注意达成某种共识并不意味着就保障了一致性。

        怎么说呢，其实和前面的个人见解不同，实际上网上对这种区别，每个人都有自己的理解，但是，跟人理解，像顺序一致性，还是从内存的角度看待，在执行指令过程中的内存一致性。共识，怎么说呢，分布式计算机需要对执行的指令达成一致。但是指令达成一致，并不能保证分布式计算机会转移到统一状态，也许指令过程出现意外，或者怎么样，那么，当一台计算机出现意外，如果存在分区容错，那么剩下的分区应该正常运行，如果不要分区容错，那所有的计算机应该要进行回滚，等待节点修复，再次达成一致状态。感觉还是有点模糊清....

3.2 共识算法解决的问题

        共识算法解决的是分布式系统对某个提案（Proposal），大部分节点达成一致意见的过程。提案泛指多个事件发生的顺序、某个键对应的值…对于分布式系而言，各个节点通常都是相同的确定性状态机模型（又称为状态机复制问题，State-Machine Replication），从相同初始状态开始接收相同顺序的指令，则可以保证相同的结果状态。

这里共识算法需要解决两个基本问题：

1. 如何提出一个待共识的提案（令牌传递、随机选取…）
2. 如何让多个节点对提案达成共识（投票、规则验证…）

现实网络环境中存在各种各样的问题，在分布式环境下，共识算法还需要解决如通信问题（网络中断、分区）、节点故障、消息伪造…

3.3 共识算法分类

        根据是否允许拜占庭错误（伪造信息恶意响应）的情况，共识算法分为 Crash Fault Tolerance 崩溃容错 (CFT) 和 Byzantine Fault Tolerance（BFT）两类。怎么理解呢，就是说，根据传递的消息的正确性进行判别，像Crash Fault 节点宕机，那么就是不能发送消息，但是节点如果恢复，那么他发送的消息一定是正确的。而像拜占庭错误，节点没有发送消息，并不一定就代表宕机了，也许是故意不发送，而即使发送消息，可能也会故意发送错误的消息。

Crash Fault Tolerance (CFT) 算法：Paxos、Raft、ZAB…

Byzantine Fault Tolerance(BFT) 算法：PBFT为代表的确定性系列算法、PoW为代表的概率算法…

四、FLP不可能定理、CAP理论、ACID原则与BASE原则

4.1 同步/异步系统模型

       同步系统模型：指系统中的各个节点的时钟误差存在上限；并且消息传递必须在一定时间内完成，否则认为失败；同时各个节点完成处理消息的时间是一定的。因此同步系统中可以很容易地判断消息是否丢失。

        异步系统模型：系统中各个节点可能存在较大的时钟差异；同时消息传输时间是任意长的；各节点对消息进行处理的时间也可能是任意长的。这就造成无法判断某个消息迟迟没有被响应是哪里出了问题（节点故障还是传输故障）。现实生活中的系统往往都是异步系统。

        说实话，没咋理解，主要却没有实例，有点太抽象了.....

4.2 FLP不可能原理

        定义：由 Fischer，Lynch 和 Patterson 三位科学家发表的《Impossibility of Distributed Consensus with One Faulty Process》论文中提出，在网络可靠，但允许节点失效（即便只有一个）的最小化异步模型系统中，不存在一个可以解决一致性问题的确定性共识算法。

        描述：FLP不可能原理假定节点只能因崩溃而失败； 网络可靠，并且异步系统模型的典型时序假设成立：例如，消息延迟没有限制的情况下，假设有A、B、C三个节点进行投票，A投票0，B投票1，而C收到了A与B的投票却没办法响应，A与B就没办法在有限的时间内获知最终结果；如果进行重新投票，类似的情况重复发生，则永远无法达到共识。

        FLP 不可能原理的意义在于，告诉我们不要浪费时间去为异步分布式系统设计在任意场景上都能够实现共识的算法，异步系统完全没有办法保证能在有限时间内达成一致。

4.3 CAP理论

       CAP定理（CAP theorem），又被称作布鲁尔定理（Brewer’s theorem），它指出对于一个分布式计算系统来说，不可能同时满足以下三点，只能满足三项中的两项：

• 一致性（Consistency） : 任何事务都应该是原子的，所有副本上的状态都是事务成功提交后的结果，并保持强一致性。
• 可用性（Availability） : 系统正常节点能在有限时间内完成对操作请求的应答。
• 分区容错性（Partition tolerance） : 系统中的网络可能发生分区故障（成为多个子网、节点上线和下线），节点之间的通信无法保障，而网络故障不应该影响到系统正常服务。

        这里的一致性实际的含义是从事务的角度说的，当对某个提议达成共识以后，并不能保证分布式计算机都处于同一状态，不同计算机执行过程中很难保证执行成功，其实这里把共识的提议当作一种事务，利用下层应用的原子性保证事务的一致性。

CAP理论证明：

假设有两个通信中的节点出现了网络分区的情况，如果允许其中一个节点更新状态，则需要舍弃一致性（C）；如果为了保证数据一致性，将分区的节点设置为不可用，就需要舍弃可用性（A）；如果两个节点可以互相通信，才能既保证一致性又保证可用性，会丧失分区容错性（P）。

CA\CP区别：CA和CP系统设计均提供相同的一致性模型：高度一致性。 唯一的区别是CA系统不能容忍任何节点故障。 CP系统可以容忍 f 在给定 2f+1 在非拜占庭式故障模型中。

场景

• CA：弱化了分区容错性，早期分布式关系数据库系统中使用的许多系统设计如两阶段提交，都没有考虑分区容错性。 分区容错性是现代系统的重要属性，因为如果系统在多个地理环境上分布，网络分区出现的概览就会加大。
• CP：弱化了可用性，一些对结果一致性很敏感的应用会选择基于此模型设计，当系统出现故障时会拒绝服务；Paxos、Raft 等共识算法，以及HBase、MongoDB等基于此模型设计。
• AP：弱化了一致性，一些对结果一致性不敏感的应用会选择基于此模型设计，可以允许在新版本上线后过一段时间才最终更新成功，期间不保证一致性；分布式同步协议如 Gossip，以及DynamoDB、 CouchDB、Cassandra 数据库等基于此模型设计。

4.3 ACID原则与BASE原则

    ACID即Atomicity(原子性)、Consistency(一致性)、Isolation(隔离性)、Durability(持久性)四种特性的缩写，一般出现在分布式数据库等基于事务过程的系统中；ACID 原则描述了分布式数据库需要满足的一致性需求，同时允许付出可用性的代价。

• Atomicity: 每次事务是原子的，事务包含的所有操作要么全部成功，要么全部不执行。一旦有操作失败，则需要回退状态到执行事务之前；
• Consistency: 数据库的状态在事务执行前后的状态是一致的和完整的，无中间状态。即只能处于成功事务提交后的状态；
• Isolation: 各种事务可以并发执行，但彼此之间互相不影响。按照标准 SQL 规范，从弱到强可以分为读未提交、读已提交、可重复读取和串行化四种隔离等级(MySQL的四个级别)；
• Durability: 状态的改变是持久的，不会失效。一旦某个事务提交，则它造成的状态变更就是永久性的。

BASE原则

BASE即 Basic Availability（基本可用），Soft-state（弱状态），Eventual Consistency（最终一致性），为 eBay 技术专家 Dan Pritchett 提出的与ACID相对的一个原则，主要面向大型高可用分布式系统，主张牺牲掉对强一致性的追求，而实现最终一致性，来换取一定的可用性。

• Basic Availability：系统在出现不可预知的故障时候，允许损失部分可用性，保证核心服务可用。
• Soft-state：允许系统在不同节点的数据副本之间进行数据同步的过程中存在延时（允许系统中的数据存在中间状态，不会影响系统的整体可用性）。
• Eventual Consistency：系统中所有的数据副本，在进过一段时间的同步后，最终能够达到一个一致的状态。

五、核心问题——复制

5.1 复制与分区

• 分区：将数据集划分为更小的不同的独立集合; 这是用来减少数据集增长的影响，提高性能
• 复制：在多台计算机上复制相同的数据; 允许更多的服务器参与计算，主要是为了通过为数据新副本提供额外的计算能力和带宽，从而提高性能；因为数据的独立副本必须在多台计算机上保持同步，这意味着确保复制遵循内存一致性模型

为什么核心问题是复制：分布式存储相关的系统都必须用某种冗余的方式在廉价硬件的基础上搭建高可靠的存储，而冗余的基础就是复制（多副本策略）, 一份数据存多份. 多副本保证了可靠性, 而副本之间的一致, 就需要各种分布式共识算法来保证.

复制是一个组通信问题。需要考虑哪种通信方式可以为我们提供我们想要的性能和可用性特性？面对网络分区以及节点同时发生故障，我们如何确保容错性，持久性以及避免分歧。

5.2 基本复制方式

• 同步复制：强持久化保证，系统响应慢，对网络延迟敏感(这种就和三阶段提交之类的算法相似，放弃了高可用性)。
• 异步复制：弱持久化保证，性能高，对网络延迟更加宽容(这种弱化了一致性保证了高可用性)。

5.3 基本复制算法

        基本复制算法大致可以分为两类：Replication methods that prevent divergence (single copy systems) 防止差异的复制方式（单拷贝系统）与Replication methods that risk divergence (multi-master systems) 有差异风险的复制方式（多主系统）

5.3.1 Replication Methods that Prevent Divergence (single Copy systems)

        对外表现得像一个单独的系统；当部分故障发生时，系统确保只有一个系统副本处于活动状态；系统需要确保副本始终保持一致，基于某一种共识算法去实现，一般有如下几种方式：

5.3.1.1 Master/Slave（主从复制）

        所有更新都在主服务器上执行，操作日志(或者更改)通过网络传送到备份副本；涉及两种相关的变体异步主/备份、同步主/备份、半同步主/备复制。

同步复制

       直到数据真的安全的复制到全部的机器上之后, master才告知客户端数据已经完成同步。

存在问题：强一致性持久化保证，但是系统响应慢，对网络延迟的变化非常敏感；并且系统的可用性随着副本数量指数降低，任何一个机器的宕机都会影响到整个系统的写入。

异步复制

        master将更新存储在本地后立即向客户端发回响应，master在之后才进行异步复制到全部的机器上。

存在问题：性能高，但是为弱一致性持久化保证，数据存在丢失风险，会造成数据不一致的情况。

半同步复制

        要求master在应答客户端之前必须把数据复制到足够多的机器上, 而非全部机器. 这样副本数够多可以提供比较高的可靠性; 1台机器宕机也不会让整个系统停止写入; 但系统中还是会存在数据不一致的情况。

5.3.1.2 2-phase commit（两阶段提交）

阶段一：投票阶段，协调人向所有参与者发送更新信息。每个参与者处理更新，并投票决定是提交还是放弃。当投票决定提交时，参与者将更新存储到一个临时区域（write-ahead log）。

阶段二：协调程序决定结果并通知每个参与者。如果所有参与者投票提交，那么更新将从临时区域获得并永久化。

问题：强一致性持久化保证，但是系统响应慢，对网络延迟的变化非常敏感；系统的可用性随着副本数量指数降低。

两阶段提交详见：

5.3.1.3 Quorum机制（多数派）

        Quorum 机制，是一种分布式系统中常用的，用来保证数据冗余和最终一致性的投票算法，其主要数学思想来源于鸽巢原理；在分布式系统中，Quorum常用于副本的读写控制，容忍最多 (N-1)/2 个节点损坏。

假设每份数据有V个副本，每个副本对应一票，读、写操作首先要请求副本以获取其票数，定义：

read quorum R（最小读票数）：读操作获取的票数必须大于该值才允许读；
write quorum W（最小写票数）：写操作获取的票数必须大于该值才允许写；

V、R、W必须满足：

• R + W > V：保证对于每份数据，不会 同时读和写（当一个写操作请求过来的时候，它必须要获得W个写票。而剩下的数量是V-W是不够R的，因此不能再有读请求过来了）。
• W > V / 2：保证对于每份数据，不会同时出现 两个写，即写操作是串行的。

其他

• 没有规定 R > V / 2，quorum 机制允许 多个读同时发生，即允许 并发读；
• 考虑write -> read序列，因为R + W > V，因此 W 和 V 之间至少有一个重叠（鸽巢原理），从而保证 write 之后，read 操作至少会获取一个最新副本；
• 在做复制冗余的时候，借助 Quorum 机制，5 个副本只需要完成 3 个写即可响应成功，提升了写操作的响应速度，又没有减弱可靠性；Quorum 机制本质上是把写负载转移到了读负载的一种设计权衡。

问题：

• 读取不一致状态情况：对于一条数据的更新时, 会产生不一致的状态问题：如第一次client update，nodeA、nodeB写入a=x；第二次client update，nodeB、nodeC写入a=y；如果读取a的客户端联系到nodeA和nodeB，会得到不一致的数据（解决：对每次的写入增加全局时间戳，以后写入的优先）

nodeA: a=x 1577851200000
nodeB: a=y 1577851230000
nodeC: a=y 1577851230000

 这个问题本身就是算法设计时本身存在的问题，因为上面的约束可以保证读到最新的数据，但是如果没有标志能指明最新数据是什么，那么仅仅是读取到的数据包含最新的数据罢了。

• 多数派写异常情况：在完成一起完整的多数派写时，发生写入异常，会产生不一致的状态问题：如第一次client update，nodeA、nodeB写入a=x；第二次client update，nodeB、nodeC写入a=y；但是只有nodeC写入成功了，然后client abort了，这时候另一个client 读取到nodeA与nodeB得到的结果与读取到nodeB与nodeC的不一致。

nodeA: a=x 1577851200000
nodeB: a=x 1577851200000
nodeC: a=y 1577851230000

• 并发环境下，因为无法保证顺序执行，所以无法保证系统的正确性。 

结论

Quorum机制无法保证强一致性，即无法实现任何时刻任何用户或节点都可以读到最近一次成功提交的副本数据；后续Paxos对Quorum机制进行了改进，通过2次多数派读写, 实现了严谨的强一致共识算法。并且，读操作可以并法而写操作必须系列化，也就是，如过尽量减少W的数量，就是说减少每次更新机器的数量是不是能够对外提供更好的性能？

5.3.2 Replication Methods that risk Divergence (multi-master systems)

5.3.1.2 Gossip算法

Gossip算法Palo Alto研究中心在论文《Epidemic Algorithms for Replicated Database Maintenance》中提出的一种用于分布式数据库在多节点间复制同步数据的算法；特点是要同步的信息如同流言一般传播，最终一致性。

具体的工作过程如下：

1. 如果有某一项信息需要在整个网络中所有节点中传播，那从信息源开始，选择一个固定的传播周期（如1秒），随机选择它 相连接的k个节点（称为Fan-Out）进行消息传播。
2. 每一个节点收到消息后，如果这个消息是它之前没有收到过的，将在下一个周期内，选择除了发送消息给它的那个节点外的 其他相邻k个节点发送相同的消息，理论上最终网络的所有节点都会拥有相同的消息。

上图从一致性、延迟、吞吐量、数据丢失和故障转移对比了各个类型共识算法实现。

六、Paxos算法

6.1 关于Paxos

        Paxos算法是Leslie Lamport于1990年提出的一种基于消息传递共识算法，能保证多副本数据强一致性与分区容错性(CP)；现已是当今分布式系统最重要的理论，为后续的如Raft、ZAB等算法、ZooKeeper、Etcd等分布式协调框架奠定了基础。

例如：Paxos可以协同让多个机器成为一个整体的系统，这个系统中的每个机器都必须让系统中的状态达成一致，如果在三副本集群中的一台机器上上传了一个文件，其他两台机器也必须复制这个文件，达到系统的一致性。

Google Chubby的作者给了Paxos极高的评价：There is only one consensus protocol, and that’s “Paxos” — all other approaches are just broken versions of Paxos（世界上只有一种共识协议，就是Paxos，其他所有共识算法都是Paxos的退化版本）。

6.2 问题-假设

问题：基于前文对分布式环境下一致性与共识算法的基础理论，在分布式系统中进行节点通信大部分采用基于消息传递通信模型，不可避免的会发生如进程可能会慢、被杀死或者重启等问题，会对分布式系统中各个节点对某一个值达成一致性产生问题；而Paxos就是为了解决这个问题而生的。

场景：在一个分布式数据库系统中，如果各节点的初始状态一致，每个节点都执行相同的操作序列，那么他们最后能得到一个一致的状态。为保证每个节点执行相同的命令序列，需要在每一条指令上执行一个“一致性算法”以保证每个节点看到的指令一致。

假设：Lamport虚构了一个名为Paxos的希腊城邦，这个城邦按照民主制度制定法律，却又不存在一个中心化的专职立法机构，立法靠着“兼职议会”（Part-Time Parliament）来完成，无法保证所有城邦居民都能够及时地了解新的法律提案、也无法保证居民会及时为提案投票。Paxos算法的目标就是让城邦能够在每一位居民都不承诺一定会及时参与的情况下，依然可以按照少数服从多数的原则，最终达成一致意见。注意：Paxos算法并不考虑拜占庭将军问题，即假设信息可能丢失也可能延迟，但不会被错误传递。

Paxos算法运行在允许宕机故障的异步系统中，不要求可靠的消息传递，可容忍消息丢失、延迟、乱序以及重复，保证了2F+1的容错能力，即2F+1个节点的系统最多允许F个节点同时出现故障。

6.3 算法详解

6.3.1 Paxos算法中对应的角色

• Proposer：提出提案 (Proposal)；可以理解为客户端，Proposal信息包括提案编号 (Proposal ID) 和提议的值 (Value)，这个提议值不一定是一个数，其目也不一定是实现数据的一致性。
• Acceptor：参与决策，可以理解为存储节点，回应Proposers的提案。收到Proposal后可以接受提案，若Proposal获得多数派Acceptors的接受，则称该Proposal被批准。
• Learners：用于学习被批准的提案。

Paxos算法中的角色允许身兼数职，也有了如下的基本约束：

1. 决策（value）只有在被 proposers 提出后才能被批准（未经批准的称为提案）；
2. 在一次 Paxos 算法的执行实例中，只批准（chosen）一个 value；
3. Learners 只能获得被批准（chosen）的 value。

6.3.2 系统模型

一个系统中，存在多个Proposer节点提出提案，多个Acceptor节点负责决策-接受提案。为了满足只批准一个 value 的约束，要求经Quorum（多数派）接受的 value 成为正式的决议。即一个提案被选定需要被半数以上的Acceptor接受。

Quorum机制下，假设只有一个Proposer提出了一个value，该value也会被决策，要保证约束2，就会产生P1约束P1：一个Acceptor必须接受第一次收到的提案。

P1 是不完备的，不同的Proposer提出不同的value的话，如果遵循P1，就会出现无法形成多数派的情况；因为存在多个提案，这里就需要给每个提案加上一个提案编号以表示顺序，即提案=编号+Value；只要提案的 value 是一样的，批准多个提案不违背约束2，我们就可以保证只有一个值被选中，可以得到如下约束P2：如果某个value为v的提案被批准（chosen），那么之后批准（chosen）的提案必须具有 value v。

因为一个提案只有被Acceptor接受才可能被选定，所以我们可以把P2约束改写成对Acceptor接受的提案的约束P2a：一旦一个具有 value v 的提案被批准（chosen），那么之后任何 Acceptor 再次接受（accept）的提案必须具有 value v。

因为通信是异步的，系统是不可靠的，P2a和P1可能会存在冲突，例如一个 value 被批准后，一个Proposer 和一个 Acceptor 从休眠中苏醒，前者提出一个具有新的 value 的提案；这种情况下根据 P1，Acceptor应当接受，根据 P2a，则不应当接受（如下图所示）， P2a 和 P1 有矛盾。于是需要换个思路，转而对 proposer 的行为进行约束得到P2b：一旦一个具有 value v 的提案被批准（chosen），那么以后任何 Proposer 提出的提案必须具有 value v。

由于 acceptor 能接受的提案都必须由 proposer 提出，所以 P2b 蕴涵了 P2a，是一个更强的约束。但是根据 P2b 难以提出实现手段，需要进一步加强 P2b；假设一个编号为 m 的 Value v 已经获得批准，存在一个 Acceptors 的多数派 C，他们都接受（accept）了v，考虑到任何多数派都和 C 具有至少一个公共成员，可以找到一个蕴涵 P2b 的约束 P2c：如果一个编号为 n 的提案具有 value v，该提案被提出，那么存在一个多数派，要么他们中所有人都没有接受（accept）编号小于 n 的任何提案，要么他们已经接受（accept）的所有编号小于 n 的提案中编号最大的那个提案具有 value v。

要满足P2c的约束，会涉及两个流程：

• prepare阶段：Proposer提出一个提案前，要和足以形成多数派的Acceptors进行通信，获得他们进行的最近一次接受（accept）的提案，根据回收的信息决定这次提案的value，形成提案开始投票。
• 批准阶段：当获得多数acceptors接受（accept）后，提案获得批准（chosen），由Acceptor将这个消息告知learner（这个过程逐渐细化，就形成了Paxos算法）

并发情况下：如果一个没有chosen过任何proposer提案的Acceptor在prepare过程中回答了一个proposer针对提案n的问题，但是在开始对n进行投票前，又接受（accept）了编号小于n的另一个提案（例如n-1），如果n-1和n具有不同的value，这个投票就会违背P2c。因此需要对P1进行加强，在prepare过程中，acceptor进行的回答后不会再接受（accept）编号小于n的提案，P1a：当且仅当Acceptor没有回应过编号大于n的prepare请求时，Acceptor接受（accept）编号为n的提案。

6.3.3 prepare阶段：为什么需要获取多数派Acceptor最近接受的提案

如果两个Proposer进程并发进行读写操作, 在多数派读写的实现中,会产生一个Proposer覆盖另一个Proposer的问题. 从而产生了数据更新点丢失的情况

以上图为例子：

问题：Proposer2步骤4进行多数派写的时候，因为并发问题覆盖了Proposer1的多数派写操作，导致Proposer1写入的值失效。

如何解决：Proposer2更新的时候不能直接更新i2版本，而是应该检测到i2的存在, 进而将自己的结果保存在下一个版本i3中,再进行多数派写。问题可推广：系统对于i的某个版本，只能有一次写入—> 一个值（变量的一个版本）被确定了之后，不允许进行修改

解决方案：每次Proposer写之前进行一次多数派读，以便确认是否存在其他Proposer在写；如果存在，则放弃写入；这种操作称为写前读取操作。

6.3.4 并发进行写前读取操作(确定一个值)导致数据不一致问题

问题：可能出现两个Proposer同时进行写前读取操作，获取到的结果都是没有其他Proposer在写入;这时候同时进行写操作，还是会造成数据不一致的情况。

如何解决：Acceptor节点需要记录最后一个做过写前读取操作的Proposer；进行限制，只允许最后一个完成写前读取的Proposer可以进行后续写入,拒绝之前做过写前读取的Proposer写入的权限。

已上便是Paxos的核心原理，通过两次多数派读，以此多数派写，实现了强一致性的共识算法。

6.3.5 提案的提出与批准

prepare阶段

1. Proposer选择一个提案编号N并将prepare请求发送给Acceptors中的一个多数派；
2. Acceptor收到一个编号为N的prepare消息后，且N大于该Acceptor已经响应过的所有Prepare请求的编号，那么它就会将它已经接受过的编号最大的提案作为响应反馈给Proposer，同时该Acceptor承诺不再接受任何编号小于N的提案。

批准阶段

1. 如果Proposer收到半数以上Acceptor对其发出的编号为N的Prepare请求的响应，进入批准阶段。Proposer会发送一个针对[N,V]提案的Accept请求给半数以上的Acceptor。（V为prepare阶段响应中编号最大的提案的value，如果响应中不包含任何提案，那么V就由Proposer决定）
2. 如果Acceptor收到一个针对编号为N的提案的Accept请求，只要该Acceptor没有对编号大于N的Prepare请求做出过响应，就接受该提案。

6.3.6 Paxos总结