# 分布式原理算法

# CAP理论

CAP 也就是 Consistency（一致性）、Availability（可用性）、Partition Tolerance（分区容错性）这三个单词首字母组合。在理论计算机科学中，CAP 定理（CAP theorem）指出对于一个分布式系统来说，当设计读写操作时，只能同时满足以下三点中的两个：

一致性（Consistency） : 所有节点访问同一份最新的数据副本
可用性（Availability）: 非故障的节点在合理的时间内返回合理的响应（不是错误或者超时的响应）。
分区容错性（Partition tolerance） : 分布式系统出现网络分区的时候，仍然能够对外提供服务。

网络分区

分布式系统中，多个节点之前的网络本来是连通的，但是因为某些故障（比如部分节点网络出了问题）某些节点之间不连通了，整个网络就分成了几块区域，这就叫网络分区。

大部分人解释这一定律时，常常简单的表述为：“一致性、可用性、分区容忍性三者你只能同时达到其中两个，不可能同时达到”。实际上这是一个非常具有误导性质的说法，而且在 CAP 理论诞生12年之后，CAP 之父也在2012年重写了之前的论文。

当发生网络分区的时候，如果我们要继续服务，那么强一致性和可用性只能2选 1。也就是说当网络分区之后P是前提，决定了P之后才有 C 和 A 的选择。也就是说分区容错性（Partition tolerance）我们是必须要实现的。

简而言之就是:CAP理论中分区容错性P是一定要满足的，在此基础上，只能满足可用性A或者一致性C

因此，分布式系统理论上不可能选择CA架构，只能选择CP或者AP架构。比如ZooKeeper、HBase就是CP架构，Cassandra、Eureka就是AP架构，Nacos不仅支持CP架构也支持AP架构。

为啥不可能选择CA架构呢？举个例子：若系统出现“分区”，系统中的某个节点在进行写操作。为了保证C，必须要禁止其他节点的读写操作，这就和A发生冲突了。如果为了保证A，其他节点的读写操作正常的话，那就和C发生冲突了。

选择CP还是AP的关键在于当前的业务场景，没有定论，比如对于需要确保强一致性的场景如银行一般会选择保证CP。另外，需要补充说明的一点是: 如果网络分区正常的话（系统在绝大部分时候所处的状态），也就说不需要保证P的时候，C和A能够同时保证。

# Base理论

Base 是三个短语的简写，即基本可用（Basically Available）、软状态（Soft State）和最终一致性（Eventually Consistent）。

基本可用

基本可用比较好理解，就是不追求 CAP 中的「任何时候，读写都是成功的」，而是系统能够基本运行，一直提供服务。基本可用强调了分布式系统在出现不可预知故障的时候，允许损失部分可用性，相比正常的系统，可能是响应时间延长，或者是服务被降级。举个例子，在双十一秒杀活动中，如果抢购人数太多超过了系统的 QPS 峰值，可能会排队或者提示限流，这就是通过合理的手段保护系统的稳定性，保证主要的服务正常，保证基本可用。

软状态

软状态可以对应 ACID 事务中的原子性，在 ACID 的事务中，实现的是强制一致性，要么全做要么不做，所有用户看到的数据一致。其中的原子性（Atomicity）要求多个节点的数据副本都是一致的，强调数据的一致性。原子性可以理解为一种“硬状态”，软状态则是允许系统中的数据存在中间状态，并认为该状态不影响系统的整体可用性，即允许系统在多个不同节点的数据副本存在数据延时。

最终一致性

数据不可能一直是软状态，必须在一个时间期限之后达到各个节点的一致性，在期限过后，应当保证所有副本保持数据一致性，也就是达到数据的最终一致性。在系统设计中，最终一致性实现的时间取决于网络延时、系统负载、不同的存储选型、不同数据复制方案设计等因素。

全局时钟和逻辑时钟

分布式系统解决了传统单体架构的单点问题和性能容量问题，另一方面也带来了很多新的问题，其中一个问题就是多节点的时间同步问题：不同机器上的物理时钟难以同步，导致无法区分在分布式系统中多个节点的事件时序。没有全局时钟，绝对的内部一致性是没有意义的，一般来说，我们讨论的一致性都是外部一致性，而外部一致性主要指的是多并发访问时更新过的数据如何获取的问题。和全局时钟相对的，是逻辑时钟，逻辑时钟描绘了分布式系统中事件发生的时序，是为了区分现实中的物理时钟提出来的概念。

