分布式协议与算法 01
一致性模型
一致性（Consistency）是指多副本（Replications）问题中的数据一致性。关于分布式系统的一致性模型有以下几种：
强一致性
当更新操作完成之后，任何多个后续进程或者线程的访问都会返回最新的更新过的值，直到这个数据被其他数据更新为止。
但是这种实现对性能影响较大，因为这意味着，只要上次的操作没有处理完，就不能让用户读取数据。
弱一致性
系统并不保证进程或者线程的访问都会返回最新更新过的值。系统在数据写入成功之后，不承诺立即可以读到最新写入的值，也不会具体的承诺多久之后可以读到。甚至不能保证可以访问到。
最终一致性
最终一致性也是弱一致性的一种，它无法保证数据更新后，所有后续的访问都能看到最新数值，而是需要一个时间，在这个时间之后可以保证这一点（就是在一段时间后，节点间的数据会最终达到一致状态），而在这个时间内，数据也许是不一致的，这个系统无法保证强一致性的时间片段被称为「不一致窗口」。不一致窗口的时间长短取决于很多因素，比如备份数据的个数、网络传输延迟速度、系统负载等。
最终一致性在实际应用中又有多种变种：
分布式事务
分布式事务是指会涉及到操作多个数据库的事务。其实就是将对同一库事务的概念扩大到了对多个库的事务。目的是为了保证分布式系统中的数据一致性。分布式事务处理的关键是必须有一种方法可以知道事务在任何地方所做的所有动作，提交或回滚事务的决定必须产生统一的结果（全部提交或全部回滚）
在分布式系统中，各个节点之间在物理上相互独立，通过网络进行沟通和协调。由于存在事务机制，可以保证每个独立节点上的数据操作可以满足ACID。但是，相互独立的节点之间无法准确的知道其他节点中的事务执行情况。所以从理论上讲，两台机器理论上无法达到一致的状态。如果想让分布式部署的多台机器中的数据保持一致性，那么就要保证在所有节点的数据写操作，要不全部都执行，要么全部的都不执行。但是，一台机器在执行本地事务的时候无法知道其他机器中的本地事务的执行结果。所以他也就不知道本次事务到底应该commit还是 roolback。所以，常规的解决办法就是引入一个“协调者”的组件来统一调度所有分布式节点的执行。
2PC ， 3PC， paxos
2PC
它可以保证在分布式事务中，要么所有参与进程都提交事务，要么都取消事务，即实现 ACID 的原子性（A）。
在数据一致性中，它的含义是：要么所有副本（备份数据）同时修改某个数值，要么都不更改，以此来保证数据的强一致性。
2PC分为2个阶段：
表决阶段：
1、事务询问
Coordinator （协调者）向所有的参与者发送一个 vote request
2、执行事务
各个参与者节点执行事务操作,并讲Undo和Redo信息记入事务日志中
3、各参与者向协调者反馈事务询问的响应.
如果参与者成功执行了事务操作,那么就反馈给协调者vote_commit响应,表示事务可以执行,如果没有参与者成功执行事务,那么就反馈给协调者vote_abort响应,表示事务不可以执行.
提交阶段：
Coordinator 收到所有参与者的表决信息，如果所有参与者一致认为可以提交事务，那么 Coordinator 就会发送 GLOBAL_COMMIT 消息，否则发送 GLOBAL_ABORT 消息；对于参与者而言，如果收到 GLOBAL_COMMIT 消息，就会提交本地事务，否则就会取消本地事务。
2PC优缺点
简单总结一下 2PC 的优缺点：
优点：原理简洁清晰、实现方便；
缺点：同步阻塞、单点问题、某些情况可能导致数据不一致。
关于这几个缺点，在实际应用中，都是对2PC 做了相应的改造：
同步阻塞：2PC 有几个过程（比如 Coordinator 等待所有参与者表决的过程中）都是同步阻塞的，所有参与该事务操作的逻辑都处于阻塞状态，各个参与者在等待其他参与者响应的过程中，将无法进行其他任何操作。在实际的应用中，这个问题是通过超时判断机制来解决的，但并不能完全解决同步阻塞问题；
Coordinator 单点问题：实际生产应用中，Coordinator 都会有相应的备选节点；
数据不一致：这个在前面已经讲述过了，如果在第二阶段，Coordinator 和参与者都出现挂掉的情况下，是有可能导致数据不一致的。
3PC
三阶段提交协议（Three-Phase Commit， 3PC）最关键要解决的就是 Coordinator 和参与者同时挂掉导致数据不一致的问题，所以 3PC 把在 2PC 中又添加一个阶段，这样三阶段提交就有：CanCommit、PreCommit 和 DoCommit 三个阶段。
3PC 过程
CanCommit
1.事务询问协调者向参与者发送CanCommit请求。询问是否可以执行事务提交操作。然后开始等待参与者的响应。
2.响应反馈参与者接到CanCommit请求之后，正常情况下，如果其自身认为可以顺利执行事务，则返回Yes响应，并进入预备状态。否则反馈No
CanCommit 流程不涉及记录undo和redo 日志，只是判断是否能执行事务提交操作。
PreCommit
执行事务预提交：如果 Coordinator 接收到各参与者反馈都是Yes，那么执行事务预提交：
发送预提交请求：Coordinator 向各参与者发送 preCommit 请求，并进入 prepared 阶段；
事务预提交：参与者接收到 preCommit 请求后，会执行事务操作，并将 Undo 和 Redo 信息记录到事务日记中；
各参与者向 Coordinator 反馈事务执行的响应：如果各参与者都成功执行了事务操作，那么反馈给协调者 ACK 响应，同时等待最终指令，提交 commit 或者终止 abort，结束流程；
中断事务：如果任何一个参与者向 Coordinator 反馈了 No 响应，或者在等待超时后，Coordinator 无法接收到所有参与者的反馈，那么就会中断事务。
发送中断请求：Coordinator 向所有参与者发送 abort 请求；
中断事务：无论是收到来自 Coordinator 的 abort 请求，还是等待超时，参与者都中断事务
doCommit
执行提交
发送提交请求：假设 Coordinator 正常工作，接收到了所有参与者的 ack 响应，那么它将从预提交阶段进入提交状态，并向所有参与者发送 doCommit 请求；
事务提交：参与者收到 doCommit 请求后，正式提交事务，并在完成事务提交后释放占用的资源；
反馈事务提交结果：参与者完成事务提交后，向 Coordinator 发送 ACK 信息；
完成事务：Coordinator 接收到所有参与者 ack 信息，完成事务。
在doCommit阶段，如果参与者无法及时接收到来自协调者的doCommit或者rebort请求时，会在等待超时之后，会继续进行事务的提交。（其实这个应该是基于概率来决定的，当进入第三阶段时，说明参与者在第二阶段已经收到了PreCommit请求，那么协调者产生PreCommit请求的前提条件是他在第二阶段开始之前，收到所有参与者的CanCommit响应都是Yes。（一旦参与者收到了PreCommit，意味他知道大家其实都同意修改了）所以，一句话概括就是，当进入第三阶段时，由于网络超时等原因，虽然参与者没有收到commit或者abort响应，但是他有理由相信：成功提交的几率很大。 ）
中断事务：假设 Coordinator 正常工作，并且有任一参与者反馈 No，或者在等待超时后无法接收所有参与者的反馈，都会中断事务
发送中断请求：Coordinator 向所有参与者节点发送 abort 请求；
事务回滚：参与者接收到 abort 请求后，利用 undo 日志执行事务回滚，并在完成事务回滚后释放占用的资源；
反馈事务回滚结果：参与者在完成事务回滚之后，向 Coordinator 发送 ack 信息；
中断事务：Coordinator 接收到所有参与者反馈的 ack 信息后，中断事务。
3PC 分析
3PC 虽然解决了 Coordinator 与参与者都异常情况下导致数据不一致的问题，3PC 依然带来其他问题：比如，网络分区问题，在 preCommit 消息发送后突然两个机房断开，这时候 Coordinator 所在机房会 abort, 另外剩余参与者的机房则会 commit。
而且由于3PC 的设计过于复杂，在解决2PC 问题的同时也引入了新的问题，所以在实际上应用不是很广泛。
2PC与3PC的区别
相对于2PC，3PC主要解决的单点故障问题，并减少阻塞，因为一旦参与者无法及时收到来自协调者的信息之后，他会默认执行commit。而不会一直持有事务资源并处于阻塞状态。但是这种机制也会导致数据一致性问题，因为，由于网络原因，协调者发送的abort响应没有及时被参与者接收到，那么参与者在等待超时之后执行了commit操作。这样就和其他接到abort命令并执行回滚的参与者之间存在数据不一致的情况。
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
什么是 paxos 算法。
Paxos算法是莱斯利·兰伯特（Leslie Lamport，就是 LaTeX 中的"La"，此人现在在微软研究院）于1990年提出的一种基于消息传递的一致性算法。
一、proposer prepare一个编号Mn的提案，然后发给超过半数的acceoptor子集
二、1个acceptor收到Mn的提案，如果编号没有超过Mn，会接受这个提案，通过承诺不接受比Mn小的编号请求
三、proposer收到半数以上Acceptor的响应，会发送对应的accept请求，附上[Mn,v0]，acceptor如果没有比Mn编号大的
prepare做出响应，就accept这个方案
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
learner 获取提案（学习策略）
- 一旦提案被批准（过半），则发送给所有learner；
- 提案批准，则发送给一个learner，该learner再发送给其他learner；
- 提案批准，则发送给一个learner集合，该learner集合再发送给其他learner；
优化
问题：proposer1 与 proposer2 两者陷入死循环；
解决：选出主proposer，只要主proposer 和 过半acceptor 能保持正常，那么但凡主proposer 能提出一个编号更高的提案，这个提案最终将会批准；
应用
chubby：分布式锁、GFS 中 master 选举
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++=
Paxos
Paxos是一种提高分布式系统容错性的一致性算法，也可以说是最著名的一致性算法了。甚至Google Chubby的作者Mike Burrows说过这个世界上只有一种一致性算法，那就是Paxos，其它的算法都是残次品。
Paxos算法也是出了名的难理解，但它本质上也是个分两阶段提交的选举算法，利用了鸽巢原理，遵循“过半与最新”原则。
阶段一:Prepare阶段
1.1【倡议者视角】倡议者选择倡议编号n，然后向大多数（即超过半数以上）接受者发送Prepare请求，请求中附带倡议编号n。
1.2【接受者视角】对于某个接受者来说，如果接收到带有倡议编号n的Prepare请求，则做如下判断：若倡议编号n比此接受者之前响应过的任何其它Prepare请求附带的倡议编号都大，那么此接受者会给倡议者以响应，并承诺不会响应之后接收到的其它任何倡议编号小于n的请求，另外，如果接受者曾经响应过2.2阶段的Accept请求，则将所有响应的Accept请求中倡议编号最高的倡议内容发送给倡议者，倡议内容包括两项信息：Accept请求中的倡议编号以及其倡议值。若倡议编号n不比此接受者之前响应过的任何其它Prepare请求附带的倡议编号都大，那么此接受者不会给倡议者以响应。
阶段二:Accept阶段
2.1【倡议者视角】如果倡议者接收到过半接受者关于带有倡议编号n的Prepare请求的响应，那么倡议者向这些接受者发送Accept请求，Accept请求附带两个信息：倡议编号n以及倡议值v。倡议值v的选择方式如下：如果在1.2阶段接受者返回了自己曾经接受的具有最高倡议编号Accept请求倡议内容，则从这些倡议内容里面选择倡议编号最高的并将其倡议值作为倡议值v；如果1.2阶段没有收到任何接受者的Accept请求倡议内容，则可以自主任意赋值给倡议值v。
2.2【接受者视角】如果接受者接收到了任意倡议编号为n的Accept请求，则接受者接受此请求，除非在此期间接受者响应过具有比n更高编号的Prepare请求。这里有个特点，一旦接受了Accept请求后，这个倡议值v值就定下了。
通过以上两阶段过程即可选出唯一的倡议值，对于学习者来说，其需要从接受者那里获知到底是哪个倡议值被选出。一个直观的方法如下：每当接受者执行完2.2步骤，即接受某个Accept请求后，由其通知所有学习者其所接受的倡议，这样，学习者很快习得是哪个倡议被最终选出。但是这种方式会导致大量通信，因为任意一个接受者会通知任意一个学习者，如果有m个接受者，n个学习者，则需要m*n次通信。一个替代策略是：从众多学习者中选择一个作为代表，由其从接受者那里获知最终被选出的倡议，然后再由其通知其它学习者，这样可以将通信量降为m+n。但是这个方案中如果这个学习者代表发生故障，其它学习者无从知晓倡议值。考虑到健壮性和通信量两个因素，可以采取折中方法：选出若干学习者作为代表，由这些代表从接受者那里获知最终倡议值，然后通知其它学习者。
通过以上流程，如果有多个并发进程提出各自的倡议值，Paxos就可以保证从中选出且只选出一个唯一确定的倡议值，以此来达到副本状态机保持状态一致的目标。
此文只是对Paxos的应用场景以及Paxos协议本身进行了介绍，而Paxos最难理解性在于是什么因素导致协议以此种方式呈现以及其正确性证明过程而非最终协议本身内容。
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
ZAB
ZAB(Zookeeper Atomic Broadcast)协议是专门为zookeeper设计的一致性协议。为什么没有直接使用Paxos算法呢？这里就要说到Paxos算法的缺点了。
Paxos算法虽然通用，可靠，但终归效率太低。Paxos算法在出现竞争的情况下，其收敛速度很慢，甚至可能出现活锁的情况，例如当有三个及三个以上的proposer在发送prepare请求后，很难有一个proposer收到半数以上的回复而不断地执行第一阶段的协议。因此，为了避免竞争，加快收敛的速度，在算法中引入了一个Leader这个角色，在正常情况下同时应该最多只能有一个参与者扮演Leader角色，而其它的参与者则扮演Acceptor的角色。
在这种优化算法中，只有Leader可以提出议案，从而避免了竞争使得算法能够快速地收敛而趋于一致；而为了保证Leader的健壮性，又引入了Leader选举，再考虑到同步。
ZAB协议包括两种基本的模式：崩溃恢复和消息广播
当整个服务框架在启动过程中，或是当Leader服务器出现网络中断崩溃退出与重启等异常情况时，ZAB就会进入恢复模式并选举产生新的Leader服务器。
当选举产生了新的Leader服务器，同时集群中已经有过半的机器与该Leader服务器完成了状态同步之后，ZAB协议就会退出崩溃恢复模式，进入消息广播模式。
当有新的服务器加入到集群中去，如果此时集群中已经存在一个Leader服务器在负责进行消息广播，那么新加入的服务器会自动进入数据恢复模式，找到Leader服务器，并与其进行数据同步，然后一起参与到消息广播流程中去。
以上其实大致经历了三个步骤：
1.崩溃恢复：主要就是Leader选举过程。
2.数据同步：Leader服务器与其他服务器进行数据同步。
3.消息广播：Leader服务器将数据发送给其他服务器。