文章摘要(AI生成)

CAP定理指出，在一个分布式系统中，一致性、可用性和分区容错性这三个特性无法同时满足。分布式系统的一致性表示多个主机之间的数据是否保持一致；可用性表示系统能够在有限时间内对用户请求做出响应；分区容错性表示系统在网络分区故障时依然能够保证一致性和可用性。CAP原则指出，分布式系统只能满足一致性和可用性中的两项，即CP或者AP。BASE理论是CAP定理的权衡结果，它通过允许系统在出现故障时损失部分可用性，以及允许数据存在中间状态来实现最终一致性。Zookeeper遵循CP原则，实现了一致性但牺牲了可用性。Zookeeper内部使用的一致性协议是ZAB协议，它是对PAXOS算法的一种实现，用于达成分布式系统中的决议一致。PAXOS算法通过分配唯一编号和记录已接受提案来保证一致性。

CAP定理

CAP定理指的是在一个分布式系统中，Consistency（一致性）、Availability（可用性）、Partitiontolerance（分区容错性），三者不可兼得。

• 一致性（C）：分布式系统中多个主机之间是否能够保持数据一致的特性。即，当系统数据发生更新操作后，各个主机中的数据仍然处于一致的状态。
• 可用性（A）：系统提供的服务必须一直处于可用的状态，即对于用户的每一个请求，系统总是可以在有限的时间内对用户做出响应。
• 分区容错性（P）：分布式系统在遇到任何网络分区故障时，仍能够保证对外提供满足一致性和可用性的服务。

对于分布式系统，网络环境相对是不可控的，出现网络分区是不可避免的，因此系统必须具备分区容错性。但其并不能同时保证一致性与可用性。CAP原则对于一个分布式系统来说，只可能满足两项，即要么CP，要么AP。

BASE理论

BASE是BasicallyAvailable（基本可用）、Softstate（软状态）和Eventuallyconsistent（最终一致性）三个短语的简写。是CAP定理对于一致性与可用性权衡的结果。BASE理论的核心思想是：即使无法做到强一致性，但每个系统都可以根据自身的业务特点，采用适当的方式来使系统达到最终一致性。

• 基本可用：是指分布式系统在出现不可预知故障的时候，允许损失部分可用性（响应时间与功能上的损失）。
• 软状态：指允许系统数据存在的中间状态，并认为该中间状态的存在不会影响系统的整体可用性，即允许系统主机间进行数据同步的过程存在一定延时
• 最终一致性：系统中所有的数据副本，在经过一段时间的同步后，最终能够达到一个一致的状态。

ZK的一致性协议

zookeeper遵循的是 CP 原则，即保证了一致性，但牺牲了可用性（集群选举时不可用）。ZK内部的一致性协议是ZAB协议，他是对PAXOS算法的一种实现，首先需要了解下PAXOS算法

PAXOS算法

Paxos算法要解决的问题是，在信道安全可靠，消息传递不可修改的前提下，如何通过消息传递在分布式系统中如何就某个决议达成一致。

算法一致性保证：

• 每个提案者在提出提案时都会首先获取到一个具有全局唯一性的、递增的提案编号N，即在整个集群中是唯一的编号N，然后将该编号赋予其要提出的提案。
• 每个表决者在accept某提案后，会将该提案的编号N记录在本地，这样每个表决者中保存的已经被accept的提案中会存在一个编号最大的提案，其编号假设为maxN。每个表决者仅会accept编号大于自己本地maxN的提案。
• 在众多提案中最终只能有一个提案被选定。
• 一旦一个提案被选定，则其它服务器会主动同步(Learn)该提案到本地。
• 没有提案被提出则不会有提案被选定。

prepare阶段

