Redian新闻
>
哪个大牛能用10-20句话讲讲paxos?
avatar
哪个大牛能用10-20句话讲讲paxos?# Programming - 葵花宝典
t*r
1
哪个大牛能用10-20句话讲讲paxos?在说说和raft的比较。
面試问这个問題没有人能回答的很好
avatar
r*s
2
衰人连说两句。 Paxos 的话Wiki 里讲的比较浅显
如果嫌细节不够可以看Lamport后续的 Paxos Made Simple。
Raft 在 consensus protocol上和Paxos 没有区别, 只不过描述了一个fault
detection 算法, Lamport在文中已经证明过不管使用神马Fault Detection算法都不
影响协议正确性。而且那算法还不是他们头一个提出的
Zab也是一样的Paxos,在Multi-Decree leader changes 的时候略有修改。 其实他们
的修改也不是头一个提出的。微软研究院几年前有两篇 PacificA 和 Niobe就是一样的
东西, 无非保证顺序而已,
avatar
z*3
3
paxos和raft都是关于consensus的论文
其本质都是为了解决一个consensus的问题
分布式和单机最大的区别就在乎
分布式是由一堆nodes组成的网络,而单机很容易
就是一台破机器而已,所以单机不存在一个consensus的问题
而分布式的nodes众多,这么多个nodes互相之间肯定有分歧
如果摆平分歧,这就是consensus的过程
所有nodes提proposal,只要proposal#之间的先后顺序确定
就没有问题,用leader就是一种方式,那就是要vote,但是如果vote数量持平呢?
比如4个nodes,两个选a,另外两个选b呢?
然后paxos的垃圾之处就在于,它假设了这个global proposal#的顺序问题已经得到了
解决
就是假设数量持平的话,a和b在某种机制下会分出胜负来,而具体这个机制是什么
“不在本文讨论范围之内”,然后还很神秘地解释了,“有很多种方式可以搞定”
wtf?对,这也是我的想法,麻痹的这个如果得到了解决,还需要你说个p啊?
对,这就是paxos通篇废话的主因,因为最关键的问题,被它假设掉了
而且很搞笑的是,蓝胖子自己在他几十年前的早期论文中,已经证明了
global clock是不存在的,就是不能依赖某一个clock来排序,不安全也影响公平性
而因为每个nodes的时序是不一样的,所以很难产生一个所有nodes都能接受的顺序
因为当选举发起的时候,有些node先收到a的proposal,而有些node先收到b的proposal
而最后恰恰是一半的nodes认为a先发起,而另外一半认为是b先发起,这不就僵持了嘛?
那么如何识别顺序就是一个非常麻烦的问题
你可以自己想想怎么搞,没那么容易想出来,因为如果你能想出来,这事就搞定了
就是因为丫不懂,所以没办法实现
raft就解决了这个问题,用一种比较实际可行的方式搞定
在此之前说一个最本能的想法,对于proposal#
你可以通过一个顺序来排序所有的nodes
这个也是上课时候,老师问如何做,下面学生绝大多数都能想出的办法
缺点也显而易见,因为这种ordering显然不能保证公平性
就是所有的nodes并不是公平的,但是这个却非常显而易见
可以很快解决冲突,并得出一个结果来,军队就是这种方式
一旦两个人冲突了,下级无条件服从上级,上级挂了,提拔一个下级上来填坑
tree结构可以比较快速地完成这个提拔,所以在讲究效率的地方
比如内存,这种机制用得比较多,但是分布式不能这么搞
因为分布式是左逼,预设前提就是,所有的nodes都无差别
这样便于插入以及拔除nodes,而不影响整个系统的运作
而对于有明显权重的系统来说,权重高的nodes如果挂了,影响会很大
所以如何保证公平性的前提下,又最大化效率呢?
然后说说raft的做法,raft的做法是先elect出一个leader来,然后所有nodes听leader的
以leader node为准,那很快就会带来一个新的问题,leader挂了怎么办?
那就要reelect,重选leader,那么选举会带来另外一个新的问题
如果四个nodes,2:2怎么办?如果过半数,3:1,就没有问题,但是如果是2:2呢?
raft引入了一个非常重要的机制,那就是通过(伪)随机数,没有真随机数,这个应该都懂
这个随机数放在一个范围内
比如300s-500s之内,count down,这个数字范围可以根据分布式大小而调整
如果在时限内,无法收集到足够多的votes,本次选举流产
再选,那么因为两个争leader的nodes产生的随机数不太可能一致
比如两个争leader的nodes分别是a和b
a的随机数是450s,而b的随机数是300s,那么b会抢先发起第二次election
在a count down完成之前收集到足够多的votes,然后广播出去,当上leader
如果不幸a和b的随机数都是300s,那么还是会同时发起election
然后再次流产,然后再次产生随机数,如此反复下去,总有一次,这个election会成功
用这种方式使得整个机制可以运作,而随机数的产生本身就是uniformly distributed
这就保证了公平性,所有nodes的权重是一致的
最后再批判一下蓝胖,蓝胖的论文废话连篇,通篇概念,故弄玄虚
很容易在开头就看晕过去,需要你从他很早以前的ordering的论文开始看
但是相信我,你看到最后,你会认同我的
而且你看到这里面的trick了没有?
因为蓝胖把其他废话都说了,唯独最关键的部分被他忽略了
所以他可以说,你无论什么方式,都是paxos,wtf?
哲学上说,任何关于事物本源的思考都是哲学,有异曲同工之妙
所以你也就可以理解为什么那片论文写得如此含混晦涩的主因了
你要是轻易看懂了,那不就知道他在灌水了么?那他在微软研究院还怎么骗?
paxos其实就三个字就结束了,就是:要选举,over
其他只要用了选举,那就是paxos,神逻辑
学术圈里面灌水的见多了,但是灌水能灌到图灵奖的,呵呵
不过反正同性恋奖嘛,也不用那么严肃了,炸药奖也没少编数据的
就费儿子奖还好,其他都不太行,因为数学比较难骗,其他专业都可以编一编
反正你也不知道他到底在干嘛,这就是皇帝的新衣
你看沙发是不是不停滴给你在扯各种概念?
根本没有跟你解释哪怕半点paxos到底是什么?
你看了他说的概念,你还是不懂,虽然他好像写了很多
但其实都是概念,没半毛钱意义,不信你挨个查他蹦的概念
avatar
c*e
4
服了你,空的发慌写这么多
我记得似乎就是 majority consensus..