一般情况下我们提到的时间都是指物理时间，但实际上很多应用中，只要所有机器有相同的时间就够了，这个时间不一定要跟实际时间相同。更进一步解释：如果两个节点之间不进行交互，那么它们的时间甚至都不需要同步。因此问题的关键点在于节点间的交互要在事件的发生顺序上达成一致，而不是对于时间达成一致。

数据一致性模型

一般来说，数据一致性模型可以分为强一致性和弱一致性，强一致性也叫做线性一致性，除此以外，所有其他的一致性都是弱一致性的特殊情况。弱一致性根据不同的业务场景，又可以分解为更细分的模型，不同一致性模型又有不同的应用场景。在互联网领域的绝大多数场景中，都需要牺牲强一致性来换取系统的高可用性，系统往往只需要保证“最终一致性”，只要这个最终时间是在用户可以接受的范围内即可。

强一致性

当更新操作完成之后，任何多个后续进程的访问都会返回最新的更新过的值，这种是对用户最友好的，就是用户上一次写什么，下一次就保证能读到什么。根据 CAP 理论，这种实现需要牺牲可用性。

弱一致性

系统在数据写入成功之后，不承诺立即可以读到最新写入的值，也不会具体的承诺多久之后可以读到。用户读到某一操作对系统数据的更新需要一段时间，我们称这段时间为“不一致性窗口”。

最终一致性

最终一致性是弱一致性的特例，强调的是所有的数据副本，在经过一段时间的同步之后，最终都能够达到一个一致的状态。因此，最终一致性的本质是需要系统保证最终数据能够达到一致，而不需要实时保证系统数据的强一致性。到达最终一致性的时间，就是不一致窗口时间，在没有故障发生的前提下，不一致窗口的时间主要受通信延迟，系统负载和复制副本的个数影响。最终一致性模型根据其提供的不同保证可以划分为更多的模型，包括因果一致性和会话一致性等。

因果一致性

因果一致性要求有因果关系的操作顺序得到保证，非因果关系的操作顺序则无所谓。进程 A 在更新完某个数据项后通知了进程 B，那么进程 B 之后对该数据项的访问都应该能够获取到进程 A 更新后的最新值，并且如果进程 B 要对该数据项进行更新操作的话，务必基于进程 A 更新后的最新值。因果一致性的应用场景可以举个例子，在微博或者微信进行评论的时候，比如你在朋友圈发了一张照片，朋友给你评论了，而你对朋友的评论进行了回复，这条朋友圈的显示中，你的回复必须在朋友之后，这是一个因果关系，而其他没有因果关系的数据，可以允许不一致。

会话一致性

会话一致性将对系统数据的访问过程框定在了一个会话当中，约定了系统能保证在同一个有效的会话中实现“读己之所写”的一致性，就是在你的一次访问中，执行更新操作之后，客户端能够在同一个会话中始终读取到该数据项的最新值。实际开发中有分布式的 Session 一致性问题，可以认为是会话一致性的一个应用。

CAP及Base的关系

Base 理论是在CAP上发展的，CAP 理论描述了分布式系统中数据一致性、可用性、分区容错性之间的制约关系，当你选择了其中的两个时，就不得不对剩下的一个做一定程度的牺牲。 Base 理论则是对CAP理论的实际应用，也就是在分区和副本存在的前提下，通过一定的系统设计方案，放弃强一致性，实现基本可用，这是大部分分布式系统的选择，比如NoSQL系统、微服务架构。在这个前提下，如何把基本可用做到最好，就是分布式工程师们追求的，在这个课程中，我们也会有专门的模块来讲解高可用。除了CAP和Base，上面还提到了ACID原理， ACID是一种强一致性模型，强调原子性、一致性、隔离性和持久性，主要用于在数据库实现中。Base 理论面向的是高可用、可扩展的分布式系统， ACID适合传统金融等业务，在实际场景中，不同业务对数据的一致性要求不一样，ACID和Base 理论往往会结合使用。

# Paxos算法原理

Paxos 算法在分布式领域具有非常重要的地位，开源分布式锁组件 Google Chubby 的作者 Mike Burrows 说过，这个世界上只有一种一致性算法，那就是 Paxos 算法，其他的算法都是残次品。 Paxos 算法虽然重要，但是也因算法复杂而著名，不过 Paxos 算法是学习分布式系统必需的一个知识点。

Quorum选举算法

