架构06-分布式共识

1、分布式共识

（1）基本概念

• **分布式共识：**在分布式系统中，多个节点之间达成一致的过程。
• **复杂性来源：**网络的不可靠性和请求的并发性。
• **应用场景：**如何确保重要数据长期存储在电脑上不会丢失。

（2）数据备份与系统可靠性

• 磁盘备份：
  • 使用多块磁盘备份数据，降低数据丢失概率。
  • 例如，使用四块磁盘保存同一份数据，数据丢失的概率仅为0.0000625%。
• 软件系统可靠性：
  • 单个节点系统宕机的原因多样，如程序错误、硬件损坏、网络分区等。
  • 通过多台机器拥有数据副本，提高系统的可靠性。

（3）系统可用性挑战

• 动态数据同步：
  • 数据同步方法如2PC、3PC，确保数据在多个节点间一致。
  • **缺点：**增加Slave节点会增加系统可用性风险。
• 状态转移 vs 操作转移：
  • **状态转移：**确保所有节点状态一致，但牺牲可用性。
  • **操作转移：**通过操作日志广播，允许内部状态不一致，但最终状态一致。

（4）高可用与高可靠性的平衡

• Quorum机制：
  • 通过“少数服从多数”原则，容忍部分节点失联，提高系统可用性。
  • 例如，超过半数节点完成状态转换，即可认为数据变化成功。

2、Paxos算法

（1）Paxos算法简介

• **提出者：**Leslie Lamport。
• **地位：**分布式系统最重要的理论基础之一。
• **背景：**Paxos算法的提出和被认可经历了多次波折。

（2）Paxos算法的工作流程

• 节点角色：
  • **Proposer：**提出提案。
  • **Acceptor：**应答提案，决定提案是否被接受。
  • **Learner：**学习已达成共识的提案。
• 工作流程：
  • 准备阶段（Prepare）：
    • Proposer向所有Acceptor广播Prepare请求，附带提案ID。
    • Acceptor回复Promise应答，承诺不再接受ID小于等于n的Prepare请求和ID小于n的Accept请求。
  • 批准阶段（Accept）：
    • Proposer收到多数Acceptor的Promise应答后，选择合适的值，广播Accept请求。
    • Acceptor在不违背承诺的前提下，接收并持久化提案值。
  • 共识达成：
    • Proposer收到多数Acceptor的Accepted应答后，共识达成，通知Learner。
  • 

（3）Paxos算法的局限性

• 缺陷：
  • 只能对单个值形成决议。
  • 至少需要两次网络请求和应答，高并发下网络开销大。
  • **活锁问题：**多个提案节点互不相让，导致系统“反复横跳”。
  • **异常场景：**由于提案节点的完全平等和并发提案，系统复杂性增加。
• 实际应用：
  • 实际应用中多使用Multi Paxos和Fast Paxos等改进版本。

3、Multi Paxos 的改进

（1）核心改进

• **核心改进：**增加“选主”过程。
• 选主机制：
  • 定时轮询（心跳）确定当前主节点。
  • 心跳超时后，节点使用 Basic Paxos 的准备、批准过程竞选主节点。
  • 得到多数派批准后，竞选成功。
• 主节点角色：
  • 只有主节点可以提出提案。
  • 从节点接收到客户端请求后，将请求转发给主节点。
  • 主节点提案时，无需再次经过准备过程，只需批准即可。

（2）数据复制过程

• 正常情况：
  1. 主节点将变更写入日志，广播给从节点。
  2. 从节点写入日志，回复确认消息。
  3. 主节点收到过半数确认后，提交变更，应答客户端，广播提交消息。
  4. 从节点提交变更，完成数据复制。
• 异常情况：
  • **网络分区：**部分节点失联，但仍能正常工作的节点数量满足多数派要求。
  • **分区恢复：**主节点通过任期编号确定唯一性，回滚未提交的变更，同步失联期间的变更。

（3）安全性保证

• **Safety（协定性）：**确保选主结果唯一，不会出现多个主节点。
• **Liveness（终止性）：**选主过程最终能够结束。
• **活锁问题：**理论上存在选主无法结束的风险，但实际工程实现中几乎不会出现。

（4）Raft 算法

• **核心思想：**将共识问题分解为三个子问题：
  1. Leader Election：选主问题。
  2. Entity Replication：数据复制问题。
  3. Safety：安全性保证。
• **应用：**etcd、LogCabin、Consul 等分布式程序的基础。

4、Gossip 协议

（1）特点

• 适用于最终一致性场景。
• 无中心化节点，节点平等。
• 高鲁棒性，适合公众互联网。

（2）工作过程

• 信息源选择固定周期，随机选择 k 个节点传播消息。
• 收到消息的节点在下一个周期内，将消息发送给 k 个节点，直到全网一致。

（3）缺点

• 状态不一致时间长。
• 消息冗余，增加网络传输压力。

（4）传播方式

• **反熵：**同步全部数据，消除节点差异。
• **传谣：**仅发送变更信息，减少网络开销。