哪个大牛能用1０－2０句话讲讲paxos？ - 未名空间MITBBS历史存档

哪个大牛能用1０－2０句话讲讲paxos？# Programming - 葵花宝典

t*r2015-07-12 07:07

1 楼

哪个大牛能用1０－2０句话讲讲paxos？在说说和raft的比较。
面試问这个問題没有人能回答的很好

r*s2015-07-12 07:07

2 楼

衰人连说两句。 Paxos 的话Wiki 里讲的比较浅显
如果嫌细节不够可以看Lamport后续的 Paxos Made Simple。
Raft 在 consensus protocol上和Paxos 没有区别，只不过描述了一个fault
detection 算法， Lamport在文中已经证明过不管使用神马Fault Detection算法都不
影响协议正确性。而且那算法还不是他们头一个提出的
Zab也是一样的Paxos，在Multi-Decree leader changes 的时候略有修改。其实他们
的修改也不是头一个提出的。微软研究院几年前有两篇 PacificA 和 Niobe就是一样的
东西，无非保证顺序而已，

z*32015-07-12 07:07

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到底是什么？
你看了他说的概念，你还是不懂，虽然他好像写了很多
但其实都是概念，没半毛钱意义，不信你挨个查他蹦的概念

c*e2015-07-12 07:07

4 楼

服了你，空的发慌写这么多
我记得似乎就是 majority consensus..

【在 z*******3 的大作中提到】

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

t*r2015-07-12 07:07

5 楼

raft感觉和浅显
python写个简单的不带transport layer也就1０００行

z*32015-07-12 07:07

6 楼

也是，paxos其实没啥东西

【在 c*****e 的大作中提到】

: 服了你，空的发慌写这么多
: 我记得似乎就是 majority consensus..

h*r2015-07-12 07:07

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 的大作中提到】

: 哪个大牛能用1０－2０句话讲讲paxos？在说说和raft的比较。
: 面試问这个問題没有人能回答的很好