在各种一致性算法中都可以看到Quorum机制的身影，主要数学思想来源于抽屉原理，用一句话解释那就是，在N个副本中，一次更新成功的如果有W个，那么我在读取数据时是要从大于N－W个副本中读取，这样就能至少读到一个更新的数据了。和 Quorum机制对应的是WARO，也就是Write All Read one，是一种简单的副本控制协议，当Client 请求向某副本写数据时（更新数据），只有当所有的副本都更新成功之后，这次写操作才算成功，否则视为失败。 WARO优先保证读服务，因为所有的副本更新成功，才能视为更新成功，从而保证了所有的副本一致，这样的话，只需要读任何一个副本上的数据即可。写服务的可用性较低，因为只要有一个副本更新失败，此次写操作就视为失败了。假设有N个副本，N－1个都宕机了，剩下的那个副本仍能提供读服务；但是只要有一个副本宕机了，写服务就不会成功。 WARO牺牲了更新服务的可用性，最大程度地增强了读服务的可用性，而Quorum 就是在更新服务和读服务之间进行的一个折衷。

Quorum就是限定了一次需要读取至少N+1-w的副本数据,听起来有些抽象，举个例子，我们维护了10个副本，一次成功更新了三个，那么至少需要读取八个副本的数据，可以保证我们读到了最新的数据。

Quorum 机制无法保证强一致性，也就是无法实现任何时刻任何用户或节点都可以读到最近一次成功提交的副本数据。 Quorum 机制的使用需要配合一个获取最新成功提交的版本号的 metadata 服务，这样可以确定最新已经成功提交的版本号，然后从已经读到的数据中就可以确认最新写入的数据。Quorum是分布式系统中常用的一种机制，用来保证数据冗余和最终一致性的投票算法，在 Paxos、Raft和ZooKeeper的Zab等算法中，都可以看到Quorum 机制的应用。

# Paxos的节点角色与交互

在 Paxos 协议中，有三类节点角色，分别是 Proposer、Acceptor 和 Learner，另外还有一个 Client，作为产生议题者。上述三类角色只是逻辑上的划分，在工作实践中，一个节点可以同时充当这三类角色。

Proposer 提案者

Proposer可以有多个，在流程开始时，Proposer 提出议案，也就是value，所谓value，在工程中可以是任何操作，比如“修改某个变量的值为某个新值”， Paxos 协议中统一将这些操作抽象为 value。不同的 Proposer 可以提出不同的甚至矛盾的 value，比如某个 Proposer 提议“将变量 X 设置为 1”，另一个 Proposer 提议“将变量 X 设置为 2”，但对同一轮Paxos 过程，最多只有一个value被批准。

Acceptor 批准者

在集群中，Acceptor 有 N 个，Acceptor 之间完全对等独立，Proposer 提出的value必须获得超过半数（N/2+1）的 Acceptor 批准后才能通过。

Learner 学习者

Learner 不参与选举，而是学习被批准的 value，在Paxos中，Learner主要参与相关的状态机同步流程。

这里Leaner的流程就参考了Quorum 议会机制，某个 value 需要获得 W=N/2 + 1 的 Acceptor 批准，Learner 需要至少读取 N/2+1 个 Accpetor，最多读取 N 个 Acceptor 的结果后，才能学习到一个通过的 value。

Client 产生议题者

Client 角色，作为产生议题者，实际不参与选举过程，比如发起修改请求的来源等。

Proposer与Acceptor的交互

Paxos 中， Proposer 和 Acceptor 是算法核心角色，Paxos 描述的就是在一个由多个 Proposer 和多个 Acceptor 构成的系统中，如何让多个 Acceptor 针对 Proposer 提出的多种提案达成一致的过程，而 Learner 只是“学习”最终被批准的提案。 Proposer 与 Acceptor 之间的交互主要有 4 类消息通信，如下图：

# 准备阶段选举原理

Proposer 生成全局唯一且递增的 ProposalID，向 Paxos 集群的所有机器发送 Prepare 请求，这里不携带 value，只携带 N 即 ProposalID。 Acceptor 收到 Prepare 请求后，判断收到的 ProposalID 是否比之前已响应的所有提案的 N 大，如果是，则：

在本地持久化 N，可记为 Max_N；
回复请求，并带上已经 Accept 的提案中 N 最大的 value，如果此时还没有已经 Accept 的提案，则返回 value 为空；
做出承诺，不会 Accept 任何小于 Max_N 的提案。如果否，则不回复或者回复 Error。

# 运行阶段选举原理

Proposer 发送 Accept

