Zookeeper 理论 - litter-fish/ReadSource GitHub Wiki

事务四大特性 ACID

  1. 原子性，事务必须是一个原子的操作序列单元。要么全部执行成功，要么不执行
  2. 一致性，
  3. 隔离性
  • 读未提交
  • 读已提交
  • 可重复读，在事务的处理过程中，多次读取同一个数据时，值都一样的。
  • 串行化，事务只能一个接一个的执行，不能并发的执行 4种隔离级别的示意图： 6c4334be31de77a9f9cb553ef4a7ef14.png
  1. 持久性

CAP 定理

cap定理示意图： 3d83850f7224a678c0a8dd8da5a5b384.png

一个分布式不能同时满足一致性（C：Consistency）,可用性（A：Availability）和分区容错性（P：Partition tolerance）这三个基本需求，最多只能同时满足两个条件。 一致性：数据在多个副本能够保持一致的特性。 可用性：系统提供的服务必须一致处于可用状态，对于用户的每一个操作请求总是能在有限的时间内返回结果。 分区容错性：分布式系统在遇到任何网络分区故障时，仍然需要能够保证对外提供满足一致性和可用性的服务，除非整个网络环境都发生了故障。

BASE 理论

基本可用（Basically Available），软状态（Soft state），最终一致性（Eventually consistent）

  1. 基本可用：分布式系统在出现不可预知的故障时，允许损失部分可用性。 相应时间上的损失： 功能上的损失：

  2. 弱状态：指运行系统中的数据存在中间状态，并认为该中间状态的存在不会影响系统的整体可用性

  3. 最终一致性：指系统中的所有副本，在经过一段时间的同步后，最终能达到一个一致的状态。

一致性协议

2PC

将事务提交分成两个阶段： 阶段一：提交事务请求

  1. 事务询问 协调者向所有的参与者发送事务内容，询问是否可以进行事务提交操作，并开始等待各参与者的响应
  2. 执行事务 各参与者执行事务操作，并将Undo和Redo信息记录事务日志中
  3. 各参与者向协调者反馈事务询问的响应 如果参与者成功执行事务操作，则向协调者反馈Yes响应，表示事务可以执行；如果参与者没有成功执行事务，那么就向协调者反馈NO响应，表示事务不可以执行。

阶段二：执行事务提交

协调者通过参与者反馈情况开最终决定是否可以执行事务的提交操作， 执行事务提交 协调者获取参与者的反馈都是YES，则会执行事务提交， 示意图： 8ccc8e717c69a7189e45cd7ada6e3a7b.png

  1. 发送提交请求 协调者向所有参与者节点发出Commit请求。

  2. 事务提交 参与者在接收到Commit请求时，会真正执行事务提交，并在完成事务提交后释放在整个事务执行期间占用的事务资源。

  3. 反馈事务提交结果 参与者在完成事务提交后，向协调者发送ACK消息。

  4. 完成事务 协调者在接收到所有参与者反馈的ACK消息后，完成事务。

中断事务：任何参与者在阶段一中反馈了NO，或者等待超时之后，协调者尚无法收到所有参与者的反馈响应 示意图： 3a09ce7e653d3e677a83454c447e56c4.png

  1. 发送回滚请求 协调者向所有参与者节点发出Rollback请求。

  2. 事务回滚 参与者在接收到Rollback请求时会利用阶段一中的Undo信息来执行事务的回滚操作，并在完成事务回滚后释放在整个事务执行期间占用的事务资源。

  3. 反馈事务回滚结果 参与者在完成事务回滚时，会向协调者反馈ACK信息。

  4. 中断事务 协调者收到所有参与者反馈的ACK信息后完成事务中断。

优缺点： 优点：原理简单，实现方便 缺点：同步阻塞，单点问题，脑裂，太过保守 同步阻塞：各个参与者在等待其他参与者的响应过程中没法进行其他任何操作。

3PC

是二阶段的改进，分为：CanCommit,PreCommit,DoCommit三个阶段 阶段一：CanCommit

  1. 事务询问 协调者向所有参与者发送一个包含事务内容的CanCommit请求，询问是否可以进行事务提交操作，并开始等待各个参与者的响应。

  2. 各个参与者向协调者反馈事务的询问的反馈 参与者在接收到来自协调者的CanCommit请求后，正常情况下，如果其自身认为可以顺利执行事务，那么会反馈YES响应，并进入预备状态；否则反馈NO响应。

