【Zookeeper 技术专题】从 Paxo 算法出发认识一下 Zookeeper

Paxo 算法介绍

Paxos 算法是莱斯利·兰伯特(Leslie Lamport)1990 年提出的一种基于消息传递的一致性算法。

Paxos 产生背景

Paxos 算法是基于消息传递且具有高度容错特性的一致性算法，是目前公认的解决分布式一致性问题最有效的算法之一，其解决的问题就是在分布式系统中如何就某个值（决议）达成一致。

Paxos 算法主要是针对 Zookeeper 这样的 master-slave 集群对某个决议达成一致，也就是副本之间写或者 leader 选举达成一致。我觉得这个算法和狭义的分布式事务不是一样的。

在常见的分布式系统中，总会发生诸如机器宕机或网络异常（包括消息的延迟、丢失、重复、乱序，还有网络分区），也就是会发生异常的分布式系统)等情况。

Paxos 算法需要解决的问题就是如何在一个可能发生上述异常的分布式系统中，快速且正确地在集群内部对某个数据的值达成一致。也可以理解成分布式系统中达成状态的一致性。

Paxos 保证一致性：

Paxos 算法是分布式一致性算法用来解决一个分布式系统如何就某个值(决议)达成一致的问题。一个典型的场景是，在一个分布式数据库系统中，如果各节点的初始状态一致，每个节点都执行相同的操作序列，那么他们最后能得到一个一致的状态。

为保证每个节点执行相同的命令序列，需要在每一条指令上执行一个“一致性算法”以保证每个节点看到的指令一致。

分布式系统中一般是通过多副本来保证可靠性，而多个副本之间会存在数据不一致的情况。所以必须有一个一致性算法来保证数据的一致，描述如下：

假如在分布式系统中初始是各个节点的数据是一致的，每个节点都顺序执行系列操作，然后每个节点最终的数据还是一致的。

Paxos 算法就是解决这种分布式场景中的一致性问题。对于一般的开发人员来说，只需要知道 paxos 是一个分布式选举算法即可。

多个节点之间存在两种通讯模型：共享内存（Shared memory）、消息传递（Messages passing），Paxos 是基于消息传递的通讯模型的。

发生网络分区所导致的数据不一致问题，就是 Paxo 算法需要解决的问题！

拜占庭问题

拜占庭问题：是指拜占庭帝国军队的将军们必须全体一致的决定是否攻击某一支敌军。

• 问题是这些将军在地理上是分隔开来的，只能依靠通讯员进行传递命令，但是通讯员中存在叛徒，它们可以篡改消息，叛徒可以欺骗某些将军采取进攻行动；

• 促成一个不是所有将军都同意的决定，如当将军们不希望进攻时促成进攻行动；或者迷惑某些将军，使他们无法做出决定。

Paxos 算法的前提假设是不存在拜占庭将军问题，即： 信道是安全的（信道可靠），发出的信号不会被篡改，因为 Paxos 算法是基于消息传递的。它也是 Paxos 算法的提出者,由于硬件和网络原因而造成的消息不完整问题，只需要一套简单的校验算法即可。

Paxos 算法概念

在 Paxos 算法中，有三种角色：

• Proposer（投票发起者）：Proposer 负责提出提案

• Acceptor（投票接受者）：Acceptor 负责对提案作出裁决（accept 与否）

• Learner（节点学习者）：learner 负责学习提案结果

Proposal：这里的一个很重要的概念叫提案（Proposal），可以理解为我们的一个操作或者数据信息传递，最终要达成一致的 value 就在提案里。

Paxo 算法的特点介绍

一个进程或者服务节点可能同时充当多种角色，可能既是 Proposer 又是 Acceptor 又是 Learner 。

• 只要 Proposer 发的提案被 Acceptor 接受（半数以上的 Acceptor 同意才行），Proposer 就认为该提案里的 value 被选定了。

• Acceptor 告诉 Learner 哪个 value 被选定，Learner 就认为那个 value 被选定。只要 Acceptor 接受了某个提案，Acceptor 就任务该提案里的 value 被选定了。

Paxo 算法的投票和认可机制

为了避免单点故障，会有一个 Acceptor 集合，Proposer 向 Acceptor 集合发送提案，Acceptor 集合中的每个成员都有可能同意该提案且每个 Acceptor 只能批准一个提案，只有当一半以上的成员同意了一个提案，就认为该提案被选定了。

Paxos 算法的解决的问题描述

• 有多个（propose）value（value 在提案 Proposal 里）的进程集合。一致性算法需要保证提出的这么多 value 中，只有一个 value 被选定（chosen）。

• 如果没有 value 被提出，就不应该有 value 被选定。如果一个 value 被选定，那么所有进程都应该能学习（learn）到这个被选定的 value。

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

• 保证最终有一个 value 会被选定，当 value 被选定后，进程最终也能获取到被选定的 value。

Paxos 算法的过程

Paxos 算法类似于两阶段提提交，其算法执行过程分为两个阶段。具体如下：

• 阶段一（prepare 阶段）：

• Proposer 选择一个提案编号 N，然后向半数以上的 Acceptor 发送编号为 N 的 Prepare 请求:Proposal（N）。

• 如果一个 Acceptor 收到一个编号为 N 的 Prepare 请求：

• 若小于它已经响应过的请求，则拒绝，不回应或回复 error。

• 若 N 大于该 Acceptor 已经响应过的所有 Prepare 请求的编号（maxN），那么它就会将它已经接受过的编号最大的提案作为响应反馈给 Proposer，同时该 Acceptor 承诺不再接受任何编号小于 N 的提案。

如果还没有的 accept 提案的话返回{pok，null，null}

• 阶段二（accept 阶段）：

• 如果一个 Proposer 收到半数以上 Acceptor 对其发出的编号为 N 的 Prepare 请求的响应，那么它就会发送一个针对[N,V]提案的 Accept 请求给半数以上的 Acceptor。注意：V 就是收到的响应中编号最大的提案的 value，如果响应中不包含任何提案，那么 V 就由 Proposer 自己决定。

• 如果 Acceptor 收到一个针对编号为 N 的提案的 Accept 请求，只要该 Acceptor 没有对编号大于 N 的 Prepare 请求做出过响应，它就接受该提案。

• 如果 N 小于 Acceptor 以及响应的 prepare 请求，则拒绝，不回应或回复 error（当 proposer 没有收到过半的回应，那么他会重新进入第一阶段，递增提案号，重新提出 prepare 请求）。

• 

Paxos 算法的过半依据

Paxos 基于的过半数学原理： 我们称大多数（过半）进程组成的集合为法定集合， 两个法定（过半）集合必然存在非空交集，即至少有一个公共进程，称为法定集合性质。 例如 A,B,C,D,F 进程组成的全集，法定集合 Q1 包括进程 A,B,C，Q2 包括进程 B,C,D，那么 Q1 和 Q2 的交集必然不在空，C 就是 Q1，Q2 的公共进程。如果要说 Paxos 最根本的原理是什么，那么就是这个简单性质。也就是说：两个过半的集合必然存在交集，也就是肯定是相等的，也就是肯定达成了一致。xie