Paxos
ZAB协议
ZAB (Zookeeper Atomic Broadcast, Zookeeper 原子消息广播协议)继承了Paxos的理念专门为zookeeper设计的一套数据一致性算法。
ZK 使用一个单一的主进程来保持集群中各副本之间数据的一致性；
将服务器数据的状态变更以事物 Proposal 的形式广播到所有的副本进程上去；
ZAB 协议包括两种基本模式：崩溃恢复 和 消息广播
消息广播
详细过程：
Leader 服务器会为每个事物请求生成对应的 Proposal 来进行广播，并在广播之前为 Proposal 分配一个全局单调递增的唯一 ID（即 ZXID）；
Leader 服务器为每个 Follower 服务器各自分配一个单独的队列，将要广播的 Proposal 依次放入队列中，并根据 FIFO 策略进行消息发送；
每个 Follower 服务器在收到 Proposal 后，会先将其以事物日志的形式写入本地磁盘，写入成功后，给 Leader 返回 Ack；
当 Leader 收到超过半数 Follower 的 Ack 响应后，就会广播 Commit 消息给所有 Follower 服务器通知其开始事物提交；
存在问题：无法处理 Leader 服务器崩溃退出而带来的数据不一致问题，所以 ZAB 协议增加了 崩溃恢复 模式；
崩溃恢复
当服务框架在启动中或 Leader 服务器出现网络中断、崩溃、重启情况时，ZAB协议就会进入恢复模式并选举新的Leader；
ZXID
在 ZAB 协议的事物编号 ZXID 设计中，ZXID 是一个 64 位的数字，低 32 位是简单单调递增计数器，每一个客户端请求 Leader 生成新事物 Proposal 对该计数器 +1；
高 32 位表示 Leader 周期 epoch 编号，每当选举产生一个新的 Leader 服务器，就会从这个 Leader 服务器上取出本地日志最大失误 Proposal 的 ZXID，并从 ZXID 中解析出对应的 epoch 值，并 +1，之后就以此编号作为新的 epoch，并将低 32 位，置 0 来开始新的 ZXID；
集群启动时，Leader 选举
上图中，(1, 1, 0)
- 第一位数代表投出该选票的服务器的logicClock;
- 第二位数代表被推荐的服务器的myid;
- 第三位代表被推荐的服务器的最大的zxid;
由于该步骤中所有选票都投给自己，所以第二位的myid即是自己的myid，第三位的zxid即是自己的zxid。此时各自的票箱中只有自己投给自己的一票
服务器收到外部投票后，进行选票PK，相应更新自己的选票并广播出去，并将合适的选票存入自己的票箱。
服务器1收到服务器2的选票（1, 2, 0）和服务器3的选票（1, 3, 0）后，由于所有的logicClock都相等，所有的zxid都相等，因此根据myid判断应该将自己的选票按照服务器3的选票更新为（1, 3, 0），并将自己的票箱全部清空，再将服务器3的选票与自己的选票存入自己的票箱，接着将自己更新后的选票广播出去。此时服务器1票箱内的选票为(1, 3)，(3, 3)。
同理，服务器2收到服务器3的选票后也将自己的选票更新为（1, 3, 0）并存入票箱然后广播。此时服务器2票箱内的选票为(2, 3)，(3, ,3)。
服务器3根据上述规则，无须更新选票，自身的票箱内选票仍为（3, 3）。
服务器1与服务器2更新后的选票广播出去后，由于三个服务器最新选票都相同，最后三者的票箱内都包含三张投给服务器3的选票。
三个服务器一致认为此时服务器3应该是Leader。因此服务器1和2都进入FOLLOWING状态，而服务器3进入LEADING状态。之后Leader发起并维护与Follower间的心跳。
集群运行时，Leader 选举
当过半机器与 Leader 完成状态同步后，ZAB 协议退出恢复模式；
Raft协议
Raft协议在功能上是完全等同于(Multi)-Paxos协议的。Raft也是一个原子广播协议（原子广播协议参见《由浅入深理解Paxos协议（1）》），它在分布式系统中的功能以及使用方法和Paxos是完全一样的。我们可以用Raft来替代分布式系统中的Paxos协议
Raft的设计理念
严格来说Raft并不属于Paxos的一个变种。Raft协议并不是对Paxos的改进，也没有使用Paxos的基础协议（The Basic Protocol）。Raft协议在设计理念上和Paxos协议是完全相反的。正是由于这个完全不同的理念，使得Raft协议变得简单起来。
Paxos协议中有一个基本的假设前提：可能会同时有多个Leader存在。这里把Paxos协议执行的过程分为以下两个部分：
Leader选举
数据广播
在《由浅入深理解Paxos协议（2）》的“Leader的选取”一节中提到过，Paxos协议并没有给出详细的Leader选举机制。Paxos对于Leader的选举没有限制，用户可以自己定义。这是因为Paxos协议设计了一个巧妙的数据广播过程，即Paxos的基本通讯协议（The Basic Protocol）。它有很强的数据一致性保障，即使在多个Leader同时出现时也能够保证广播数据的一致性。
而Raft协议走了完全相反的一个思路：保证不会同时有多个Leader存在。因此Raft协议对Leader的选举做了详细的设计，从而保证不会有多个Leader同时存在。相反，数据广播的过程则变的简单易于理解了。
Raft的日志广播过程
为了保证数据被复制到多数的节点上，Raft的广播过程尽管简单仍然要使用多数派协议，只是这个过程要容易理解的多：
发送日志到所有Followers（Raft中将非Leader节点称为Follower）；
Followers收到日志后，应答收到日志；
当半数以上的Followers应答后，Leader通知Followers日志广播成功；
日志和日志队列
Raft将用户数据称作日志（Log），存储在一个日志队列里。每个节点上都有一份。队列里的每个日志都一个序号，这个序号是连续递增的不能有缺。
日志队列里有一个重要的位置叫做提交日志的位置（Commit Index）。将日志队列里的日志分为了两个部分：
已提交日志：已经复制到超过半数节点的数据，这些是可以让应用读取到的日志；
未提交日志：还未复制到超过半数节点的数据；
当Followers收到日志后，将日志按顺序存储到队列里。但这时Commit Index不会更新，因此这些日志是未提交的日志，不能被读取到。当Leader收到超过半数的Followers的应答后，会更新自己的Commit Index，并将Commit Index广播到Followers上。这时Followers更新Commit Index，未提交的日志就变成了已提交的日志，可以被应用程序去读取到了。
从上面的解释我们可以知道，日志队列中已经提交的日志是不可改变的，而未提交的日志则可以被更新成其他的日志（在Leader发生变化时会发生）。
Raft的Leader选举
Raft称它的Leader为“Strong Leader”。Strong Leader 有以下特点：
同一时间只有一个Leader；
只能从Leader向Followers发送数据，反之不行；
下面我们看一下Raft通过哪些机制来实现Strong Leader。
多数派协议
为了保证只有一个Leader被选举出来，选举的过程使用了多数派协议。这样很好理解，当一个Candidate（申请成为Leader的节点）请求成为Leader时，只有半数以上的Followers同意后，才能成为Leader。投票过程如下：
当发现Leader无响应后（一段时间内没有日志或心跳），Candidate发送投票请求；
Followers投票；
如果超过半数的Followers投了票，则Candidate自动变成Leader，开始广播日志；
随机超时机制
和《由浅入深理解Paxos协议（1）》中提到问题一样，这里也会发生多个Candidate同时发送投票请求，而导致谁都不能够得到多数赞成票的情况，有可能永远也选不出Leader。为了保证Leader选举的效率，Raft在投票选举中使用了随机超时的机制：
在每个Followers上设定的Leader超时时间是在一个范围内随机的。这样可以尽量让Followers不在同一时间发起Leader选举；
每个Candidate发起投票后，如果在一段时间内没有任何Candidate称为Leader则，需要重新发起Leader选举。这段等待的时间，在每个Candidate上也是随机的。从而保证不会有多个Candidate同时重新发起Leader选举。
虽说是随机的超时时间，但是也有个范围，太小或者太大都会影响系统的可用性。太小会导致过多的选举冲突，太大又会影响系统的平滑运行。在Raft的论文中，作者将这个超时时间称为electionTimeout，并给出了合理的范围，公式如下：
broadcastTime ≪ electionTimeout ≪ MTBF≪ 代表数量级上的差异（10倍以上）。
日志长度过半机制
Candidate的日志长度要等于或者超过半数节点才能选为Leader。
当Leader故障时，Followers上日志的状态很可能是不一致的。有的多有的少，而且Commit Index也不尽相同。
我们知道已经提交的日志是不能够丢弃的，必须要最终复制到所有的节点上才行。假如在选Leader时，图中Candidate A变成了Leader，就必须要首先从Candidate B上将日志4复制过来，然后才能开始处理新的日志。为了减少复杂性，raft就规定，只有包含了所有已提交日志的Candidate才能当选为Leader。
实现也很简单：
当发现Leader无响应后（一段时间内没有数据或心跳），Candidate发送投票请求，请求中包含自己日志队列的长度（或者说最大日志的Index）；
Followers检查Candidate的日志长度，只有Candidate的日志等于或者长于自己才投票；
如果超过半数的Followers投了票，则Candidate自动变成Leader，开始广播数据；
因为已经提交的日志一定被复制到了多数节点上，所以日志长度等于或者长于多数节点的Candidate一定包含了所有已经提交的日志。
为什么不是检查Commit Index？
因为Leader故障时，很有可能只有Leader的Commit Index是最大的。
如果图中的Candidate A被选举为Leader，那么日志4就会被丢弃。但是日志4已经在原来的Leader上提交了，因此必须被保留才行。所以只能让日志长度更长的Candidate B选为Leader。这种做法有可能把原来Leader没广播完成的日志（图中的日志5）接着广播完成，这没有什么关系。
Followers日志补齐
当Leader故障时，Followers上的日志状态是不一样的，有长有短。因此新的Leader选出后，首先要将所有Followers的日志补齐才行。因此Leader要询问Followers的日志长度，从最小的日志位置开始补齐。
Followers未提交日志的更新
新Leader的日志一定包含所有已经提交的日志。但新Leader的日志不一定是最长的，那些新Leader没有的日志，一定是未提交的日志，因此可以被更新，没有关系的。Leader只需要从自己的当前位置开始插入日志并广播出去就可以了。Followers会用新的日志去更新指定位置上的日志。
新旧Leader的交替
新的Leader选出后，开始广播日志。这时如果旧的Leader故障恢复了（比如网络临时中断），并且还认为自己是Leader，也会广播日志。这不就导致了同时有两个Leader出现吗？是的，Raft也没办法让旧的Leader不发日志，但是Raft有办法让Followers拒绝旧Leader的日志。
Term
Raft将时间划分为连续的时间段，称为Term。 Term是指从一次Leader选举开始到下一次Leader选举的一段时间。这段时间内只能有一个Leader被选举成功，并负责管理系统或者没有Leader选出。
每个Term都有一个唯一的数字编号。所有Term的数字编号是从小到大连续排列的。
作废旧Leader
Term编号在作废旧Leader的过程中至关重要，但却十分简单。过程如下：
发送日志到所有Followers，Leader的Term编号随日志一起发送;
Followers收到日志后，检查Leader的Term编号。如果Leader的Term编号等于或者大于自己的当前Term（Current Term）编号，则存储日志到队列并且应答收到日志。否则发送失败消息给Leader，消息中包含自己的当前Term编号。
当Leader收到任何Term编号比自己的Term编号大的消息时，则将自己变成Follower。收到的消息包括：Follower给自己的回复消息、新Leader的日志广播消息、Leader的选举消息。
Gossip协议
RedisCluster是基于Gossip协议的PING/PONG通讯来保证数据分片集群中的状态一致性。
Gossip协议主要用在分布式系统中各个节点的数据同步。
Gossip协议原理
Gossip协议由种子节点发起请求（种子节点即状态发生改变的节点），当一个种子节点有状态需要更新到网络中的其他节点时，它会随机选择周围几个节点进行散播消息，收到消息的节点也会重复此过程，直至网络中的所有节点都收到消息，这个过程需要一定的时间，因此Gossip是一个最终一致性协议。
Gossip协议中提供了三种通讯类型：
PUSH类型：A节点将数据发送给B节点，B节点更新A节点比自己新的数据。
PULL类型：A节点将数据发送给B节点，B节点返回比A节点新的数据，A节点再更新自己。
PULL/PUSH类型：A节点将数据发送给B节点，B节点返回比A节点新的数据，A节点再更新自己，然后A节点将数据发送给B节点，B节点更新A节点比自己新的数据。
PUSH类型发送一次请求，目的是让其他节点更新。
PULL类型发送两次请求，目的是更新自身节点的信息。
每个消息都有一个时间戳，用来区分新老信息。
RedisCluster中的PING/PONG通讯
PING：发送集群中节点的信息、角色、集群ID、时间戳。
PONG：响应PING的请求。
PING请求即Gossip协议中的PUSH，目的是让其他节点进行更新。
RedisCluster中的每个节点都会定期的向其他节点发送PING请求，用于集群间状态的同步以及检测节点的可用性。
当集群中有新节点加入时（经过Meet操作），该节点会向其他节点发送PING请求，同时其他节点也会向其发送PING请求，最终达到数据一致性。
RedisCluster中的节点故障是通过Master投票决定的，当有半数的Master认为该节点故障时，那么集群认为该节点故障，如果故障的节点是Master，那么会将其Slave节点切换为Master。
当RedisCluster中有一半的Master同时失效，那么整个集群将不可用，因为已经没有足够的Master进行投票。