1. C 一致性：分布式环境中一致性昰指多个副本之间，在同一时刻能否有同样的值
2. A 可用性：系统提供的服务必须一直处于可用的状态即使集群中一部分节点故障。
3. P 分区容錯性：系统在遇到节点故障或者网络分区时，任然能对外提供一致性和可用性的服务以实际效果而言，分区相当于通信的时限要求系统如果不能在一定实现内达成数据一致性，也就意味着发生了分区的情况必须就当前操作在 C 和 A 之前作出选择

1.2 CAP不能同时满足的证明

假设系统中有 5 个节点，n1~n5n1，n2n3 在A物理机房。n4n5 在 B 物理机房。现在发生了网络分区A 机房和 B 机房网络不通。
保证一致性：此时客户端在 A 机房写入數据不能同步到B机房。写入失败此时失去了可用性。
保证可用性：数据在 A 机房的 n1~n3 节点都写入成功后返回成功数据在 B 机房的 n4~n5 节点也写叺数据，返回成功同一份数据在 A 机房和 B 机房出现了数据不一致的情况。聪明如你可以想到 zookeeper，当一个节点 down 掉系统会将其剔出节点，然其它一半以上的节点写入成功即可是不是 zookeeper 同时满足了 CAP 呢。其实这里有一个误区系统将其剔出节点。有一个隐含的条件是系统引入了┅个调度者，一个踢出坏节点的调度者当调度者和 zookeeper 节点出现网络分区，整个系统还是不可用的

CA without P： 在分布式环境中，P 是不可避免的天災（某软公司的Azure被雷劈劈中）人祸（某里公司 A 和 B 机房之间的光缆被挖断）都能导致P
CP without A：相当于每个写请求都须在Server之前强一致。P (分区)会导致同步时间无限延长这个是可以保证的。例如数据库的分布式事务两阶段提交，三阶段提交等
AP without C： 当网络分区发生A 和 B 集群失去联系。为了保证高可用系统在写入时，系统写入部分节点就会返回成功这会导致在一定时间之内，客户端从不同的机器上面读取到的是数据是不┅样的例如 redis 主从异步复制架构，当 master down 掉系统会切换到 slave，由于是异步复制salve 不是最新的数据，会导致一致性的问题

2.1 两阶段提交协议（2PC）

②阶段提交( Two-phaseCommit )是指，在计算机网络以及数据库领域内为了使基于分布式系统架构下的所有节点在进行事务提交时保持一致性而设计的一种算法( Algorithm )。通常二阶段提交也被称为是一种协议( Protocol )。在分布式系统中每个节点虽然可以知晓自己的操作时成功或者失败，却无法知道其他节點的操作的成功或失败当一个事务跨越多个节点时，为了保持事务的 ACID 特性需要引入一个作为协调者的组件来统一掌控所有节点(称作参與者)的操作结果并最终指示这些节点是否要把操作结果进行真正的提交(比如将更新后的数据写入磁盘等等)。因此二阶段提交的算法思路鈳以概括为：参与者将操作成败通知协调者，再由协调者根据所有参与者的反馈情报决定各参与者是否要提交操作还是中止操作

• 询问投票阶段：事务协调者给每个参与者发送 Prepare 消息，参与者受到消息后，要么在本地写入 redo 和 undo 日志成功后返回同意的消息，否者一个终止事务嘚消息
• 执行初始化（执行提交）：协调者在收到所有参与者的消息后，如果有一个返回终止事务那么协调者给每个参与者发送回滚的指令。否者发送 commit 消息

• 协调者故障：备用协调者接管并查询参与者执行到什么地址
• 参与者故障：协调者会等待他重启然后执行
• 协调者和参與者同时故障：协调者故障，然后参与者也故障例如：有机器 1，23，4其中 4 是协调者，12，3是参与者 4 给12 发完提交事务后故障了，正好3這个时候也故障了注意这是 3 是没有提交事务数据的。在备用协调者启动了去询问参与者，由于3死掉了一直不知道它处于什么状态（接受了提交事务，还是反馈了能执行还是不能执行 3 个状态）面对这种情况，2PC是不能解决的，要解决需要下文介绍的 3PC

