概述

[TOC]

分布式系统里，最重要的事情，就是如何选择或设计适合的算法，解决一致性和可用性相关的问题了。

掌握分布式算法也是你面试架构师、技术专家等高端岗位时的敲门砖。

要想掌握这部分内容，不仅要理解常用算法的原理、特点和局限，还要能根据场景特点选择适合的分布式算法。

如何高效地学习和掌握分布式算法？，开发分布式系统最关键的就是根据场景特点，选择合适的算法，在一致性和可用性之间妥协折中，而妥协折中的关键就在于能否理解各算法的特点。首先要弄清楚每个算法的特点是什么，适合怎样的场景。

分布式算法的四度空间

从拜占庭容错、一致性、性能和可用性四个纬度

	拜占庭容错	一致性	性能	可用性
2PC	否	强一致性	低	低
TCC	否	最终一致性	低	低
Paxos	否	强一致性	中	中
2AB	否	最终一致性	中	中
Raft	否	强一致性	中	中
Gossip	否	最终一致性	高	高
Quorum NWR	否	强一致性	中	中
PBFT	是	N/A	低	中
POW	是	N/A	低	中

拜占庭容错

拜占庭错误描述了一个完全不可信的场景，除了存在故障行为。拜占庭容错（Byzantine Fault Tolerance，BFT），就是指能容忍拜占庭错误。

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

拜占庭容错是分布式领域最复杂的容错模型。

一致性

一致性，从弱到强可以分为：

最终一致性，经过一段时间达到一致性的弱一致性。
因果一致性（Casual Consistency），弱一致性，只对有因果关系的事件有一致性要求。
顺序一致性（Sequential Consistency），属于强一致性
线性一致性，也叫原子一致性，属于强一致性

线性一致性：也叫原子一致性，要求最严格的一致性，通常，CAP， ACID 中的 C 都属于这类一致性。它要求

任何一次读都能读到某个数据的最近一次写的数据。
系统中的所有进程，看到的操作顺序，都和全局时钟下的顺序一致。

顺序一致性：与线性一致性相比，少了全局时钟下的顺序一致要求。但是要求所有系统进程的顺序一致。所有进程读到的顺序都一样，要么一起对，要么一起错。如进程1 先后写入数据A和B，其他所有进程读到这两个数据的顺序都一致，要么都是先A后B，要么都是先B后A，这里的一致性不保证正确性。

Write(x, 4) 表示写入x=4 ,Read(x, 2)表示读出x=2；

P1，P2 代表进程1，进程2； x, y 初始值为 0；

# 场景一：满足顺序一致性，但不满足线性一致性
P1  ------Write(x, 5)-------Read(y, 3)--
P2  --Write(y,3)-----Read(x,0)----------


# 场景二：满足顺序一致性，也满足线性一致性
P1  ------Write(x, 5)-------Read(y, 3)--
P2  --Write(y,3)-----Read(x,5)----------


# 场景三：不满足顺序一致性，更不满足线性一致性
P1  ------Write(x, 5)-------Read(y, 0)--
P2  --Write(y,3)-----Read(x,0)----------

# 场景四：不满足顺序一致性
P1  ------Write(x, 5)-------------------
P2  --Write(x,3)------------------------
P3  ------------------Read(x,3)-----Read(x,5)----
P3  ------------------Read(x,5)----Read(x,3)-----

场景一：从全局时钟的观点来看，P2进程对变量X的读操作在P1进程对变量X的写操作之后，然而读出来的却是旧的数据，所以不满足线性一致性。

从P1，对角度看顺序是： Write(y,3)，Read(x,0)，Write(y,5)，Read(x,3)；这个顺序用做P2到角度也是合理的。

场景二：满足全局时钟顺序一致。

场景三：从P2到角度是顺序是：Write(y,3)，Read(x,0)，Write(x,5)，Read(y,0)；但是从P1到角度，Read(y,0) 读取 y 的值是0，应该在 Write(y,3) 操作之前，这与前面的并不一致。

因果一致性

对有因果关系的事件有一致性要求。比如一些社交软件朋友圈功能就利用了因果一致性。

比如有三条动态，“我家狗丢了”，“晚上狗自己回家了”，“太好啦”。如果这三条动态没满足因果一致性，可能变成：“我家狗丢了”，“太好啦”…..“晚上狗自己回家了”。

因果一致性既满足了事情的因果依赖关系，有没有像强一致性那样的高开销。

最终一致性

属于弱一致性，也是应用最广泛的。即不保证在任意时刻任意节点上的同一份数据都是相同的，但是随着时间的迁移，不同节点上的同一份数据总是在向趋同的方向变化。

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

可用性

可用性说的是任何来自客户端的请求，不管访问哪个非故障节点，都能得到响应数据，但不保证是同一份最新数据，可用性强调的是服务可用。

一般来讲，采用 Gossip 协议实现最终一致性系统，它的可用性是最高的，因为哪怕只有一个节点，集群还能在运行并提供服务。

其次是 Paxos 算法、ZAB 协议、Raft 算法、Quorum NWR 算法、PBFT 算法、POW 算法，它们能容忍一定数节点故障。

最后是二阶段提交协议、TCC，只有当所有节点都在运行时，才能工作，可用性最低。

性能

采用 Gossip 协议的 AP 型分布式系统，具备水平扩展能力，读写性能是最高的。

其次是 Paxos 算法、ZAB 协议、Raft 算法，因为它们都是领导者模型，写性能受限于领导者，读性能取决于一致性实现。

二阶段提交协议和 TCC，因为在实现事务时，需要预留和锁定资源，性能相对低。

实现分布式事务，最常用的方法是二阶段提交协议和 TCC，这两个算法的适用场景是不同的，二阶段提交协议实现的是数据层面的事务，比如 XA 规范采用的就是二阶段提交协议；TCC 实现的是业务层面的事务，比如当操作不仅仅是数据库操作，还涉及其他业务系统的访问操作时，这时就应该考虑 TCC 了。

Gossip 协议是实现最终一致性的常用方法。

在一个完全不可信的环境中（比如有人作恶），如果需要达成共识，那么就必须考虑拜占庭容错算法，常用的拜占庭容错算法有 POW 算法、PBFT 算法，它们在区块链中应用广泛。

ZooKeeper 基于读性能的考虑，它通过 ZAB 协议提供的是最终一致性。

常用算法概述

Paxos

1989 年莱斯利·兰伯特（Leslie Lamport）提出了 Paxos，2006 年，谷歌研发团队让 Paxos 在生产环境中落地，但是 Paxos 缺乏编程实现的必须细节，最终的算法实现仍是建立在一个未证明的算法之上。

Raft

2013，斯坦福大学的迭戈·安加罗（Diego Ongaro）和约翰·奥斯特霍德（John Ousterhout）提出了 Raft，但是 2016 年，Raft 仍在解决成员变更的 Bug。

分布式算法的四度空间

拜占庭容错

一致性

可用性

性能

常用算法概述

Paxos

Raft

推荐阅读