【在 z*******3 的大作中提到】
: paxos和raft都是关于consensus的论文
: 其本质都是为了解决一个consensus的问题
: 分布式和单机最大的区别就在乎
: 分布式是由一堆nodes组成的网络,而单机很容易
: 就是一台破机器而已,所以单机不存在一个consensus的问题
: 而分布式的nodes众多,这么多个nodes互相之间肯定有分歧
: 如果摆平分歧,这就是consensus的过程
: 所有nodes提proposal,只要proposal#之间的先后顺序确定
: 就没有问题,用leader就是一种方式,那就是要vote,但是如果vote数量持平呢?
: 比如4个nodes,两个选a,另外两个选b呢?

avatar
t*r
5
raft感觉和浅显
python写个简单的不带transport layer也就1000行
avatar
z*3
6

也是,paxos其实没啥东西

【在 c*****e 的大作中提到】
: 服了你,空的发慌写这么多
: 我记得似乎就是 majority consensus..

avatar
h*r
7
raft has very limited use case, after all it was just a student's work. not
something can save the cluster chaos.
It won't be effective with more than 9 members quorum. It won't work well if
the cluster is geographically distributed.
in a word, it won't work with large cluster well.

【在 t**r 的大作中提到】
: 哪个大牛能用10-20句话讲讲paxos?在说说和raft的比较。
: 面試问这个問題没有人能回答的很好

相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。