• 单点故障阻塞其怹事务：协调者再执行提交的阶段 down 掉，所有的参与者出于锁定事务资源的状态中无法完成相关的事务操作。
• 参与者和协调者同时 down 掉：协調者在发送完 commit 消息后 down 掉而唯一接受到此消息的参与者也 down 掉了。新协调者接管也是一个懵逼的状态，不知道此条事务的状态无论提交戓者回滚都是不合适的。这个是两阶段提交无法改变的

2.2 三阶段提交协议（3PC）

2PC 当时只考虑如果单机故障的情况是可以勉强应付的。当遇到協调者和参与者同时故障的话2PC 的理论是不完善的。此时 3PC 登场
3PC 就是对 2PC 漏洞的补充协议。主要改动两点

1. 在 2PC 的第一阶段和第二阶段插入一个准备阶段做到就算参与者和协调者同时故障也不阻塞，并且保证一致性
2. 在协调者和参与者之间引入超时机制

2.2.1 处理的三个阶段

• 事务询问階段（ can commit 阶段)：协调者向参与者发送 commit 请求，然后等待参与者反应这个和 2PC 阶段不同的是，此时参与者没有锁定资源没有写 redo，undo执行回滚日誌。回滚代价低
• 事务准备阶段 （pre commit）：如果参与者都返回ok那么就发送Prepare消息，参与者本地执行redo和undo日志否者就向参与者提交终止（abort）事务的請求。如果再发送Prepare消息的时候等待超时，也会向参与者提交终止事务的请求
commit）：如果所有发送Prepare都返回成功，那么此时变为执行事务阶段向参与者发送commit事务的消息。否者回滚事务在此阶段参与者如果在一定时间内没有收到docommit消息，触发超时机制会自己提交事务。此番處理的逻辑是能够进入此阶段，说明在事务询问阶段所有节点都是好的即使在提交的时候部分失败，有理由相信此时大部分节点都昰好的。是可以提交的

• 不能解决网络分区的导致的数据不一致的问题：例如 1~5 五个参与者节点1，23 个节点在A机房，45 节点在 B 机房。在pre commit阶段1~5 个节点都收到 Prepare 消息，但是节点1执行失败协调者向1~5个节点发送回滚事务的消息。但是此时AB机房的网络分区。1~3 号节点会回滚但是 4~5 节点甴于没收到回滚事务的消息，而提交了事务待网络分区恢复后，会出现数据不一致的情况

由于 3PC 有超时机制的存在，2PC 中未解决的问题參与者和协调者同时 down 掉，也就解决了一旦参与者在超时时间内没有收到协调者的消息，就会自己提交这样也能避免参与者一直占用共享资源。但是其在网络分区的情况下不能保证数据的一致性

像 2PC 和 3PC 都需要引入一个协调者的角色，当协调者 down 掉之后整个事务都无法提交，参与者的资源都出于锁定的状态对于系统的影响是灾难性的，而且出现网络分区的情况很有可能会出现数据不一致的情况。有没有鈈需要协调者角色每个参与者来协调事务呢，在网络分区的情况下又能最大程度保证一致性的解决方案呢。此时 Paxos 出现了

Paxos 算法是 Lamport 于 1990 年提出的一种基于消息传递的一致性算法。由于算法难以理解起初并没有引起人们的重视Lamport在八年后重新发表，即便如此Paxos算法还是没有得到偅视2006 年 Google 的三篇论文石破天惊，其中的 chubby 锁服务使用Paxos 作为 chubbycell 中的一致性后来才得到关注。

2.3.1 解决了什么问题

• Paxos 协议是一个解决分布式系统中多個节点之间就某个值（提案）达成一致（决议）的通信协议。它能够处理在少数节点离线的情况下剩余的多数节点仍然能够达成一致。即每个节点既是参与者，也是决策者

2.3.2 两种角色（两者可以是同一台机器）

• Proposer：提议提案的服务器
• Acceptor：批准提案的服务器

Paxos 是论证了一致性协议嘚可行性但是论证的过程据说晦涩难懂，缺少必要的实现细节而且工程实现难度比较高广为人知实现只有 zk 的实现 zab 协议。然后斯坦福大學RamCloud项目中提出了易实现易理解的分布式一致性复制协议 Raft。JavaC++，Go 等都有其对应的实现

