《分布式协议与算法实战》笔记

分布式算法特点和适合场景

分布式算法的四度空间

拜占庭容错

拜占庭错误：描述了一个完全不可信的场景，除了存在故障行为，还存在恶意行为。

拜占庭容错（Byzantine Fault Tolerance，BFT），是指能容忍拜占庭错误，常见算法有： POW 算法、PBFT 算法。

故障容错（Crash Fault Tolerance，CFT），即非拜占庭容错，解决的是分布式系统中存在故障，但不存在恶意节点的共识问题，常见算法有：二阶段提交协议（2PC）、TCC（Try-Confirm-Cancel）、Paxos 算法、ZAB 协议、Raft 算法、Gossip 协议、Quorum NWR 算法。

一致性

一致性分为三类。

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

强一致性是具有多种含义的。CAP定理中的强一致性（也就是 C），可以是指 ACID 的 C，系统状态的一致性，这种一致性可以通过二阶段提交协议、TCC来实现。也可以指原子一致性（也就是线性一致性），Paxos、Raft 能实现线性一致性，而 ZooKeeper 基于读性能的考虑，它通过 ZAB 协议提供的是最终一致性。在可用性优先的系统，你可以采用 Gossip 协议来实现最终一致性，并实现 Quorum NWR 来提供强一致性。

可用性

分三层：

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

性能

与可用性一样，分三层：

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

CAP理论

不仅是知道 CAP 不可能三角，而是要能在 C 和 A 之间，根据实际场景特点，妥协权衡折中。

分布式事务

实现分布式事务，最常用的方法是二阶段提交协议和 TCC，这两个算法的适用场景是不同的。

二阶段提交协议实现的是数据层面的事务，比如MySQL XA 规范采用的就是二阶段提交协议；
TCC 实现的是业务层面的事务，比如当操作不仅仅是数据库操作，还涉及其他业务系统的访问操作时，这时就应该考虑 TCC 了。

分布式强一致性

共识（Consensus）和一致性（Consistency）是两个完全不同的概念。

共识：各节点就指定值（Value）达成共识，而且达成共识后的值，就不再改变了。Paxos 和 Raft 是共识算法。
一致性：是指写操作完成后，能否从各节点上读到最新写入的数据，如果立即能读到，就是强一致性，如果最终能读到，就是最终一致性。

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

一致哈希是常用的寻址算法，能突破集群性能的领导者限制，也是需要掌握的。

分布式最终一致性

Gossip 协议是实现最终一致性的常用方法。如果实现了最终一致性，但有时可能需要临时提供强一致性能力，这个时候，你可以用 Quorum NWR 来实现。