CNDBA社区
在之前的博客我们了解到了数据库的分类，
数据库的三种分类说明：SQL / NoSQL / 分布式NewSQL
https://www.cndba.cn/dave/article/4579
NewSQL 分布式数据库需要遵守CAP 理论 和 BASE理论。因此分布式系统的架构设计过程中，往往需要对一致性和可用性 CA之间进行反复的权衡，基于此产生一系列的一致性协议和算法，其中比较有名的就是两阶段提交协议、三阶段提交协议、Paxos算法、Raft 算法。
1 两阶段提交 2PC（Two-Phase Commit）
2PC是为了使分布式系统架构下的所有节点进行实务的过程中能够保持原子性和一致性的而设计的一种算法。
1.1 2PC 阶段一 : 提交实务请求
(1)协调者向所有的参与者发送实务内容，询问是否可以实务操作，并等待参与者的响应
(2)各参与者节点执行实务，注意这时候只是执行了事务，事务并未提交，然后参与者向协调者反馈，如果执行成功返回OK，否则NO
1.2 2PC 阶段二 : 执行事务提交
(1)如果所有参与者的反馈都是OK，那么执行事务提交，协调者向所有参与者发出commit请求。
(2)参与者收到commit请求之后执行实务提交，执行完之后向协调者反馈ACK信息（Acknowledge 确认信息）。
(3)协调者收到所有参与者的ACK反馈之后，完成事务。
如果在第一阶段中有参与者的反馈是NO的话，那么需要中断事务：
(1)协调者向所有参与者发送回滚请求rollback
(2)所有参与者收到回滚请求rollback之后回滚事务，并在回滚之后反馈结果
(3)协调者收到所有参与者的反馈，事务中断完成
1.3 二阶段提交存在的问题：
(1)同步阻塞，执行过程中，所有参与节点都是事务阻塞型的，各个参与者在等待其他参与者的响应过程中无法进行其他操作
(2)单点问题，协调者的角色很重要，一旦协调者出现问题，整个过程都无法继续，如果在阶段二中出现问题，参与者将一直处于锁定事务资源的状态中，无法继续完成事务操作
(3)数据不一致 ，在阶段二的时候，当协调者向所有参与者发送Commit请求之后，发生了网络异常，导致只有部分参与者收到了Commit请求，于是，这部分收到了Commit请求的参与者提交了事务，而其他没有收到Commit请求的参与者则无法提交事务，导致整个系统出现了数据不一致现象
2 三阶段提交 ，3PC
三阶段提交是两阶段提交的改进型，进行了如下改进：
(1)引入了超时机制
(2)在2PC的第一阶段和第二阶段中插入了一个准备阶段，将提交事务请求一分为二
3PC由：CanCommit, PreCommit, DoCommit三个阶段组成
2.1 阶段一 ：CanCommit
(1)协调者向所有参与者发送CanCommit请求，询问是否可以执行事务提交操作，并等待参与者的反馈
(2)各个参与者收到协调者的CanCommit请求之后，查看自身状态是否可以顺利执行事务，正常返回OK，否则NO
2.2 阶段二 ：PreCommit
如果阶段一各参与者反馈OK,开始阶段二
(1)协调者向所有参与者发送PreCommit请求，进入Prepared阶段
(2)参与者收到preCommit请求后，执行事务操作，将Undo和Redo记录到事务日志，这时候并未commit事务，然后向协调者反馈，返回OK or NO
如果任意一个参与者返回了NO，或者协调者等待参与者反馈超时，这时候中断事务：
(1)协调者向所有参与者发送abort请求
(2)参与者收到abort请求，或者等待协调者请求出现超时都会abort事务
2.3 阶段三 ：DoCommit
这时候开始进行真正的事务提交，如果阶段二中所有参与返回OK，则：
(1)协调者从Prepared状态进入Commit状态，向所有参与者发送DoCommit请求
(2)参与者收到协调者的DoCommit请求时候，进行事务提交，并返回信息给协调者
(3)协调者收到所有参与者的反馈后，完成事务
如果这个阶段协调者正常工作，并且任意一个参与者返回了NO，或者协调者等待参与者反馈超时，这时候中断事务：
(1)协调者向所有参与者发送abort请求
(2)参与者收到abort请求后，会根据在阶段二中记录的undo信息执行事务回滚，之后反馈协调者
(3)协调者收到所有参与者反馈，中断事务
需要注意的是，一旦进入阶段三，可能存在下面两种故障：
(1)协调者出现问题
(2)协调者和参与者之间出现网络故障
无论出现上述哪种情况，都会导致参与者无法及时接收到协调者的doCommit或者abort请求，这时候参与者会在等待超时之后进行事务的提交
三阶段的优点：
相比两阶段，降低了参与者的阻塞范围，并且能够在出现单点故障后继续达到一致
三阶段的缺点：
参与者接收到preCommit请求之后，如果出现网络分区问题，此时协调者和参与者无法通信，这时候该参与者依然会进行事务的提交，会导致数据不一致。
3 选主算法
Consensus一致性这个概念是指多个服务器在状态达成一致，但是在一个分布式系统中，因为各种意外可能，有的服务器可能会崩溃或变得不可靠，它就不能和其他服务器达成一致状态。这样就需要一种Consensus协议，一致性协议是为了确保容错性，也就是即使系统中有一两个服务器当机，也不会影响其处理过程。
为了以容错方式达成一致，我们不可能要求所有服务器100%都达成一致状态，只要超过半数的大多数服务器达成一致就可以了，假设有N台服务器，N/2 +1 就超过半数，代表大多数了。
Paxos和Raft都是为了实现Consensus一致性这个目标，这个过程如同选举一样，参选者需要说服大多数选民(服务器)投票给他，一旦选定后就跟随其操作。Paxos和Raft的区别在于选举的具体过程不同。
3.1 Paxos算法
Paxos算法的核心是一个一致性算法，是一个经典、完备的分布式一致性算法，其目标是在不同的节点之前，对同一个key的取值达成共识。
在Paxos算法中，有如下三种角色：
(1)Proposer 提案者，对key值提出自己的值
(2)Acceptor 决议者，对提案者的提议进行投票，选定一个提案形成最终的决策
(3)Leaner 学习者，学习决议者达成共识的决策
Paxos算法分为两个阶段：
阶段一 准备阶段：Prepare请求
Porposer选择一个新的提案编号N，然后向Acceptor过半集合成员发送Prepare请求，要求该集合中的Acceptor做出如下回应：
(1) 向Proposer承诺，保证不再批准任何编号小于N的提案
(2) 如果Acceptor已经批准过任何提案，那么就应该向Proposer反馈当前Acceptor已经批准的编号小于N的最大的提案的值
阶段二 批准提案：Accept请求
1）如果Proposer收到了来自半数以上的Acceptor的响应结果，那么就可以产生编号为N，Value值为Vn的天，这里的Vn死所有相中编号最大的提案的值，如果半数以上的Acceptor都没有批准过任何提案，这时候Vn的值由Proposer任意选择
2) 如果Acceptor收到了[N ,Vn]的提案的Accept请求，只要改Acceptor尚未对编号大于N的天的Prepare请求做出响应，它就可以通过这个提案
Paxos协议中一个提案被通过后，这个提案的值被选中，后面按照协议继续交互下去，这个值一直保持不变，也就是一直一致，其目标是保证最终有一个提案会被通过，提案通过后，其他Acceptor最终也只能获取通过的提案，一言蔽之，将所有节点都写入同一个值，且被写入后不再更改。
Paxos 活锁：两个Proposer交替请求，编号不断变大，但是无法通过任何一个提案。
3.2 Raft算法
Raft算法是Paxos算法的一种简化实现，有三种角色
(1) Leader 领导者，所有写入都是通过leader写入，同时leader会强制所有follower来同步数据
(2) Candidate 选举的状态，会向其他所有节点拉选票，如果得到大部分选票，则会变成Leader
(3) Follower 所有节点开始都是Follower状态，如果没有收到Leader的消息则会变成Candidate
其他概念：
(1)Term： 连续单调递增的编号，每个term代表一轮选举
(2)随机心跳时间：Follower节点每次收到Leader节点心跳请求之后都会设置一个区间在[150ms ,300ms]的超时时间，如果超过这个时间还没收到心跳，则认为Leader故障
Raft算法是通过选出一个Leader来简化副本之间的数据同步，将一致性分为了两个重要个子逻辑：
(1) Leader选举
(2) 日志复制
3.2.1 Leader选举过程
(1)当Follower节点在超时时间内没有收到Leader心跳，则认为当前Leader故障，将从Follower状态变为Candidate,更新本地的Current Term值，同时批量向其他节点发送拉票请求
(2)其他Follower节点收到请求后，判断请求的Term大于自己的Current Term，且请求的log序号不低于本地，则认为这张票是合法的（每轮term只能投一次票）
(3)如果Candidate收到了超过半数的投票，则晋升为Leader，同时立刻给所有节点发送消息，避免其余节点触发新的选举，然后开始日志同步、处理客户端请求
3.2.2 日志复制
(1)Leader收到客户端的数据请求后，先把数据写到本地日志（这时候尚未提交），同时向Follower节点发送AppendEntries，将请求的数据发送给Follower
(2)Follower收到请求数据判断如果没有冲突的话，则将数据写入日志（未提交），然后反馈给Leader
(3)Leader收到Follower的反馈如果超过半数成功，则提交本地未提交的事务，（这时候就可以给客户端响应了），然后向Follower再次发送AppendEntries请求
(4)Follower收到请求后提交本地事务
4 Zookeeper 分布式的协调服务
zookeeper作为一个分布式的协调服务，实现的是CP，实现了最终一致性。
在zookeeper中有如下几个角色：
(1) Leader节点，领导者，集群所有的写入都通过leader写入，维护与Follower和Observer之间的心跳，同时会将写入的数据广播给其他节点，zookeeper集群同一时间只会有一个工作的Leader
(2) Follower节点，与Leader保持心跳，Follower节点可以直接处理客户端的读请求，可以接受写请求，但是无法处理读请求，会将读请求转发给Leader进行处理。另外还会参与投票，包含Leader写请求的投票以及选主的投票
(3) Observer节点，与Follower基本一样，但是没有投票权
zookeeper的核心是原子广播（zookeeper automic broadcast，ZAB原子消息广播协议）。讲解这部分之前，我们先了解zk中几个属性：
(1) myid，每个zk节点在集群中的唯一id，我们在安装配置zk的时候都会写入一个唯一id到myid的配置文件汇总
(2) zxid，zk的事务id，用来表示每次更新操作的提案（Proposal ID），该ID单调递增，保证了顺序一致性，zk使用64位来表示zxid，其中高32位表示Leader的epoch，从1开始，每次Leader变化选出新的Leader之后，epoch 加一，低32位表示的是该epoch内的事务id，单调递增，每次epoch发生改变，低32位重置。
zk为了保证提案的按zxid顺序生效，使用了一个ConcurrentHashMap，记录所有未提交的提案，key为zxid，value为提案的信息。当有事务发生的时候，Leader节点会把数据通过proposal请求发送到所有的节点上面，所有收到proposal的节点接收到数据以后会把数据写入到本地磁盘，然后发送ACK给leader，leader节点判断过半节点都返回了ACK，会发送commit消息给各个节点，各节点就会把消息放入内存中。
可以看到，zk的写操作，类似两阶段提交。
zk在选主的时候，会向集群中其他节点发送下面的信息：
(1)logicClock，灭节点维护的自增整数，表示的是当前节点发起的第多少轮投票，zk的每次选举必须在同一轮中，就是logicClock必须一致
(2)state 当前节点的状态
(3)self_id 当前节点的myid
(4)self_zxid 当前节点上保存数据的最大的zxid
(5)vote_id 被推举的节点的myid
(6)zote_zxid 被推举的节点保存的数据的最大zxid
选主大致流程：
(1)每个节点在开始投票的时候会将自己的logicClock自增加一
(2)清空节点自身的投票箱
(3)发送投票给自己，初始的时候，每个节点都是投给自己
(4)接收外部投票
(5)收到外部投票后，判断选举轮次logicClock，
- 如果当前节点的logicClock比收到logicClock小，更新当前节点logicClock到收到的logicClock，然后在比较之前的投票与当前投票确定是否需要变更自己的投票，然后将自己的投票广播出去
- 外部投票的logicClock小于当前节点的logicClock，直接忽略该投票
- 外部投票的logicClock与当前节点的logicClock相等，进行选票处理
(6)选票处理。选票的处理是基于（self_id,self_zxid)与（vote_id,vote_zxid)，首先比较外部选票与自己的选票的self_zxid，如果外部选票的vote_zxid比自己的选票的vote_zxid大，则将自己手中的选票的vote_id,vote_zxid都更新为收到的外部选票；如果这两张选票的vote_zxid一致，则比较二者的vote_myid，哪个大，将vote_id,vote_zxid更新为vote_zxid大的那个信息，然后将自己的选票广播出去
(7)统计选票，若有过半的服务器认可了自己的投票，则终止投票
(8)更新节点状态
zk集群节点存在四种状态：
(1)LOOKING，一般这时候没有确定Leader，会发起选主
(2)LEADING，领导者状态，当前节点是Leader节点
(3)FOLLOWING，跟随者状态，当前节点是Follower节点
(4)OBSERVERING，观察者状态，当前节点是Observer节点