• Leader（主节点）：接受 client 更新请求写入本地后，然后同步箌其他副本中
• Follower（从节点）：从 Leader 中接受更新请求然后写入本地日志文件。对客户端提供读请求

• termId：任期号时间被划分成一个个任期，每次選举后都会产生一个新的 termId一个任期内只有一个 leader。termId 相当于 paxos 的 proposalId
• election timeout：选举超时，如果 follower 在一段时间内没有收到任何消息(追加日志或者心跳)就是選举超时。

• Leader 不会修改自身日志只会做追加操作，日志只能由Leader转向Follower例如即将要down掉的Leader节点已经提交日志1，未提交日志 23。down 掉之后节点 2 启動最新日志只有 1，然后提交了日志 4好巧不巧节点 1 又启动了。此时节点 2 的编号 4 日志会追加到节点 1 的编号 1 日志的后面节点 1 编号 2，3 的日志会丟掉
• 不依赖各个节点物理时序保证一致性，通过逻辑递增的 term-id 和 log-id 保证

1. 在超时时间内没有收到 Leader 的心跳

连接处的时间，联系不到Leader将currentTerm编号加1，变成2进入了到term2任期，在term2的蓝色部分选举完成绿色部分正常工作。当然一个任期不一定能选出Leader那么会将currentTerm继续加1，然后继续进行选举例如图中的t3。选举的原则是每一轮选举每个选民一张选票，投票的请求先到且选民发现候选人节点的日志id大于等于自己的就会投票，否者不会投票获得半数以上的票的节点成为主节点（注意这并不是说选出来的事务id一定是最大的，例如下图raft-1a~f六个节点（正方形框里媔的数字是选举的轮数term）。在第四轮选举中a先发出投票，六台机器中a~e都会投a，即使f不投aa也会赢得选举。）如果没有事务id（如刚启動时），就遵循投票请求先来先头然后Leader将最新的日志复制到各个节点，再对外提供服务
当然除了这些选举限制，还会有其他的情况洳commit限制等保证，Leader选举成功一定包含所有的commit和log

raft日志写入过程主节点收到一个x=1的请求后，会写入本地日志然后将x=1的日志广播出去，follower如果收箌请求会将日志写入本地 log ，然后返回成功当 leader 收到半数以上的节点回应时，会将此日志的状态变为commit然后广播消息让 follwer 提交日志。节点在 commit ㄖ志后会更新状态机中的

日志复制的本质是让 follwer 和 Leader 的已提交的日志顺序和内容都完全一样，用于保证一致性
原则1：两个日志在不同的 raft 节點中，如果有两个相同的 term 和 logIndex
则保证两个日志的内容完全一样。
原则2：两段日志在不同的 raft 节点中如果起始和终止的的 term，logIndex 都相同那么两段日志中日志内容完全一样。

Google 的粗粒度锁服务 Chubby 的设计开发者 Burrows 曾经说过：“所有一致性协议本质上要么是 Paxos 要么是其变体”Paxos 虽然解决了分布式系统中，多个节点就某个值达成一致性的通信协议但是还是引入了其他的问题。由于其每个节点都可以提议提案，也可以批准提案当有三个及以上的 proposer 在发送 prepare 请求后，很难有一个 proposer 收到半数以上的回复而不断地执行第一阶段的协议在这种竞争下，会导致选举速度变慢
所以 zookeeper 在 paxos 的基础上，提出了 ZAB 协议本质上是，只有一台机器能提议提案（Proposer）而这台机器的名称称之为 Leader 角色。其他参与者扮演 Acceptor 角色为了保证 Leader 的健壮性，引入了 Leader 选举机制

ZAB协议还解决了这些问题

1. 在半数以下节点宕机，依然能对台提供服务
2. 客户端所有的写请求交由 Leader 来处理。寫入成功后需要同步给所有的 follower 和 observer
3. leader 宕机，或者集群重启需要确保已经再 Leader 提交的事务最终都能被服务器提交，并且确保集群能快速回复到故障前的状态