阶段二：PreCommit 根据阶段一的响应来决定是否进行PreCommit操作 执行事务预提交：协调者从所有参与者中获取到的响应都是Yes响应

  1. 发送预提交请求 协调者向所有参与者节点发出PreCommit请求，并进入PrePared阶段。

  2. 事务预提交 参与者接收到PreCommit请求后，会执行事务，并将Undo和Redo信息记录到事务日志中。

  3. 各参与者向协调者反馈事务执行的响应 如果参与者成功执行了事务操作，那么就会反馈给协调者ACK响应，同时等待最终指令：提交（commit）或中止（abort)。

中断事务：任何参与者在阶段一中反馈了NO，或者等待超时之后，协调者尚无法收到所有参与者的反馈响应

  1. 发送中断请求 协调者向所有参与者节点发出abort请求。

  2. 中断事务 无论是收到来自协调者的abort请求，或者等待协调者请求过程中出现超时，参与者都会中断事务。

阶段三：DoCommit 真正进行事务提交 执行提交

  1. 发送提交请求 进入这个阶段，假设协调者处于正常工作状态，并且它接收到来自所有参与者的ACK响应，那么它将从“预提交”状态转换为“提交”状态，并向所有的参与者发送doCommit请求。

  2. 事务提交 参与者接收到doCommit请求后，会正式执行事务提交操作，并在完成事务回滚后释放在整个事务执行期间占用的事务资源。

  3. 反馈事务提交结果 参与者在完成事务提交后会向协调者反馈ACK消息。

  4. 完成事务 协调者接收到所有参与者反馈的ACK消息，完成事务。

中断事务 进入这个阶段，假设协调者处于正常工作状态， 任何参与者在阶段二中反馈了NO，或者等待超时之后，协调者尚无法收到所有参与者的反馈响应

  1. 发送中请求 协调者向所有参与者节点发送abort请求。

  2. 事务回滚 参与者在接收到Rollback请求时会利用阶段二中的Undo信息来执行事务的回滚操作，并在完成事务回滚后释放在整个事务执行期间占用的事务资源

  3. 反馈事务回滚结果 参与者在完成事务回滚操作后，向协调者反馈ACK信息。

  4. 中断事务 协调者接收到所有参与者反馈的Ack信息，中断事务。

事务在进入阶段三时，如果出现：

  • 协调者故障
  • 协调者后与参与者网络出现异常 导致参与者无法接收到协调者发出的doCommit或Abort请求，这时参与者会进入等待超时之后，继续进行事务提交。

优点：相对于二阶段，降低了参与者的阻塞范围，能够在出现单点故障时继续达成一致 缺点：参与者在接收到PreCommit请求后如果出现了网络分区，协调者和参与者无法进行通信，这时参与者依旧会进行事务提交，此时会存在数据不一致

Paxos算法

推导过程 P1：一个Acceptor必须批准它收到的第一个提案。

P2：如果编号为M0，value值为V0的提案[M0，v0]被选定，那么所有比编号M0更高的，且被选定的提案，其value值也必须是V0。

P2a：如果编号为M0，value值为V0的提案[M0，V0]被选定，那么所有比编号M0更高的，且被Acceptor批准的提案，其value值也必须是V0.

P2b：如果一个提案[M0，V0]被选定后，那么之后任何Proposer产生编号更高的提案，其值也必须是V0.

ZAB协议

支持奔溃恢复的原子广播协议。 消息广播 ZAB在进行广播的过程使用的是一个原子广播协议，类似于二阶段提交过程。 针对客户的的事务请求，Leader服务器会为其生成一个对应的事务Proposal，并将其发送给集群的其余机器，然后再分别收集各自的选票，最后进行事务提交。 消息广播流程示意图： 20f160b7ccc305b3b69a4e4ddbd90aee.png

首先，移除中断逻辑，所有的Follower服务器要么正常反馈Leader服务器提出的事务Proposal，要么就抛弃Leader服务器。 其次，如果过半的Follower服务器反馈了Ack后就会进行事务的提交，不需要等待集群的所有服务器的反馈。

奔溃恢复 当Leader服务器出现奔溃或由于网络原因导致Leader服务器失去过半Follower的联系，那么就会进入奔溃恢复模式。