# 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。
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://yunzhao.gitbook.io/notes/computer-science/distributed-system/protocol-and-algorithm.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.