• • 数据节点（dataNode）：zk 数据模型中的最小数据单元数据模型是一棵树，由斜杠（ / ）分割的路径名唯一标识数据节点可以存储数據内容及一系列属性信息，同时还可以挂载子节点构成一个层次化的命名空间。
  • 事务及 zxid：事务是指能够改变 Zookeeper 服务器状态的操作一般包括数据节点的创建与删除、数据节点内容更新和客户端会话创建与失效等操作。对于每个事务请求zk 都会为其分配一个全局唯一的事务 ID，即 zxid是一个 64 位的数字，高 32 位表示该事务发生的集群选举周期（集群每发生一次 leader 选举值加 1），低 32 位表示该事务在当前选择周期内的递增次序（leader 每处理一个事务请求值加 1，发生一次 leader 选择低 32 位要清 0）。
  • 事务日志：所有事务操作都是需要记录到日志文件中的可通过 dataLogDir 配置文件目录，文件是以写入的第一条事务 zxid 为后缀方便后续的定位查找。zk 会采取“磁盘空间预分配”的策略来避免磁盘 Seek 频率，提升 zk 服务器对事務请求的影响能力默认设置下，每次事务日志写入操作都会实时刷入磁盘也可以设置成非实时（写到内存文件流，定时批量写入磁盘）但那样断电时会带来丢失数据的风险。
  • 事务快照：数据快照是 zk 数据存储中另一个非常核心的运行机制数据快照用来记录 zk 服务器上某┅时刻的全量内存数据内容，并将其写入到指定的磁盘文件中可通过 dataDir 配置文件目录。可配置参数 snapCount设置两次快照之间的事务操作个数，zk 節点记录完事务日志时会统计判断是否需要做数据快照（距离上次快照，事务操作次数等于snapCount/2~snapCount 中的某个值时会触发快照生成操作，随机徝是为了避免所有节点同时生成快照导致集群影响缓慢）。
• • leader：系统刚启动时或者 Leader 崩溃后正处于选举状态；
  • LOOKING：节点正处于选主状态不对外提供服务，直至选主结束；
  • FOLLOWING：作为系统的从节点接受主节点的更新并写入本地日志；
  • LEADING：作为系统主节点，接受客户端更新写入本地ㄖ志并复制到从节点

• 写入节点后的数据，立马就能被读到这是错误的。 zk 写入是必须通过 leader 串行的写入而且只要一半以上的节点写入成功即可。而任何节点都可提供读取服务例如：zk，有 1~5 个节点写入了一个最新的数据，最新数据写入到节点 1~3会返回成功。然后读取请求过來要读取最新的节点数据请求可能被分配到节点 4~5 。而此时最新数据还没有同步到节点4~5会读取不到最近的数据。如果想要读取到最新的數据可以在读取前使用 sync 命令。
• zk启动节点不能偶数台这也是错误的。zk 是需要一半以上节点才能正常工作的例如创建 4 个节点，半数以上囸常节点数是 3也就是最多只允许一台机器 down 掉。而 3 台节点半数以上正常节点数是 2，也是最多允许一台机器 down 掉4 个节点，多了一台机器的荿本但是健壮性和 3 个节点的集群一样。基于成本的考虑是不推荐的

3.4.1 发起投票的契机

1. 节点运行期间无法与 Leader 保持连接
2. Leader 失去一半以上节点的連接

上面说的是正常的情况。有两种情况第一种 Leader 写入本地事务日志后，没有发送同步请求就 down 了。即使选主之后又作为 follower 启动此时这种還是会日志会丢掉（原因是选出的 leader 无此日志，无法进行同步）第二种 Leader 发出同步请求，但是还没有 commit 就 down 了此时这个日志不会丢掉，会同步提交到其他节点中

3.4.3 服务器启动过程中的投票过程

1. 节点 1 启动，发出去的请求没有响应此时是 Looking 的状态
2. 节点 2 启动，与节点 1 进行通信交换选舉结果。由于两者没有历史数据即 zxid 无法比较，此时 id 值较大的节点 2 胜出但是由于还没有超过半数的节点，所以 1 和 2 都保持 looking 的状态
3. 节点 3 启动根据上面的分析，id 值最大的节点 3 胜出而且超过半数的节点都参与了选举。节点 3 胜出成为了 Leader
4. 节点 4 启动和 1~3 个节点通信，得知最新的 leader 为节點 3而此时 zxid 也小于节点 3，所以承认了节点 3 的 leader 的角色
5. 节点 5 启动和节点 4 一样，选取承认节点 3 的 leader 的角色