经过一段时间后，Proposer 收集到一些 Prepare 回复，有下列几种情况：

若回复数量 > 一半的 Acceptor 数量，且所有回复的 value 都为空时，则 Porposer 发出 accept 请求，并带上自己指定的 value。
若回复数量 > 一半的 Acceptor 数量，且有的回复 value 不为空时，则 Porposer 发出 accept 请求，并带上回复中 ProposalID 最大的 value，作为自己的提案内容。
若回复数量 <= 一半的 Acceptor 数量时，则尝试更新生成更大的 ProposalID，再转到准备阶段执行。

Acceptor 应答 Accept

Accpetor 收到 Accpet 请求后，判断：

若收到的 N >= Max_N（一般情况下是等于），则回复提交成功，并持久化 N 和 value；
若收到的 N < Max_N，则不回复或者回复提交失败。

Proposer 统计投票

经过一段时间后，Proposer 会收集到一些Accept回复提交成功的情况，比如：

当回复数量 > 一半的 Acceptor 数量时，则表示提交 value 成功，此时可以发一个广播给所有的 Proposer、Learner，通知它们已 commit 的 value；
当回复数量 <= 一半的 Acceptor 数量时，则尝试更新生成更大的 ProposalID，转到准备阶段执行。
当收到一条提交失败的回复时，则尝试更新生成更大的 ProposalID，也会转到准备阶段执行

如果半数以内的 Acceptor 失效，如何正常运行？

在Paxos流程中，如果出现半数以内的Acceptor失效，可以分为两种情况：

第一种，如果半数以内的Acceptor失效时还没确定最终的value，此时所有的Proposer会重新竞争提案，最终有一个提案会成功提交。
第二种，如果半数以内的Acceptor失效时已确定最终的value，此时所有的Proposer提交前必须以最终的value提交，也就是Value实际已经生效，此值可以被获取，并不再修改。

Acceptor需要接受更大的N，也就是ProposalID有什么意义？

这种机制可以防止其中一个Proposer崩溃宕机产生阻塞问题，允许其他Proposer用更大ProposalID来抢占临时的访问权。

如何产生唯一的编号，也就是 ProposalID？

在《Paxos made simple》论文中提到，唯一编号是让所有的 Proposer 都从不相交的数据集合中进行选择，需要保证在不同Proposer之间不重复，比如系统有 5 个 Proposer，则可为每一个 Proposer 分配一个标识 j(0~4)，那么每一个 Proposer每次提出决议的编号可以为 5*i + j，i 可以用来表示提出议案的次数。

# Raft算法原理

Raft是一种共识算法，旨在替代Paxos。它通过逻辑分离比Paxos更容易理解，但它也被正式证明是安全的，并提供了一些额外的功能。 Raft提供了一种在计算系统集群中分布状态机的通用方法，确保集群中的每个节点都同意一系列相同的状态转换。

根据官方文档解释，一个 Raft 集群包含若干节点，Raft 把这些节点分为三种状态：Leader、 Follower、Candidate，每种状态负责的任务也是不一样的。正常情况下，集群中的节点只存在 Leader 与 Follower 两种状态。

Leader（领导者）:负责日志的同步管理，处理来自客户端的请求，与Follower保持heartBeat的联系；
Follower（追随者）:响应 Leader 的日志同步请求，响应Candidate的邀票请求，以及把客户端请求到Follower的事务转发（重定向）给Leader；
Candidate（候选者）:负责选举投票，集群刚启动或者Leader宕机时，状态为Follower的节点将转为Candidate并发起选举，选举胜出（获得超过半数节点的投票）后，从Candidate转为Leader状态。

Raft 三个子问题

通常，Raft 集群中只有一个 Leader，其它节点都是 Follower。Follower 都是被动的，不会发送任何请求，只是简单地响应来自 Leader 或者 Candidate 的请求。Leader 负责处理所有的客户端请求（如果一个客户端和 Follower 联系，那么 Follower 会把请求重定向给 Leader）。

为简化逻辑和实现，Raft 将一致性问题分解成了三个相对独立的子问题。

选举（Leader Election）:当Leader宕机或者集群初创时，一个新的Leader需要被选举出来；
日志复制（Log Replication）:Leader接收来自客户端的请求并将其以日志条目的形式复制到集群中的其它节点，并且强制要求其它节点的日志和自己保持一致；
安全性（Safety）:如果有任何的服务器节点已经应用了一个确定的日志条目到它的状态机中，那么其它服务器节点不能在同一个日志索引位置应用一个不同的指令。

