079. 分布式一致性算法

原创
2020/09/18 14:13
阅读数 76

1. 理解一致性


多份数据保持一致。

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

image-20200706134017936

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

image-20200706134823448

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


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

image-20200706135625239

问题

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

3. 2PC


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

P1:准备阶段(投票阶段)

image-20200706141121937

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

image-20200706141358411

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

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

P2:提交阶段

image-20200706141816703

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

image-20200706142105500

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

image-20200706142213499

  1. 结束。

两阶段提交过程消息流

image-20200706165636771

存在的不足

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

4. 3PC


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

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

3PC 过程消息流

image-20200706145736333

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

3PC 存在问题及难点

  • 基于 2PC 引入超时机制、预提交。
  • 问题:仍然会出现不一致的问题。
  • 难点:超时时长该设置为多长?

没有实现,只是一种理论!

5. Paxos 推出


1. 正常操作

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

image-20200706150827911

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

image-20200706151310233

造成集群中节点不一致

image-20200706151434639

2. 添加 Leader 节点

会有一个 Leader 节点

image-20200706154723302

所有的写请求发往 Leader 节点

image-20200706154853799

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

image-20200706155009005

v2 后到,再次进行广播

image-20200706155113104

节点数据更新为 v2

image-20200706155148468

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

6. Paxos 算法


image-20200706155609197

  • Proposer:提议者,负责提议,提出想要达成一致的 value 提案。

  • Acceptor:接收者,对提案投票,决定是否接受此 value 提案。

  • Learner:学习者,不参与投票,学习投票决定的提案。

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

提案内容

  • 提案编号:唯一,保证全局递增,体现提案的先后顺序。
  • 更新值。

操作流程,两阶段:

  • 准备阶段(投票阶段)
    • 提议者提出提案给接收者;
    • 接收者如果同意该提案,做出 promise 响应,并不再 Accept 比当前提案号低的提案;
    • 提议者收到超过半数的响应,则进入下一阶段;否则重新提案。
  • 接受变更阶段(提交阶段)
    • 提议者向接收者发送 Accept 消息;
    • 接收者比较 Accept 消息中的提案号,如果比自己当前已 promise 的提案号低,则回应 Nack(自己当前 promise 的提案号),否则 Accept,广播 Accepted。

算法图示

image-20200706161943686

Paxos 先后批准场景

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

    image-20200706162518208

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

    image-20200706162945883

Paxos 读流程

image-20200706163321230

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

7. 其他


  • ZAB
    • 具体看上一篇笔记《4.1.2-4. zk 集群》。
  • RAFT:http://thesecretlivesofdata.com/raft/
    • 节点有三个状态:从节点、候选、Leader。
    • 第一个要做的事情就是 Leader 选举。
    • 然后才是 Leader 接收写请求,协调数据的一致性。
    • 保证数据一致性的过程:日志+同步。
展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部