最近在看《从paxos到zookeeper分布式一致性原理与实践》这本书，顺便研究了一下微信开源项目phxpaxos 和 phxqueue。好记性不如烂笔头，做个笔记，便于学习一下。
[TOC]
第1章：关键词汇解析
ACID
Atomicity 原子性
Consistency 一致性
Isolation 隔离性
Durability 持久性
CAP
Consistency 一致性:
Availability 可用性:
Partition tolerance 分区容错性:
BASE理论
BASE 是 Basically Available（基本可用）、Soft State（软状态）和 Eventually consistent（最终一致性）。
基本可用是指 分布式系统在出现不可预知故障的时候，允许损失部分可用性，如 时延增大，功能降级等。绝对不是整个系统不可用。
软状态：系统中数据存在中间状态，不会影响系统整体可用性，不同节点的数据副本之间进行数据同步可以存在延时。
最终一致性：系统中所有数据副本，在经过一定时间后，最终达到一致状态。主要分为以下五类变种：
1、因果一致性(Causal consistency)。进程A更新了数据，告诉了进程B，则B一定是在更新后的值上面做操作，不能发生更新丢失情况。
2、读己之所写(read your writes)。进程A更新数据后，一定只能访问更新过的值，不会看到旧值。
3、会话一致性(session consistency)。系统能保证在同一个有效会话中实现“读己之所写”的一致性。
4、单调读一致性(monotonic read consistency)。 进程A从系统读取过一个数据值后，后续该进程在系统中都不会返回更旧的值。
5、单调写一致性(monotonic write consistency)。一个系统要保证来自同一个进程的写操作被顺序执行。
第2章 一致性协议
2PC
2PC，是 two phase commit， 二阶段提交。
阶段一：提交事务请求。
1、事务询问。
2、执行事务。
3、各个参与者向协调者反馈事务询问的响应。
阶段二：执行事务提交，分两种可能：
a、执行事务提交
1、发送提交请求。
2、事务提交。
3、反馈事务提交结果。
4、完成事务。
b、中断事务
1、发送回滚请求。
2、事务回滚。
3、反馈事务回滚结果。
4、中断事务。
2PC优点：原理简单，实现简单。
2PC缺点：同步阻塞，单点问题，脑裂，过于保守。
3PC
3PC，是 three phase commit， 三阶段提交，分出三个阶段：can commit, pre commit, do commit。
阶段一：can commit
1、事务询问。
2、各参与者向协调者反馈事务询问的响应。
阶段二：pre commit，分两种可能
a、执行事务预提交
1、发送预提交请求。
2、事务预提交。
3、各个参与者向协调者反馈事务执行的响应。
b、中断事务
1、发送中断请求。
2、中断事务。
阶段三：do commit，分两种情况
a、执行提交
1、发送提交请求。
2、事务提交。
3、反馈事务提交结果。
4、完成事务。
b、中断事务
1、发送中断请求。
2、事务回滚。
3、反馈事务回滚结果。
4、中断事务。
PAXOS概念
三种参与角色：proposer， acceptor，learner。
proposer生成提案，acceptor批准提案，learner获取提案。
paxos依赖一个全局的编号，这个全局唯一编号的生成并不是paxos算法需要关注的，它是paxos算法的一个前提。
###proposer行为
1、proposer选择一个新编号n，向某个acceptor集合中的所有成员发送请求（prepare请求阶段，n是prepare请求的编号，也是下面acceptor请求的议案编号），并要求回应：
a、如果acceptor没有接受过议案，则接受该n议案，并承诺永不批准编号小于n的议案，即accept后续再也不接受编号小于n的议案。
b、如果acceptor已经接受过议案，在已经批准的所有编号小于n的议案中，反馈编号最大的议案的编号k(k<n)，回应{k, v}给proposer。
2、如果proposer收到了多数（一半以上）acceptor的回应，那么它就可以提出议案{n,v}，其中v是所有回应中编号最高的议案的决议。或者如果acceptor们回应说还没有接受过议案，则由proposer选择一个任意值。
###acceptor行为
Acceptor在任何时候都可以回应prepare请求，回应就意味着接受了这个prepare请求和编号n。同时也可以回应accept请求，并批准议案，当且仅当acceptor没有承诺批准或批准一个更高编号的议案。
假设一个acceptor接收到一个编号为n的prepare请求，但是它已经回应了一个编号大于n的prepare请求，此时它就没有必要回应这个prepare请求了，因为它不会批准这个编号为n的议案，同时它还可以忽略已经批准过的议案的prepare请求。
###learner行为
learner必须要知道哪个议案被选择了。如果让每个acceptor在批准议案时去通知所有的learner，那learner就可以尽快知道选择的决议，但此时，每个acceptor通知每个learner需要的消息个数就等于 acceptor个数和learner个数的乘积。
如果让acceptor通知主learner，然后由主learner通知其他learner的话，消息个数就是等于 acceptor个数和learner个数的总和。
主learner个数只有一个的话，会有单点问题，所以可以有多个主learner，提升可靠性，但此时消息数量就增多了几个。
如果learner需要知道是否已经选择了一个决议，它可以让proposer根据上面的算法提出一个议案，提出请求就会有回应，并且新的提案的决议就是当前选择的决议。
Paxos算法
###阶段一：prepare/promise
a）proposer选择一个议案编号，向多数acceptor发送编号为n的prepare请求。
b）acceptor如果接收到prepare请求的编号n大于它已经回应的任何prepare请求，它就回应已经批准的编号最高的议案（如果有的话），并承诺不再回应任何编号小于n的议案。
Paxos的第一阶段是prepare/promise，准备阶段就是将建议值发送到各个目标节点。
当建议被发到目标节点后，进程会会检查建议中的序列号，是否是它们见到过的最高级，如果是最高级，它们会发出一个promise不再接受比这个新序列号更旧的建议了，这个诺言promise作为消息从许下诺言的进程发到提交建议新值的进程服务器，这个诺言消息给提交建议的进程后，提交建议的进程需要自己统计一下有多少其他进程已经发回它们的诺言promise了，如果判断数量上是否达到大多数？如果大多数进程已经同意接受这个建议或者更高级序列号的建议，这个提交建议的进程就能知道它获得了发言权(因为有大多数支持)，这样就开始讲话，算法中的下一步处理将可能进行；如果回复诺言的节点数量没有达到大多数，也就是共识没有达成，这样这个节点提交的建议将退出，客户端要求的写操作失败。
为了决定一个建议是否已经有足够的回复诺言promises, 提交建议者只是统计一下它接受到的 promise 消息数量，然后和整个系统中节点服务器数量比较一下，“足够”意味着大多数(N/2 + 1)个进程服务器在某段时间内都回复了诺言promises。如果超过一半的进程服务器没有返回诺言，这意味着这个建议没有被大多数通过，那么在前面描述的读算法中就不能满足大多数的要求，也就不能达成共识，这个建议就退出。其他包括网络分区错误也可能会阻止大多数达成共识，
###阶段二：propose/accept
a）proposer如果收到了多数acceptor对prepare请求（编号为n）的回应，它就向这些acceptor发送议案{n，v}的accept请求，其中v是所有prepare回应中编号最高的议案的决议v，或者回应中说还没有议案的话，该v就是proposer自主选择的值。
b）acceptor如果接收到议案{n，v}的accept请求，它就批准该议案，除非它已经回应了一个编号大于n的议案。
当完成prepare/promise阶段，进入了 propose/accept阶段。一旦建议提交者已经从大多数其他进程服务器获得了诺言，它会要求许诺的进程服务器接收它们之前承诺接受的新值数据，这是一个“确认commit”阶段，如果没有冲突建议 失败或分区错误，那么这个新建议将被所有其他节点接受，那么Paxos过程就完成了。
你能看到右边的演示，注意这个演示比上面promise在最后多了一个动作，也就是提交建议者将新值发给那些许诺言的进程服务器，让它们接受了这个新值。
接受的过程也许可能会发生失败，在回复了诺言消息以后，在接受到Accept消息之前，如果有足够多的服务器正好在这个时间段失败，那么接受行为只能是少数服务器，那么Paxos进入了厄运状态：一些进程服务器接受了新值，而不是全部的，这种不一致已经在前面读操作中描述：一个客户端试图从系统中大多数节点服务器读取它们同意接受的值，它发现一些节点服务器报告有不同的值数据，这会引起读失败，但是Paxos还保持一致性，不允许在没有达成共识情况下任何写操作发生，这种坏的情况在实践中经常通过重复接受阶段来让大多数节点最终接受。
总结
Paxos算法是保证在分布式系统中写操作能够顺利进行，保证系统中大多数状态是一致的，没有机会看到不一致，因此，Paxos算法的特点是一致性>可用性。
vector clock向量时钟是另外一种保证复制的算法，其特点是可用性>一致性，但是，一旦发生冲突，不像Paxos能自行解决，需要人工干预编写代码解决。
为了保证流程，必须选择一个主proposer，只有主proposer才能提出议案。如果主proposer和多数acceptor成功通信，并提出一个编号更高的议案，该议案将被批准。如果它得知已经有编号更高的议案，它将放弃当前的议案，并最终能选择一个足够大的编号。
第3章 zookeeper
ZAB协议
ZAB，ZooKeeper Atomic Broadcast, ZooKeeper原子消息广播协议。
所有事务请求必须由一个全局唯一的服务器来协调处理，这样的服务器被称为Leader服务器，而余下的其他服务器则成为Follower服务器。Leader服务器负责将一个客户端事务请求转换成一个事务Proposal（提议），并将该Proposal分发给集群中所有的Follower服务器。之后Leader服务器需要等待所有Follower服务器的反馈，一旦超过半数的Follower服务器进行了正确的反馈后，那么Leader就会再次向所有的Follower服务器分发Commit消息，要求将前一个Proposal进行提交。
Leader选举算法要保证新选举出来的Leader服务器拥有集群中所有机器最高编号（即ZXID最大）的事务proposal，那么就可以保证这个新选举出来的Leader一定具有所有已经提交的proposal。未更重要的是，如果让具有最高编号事务proposal的机器来成为Leader，就可以省去Leader服务器检查proposal的提交和丢弃工作的这一步操作了。
ZXID设计：ZXID是一个64位的数字，其中低32位可以看作是一个简单的单调递增的计数器，针对客户端的每一个事务请求，Leader服务器在产生一个新的事务proposal的时候，都会对该计数器进行加1操作； 而高32位则代表Leader周期epoch的编号，每当选举产生一个新Leader服务器，就会从这个Leader服务器上取出其本地日志中最大事务proposal的ZXID，并从ZXID中解析出对应的epoch值，然后再对其进行加1操作，之后就以此编号作为新的epoch，并将低32位置0来生成新的ZXID。