# 选举算法原理

根据 Raft 协议，一个应用 Raft 协议的集群在刚启动时，所有节点的状态都是 Follower。由于没有Leader，Followers 无法与 Leader 保持心跳（Heart Beat），因此，Followers 会认为Leader已经下线，进而转为 Candidate 状态。然后，Candidate 将向集群中其它节点请求投票，同意自己升级为Leader。如果Candidate 收到超过半数节点的投票（N/2 + 1），它将获胜成为 Leader。

# 日志复制原理

在一个Raft集群中，只有Leader节点能够处理客户端的请求（如果客户端的请求发到了 Follower，Follower将会把请求重定向到Leader），客户端的每一个请求都包含一条被复制状态机执行的指令。Leader把这条指令作为一条新的日志条目（Entry）附加到日志中去，然后并行得将附加条目发送给Followers，让它们复制这条日志条目。

当这条日志条目被Followers安全复制，Leader会将这条日志条目应用到它的状态机中，然后把执行的结果返回给客户端。如果Follower崩溃或者运行缓慢，再或者网络丢包，Leader会不断得重复尝试附加日志条目（尽管已经回复了客户端）直到所有的 Follower都最终存储了所有的日志条目，确保强一致性。

# 安全性原理

目前为止描述的机制并不能充分地保证每一个状态机会按照相同的顺序执行相同的指令。例如，一个 Follower 可能处于不可用状态，同时 Leader 已经提交了若干的日志条目；然后这个 Follower 恢复（尚未与 Leader 达成一致）而 Leader 故障；如果该 Follower 被选举为 Leader 并且覆盖这些日志条目，就会出现问题，即不同的状态机执行不同的指令序列。

在Leader选举的时候需增加一些限制来完善Raft算法。这些限制可保证任何的Leader对于给定的任期号（Term），都拥有之前任期的所有被提交的日志条目（所谓 Leader 的完整特性）。

选举限制

在所有基于 Leader 机制的一致性算法中，Leader 都必须存储所有已经提交的日志条目。为了保障这一点，Raft 使用了一种简单而有效的方法，以保证所有之前的任期号中已经提交的日志条目在选举的时候都会出现在新的Leader 中。换言之，日志条目的传送是单向的，只从 Leader传给Follower，并且Leader从不会覆盖自身本地日志中已经存在的条目。

Raft 使用投票的方式来阻止一个 Candidate 赢得选举，除非这个 Candidate 包含了所有已经提交的日志条目。 Candidate 为了赢得选举必须联系集群中的大部分节点。这意味着每一个已经提交的日志条目肯定存在于至少一个服务器节点上。如果 Candidate 的日志至少和大多数的服务器节点一样新（这个新的定义会在下面讨论），那么它一定持有了所有已经提交的日志条目（多数派的思想）。投票请求的限制中请求中包含了 Candidate 的日志信息，然后投票人会拒绝那些日志没有自己新的投票请求。

Raft 通过比较两份日志中最后一条日志条目的索引值和任期号，确定谁的日志比较新。如果两份日志最后条目的任期号不同，那么任期号大的日志更加新。如果两份日志最后的条目任期号相同，那么日志比较长的那个就更加新。

提交之前任期内的日志条目

Leader 知道一条当前任期内的日志记录是可以被提交的，只要它被复制到了大多数的 Follower 上（多数派的思想）。如果一个 Leader 在提交日志条目之前崩溃了，继任的 Leader 会继续尝试复制这条日志记录。然而，一个 Leader 并不能断定被保存到大多数 Follower 上的一个之前任期里的日志条目就一定已经提交了。这很明显，从日志复制的过程可以看出。

鉴于上述情况，Raft 算法不会通过计算副本数目的方式去提交一个之前任期内的日志条目。只有 Leader 当前任期里的日志条目通过计算副本数目可以被提交；一旦当前任期的日志条目以这种方式被提交，那么由于日志匹配特性，之前的日志条目也都会被间接的提交。在某些情况下，Leader 可以安全地知道一个老的日志条目是否已经被提交（只需判断该条目是否存储到所有节点上），但是 Raft 为了简化问题使用了一种更加保守的方法。

当 Leader 复制之前任期里的日志时，Raft 会为所有日志保留原始的任期号，这在提交规则上产生了额外的复杂性。但是，这种策略更加容易辨别出日志，即使随着时间和日志的变化，日志仍维护着同一个任期编号。此外，该策略使得新Leader只需要发送较少日志条目。

