您现在的位置:首页 > >

分布式算法 -

发布时间:

?


序言

本章意在讲解,基本的分布式算法,Basic Paxos 的原理, 以及其解决的问题


?


?


正文

?


所谓的Paxos 算法,是兰伯特先生在1990 年提出的一个共识算法,何谓共识? 即指多个节点之间对某个值能达成统一的共识。 而 Paxos 算法,分为 Basic Paxos 和 Mutliple Paxos ,Multiple Paxos 算是一种思想,在兰伯特的论文里面并没有提及其内部实现,而基于此种思想,衍生出一些 分布式一致性算法,其中raft算法,是其中经过验证的一致性算法,很多开源的分布式组件,为了实现其一致性都采用了此种算法来实现。


?


Paxos 算法为了解决什么问题,这里先提 multiple paxos 为了解决什么问题?


总而言之是,为了解决多个节点下的数据一致性问题,说得这么简洁又不知道是什么意思了。


?


画个图


?



?


假如我们有三台服务器,server1 ,server2,server3, 三台服务器都能接受客户端写请求,这时候,同一时刻来了三个请求,分别还是不同的内容,那么因为我们知道服务端为了同步数据都会把客户端命令已 日志log方式存储到本地,而且为了 分区容错性(P),我们需要三台服务器的log都是一致的,对于每台服务器的log 日志都有序并且一致的,那么这样的好处是,如果有一台新的new server 加进来,我们可以让它同步log 日志,恢复整体的数据状态,从而加入这个服务集群。所以如何让三台服务器的日志 一致,这就是我们要解决的同一时刻,协调并发请求的一个value问题。这时候 paxos 算法就是通过协商 三个请求的命令,从中选出一个执行命令,并且三台服务器都能认可写进自己的log日志里面,那么这个协调就算完成,得到了一致性的结果了。从而后续的一系列命令都能以相同的方式,协商出一个共同的认可的命令,写进不同机器的日志,达到日志一致的效果。


看起来倒是不难,但其中因为网络分区和时延的不可信,解决这个问题会有想不到的细节要考虑。


题外话,如果是只有一台服务器,那还需要协调吗?? 比如只有一个服务器 server1 ,那就不用协调了,命令即使是并发过来的,都能在同一个server1 里面进行队列排队,压根不用进行复杂的算法协商。主从一个道理,因为从服务器不负责写操作,只会把写操作转发到主服务器,所以写操作还是在一台服务器上面。那么这样带来的结果就是 整体系统的脆弱性,我们知道单点总是没有多点稳健, 而且即使是你单点 加上 setinal (哨兵)方式来控制整体服务的可用性,假如主节点挂了,sentinal 进行 从节点选举的时候,还是有小部分时间的服务不可用,而且这个failover过程,选举出一个主节点,其实也是多台从节点协商选出一个固定的值的过程,也是一个分布式一致性算法的过程。 从而我们看到,现在的网络环境,讲究的是分区容错,也就是P,? 这个分布式协商算法(为了多节点能协商出一个值)用到的场景可以说是非常多的,这也就是这个Paxos 及其变种算法要解决的 协商问题。


?


?


?


Basic Paxos 算法为了解决什么问题?


?


上面讲完 mutiple paxos 算法解决问题,细化到细处,那就是这个Basic Paxos 算法解决的问题,还是这个图



?


它是为了解决某一个时刻,到达不同节点的不同数据,但是我们要协商出一个一致的值,从而让所有节点都接受这个值的这个算法。


Basic Paxos用来在多个节点间确定并只确定一个不可变变量的取值。(一旦确定后就不可以更改),这一点值得注意,Basic Paxos只能就单值达成共识,属于一个基础算法,Multi-Paxos,才能在实际场景中落地。


?


?


细节实现


魔鬼在细节,我们来详细讲讲,它这个多节点在并发情况下,确定出一个不可变变量是个怎样的过程。?


?


假设我们现在有一个集群,其中有五个节点


?



?


然后5个节点都可接受读写请求, 这时候有客户端要连入这些节点了,? 然后客户端想设置一个 值 SET X ,? ?假设 客户端 1 连入了 A 节点, 发出命令 SET X = 1,? 客户端2 连入了 B节点, 发出命令? SET X = 2, 那么我们来看看会发生什么过程。


由于目前 X 不存在,所以第一个能设置 X的值的节点,设置完成以后,X 的值就不会变了。


?


一般来说,接受 客户端请求的那个节点 叫为 proposer, 也就是提议者。然后投票的各个节点叫 acceptor(接受者,可以进行投票),一般分布式系统还有个角色叫做 learner(学*者)来学*投票结果,并不参与投票。


现在情况也就是如下图



?


为了演示结果清晰,就不直接连线了,可以知道的是 A 节点想把 这个 SET X = 1 这个提议发给其他节点, B同样,同时只有当结果得到大多数节点肯定时候,这个提议才能通过。看看其流程。


?


我们可以思考的是,肯定不能直接发 命令发给各个节点,因为这样的话, B节点的命令也是并发同时发过来的,这样把最终结果写入各自日志的时候,达不到同识的效果。于是这里采用的策略是,分布式系统常用的二阶提交策略,


第一阶段进行 proposal (提议)提出,然后得到大部分数量的同意后,然后第二阶段 进行 proposal 执行, 大多数节点都同意执行后,该proposal 正式成立执行。


?


二阶提交的细节


    ?由于需要辨别命令到达的先后顺序,所以在分布式系统共识算法中,递增编号是一个常见的思路,也就是proposal 的提出,都具有编号的特性,这样我们能知道,谁先谁后,而且这个编号需要递增A 提出一个提议, SET X =1 ,首先提出提议阶段,不需要 带上值 ,带上一个编号即可,因为提议阶段,是编号值大的提议就能被接受,所以不需要带上值,A 提出? ?【1, 】 然后分别发送给其余各个节点

