适合 分布式系统工程师 的 分布式系统理论
适合 分布式系统工程师 的 分布式系统理论
Gwen Shapira曾在Cloudera做工程师，现在宣传Kafka，他在Twitter问了以下问题，使我有所思考。
我想在分布式理论上有所提升。应该从哪开始？有推荐的书？
— Gwen (Chen) Shapira (@gwenshap) August 7, 2014
我第一反应是“可以看：FLP论文、paxos论文、Byzantine将军论文”。我推荐的主要阅读材料，如果你贸然去读，你至少要阅读6个月才会有感觉。由此可知，推荐一吨的理论论文让你阅读，这是了解分布式系统的错误的方式（除非你在读博士）。 论文一般是深奥、复杂的，而且需要一系列学习和丰富的经验才能感觉到其贡献、才能把其放到对应的场景(以理解和应用)。
工程师了解分布式理论有什么好处？
很不幸，几乎没有好的引导文章，来总结、提炼、场景化 分布式系统理论中的重要结论和想法; 特别是 通俗易懂的引导文章 更没有。
考虑这样的空白区域，让我想问另一个问题：
一个分布式系统工程师应该了解什么样的分布式系统理论？
这种情况下，了解一点点理论并不是坏事。我日常工作是一个分布式系统工程师，下面会给出 我认为适合我的基本概念 们。
你认为我缺失的请告知我!
准备
下面四个读物解释了构建分布式系统会遇到的困难。这些读物都勾勒了一些列 抽象而非技术 的困难，分布式系统工程师必须要克服这些困难。这些读物的后面章节有更详细的研究。
Distributed Systems for Fun and Profit 是一本小书，它想覆盖分布式系统中的一些基本问题，包括 时钟所起的作用、不同策略的复制。
Notes on distributed systems for young bloods - 非理论，而是一个很好的实践，以让你落到实处。
A Note on Distributed Systems - 一个经典论文，关于 为什么你不能假装所有远程交互像本地对象一样。
The fallacies of distributed computing 分布式计算的8个错误的推论，以提醒系统设计者。
你应该知道 安全 和 活力:
- 安全 说的是 永远不会发生坏事。比如，不返回不一致的值 是 一种 安全， 同一时刻不会选出两个 主节点 也是 一种 安全。
- 活力 说的是 好事情终究会发生。比如，对于每个api调用，一个系统终究会返回一个结果，这是一种 活力；保证一次写磁盘最终总能结束，这是一种 活力。
失败和时钟
分布式系统工程师面对的许多困难可以归结为以下两个原因:
-
进程可能失败
-
There is no good way to tell that they have done so
进程间怎么共用时钟、什么样的失败可以检测、什么样的算法和原语可以被正确实现，这三者之间有很深的联系。一般情况下，我们假设不同节点绝对无法共用时钟(时刻值或流过了多少时间).
你应该知道:
- 失败模型的层次：节点崩溃后关机 -> 节点崩溃后死机(经过无限长时间后才响应) -> 恶意节点 (不遵守约定的规则) 。 各个层次间逐渐将限制放松，你应该知道这些限制.
- 允许单节点失败对实现正确的分布式系统有多大的冲击？(见下面FLP结论处)
- 时钟的不同模型：同步、部分同部 、 异步
- 失败检测是一个基本问题，失败检测可以平衡准确度和完成度(如果能检测到失败了，则可以容许不那么准确、没完全做完)，失败检测也可以解决安全和活力间的冲突。把失败检测作为理论来研究的论文是 Chandra and Toueg’s ‘Unreliable Failure Detectors for Reliable Distributed Systems’. 不过也有一些简短的总结-我特别喜欢this random one from Stanford.
容错导致的基本矛盾
一个系统容忍一些错误而没有降级 必须能当成 就像这些错误没有发生过一样。这意味着系统的一部分要冗余地工作(同样的功能部署多个节点)，冗余是绝对必要的，冗余一般会带来性能和资源的消耗。这就是给一个系统添加冗余的基本矛盾。
你应该知道：
- 确保串行单复制的多数派技术. 见 Skeen’s original paper, 不过或许更好的是 Wikipedia条目.
(多数派中有一个是主节点,其余为从节点，以主节点接收到的写请求序列为准[即串行]，主节点单方面的要求从节点们接受主节点的写请求序列[从节点不得反抗、不得有异议：从节点是诚实的非恶意的、遵守全局规则的、非拜占庭的])
-
最终一致性、其他技术 以 对系统行为做更弱的保证 为代价 来 设法避开 此矛盾 . 可以看 Dynamo 论文 , 不过 必须要读 Pat Helland的论文 经典 Life Beyond Transactions .
基本原语
在分布式系统中，很少有约定的基本构建块，更多的是处于形成中的基本构建块。你应该知道下面的问题是什么，并且从哪能找到他们的解决方案：
- 主节点选举 (例如 Bully 算法)
-
一致快照 (比如 这个来自 Chandy and Lamport的经典论文 )
-
一致性 (见上面 2PC 、 Paxos 处)
- 分布式状态机复制 (看Wikipedia 就行, Lampson的 论文 是权威但是太枯燥了).
- 广播 - 同时发送消息给集群
* [原子广播](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.3.4709&rep=rep1&type=pdf) - 你能发送消息给一集群，使得要么集群中的所有节点都收到了这条信息、要么集群中全部节点都没收到此消息?(这就是原子广播)
* Gossip ([经典论文](http://bitsavers.informatik.uni-stuttgart.de/pdf/xerox/parc/techReports/CSL-89-1_Epidemic_Algorithms_for_Replicated_Database_Maintenance.pdf))
* [因果广播](https://www.cs.cornell.edu/courses/cs614/2003sp/papers/BSS91.pdf) (也可以看看 [Birman](https://www.cs.rice.edu/~alc/comp520/papers/Cheriton_Skeen.pdf)和[forth](https://www.cs.princeton.edu/courses/archive/fall07/cos518/papers/catocs-limits-response.pdf) ).
-
链式复制 (将节点们放进一个虚拟链表中，从而可以干净的确保写请求的一致性和顺序 ).
-
对负载中读请求占绝大多数的一系列改良
基础结论
有些事实只需要主观理解(不需要关注证明).
-
如果节点间可能丢失消息[:P]，那么你不可能 既 实现一致性存储[:C] 又 响应所有时刻的请求[:A]. 这就是 CAP理论.
-
在一个异步系统中，一致性不可能以这样一个途径实现：既a) 总是正确的 ； 又b) 总是能结束 即使只有一个节点可能以 崩溃-*停止 失败 (FLP结论). 在看证明之前，看下我以简明的方式解释FLP结论的论文 Papers We Love SF talk . 建议: 没有理解证明的需要.
(一个异步系统中，假设节点崩溃后停止而不是奔溃后又恢复；1、要确保结果总是正确的，2、每次写请求能够在有限时间内返回结果。这两点没法同时满足：这就是FLP结论)
-
一般地，只进行少于2轮的消息传递，不可能达成一致性 .
-
原子广播和一致性，二者的难度精确的相等。更直白的说，如果你能解原子广播，那么你也能解一致性，反之亦然。 Chandra 和 Toueg 证明了这一点, 但是你只需要知道这个论断是成立的。
真实系统
最重要的、应该不断重复的实践是：读新的、真实的系统的描述，并评价他们设计的决定。 下面是建议的系统：
Google:
Not Google:
Postscript 结尾
如果你驯服了这个列表中的所有概念和技术，我很乐意和你聊聊Cloudera的分布式系统工程师职位。
