科普文：分布式数据一致性协议Paxos

1 什么是Paxos

　　Paxos协议其实说的就是Paxos算法, Paxos算法是基于消息传递且具有高度容错特性的一致性算 法，是目前公认的解决分布式一致性问题最有效的算法之一。

　　Paxos由 莱斯利·兰伯特(Leslie Lamport)于1998年在《The Part-Time Parliament》论文中首次公 开，最初的描述使用希腊的一个小岛Paxos，描述了Paxos小岛中通过决议的流程，并以此命名这个算 法，但是这个描述理解起来比较有挑战性。后来在2001年，莱斯利·兰伯特重新发表了朴实的算法描述版 本《Paxos Made Simple》

　　 自Paxos问世以来就持续垄断了分布式一致性算法，Paxos这个名词几乎等同于分布式一致性。 Google的很多大型分布式系统都采用了Paxos算法来解决分布式一致性问题，如Chubby、Megastore 以及Spanner等。开源的ZooKeeper，以及MySQL 5.7推出的用来取代传统的主从复制的MySQL Group Replication等纷纷采用Paxos算法解决分布式一致性问题。然而，Paxos的最大特点就是难，不仅难以 理解，更难以实现。 Google Chubby的作者Mike Burrows说过这个世界上只有一种一致性算法，那就是Paxos，其它 的算法都是残次品。

　　在整个 Paxos 算法的实现过程中，将参与算法的集群中的全部服务器，分成三种角色：提议者（Proposer）、决策者（Acceptor）、决策学习者（Learner）。

• 提议者（Proposer）：提出提案（Proposal）。Proposal 信息包括提案编号（Proposal ID）和提议的值（Value）。
• 决策者（Acceptor）：参与决策，回应 Proposers 的提案。收到 Proposal 后可以接受提案，若 Proposal 获得超过半数 Acceptors 的许可，则称该 Proposal 被批准。
• 决策学习者：不参与决策，从 Proposers/Acceptors 学习最新达成一致的提案（Value）。

　　在 Paxos 算法中，当处理来自客户端的事务性会话请求的过程时，首先会触发一个或多个服务器进程，就本次会话的处理发起提案。当该提案通过网络发送到集群中的其他角色服务器后，这些服务器会就该会话在本地的执行情况反馈给发起提案的服务器。发起提案的服务器会在接收到这些反馈信息后进行统计，当集群中超过半数的服务器认可该条事务性的客户端会话操作后，认为该客户端会话可以在本地执行操作。 Paxos 算法则采用多副本的处理方式，即存在多个副本，每个副本分别包含提案者、决策者以及学习者。

　　整个提案的处理过程可以分为三个阶段，分别是提案准备阶段、事务处理阶段、数据同步阶段。

• 提案准备阶段：该阶段是整个 Paxos 算法的最初阶段，所有接收到的来自客户端的事务性会话在执行之前，整个集群中的 Proposer 角色服务器或者节点，需要将会话发送给 Acceptor 决策者服务器。在 Acceptor 服务器接收到该条询问信息后，需要返回 Promise ，承诺可以执行操作信息给 Proposer 角色服务器。
• 事务处理阶段：在经过提案准备阶段，确认该条事务性的会话操作可以在集群中正常执行后，Proposer 提案服务器会再次向 Acceptor 决策者服务器发送 propose 提交请求。Acceptor 决策者服务器在接收到该 propose 请求后，在本地执行该条事务性的会话操作。
• 数据同步阶段：在完成了事务处理阶段的操作后，整个集群中对该条事务性会话的数据变更已经在 Acceptor 决策者服务器上执行完成，当整个集群中有超过半数的 Acceptor 决策者服务器都成功执行后，Paxos 算法将针对本次执行结果形成一个决议，并发送给 Learner 服务器。当 Learner 服务器接收到该条决议信息后，会同步 Acceptor 决策者服务器上的数据信息，最终完成该条事务性会话在整个集群中的处理。

2 Paxos 解决了什么问题

在常见的分布式系统中，总会发生诸如机器宕机或网络异常（包括消息的延迟、丢失、重复、乱 序，还有网络分区）等情况。Paxos算法需要解决的问题就是如何在一个可能发生上述异常的分布式系 统中，快速且正确地在集群内部对某个数据的值达成一致，并且保证不论发生以上任何异常，都不会破 坏整个系统的一致性。

注：这里某个数据的值并不只是狭义上的某个数，它可以是一条日志，也可以是一条命令 （command）。。。根据应用场景不同，某个数据的值有不同的含义。

　　2PC 和 3PC的时候在一定程度上是可以解决数据一致性问题的. 但是并没有完全解决就 是协调者宕机的情况。

如何解决2PC和3PC的存在的问题呢?

　　步骤1-引入多个协调者。

　　步骤-引入主协调者,以他的命令为基准。

　　其实在引入多个协调者之后又引入主协调者.那么这个就是最简单的一种Paxos 算法. Paxos的版本有: Basic Paxos , Multi Paxos, Fast-Paxos, 具体落地有Raft 和zk的ZAB协议。

