极客时间已完结课程限时免费阅读

学习路径 | 分布式协议与算法你应该这么学

学习路径 | 分布式协议与算法你应该这么学-极客时间

学习路径 | 分布式协议与算法你应该这么学

2020-07-02 韩健 来自北京
《分布式协议与算法实战》
课程介绍

讲述：于航

时长12:43大小11.64M

你好，我是韩健。
在正式开始学习这门课之前，我想先和你聊一聊怎么学，因为掌握了学习路径、建立了全局观之后，你才能达到事半功倍的效果。
我们都知道，分布式协议和算法（为了不啰嗦，咱们下文都简称分布式算法）很实用、也很火，很多后端工程师在面试的时候，都会被问及分布式、高可用、一致性这些专业名词背后的算法原理和实现方式。
但是分布式算法也是比较新的，快速发展的。比如，1989 年莱斯利·兰伯特（Leslie Lamport）提出了 Paxos，2006 年，谷歌研发团队让 Paxos 在生产环境中落地，但是 Paxos 缺乏编程实现的必须细节，最终的算法实现仍是建立在一个未证明的算法之上。再后来，也就是到了 2013，斯坦福大学的迭戈·安加罗（Diego Ongaro）和约翰·奥斯特霍德（John Ousterhout）提出了 Raft，但是 2016 年，Raft 仍在解决成员变更的 Bug。
正因为技术比较新，所以尚未能沉淀为书，很多同学都找不到分布式算法方面的经典书籍，再加上互联网上中文资料错误多，他们在学习相关的分布式算法的时候，会觉得吃力和困惑。
那么，如何才能掌握一个相对新、而且又在蓬勃快速发展的技术知识呢？这就是我这节课想要跟你分享的内容：如何高效地学习和掌握分布式算法？
在我看来，开发分布式系统最关键的就是根据场景特点，选择合适的算法，在一致性和可用性之间妥协折中，而妥协折中的关键就在于能否理解各算法的特点。
也就是说，我们先要弄清楚每个算法的特点是什么，适合怎样的场景，这样当你在开发分布式系统时，才能做到心中有数，游刃有余地选择适合的算法，来解决实际场景的问题。
那么问题来了：这些算法究竟有什么特点？适合怎样的场景呢？

分布式算法的四度空间

为了帮你更好地理解最常用的分布式算法的特点，我从拜占庭容错、一致性、性能和可用性四个纬度帮你整理了一张表，你可以对照着看一下：

拜占庭容错

拜占庭错误是莱斯利·兰伯特在《拜占庭将军问题》中提出的一个错误模型，描述了一个完全不可信的场景，除了存在故障行为，还存在恶意行为。顾名思义，拜占庭容错（Byzantine Fault Tolerance，BFT），就是指能容忍拜占庭错误了。
而非拜占庭容错，又叫故障容错（Crash Fault Tolerance，CFT），解决的是分布式系统中存在故障，但不存在恶意节点的共识问题，比如进程崩溃、服务器硬件故障等。
一般而言，在可信环境（比如企业内网）中，系统具有故障容错能力就可以了，常见的算法有二阶段提交协议（2PC）、TCC（Try-Confirm-Cancel）、Paxos 算法、ZAB 协议、Raft 算法、Gossip 协议、Quorum NWR 算法。
而在不可信的环境（比如有人做恶）中，这时系统需要具备拜占庭容错能力，常见的拜占庭容错算法有 POW 算法、PBFT 算法。

一致性

一般来讲，我们将一致性分为三类。
强一致性：保证写操作完成后，任何后续访问都能读到更新后的值。
弱一致性：写操作完成后，系统不能保证后续的访问都能读到更新后的值。
最终一致性：保证如果对某个对象没有新的写操作了，最终所有后续访问都能读到相同的最近更新的值。
但是我要提醒你注意，强一致性是具有多种含义的。
首先，在埃里克·布鲁尔的猜想中，CAP 中的强一致性（也就是 C）是指 ACID 的 C，系统状态的一致性，而这种一致性，可以通过二阶段提交协议来实现。
其次，在 CAP 定理中，CAP 中的强一致性（也就是 C）是指原子一致性（也就是线性一致性）。其中，Paxos、Raft 能实现线性一致性，而 ZooKeeper 基于读性能的考虑，它通过 ZAB 协议提供的是最终一致性。
一般而言，在需要系统状态的一致性时，你可以考虑采用二阶段提交协议、TCC。在需要数据访问是的强一致性时，你可考虑 Raft 算法。在可用性优先的系统，你可以采用 Gossip 协议来实现最终一致性，并实现 Quorum NWR 来提供强一致性。

