Paxos共识算法
李素晴 781 0

就算你没了解过分布式,但也应该知道强一致是个很难的东西吧,上一节讲的WARO和Quorum是做到了写入读取的强一致性,并不是那个很难的数据强一致,后面会讲到这点。

科学家们试图寻求更好的算法,Paxos是其中之一,专业讲解可以看Paxos Made Simple,这里就通俗点讲了,理解这个算法的精髓在于不要多想。

三军问题

考虑下面的场景。

蓝军的三个军团包围了红军基地,两个及以上的蓝军军团同时进攻才能获取胜利。

通信方式只能依靠通信兵去其他军团驻地,送达或带回消息。通信兵有可能战死在路上,或者被红军俘虏,总之是不能保证消息是一定带到的。

保证军团中不存在内鬼、叛徒之类的,即保证消息是准确的。

每个蓝军军团有1个将军,1个参谋,参谋负责指定作战计划,将军负责批准作战计划。

那么如果蓝军想要胜利,就需要至少两个将军批准某个军团参谋的作战计划。

问是否有一种办法能够使得蓝军取得胜利?

解决办法

如果按WARO的思路来讲,一方蓝军军团派出两名通信兵去到其他两个军团,如果有一名通信兵带回了批准计划的消息,那么即可获取胜利。

在这个过程中,如果其他军团的通信兵带来了作战计划,则统统不能批准,很不巧的是,其他两个军团也是这么想的。

可以理解到,读写强一致,和数据强一致的区别了吧。

那该怎么办呢?

让通信兵带的消息,加上一个字段,可以理解为版本,这个版本号是全局递增的,至于怎么全局递增先不要去考虑。

把自己想作其中一个蓝军1军团,理所当然的,一开始我们什么都不知道,所以先试探一下其他两方军团是否正常。

于是派出小兵12,小兵13,分别前往两个军团,此时他们只带一个消息版本号1。

在小兵12和小兵13没回来的这段时间,来了2军团的小兵21,带着版本号2,询问我方是否可以协同发起进攻,我军将军答应了。

可能小兵12和小兵13腿脚慢,又或者战死了,反正就是一直没回来,而此时3军团的小兵31来了,带着版本号3,询问我方是否可以协同发起进攻,我军将军答应了。

小兵12和13还是没回来,这时候小兵21又来了,带着消息版本2和进攻时间t2,要求我军在t2时刻发起进攻,因为之前答应了3军团,拒绝了2军团的请求,并让小兵21带回去了小兵31的版本号3。

小兵12回来了,告诉我方2军团愿意与我方协同作战,参谋制定了进攻时间为t1的计划,首先当然是要我方将军批准,如果上面你理解了,将军是不会批的,因为之前将军答应了版本号为3的商议协同进攻的请求。

于是参谋改了计划,版本号为4,进攻时间还是t1,交给将军,将军批准了。小兵12带着作战计划前往了2军团。

这时候小兵31又来了,带着版本号3和作战时间t3,请求我方将军批准,相信你已经可以替将军做出决策了,当然是不批准,并回复一个版本号4和作战时间t1。

这个时候小兵12回来了,告诉我方2军团愿意在t1时间发起进攻,于是在t1时刻,我军和2军发起了进攻,蓝军胜利了。

这里可能有人回想,2军团怎么确定小兵12一定回的来?答案是不需要确定,既然选择答应了,就一定会在t1进攻。

知道你看到这里一定还是有很多疑问,我写文章的时候,也是想到哪写到哪,这个情景并不是涵盖了所有的情况,也没把会产生活锁的情况写出来。

但对于paxos算法大概是什么,我想看到这的你应该已经理解了。

评论区

索引目录