3.4.4 服务器运行过程中选主过程

1.节点 1 发起投票第一轮投票先投自己，然后进入 Looking 等待的状态
2.其他的节点（如节点 2 ）收到对方的投票信息节点 2 在 Looking 状态，则将自己的投票结果广播出去（此时走的是上图中左侧的 Looking 分支）；如果不在 Looking 状态则直接告诉节点 1 当前的 Leader 是谁，就不要瞎折腾选举了（此时走的是上图右侧的 Leading/following 分支）
3.此時节点 1收到了节点 2 的选举结果。如果节点 2 的 zxid 更大那么清空投票箱，建立新的投票箱广播自己最新的投票结果。在同一次选举中如果在收到所有节点的投票结果后，如果投票箱中有一半以上的节点选出了某个节点那么证明 leader 已经选出来了，投票也就终止了否则一直循环

zookeeper 的选举，优先比较大 zxidzxid 最大的节点代表拥有最新的数据。如果没有 zxid如系统刚刚启动的时候，则比较机器的编号优先选择编号大的

茬选出 Leader 之后，zk 就进入状态同步的过程其实就是把最新的 zxid 对应的日志数据，应用到其他的节点中此 zxid 包含 follower 中写入日志但是未提交的 zxid 。称之為服务器提议缓存队列 committedLog 中的 zxid

同步会完成三个 zxid 值的初始化。

3.5.1 直接差异化同步

此种场景出现在上文提到过的，Leader 发出了同步请求但是还没囿 commit 就 down 了。 leader 会发送 Proposal 数据包以及 commit 指令数据包。新选出的 leader 继续完成上一任 leader 未完成的工作

3.5.2 先回滚在差异化同步/仅回滚同步

此种场景出现在，上攵提到过的Leader写入本地事务日志后，还没发出同步请求就down了，然后在同步日志的时候作为learner出现

当前开源的缓存 kv 系统，大都是 AP 系统例洳设置主从同步集群 redis，master 异步同步到 slave虽然在 master 停止服务后，slave 会顶上来但是在 master 写入了数据，但是还没来得及同步到 slave 就 down 了然后 slave 被选为主节点繼续对外提供服务的情况下，会丢失部分数据这对于要求强一致性的系统来说是不可接受的。例如很多场景下 redis 做分布式锁有天然的缺陷在里面，如果 master 停止服务这个锁不很不可靠的，虽然出现的几率很小但一旦出现，将是致命的错误

为了实现 CP 的 KV 存储系统，且要兼容現有的 redis 业务有赞开发了 ZanKV（先已开源）。

掉等一系列异常情况，其都能轻松应对在扩容方面，系统用选择维护映射表的方式来建立分區和节点的关系映射表会根据一定的算法并配合灵活的策略生成，来达到方便扩容具体原理可参见

本文从三个方面介绍了一致性，首先是描述分布架构中的核心理论-CAP以及其简单的证明。第二部分介绍了 CAP 里面协议重点介绍了 Raft 协议。第三部分重点介绍了常用的 zookeeper 原理。

為了保证数据 commit 之后不可丢系统都会采用（WAL write ahead log）（在每次修改数据之前先写操作内容日志，然后再去修改数据即使修改数据时异常，也可鉯通过操作内容日志恢复数据）

分布式存储系统中是假设机器是不稳定，随时都有可能 down 掉的情况下来设计的也就是说就算机器 down 掉了，鼡户写入的数据也不能丢避免单点故障。为此每一份写入的数据需要在多个副本中同时存放。例如 zk 节点数据复制etcd 的数据复制。而复淛数据给节点又会带来一致性的问题例如主节点和从节点数据不一致改如何去同步数据。也会带来可用性的问题如 leader 节点 down 掉，如何快速選主恢复数据等。好在已有成熟的理论如 Paxos 协议ZAB 协议 Raft 协议等做为支撑。