面向分布式系统工程师的分布式系统理论（译）

- 日理万妓 2022-11-21 15:17 150阅读 0赞

## [面向分布式系统工程师的分布式系统理论（译）][Link 1]   ##

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

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

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

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

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

入门第一步

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

*  [好玩又实在的分布式系统理论][Link 2]是一本简短的书籍，其内容覆盖了分布式系统领域的一些基本议题，包括时间的作用及不同的复制策略。
 *  [为分布式系统领域新人整理的笔记][Link 3] - 不是理论对理论地讲述，而是做一个非常好非常实用的平衡，让你对其余材料的阅读能够落地。
 *  [分布式系统研究综述报告][Link 4] - 一篇经典的论文，解释了为什么不能将所有远程交互都模拟成和本地对象一样。
 *  [关于分布式计算的若干谬论][Link 5] - 分布式计算方面的8点谬论，提醒系统设计者可能会忘记的几类事情。

失败和时间

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

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

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

你应该知道：

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

容错的基本矛盾

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

你应该知道：

*  确保单拷贝可串行化(single-copy serialisability)的仲裁(quorum)技术。可阅读[Skeen的原始论文][Skeen]，但可能更建议阅读[这个Wikipedia词条][Wikipedia]。
 *  关于[两阶段提交][Link 8]、[三阶段提交][Link 9]和[Paxos][]算法，以及为什么它们有不同的容错性质。
 *  最终一致性，及其他技术是如何以弱化对系统行为的保证为代价来尝试避免这种矛盾的。这篇[Dynamo论文][Dynamo]是一个很好的起点，同时Pat Helland的经典之作[Life Beyond Transactions][]也是必读的。

基本的原语

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

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

基础结论

某些客观事实是需要内化于心的，以下是几个关键点（a flavour）（当然还有更多）：

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

真实系统

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

**Google:**

[GFS][]、[Spanner][]、[F1][]、[Chubby][]、[BigTable][]、[MillWheel][]、[Omega][]、[Dapper][]、[Paxos Made Live][]、[The Tail At Scale][]。

**Not Google:**

[Dryad][], [Cassandra][], [Ceph][], [RAMCloud][], [HyperDex][], [PNUTS][]

[Link 1]: https://blog.xiayf.cn/2014/08/10/Distributed-systems-theory-for-the-distributed-systems-engineer/
[Twitter]: https://twitter.com/gwenshap/status/497203248332165121
[Link 2]: http://book.mixu.net/distsys/
[Link 3]: http://www.somethingsimilar.com/2013/01/14/notes-on-distributed-systems-for-young-bloods/
[Link 4]: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.41.7628
[Link 5]: http://en.wikipedia.org/wiki/Fallacies_of_Distributed_Computing
[-_omission]: http://www.cse.psu.edu/~gcao/teach/513-00/c7.pdf
[Link 6]: http://en.wikipedia.org/wiki/Byzantine_fault_tolerance
[Lamport]: http://web.stanford.edu/class/cs240/readings/lamport.pdf
[Link 7]: http://en.wikipedia.org/wiki/Vector_clock
[Dynamo]: http://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf
[Skeen]: https://ecommons.library.cornell.edu/bitstream/1813/6323/1/82-483.pdf
[Wikipedia]: http://en.wikipedia.org/wiki/Quorum_%28distributed_computing%29
[Link 8]: http://the-paper-trail.org/blog/consensus-protocols-two-phase-commit/
[Link 9]: http://the-paper-trail.org/blog/consensus-protocols-three-phase-commit/
[Paxos]: http://the-paper-trail.org/blog/consensus-protocols-paxos/
[Life Beyond Transactions]: http://www.ics.uci.edu/~cs223/papers/cidr07p15.pdf
[Bully]: http://en.wikipedia.org/wiki/Bully_algorithm
[Link 10]: http://research.microsoft.com/en-us/um/people/lamport/pubs/chandy.pdf
[Wikipedia 1]: http://en.wikipedia.org/wiki/State_machine_replication
[Lampson]: http://research.microsoft.com/en-us/um/people/blampson/58-Consensus/Acrobat.pdf
[CAP]: http://lpd.epfl.ch/sgilbert/pubs/BrewersConjecture-SigAct.pdf
[Papers We Love]: http://www.slideshare.net/HenryRobinson/pwl-nonotes
[GFS]: http://static.googleusercontent.com/media/research.google.com/en/us/archive/gfs-sosp2003.pdf
[Spanner]: http://static.googleusercontent.com/media/research.google.com/en/us/archive/spanner-osdi2012.pdf
[F1]: http://static.googleusercontent.com/media/research.google.com/en/us/pubs/archive/41344.pdf
[Chubby]: http://static.googleusercontent.com/media/research.google.com/en/us/archive/chubby-osdi06.pdf
[BigTable]: http://static.googleusercontent.com/media/research.google.com/en/us/archive/bigtable-osdi06.pdf
[MillWheel]: http://static.googleusercontent.com/media/research.google.com/en/us/pubs/archive/41378.pdf
[Omega]: http://eurosys2013.tudos.org/wp-content/uploads/2013/paper/Schwarzkopf.pdf
[Dapper]: http://static.googleusercontent.com/media/research.google.com/en/us/pubs/archive/36356.pdf
[Paxos Made Live]: http://www.cs.utexas.edu/users/lorenzo/corsi/cs380d/papers/paper2-1.pdf
[The Tail At Scale]: http://cacm.acm.org/magazines/2013/2/160173-the-tail-at-scale/abstract
[Dryad]: http://research.microsoft.com/en-us/projects/dryad/eurosys07.pdf
[Cassandra]: https://www.cs.cornell.edu/projects/ladis2009/papers/lakshman-ladis2009.pdf
[Ceph]: http://ceph.com/papers/weil-ceph-osdi06.pdf
[RAMCloud]: https://ramcloud.stanford.edu/wiki/display/ramcloud/RAMCloud+Papers
[HyperDex]: http://hyperdex.org/papers/
[PNUTS]: http://www.mpi-sws.org/~druschel/courses/ds/papers/cooper-pnuts.pdf