可用性

可用性说的是任何来自客户端的请求，不管访问哪个非故障节点，都能得到响应数据，但不保证是同一份最新数据，可用性强调的是服务可用。
一般来讲，采用 Gossip 协议实现最终一致性系统，它的可用性是最高的，因为哪怕只有一个节点，集群还能在运行并提供服务。其次是 Paxos 算法、ZAB 协议、Raft 算法、Quorum NWR 算法、PBFT 算法、POW 算法，它们能容忍一定数节点故障。
最后是二阶段提交协议、TCC，只有当所有节点都在运行时，才能工作，可用性最低。

性能

一般来讲，采用 Gossip 协议的 AP 型分布式系统，具备水平扩展能力，读写性能是最高的。其次是 Paxos 算法、ZAB 协议、Raft 算法，因为它们都是领导者模型，写性能受限于领导者，读性能取决于一致性实现。最后是二阶段提交协议和 TCC，因为在实现事务时，需要预留和锁定资源，性能相对低。
以上就是这些算法的特点了，了解完这部分内容之后，我想你一定有这样的疑问：“老韩，这些算法看起来很深奥，我怎样才能搞懂它们呢？按部就班的学吗？”
根据我多年的经验，你之所以觉得这些算法和相关的分布式技术，学起来比较难，是因为它们比较新，缺乏体系化。如果这时有个全景图，帮你建立全局观，那么你就可以体系化的理解相关算法了，在提高学习效率同时，也能在实际场景中“按图索骥”的选用相关的算法，而这些就是我接下来想和你具体聊一聊的。

专栏内容该如何学？