线性化语义

raft 的读写都在 leader 节点中进行，它保证了读的都是最新的值，它是符合强一致性的（线性一致性）， raft 除了这个还在【客户端交互】那块也做了一些保证，详情可以参考论文。但是 zookeeper 不同， zookeeper 写在 leader，读可以在 follower 进行，可能会读到了旧值，它不符合强一致性（只考虑写一致性，不考虑读一致性），但是 zookeeper 去 follower 读可以有效提升读取的效率。

# ZAB算法原理

在分布式场景中，ZooKeeper 的应用非常广泛，比如数据发布和订阅、命名服务、配置中心、注册中心、分布式锁等。 ZooKeeper 提供了一个类似于 Linux 文件系统的数据模型，和基于 Watcher 机制的分布式事件通知，这些特性都依赖 ZooKeeper 的高容错数据一致性协议。

ZooKeeper 是通过 Zab 协议来保证分布式事务的最终一致性。Zab（ZooKeeper Atomic Broadcast，ZooKeeper 原子广播协议）支持崩溃恢复，基于该协议， ZooKeeper 实现了一种主备模式的系统架构来保持集群中各个副本之间数据一致性。

在 ZooKeeper 集群中，所有客户端的请求都是写入到 Leader 进程中的，然后，由 Leader 同步到其他节点，称为 Follower。在集群数据同步的过程中，如果出现 Follower 节点崩溃或者 Leader 进程崩溃时，都会通过 Zab 协议来保证数据一致性。

Zab协议的具体实现可以分为以下两部分：

消息广播阶段

Leader 节点接受事务提交，并且将新的 Proposal 请求广播给 Follower 节点，收集各个节点的反馈，决定是否进行 Commit，在这个过程中，也会使用上一课时提到的 Quorum 选举机制。

崩溃恢复阶段

如果在同步过程中出现 Leader 节点宕机，会进入崩溃恢复阶段，重新进行 Leader 选举，崩溃恢复阶段还包含数据同步操作，同步集群中最新的数据，保持集群的数据一致性。

整个 ZooKeeper 集群的一致性保证就是在上面两个状态之前切换，当 Leader 服务正常时，就是正常的消息广播模式；当 Leader 不可用时，则进入崩溃恢复模式，崩溃恢复阶段会进行数据同步，完成以后，重新进入消息广播阶段。

Zab 的具体流程可以拆分为消息广播、崩溃恢复和数据同步三个过程。

# 消息广播原理

在 ZooKeeper 中所有的事务请求都由 Leader 节点来处理，其他服务器为 Follower，Leader 将客户端的事务请求转换为事务 Proposal，并且将 Proposal 分发给集群中其他所有的 Follower。
完成广播之后，Leader 等待 Follwer 反馈，当有过半数的 Follower 反馈信息后，Leader 将再次向集群内 Follower 广播 Commit 信息，Commit 信息就是确认将之前的 Proposal 提交。
这里的 Commit 可以对比 SQL 中的 COMMIT 操作来理解，MySQL 默认操作模式是 autocommit 自动提交模式，如果你显式地开始一个事务，在每次变更之后都要通过 COMMIT 语句来确认，将更改提交到数据库中。
Leader 节点的写入也是一个两步操作，第一步是广播事务操作，第二步是广播提交操作，其中过半数指的是反馈的节点数 >=N/2+1，N 是全部的 Follower 节点数量。

客户端的写请求进来之后，Leader 会将写请求包装成 Proposal 事务，并添加一个递增事务 ID，也就是 Zxid，Zxid 是单调递增的，以保证每个消息的先后顺序；
广播这个 Proposal 事务，Leader 节点和 Follower 节点是解耦的，通信都会经过一个先进先出的消息队列，Leader 会为每一个 Follower 服务器分配一个单独的 FIFO 队列，然后把 Proposal 放到队列中；
Follower 节点收到对应的 Proposal 之后会把它持久到磁盘上，当完全写入之后，发一个 ACK 给 Leader；
当 Leader 收到超过半数 Follower 机器的 ack 之后，会提交本地机器上的事务，同时开始广播 commit， Follower 收到 commit 之后，完成各自的事务提交。

# 崩溃恢复原理

消息广播通过 Quorum 机制，解决了 Follower 节点宕机的情况，但是如果在广播过程中 Leader 节点崩溃呢？这就需要 Zab 协议支持的崩溃恢复，崩溃恢复可以保证在 Leader 进程崩溃的时候可以重新选出 Leader，并且保证数据的完整性。

