CAP 理论

C 一致性 指多个副本之间数据一致
A 可用性 系统服务一直处于可用的状态，即使部分节点故障。
P 分区容错性 遇到节点故障，或者网络分区，任然能对外提供服务

CAP不能同时满足
分布式系统 系统P都需要满足
主要在 AP CP 之中选择

CP 系统   譬如 分布式事务 二阶段提交 三阶段提交
AP 系统  Redis MySQL 主从异步复制


一致性协议

两阶段提交协议  Two phase Commit  2PC 
参与者将操作成败通知协调者，再由协调者根据所有参与者的反馈情报决定各参与者是否要提交操作还是中止操作。
两种角色 协调者 参与者
准备阶段
提交阶段

异常情况处理
协调者故障 备用协调者接管，并查询参与者执行状态
参与者故障 协调者会等待他重启然后执行

缺点
同步阻塞问题
单点故障阻塞其他事务
参与者和协调者同时 down 掉  ，状态不确定

三阶段提交协议（3PC）
两点改动

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

事务询问阶段（ can commit 阶段)
   协调者向参与者发送 commit 请求，然后等待参与者反应。
   这个和 2PC 阶段不同的是，此时参与者没有锁定资源，没有写 redo，undo，执行回滚日志。 回滚代价低
事务准备阶段 （pre commit）
   如果参与者都返回ok，那么就发送Prepare消息，参与者本地执行redo和undo日志。
   否者就向参与者提交终止（abort）事务的请求。如果再发送Prepare消息的时候，等待超时，也会向参与者提交终止事务的请求。
执行事务阶段（do commit）

缺点
不能解决网络分区的导致的数据不一致的问题

Paxos协议

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


两种角色
Proposer 提议提案者
Acceptor 提案批准者

Raft协议
分布式一致性复制协议 

Leader（主节点）：接受 client 更新请求，写入本地后，然后同步到其他副本中
Follower（从节点）：从 Leader 中接受更新请求，然后写入本地日志文件。对客户端提供读请求
Candidate（候选节点）：如果 follower 在一段时间内未收到 leader 心跳。则判断 leader 可能故障，发起选主提议。节点状态从 Follower 变为 Candidate 状态，直到选主结束
termId：任期号，时间被划分成一个个任期，每次选举后都会产生一个新的 termId，一个任期内只有一个 leader。termId 相当于 paxos 的 proposalId。
RequestVote：请求投票，candidate 在选举过程中发起，收到 quorum (多数派）响应后，成为 leader。
AppendEntries：附加日志，leader 发送日志和心跳的机制
election timeout：选举超时，如果 follower 在一段时间内没有收到任何消息(追加日志或者心跳)，就是选举超时。

Leader 不会修改自身日志，只会做追加操作，日志只能由Leader转向Follower。
不依赖各个节点物理时序保证一致性，通过逻辑递增的 term-id 和 log-id 保证


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


firstLogIndex/lastLogIndex 为节点中开始和结束的索引位置（包含提交，未提交，写入状态机）
commitIndex：已提交的索引。applyIndex：已写入状态机中的索引。
日志复制的本质是让 follwer 和 Leader 的已提交的日志顺序和内容都完全一样，用于保证一致性。

Zookeeper 原理

Paxos 潜在问题 选举速度慢
zookeeper 在 paxos 的基础上，实现了 ZAB 协议

只有一台机器能提议提案（Proposer），而这台机器的名称称之为 Leader 角色。
其他参与者扮演 Acceptor 角色。为了保证 Leader 的健壮性，引入了 Leader 选举机制。

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


数据节点（dataNode）
事务及 zxid
zxid，是一个 64 位的数字，高 32 位表示该事务发生的集群选举周期（集群每发生一次 leader 选举，值加 1），
低 32 位表示该事务在当前选择周期内的递增次序（leader 每处理一个事务请求，值加 1，发生一次 leader 选择，低 32 位要清 0）
事务日志 
所有事务操作都是需要记录到日志文件中的，可通过 dataLogDir 配置文件目录，文件是以写入的第一条事务 zxid 为后缀，方便后续的定位查找。
默认设置下，每次事务日志写入操作都会实时刷入磁盘，也可以设置成非实时（写到内存文件流，定时批量写入磁盘）

事务快照：数据快照是 zk 数据存储中另一个非常核心的运行机制。
数据快照用来记录 zk 服务器上某一时刻的全量内存数据内容，并将其写入到指定的磁盘文件中，可通过 dataDir 配置文件目录。
可配置参数 snapCount，设置两次快照之间的事务操作个数，zk 节点记录完事务日志时，会统计判断是否需要做数据快照
距离上次快照，事务操作次数等于snapCount/2~snapCount 中的某个值时，会触发快照生成操作，随机值是为了避免所有节点同时生成快照，导致集群影响缓慢。


核心角色

leader 
follower 
observer 

节点状态

LOOKING：节点正处于选主状态，不对外提供服务，直至选主结束；
FOLLOWING：作为系统的从节点，接受主节点的更新并写入本地日志；
LEADING：作为系统主节点，接受客户端更新，写入本地日志并复制到从节点

如果想要读取到最新的数据，可以在读取前使用 sync 命令 。

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

同步过程

同步会完成三个 zxid 值的初始化。
peerLastZxid ：该 learner 服务器最后处理的 zxid。 
minCommittedLog ：leader服务器提议缓存队列 committedLog 中的最小 zxid。 
maxCommittedLog ：leader服务器提议缓存队列 committedLog 中的最大 zxid。

系统会根据 learner 的 peerLastZxid 和 leader 的 minCommittedLog ， maxCommittedLog 做出比较后使用不同的同步策略。

直接差异化同步
peerLastZxid 介于 minCommittedLogZxid 和 maxCommittedLogZxid 间

先回滚再差异化同步/仅回滚同步

全量同步
peerLastZxid 小于 minCommittedLogZxid 或者 leader 上面没有缓存队列。leader 直接使用 SNAP 命令进行全量同步。




预写日志WAL write ahead log