拜占庭将军问题：最复杂的分布式容错模型
难度：一颗星
学习材料： 01 讲、加餐 | 拜占庭将军问题：如何基于签名消息实现作战计划的一致性？
拜占庭容错是分布式领域最复杂的容错模型，是你必须要了解的。另外，口信消息型拜占庭问题之解、签名消息型拜占庭问题之解，你可以通过预设不同的忠将数、叛将数，来推演下，在推演中学习和掌握。
CAP 理论：酸碱平衡之道
难度： 二颗星
学习材料： 02 讲、03 讲、04 讲
学习 CAP 理论的关键，不是仅仅知道 CAP 不可能三角，而是要能在 C 和 A 之间，根据实际场景特点，妥协权衡折中。这也是 CAP 猜想提出的初衷，希望业界能重视可用性，而不是只考虑 ACID。
分布式事务：进退与共
难度： 二颗星
学习材料： 03 讲，加餐 | MySQL XA 是如何实现分布式事务的，加餐 | TCC 如何实现指令的原子性
事务是指具有 ACID 特性的一组操作，要么全部执行，要么全部不执行，实现的是系统状态的一致性。一般在支付，或其他需要原子操作的场景下比较常用。
实现分布式事务，最常用的方法是二阶段提交协议和 TCC，这两个算法的适用场景是不同的，二阶段提交协议实现的是数据层面的事务，比如 XA 规范采用的就是二阶段提交协议；TCC 实现的是业务层面的事务，比如当操作不仅仅是数据库操作，还涉及其他业务系统的访问操作时，这时就应该考虑 TCC 了。
分布式强一致性：你必须给我最新的数据
难度： 五颗星
学习内容： 05 讲、06 讲、07 讲、08 讲、09 讲、10 讲。
很多同学经常误解的一个点，就是将 Consensus（共识）当成了一致性，也就是称为 Paxos、Raft 为一致性算法，其实 Paxos 和 Raft 是共识算法。而之所以出现这个问题，是因为在很多中文文章中，将 Consensus 和 Consistency 都翻译成了一致性，其实这样是不合适的，因为共识（Consensus）和一致性（Consistency）是两个完全不同的概念。
共识：各节点就指定值（Value）达成共识，而且达成共识后的值，就不再改变了。
一致性：是指写操作完成后，能否从各节点上读到最新写入的数据，如果立即能读到，就是强一致性，如果最终能读到，就是最终一致性。
提到共识算法，Paxos 是一个必须要提及的话题，而且 ZAB 协议、Raft 算法都可以看作是 Paxos 变种，所以，你需要了解 Paxos 算法。
但因为 Paxos 算法的可理解性和可编程性痛点突出，所以在实际场景中，最常的共识算法是 Raft，我们可以基于 Raft 实现强一致性系统，Raft 是需要彻底掌握的，在学习时，你可以结合 17 讲、18 讲、19 讲、20 讲来一起学习，从前传（Paxos）到理论，再到实战，彻底吃透和掌握。
而一致哈希是常用的寻址算法，能突破集群性能的领导者限制，也是需要我们掌握的。
分布式最终一致性：数据旧点没关系
难度：三颗星
学习材料： 11 讲、12 讲。
无论实现分布式事务还是强一致性，性能和可用性都是挑战，在一些对性能或可用性要求比较高的场景，比如时序数据、统计数据、状态数据（QQ 登录状态），最终一致性是首选，因为最终一致性系统不仅能提供出色的性能，还能实现水平扩展。而 Gossip 协议是实现最终一致性的常用方法。
如果实现了最终一致性，但有时可能需要临时提供强一致性能力，这个时候，你可以用 Quorum NWR 来实现。
ZAB 协议：ZooKeeper 背后的一致性秘密
难度： 二颗星
学习材料： 15 讲，加餐 | ZAB 协议（一）：主节点崩溃了，怎么办？加餐 | ZAB 协议（二）：如何从故障中恢复？加餐 | ZAB 协议（三）：如何处理读写请求？
ZooKeeper 是一个常用的分布式协调服务，而且 ZAB 协议在共识算法的发展过程中起到了一个承前启后的作用，它受 Paxos 算法、原子广播协议的启发，又影响到后来的 Raft 算法。但从实战的角度，ZAB 协议的实现，无法剥离 ZooKeeper 代码独立使用，所以这部分内容，我建议日常使用 ZooKeeper 的同学仔细学习一下，其他同学的话，可以选学。
拜占庭容错算法：有人作恶，如何达成共识
难度： 二颗星
学习材料： 13 讲、14 讲，加餐 | PBFT 算法：如何替换作恶的领导者？
在一个完全不可信的环境中（比如有人作恶），如果需要达成共识，那么我们就必须考虑拜占庭容错算法，常用的拜占庭容错算法有 POW 算法、PBFT 算法，它们在区块链中应用广泛。
实战：实践是最好的学习方式
难度：四颗星
学习材料： 16 讲、17 讲、18 讲、19 讲、20 讲。
你可能有这样的体会，技术的学习往往是在模仿中开始的，在实战中顿悟升华。分布式算法的学习也不例外，技术是需要在实战中学习，也只有在实战中，你才能真正的理解技术。
他山之石，可以攻玉，为了帮助你更好地理解实际场景中一致性的实现，我会剖析 InfluxDB 企业版的一致性实现（强一致性和最终一致性两个方案）。也会分析一个流行的 Raft 实现（Hashicorp Raft），除了在代码中理解 Raft 算法，也会带你熟悉一下 Hashicorp Raft 的 API 接口，最终在 19、20 讲，带你使用 API 接口开发实现自己的分布式 KV 系统。
我啰嗦了那么多，其实就是为了让你更高效地掌握常用的分布式算法。另外，为了帮你更好的理解算法的特点和整体学习的思路，我做了个知识地图，方便你梳理整个知识体系。

总结

生有涯知无涯，只有抓住技术本质，才能举一反三，以不变应万变。而本课程我带你了解的这些算法和理论，都是最经典和经得起时间检验的。
但学习的过程绝不会一帆风顺，如果你在学习过程中有困惑、茫然，甚至是沮丧，希望你能多留言，咱们聊一聊，一起想想办法，让我们把分布式算法学习这件意义非凡的事情坚持下去，一起攻克分布式系统设计的关键难题。
现在，就让我们正式开始分布式算法之旅吧！一起享受技术的乐趣。
分享给需要的人，Ta购买本课程，你将得18元
生成海报并分享

赞 55

提建议

