面向分布式系统工程师的分布式系统理论(译)

原文:Distributed systems theory for the distributed systems engineer

译者:youngsterxyf

Gwen Shapira,大腕级的解决方案架构师(SA),如今 Cloudera 的全职工程师,在 Twitter 上提的一个问题引起了我的思考。

如果是以前,我可能会回答“嗯,这里有篇 FLP 论文,这里有篇 Paxos 论文,这里还有篇拜占庭将军问题的论文...”,我会罗列一箩筐重要的材料,如果你一头扎进去,至少花费 6 个月的时间才能过一遍这些材料。然而我已逐渐明白推荐大量的理论性的论文通常恰恰是着手学习分布式系统理论的错误方式(除非你在做一个 PhD 项目)。论文通常比较深入难懂,需要认真地研习,通常还需要大量的时间投入(significant experience)来理清这些论文的重要贡献,以及在整个理论体系中的位置。要求工程师具备这样的专业水平又有多大的意义呢?

但是,很遗憾,对分布式系统理论方面的重大研究成果和思想进行概括、归纳、背景分析的‘导引’性质的优秀材料非常缺乏;特别是没有居高临下态度的材料。对这块空白区域的思考让我想到了另一个有趣的问题:

一个分布式系统工程师应该知道些什么分布式系统理论?

在这种情况下,一知半解(a little theory)并不会是一件多危险的事情。因此我尝试整理一个列表,罗列出作为一个分布式系统工程师的我认为能够直接应用于我日常工作的一些基本概念;或者让分布式系统工程师完全有能力设计一个新系统的“筹码”。如果你认为我漏掉了一些东西,请联系我。

入门第一步

以下 4 篇材料出色地解释了构建分布式系统会遇到的一些挑战,共同概述了一系列分布式系统工程师必须要解决的技术上的难题,为之后章节中更深入的研究做好准备。

失败和时间

分布式系统工程师需要面对的许多困难最终都可以归咎于两个潜在的原因:

  • 进程可能会失败
  • 不存在一种好的方式来周知目前为止进程已经做了些什么

进程之间对于时间的认知能共享些什么?哪些失败的场景是能够检测到?什么算法和原语可能被正确地实现?这三个问题有着非常深层的联系。多数时候,我们会假设两个不同节点之间对于时间概念或时间以什么样的速度逝去没有任何可共享的认知。

你应该知道:

  • 失败模式的(部分)分层:崩溃停止->排除(omission)->拜占庭容错。你应该理解:在高层次上可能发生的问题在低层次上肯定可能发生,在低层次上不可能发生的问题在高层次上也肯定不可能发生。
  • 在没有任何共享时钟的情况下如何判断在另一个事件之前是否产生了某事件。这意味着你需要理解 Lamport 时钟及其一般化的向量时钟,也需要阅读一下这篇 Dynamo 论文
  • 单个失败发生的可能性对于我们实现正确的分布式系统到底会有多大的影响(请阅读下面关于 FLP 结果的笔记)?
  • 不同的时间模型:同步、部分同步和异步(若我找到好的参考文献会添加链接)

容错的基本矛盾

一个系统,若要不降级而容忍某些错误的发生,就必须能够好像那些错误没有发生一样地运作。这通常意味着系统的这些部分必须能够冗余地工作,但是非绝对必要地做更多的工作通常会在性能和资源耗用方面产生一些消耗。这是为系统添加容错带来的基本矛盾。

你应该知道:

基本的原语

分布式系统中很少有大家一致认同的基本构建块,但越来越多地在出现。你应该以下的问题是什么,以及在哪可以找到它们的解决方案:

  • 群首选举(leader election)(例如 Bully 算法
  • 一致的快照(例如 Chandy 和 Lamport 所写的经典论文
  • 共识(阅读上文提到的关于 2PC 和 Paxos 的博文)
  • 分布式状态机复制(看看 Wikipedia 就可以,但 Lampson 的论文更权威,只是枯燥了点)。

基础结论

某些客观事实是需要内化于心的,以下是几个关键点(a flavour)(当然还有更多):

  • 如果进程之间可能丢失某些消息,那么不可能在实现一致性存储的同时能响应所有的请求。这就是 CAP 定理
  • 以这样一种方式(a.始终是正确的、b.始终能终止-若在一个可能因失败崩溃停止(crash-* stop failures)的异步系统中有(甚至仅)一台机器失效时(FLP 的结果))。我希望在洛杉矶题为 Papers We Love 报告的第一部分幻灯片-进行证明之前-已经合理地解释了这个结论。建议:没有实际的必要理解这个证明。
  • 一般而言,消息交互少于两轮是不可能达成共识(Consensus)。

真实系统

最重要的练习是重复地阅读新兴的、真实系统的描述,并尝试评价它们的设计决策。一遍又一遍地这样去做。一些建议:

Google:

GFSSpannerF1ChubbyBigTableMillWheelOmegaDapperPaxos Made LiveThe Tail At Scale

Not Google:

Dryad, Cassandra, Ceph, RAMCloud, HyperDex, PNUTS