Paxos&ZAP
paxos
是什么
Paxos is a family of protocols for solving consensus in a network of unreliable processors (that is, processors that may fail). Consensus is the process of agreeing on one result among a group of participants. This problem becomes difficult when the participants or their communication medium may experience failures.
是个协议，解决在不可靠节点中达到共识的问题。具体的讲，可以确定一个不可变变量的取值。对比2PC和3PC，2PC主要问题是同步阻塞、单点、保守，3PC通过都一个preCommit，可以实现超时提交/abort，减少数据不一致的情况。但仍然参在脑裂问题。而paxos通过更多的accptors能解决脑裂问题。
应用
在分布式存储系统中，多个副本的操作序列op1、op2…是相同的，不变的，可以用paxos来依次确定不可变的值opi，让各个副本执行opi，然后达成一致。
解决一致性问题
确定一个不可变变量的取值 系统满足容错性：
- 可以容忍任意proposer机器出现故障
- 可以容忍少数accptor故障（半数以下）
方案一：单个acceptor，使用类似互斥锁管理并发proposer
- 问题，死锁问题，当其中一个proposer获取了互斥锁后崩溃，需要等待。
方案二：引入抢占式访问权，accpetor可以让某个proposer的访问权实现，并不在接收他的访问
- 问题，acceptor的单点问题
- 方式就是proposer想accceptor申请访问权的时候指定epoch（越大epoch越新），获取到访问权才能提交取值
两个原则
- 喜新厌旧（抢占式访问权），新epoch可以抢占旧epoch，让旧epoch失效，旧epoch无法运行。
- 后者认同前者：在旧的epoch确定无法形成确定性取值后，新epoch提交自己的值；一旦旧epoch形成确定性取值，新epoch可以获取到此值，并且认同此取值，不会破坏。
PS：后者认同前置，首先是没有处理拜占庭将军问题，一般场景中，为了确定opi，这value会不同么？应该是一个确定的值。要不也不会有后者认同前者，这样的规则，新epoch的value生效的唯一场景就是前面的epoch没有形成确定性取值（一个也没有写成功）。
方案三：paxos，引入多个accpetor
又加了个原则：少数服从多数
- 一旦某epoch已经被半数以上的accepotor获取，则认为此var被确定，不在更改
两阶段：
- 第一阶段：prepare，proprosor选定epoch，获取半数以上的acceptor的访问权和对应的var值
- 第二阶段：accept，proprosor后者认同前者执行修改或者获取var
核心思想
- 在抢占式的访问权基础上引入多acceptor
- 保证一个epoch，只有一个proprosor在运行，proprosor按照epoch递增顺序一次运行。
- 新epoch的proproser采用后者认同前者的方式运行，在肯定旧的epoch无法形成确定性取值的时候，新的epoch会提交自己的值，不会冲突；一旦旧epoch形成确定性取值，新epoch或获取到此值，并会认同此取值（自己也会提交此值），不会破坏
问题
- 活锁，epoch一直交替获取到访问权但没来得及第二阶段
ZAP
This documents the Zab, an atomic broadcast protocol used by ZooKeeper to propagate state changes.
Zab at a high level is a leader based protocol similar to Paxos. Some of the aspects that distinguish Zab from Paxos is that Zab recovers histories rather than single instances of protocols; Zab has prefix ordering properties to allow primary/backup implementations to have multiple outstanding operations outstanding at a time; and Zab does special processing at leadership change to guarantee unique sequence numbers for values proposed by a leader.
Zab与pasox不同：
- Zab是恢复histories，而paxos是恢复单个实例
- Zab又前缀排序，能够并发的处理多个operations。
- Zab在切换leader有特殊处理（zxid中的epoch每次切换都会加1）
两种基本模式
崩溃恢复
选举
- 先比较zxid，谁大选谁，其次比较serverId。这样就可以省去leader服务器的检查proposal的提交和丢弃工作的操作了。
- 这zxid并不是是必须commit的，最大的proposal的即可
- 由于每次更换leader都对epoch加1，能确保丢弃只在leader服务器上被提出的事物
数据同步
- leader为每个follower准备一个队列，把那些没有被
消息广播
- zab的原子广播类似于二阶段提交，但不必收到所有的follower的ack消息，在有一半的folloer ack后（加上leader自己就超过一半）就可以进行commit了
参考