🗂 目录

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

May 10, 2020 • 预计阅读时间 6 分钟

Distributed systems theory for the distributed systems engineer 简单明了的分布式入门读物

原文:   istributed systems theory for the distributed systems engineer(2014)
译者:  夏永锋

原文在 2018 年进行了更新,我在夏永锋译文基础上做了部分更改。


Gwen Shapira,曾今 的 Cloudera 工程师,现在引领 Kafka,在 Twitter 上提的一个问题 引起了我的思考。

我需要提高我在分布式系统理论方面的熟知程度,我该怎么开始,有哪些推荐书籍?

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

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

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

在这种情况下,一知半解(a little theory)并不会是一件多危险的事情。因此我尝试整理一个列表,罗列出作为一个分布式系统工程师的我认为能够直接应用于我日常工作的基础理论。如果你认为我漏掉了一些东西,请联系我。

入门第一步

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

你需要知道分布式系统中的 SafetyLiveness 属性:

Safety 属性指的是不好的结果永远不会发生:系统永远不返回不一致的结果就是 Safety 属性,例如系统不会在同一时刻选出两个 leader;
Liveness 属性指的是好的结果最终会发生:系统最终一定会返回 API 调用的结果就是 Liveness 属性,例如系统保障每个磁盘写调用一定会处理完成。

失败和时间

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

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

进程之间如何共享各自的时间信息?哪些失败的场景是能够检测到?什么算法和原语可能被正确地实现?这三个问题有着非常深层的联系。多数时候,我们会假设两个不同节点之间对对方的时间信息,或者对方时间过了多久是完全无知的。

你应该知道:

容错的基本矛盾

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

你应该知道:

基本的原语

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

  • leader 选举(leader election):例如 Bully 算法
  • 一致的快照(consistent snapshotting):例如 Chandy 和 Lamport 所写的 经典论文
  • 共识(consensus):阅读上文提到的关于 2PC 和 Paxos 的博文
  • 分布式状态机复制(distributed state machine replication):看看 Wikipedia 就可以,但 Lampson 的论文 更权威,只是枯燥了点
  • 广播(broadcast) - 一次性向多个节点上发布消息
    • Atom 方式 - 你能否要么成功发布消息到所有节点,要么一个都没有?
    • Gossip 方式:Gossip 经典论文
    • Causal 因果排序组播方式:参考 这篇论文 ,也可欣赏 Birman 和 Cheriton 对此提出的 质疑
  • 链复制(chain replication):把节点组织成一个虚拟的链表来保障写的一致性和顺序性

基础结论

某些结论是需要内化于心的,以下是几个关键点(a flavour),当然可以更多:

  • 如果进程之间可能丢失某些消息,那么不可能在实现存储一致性的同时能响应所有的请求。这就是 CAP 定理
  • 共识机制不可能以这样一种方式实现 - 同时满足 a & b:
    • a. 总是正确的
    • b. 总是能终止的 - 在异步系统中,即使仅有一台机器失败(因 FLP 的 crash-*stop 结果而导致)

我希望在 Papers We Love 洛杉矶座谈会上合理地解释了这个结论,参考幻灯片的第一部分-进行证明之前 (提示:没有实际必要去理解如何证明)

  • 一般而言,少于两轮消息交互是不可能达成共识(consensus)。
  • 达成原子广播和达成共识一样难,准确的讲,如果能解决原子广播的问题,共识的问题也能解决,反之亦然,Chandra 和 Toueg 已经给出证明 ,你只要知道这个结论就好。

真实的系统

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

系统设计 & 架构

  上一篇:Jackson 常用注解

  下一篇:淘宝服务端高并发分布式架构演进之路(转载)

comments powered by Disqus