Zookeeper算法原理
zk算法的演进过程
1.Write-all-read-one
先讨论最简单的副本控制规则
Write-all-read-one（简称 WARO）是一种最简单的副本控制规则，顾名思义即在更新时写所有
的副本， 只有在所有的副本上更新成功，才认为更新成功， 从而保证所有的副本一致，这样在读取数据时可以读任一副本上的数据。
先做这样的约定 ：更新操作（write）是一系列顺序的过程，通过其他机制
确定更新操作的顺序（例如 primary-secondary 架构中由 primary 决定顺序），每个更新操作记为 wi，
i 为更新操作单调递增的序号，每个 wi执行成功后副本数据都发生变化，称为不同的数据版本，记作 vi。假设每个副本都保存了历史上所有版本的数据。
假设有一种 magic 的机制，当某次更新操作 wi一旦在所有 N 个副本上都成功，此时 全局都能知
道这个信息(现实情况是比较难的) ，此后读取操作将指定读取数据版本为 vi的数据，称在所有 N 个副本上都成功的更新操作为“成功提交的更新操作”，称对应的数据为“成功提交的数据”。 在 WARO 中，如果某次更新操作 wi在某个副本上失败，此时该副本的最新的数据只有 vi-1，由于不满足在所有 N 个副本上都成功，
则 wi 不是一个“成功提交的更新操作”，此时，虽然其他 N-1 个副本上最新的数据是 vi，但 vi不是一个“成功提交的数据”，最新的成功提交的数据只是 vi-1 。
在工程实践中，这种 magic 的机制往往较难实现或效率较低。通常实现这种 magic 机制的方式就是 将版本号信息存放到某个或某组元数据服务器上 。假如更新操作非常频繁，那么记录更新成功的版本号 vi的操作将成为一个关键操作，容易成为瓶颈。另外，为了实现强一致性，在读取数据的前必须首先读取元数据中的版本号，在大压力下也容易因为元数据服务器的性能造成瓶颈。
缺点:
WARO 的可用性。 由于更新操作需要在所有的 N 个副本上都成功，更新操作才能成功，所以一旦有一个副本异常，更新操作失败，更新服务不可用。对于更新服务，虽然有 N 个副本，
但系统无法容忍任何一个副本异常。另一方面， N 个副本中只要有一个副本正常，系统就可以提供读服务。对于读服务而言，当有 N 个副本时，系统可以容忍 N-1 个副本异常。
从上述分析可以发现 WARO 读服务的可用性较高，但更新服务的可用性不高 ，甚至虽然使用了
副本，但更新服务的可用性等效于没有副本.
2.Quorum 机制
将 WARO 的条件进行松弛，从而使得可以在 读写服务可用性之间做折中 ，得出 Quorum 机制.
在 Quorum 机制下，当某次更新操作 wi一旦在所有 N 个副本中的 W 个副本上都成功，则就称
该更新操作为“成功提交的更新操作”，称对应的数据为“成功提交的数据”。令 R>N-W，由于更新
操作 wi仅在 W 个副本上成功，所以在读取数据时，最多需要读取 R 个副本则一定能读到 wi 更新后的数据 vi 。如果某次更新 wi在 W 个副本上成功，由于 W+R>N，任意 R 个副本组成的集合一定与成功的 W 个副本组成的集合有交集，所以读取 R 个副本一定能读到 wi更新后的数据 vi。
例一:
某系统有 5 个副本， W=3， R=3，最初 5 个副本的数据一致，都是 v1， 某次更新操作
w2 在前 3 副本上成功，副本情况变成（v2 v2 v2 v1 v1）。此时， 任意 3 个副本组成的集合中一定包括v2。
例二:
N=5， W=2， R=3 时，若 4 个副本异常，更新操作始终无法完成。若 3 个副本异常时，
剩下的两个副本虽然可以提供更新服务，但对于读取者而言，在缺乏某些 magic 机制的，即如果读取者不知道当前最新已成功提交的版本是什么的时候，仅仅读取 2 个副本并不能保证一定可以读到最新的已提交的数据。
得出一个简单的结论:
仅 仅依赖 quorum 机制 是无法保证强一致性的。因为仅有 quorum 机制时 无法确定最新已成功提交的版本号 ，除非将最新已提交的版本号作为元数据由特定的元数据服务器或元数据集群管理，否则很难确定最新成功提交的版本号。
Quorum 机制只需成功更新 N 个副本中的 W 个，在读取 R 个副本时，一定可以读到 最新的成功
提交的数据。 但由于有不成功的更新情况存在，仅仅读取 R 个副本却不一定能确定哪个版本的数据是最新的已提交的数据(简而言之,就是说我读到的结果中包含了v1,v2我可以肯定最新的数据一定是他们两种的一个,但我却没办法确定是哪一个的)
例三:
在 N=5， W=3， R=3 的系统中，某时刻副本最大版本号为（v2 v2 v2 v1 v1）。注意，这里继续假设有 v2 的副本也有 v1，上述列出的只是最大版本号。此时，最新的成功提交的副本应该
是 v2，因为从全局看 v2已经成功更新了 3 个副本。 读取任何 3 个副本，一定能读到 v2。 但仅读 3 个副本时，有可能读到（v2 v1 v1）。 此时，由于 v2蕴含 v1， 可知 v1是一个成功提交的
版本， 但却不能判定 v2一定是一个成功提交的版本。 这是因为 ,假设**副本最大版本号为（v2 v1 v1 v1 v1）， 当读取 3 个副本时也可能读到v2 v1 v1） ,此时 v2是一个未成功提交的版本。 所
以在本例中，仅仅读到（v2 v1 v1）时，可以肯定的是最新的成功提交的数据要么是 v1要么是 v2，却没办法确定究竟是哪一个。
对于一个强一致性系统，应该始终读取返回最新的成功提交的数据，在 quorum 机制下，要达
到这一目的需要对读取条件做进一步加强。
1. 限制提交的 更新操作必须严格递增 ，即只有在前一个更新操作成功提交后才可以提交后一
个更新操作，从而成功提交的数据版本号必须是连续增加的。
2. 读取 R 个副本，对于 R 个副本中版本号最高的数据，
2.1 若已存在 W 个，则该数据为最新的成功提交的数据
2.2 若存在个数据少于 W 个， 假设为 X 个， 则继续读取其他副本，直若成功读取到 W 个
该版本的副本，则该数据为最新的成功提交的数据；如果在所有副本中该数据的个数肯定不满
足 W 个，则 R 中版本号第二大的为最新的成功提交的副本。
例四:
依旧接例三，在读取到（v2 v1 v1）时，继续读取剩余的副本，若读到剩余两个副本为（v2 v2）则 v2 是最新的已提交的副本；若读到剩余的两个副本为（v2 v1）或（v1 v1）则 v1是最新成功提交的版本；若读取后续两个副本有任一超时或失败，则无法判断哪个版本是最新的成功提交的版本。
可以看出，在单纯使用 Quorum 机制时，若要确定最新的成功提交的版本，最多需要读取 R+
（W-R-1）=N 个副本，当出现任一副本异常时，读最新的成功提交的版本这一功能都有可能不可用。
实际工程中，应该尽量通过其他技术手段，回避通过 Quorum 机制读取最新的成功提交的版本。例如，当 quorum 机制与 primary-secondary 控制协议结合使用时，可以通过读取 primary 的方式读取到最新的已提交的数据。
在 primary-secondary 协议中，当 primary 异常时，需要选择出一个新的 primary，之后 secondary副本与 primary 同步数据。 通常情况下，选择新的 primary 的工作是由某一中心节点完成的，在引入quorum 机制后，常用的 primary 选择方式与读取数据的方式类似，即中心节点读取 R 个副本，选择R 个副本中版本号最高的副本作为新的 primary。新 primary 与至少 W 个副本完成数据同步后作为新的 primary 提供读写服务。首先， R 个副本中版本号最高的副本一定蕴含了最新的成功提交的数据。再者，虽然不能确定最高版本号的数是一个成功提交的数据，但新的 primary 在随后与 secondary 同步数据，使得该版本的副本个数达到 W，从而使得该版本的数据成为成功提交的数据。
以上这段其实就是zk的原理
简述下就是先用Quorum 机制选择出primary(版本号最高的,版本号是严格递增的),然后再用primary-secondary来同步数据,(我一定可以读取到版本号最高的,虽然此时有可能是已提交也有可能为未提交)，但我同步之后可以保证该版本号的副本数达到w,从而使得该版本号的数据成为成功提交的数据.
例五:
在 N=5， W=3， R=3 的系统中，某时刻副本最大版本号为（v2 v2 v1 v1 v1），此时 v1是
系统的最新的成功提交的数据， v2 是一个处于中间状态的未成功提交的数据。假设此刻原 primary副本异常，中心节点进行 primary 切换工作。 这类“中间态”数据究竟作为“脏数据”被删除，还是作为新的数据被同步后成为生效的数据，完全取决于这个数据能否参与新 primary 的选举。此时有以下两种情况
情况一:
若中心节点与其中 3 个副本通信成功，读取到的版本号为（v1 v1 v1），则任
选一个副本作为 primary，新 primary以 v1 作为最新的成功提交的版本并与其他副本同步，当与第 1、第 2 个副本同步数据时，由于第 1、第 2 个副本版本号大于 primary，属于脏数据，删除脏数据,然后重新同步。
情况二:
若中心节点与其他 3 个副本通信成功，读取到的版本号为（v2 v1 v1）， 则选取版本号为v2 的副本作为新的 primary，之后，一旦新 primary 与其他 2 个副本完成数据同步，则符合 v2 的副本个数达到 W 个，成为最新的成功提交的副本，新 primary 可以提供正常的读写服务。
一致性算法在实现状态机这种应用时，有以下常见的问题：
1.1 一般的leader选举过程
选举的轮次
1.2 leader选举的效率
1.3 加入一个已经完成选举的集群
怎么发现已完成选举的leader？
1.4 leader选举的触发
3.3.2 异常过程的顺序
follower挂掉又连接
raft与zk的对比
1 leader选举
为什么要进行leader选举？
在实现一致性的方案，可以像base-paxos那样不需要leader选举，这种方案达成一件事情的一致性还好，面对多件事情的一致性就比较复杂了，所以通过选举出一个leader来简化实现的复杂性。
1.1 一般的leader选举过程
更多的有2个要素：
1.1.1 选举投票可能会多次轮番上演，为了区分，所以需要定义你的投票是属于哪个轮次的。
他们都需要在某个轮次内达成过半投票来结束选举过程
1.1.2 投票PK的过程，更多的是日志越新越多者获胜
在选举leader的时候，通常都希望
选举出来的leader至少包含之前全部已提交的日志
自然想到包含的日志越新越大那就越好。
通常都是比较最后一个日志记录，如何来定义最后一个日志记录？
有2种选择，一种就是所有日志中的最后一个日志，另一种就是所有已提交中的最后一个日志。目前Raft和ZooKeeper都是采用前一种方式。日志的越新越大表示：轮次新的优先，然后才是同一轮次下日志记录大的优先
ZooKeeper：peerEpoch大的优先，然后zxid大的优先
但是有一个问题就是：通过上述的日志越新越大的比较方式能达到我们的上述希望吗？
特殊情况下是不能的，这个特殊情况详细可参见我们上面描述的
这个案例就是这种比较方式会 选举出来的leader可能并不包含已经提交的日志(和我们例三分析的一样) ，而Raft的做法则是对于日志的提交多加一个限制条件，即不能直接提交之前term的已过半的entry，即把这一部分的日志限制成未提交的日志，从而来实现上述的希望。
ZooKeeper呢？会不会出现这种情况？又是如何处理的？
ZooKeeper是不会出现这种情况的，因为ZooKeeper在每次leader 选举完成之后，都会进行数据之间的同步纠正，所以每一个轮次，大家都日志内容都是统一的
而Raft在leader选举完成之后没有这个同步过程，而是靠之后的AppendEntries RPC请求的一致性检查来实现纠正过程，则就会出现上述案例中隔了几个轮次还不统一的现象
1.2 leader选举的效率
Raft中的每个server在某个term轮次内只能投一次票，哪个candidate先请求投票谁就可能先获得投票，这样就可能造成split vote，即各个candidate都没有收到过半的投票，Raft通过candidate设置不同的超时时间，来快速解决这个问题，使得先超时的candidate（在其他人还未超时时）优先请求来获得过半投票**
ZooKeeper中的每个server，在某个electionEpoch轮次内，可以投多次票，只要遇到更大的票就更新，然后分发新的投票给所有人。这种情况下不存在split vote现象，同时有利于选出含有更新更多的日志的server，但是选举时间理论上相对Raft要花费的多。
1.3 加入一个已经完成选举的集群
1.3.1 怎么发现已完成选举的leader？
一个server启动后（该server本来就属于该集群的成员配置之一，所以这里不是新加机器），如何加入一个已经选举完成的集群
1.3.2 加入过程是否阻塞整个请求？
这个其实还要 看对日志的设计是否是连续的
如果 是连续的，则leader中只需要保存每个follower上一次的同步位置，这样在同步的时候就会自动将之前欠缺的数据补上，不会阻塞整个请求过程(****所以为什么redis的选举算法是raft?毕竟redis单线程****)
如果 不是连续的，则在确认follower和leader当前数据的差异的时候，是需要获取leader当前数据的读锁，禁止这个期间对数据的修改。差异确定完成之后，释放读锁，允许leader数据被修改，每一个修改记录都要被保存起来，最后一一应用到新加入的follower中。
1.4 leader选举的触发
触发一般有如下2个时机
2 上一轮次的leader
2.1 上一轮次的leader的残留的数据怎么处理？
首先看下上一轮次的leader在挂或者失去leader位置之前，会有哪些数据？
一个日志是否被过半复制，是否被提交，这些信息是由leader才能知晓的，那么下一个leader该如何来判定这些日志呢？
下面分别来看看Raft和ZooKeeper的处理策略：
Raft的保守策略更多是因为Raft在leader选举完成之后，没有同步更新过程来保持和leader一致（在可以对外处理请求之前的这一同步过程）。而ZooKeeper是有该过程的
2.2 怎么阻止上一轮次的leader假死的问题
这其实就和实现有密切的关系了。
3 请求处理流程
3.1 请求处理的一般流程
这个过程对比Raft和ZooKeeper基本上是一致的，大致过程都是过半复制
先来看下Raft：
再来看看ZooKeeper：
备注:数据同步过程就有点类似于两阶段提交了。
假装是图2
3.2 日志的连续性问题
在需要保证顺序性的前提下，在利用一致性算法实现状态机的时候，到底是实现连续性日志好呢还是实现非连续性日志好呢？
还有在复制和提交的时候：
其他有待后续补充
3.3 如何保证顺序
具体顺序是什么？
这个就是先到达leader的请求，先被应用到状态机。这就需要看正常运行过程、异常出现过程都是怎么来保证顺序的
3.3.1 正常同步过程的顺序
3.3.2 异常过程的顺序保证
如follower挂掉又重启的过程：
ZooKeeper：重启之后，需要和当前leader数据之间进行差异的确定，同时期间又有新的请求到来，所以需要暂时获取leader数据的读锁，禁止此期间的数据更改，先将差异的数据先放入队列，差异确定完毕之后，还需要将leader中已提交的议案和未提交的议案也全部放入队列，即ZooKeeper的如下2个集合数据
ConcurrentMap<Long, Proposal> outstandingProposals
ConcurrentLinkedQueue<Proposal> toBeApplied
如果是leader挂了之后，重新选举出leader，会不会有乱序的问题？
3.4 请求处理流程的异常
一旦leader发给follower的数据出现超时等异常
4 分区的应对
目前ZooKeeper和Raft都是过半即可，所以对于分区是容忍的。如5台机器，分区发生后分成2部分，一部分3台，另一部分2台，这2部分之间无法相互通信
其中，含有3台的那部分，仍然可以凑成一个过半，仍然可以对外提供服务，但是它不允许有server再挂了，一旦再挂一台则就全部不可用了。
含有2台的那部分，则无法提供服务，即只要连接的是这2台机器，都无法执行相关请求。
所以ZooKeeper和Raft在一旦分区发生的情况下是是牺牲了高可用来保证一致性，即CAP理论中的CP。但是在没有分区发生的情况下既能保证高可用又能保证一致性，所以更想说的是所谓的CAP二者取其一，并不是说该系统一直保持CA或者CP或者AP，而是一个会变化的过程。在没有分区出现的情况下，既可以保证C又可以保证A，在分区出现的情况下，那就需要从C和A中选择一样。ZooKeeper和Raft则都是选择了C。
