诸葛亮 VS 庞统,拿下分布式 Paxos
共 3715字,需浏览 8分钟
·
2021-02-10 21:56
前言
分布式确实是一个有趣的话题,只要你留心观察,分布式在生活中无处不在。
前两讲主要是讲解分布式理论,涉及到了分布式的四大理论。详见如下文章:
拜占庭将军问题:用三国杀讲分布式算法,舒适了吧?
BASE、CAP、ACID:用太极拳讲分布式理论,真舒服!
从这篇开始,将会讲解分布式的八大协议/算法。本篇主要讲解 Paxos 共识算法。
本文主要内容如下:
![](https://filescdn.proginn.com/23bc165a44a2166962a4f80b23e4e16b/f708bbaa56f772560b7b0d19dec78572.webp)
Paxos 算法
Paxos
是分布式算法中的老大哥,可以说 Paxos 是分布式共识的代名词。最常用的分布式共识算法都是基于它改进。比如 Raft 算法(后面也会介绍)。所以学习分布式算法必须先学习 Paxos 算法。
Paxos 算法主要包含两个部分:
Basic Paxos 算法:多个节点之间如何就某个值达成共识。(这个值我们称作 提案 Value
)Multi-Paxos 算法:执行多个 Basic Paxos 实例,就一系列值达成共识。
Basic Paxos 算法是 Multi-Paxos 思想的核心,Multi 的意思就是多次,也就是说多执行几次 Basic Paxos 算法。所以 Basic Paxos 算法是重中之重。
三国中的 Paxos
三国中刘备集团,有两大军师:诸葛亮和庞统,都是非常厉害的人物,当他们有不同作战计划给多名武将时,如何达成一致?
角色
Paxos 中有三种角色:提议者、接受者、学习者。
让我们用更通俗的方式来讲解 Paxos 算法。让我们穿越回东汉末年,刘备集团的帐营中一同学习 Paxos 算法是怎么攻打曹操的。
刘备的帐营中人物介绍:
主公一名:
刘备
,作为请求方或客户端
。军师两名:
诸葛亮
、庞统
,作为提议者
。武将三名:
关羽
、张飞
、赵云
,作为接受者
。文臣两名:
法正
、马良
,作为学习者
。
![](https://filescdn.proginn.com/1a02252fc877bc47dcddb4c2662df1dc/72f195ac3ac20e60736f1dc169cdb2b3.webp)
提议者(Proposer)
提议一个值,用于投票表决。 接入和协调,收到客户端的请求后,可以发起二阶段提交,进行共识协商。 映射
到上面的故事中,军师
就是用来部署作战计划的。
接受者(Acceptor)
对每个提议的值进行投票,并存储接受的值。
投票协商和存储数据,对提议的值进行投票,并接受达成共识的值,存储保存。
映射
到上面的故事中,武将
就是用来接受军师的作战计划。其实,集群中所有的节点都在扮演接受者的角色,参与共识协商,并接受和存储数据。
学习者(Learner)
被告知投票的结果,接受达成共识的值,存储数据,
不参与投票的过程,即不参与共识协商。
映射
到上面的故事中,就是两名文臣
作为记录作战方案的备胎
。
接受者 or 提议者
为什么说节点可以扮演接受者,也可以扮演提议者呢?
上篇我在讲解 BASE 协议的时候,讲到二阶段
提交协议。其中有一个协调者的身份,协调者既可以是接受者,也可以是提议者。
作为接受者,接收客户端的消息。比如 诸葛亮
需要接收刘备
的作战要求。作为提议者,发起二阶段提交。然后这个节点和另外其他节点作为接受者进行共识协商。比如 诸葛亮
要汇总最终的作战计划给刘备
。
如下图所示,节点 1 作为提议者和接受者,节点 2 和节点 3 作为接受者。
![](https://filescdn.proginn.com/128923b55fb9812689b71bedd1620598/80262a99787f89ad07958b7eb00726a6.webp)
诸葛亮 VS 庞统
三国中有刘备集团(占据西蜀)、曹操集团(占据北边)、孙权集团(占据江南)。
诸葛亮
和庞统
作为提议者,向三个接受者进作战计划的提案。提案中有两个属性:
提案编号
,每次军师进行提案,都会有个编号,这里用 n 表示。提议值
,也就是作战计划,这里用 v 表示。所以提案就是 [n, v]。
诸葛亮
的作战计划是从北边
进攻曹操,庞统
的作战计划是从南边
进攻曹操,而关羽、张飞、赵云先后收到了他们的作战计划,该听谁的呢?这里就是一个共识
的问题。而 Paxos 算法达成共识分两个阶段。准备(Prepare)阶段
和接受(Accept)阶段
。
准备阶段
诸葛亮和庞统作为提议者,分别向所有的接受者(关羽、张飞、赵云)发送包含作战计划编号(提案编号)的准备请求
,但不包含作战计划(提案值)。
发送准备请求
提议者
诸葛亮
先发送编号为1
的作战计划的准备请求,庞统
发送编号为2
的作战计划的准备请求。接受者
关羽
(节点 X)在8 点
收到来自诸葛亮发送的作战计划准备请求,在10 点
收到来自庞统发送的作战计划准备请求。接受者
张飞
(节点 Y)在9 点
收到来自诸葛亮发送的作战计划准备请求,在11 点
收到来自庞统发送的作战计划准备请求。接受者
赵云
(节点 Z)在12 点
收到来自庞统发送的作战计划准备请求,在13 点
收到来自诸葛亮发送的作战计划准备请求。
![](https://filescdn.proginn.com/f739a02faf7aab41cbe8eb6b4e2ea2dd/6ae81ccc0d5defbdf58e81a1ef92cea6.webp)
注意:准备阶段不需要携带具体的作战计划,所以作战计划可以为空,但是提议编号必须有。
收到准备请求(第一次)
按照接受请求的时间顺序,关羽和张飞收到诸葛亮的请求[1,空]
,赵云收到庞统的请求[2,空]
。
![](https://filescdn.proginn.com/30bb1ce7b926de0c1a83c47d7577c4a1/959b8785b066e052b30cb68b081e65e2.webp)
因为关羽、张飞之前没有收到提案,所以返回一个尚无提案
的响应。也就是告诉诸葛亮,不会再响应编号小于等于 1
的准备请求了,也不会通过编号小于 1
的提案。响应的时间点是 14 点和 15 点。
而赵云之前也没有收到提案,所以返回一个尚无提案
的响应。也就是告诉庞统,不会再响应编号小于等于 2
的准备请求了,也不会通过编号小于 2
的提案。响应的时间点是 16 点。
收到准备请求(第二次)
![](https://filescdn.proginn.com/dc7679f911323661ccde7e2e3156f961/10c9be07f7d0cdaa8f74dedd7bddb2d3.webp)
而对于庞统的准备请求,关羽、张飞收到编号为 2
的准备请求,而 编号 2
大于之前接受到的编号 1
,而且关羽和张飞没有通过任何提案,所以还是会返回给庞统一个尚无提案
的响应。也就是告诉庞统不会再响应编号小于等于 2
的准备请求了,也不会通过编号小于 2
的提案。响应的时间点是 14 点和 15 点。
而赵云最后收到诸葛亮编号为 1
的准备请求
后,因编号 1
小于之前响应的准备请求的提案编号 2
,所以直接丢弃该准备请求,不做响应,如上图的 ❌ 图示。
接受阶段
发送接受请求
诸葛亮和庞统收到准备响应后,会分别发送接受请求,如下图所示:
![](https://filescdn.proginn.com/1dde82dd6370a1307e11032fcb9525f2/2bd42c9b0ad87c5fcd6acbcc729b9afa.webp)
诸葛亮
收到大多数接受者(关羽和张飞)的准备响应
后,根据响应中提案编号最大的提案的值,设置接受请求
中的值。因为关羽和张飞返回的准备响应都是尚无提案,所以还是发送提案编号为 1
,提案值为北
的接受请求
,北
代表从北边进攻曹操。发送的时间点是 15 点过 1 分、16 点。
为什么是 15 点过 1 分? 因为只要满足大多数接受者的准备请求后,就可以发送接受请求
了。关羽和张飞响应的时间点是 14 点和 15 点,所以 15 点以后就可以发送了。
而庞统
收到大多数接受者(关羽、张飞和赵云)的准备响应
后,根据响应中提案编号最大的提案的值,,设置接受请求
中的值。因为关羽、张飞和赵云返回的准备响应都是尚无提案,所以还是发送提案编号为 2
,提案值为南
的接受请求
,南
代表从南边进攻曹操。发送的时间点是 18 点、19 点、20 点。
收到接受请求
当关羽、张飞、赵云收到诸葛亮和庞统的接受请求
后,会进行如下处理,如下图所示:
![](https://filescdn.proginn.com/5e17e39e8e10267eb9a6fab1fd966f93/1bd512bcd5487abc66f74843f054d24f.webp)
关羽、张飞、赵云收到诸葛亮发送的提案 [1,北]时候,因为提案编号 1
小于他们承诺的能通过的提案的最小提案编号 2
,所以诸葛亮的提案被拒绝了。
而当他们收到庞统的发送的提案 [2,南] 的时候,因为编号 2 不小于之前承诺的编号 2,所以通过庞统的提案 [2,南] ,所以关羽、张飞、赵云他们的作战计划是从南边进攻曹操。达成了共识。
学习者登场
当接受者通过了一个提案时,就通知所有的学习者。当学习者发现大多数的接受者都通过了某个提案,那么学习者也会通过该提案,接受该提案的值。
也就是说关羽、张飞、赵云达成了共识后,学习者法正
和马良
也同样通过从南边进攻的作战计划。
总结
Basic Paxos 也是通过二阶段提交协议达成共识。准备阶段、接受阶段。不知道二阶段提交协议的,可以看我前面的文章。《用太极拳讲分布式理论,舒服!》
Basic Paxos 不仅仅实现了共识,还实现了容错。有少于一半的节点出现故障时,集群也能正常工作。文中也多次强调了大多数节点都同意的原则,而这个原则赋予了 Basic Paxos 容错的能力。
提案编号代表优先级,保证了三个承诺:
如果 准备请求
的提案编号,小于等于
接受者已经响应的准备请求
的提案编号,那么接受者将承诺不响应这个准备请求
。如果 接受请求
中的提案的提案编号,小于
接受者已经响应的准备请求
的提案,那么接受者将承诺不通过这个提案。如果接受者之前有通过提案,那么接受者将承诺,会在 准备请求
的响应中,包含已经通过的最大编号的提案信息。
加分题
如果关羽和张飞已经通过了提案 [2,南]
,而赵云还未通过任何提案,当第三名军师简雍
提出一个提案,编号为 8,作战计划为从东边进攻曹操,也就是 [8, 东]
的作战计划,那么最终关羽、张飞、赵云的作战计划是怎么样的?