一致性协议和算法

• 二阶段提交协议
• 三阶段提交协议
• Paxos协议

（2PC）二阶段提交协议

• 协调者
  • （统一调度所有分布式节点执行逻辑）
• 参与者
  • （被调度的分布式节点）
• 绝大部分关系型数据库都是采用二阶段提交协议
• 协议说明：
  • 阶段一：提交事务请求（“投票阶段”）
    • 事务询问
      • 协调者向各参与者发送事务内容，询问是否执行事务提交，等待各个参与者响应
    • 执行事务
      • 各个参与者执行事务操作，并将undo、redo 计入事务日志
    • 各个参与者向协调者反馈事务询问的响应
      • 成功执行返回YES
      • 失败返回NO
  • 阶段二包含两种可能：
    • 可能1：执行事务提交（所有参与者都返回YES）
      1. 发送提交请求（协调者向各个参与者发出commit 请求）
      2. 事务提交（参与者 commit 后释放资源）
      3. 反馈事务提交结果（向协调者发送事务提交Ack消息）
      4. 完成事务（收到所有Ack，完成事务）
    • 
    • 可能2：中断事务（任何一个参与者返回NO或超时未返回结果）
      1. 发送回滚请求
      2. 回滚提交
      3. 反馈回滚
      4. 完成回滚
    • 
• 强一致算法
• 优缺点：
  • 优点：
    • 原理简单，实现方便
  • 缺点：
    • 同步阻塞
      • 极大限制分布式系统性能
      • 所有参与该事务操作逻辑都处于阻塞状态
    • 单点问题
      • 一旦协调者出现问题，二阶段无法运转
    • 脑裂（数据不一致）
      • 二阶段协调者发送commit 网络异常，只有部分参与者commit成功，导致数据不一致
    • 过于保守
      • 二阶段提交协议没有完善的容错机制，任何节点失败都会导致整个事务失败

（3PC）三阶段提交协议

• 二阶段提交协议的改进
• 将2pc的“提交事务请求”一分为二，变成：
• Cancommit、PreCommit、doCommit
• 
• 进入阶段三可能出现两种故障：
  • 协调者出现问题
  • 协调者与参与者网络出现问题
• 无论哪种情况，参与者都会在最终超时的时候，doCommit 或 回滚

优点：

• 降低参与者阻塞范围，并能在出现单点故障后继续达成一致

缺点：

• 在preCommit 后，如果出现“网络分区（部分网络故障）”，未故障节点依然会commit，导致不一致

Paxos 算法

• 基于消息传递、具有高度容错特点的一致性算法
• 是目前公认的最有效的分布式一致性算法之一
• 在机器宕机或网络异常情况下，快速且正确的将某个数据达成一致
• 既解决了数据不一致问题，也解决了无限等待问题
• paxos是一个分布式选举算法即可

有三种角色：

• Proposer
• Acceptor
• Learners
• 一个进程可能同时充当多种角色。比如一个进程可能既是Proposer又是Acceptor又是Learner。
• Proposer负责提出提案，Acceptor负责对提案作出裁决（accept与否），learner负责学习提案结果。

Paxos算法的活锁问题（保证算法活性）