图解分布式一致性协议 Paxos 算法【BAT 面试题宝库附详尽答案解析】

一个会写诗的程序员

发布于 2019-12-20 10:50:38

1.2K0

发布于 2019-12-20 10:50:38

文章被收录于专栏：一个会写诗的程序员的博客一个会写诗的程序员的博客

0. 问题场景

1.Paxos 简介

Paxos is a family of protocols for solving consensus in a network of unreliable processors. 分布式系统中，多个节点的数据, 如何保持一致性?
Paxos is a family of protocols for solving consensus in a network of unreliable processors (that is, processors that may fail). Consensus is the process of agreeing on one result among a group of participants. This problem becomes difficult when the participants or their communication medium may experience failures.[1] Consensus protocols are the basis for the state machine replication approach to distributed computing, as suggested by Leslie Lamport [2] and surveyed by Fred Schneider.[3] State machine replication is a technique for converting an algorithm into a fault-tolerant, distributed implementation. Ad-hoc techniques may leave important cases of failures unresolved. The principled approach proposed by Lamport et al. ensures all cases are handled safely.

https://en.wikipedia.org/wiki/Paxos_(computer_science)

1990年，Leslie Lamport在论文《The Part-Time Parliament》(http://lamport.azurewebsites.net/pubs/lamport-paxos.pdf)中提出Paxos算法。由于论文使用故事的方式，没有使用数学证明，起初并没有得到重视。直到1998年该论文才被正式接受。后来2001年Lamport又重新组织了论文，发表了《Paxos Made Simple》。作为分布式系统领域的早期贡献者，Lamport获得了2013年图灵奖。

Paxos算法广泛应用在分布式系统中，Google Chubby的作者Mike Burrows说：“这个世界上只有一种一致性算法，那就是 Paxos（There is only one consensus protocol, and that's Paxos）”。

后来的Raft算法、是对Paxos的简化和改进，变得更加容易理解和实现。

Paxos算法是目前公认的解决分布式一致性问题最有效的算法之一。

在一个分布式系统中，由于节点故障、网络延迟等各种原因，根据CAP理论，我们只能保证一致性（Consistency）、可用性（Availability）、分区容错性（Partition Tolerance）中的两个。

对于一致性要求高的系统，比如银行取款机，就会选择牺牲可用性，故障时拒绝服务。MongoDB、Redis、MapReduce使用这种方案。

对于静态网站、实时性较弱的查询类数据库，会牺牲一致性，允许一段时间内不一致。简单分布式协议Gossip，数据库CouchDB、Cassandra使用这种方案。

如图所示，一致性问题，可以根据是否存在恶意节点分类两类。无恶意节点，是指节点会丢失、重发、不响应消息，但不会篡改消息。而恶意节点可能会篡改消息。有恶意节点的问题称为拜占庭将军问题，不在今天的讨论范围。Paxos很好地解决了无恶意节点的分布式一致性问题。

Paxos算法的核心问题是：解决分布式系统的一致性的问题，所有问题均围绕着在分布式环境达成一致性而展开讨论的。Paxos算法为了达成一致性，算法就必须保证其安全性和活性。

安全性：只有被提出的提案才能被选定，并且只有一个提案被选定。
活性：最终保证会有一个提案被选定。

安全性和活性的组合结果就是：最终有且只有一个被提出的提案被选定。

拜占庭将军问题

提及paxos协议的起源，首先得说说这个“拜占庭将军”问题，这个问题实际上是分布式数据一致性问题的一个抽象故事。

拜占庭将军问题（Byzantine failures）:

拜占庭位于如今的土耳其的伊斯坦布尔，是东罗马帝国的首都。 Leslie Lamport在1982年提出虚拟模型，用来解释一致性问题。拜占庭作为东罗马帝国的首都，地域辽阔，在首都周边有众多将军负责城防，将军之间通过信使来传递消息，达成某些一致的决定。但由于将军中存在叛徒，叛徒会想尽一切办法干扰一致性的达成，甚至是达成叛徒想要的共识从而实现攻击。

拜占庭问题，假设节点总数是N，叛徒将军数为F，则当 N >= 3F+1 时，问题才有解，共识才能达成，这就是Byzantine Fault Tolerant（BFT）算法。

拜占庭假设是对现实世界的模型化，由于硬件错误、网络拥塞或断开以及遭到恶意攻击，计算机和网络可能出现不可预料的行为。拜占庭容错协议必须处理这些失效，并且这些协议还要满足所要解决的问题要求的规范。这些算法通常以其弹性t作为特征，t表示算法可以应付的错误进程数。在n ≥ 3t+1时才有解，其中n是系统中进程的总数。

科学告诉你什么是不可能的；工程则告诉你，付出一些代价，我可以把它变成可能。这就是工程的魅力。

Byzantine Fault Tolerant算法

面向拜占庭将军问题的容错算法，解决的是网络通信可靠，但节点可能故障情况下的一致性达成。

最早由Castro和Liskov在1999年提出的Practical Byzantine Fault Tolerant（PBFT）是第一个得到广泛应用的BFT算法。只要系统有2/3的节点是正常工作的，则可以保证一致性。

PBFT算法包括三个阶段来达成共识：

Pre-Prepare，Prepare 和 Commit。

拜占庭将军问题之所以难解，在于任何时候系统中都可能存在多个提案（作恶成本很低），并且要完成最终的一致性确认过程十分困难，容易受到干扰。但是一旦确认，即最终确认，概率上是100%。

但比特币采用的方案就不是完全按照PBFT来的，比特币的区块链网络采在设计时提出了PoW（Proof of Work）算法思路，计算高难度的hash是为了限制在一段时间内整个网络中出现提案的个数（增加作恶成本），另外一个是放宽对最终一致性确认的需求，是约定好大家都确认并沿着已知最长的链进行延展，系统的最终确认是概率上的确认，不是100%。这样，有人想作恶，会付出很大的经济代价（超过系统一半的算力）。

后来各种PoX的算法，也是沿着这个思路进行改进，采用经济上的惩罚来制约破坏者。

2、算法陈述

角色定义

Paxos一共4个角色：Client , Proposer , Acceptor , Learner。

Client：产生议题者.
Proposer ：提议者/提案者，它可以提出一个提案。一个提案由一个编号及value形成的对组成，如 [m, value]，提案的编号必须是全局唯一，value即代表了提案本身的内容。
Acceptor：决策者, 提案的受理者，有权决定是否它本身是否批准该提案。
Learner：最终决策学习者，也就是执行者。不参与Paxos提案选定的过程，只在提案被选定时，知道提案结果的角色。

Learner最终学习的目标是向所有Acceptor学习，如果有多数派个Acceptor最终接受了某提议，那就得到了最终的结果，算法的目的就达到了。

最基本的Message flow: Basic Paxos演示图如下图所示:

推导过程

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

一个提案被选定需要由半数以上的acceptor批准. 我们为每个提案设定一个编号来记录一个acceptor批准的那些提案。为了避免混淆，需要保证不同的提案具有不同的编号。当一个具有某value值的提案被半数以上的acceptor批准后，我们就认为该value被选定了。此时我们也认为该提案被选定了，提案是由[编号,value]组成。

P2. 如果提案P [m,v]被已选定，那所有编号大于m的提案 P [n,?] (n > m) 的值 ? 必须是v.

因为编号是全序的，条件P2 保证只有一个 Value 值被选定, 保证安全性属性。

过半数学原理

在Paxos算法中，采用了“过半”理念，也就是少数服从多数，这使Paxos算法具有很好的容错性。那么为什么采用过半就可以呢？

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

Paxos是基于消息传递的具有高度容错性的分布式一致性算法。Paxos算法引入了过半的概念，解决了2PC，3PC的太过保守的缺点，且使算法具有了很好的容错性，另外Paxos算法支持分布式节点角色之间的轮换，这极大避免了分布式单点的出现，因此Paxos算法既解决了无限等待问题，也解决了脑裂问题，是目前来说最优秀的分布式一致性算法。其中，Zookeeper的ZAB算法和Raft一致性算法都是基于Paxos的。

一个value被选定需要被半数以上的Acceptor接受。因为一个集合不可能同时存在两个半数以上的子集同时接受两个不同value（两个半数以上子集必然有非空的交集，由于算法限定只接受最大的prepare编号，导致value值在同一时刻是唯一的）。因此算法如果能保证value被半数acceptor接受，则意味这此时被认定的value是唯一的。

Basic Paxos

Basic Paxos 是 Paxos 中最为基础的协议，每一个 Basic Paxos 的协议实例最终都会选择唯一一个结果；使用 Paxos 作为共识算法的分布式系统中，节点都会有三种身份，分别是 Proposer、Acceptor 和 Learner：

paxos-roles

我们在这里会忽略最后一种身份 Learner 简化协议的运行过程，便于读者理解；Paxos 的运行过程分为两个阶段，分别是准备阶段（Prepare）和接受阶段（Accept），当 Proposer 接收到来自客户端的请求时，就会进入如下流程：

算法可以分为两个阶段来执行。

阶段1.

proposer: 选择一个提案编号Mn，向acceptor的多数派发送编号为Mn的prepare请求。

acceptor：如果接收到编号为Mn 的prepare请求，并且Mn大于它已经回应的任何prepare请求，它就返回已经批准的编号最高的提案的value（如果有的话），并承诺不再批准任何编号小于Mn的提案。

阶段2.

proposer ：如果收到了多数acceptor对prepare请求Mn的回应，它就向这些Acceptor发送提案[Mn, Mv]的accept请求，其中Mn是所有prepare请求回应中编号最大的已批准提案的value.

acceptor：如果收到了提案[Mn, Mv]的accept请求，它就批准该提案，除非它已经回应了一个编号大于Mn的提案。

Acceptor需要持久化存储minProposal、acceptedProposal、acceptedValue这3个值。

提出一个提案有三种可能：

(1) 之前的值已经被选中了, 新的Proposer会发现它并使用它

P表示Prepare，A表示Accept

3.1中的3表示 Round Number，1表示由s1提出，X为acceptedValue 可以看到之后的提案了解到X已经被选中，s3、s4、s5也会选中同样的值之前没有值被选中，但已经被接受

(2) 新的Proposer会发现它并使用它

(3) 之前没有值被选中, 后来的Proposer会使用自己的值, 旧的值会被拒绝

paxos算法有着严格的数据公式的证明，但太过于复杂，能以理清，这里我们不在讨论具体的证明过程，只给出paxos算法是如何从众多提案中最终选择一个统一提案的过程。

3、paxos算法优缺点

paxos算法的优点很明显，按照此方法可以对多个数据值达到一致，收敛较好。

paxos 算法的缺点即存在活性问题：考虑到一种极端的情况下，有两个proposer依次提出了一系列编号递增的议案，但是最终paxos无法形成最终的议案。具体场景如下：

没错，在这种情况下，提案只会不断的死循环，提出，被抛弃，再次提出，被抛弃。。。无法保持活性。。。

活锁

当某一proposer提交的proposal被拒绝时，可能是因为acceptor 承诺返回了更大编号的proposal，因此proposer提高编号继续提交。如果2个proposer都发现自己的编号过低转而提出更高编号的proposal，会导致死循环，这种情况也称为活锁。

比如说当此时的 proposer1提案是3, proposer2提案是4, 但acceptor承诺的编号是5，那么此时proposer1,proposer2 都将提高编号假设分别为6,7，并试图与accceptor连接，假设7被接受了，那么提案5和提案6就要重新编号提交，从而不断死循环。

解决办法：

a. Proposer失败之后给一个随机的等待时间，这样就减少同时请求的可能。
b. 选出一个主proposer，作为提案的唯一人选。如果主proposer能和大数派的集合进行通信，并且使用了一个比所有已经批准的提案号都大的编号，那么它就能成功产生被接受的proposal。批准拒绝已有的提案并且批准更高的提案号，主proposer最终会选择到一个足够大的提案号，最终使用提案被选定，从而达到数据一致性的目的。通过选择一个主Proposer，并规定只能由主Proposer才能提出议案，整个paxos算法就可以保持活性。

4.总结

分布式系统中面对的最重要问题，就是分布式一致性. 当整个网络需要实现拜占庭容错时，仅靠算法确实是比较难以实现的，往往都需要使用其他方面的激励或者惩罚，让诚实表现的节点利益最大化才是解决一致性的最佳方案；从工作量证明、权益证明再到委托权益证明，共识算法的不同导致性能也有着非常大的差异，我们可以看到随着网络中进行『投票』的节点越少，网络的处理能力就会越强和性能就会越快，委托权益证明选举了 N 个节点来保证性能和去中心化程度确实是一件非常聪明的事情。