崩溃恢复和集群启动时的选举过程是一致的，也就是说，下面的几种情况都会进入崩溃恢复阶段：

初始化集群，刚刚启动的时候
Leader崩溃，因为故障宕机
Leader失去了半数的机器支持，与集群中超过一半的节点断连

崩溃恢复模式将会开启新的一轮选举，选举产生的 Leader 会与过半的 Follower 进行同步，使数据一致，当与过半的机器同步完成后，就退出恢复模式，然后进入消息广播模式。

Zab 中的节点有三种状态，伴随着的 Zab 不同阶段的转换，节点状态也在变化：

我们通过一个模拟的例子，来了解崩溃恢复阶段，也就是选举的流程。假设正在运行的集群有五台 Follower 服务器，编号分别是 Server1、Server2、Server3、Server4、Server5，当前 Leader 是 Server2，若某一时刻 Leader 挂了，此时便开始 Leader 选举。

选举过程如下：

各个节点变更状态，变更为 Looking ZooKeeper 中除了 Leader 和 Follower，还有 Observer 节点，Observer 不参与选举，Leader 挂后，余下的 Follower 节点都会将自己的状态变更为 Looking，然后开始进入 Leader 选举过程。
各个 Server 节点都会发出一个投票，参与选举在第一次投票中，所有的 Server 都会投自己，然后各自将投票发送给集群中所有机器，在运行期间，每个服务器上的 Zxid 大概率不同。
集群接收来自各个服务器的投票，开始处理投票和选举处理投票的过程就是对比 Zxid 的过程，假定 Server3 的 Zxid 最大，Server1 判断 Server3 可以成为 Leader，那么 Server1 就投票给 Server3，判断的依据如下：

首先选举 epoch 最大的
如果 epoch 相等，则选 zxid 最大的
若 epoch 和 zxid 都相等，则选择 server id 最大的，就是配置 zoo.cfg 中的 myid

在选举过程中，如果有节点获得超过半数的投票数，则会成为 Leader 节点，反之则重新投票选举。

选举成功，改变服务器的状态，参考上面这张图的状态变更.

# 数据同步原理

崩溃恢复完成选举以后，接下来的工作就是数据同步，在选举过程中，通过投票已经确认 Leader 服务器是最大Zxid 的节点，同步阶段就是利用 Leader 前一阶段获得的最新Proposal历史，同步集群中所有的副本。

# 分布式算法总结

对比于 zab、raft，我们发现他们选举、setData都是需要过半机制才行，所以他们针对网络分区的处理方法都是一样的。

一个集群的节点经过网络分区后，如一共有 A、B、C、D、E 5个节点，如果 A 是 leader，网络分区为 A、B、C 和 D、E，在A、B、C分区还是能正常提供服务的，而在 D、E 分区因为不能得到大多数成员确认（虽然分区了，但是因为配置的原因他们还是能知道所有的成员数量，比如 zk 集群启动前需要配置所有成员地址，raft 也一样），是不能进行选举的，所以保证只会有一个leader。

如果分区为 A、B 和 C、D、E ，A、B 分区虽然 A 还是 leader，但是却不能提供事务服务（setData），C、D、E 分区能重新选出leader，还是能正常向外提供服务。

我们所说的日志（log）与状态机（state machine）不是一回事，日志指还没有提交到状态机中的数据。
新leader永远不会通过计算副本数量提交旧日志，他只能复制旧日志都其他 follower 上，对于旧日志的提交，只能是新 leader 接收新的写请求写新日志，顺带着把旧日志提交了。

为什么采取随机超时时间变成candidate获取选票，是为了防止导致没有任何一个 Candidate 选票数超过一半的情况重复循环发生。 比如有3个Candidate，都得不到多数选票，指的是都同时变成 candidate 然后都投给自己，然后都不会投给别人（如果日志都相同的情况下，如果自己日志落后于别人或者任期落后于别人，自己就会stepDown，选票清空角色变成follower）。然而其中某个Candidate C1 超时短，立刻重新开始新的选举，那么基本上就可以平定局势了。注意，此时另外两个Candidate C2和Candidate C3虽然也处于Candidate状态，但是收到了 Candidate C1 的竞选请求，并且发现 C1 的任期号比自己大，会立刻变为Follower ，并且投票给 C1 。

raft 协议和 zab 协议区别

相同点：

采用 quorum(仲裁集,大多数投票机制，法定人数 ) 来确定整个系统的一致性,这个 quorum 一般实现是集群中半数以上的服务器。
zookeeper 里还提供了带权重的 quorum 实现。
都由 leader 来发起写操作。
都采用心跳检测存活性。
leader election 都采用先到先得的投票方式。

不同点

zab用的是epoch(时代，纪元) 和 count 的组合来唯一表示一个值, 而raft用的是term 和 index。
zab的follower在投票给一个 leader之前必须和 leader 的日志达成一致,而 raft的follower则简单地说是谁的term高就投票给谁。
raft协议的心跳是从leader到follower, 这里注意zab协议也是一样从leader到follower。
raft协议数据只有单向地从leader到follower(成为 leader 的条件之一就是拥有最新的 log)。而zab协议在discovery 阶段, 一个 prospective(潜在的) leader 需要将自己的 log 更新为 quorum 里面最新的 log,然后才好在 synchronization 阶段将 quorum 里的其他机器的 log 都同步到一致。

单M架构、两者都要先写入leader、都为CP。

	ZAB算法	raft算法
节点状态	looking：选举状态，无主、leading、following、observing：不参与选举	leader、follower、candidate：不认leader的node
选举机制	默认FastLeaderElection：节点启动直接投自己，然后开始给其他节点发请求，在每个朝代（epoch，raft里是term）中，节点先收到其他提案（proposal），然后本地battle（zxid, myid）大小后再发出选票给所有node，一个朝代中每个节点可以发多次投票，一个节点收到半数以上选票则当选leader	每个candidate具备随机时钟（election timeout），到时间了先投自己，然后发消息给其他所有node，收到消息的candidate变为follower并回复，当半数原则满足后leader确立，leader再通告所有节点你们的leader出现了，停下手里的针线活吧。但每个朝代一个节点只能投票一次，而且candidate只响应大于自己term的请求，否则保持选举状态。
选举机制优劣	不存在分区、有利于选出有最新数据的node battle次数过多造成选举时间长、首次启动会有myid节点大概率成为leader	选举速度快、可能因为随机时钟差不多造成每个node的票数都没过半，发生投票分区，那只能进入下一个周期再选举
选主依据	1. epoch选举朝代、2.ZXID：64BIT正整数，高32为epoch，低32为顺序自增的事务ID、3. 机器myid	1. term朝代每一轮选举都增加、2. 日志条目 3. election timeout
定时心跳	双方检测。leader向所有follower发送定期心跳，心跳返回不过半则导致leader退位。follower没有收到来自leader的心跳会导致进入looking状态	1. term朝代每一轮选举都增加、2. 日志条目 3. election timeout
新节点加入	新节点启动先给所有node发消息，然后自己内部做选主依据信息battle	直接接到leader的append entry消息，就知道谁是leader了
写消息流程	两阶段：client请求followerA、follower发请求给leader，leader对众follower发送proposal，过半后返回后再发commit，当followerA commit后返回客户端。	非两阶段：client请求follower，follower把消息转到leader后，leader写日志并向其他节点发AppendEntries，大多数返回后leader就向客户端返回。
消息一致性（线性顺序）	zab利用client、leader、follower的多端努力，以自增的zxid为依据，保证写入强一致性（线性一致性）。若收到非顺序的zxid则禁止写入或节点退出。	相同的 term 和 index的节点之前内容肯定一样。选举时candidate携带最新 (term, index)，如果对家小于自己则拒绝投票，所以选出来的leader肯定是大多节点里最新的。外加，提交也要过半成功。两者组合实现了一致性
消息顺序性	follower必须按顺序接收zxid+提交,否则退出进入恢复。	leader每次都发当前的消息和上一条消息，如果follower找不到上一条消息就不复制，再要求leader发上一条消息，直到定位到缺失消息。
残留消息一致性follower有较新的未提交消息	新leader上台后，leader尝试commit未提交的消息，没commit的proposal都会被丢弃	STRONG LEADER，非持有uncommitted log的新leader，会强制follower复制自己的日志解决一致性。
脏读	存在但几率低，leader 发proposal过半后再发commit，接收follower commit后才返回客户端	存在，leader 发消息过半ack后就返回client请求了，可能follower没有commit就没了、或者leader没发现自己丧失领导权等
持久性	WAL实现，zk将其优化为每个64MB的预占文件。snapshot压缩数据日志	类似zab，也是WAL + snapshot committed log

← 场景面试问题总结分布式ID原理与设计 →