从Paxos到Zookeeper-分布式一致性原理与实践
1 分布式特点
- 分布性
- 对等性
- 并发性
- 缺乏全局时钟
- 故障总会发生
2 分布式问题
- 通信异常
- 网络分区
- 三态 单体应用中一次请求的结果总是明确的，分布式系统中因为网络是不可靠的，导致成功、失败和超时
- 节点故障
3 单机事务
ACID
A=Atomicity 原子性
C=Consistency 一致性
I=Isolation 隔离性
D=Durability 持久性
4 分布式理论
4.1 CAP
C=Consistency 一致性
A=可用性
P=分区容错性
分区容错性约束了一个分布式系统在遇到任何网络分区故障的时候，都要能够保证对外提供满足一致性和可用性的服务，除非是整个网络都发生故障
4.2 BASE
BA=Basically Available 基本可用
S=Soft State 软状态
E=Eventually consistent 最终一致性
4.3 最终一致性变种
因果一致性
读己之所写
会话一致性
单调读一致性
单调写一致性
5 一致性协议
5.1 2PC
5.1.1 角色
协调者 统一调度所有分布式节点的执行逻辑
参与者 执行节点
5.1.2 阶段
阶段一 提交事务请求
- 事务询问 协调者向参与者询问是否可以执行事务
- 执行事务 参与者执行事务，记录Undo和Redo日志信息
- 反馈响应 参与者反馈Ack，可以执行事务返回Yes，不可以执行事务返回No
阶段二 执行事务提交
协调者根据Ack决策
- 提交事务 所有参与者都回复Yes表示可以执行事务
- 协调者告诉参与者进行Commit
- 参与者提交事务，释放独占的资源
- 参与者向协调者Ack
- 协调者收到所有Ack 整个分布式事务结束
- 回滚事务 但凡有一个参与者回复No
- 协调者向参与者发送Rollback请求
- 参与者执行回滚，释放独占的资源
- 参与者回复协调者Ack
- 协调者收到所有参与者Ack后 整个分布式事务宣告结束
5.1.3 两阶段协议问题
- 同步阻塞
- 单点问题 极度依赖协调者
- 数据不一致 第二阶段时，协调者向参与者发送提交请求时，发送一半出现网络问题，导致有的参与者提交了事务，有的参与者没有提交事务
- 过于保守 没有设计完善的容错机制，任意一个节点的失败都会导致整个事务的失败
5.2 3PC
5.2.1 角色
协调者 统一调度所有分布式节点的执行逻辑
参与者 执行节点
5.2.2 阶段
阶段一 CanCommit
阶段二 PreCommit
阶段三 doCommit
5.2.3 三阶段提交的问题
参与者接收到preCommit消息后，如果网络出现分区，此时协调者所在的节点和参与者无法进行网络通信，在这种情况下，该参与者依然会进行事物的提交，导致数据不一致
6 Paxios算法
基于消息传递且具有高度容错特性的一致性算法
引入过半理念和支持分布式节点角色转换，避免了分布式单点问题，也解决了无限期等待问题
6.1 一致性安全需求
- 只有被剔除的提案才能被选定
- 只有一个值被选定
- 如果某个进程认为某个提案被选定了，那么这个提案必须是真的被选定的那个
6.2 目标
保证最终有一个提案会被选定，当提案被选定之后，进程最终也能获取到被选定的提案
6.3 角色
- Proposer
- Acceptor
- Learner
6.4 过程
6.4.1 提案的选定
Poposer向一个Acceptor集合发送提案
足够多的Acceptor是整个Acceptor集合的一个子集，并且让这个集合大的可以包含Acceptor集合中的大多数成员
提案由一个编号和Value的组成的组合体，[编号, Value]
6.4.2 Proposer生成提案
Proposer在产生一个编号为Mn的提案时，必须要知道某一个将要或者已经被半数以上Acceptor批准的编号小于Mn但为最大编号的提案，并且Proposer会要求所有的Acceptor都不要再批准任何编号小于Mn的提案
6.4.3 Acceptor批准提案
一个Acceptor可能会收到来自Proposer的两种请求，分别是Prepare请求和Accept请求
- Prepare请求 Acceptor可以在任何时候响应一个Prepare请求
- Accept请求 在不违背Accept现有承诺的前提下，可以任意响应Accept请求
6.5 算法
6.5.1 Proposer和Acceptor提案选定
阶段一
1 Proposer选择一个提案编号Mn，然后向Acceptor的某个超过半数的子集发送编号为Mn的Prepare请求
2 如果一个Acceptor收到一个编号为Mn的Prepare请求，且编号Mn大于该Acceptor已经响应过的所有Prepare请求的编号，那么它就会将已经批准过的最大编号作为响应反馈给Proposer，同时该Acceptor会承诺不会再批准任何编号小于Mn的提案
阶段二
1 如果Proposer收到来自半数以上的Acceptor对于其发出的编号为Mn的Prepare请求的响应，那么它就会发送一个针对[Mn,Vn]提案的Accept请求给Acceptor
2 如果Acceptor收到针对这个[Mn,Vn]提案的Accept请求，只要该Acceptor尚未对编号大于Mn的Prepare请求作出响应，就会通过这个提案
6.5.2 Learner获取提案
6.5.3 选取主Proposer保证算法活性
7 zk
7.1 集群角色
- Leader
- Follower
- Observer
7.2 数据结构
ZNode
- 持久节点 除非主动移除，否则一直保存在zk上
- 临时节点 生命周期跟客户端会话绑定
SEQUENTIAL属性 zk允许用户为每个节点添加属性，一旦节点被标记上这个属性，那么在这个节点被创建的时候，zk会自动在其节点后面追加上一个整型数字(由父节点维护的自增数字)
7.3 版本
对于每个ZNode，zk都会维护一个Stat的数据结构
Stat中记录了这个ZNode的3个数据版本
- version 当前ZNode的版本
- cversion 当前ZNode子节点的版本
- aversion 当前ZNode的ACL版本
7.4 ZAB协议
ZooKeeper Atomic Broadcast zk原子广播协议，数据一致性的核心算法
支持崩溃恢复的原子广播协议
zk使用一个单一的主进程接收并处理客户端的所有事务请求，采用ZAB的原子广播协议，将服务器数据的变更以事务Proposal的形式广播到所有的副本进程上
ZAB协议的这个主备模型架构保证了同一时刻集群中只能有一个主进程来广播服务器的状态变更，因此能够很好地处理客户端大量的并发请求
ZAB协议的核心是定义了对于那些会改变zk服务器数据状态的事务请求的处理方式
- 所有事务请求必须由一个全局唯一的服务器来协调处理，即Leader
- Leader服务器负责将一个客户端事务请求转为一个事务Proposal提议，并将该Proposal分发给集群中所有的follower服务器
- Leader服务器等待所有Follower服务器的反馈，收到半数后Leader就会再次向所有Follower服务器分发Commit消息，要求将Proposal进行提交
ZAB协议包括两种基本模式
- 崩溃恢复
- 整个服务框架启动或者Lader出现网络中断、崩溃退出与重启等异常情况时，ZAB协议就会进入恢复模式并选举产生新的Leader
- 当选举产生了新的Leader，同步集群中过半机器与Leader完成了同步之后ZAB就会退出恢复模式
- 消息广播
- 集群中已经过半的Follower完成了和Leader的状态同步，那么整个服务框架就可以进入消息广播模式了
- 当一台同样遵守ZAB协议的服务器启动后加入到集群时，如果此时集群中已经存在了一个Leader在负责进行消息广播，那么新加入的服务器会自觉加入数据恢复模式
- 找到Leader所在的服务器，并与其进行数据同步
- 然后一起参与到消息广播流程中
ZAB协议的事务编号ZXID设计中，64位
- 高32位 代表了Leader周期epoch的编号，每当选举产生一个新的Leader服务器，就会从这个服务器上本地日志中最大事务Proposal的ZXID中解析出对应的epoch值加1
- 低32位 单调递增的计数器，针对客户端的每一个事务请求，Leader服务器在产生一个的新的事务Proposal的时候都会对该计数器进行加1操作
7.4.1 过程
- 崩溃恢复
- 消息广播
7.4.2 阶段
- 发现 Leader选举过程
- 同步
- 广播 ZAB协议正式开始接收客户端新的事务请求，并进行消息广播流程
7.4.3 状态
- Looking Leader选举阶段
- Following Follower服务器和Leader服务器保持同步状态
- Leading Leader服务器作为主进程领导状态
8 ZAB vs Paxos
区别
设计目标不一样
- ZAB协议主要用于构建一个高可用的分布式数据主备系统
- Paxos算法用于构建一个分布式的一致性状态机系统
5.6 zk典型应用场景
- 数据发布/订阅
- 负载均衡
- 命名服务
- 分布式协调/通知
- 集群管理
- Master选举
- 分布式锁
- 分布式队列