B, C,D,E,? 然后先考虑简单情况,就是 B节点的命令还没发送给任何节点, C, D,E因为现在还没接受任何提议,它们目前保留的提议编号为空(这个提议编号就是接受到提议的最大编号),C,D,E 发送 ack给 A节点


表示 这个proposal 通过了,可以进入第二步执行阶段了, 按照多数原则,其实只要 C,D节点通过就可以,Math.ceil(5/2) =3, A本身算是一个节点,自己提出的proposal ,自己当然是同意的。?


? ?3.? 往下走,这时候A 如果接受到 第一阶段的ack以后,直接发送第二阶段的执行命令 【1,1】 注意第二个1是指要设置的值, SET X =1 ,这个值, 简单的情况是,发这个命令发送给 B,C,D,E 几个节点,可以看到,C,D,E中


三个节点,之前它们记录的最大proposal值为1, 此时命令是【1,1】 提议编号,不比它们记录的最大编号要小,那么通过,发送ack 给A节点,只要有两个 节点,发送给A节点,那么其实这个提议已经通过了,X的值为1,不可改。


?


上述是最简单的情况,下面我们来阐述其他情况,然后后面我们再总结Basic Paxos 规则


?


? 假如第一阶段, C,D,E 发送 给A ack以后, B节点同时发送第一阶段的proposal 也就是【2,】 ,这时候C,D,E 发送自己的最大提议值 为1,那么这个时候,C,D,E节点会发送给B节点ack ,表示同意。


然后A节点这时候,发送命令过来【1,1】 ,C,D,E节点收到后,那么由于它们本身记录的最大提议值这时候为 2了,那么这个命令直接被抛弃, 等待 B节点继续发第二阶段命令 【2,2】 发送给其余节点,其余节点接受,此时候,那么X的值被通过的为2,不可改变。


?


这里常说的X 设定完后不可改变又是啥意思呢,这里其实是Basic Paxos算法的一个限制, 看下面一种情况,举例说明


A 在第一阶段收到 ack 以后, 紧接着在第二阶段 发送【1,1】 然后C,D,E收到命令,执行了 SET X =1 这个命令了,那么此时这个X的值已经确定了。此时 B节点的提议过来【2,】,由于此时最大提议值为1,C,D,E还是要接受这个提议,因为2比1大,但是此时已经确定了X的值了,所以


那么此时,其他节点C,D,E 会把已经通过的值【1,1】 发送给B节点,告诉它,你来的太晚了。没办法了。


这时候B 想改 X的值已经做不到了,此时B的行为是(这个行为其实是Basic Paxos规定提议者必须要做的行为),就是改变自己的命令,把自己想设置的值 之前是2,现在改为1, 然后第一阶段的提议阶段在B这边已经通过了,第二阶段的执行阶段,B节点把命令改为 【2,1】,


然后发送给各个节点,各个节点接受命令, 大部分节点通过后,这个命令执行成功,但是X的值依旧为1.


?


?


总结下 这个 Basic Paxos的规则


? ? ? ?0. 提议者不管在第一阶段,还是第二阶段,收到大部分的同意选票后,就算成功


    提议者 发送给各个接受者,接受者接受比自己目前记录的最大提议值大的提议,大多数节点同意后,发送给提议者,第一阶段提议结束第二阶段,发送的提议,如果接受者当前记录的最大提议编号比当前发送的提议要大,直接抛弃这个执行提议??第一阶段,发送给接受者节点,根据响应中提案编号最大的提案的值,来设置接受请求中的值,如果当前没有接受者发过来的值,就设置自己的值。 如果接受者节点有值,根据该规则,提议者把自己的值改掉,然后执行第二阶段流程。

?


通过上面几条规则,就可以确立起 Basic Paxos算法的规则了,就能实现多节点下某个值的共识,这里没有提及的是learner 角色,learner 由于不能投票,它的行为是


如果集群中有学*者,当接受者通过了一个提案时,就通知给所有的学*者。当学*者发现大多数的接受者都通过了某个提案,那么它也通过该提案,接受该提案的值。


这里值得注意的是,其实节点内可能有多个进程,同时肩负多个角色。例如 proposor 和 accecptor 。


?


?


结尾

?Basic Paxos 算法是 分布式共识算法的基础,它的一些思想渗透进,其他 mutlip paxos算法的方方面面,虽然Basic Paxos算法没有什么落地价值,但是基于它的 Mutliple paxos算法具有很强的价值,Mutiple Paxos并不是一种特定的算法,它是一种思想,


基于这个思想来实现的共识算法,有较多。


?


Q&A 环节:


基于 大多数 节点同意就算通过,那么其他还没投票的节点怎么同步 X 的值?


这个同步节点的值,可以通过较多的方法,这个后面会讲,主要通过 反熵,和gossipe 来实现其他节点的值的覆盖,而且一般来说, 提议者都是广播发送给各个节点的。就算是还没同步到某个节点,也可以通过配置?Quorum NWR 算法来实现,读写一致性,这个算法


的核心在于,例如读取值的时候, 可以配置成多个节点的值(返回节点值中提议编号最大的那个值,空的值就算没有编号)来获取到最新的值。


?


?


?


?


?


?


热文推荐
猜你喜欢
友情链接: 医学资料大全 农林牧渔 幼儿教育心得 小学教育 中学 高中 职业教育 成人教育 大学资料 求职职场 职场文档 总结汇报