跳至主要內容

写了八篇分布式算法,我悟空了

悟空约 2179 字大约 7 分钟...

写了八篇分布式算法,我悟空了

主要内容
主要内容

最近三个月更新了 8 篇分布式理论和算法的文章,发现这些知识点虽然枯燥,但是非常重要,于是每篇我都用故事的方式进行讲解,力求每篇都能让大家都能看懂,是不是很用心呢?

在写的过程中,我慢慢地悟出了分布式理论和算法的真谛,且听下文分解。

重要性

分布式理论和算法的重要性体现在哪呢?

你是不是经常听到 CA,AP 理论,CAP 三角不可能同时达成?

Zookeeper 怎么进行 Leader 选举的?

怎么进行容错?

这些问题的答案都是分布式理论和算法的精髓所在。而且说个很现实的问题,在现阶段,掌握分布式算法也是出去面试架构师、技术专家等高薪职位时,也是会被经常问到的。但是求职者中只有少部分懂这一块。

我为什么要强调分布式算法的重要性?不论是对技术深度的追求,还是长期职业发展的需要,都是可以提升你的核心竞争力的。

好学吗?

现在很多开发同学对分布式的组件怎么使用都有一定经验,也知道 CAP 理论和 BASE 理论的大致含义。但认真去看分布式算法的真的很少,原因有三:

  • 担心算法过于复杂,所以花的时间很少。
  • 网上的资料能用大白话将分布式算法讲清楚的比较少。
  • 学习分布式算法没有一条清晰的路线。

学习分布式协议和算法的路线可以是先学习四大基础理论,作为地基。然后再学习分布式协议和算法。就像是在地基上建房子,地基打好了,才能建更稳固的高楼大厦。

而分布式理论主要有四大块:

四大基础理论

  • 拜占庭将军问题
  • CAP 理论
  • ACID 理论
  • BASE 理论

分布式协议和算法主要有八种:

八大分布式协议和算法

  • Paxos 算法
  • Raft 算法
  • 一致性 Hash 算法
  • Gossip 协议算法
  • Quorum NWR 算法
  • FBFT 算法
  • POW 算法
  • ZAB 协议

如何高效地学习和掌握?

开发分布式系统最关键的就是根据场景特点,选择合适的算法,在一致性和可用性之间妥协折中,而如何做好折中方案,依赖于是否真正理解了各算法的特点。

讲真,如果认真学习这些理论和算法,并清楚了每个算法的特点,适合怎样的场景,当开发分布式系统时,做到知己知彼,才能旗开得胜,实际场景中的问题也能分析清楚并解决掉。

那么这些算法有哪些特点和适用场景,该从哪些方面考量?

分布式算法的四大维度

四大维度:拜占庭容错、一致性、性能、可用性。

这里我做了一个分布式算法四大维度的表格,大家可以对比下:

分布式算法的对比
分布式算法的对比

拜占庭容错

拜占庭容错就是《拜占庭将军问题》中提出的一个模型,该模型描述了一个完全不可信的场景。不可信体现在:

  • 故障行为。比如节点故障了。
  • 恶意行为。比如恶意节点冒充正常节点,发出错误指令。

拜占庭容错的另外一面就是非拜占庭容错,又叫故障容错,解决了分布式系统存在故障,但是不存在恶意节点共识的问题,譬如节点所在服务器硬件故障、节点的服务进程崩溃等。

非拜占庭容错算法

在可信的环境,只需要具有故障容错能力,譬如 2PC、TCC、Paxos算法、Raft 算法、Gossip 协议、Ouorum NWR 算法、ZAB 协议。

拜占庭容错算法

而在不可信的环境,需要具有拜占庭容错能力,报错 POW 算法、FBFT 算法。

一致性

一致性分为三种:

  • 强一致性:保证写操作完成后,任何后续访问都能读到更新后的值。
  • 弱一致性:写操作完成后,系统不能保证后续的访问都能读到更新后的值。
  • 最终一致性:保证如果对某个对象没有新的写操作,最终所有后续访问都能读到相同的最近更新的值。