1. 提案者(Proposer)准备提交一个编号为N的提议，于是其首先向所有表决者(Acceptor)发送prepare(N)请求，用于试探集群是否支持该编号的提议。
2. 每个表决者(Acceptor)中都保存着自己曾经accept过的提议中的最大编号maxN。当一个表决者接收到其它主机发送来的prepare(N)请求时，其会比较N与maxN的值。
   1. 若N小于maxN，则说明该提议已过时，当前表决者采取不回应或回应Error的方式来拒绝该prepare请求
   2. 若N大于maxN，则说明该提议是可以接受的，当前表决者会首先将该N记录下来，并将其曾经已经accept的编号最大的提案Proposal(myid,maxN,value)反馈给提案者，以向提案者展示自己支持的提案意愿。其中第一个参数myid表示该提案的提案者标识id，第二个参数表示其曾接受的提案的最大编号maxN，第三个参数表示该提案的真正内容value。当然，若当前表决者还未曾accept过任何提议，则会将Proposal(myid,null,null)反馈给提案者。
   3. 在prepare阶段N不可能等于maxN。这是由N的生成机制决定的。要获得N的值，其必定会在原来数值的基础上采用同步锁方式增一。

示例如下：有提案者1、提案者2两个各提出两个方案，由于本集群中各节点的已存储的最大提案均为【0002：世界】，所以提案者1和提案者2的方案在准备阶段都能被各节点接受。

accept阶段

1. 当提案者(Proposer)发出prepare(N)后，若收到了超过半数的表决者(Accepter)的反馈，那么该提案者就会将其真正的提案Proposal(myid,N,value)发送给所有的表决者。
2. 当表决者(Acceptor)接收到提案者发送的Proposal(myid,N,value)提案后，会再次拿出自己曾经accept过的提议中的最大编号maxN，或曾经记录下的prepare的最大编号，让N与它们进行比较，若N大于等于这两个编号，则当前表决者accept该提案，并反馈给提案者。若N小于这两个编号，则表决者采取不回应或回应Error的方式来拒绝该提议。
3. 若提案者没有接收到超过半数的表决者的accept反馈，则有两种可能的结果产生。一是放弃该提案，不再提出；二是重新进入prepare阶段，递增提案号，重新提出prepare请求。
4. 若提案者接收到的反馈数量超过了半数，则其会向外广播两类信息：
   1. 向曾accept其提案的表决者发送“可执行数据同步信号”，即让它们执行其曾接收到的提案；
   2. 向未曾向其发送accept反馈的表决者发送“提案+可执行数据同步信号”，即让它们接受到该提案后马上执行。

接续上述示例，当两个提案在prepare阶段都被接受时，在accept阶段，两者会并发执行，节点可能会先接受3后接受4，这种情况下在accept阶段，各节点会只接受提案3，提案4会在下个prepare和accept中被接受；但是如果出现先接受4后接受提案3的情况，那么比较就是必须的了：

如上所示，接受者1和2在接受完提案4后，无法在accept阶段无法再接受提案3，此时提案3会被丢弃。保证了在accept阶段各节点只会接受到一个提案：

ZAB协议

Zookeeper使用一个单一主进程来接收并处理客户端的所有事务请求，即写请求。当服务器数据的状态发生变更后，集群采用ZAB原子广播协议，以事务提案Proposal的形式广播到所有的副本进程上。ZAB协议能够保证一个全局的变更序列，即可以为每一个事务分配一个全局的递增编号xid。

ZAB协议主要用于构建一个高可用的分布式数据主从系统，即Follower是Leader的从机，Leader挂了，马上就可以选举出一个新的Leader，但平时它们都对外提供服务。而FastPaxos算法则是用于构建一个分布式一致性状态机系统，确保系统中各个节点的状态都是一致的，提案者可以有多个。

角色

Leader：事务请求的唯一处理者，也可以处理读请求。

Follower：可以直接处理客户端的读请求，并向客户端响应；但其不会处理事务请求，其只会将客户端事务请求转发给Leader来处理；对Leader发起的事务提案具有表决权；同步Leader中的事务处理结果；Leader选举过程的参与者，具有选举权与被选举权。（就好像正式工）

