2万字 | 写了八篇分布式算法，我“悟空”了-技术圈

这是悟空的第 86 篇原创文章

作者 | 悟空聊架构

来源 | 悟空聊架构（ID：PassJava666）

转载请联系授权（微信ID：PassJava）

本文主要内容：

最近三个月更新了 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 协议提供最终一致性。