State-machine replication

Fault models

• Fault: Some component is not working correctly
• Failure: System as a whole is not working correctly

在分布式系统中，故障（Fault，指单个组件出错）并不罕见，如果不加以处理，会导致整个系统瘫痪（Failure）。为了设计高可用系统，首先需要对可能发生的故障建立模型：

• 崩溃故障（Crash faults）：节点由于操作系统崩溃、断电等原因直接停止运行。
• 理性故障（Rational faults）：节点并没有崩溃，而是因为其所有者为了增加自身利益而自私地操纵节点（例如 BGP 路由中的流量吸引攻击，网络提供商故意谎报自己有更优的路由以赚取费用）。
• 拜占庭故障（Byzantine faults）：任意的、恶意的故障。故障节点可以做任何事情，包括停止、篡改数据、撒谎、攻击其他节点或发送垃圾邮件（例如黑客入侵、内部员工植入逻辑炸弹等）。
• 相关性故障（Correlated faults）：多个故障不是独立发生的，一个问题可能引发多米诺骨牌效应，导致大量节点同时宕机（例如共享同一电源、同一个软件 Bug 被大面积触发等）。

State-machine replication

Consensus protocols

为了让所有副本以相同的顺序处理请求，节点之间必须达成“共识”。一个严谨的共识机制必须满足四个条件：终止性（大家都做出决定）、有效性、完整性以及一致性（Agreement，如果有节点决定了某个值，其他所有正常节点也必须决定该值）。

FLP impossibility

FLP 不可能定理（FLP Impossibility）：分布式计算中极具理论意义的定理。它指出，在异步网络模型中，只要哪怕存在一个可能发生崩溃故障的节点，就没有任何算法能保证共识一定能达成（即无法保证终止性/Liveness）

Paxos

Intuition

Paxos 的目标是在存在崩溃故障（不能容忍拜占庭撒谎）且网络可能延迟、丢包的情况下，让多个节点协同维护一个仅追加的一致性日志（Append-only log）。其核心通过两阶段（Two-Phase）协议来实现提案的通过：

1. **第一阶段：准备阶段（Phase 1: Prepare）提议者（Proposer）提案编号 n，并向多数派（Quorum）节点发送 PREPARE(n) 消息。这相当于在问：“我能用编号 n 提议吗？如果可以，你们之前有没有接受过别的值？”。**接受者（Acceptor）**收到后：如果它已经回应过编号比 n 更大的 PREPARE，就直接忽略。否则，它会向提议者回复 ACK，承诺以后绝不接受编号小于 n 的提案。如果在以前它已经接受过其他提案，它会在 ACK 中带上它接受过的最高编号及其对应的值（n′,X′）。
2. 第二阶段：接受阶段（Phase 2: Accept）如果提议者收到了多数派的 ACK，它就可以正式发出提案 ACCEPT(n, X*)。这里非常关键的一点是值的选择：如果收到的 ACK 中包含了别人以前接受过的值，它必须选择其中编号最大的那个值作为 X∗；如果所有的 ACK 都是空的，它才可以提议自己最初想要提议的值。接受者收到 ACCEPT(n, X*) 后，只要它没有在此期间回应过比 n 更大的 PREPARE 请求，它就会接受这个提案，并把这个决定广播给所有的学习者（Learners）。学习/决定阶段：当一个学习者收到来自多数派接受者的 ACCEPT 消息时，这个值 X∗ 就被正式**决定（Decide）**了，然后它会通知其他所有人。

Paxos 的精髓在于通过第一阶段的“读取与承诺”机制，强制后来的提议者必须沿用之前多数派可能已经通过的值，从而确保一旦某个值被多数派接受，后续任何成功的高编号提案都只能是这个相同的值，这就完美保证了一致性（Safety）。但如前所述，Paxos 假设节点遵循协议不会撒谎（即针对 Crash faults），它无法处理恶意篡改数据的拜占庭故障。