Observer：可以理解为不参与Leader选举的Follower，在Leader选举过程中没有选举权与被选举权；同时，对于Leader的提案没有表决权。用于协助Follower处理更多的客户端读请求。

工作模式

恢复模式-选举与同步

恢复模式具有两个阶段：Leader选举与初始化同步(广播)。当完成Leader选举后，此时的Leader还是一个准Leader，其要经过初始化同步后才能变为真正的Leader。

恢复模式有三个原则：

1. Leader的主动出让原则：若集群中Leader收到的Follower心跳数量没有过半，此时Leader会自认为自己与集群的连接已经出现了问题，其会主动修改自己的状态为LOOKING，去查找新的Leader。
2. 已被处理过的消息不能丢原则：如果在非全部Follower收到COMMIT消息之前Leader就挂了，这将导致一种后果：部分Server已经执行了该事务，而部分Server尚未收到COMMIT消息，所以其并没有执行该事务。当新的Leader被选举出，集群经过恢复模式后需要保证所有Server上都执行了那些已经被部分Server执行过的事务。
3. 被丢弃的消息不能再现原则：新事务已经通过，其已经将该事务更新到了本地，但所有Follower还都没有收到COMMIT之前，Leader宕机了。在该leader恢复后，类似这样应该被丢弃的事务，是不能再次出现在集群中的，应该被清除。

选举

1. 每个Server发出一个投票。然后各自将这个投票发给集群中其他机器。
2. 接受来自各个服务器的投票。集群的每个服务器收到投票后，首先判断该投票的有效性，如检查是否是本轮投票、是否来自LOOKING状态的服务器。
3. 处理投票。针对每一个投票，服务器都需要将别人的投票和自己的投票进行PK，PK规则如下：
   • 优先检查ZXID。ZXID比较大的服务器优先作为Leader。
   • 如果ZXID相同，那么就比较myid。myid较大的服务器作为Leader服务器。

初始化同步

1. 为了保证Leader向Learner发送提案的有序，Leader会为每一个Learner服务器准备一个队列
2. Leader将那些没有被各个Learner同步的事务封装为Proposal
3. Leader将这些Proposal逐条发给各个Learner，并在每一个Proposal后都紧跟一个COMMIT消息，表示该事务已经被提交，Learner可以直接接收并执行
4. Learner接收来自于Leader的Proposal，并将其更新到本地
5. 当Learner更新成功后，会向准Leader发送ACK信息
6. Leader服务器在收到来自Learner的ACK后就会将该Learner加入到真正可用的Follower列表或Observer列表。没有反馈ACK，或反馈了但Leader没有收到的Learner，Leader不会将其加入到相应列表。

工作模式-消息广播

当集群中的Learner完成了初始化状态同步，那么整个zk集群就进入到了正常工作模式了。

1. Leader接收到事务请求后，为事务赋予一个全局唯一的64位自增id，即zxid，通过zxid的大小比较即可实现事务的有序性管理，然后将事务封装为一个Proposal。
2. Leader根据Follower列表获取到所有Follower，然后再将Proposal通过这些Follower的队列将提案发送给各个Follower。
3. 当Follower接收到提案后，会先将提案的zxid与本地记录的事务日志中的最大的zxid进行比较。若当前提案的zxid大于最大zxid，则将当前提案记录到本地事务日志中，并向Leader返回一个ACK。（提问学员）
4. 当Leader接收到过半的ACKs后，Leader就会向所有Follower的队列发送COMMIT消息，向所有Observer的队列发送Proposal。
5. 当Follower收到COMMIT消息后，就会将日志中的事务正式更新到本地。当Observer收到Proposal后，会直接将事务更新到本地。
6. 无论是Follower还是Observer，在同步完成后都需要向Leader发送成功ACK。