2.1 Basic Paxos

1. 角色介绍

　　Client:客户端 客户端向分布式系统发出请求，并等待响应。例如，对分布式文件服务器中文件的写请求。

　　Proposer：提案发起者 提案者提倡客户端请求，试图说服Acceptor对此达成一致，并在发生冲突时充当协调者以推 动协议向前发展

　　Acceptor: 决策者，可以批准提案 Acceptor可以接受（accept）提案；并进行投票, 投票结果是否通过以多数派为准, 以如果某 个提案被选定，那么该提案里的value就被选定了 Learner: 最终决策的学习者 学习者充当该协议的复制因素(不参与投票)。

　　basic paxos流程 basic paxos流程一共分为4个步骤:

　　Prepare Proposer提出一个提案,编号为N, 此N大于这个Proposer之前提出所有提出的编号, 请求 Accpetor的多数人接受这个提案。

　　Promise 如果编号N大于此Accpetor之前接收的任提案编号则接收, 否则拒绝。

　　Accept 如果达到多数派, Proposer会发出accept请求, 此请求包含提案编号和对应的内容。

　　Accepted 如果此Accpetor在此期间没有接受到任何大于N的提案,则接收此提案内容, 否则忽略。

2.2 Multi-Paxos

　　Multi-Paxos在实施的时候会将Proposer，Acceptor和Learner的角色合并统称为“服务器”。因此， 最后只有“客户端”和“服务器”。

2.3 Raft协议

　　Paxos 是论证了一致性协议的可行性，但是论证的过程据说晦涩难懂，缺少必要的实现细节，而且 工程实现难度比较高, 广为人知实现只有 zk 的实现 zab 协议。

　　Paxos协议的出现为分布式强一致性提供了很好的理论基础，但是Paxos协议理解起来较为困难， 实现比较复杂。

　　然后斯坦福大学RamCloud项目中提出了易实现，易理解的分布式一致性复制协议 Raft。Java， C++，Go 等都有其对应的实现之后出现的Raft相对要简洁很多。引入主节点，通过竞选确定主节点。节 点类型：Follower、Candidate 和 Leader.

　　Sentinel系统选举leader的方法是对Raft算法的leader选举方法的实现。

　　Leader 会周期性的发送心跳包给 Follower。每个 Follower 都设置了一个随机的竞选超时时间，一 般为 150ms~300ms，如果在这个时间内没有收到 Leader 的心跳包，就会变成 Candidate，进入竞选 阶段, 通过竞选阶段的投票多的人成为Leader.

1. 节点状态

　　Leader（主节点）：接受 client 更新请求，写入本地后，然后同步到其他副本中

　　Follower（从节点）：从 Leader 中接受更新请求，然后写入本地日志文件。对客户端提供读 请求

　　Candidate（候选节点）：如果 follower 在一段时间内未收到 leader 心跳。则判断 leader 可能故障，发起选主提议。节点状态从 Follower 变为 Candidate 状态，直到选主结束

2. termId：任期号，时间被划分成一个个任期，每次选举后都会产生一个新的 termId，一个任期内 只有一个 leader。

3. RequestVote：请求投票，candidate 在选举过程中发起，收到多数派响应后，成为 leader。

竞选阶段流程:

　　1. 最初阶段只有 Follower，没有 Leader。Follower A 等待一个随 机的竞选超时时间之后，没收到 Leader 发来的心跳包，因此进入竞选阶段。

　　2.此时 A 发送投票请求给其它所有节点.

　　3.其它节点会对请求进行回复，如果超过一半的节点回复了，那么该 Candidate 就会变成 Leader。

　　4. 之后 Leader 会周期性地发送心跳包给 Follower，Follower 接收到心跳包，会重新开始计时.

　　如果有多个 Follower 成为 Candidate，并且所获得票数相同，那么就需要重新开始投票.当重新开始投票时，由于每个节点设置的随机竞选超时时间不同，因此能下一次再次出现多个 Candidate 并获得同样票数的概率很低.

　　面对网络分区，Raft甚至可以保持一致。 1. 最初始正常情况下状态,B节点会对其他4个节点发送心跳.

　　当出现网络分区情况,但是出现网络分区的请求后,只能对A发送心跳,同时其他三个节点会再次选出 一个leader节点.不同分区写入数据不同,节点Termid最大成为Leader节点,同步节点数据,达成数据一致性.

　　在处理事务性的回来请求时，Raft 算法中的领导者服务器会执行该条会话操作，但并不提交，只是将该操作写入到日志中，再发送给集群中的其他服务器。当接收到超过一半的服务能够正常操作的反馈信息后，领导者服务器才最终提交本次会话请求操作，并向集群中的其他服务器发送提交请求。

2.4 Zab协议

ZAB 协议算法（Zookeeper Atomic Broadcast ，Zookeeper 原子广播协议）是 ZooKeeper 专门设计用来解决集群最终一致性问题的算法，它的两个核心功能点是崩溃恢复和原子广播协议。

