4.1.2-5. 分布式一致性算法

1. 理解一致性

多份数据保持一致。

1. 一份数据，存储在不同数据存储服务节点上，主从场景。

1. 业务方面，涉及到多个有状态的服务。如下单需增加订单数据、扣减库存。

2. 什么情况会导致不一致？

网络分区、故障、异常导致多个操作的部分操作不能成功。

问题

• 网络分区、故障、异常能避免吗？
• 如何保证 a1 成功、b1 失败时的一致性？
• 将更新过程分为预操作、提交/回滚两个阶段，可否？
• 要能回滚、提交，需要什么？
  • undo、redo 日志

    3. 2PC

• 2PC：将提交操作分为准备（投票）、提价（完成）两个阶段来达成一致性的 算法。主要用于事务管理、分布式一致性。

  P1：准备阶段（投票阶段）

  

1. 协调者询问各参与者是否可以提交；等待所有参与者给出响应。
2. 参与者执行事务操作到等待提交指令的点（这个过程中记录 redo、undo 日志）。

1. 参与者响应是否准备好提交的结果给协调者，并阻塞等待协调者的下一个指令。

2. 协调者接收所有参与者的响应，如果超时未收到响应，当 abort 处理。有一个 abort，则下一步是回滚。

   P2：提交阶段

   

3. 协调者向所有参与者发出提交或回滚的消息。

1. 参与者执行提交/回滚，释放占用的锁等资源，并作出响应。

1. 结束。

   两阶段提交过程消息流

   

   存在的不足

2. 阻塞

   • 参与者响应是否准备好提交的结果给协作者，并阻塞等待协作者的下一步指令。
   • 准备完成时，如果协调者宕机，所有参与者将一直阻塞。
3. 不一致
   • 协调者向所有参与者发出提交或回滚消息。
   • 参与者宕机，将接收不到提交消息，会出现不一致（需要人工干预）。

     4. 3PC

2PC 当协调者宕机时（网络分区时）将一直阻塞。

• 3PC 增加预提交阶段+超时限制来改进这个问题。

  3PC 过程消息流

  

• 什么情况下出现不一致？

  • 部分 preCommit 失败，协调者宕机，等待超时后，preCommit 成功者自动提交，此时会出现不一致的情况。

    3PC 存在问题及难点

• 基于 2PC 引入超时机制、预提交。

• 问题：仍然会出现不一致的问题。
• 难点：超时时长该设置为多长？

  没有实现，只是一种理论！

  5. Paxos 推出

1. 正常操作

两个客户端分别修改两个节点状态

两个节点状态修改，并分别通知其他节点

造成集群中节点不一致

2. 添加 Leader 节点

会有一个 Leader 节点

所有的写请求发往 Leader 节点

请求会有先后顺序，假如 v1 先到达，会通知其他节点

v2 后到，再次进行广播

节点数据更新为 v2

问题

• Leader 的负载高。
• Leader 单点故障，整个集群不可用。

  6. Paxos 算法

• Proposer：提议者，负责提议，提出想要达成一致的 value 提案。
• Acceptor：接收者，对提案投票，决定是否接受此 value 提案。
• Learner：学习者，不参与投票，学习投票决定的提案。

  一个节点既可以是 提议者，也可以是投票者。

提案内容

• 提案编号：唯一，保证全局递增，体现提案的先后顺序。

• 更新值。

  操作流程，两阶段：

• 准备阶段（投票阶段）

  • 提议者提出提案给接收者；
  • 接收者如果同意该提案，做出 promise 响应，并不再 Accept 比当前提案号低的提案；
  • 提议者收到超过半数的响应，则进入下一阶段；否则重新提案。

• 接受变更阶段（提交阶段）

  • 提议者向接收者发送 Accept 消息；
  • 接收者比较 Accept 消息中的提案号，如果比自己当前已 promise 的提案号低，则回应 Nack（自己当前 promise 的提案号），否则 Accept，广播 Accepted。

    算法图示

    

    Paxos 先后批准场景

• 同一提案，提议者 2、提议者 1 先后被批准，正常场景。

• 接收者 3 与提议者 2 失联、接收者 1 与 提议者 1 失联，异常场景。
  

Paxos 读流程

• 接收客户端请求的节点，向集群广播获取大家的当前值；
• 接收到过半数相同的值，则返回该值，如果本地的值不同，则更新为多数值；
• 如果得不到过半数的相同值，则读取失败。

7. 其他

• ZAB
  • 具体看上一篇笔记《4.1.2-4. zk 集群》。
• RAFT：http://thesecretlivesofdata.com/raft/
  • 节点有三个状态：从节点、候选、Leader。
  • 第一个要做的事情就是 Leader 选举。
  • 然后才是 Leader 接收写请求，协调数据的一致性。
  • 保证数据一致性的过程：日志+同步。