1.CAP理论
1.1 CAP理论介绍
CAP理论又称CAP原则，指的是在一个分布式系统中， Consistency（一致性）、 Availability（可用性）、Partition tolerance（分区容错性），三者不可得兼。
1.2 CAP三个特性
一致性（C）：在分布式系统中的所有数据备份，在同一时刻是否同样的值。（等同于所有节点访问同一份最新的数据副本）
可用性（A）：在集群中一部分节点故障后，集群整体是否还能响应客户端的读写请求。（对数据更新具备高可用性）
分区容忍性（P）：以实际效果而言，分区相当于对通信的时限要求。系统如果不能在时限内达成数据一致性，就意味着发生了分区的情况，必须就当前操作在C和A之间做出选择
1.3 取舍策略
CAP三个特性只能满足其中两个，那么取舍的策略就共有三种：
CA without P：如果不要求P（不允许分区），则C（强一致性）和A（可用性）是可以保证的。但放弃P的同时也就意味着放弃了系统的扩展性，也就是分布式节点受限，没办法部署子节点，这是违背分布式系统设计的初衷的。传统的关系型数据库RDBMS：Oracle、MySQL就是CA。
CP without A：如果不要求A（可用），相当于每个请求都需要在服务器之间保持强一致，而P（分区）会导致同步时间无限延长(也就是等待数据同步完才能正常访问服务)，一旦发生网络故障或者消息丢失等情况，就要牺牲用户的体验，等待所有数据全部一致了之后再让用户访问系统。设计成CP的系统其实不少，最典型的就是分布式数据库，如Redis、HBase、ZooKeeper等。对于这些分布式数据库来说，数据的一致性是最基本的要求，因为如果连这个标准都达不到，那么直接采用关系型数据库就好，没必要再浪费资源来部署分布式数据库。
AP wihtout C：要高可用并允许分区，则需放弃一致性。一旦分区发生，节点之间可能会失去联系，为了高可用，每个节点只能用本地数据提供服务，而这样会导致全局数据的不一致性。典型的应用就如某米的抢购手机场景，可能前几秒你浏览商品的时候页面提示是有库存的，当你选择完商品准备下单的时候，系统提示你下单失败，商品已售完。这其实就是先在 A（可用性）方面保证系统可以正常的服务，然后在数据的一致性方面做了些牺牲，虽然多少会影响一些用户体验，但也不至于造成用户购物流程的严重阻塞。
2.Paxos算法
通过CAP理论我们知道分布式系统是不可能同时满足三大特性，而ZooKeeper设计的架构是以牺牲可用性来保证数据的一致性也就是我们常说的CP,这个章节来介绍一下一致性算法Paxos
2.1 为什么需要一致性
数据不能存在单个节点上，否则可能出现单点故障。
多个节点需要保证具有相同的数据。
2.2 什么是paxos算法
Paxos算法是莱斯利·兰伯特在1990年提出的一种基于消息传递并且具有高度容错特性的一致性算法，是目前公认的解决分布式问题上最有效的算法之一。
核心一句话：paxos是一种基于消息传递的，具有高容错的一致性算法。
2.3 解决了什么问题
主要解决分布式系统中，如何就某个决策达成一致性的问题。主要的工程实现：ZAB，GoogleChubby、微信的 PhxPaxos。
2.4 Paxos的三种角色
在paxos算法中有三种角色，每种角色有不同的功能。但很多时候，一个进程可能充当多种角色。Proposal是提案，处理提案会涉及到三种角色：
Proposer：提案者
Accecptor：决策者
Learner：学习者，同步者
2.5 Paxos算法
我们首先来看一下，对于一个一致性算法来说，我们应该满足哪几点：
所有提出的提案最终只有一个被选定
如果没有提案，那么最终没有任何选定的提案
当提案被选定后，所有客户端都应该能获取到提案信息
在Paxos算法中，有Proposer（提案者）、Acceptor（决策者）以及Learner（学习者/同步者）三种角色，彼此之间通过收发消息来实现通信。在分布式场景下，Acceptor绝不可能只有一个实例存在，防止出现单机故障，因此我们需要满足，多个Acceptor的情况下完成选举操作，因此我们可以指定Proposer都向一个Acceptor集合中发送提案，而这个集合中的所有的Acceptor都可能批准提案，当有足够多的Acceptor批准提案的时候(多数派)，我们就认为这个提案被选定，而所谓的足够多，只需要满足当前Acceptor集合中的大半Acceptor批准提案即可，并且我们规定每个Acceptor在一次选举过程中，只可以批准一个提案。
2.6 Paxos算法过程
整个Paxos算法的过程可以总结为两阶段提交的算法执行过程，分为Prepare请求阶段和Accept请求阶段
2.6.1 Prepare阶段
Proposer会选择一个提案，并且编号为M0,然后向Acceptor集合中发送M0编号的Prepare请求，如果这个时候Acceptor集合中的某个Acceptor收到了这个请求，并且编号M0比当前已经相应的所有的提案的最大编号还要大，那么Acceptor就需要反馈自己处理的最大编号，并且不会再去响应低于M0编号的任何请求。如果没有响应过请求，则会直接响应当前的M0编号的请求。
2.6.2 Accept阶段
同样的，当Proposer发出的提案请求收到了来自整个Acceptor集合中的过半Acceptor的响应，那么就代表该提案可以生成，这个时候如果响应中过半是无任何提案信息的，则代表当前的提案的取值可以是任意值，如果响应中过半是其他的提案信息，那么则从中找到最大编号的提案的值，这里称为V0，组成M0,V0的Acceptor请求，再次发送给整个Acceptor集合。这个时候Acceptor如果没有通过大于V0 编号的提案，那么则会视为自动同意该提案，同样如果得到了过半数的同意，则当前提案视为通过。
当然在整个过程中，每个Proposer都有自己的周期定时生成不同的提案，并且严格按照上述过程运行，最终一定能保证算法的正确性，同样的，如果Proposer已经要生成更大编号的提案，Accept将收到的最大的编号信息通知给上一个同意的最大提案的Proposer，让其放弃自己的提案，选择最新的最大编号的提案即可。
3.ZAB协议
3.1 ZAB协议
看了前面的Paxos算法，我们可能会认为Zookeeper就是基于Paxos算法的实现，但是事实上，Zookeeper并不是完全采用的Paxos，而是一种名为ZookeeperAtomic Broadcast，简称ZAB协议，一种支持奔溃恢复的协议作为数据一致性核心算法。
3.2 ZAB三种角色
leader：ZK中写请求的唯一处理者，也能处理读请求；
follower：处理读请求、对leader的提案进行表决、同步leader的结果、具有选举权和被选举权；
observer：没有表决权。只能处理写请求、没有选举和被选举权。
3.3 ZAB协议事务消息的处理流程
ZAB协议定义整个Zookeeper中关于事务消息的处理流程，大致如下:
所有的Zookeeper处理的事务请求必须仅有一个机器来协调处理，这样的机器被称之为Leader服务器，而剩下的其他Zookeeper则称之为Follower，而Leader服务器则是会将客户端的事务请求发给所有的Follwer服务器，等待所有的Follwer服务器的反馈，一旦接受到了超过半数的Follwer服务器的正常完成事物处理的反馈后，Leader服务器就会再次发送一个Commit消息给所有的Follwer服务器，要求将刚刚的事物请求进行提交。
3.4 ZAB协议模式
ZAB协议有两种基本的模式，分别为崩溃恢复和消息广播。当整个框架在运行的过程中，或者是当Leader出现网络中断、崩溃重启等异常的情况的时候，ZAB协议就会进入恢复模式，来重新选举一个新的Leader服务器来处理事务请求，当新的Leader服务器选择出来，并且和过半以上的机器实现了状态同步后，ZAB的恢复模式就结束了。这个时候就可以进行ZAB的消息广播模式了，如果在这个过程中有一个新的Zookeeper加入了当前的集群中，就会启动恢复模式，直到实现了和Leader的状态同步为止。
正如上述事务处理的过程一样，Zookeeper中只有Leader可以协调处理事务请求，那么其他的Follower服务器是不是没用了呢？
当然不是，在整个ZooKeeper集群中，所有的服务器都可以提供对外的请求处理，唯一的区别在于，当Follower服务器接受到了事务请求以后，会转发给Leader，让Leader进行统一处理和协调而已。当然在整个集群的运行过程中会出现很多意外，例如有半数以上的Follower服务器无法与Leader进行正常通信，就会从消息广播模式进入到崩溃恢复模式，从其他的机器中选举一个新的Leader出来,同样的一个Leader的选举必须得到超过半数的机器的支持，所以当整个集群的正常服务的机器超过半数，都可以不停的模式转换，保证集群服务的稳定性，一旦出现问题的机器数量超过了集群的半数，整个集群就不再对外提供事务请求的处理，进入保护模式，仅仅可读。
4.扩展阅读
BASE理论
BasePaxos 和 Muli Paxos
Raft算法
评论区