# Protocol & Algorithm
## 大纲
对于一个分布式算法，我们常从拜占庭容错、一致性、性能、可用性四个角度来分析。
### 拜占庭容错
描述一个不可信场景，除了存在故障，还存在恶意行为。
大部分环境（企业内网）是可信的，系统具有故障容错能力就行了。
在不可信环境中，常见的拜占庭容错算法有 POW、PBFT 等。
### 一致性
* 强一致性(Strong consistency)：写操作完成后，任何后续的读操作都能读到更新后的值。包括：
* 线性一致性(Linearizability consistency)、原子一致性：CAP 中的 C 即指这个，如 ZK 的写操作，etcd 的读写都是。
* 顺序一致性(Sequential consistency)：如 ZK 的整体（read+write）
* 弱一致性(Weak consistency)：写操作完成后，不能保证后续读操作能读到最新的值。包括：
* 因果一致性(Causal consistency)
* 最终一致性(Eventual consitency)：若某个对象没有写操作了，最终所有后续的读操作都能读到最新的值。
一致性的定义在不同理论中有不同的意义，很容易混淆，待补充。可以参考：
*
*
### 可用性
Gossip 只有一个节点也能提供服务；Paxos、ZAB、Raft、Quorum NWR、PBFT、POW 能容忍一定数量的节点故障；2PC、TCC 只有所有节点都健康时才能运行。
### 性能
Gossip 是 AP 系统，性能最高；Paxos、ZAB、Raft 都是领导者模型，写性能受限于领导者，读性能取决于一致性实现；2PC、TCC 需要预留和锁定资源，性能较低。
## 拜占庭将军问题
描述的是最复杂的分布式故障场景，除了存在故障行为，还存在恶意行为。常用的算法有 PBFT 算法和 PoW 算法。
可以通过 2 忠 1 叛来举例。
### 口信消息型
兰伯特论文中 [The Byzantine Generals Problem](https://www.microsoft.com/en-us/research/publication/byzantine-generals-problem/) 提到解法。
算法前提：叛将人数 m 是已知的。而且需要 m+1 轮递归循环。
算法结论：若叛将人数为 m，则总将军数不能少于 3m + 1。
所以 2 忠 1 叛问题，必须再增加一名忠将才能解决。
### 签名消息型
消息特性：
* 消息无法伪造，且对消息的任何更改都能被发现。
* 所有人都能验证消息的真伪。
基于上述特性，兰伯特论文提到，任何伪造消息都能被发现，且无论多少忠将多少叛将，忠将总能达成一致的作战消息，即 n 位将军能容忍 n-2 位叛将。也需要 m+1 轮协商。此问题是解决忠将如何达成共识的问题，不关心共识是什么，比较理论化。
{% hint style="info" %}
消息签名一般通过非对称加密方式实现。比如 A 向 B 发送消息，A 存有私钥，B 存有公钥。A 把消息计算 hash 值(MD5)，再通过私钥加密，把消息和加密的 hash 都发送过去，B 通过公钥解密 hash，同时也计算消息的 hash，比较两个 hash 值即可。
{% endhint %}
## CAP 理论
对分布式系统特性做了高度抽象，即一致性、可用性、分区容错性，并对特性间的冲突做了总结，让我们在数据一致性（ACID）和服务可用性（BASE）之间权衡。
### 一致性（Consistency）
客户端每次读操作，不管访问哪个节点，要么读到的都是同一份最新写入的数据，要么失败。
可以认为是分布式系统对访问自己客户端的一种承诺：不管你访问我的哪个节点，我给你返回的是绝对一致的最新写入的数据，要么你读取失败。
### 可用性（Availability）
客户端不管访问哪个非故障节点，都能得到响应数据，但不保证是同一份最新数据。
{% hint style="success" %}
我认为是同时保证读写的可用性，如果仅保证读或写中的一者，那么既可以保证一者的 A 又可以保证 C。
{% endhint %}
### 分区容错性（Partition Tolerance）
当节点间出现任意数量的消息丢失或高延迟的时候，系统仍能继续工作。
分布式系统中分区容错性是必须支持的。
### 分析
论文《[Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web services](https://dl.acm.org/doi/10.1145/564585.564601)》证明三个指标不可兼得，只能选两个。注意论文中设定一致性定义为原子一致性。
* 当选择 CP 系统时，若系统节点间发生网络故障，为了不破坏一致性，系统可能无法响应客户端的读请求。
* 当选择 AP 系统时，若系统节点间发生网络故障，系统将始终处理客户端的查询，只是一些节点无法返回最新数据。
* CA 模型，舍弃了分布式，如单机版的 MySQL。
{% hint style="success" %}
对于 CP 系统，我认为有办法保证读的 C、A。即当 P 发生时，让写操作失败，这样任何节点收到读请求都能响应(保证 A)，并返回最新的写入成功的数据(保证 C)。
{% endhint %}
{% hint style="warning" %}
很多人对 CAP 有**误解**：无论在什么情况下，分布式系统只能在 C、A 中选一个。
当不存在网络分区时（系统大部分时间所处的状态），即不需要 P 时，C、A 能够同时保证。
{% endhint %}
对于 InfluxDB 的集群版本，Meta 集群采用 CP 系统设计，Data 集群采用 AP 系统设计。
{% hint style="info" %}
* 可以把 ACID 理解为 CAP 理论中 CP 系统的对一致性的要求。
* 可以把 BASE 理解为 CAP 理论中 AP 系统的延伸。
{% endhint %}
## ACID
ACID 理论是对事务特性的抽象和总结。可以理解为无论是单机系统还是分布式系统，只要实现了操作的 ACID 特性，那么这个系统就实现了事务。
* Atomicity：原子性，进行数据处理操作的基本单位，不可分割。一个事务有多个操作，要不全部执行成功，要不全部没执行（涉及回滚操作）。
* Consistency：一致性，数据库在进行事务操作后，会由原来的一致状态，变成另外一种一致状态。一致性一般由**业务定义**的。这里的 C 是强一致性，但是分布式系统中实现较难，所以出现了 BASE 理论。
* Isolation：隔离性，事务不受其它事务影响。
* Durability：持久性，事务提交之后对数据的修改是持久性的。
单机事务的原理、实现等相关介绍见[ MySQL 一章](https://yunzhao.gitbook.io/notes/database/mysql/transaction)。分布式事务的实现、算法见[分布式事务一章](https://yunzhao.gitbook.io/notes/computer-science/distributed-system/transcation)。
## BASE
CP 系统的可用性为系统中所有节点可用性的乘积，节点越多，可用性也就越低，所以尽量选用 AP 系统。
BASE 理论是对 CAP 理论中一致性和可用性权衡的结果，是基于 CAP 演化而来，它的核心是**基本可用**（Basically Available）和**最终一致**（Eventually Consistent）。
{% hint style="info" %}
软状态（Soft State）描述的是实现服务可用性时数据的一种过渡状态，即不同节点间，数据副本存在短暂的不一致。
{% endhint %}
### 基本可用
当分布式系统出现不可预知的故障时，允许损失部分功能的可用性，保障核心功能的可用性。
基本可用的本质是妥协，通常实现基本可用的方式有：**流量削峰**、**延迟响应**、**体验降级**、**过载保护**。
### 最终一致
系统中所有的数据副本在经过一段时间的同步后，最终能达到一个一致的状态，即在数据一致上，有一个短暂的延迟。
大部分互联网系统都采用最终一致，只有实在无法用最终一致时才会使用强一致，如觉得系统运行的敏感元数据采用强一致，支付或金融数据采用事务。
可以把强一致理解为不存在延迟的最终一致。
决定最终一致的数据准则一般有两种方式：
* 最新写入的数据。
* 第一次写入的数据。
实现最终一致的方式一般有：
* 读时修复：如 Cassandra 的 Read Repair。需要尽可能优化数据一致性对比算法。
* 写时修复：如 Hinted-Handoff。不需要做数据对比，性能较好，优先使用这种方式。
* 异步修复：定时对账检测。需要尽可能优化数据一致性对比算法。
{% hint style="info" %}
在实现最终一致时，推荐定义写的一致性级别，让用户自主选择， 如 All、Quorum、One、Any。
{% endhint %}
## Basic Paxos
三种角色：
* 提议者（Proposer）：集群中收到客户端请求的节点。
* 接受者（Acceptor）：对每个提议的值进行投票，并存储接受的值。
* 学习者（Learner）：被告知投票的结果，接受达成共识的值，存储保存。
> 一般集群中的节点承担多个角色，如 proposer & acceptor。如 3 个节点的集群，节点 3 接受客户端的请求，作为 proposer，这个节点和另外两个节点一起作为 acceptor。