　　在整个 ZAB 协议的底层实现中，ZooKeeper 集群主要采用主从模式的系统架构方式来保证 ZooKeeper 集群系统的一致性。整个实现过程如下图所示，当接收到来自客户端的事务性会话请求后，系统集群采用主服务器来处理该条会话请求，经过主服务器处理的结果会通过网络发送给集群中其他从节点服务器进行数据同步操作。

　　以 ZooKeeper 集群为例，这个操作过程可以概括为：当 ZooKeeper 集群接收到来自客户端的事务性的会话请求后，集群中的其他 Follow 角色服务器会将该请求转发给 Leader 角色服务器进行处理。当 Leader 节点服务器在处理完该条会话请求后，会将结果通过操作日志的方式同步给集群中的 Follow 角色服务器。然后 Follow 角色服务器根据接收到的操作日志，在本地执行相关的数据处理操作，最终完成整个 ZooKeeper 集群对客户端会话的处理工作。

　　 就这种ZooKeeper 架构方式而言，极易产生单点问题，即当集群中的 Leader 发生故障的时候，整个集群就会因为缺少 Leader 服务器而无法处理来自客户端的事务性的会话请求。因此，为了解决这个问题。在 ZAB 协议中也设置了处理该问题的崩溃恢复机制。

　　崩溃恢复机制是保证 ZooKeeper 集群服务高可用的关键。触发 ZooKeeper 集群执行崩溃恢复的事件是集群中的 Leader 节点服务器发生了异常而无法工作，于是 Follow 服务器会通过投票来决定是否选出新的 Leader 节点服务器。

　　投票过程如下：当崩溃恢复机制开始的时候，整个 ZooKeeper 集群的每台 Follow 服务器会发起投票，并同步给集群中的其他 Follow 服务器。在接收到来自集群中的其他 Follow 服务器的投票信息后，集群中的每个 Follow 服务器都会与自身的投票信息进行对比，如果判断新的投票信息更合适，则采用新的投票信息作为自己的投票信息。在集群中的投票信息还没有达到超过半数原则的情况下，再进行新一轮的投票，最终当整个 ZooKeeper 集群中的 Follow 服务器超过半数投出的结果相同的时候，就会产生新的 Leader 服务器。

　　筛选过程：首先，会对比 logicClock 服务器的投票轮次，当 logicClock 相同时，表明两张选票处于相同的投票阶段，并进入下一阶段，否则跳过。接下来再对比 vote_zxid 被选举服务器上所保存的最大事务 ID，若接收到的外部投票信息中的 vote_zxid 字段较大，则将自己的票中的 vote_zxid 与 vote_myid 更新为收到的票中的 vote_zxid 与 vote_myid ，并广播出去。要是对比的结果相同，则继续对比 vote_myid 被选举的服务器 ID 信息 ，若外部投票的 vote_myid 比较大，则将自己的票中的 vote_myid 更新为收到的票中的 vote_myid 。 经过这些对比和替换后，最终该台 Follow 服务器会产生新的投票信息，并在下一轮的投票中发送到 ZooKeeper 集群中。

　　消息广播：在 Leader 节点服务器处理请求后，需要通知集群中的其他角色服务器进行数据同步。ZooKeeper 集群采用消息广播的方式发送通知。该协议的底层实现过程二阶段提交过程非常相似，如下图所示。

　　当要在集群中的其他角色服务器进行数据同步的时候，Leader 服务器将该操作过程封装成一个 Proposal 提交事务，并将其发送给集群中其他需要进行数据同步的服务器。当这些服务器接收到 Leader 服务器的数据同步事务后，会将该条事务能否在本地正常执行的结果反馈给 Leader 服务器，Leader 服务器在接收到其他 Follow 服务器的反馈信息后进行统计，判断是否在集群中执行本次事务操作。

　　ZAB 协议算法能够保证 ZooKeeper 集群服务在处理事务性请求后的数据一致性 ，当集群中的 Leader 服务器发生崩溃的时候，ZAB 协议算法可以在 ZooKeeper 集群中重新选举 Leader 并进行数据的同步恢复。其中值得注意的是消息广播的底层实现过程虽然与二阶段提交非常相似，但是与二阶段提交相比，并没有事务丢弃的过程。在 ZooKeeper 集群的消息广播中，只要满足整个集群中超过半数的 Follow 服务器可以执行本次事务操作，Leader 就可以向集群中发送提交事务操作，最终完成数据的变更。

　　Paxos 算法与 ZAB 协议不同的是，Paxos 算法的发起者可以是一个或多个。当集群中的 Acceptor 服务器中的大多数可以执行会话请求后，提议者服务器只负责发送提交指令，事务的执行实际发生在 Acceptor 服务器。这与 ZooKeeper 服务器上事务的执行发生在 Leader 服务器上不同。Paxos 算法在数据同步阶段，是多台 Acceptor 服务器作为数据源同步给集群中的多台 Learner 服务器，而 ZooKeeper 则是单台 Leader 服务器作为数据源同步给集群中的其他角色服务器。