© 版权归极客邦科技所有，未经许可不得传播售卖。 页面已增加防盗追踪，如有侵权极客邦将依法追究其法律责任。
上一篇
开篇词 | 想成为分布式高手？那就先把协议和算法烂熟于心吧
下一篇
01 | 拜占庭将军问题：有叛徒的情况下，如何才能达成共识？
 写留言

精选留言(18)

  • 小何
    2020-10-08
    “一般而言，在需要系统状态的一致性时，你可以考虑采用二阶段提交协议、TCC。在需要数据访问是的强一致性时，你可考虑 Raft 算法。在可用性优先的系统，你可以采用 Gossip 协议来实现最终一致性，并实现 Quorum NWR 来提供强一致性。” 老师，能解释一下上文中的需要系统状态的一致性和数据访问的一致性？

    作者回复: 加一颗星:)，系统状态的一致性，可以理解为操作要么全部成功，要么全部失败，各节点处于一个一致的状态；数据访问的一致性，可以理解为写操作完成后，能否读取到最新数据，如果写操作完成后，读操作都能读取到最新数据，那么就是强一致性。

    共 5 条评论
    17
  • 赵学习
    2021-04-23
    为什么大多数人都说zk是cp的，有说强一致的，又说顺序一致的，这里又说zab是最终一致的，希望后面阅读中能找到合适的答案！
    共 3 条评论
    13
  • 离境”
    2021-06-07
    之前看其他文章，搞得自己云里雾里的，希望在这拨开云雾
    3
  • 庄周梦蝶
    2021-06-13
    老师分布式的脑裂问题、羊群问题能讲讲吗？面试中经常问到
    共 1 条评论
    2
  • --
    2020-08-30
    我觉得线性一致性有点绕，所以补充一个线性一致性的说明：https://en.wikipedia.org/wiki/Consistency_model#Sequential_consistency 线性一致性是属于强一致性的，但是它是“稍弱”的强一致性，因为在算法系统的内部，写操作的提交并不是所有的节点都是同时应用的。而系统状态的一致性，写操作的提交是同时应用的，所以它是“稍强”的一致性。之所以说它们都是强一致的，那是因为一致性是对外部系统访问算法系统而言，只有写操作提交之后，外部系统都能读取到最新的值。如有不正确之处，麻烦指教。
    展开
    共 2 条评论
    2
  • 返璞归真
    2020-08-03
    在四度空间的表格中，TCC应该是强一致性吧。在一致性标题下，还强调了强一致性的两种不用理解。前后有矛盾呀

    作者回复: 加一颗星:)，TCC最终一致性，指的是系统状态的最终一致。

    共 2 条评论
    1
  • abcdabcd999
    2023-01-16 来自山西
    ”我们可以基于 Raft 实现强一致性系统“ 这样子的说法其实很不严谨，这也是模糊了 raft 和 2PC 差异导致的结果
  • abcdabcd999
    2023-01-16 来自山西
    我觉得不应该把 2PC 和 Paxos、raft 这些放一起说，它们本质上是不同的，共识只是 log replication的，它和 2PC 完全不一样
  • 纵不朽
    2022-08-27 来自广东
    现在，raft还有bug吗？
  • 逍遥
    2022-05-30
    读了两边，还是有点懵逼，但是觉得很有料。期待下个月重读的时候能有很深入的理解！
  • 零零玲
    2021-12-08
    老师，是否可以理解为可用性高的协议性能也一定高？？
  • 宇飞
    2021-10-27
    棒棒的，系统整理各个算法区别和学习方法，收货多
  • Dear。
    2021-06-01
    「CAP关注的是数据」这个说法成立吗
  • 金龟
    2021-01-19
    系统状态一致性是指原子性吧
  • 密码123456
    2020-07-04
    😂😂在回头看的时候，发现自己只记得大概。正好复习下。

    作者回复: 加一颗星:)，学而时习之不亦说乎，有问题多留言，咱们多交流。

  • Geek.Kwok
    2020-07-03
    老师的总结很棒，给我们指明了学习和实践的框架

    作者回复: 学习中，遇到问题，多留言交流，一起解决:)

  • 任禹潼
    2020-07-02
    必须给个赞
  • 宁悦
    2020-07-02
    老师，这个加餐点赞！