在数据库操作层面,我们多使用二阶段提交协议(2PC)保证强一致性。在分布式系统中,多使用 Raft 算法来保证强一致性。如果考虑可用性,则使用 Gossip 协议实现最终一致性,配合 Quorum NWR 算法的三个参数来调节容错能力。而 zookeeper 基于读性能的考虑,通过 ZAB 协议提供最终一致性。

可用性

可用性表示能得到响应数据,但不保证数据最新,强调服务可用。前提条件:访问的是非故障节点。

可用性最强的就是 Gossip 协议了,即时只有一个节点,集群可以提供服务。然后是 Paxos/Raft/ZAB/Quorum NWR/FBFT/POW 算法,能够容忍部分节点故障。

而 2PC、TCC 要求所有节点都正常运行,系统才能正常工作,可用性最低。

性能

性能和可用性联系非常紧密,可用性越高,性能越强。

上面可用性的排序同样适用于性能维度。Gossip 协议可用于 AP 型分布式系统,水平扩展能力强,读写性能最强。

Paxos/Raft/ZAB/Quorum NWR/FBFT/POW 算法都是领导者模型,写性能依赖领导者,读性能依赖一致性的实现。性能处于中等位置。

而 2PC、TCC 实现事务时,需要预留和锁定资源,性能较差。

学习路线

第一讲:拜占庭将军问题

必须先把拜占庭将军问题弄懂,这篇我用三国杀卡牌游戏中的四种身份牌来讲解了拜占庭将军问题。

第二讲:CAP、BASE、ACID 理论

是针对 CAP、BASE、ACID 三大理论的讲解,文中我用太极拳中的来比喻 ACID 和 BASE,而如何平衡刚和柔就需要 CAP 理论了。

第三讲:Paxos 算法

为了更好地理解 Paxos 算法,我用三国演义中的诸葛亮庞统两种角色充当提议者对 Paxos 算法的细节进行了分析。

第四讲:Raft 算法

Raft 算法其实比较好理解,但是直接描述出来会让人云里雾里,所以我借助了动图,用动图模拟 Raft 算法的选举过程,轻松易懂。

第五讲:一致性哈希

这个也算作分布式算法中的一种,常用在负载均衡、路由寻址中。该算法理解起来不难,但比较枯燥,所以我用韩信点兵的故事来进行讲解,诙谐有趣。

第六讲:Gossip 协议

Gossip 的英文单词就是流言蜚语,具有传染性,所以我用一个传染性病毒的故事进行讲解,既可以学习分布式算法又可以了解病毒知识,一举两得。

第七讲:Quorum NWR

N、W、R 这三个参数,比较晦涩,为了让大家更容易理解,我用太上老君的炼丹炉比作节点,丹炉里面的药比作数据,用炼造过程来体现 NWR 这三个参数,更加形象化。

第八讲:POW 算法

在学习 POW 算法时,牵扯到区块链的知识,于是我就去看了一本区块链的书《区块链:从数字货币到信用社会》,一本科普书,对我了解区块链、比特币帮助很大。而区块链中用到的核心知识之一就是 POW 算法,也叫做工作量证明。我用紫霞仙子和至尊宝的故事对区块链、比特币、工作量证明进行了讲解,诙谐有趣。

对了,FBFT 和 ZAB 协议还没有给大家讲解,后续可能得过一段时间才能补上,因为有很多读者朋友在催更我的开源项目 PassJava,所以得去倒腾开源项目了。

另外我将这八篇内容整理成了一份 PDF 文档,总共三万字,在公众号后台回复:【分布式】三个字即可获取。

分布式算法 1.0
分布式算法 1.0
文中插图
文中插图
评论
  • 按正序
  • 按倒序
  • 按热度
Powered by Waline v3.3.0