分布式的一些基本概念笔记
分布式计算的经典谬误
- 网络是可靠的
- 延迟为0
- 带宽是无限的
- 网络是安全的
- 拓扑不会改变
- 有一个管理员
- 运输成本为0
- 网络是同构的
- 编写软件应用程序时，对网络错误进行很少的错误处理。在网络中断期间，此类应用程序可能会停止或无限等待应答数据包，从而永久消耗内存或其他资源。当失败的网络可用时，这些应用程序也可能无法重试任何停止的作或需要（手动）重启。
- 由于无视网络延迟及其可能导致的数据包丢失，应用程序层和传输层开发人员允许无限流量，从而大大增加丢弃的数据包并浪费带宽。
- 流量发送方对带宽限制的无知可能会导致瓶颈。
- 对网络安全的自满导致被不断适应安全措施的恶意用户和程序所蒙蔽。
- 网络拓扑的更改可能会对带宽和延迟问题产生影响，因此可能会出现类似的问题。
- 与竞争对手公司的子网一样，多个管理员可能会制定相互冲突的策略，规定网络流量的发送方必须了解哪些策略才能完成其所需的路径。
- 构建和维护网络或子网的“隐性”成本是不可忽视的，因此必须在预算中注明，以避免巨大的缺口。
- 如果一个系统假设一个同构网络，那么它可能会导致与前三个谬误相同的问题。
分布式系统时间模型
同步模型Synchronous
- 定义：所有消息的传递延迟和进程的执行速度都有严格的上界（即已知最大延迟）。
特点
- 消息一定会在某个固定时间（如 Δ 时间单位）内到达。
- 进程的每一步操作都在确定的时间内完成。
- 系统行为完全可预测。
- 优点：算法设计简单（例如，超时机制容易实现）。
- 缺点：现实中的网络很难满足严格的时间约束，容错性差。
- 典型应用：同步共识算法（如拜占庭容错中的同步协议）。
部分同步模型Partially Synchronous
- 定义：系统在某些时段满足同步假设（消息延迟和进程速度有界），但界限是未知的或仅在运行期间某个时间点后生效。
特点
- 可能存在初始阶段的异步行为（例如，网络延迟无界），但最终会稳定为同步。
- 更贴近现实网络（如互联网可能临时拥塞，但最终恢复）。
- 优点：平衡了现实可行性和算法可解性，是许多经典分布式算法（如 Paxos、Raft）的基础。
- 典型场景：共识算法、分布式数据库复制。
异步模型（Asynchronous）
- 定义：无任何时间约束——消息延迟和进程执行速度可能无限长，甚至可能丢失消息。
特点
- 无法假设消息何时到达或进程何时响应。
- 算法不能依赖超时机制（因为无法区分“进程崩溃”和“延迟高”）。
- 挑战：著名的 FLP 不可能定理证明，在纯异步模型中，即使只有一个进程崩溃，也无法实现确定性共识。
- 应对方法：通过随机化算法（如 Ben-Or 算法）或弱一致性妥协（如最终一致性）。
FLP不可能性
异步系统的挑战：在完全异步的分布式系统中，由于没有时间假设（如消息延迟，时钟漂移等），确定公式和原子广播问题是不可能的（Fischer-Lynch-Paterson不可能结果）。换句话说，在异步模型下，共识问题无解。
论文：Impossibility of Distributed Consensus With One Faulty Process
在异步模型中（无时钟或超时假设），无法可靠区分节点崩溃、网络延迟或分区，因为任何消息延迟都可能由网络或节点故障引起。
欧节点A未收到节点B响应可能是：
- B已崩溃（掉线）。
- B繁忙（长忙）。
- 网络分区阻断了通信。
handra-Toueg的论文《Unreliable Failure Detectors for Reliable Distributed Systems》引入了不可靠检测器。将故障检测的不可靠性建模为系统的一部分，从而在异步模型中实现确定性方案。在异步系统中，任何故障检测器本质上都是不可靠的。可能将慢节点误判为崩溃（或反之）。他们形式化了故障检测器的强弱分类。研究者通过放宽条件（如允许暂时误判）来设计使用的故障检测器。强弱分类的本质是在系统可用性和正确性之间的权衡。
handra-Toueg提出了以下经典分类
完美故障检测器P
强完备性+强准确性，永不误判，且能检测所有故障（理论上只能在同步系统中实现）。
- 在异步系统中无法实现
最终弱故障检测器◊P
强完备性+弱准确性
特点：最终所有故障会被检测到（强完备性）。在某个时间点后，只少一个正常节点不再被误判（弱准确性）。
◊P 是异步系统中能实现的最强故障检测器，可用于解决共识问题（如 Paxos 隐含依赖此类检测器）。◊P是实现共识最低的要求。
弱故障检测器 w
弱完备性+弱准确性
特点：只少一个故障最终会被检测到，只少一个正常节点不被误判。
适合用于部分容错场景，但无法直接解决共识问题.
不可靠故障检测器（如s）
仅满足完备性，无准确性保证。
| 场景 | 完美检测器（P） | 最终弱检测器（◊P） | 弱检测器（W） |
|---|---|---|---|
| 节点A实际崩溃 | 立即检测到 | 最终检测到 | 可能检测到 |
| 节点B因网络延迟无响应 | 永不误判 | 可能误判，但最终恢复 | 可能误判 |
| 能否解决共识问题 | 能（同步模型） | 能（异步模型） | 不能 |
bully算法
bully算法是一种经典的分布式系统leader election算法，用于在多个节点中动态选出一个leader，尤其是节点故障时快速恢复集群一致性。
其核心思想是谁ID大谁当leader，通过节点之间的竞争决定主节点。
场景假设
- 集群有多个节点（如节点A、B、C，ID分别为1、2、3）。
- 当前Leader（节点3）突然故障，其他节点需选举新Leader。
步骤
- 故障检测
节点通过心跳超时（如未收到Leader响应）发现Leader失效。 发起选举
- 检测到故障的节点（如节点2）向所有ID比自己大的节点发送
Election消息（例如节点2会通知节点3）。 - 若无人响应（如节点3已宕机），节点2认为自己可能是Leader。
- 检测到故障的节点（如节点2）向所有ID比自己大的节点发送
应答竞争
- 若ID更大的节点（如节点3）存活，它会响应
Alive消息，并接管选举（节点3向更高ID节点发起选举）。 - 若无更高ID节点响应，发起选举的节点（节点2）宣布自己为Leader。
- 若ID更大的节点（如节点3）存活，它会响应
- 宣布Leader
胜出的节点向所有节点广播Leader消息，通知集群新Leader身份。
原子广播
atomic broadcast
原子广播要求所有节点以相同的顺序接受相同的消息集合，要么消息被所有节点成功传递，要么不被任何节点接受（原子性）。
- 全序性（Total Order）：所有节点对消息的顺序达成一致。
- 可靠性（Reliability）：消息不会丢失，最终会被所有存活节点接收。
- 原子性（Atomicity）：要么所有节点收到消息，要么都收不到（无部分传递）。
实现原子广播需要共识协议来确保消息的全序性。论文《unreliable failure detectors for reliable distributed system》证明了这俩者是一样难的。（你只需知道这是真的）。
共识一般不可能在小于2轮的消息中解决。
你现在知道了为什么ZAB协议全名叫做Zookeeper Atomic Broadcast了。
尾部延迟
在大规模分布式系统（如Google搜索）中，即使单个组件出现罕见的高延迟事件（如1%的请求变慢），也会因并行化请求处理的架构设计导致整体服务延迟显著恶化。例如：
当用户请求需要同时访问100台服务器时，单台服务器99%延迟为10ms、1%延迟为1秒的情况下，63%的用户请求会因等待最慢的服务器而超过1秒
- 系统设计因素
- 资源共享：CPU缓存、网络带宽等竞争
- 后台任务：垃圾回收、日志压缩等周期性活动
- 队列堆积：多层队列放大延迟波动
- 硬件趋势
- 功耗管理：CPU动态降频（如Intel Turbo Boost）
- 固态存储：垃圾回收导致读取延迟激增100倍
- 节能模式：设备唤醒延迟
可能有帮助的论文
- The Tail At Scale
- RAMCloud 存储系统 |计算机系统上的 ACM 事务
- PNUTS: Yahoo!'s hosted data serving platform: Proceedings of the VLDB Endowment: Vol 1, No 2
- Azure Data Lake Store | Proceedings of the 2017 ACM International Conference on Management of Data
- Omega
模型检查和形式化验证
formal verification
指通过数学方法（如逻辑、自动机理论）严格证明系统（硬件、软件）是否满足规约（Specification）的所有可能行为。
涵盖所有形式化技术，包括模型检查、定理证明（Theorem Proving）、抽象解释（Abstract Interpretation）等。
model checking
形式化验证的一种具体方法，通过穷举搜索系统的有限状态空间，自动验证其是否满足特定性质（如安全性、活性）。
属于形式化验证的子集，专指基于状态空间遍历的自动化验证技术。
| 维度 | 模型检查 | 形式化验证 |
|---|---|---|
| 方法 | 自动化遍历有限状态模型 | 可能结合自动化或人工证明（如定理证明） |
| 适用范围 | 适用于有限状态系统（或抽象后的模型） | 可处理无限状态系统（如通过数学归纳） |
| 工具示例 | SPIN、NuSMV、TLA+ | IVy，Coq（定理证明）、Z3（SMT求解器） |
| 规约语言 | 时序逻辑（LTL、CTL） | 多种逻辑（一阶逻辑、高阶逻辑等） |
| 可扩展性 | 受限于状态爆炸问题 | 定理证明可处理更复杂系统，但需人工指导 |
- 模型检查是全自动的，适合验证特定性质（如“死锁不存在”），但需模型简化（如抽象）以应对状态爆炸。
- 形式化验证中的定理证明等方法依赖人工，可验证更复杂的数学性质（如算法正确性），但需要专家介入。
- 模型检查的结果仅针对给定模型，若模型与真实系统不一致，结论可能无效。
- 形式化验证（如定理证明）可提供更通用的数学证明，但需确保规约的完备性。
CRDT
初识CRDT协作CRDT 无冲突复制数据类型，是一种可以在网络中的多台计算机上复制的数据结构，副本可以独立和并行地更新， - 掘金
CvRDT
Conflict-Free Replicated Data Type是分布式系统中用于实现无冲突复制数据类型的总称，CvRDT（Convergent Replicated Data Type，收敛复制数据类型）
这是基于状态的CvRDT（state-based CRDT）。通过状态传播的合并来实现一致性。节点定期将状态发送给其他节点，其他节点通过合并状态来更新本地副本。本操作必须是幂等的、结合的。
核心思想：通过数学上的交换律、结合律和幂等率保证最终副本一致。
要求：操作必须是可交换的（顺序不影响结果，如集合的并集操作）
通常基于状态的合并
典型例子如：G-Counter（增长计数器）、PN-Counter（正负计数器）、OR-Set（移除观察集合）
CmRDT
commutative replicated data type 可交换复制数据类型
基于操作的CRDT（Op-based CRDT，CmRDT）。通过传播操作来实现一致性。每个操作都是可交换的，通过将操作广播到所有节点，所有节点独立应用这些操作确保最终状态一致。
核心思想：通过确保操作必须是可交换的，一来操作传输（operation-based），即传播操作而非状态。
LWW-Register（Last-Write-Wins Register，最后写入胜出寄存器）是分布式系统中常用的一种冲突解决机制和数据结构。
LWW-Register（最后写入获胜寄存器）、特定条件下的计数器。
转换
简单来说一个同步的是状态一个同步的是操作。
- CvRDT：需要发送完整状态，比如分布式计数器（购物车库存），设备状态同步（如传感器网络）。
- CmRDT：仅发送操作，实时协作编辑（谷歌文档），聊天应用。
在形式上，Op-based CRDT 和 State-based 是可以互相转换的。思路为：
通过 Op-based CRDT 构建 State-based CRDT 的方式为:
- 将新的 State-based Object 的 state 定义为一个二元组(s, M)，s 和 Op-based CRDT 的内部状态一致，M 是 Op-based CRDT 的内部 Op 的集合。
- 将新的 State-based Object 的 merge 操作定义为
merge((s, M), (s', M')) = apply_ops(s, M' - M)。
通过 State-based CRDT 构建 Op-based CRDT 的方式为：
- 将新的 Op-based object 的 Op 定义为 State-based CRDT 的 State。
- 将
apply_op的操作定义为apply_op(state, op) = merge(state, op)，而 merge 是服从对称性的操作，从而我们能够满足 SEC 得到一个 Op-based CRDT。