超越不可能

相信所有研究过分布式系统的同学都对大名鼎鼎的FLP不可能性有所耳闻,简单来说,FLP不可能性证明了“在可能有哪怕一个进程故障的异步系统模型中,共识问题无法被解决”。但矛盾的是,现在正当红的很多分布式系统,都依赖于底层的共识算法,比如Multi-Paxos、Raft等,难道是FLP错了么?共识问题已经被解决了?还是说我们用的分布式系统都是有问题的?

想要理解这个问题,其实是要搞清楚一件事情:FLP不可能性真正意味着什么?

注:如无特殊说明,本文中的进程故障模型均为crash-stop,通信链路模型为perfect link。

继续阅读:

Paxos revisit

前一段时间借着组里的实习生学习交流的机会,又重新讨论了一次Paxos算法,颇有收获。本文整理记录几个我个人觉得比较有意义的问题,希望通过思考这几个问题,能够加深你对Paxos算法的理解。

本文假定读者已经对Paxos算法有一定了解(包括原理、正确性证明、执行流程),如果你还不了解Paxos,请移步这里

Paxos算法流程


在思考问题之前,首先重温一下Paxos算法的流程,同时统一变量名称,方便后文讨论。

Prepare阶段:

  1. Proposer选择proposal number n,并向acceptors发送Prepare(n)消息
  2. Acceptor收到Prepare(n):if n > minProposal then minProposal = n; return (acceptedProposal, acceptedValue)

Accept阶段:

  1. 如果Proposer收到了超过多数派acceptors对于Prepare(n)的回复,如果回复中有包含acceptedValue,则选择acceptedProposal值最大的作为value,否则Proposer可以自行选择value
  2. Proposer向所有acceptors发出Accept(n, value)消息
  3. Acceptor收到Accept(n, value):if n >= minProposal then acceptedProposal = n; acceptedValue = value,并回复AcceptAck(n)
  4. Proposer收到来自多数派acceptors的AcceptAck消息,value已达成决议(chosen)

问题


在上述Paxos算法流程的基础上,仔细思考下面几个问题:

  1. 为了保证算法在容灾(节点故障重启)场景下的正确性,Acceptor上需要持久化哪些信息?
  2. 如果Acceptor不持久化acceptedProposal,在Prepare阶段的第2步中minProposal代替,有没有问题?

  3. Accept阶段,Proposer不用n覆盖acceptedProposal,仍将其发送给Acceptor,Acceptor收到Accept(n, acceptedProposal, value)之后使用消息中的acceptedProposal而不是n来作为acceptedProposal,有没有问题?

  4. 在5个节点的情况下,如果修改流程为Proposer要收到4个acceptor对Prepare(n)的回应才可以发送Accept消息,要收到2个acceptor对Accept(n, value)的回应才能确认决议,有没有问题?

  5. 论文中提到Proposer选择proposal number要递增且不重复,这个要求是不是必要的?如果把Prepare阶段第2步中的>改为>=呢?

WARNING: 强烈建议花一些来仔细思考上面的问题,在得出自己的答案之后再继续往下看

继续阅读:

被误用的“一致性”

想必每个接触过分布式系统的同学都没少看到过“一致性”这个词,但是我最近有一个越来越强烈的感觉:“一致性”这个词已经被严重的误用了,以至于当我看到这个词的时候,我甚至得花些功夫去思考这到底指的是哪个“一致性”,更严重的是,当别人在谈到“一致性”的时候,实际上他们在谈的完全是另一种东西。

无辜的Paxos


故事的起因来源于Paxos(没错,又是这货),网上对于Paxos的文献太多,而且质量参差不齐,在绝大多数的中文文档中,你都可以看到这样的描述:“Paxos是一个分布式强一致性协议”,不瞒你说,每次看到这样的表述的时候,我的内心是崩溃的…且听我慢慢道来。

问题的由来很大一部分原因在于英文对中文的翻译,因此我们必须将术语还原到英文进行讨论,『一致性』对应的英文名词应该是Consistency没错了,然后我们在Lamport大神的原始论文《Paxos Made Simple》中搜索关键词,你会发现:

"Consistency" Not Found

“Consistency” Not Found

没错,论文中一次都没有提到过Consistency,也就是说,Paxos和『一致性』根本半毛钱关系都没有啊!那Paxos究竟是什么呢?论文中写的很明确——”The Consensus Algorithm”。

PS:本文中所有使用中文“一致”均指Consistency,“共识”为Consensus。

继续阅读:

分布式共识(Consensus):Viewstamped Replication、Raft以及Paxos

从上篇文章到现在,已经有半年多的时间没有写过什么了,时间真是匆匆而过,感觉从上次写博客到现在似乎也就是一眨眼的功夫。

回顾我这大半年,完全可以用四个字概括:“不务正业”,先是跟着曼昆的书学习了微观、宏观经济学的基础知识,恶补了一下个人理财的基础理论(很有意思,但依然挡不住我买的基金嗷嗷跌),然后又入坑了摄影(其实就是买个微单瞎拍瞎修)。至于个人的技术提升方面就显得捉襟见肘了,先是跟着斯坦福CS145、CS245两门课程复习了一下数据库方面的知识,然后就在分布式系统的泥沼中挣扎到了现在…可能唯一一件值得纪念的事情就是去年年底抱大牛大腿参加某司举办的hackathon,过程中学到了一点Golang的皮毛,最后搞了个apple watch耍(队友大牛依然表示对结果不太满意…),另外出于对tby大牛的仰慕,又补习了一下前端开发技能,然并卵,已经又忘光了…

一不小心写了一大段流水账,回归主题。之前花了大概两个多月时间从头琢磨分布式系统,研一时候修这门课完全是白学了,本来学的就不好,两年过去基本也不剩什么了。翻了两本最出名的教材,看了一些高校的课程安排和slides,总算感觉自己有点“上道”了~

这篇文章主要总结一下我个人认为是整个分布式系统中最为重要的问题(没有之一):分布式共识(Consensus)

达成共识

达成共识

PS:我在学习过程中是以《分布式系统:概念与设计》1这本书作为基础的,在下文中如果没有特别指明,所提书中内容均指该书。

继续阅读: