常见分布式协议和算法的说明和对比

常见分布式协议和算法的说明和对比

开发分布式系统最关键的就是根据场景特点，选择合适的算法，在一致性和可用性之间妥协折中，而妥协折中的关键就在于能否理解各算法的特点。

分布式一致性的背景

一致性的分类

我们讲分布式系统的一致性，一般来说，有如下几个分类：

• 强一致性。对一致性要求最高的，是强一致的，保证写操作完成后，任何后续访问都能读到更新后的值。。但是性能较弱，在互联网系统里面用的较少，但是在金融领域使用的较多。因为是同步的，因此性能会比较低。
• 弱一致性。写操作完成后，系统不能保证后续的访问都能读到更新后的值。
• 最终一致性。是弱一致性的一个特定形式，如果对某个对象没有新的写操作了，最终所有后续访问都能读到相同的最近更新的值，但是是在最终某个时间点才能保证。弱一致性（最终一致性）都是异步的，因此性能会比较好。

一般而言，在需要系统状态的一致性时，你可以考虑采用二阶段提交协议、TCC。在需要数据访问是的强一致性时，你可考虑 Raft 算法。在可用性优先的系统，你可以采用 Gossip 协议来实现最终一致性，并实现 Quorum NWR 来提供强一致性。

如何理解分布式一致性

设计分布式系统的两大初衷：横向扩展（scalability）和高可用性（availability），横向扩展的目的也是为了解决单点问题从而保障可用性，因此分布式系统的核心诉求也就是可用性，为了保证可用性，一个分布式系统通常由多个节点组成，而这些节点各自维护一份数据，因此我们需要能够保证每个节点上的数据都是相同的，也就是要保证一致性，这就是我们所说的分布式一致性，他通过给定的一系列操作，在协议（共识算法）的保障下，试图使得它们对处理结果达成某种程度的一致。

分布式系统的核心问题

前面说到，分布式一致性，是通过给定的一系列操作，在协议（共识算法）的保障下，试图使得它们对处理结果达成某种程度的一致。这里，也就是整个分布式系统的核心问题，怎么保证多个节点间的数据是一致的，这就需要我们对分布式协议（共识算法）要能够有比较深刻的理解，然后才能很好的解决分布式数据的一致性，掌握分布式协议（共识算法）也是你面试架构师、技术专家等高端岗位时的敲门砖。

拜占庭容错 和 非拜占庭容错

拜占庭错误是一个错误模型，描述了一个完全不可信的场景，除了存在故障行为，还存在恶意行为。拜占庭容错（Byzantine Fault Tolerance，BFT），就是指能容忍拜占庭错误了。拜占庭容错是分布式领域最复杂的容错模型，是你必须要了解的。在一个完全不可信的环境中（比如有人作恶），如果需要达成共识，那么我们就必须考虑拜占庭容错算法，常用的拜占庭容错算法有 POW 算法、PBFT 算法，它们在区块链中应用广泛。从概率角度，PBFT 系列算法是确定的，一旦达成共识就不可逆转；而 PoW 系列算法则是不确定的，随着时间推移，被推翻的概率越来越小。

而非拜占庭容错，又叫故障容错（Crash Fault Tolerance，CFT），解决的是分布式系统中存在故障，但不存在恶意节点的共识问题。实际上，这种故障是非常场景的，比如进程奔溃、服务器硬件故障、网络中断、响应延迟等等。针对非拜占庭错误的解决方案，业界一般采用 Paxos、Raft 及其各种变种的协议。

共识 vs 一致性

共识算法解决的是对某个提案（Proposal）让大家都达成一致意见的过程，而这个提案可以认为任何需要达成一致的信息都是一个提案，如多个事件发生的顺序、某个键对应的值等等。在实践中，一致性的结果还需要客户端的支持，比如通过访问足够多个服务节点来验证确保获取共识后结果。

但是由于分布式系统会存在各种非拜占庭容错，因此要达成共识就比较困难，需要一些共识算法来解决。这里需要注意，共识（Consensus）和一致性（Consistency）是两个完全不同的概念。共识是指各节点就指定值（Value）达成共识，而且达成共识后的值，就不再改变了。一致性是指写操作完成后，能否从各节点上读到最新写入的数据，如果立即能读到，就是强一致性，如果最终能读到，就是最终一致性。

提到共识算法，Paxos 是一个必须要提及的话题，而且 ZAB 协议、Raft 算法都可以看作是 Paxos 变种，Paxos 和 Raft 是共识算法。所以，你需要了解 Paxos 算法。但因为 Paxos 算法的可理解性和可编程性痛点突出，所以在实际场景中，最常的共识算法是 Raft，我们可以基于 Raft 实现强一致性系统，Raft 是需要彻底掌握的。

8 条荒谬的分布式假设

Fallacies of Distributed Computing 是英文维基百科上的一篇文章，讲的是刚刚进入分布式计算领域的程序员常会有的 8 条假定，随着时间的推移，每一条都会被证明是错误的，也都会导致严重的问题，以及痛苦的学习体验：

• 网络是稳定的。
• 网络传输的延迟是零。
• 网络的带宽是无穷大。
• 网络是安全的。
• 网络的拓扑不会改变。
• 只有一个系统管理员。
• 传输数据的成本为零。
• 整个网络是同构的。

为什么我们要深刻地认识这 8 个错误？是因为，这要我们清楚地认识到，在分布式系统中错误是不可能避免的，我们能做的不是避免错误，而是要把错误的处理当成功能写在代码中。这 8 个需要避免的错误不仅对于中间件和底层系统开发者及架构师是重要的知识，而且对于网络应用程序开发者也同样重要。分布式系统的其他部分，如容错、备份、分片、微服务等也许可以对应用程序开发者部分透明，但这 8 点则是应用程序开发者也必须知道的。

常见分布式算法的对比

从拜占庭容错、一致性、性能和可用性四个纬度来分析如下（来自极客时间-韩健-分布式协议与算法实战）：

 

一般而言，在可信环境（比如企业内网）中，系统具有故障容错能力就可以了，常见的算法有二阶段提交协议（2PC）、TCC（Try-Confirm-Cancel）、Paxos 算法、ZAB 协议、Raft 算法、Gossip 协议、Quorum NWR 算法。而在不可信的环境（比如有人做恶）中，这时系统需要具备拜占庭容错能力，常见的拜占庭容错算法有 POW 算法、PBFT 算法。

采用 Gossip 协议实现的最终一致性系统的可用性是最高的，因为哪怕只有一个节点，集群还能在运行并提供服务。其次是 Paxos 算法、ZAB 协议、Raft 算法、Quorum NWR 算法、PBFT 算法、POW 算法，它们能容忍一定数节点故障。最后是二阶段提交协议、TCC，只有当所有节点都在运行时，才能工作，可用性最低。

采用 Gossip 协议的 AP 型分布式系统，具备水平扩展能力，读写性能是最高的。其次是 Paxos 算法、ZAB 协议、Raft 算法，因为它们都是领导者模型，写性能受限于领导者，读性能取决于一致性实现。最后是二阶段提交协议和 TCC，因为在实现事务时，需要预留和锁定资源，性能相对低。

2PC【强一致性】

两阶段提交（2PC，Two-phase Commit Protocol）是非常经典的强一致性协议，在各种事务和一致性的解决方案中，都能看到两阶段提交的应用，二阶段提交协议，不仅仅是协议，也是一种非常经典的思想。2PC 的流程就是第一阶段做投票，第二阶段做决定的一个算法。

二阶段提交在达成提交操作共识的算法中应用广泛，比如 XA 协议、TCC、Paxos、Raft 等。Paxos、Raft 等强一致性算法，也采用了二阶段提交操作，在“提交请求阶段”，只要大多数节点确认就可以，而具有 ACID 特性的事务，则要求全部节点确认可以。所以可以将具有 ACID 特性的操作，理解为最强的一致性。

三阶段提交协议（3PC，Three-phase_commit_protocol）是在 2PC 之上扩展的提交协议，主要是为了解决两阶段提交协议的阻塞问题，从原来的两个阶段扩展为三个阶段，增加了超时机制。但目前两阶段提交、三阶段提交存在如下的局限性，并不适合在微服务架构体系下使用：

• 所有的操作必须是事务性资源（比如数据库、消息队列），存在使用局限性
• 由于是强一致性，资源需要在事务内部等待，性能影响较大，吞吐率不高，不适合高并发与高性能的业务场景；

Paxos【强一致性】

Paxos 算法基本上来说是个民主选举的算法——大多数的决定会成个整个集群的统一决定。任何一个点都可以提出要修改某个数据的提案，是否通过这个提案取决于这个集群中是否有超过半数的结点同意（所以Paxos算法需要集群中的结点是单数）。兰伯特提出的 Paxos 算法包含 2 个部分：

• 一个是 Basic Paxos 算法，描述的是多节点之间如何就某个值（提案 Value）达成共识；
• 另一个是 Multi-Paxos 思想，描述的是执行多个 Basic Paxos 实例就一系列值达成共识。Basic Paxos 是 Multi-Paxos 思想的核心。

Raft【强一致性】

Raft 算法是 Paxos 算法的一种简化实现，其实 Raft 不是一致性算法而是共识算法，是一个 Multi-Paxos 算法，实现的是如何就一系列值达成共识。Raft 算法是在兰伯特 Multi-Paxos 思想的基础上，做了一些简化和限制，比如增加了日志必须是连续的，只支持领导者、跟随者和候选人三种状态，在理解和算法实现上都相对容易许多。

ZAB【最终一致性】

ZAB 协议和 ZooKeeper 代码耦合在一起了，无法单独使用 ZAB 协议，所以一般而言，只需要理解 ZAB 协议的架构和基础原理就可以了。

TCC【最终一致性】

TCC 是一个分布式事务的处理模型，将事务过程拆分为 Try、Confirm、Cancel 三个步骤，在保证强一致性的同时，最大限度提高系统的可伸缩性与可用性，又被称补偿事务。它的核心思想是针对每个操作都要注册一个与其对应的确认操作和补偿操作（也就是撤销操作）

二阶段提交协议实现的是数据层面的事务，比如 XA 规范采用的就是二阶段提交协议；TCC 实现的是业务层面的事务，TCC 可以理解为是一个业务层面的协议，可以当做为一个编程模型来看待，因此这个的应用还是非常广泛的。，TCC 的 3 个操作是需要在业务代码中编码实现的，为了实现一致性，确认操作和补偿操作必须是等幂的，因为这 2 个操作可能会失败重试。

TCC 不依赖于数据库的事务，而是在业务中实现了分布式事务，这样能减轻数据库的压力，但对业务代码的入侵性也更强，实现的复杂度也更高。所以，推荐在需要分布式事务能力时，优先考虑现成的事务型数据库（比如 MySQL XA），当现有的事务型数据库不能满足业务的需求时，再考虑基于 TCC 实现分布式事务。

Gossip【最终一致性】

Gossip 协议利用一种随机、带有传染性的方式，将信息传播到整个网络中，并在一定时间内，使得系统内的所有节点数据一致。掌握这个协议不仅能很好地理解这种最常用的，实现最终一致性的算法，也能在后续工作中得心应手地实现数据的最终一致性。

Gossip 主要通过三个步骤：直接邮寄（Direct Mail）、反熵（Anti-entropy）和谣言传播（Rumor mongering） 来实现最终一致性。实现数据副本的最终一致性时，一般而言，直接邮寄的方式是一定要实现的。在节点都是已知的情况下，一般采用反熵修复数据副本的一致性。当集群节点是变化的，或者集群节点数比较多时，这时要采用谣言传播的方式来实现最终一致。

Quorum NWR【最终一致性】

Quorum NWR 算法非常实用，能有效弥补 AP 型系统缺乏强一致性的痛点，给业务提供了按需选择一致性级别的灵活度。实际应用中，一般的 AP 型分布式系统中（比如 Dynamo、Cassandra、InfluxDB 企业版的 DATA 节点集群）都会实现 Quorum NWR 的功能。掌握 Quorum NWR，不仅是掌握一种常用的实现一致性的方法，同时可以根据业务的特点来灵活地指定一致性级别。

N、W、R 值的不同组合，会产生不同的一致性效果：

• 当 W + R > N 的时候，对于客户端来讲，整个系统能保证强一致性，一定能返回更新后的那份数据。
• 当 W + R <= N 的时候，对于客户端来讲，整个系统只能保证最终一致性，可能会返回旧数据。

如何设置 N、W、R 值，取决于我们想优化哪方面的性能。比如，N 决定了副本的冗余备份能力；如果设置 W = N，读性能比较好；如果设置 R = N，写性能比较好；如果设置 W = (N + 1) / 2、R = (N + 1) / 2，容错能力比较好，能容忍少数节点（也就是 (N - 1) / 2）的故障。

POW【拜占庭容错】

区块链中有此应用

PBFT【拜占庭容错】

区块链中有此应用

本文转载自微信公众号「 后端系统和架构」