Redis选举领头Sentinel（raft算法）

Sentinel是Redis实现高可用的保证。Sentinel系统作用就是监视Redis服务器集群，它可以不停的获得redis集群状态，当一个主节点挂了，故障转移操作会在从节点中选出一个新的主节点，这里故障转移就是由Sentinel来主导完成的。不要把Sentinel想的太复杂，它其实就是一个特殊工作模式的Redis服务器而已，Redis是集群部署的，这里的Sentinel也是要集群部署的，要是非单点部署，你的Sentinel挂了，此时的Redis集群就GG了。接着上边说，当主服务器节点挂了，Sentinel系统就会选出一个领头的Sentinel来完成故障转移工作。选举规则如下: - 监视这个挂了的主节点的所有Sentinel都有被选举为领头的资格

每进行一次选举，不论是否成功，配置纪元+1，配置纪元就是个计数器

每个Sentinel在每个配置纪元中有且仅有一次选举机会，一旦选好了该节点认为的主节点，在这个纪元内，不可以再更改

每个发现服务器挂了的Sentinel都会配置纪元+1并投自己一票，接着发消息要求其他Sentinel设置自己为领头人1，每个Sentinel都想成为领头的

每个Sentinel会将最先发来请求领头的节点设为自己的领头节点并发送回复，谁先来我选谁

当源Sentinel收到回复，并且回复中的配置纪元和自己的一致且领头Id是自己的Sentinel Id时，表明目标Sentinel已经将自己设为领头

在一个配置纪元内，当某个Sentinel收到半数以上的同意回复时，它就是领头的了

如果在给定时间内，没有被成功选举的Sentinel，那么过段时间发起新的选举

选举领头Sentinel的过程和规则大概就如上所述，需要注意的是只有集群出现节点挂了才需要选举出领头Sentinel，平时每个Sentinel还是平等身份~

Zookeeper选举

Zookeeper是一个很强的分布式数据一致性解决方案，比如dubbo中的注册中心就使用的Zookeeper。当然，这也是集群部署的，但是它没有采用传统的Master/Slave结构，而是引入了Leader、Follwer和Observer。Leader和Follower类似于Master/Slave，新增的Observer作用仅仅只是增加集群的读性能，它不参与Leader的选举。

节点的状态有以下几种：

LOOKING: 节点正处于选主状态，不对外提供服务，直至选主结束；

FOLLOWING: 作为系统的从节点，接受主节点的更新并写入本地日志；

LEADING: 作为系统主节点，接受客户端更新，写入本地日志并复制到从节点

Zookeeper的状态同步是基于Zab协议实现的，Zab协议有两种模式，它们分别是崩溃恢复（选主）和消息广播（同步）。当服务启动或者在Leader崩溃后，Zab就进入了恢复模式，当Leader被选举出来，且超过一半机器完成了和 leader的状态同步以后，恢复模式就结束了。

首先明确几个概念： - Sid：服务器id；

Zxid：服务器的事务id，数据越新，zxid越大；zxid的高32位是epoch，低32位是zpoch内的自增id，由0开始。每次选出新的Leader，epoch会递增，同时zxid的低32位清0。

整个选主流程如下

状态变更。服务器启动的时候每个server的状态时Looking，如果是leader挂掉后进入选举，那么余下的非Observer的Server就会将自己的服务器状态变更为Looking，然后开始进入Leader的选举状态；

发起投票。每个server会产生一个（sid，zxid）的投票，系统初始化的时候zxid都是0，如果是运行期间，每个server的zxid可能都不同，这取决于最后一次更新的数据。将投票发送给集群中的所有机器；

接收并检查投票。server收到投票后，会先检查是否是本轮投票，是否来自looking状态的server；

处理投票。对自己的投票和接收到的投票进行PK：

先检查zxid，较大的优先为leader；如果zxid一样，sid较大的为leader；根据PK结果更新自己的投票，再次发送自己的投票；

统计投票。每次投票后，服务器统计投票信息，如果有过半机器接收到相同的投票，那么leader产生，如果否，那么进行下一轮投票；

改变server状态。一旦确定了Leader，server会更新自己的状态为Following或者是Leading。选举结束。

我们要保证选主完成后，原来的主节点已经提交的事务继续完成提交；原主节点只是提出而没提交的事务要抛弃。这也是为什么倾向于选zxid最大的从节点为主节点，因为它上边的事务最新，最与原主节点保持一致。

哨兵模式(raft)与Zookeeper模式（zab）选主的总结

Redis中的Sentinel选主相对来说更简单，因为不涉及事务状态的一致性

Sentinel选主是基于raft协议，Zookeeper则基于Zab协议

二者都是收到半数的选票就选举成功

Sentinel投票发消息主要内容是Sentinel id和配置纪元，Zookeeper则是 zxid和 sid

Sentinel谁先来找他投票他就投谁，Zookeeper中则是要细细检查比较一番，检查内容包括epoch和节点状态，检查完毕后再跟自己的投票进行pk，进而看需不需要更新自己的投票，若是需要，则自己的投票也要广播出去

分布式选举的算法：bully , Raft，ZAB

分布式选举的算法：

Paxos 理论为基础而衍生出来的变种和简化版。例如 Google 的 Chubby、MegaStore、Spanner 等系统，ZooKeeper 的 ZAB 协议，还有更加容易理解的 raft 协议。大部分系统都是靠在实践中运行很长一段时间才能谨慎的表示，系统已基本运行，没有发现大的问题。

Bully算法：

在所有活着的节点中，选取 ID 最大的节点作为主节点。

集群中每个节点均知道其他节点的 ID

节点：主节点和普通节点

三种消息：Election 消息，用于发起选举；Alive 消息，对 Election 消息的应答；Victory 消息，竞选成功的主节点向其他节点发送的宣誓主权的消息。

eg：MongoDB 的副本集故障转移功能。MongoDB 的分布式选举中，采用节点的最后操作时间戳来表示 ID

优点：选举速度快、算法复杂度低、简单易实现。

缺点：需要每个节点有全局的节点信息；

前提条件

集群中的每个节点均知道其他节点的ID（mongo各个节点都会保存其他节点的快照信息）

任意一个比当前主节点 ID 大的新节点或节点故障后恢复加入集群的时候，都可能会触发重新选举，成为新的主节点，如果该节点频繁退出、加入集群，就会导致频繁切主。

Raft算法：

少数服从多数

redis - cluster用的该算法

eg：etcd 的集群管理器 etcds

Leader：主节点，同一时刻只有一个 Leader，负责协调和管理其他节点；

Candidate：即候选者，每一个节点都可以成为 Candidate，节点在该角色下才可以被选为新的 Leader；

Follower：Leader 的跟随者，不可以发起选举。

选举流程

初始化时，所有节点均为 Follower 状态。

开始选主时，所有节点的状态由 Follower 转化为 Candidate，并向其他节点发送选举请求。

其他节点根据接收到的选举请求的先后顺序，回复是否同意成为主。在每一轮选举中，一个节点只能投出一张票。

若发起选举请求的节点获得超过一半的投票，则成为主节点，其状态转化为 Leader，其他节点的状态则由 Candidate 降为 Follower。Leader 节点与 Follower 节点之间会定期发送心跳包，以检测主节点是否活着。

当 Leader 节点的任期到了，Leader 节点的状态由 Leader 降级为 Follower，进入新一轮选主。

优点：选举速度快、算法复杂度低、易于实现的优点

缺点：要求系统内每个节点都可以相互通信，且需要获得过半的投票数才能选主成功，因此通信量大

ZAB算法：

相较于 Raft 算法的投票机制，ZAB 算法增加了通过节点 ID 和数据 ID 作为参考进行选主，节点 ID 和数据 ID 越大，表示数据越新，优先成为主。

选举原则：server_zxID 最大者成为 Leader；若 server_zxID 相同，则 server_id 最大者成为 Leader。

server_id 表示本节点的唯一 ID；

server_zxID 表示本节点存放的数据 ID，数据 ID 越大表示数据越新，选举权重越大；

epoch 表示当前选取轮数，一般用逻辑时钟表示。

优点：稳定性比较好，性能高。

缺点：每个节点同时广播，每个节点同时广播。对比节点 ID 和数据 ID，需要知道所有节点的 ID 和数据 ID，所以选举时间相对较长。

eg：ZooKeeper 实现分布式协调功能

深入ZAB算法

ZAB算法分为两大块内容，消息广播和崩溃恢复。

消息广播（boardcast）：Zab 协议中，所有的写请求都由 leader 来处理。正常工作状态下，leader 接收请求并通过广播协议来处理。

崩溃恢复（recovery）：当服务初次启动，或者 leader 节点挂了，系统就会进入恢复模式，直到选出了有合法数量 follower 的新 leader，然后新 leader 负责将整个系统同步到最新状态。

ZAB消息广播过程

Zookeeper集群中，存在以下三种角色的节点：

Leader：Zookeeper集群的核心角色，在集群启动或崩溃恢复中通过Follower参与选举产生，为客户端提供读写服务，并对事务请求进行处理。 Follower：Zookeeper集群的核心角色，在集群启动或崩溃恢复中参加选举，没有被选上就是这个角色，为客户端提供读取服务，也就是处理非事务请求，Follower不能处理事务请求，对于收到的事务请求会转发给Leader。 Observer：观察者角色，不参加选举，为客户端提供读取服务，处理非事务请求*，对于收到的事务请求会转发给Leader。使用Observer的目的是为了扩展系统，提高读取性能。

Leader 接收到消息请求后，将消息赋予一个全局唯一的 64 位自增 id，叫做：zxid，通过 zxid 的大小比较即可实现因果有序这一特性。

Leader 通过先进先出队列（通过 TCP 协议来实现，以此实现了全局有序这一特性）将带有 zxid 的消息作为一个提案（proposal）分发给所有 follower。

当 follower 接收到 proposal，先将 proposal 写到硬盘，写硬盘成功后再向 leader 回一个 ACK。

当 leader 接收到合法数量的 ACKs 后，leader 就向所有 follower 发送 COMMIT 命令，同时会在本地执行该消息。

当 follower 收到消息的 COMMIT 命令时，就会执行该消息。

相比于完整的二阶段提交，Zab 协议最大的区别就是不能终止事务，follower 要么回 ACK 给 leader，要么抛弃 leader，在某一时刻，leader 的状态与 follower 的状态很可能不一致，因此它不能处理 leader 挂掉的情况，所以 Zab 协议引入了恢复模式来处理这一问题。

从另一角度看，正因为 Zab 的广播过程不需要终止事务，也就是说不需要所有 follower 都返回 ACK 才能进行 COMMIT，而是只需要合法数量（2n+1 台服务器中的 n+1 台） 的follower，也提升了整体的性能。

（commit类似两阶段提交的commit，一般错误概率非常小），可能出现的就是主节点挂了的情况，主节点commit，其他节点还没收到

Leader 服务器与每一个 Follower 服务器之间都维护了一个单独的 FIFO 消息队列进行收发消息，使用队列消息可以做到异步解耦。 Leader 和 Follower 之间只需要往队列中发消息即可。如果使用同步的方式会引起阻塞，性能要下降很多。

选举参数

在介绍选举流程之前，需要介绍几个参数，

myid: 服务器ID，这个是在安装Zookeeper时配置的，myid越大，该服务器在选举中被选为Leader的优先级会越大。ZAB算法中通过myid来规避了多个节点可能有相同zxid问题，注意可以对比之前的Raft算法，Raft算法中通过随机的timeout来规避多个节点可能同时成为Leader的问题。

zxid: 事务ID，这个是由Zookeeper集群中的Leader节点进行Proposal时生成的全局唯一的事务ID，由于只有Leader才能进行Proposal，所以这个zxid很容易做到全局唯一且自增。因为Follower没有生成zxid的权限。zxid越大，表示当前节点上提交成功了最新的事务，这也是为什么在崩溃恢复的时候，需要优先考虑zxid的原因。

epoch: 投票轮次，每完成一次Leader选举的投票，当前Leader节点的epoch会增加一次。在没有Leader时，本轮此的epoch会保持不变。

另外在选举的过程中，每个节点的当前状态会在以下几种状态之中进行转变。

LOOKING: 竞选状态。

FOLLOWING: 随从状态，同步Leader 状态，参与Leader选举的投票过程。

OBSERVING: 观察状态，同步Leader 状态，不参与Leader选举的投票过程。

LEADING: 领导者状态。

选举流程

选举的流程如下：

每个Server会发出一个投票,第一次都是投自己。投票信息：（myid，ZXID）

收集来自各个服务器的投票

处理投票并重新投票，处理逻辑：优先比较ZXID,然后比较myid

统计投票，只要超过半数的机器接收到同样的投票信息，就可以确定leader

改变服务器状态，进入正常的消息广播流程。

ZAB算法需要解决的两大问题

  1. 已经被处理的消息不能丢

这一情况会出现在以下场景：当 leader 收到合法数量 follower 的 ACKs 后，就向各个 follower 广播 COMMIT 命令，同时也会在本地执行 COMMIT 并向连接的客户端返回「成功」。但是如果在各个 follower 在收到 COMMIT 命令前 leader 就挂了，导致剩下的服务器并没有执行都这条消息。

为了实现已经被处理的消息不能丢这个目的，Zab 的恢复模式使用了以下的策略：

选举拥有 proposal 最大值（即 zxid 最大） 的节点作为新的 leader：由于所有提案被 COMMIT 之前必须有合法数量的 follower ACK，即必须有合法数量的服务器的事务日志上有该提案的 proposal，因此，只要有合法数量的节点正常工作，就必然有一个节点保存了所有被 COMMIT 的 proposal。 而在选举Leader的过程中，会比较zxid，因此选举出来的Leader必然会包含所有被COMMIT的proposal。

新的 leader 将自己事务日志中 proposal 但未 COMMIT 的消息处理。

新的 leader 与 follower 建立先进先出的队列， 先将自身有而 follower 没有的 proposal 发送给 follower，再将这些 proposal 的 COMMIT 命令发送给 follower，以保证所有的 follower 都保存了所有的 proposal、所有的 follower 都处理了所有的消息。

2. 被丢弃的消息不能再次出现

（通过没有发送ack可以判断是否要删除）

这一情况会出现在以下场景：当 leader 接收到消息请求生成 proposal 后就挂了，其他 follower 并没有收到此 proposal，因此经过恢复模式重新选了 leader 后，这条消息是被跳过的。 此时，之前挂了的 leader 重新启动并注册成了 follower，他保留了被跳过消息的 proposal 状态，与整个系统的状态是不一致的，需要将其删除。

Zab 通过巧妙的设计 zxid 来实现这一目的。一个 zxid 是64位，高 32 是纪元（epoch）编号，每经过一次 leader 选举产生一个新的 leader，新 leader 会将 epoch 号 +1。低 32 位是消息计数器，每接收到一条消息这个值 +1，新 leader 选举后这个值重置为 0。这样设计的好处是旧的 leader 挂了后重启，它不会被选举为 leader，因为此时它的 zxid 肯定小于当前的新 leader。当旧的 leader 作为 follower 接入新的 leader 后，新的 leader 会让它将所有的拥有旧的 epoch 号的未被 COMMIT 的 proposal 清除。

Zab 协议设计的优秀之处有两点，一是简化二阶段提交，提升了在正常工作情况下的性能；二是巧妙地利用率自增序列，简化了异常恢复的逻辑，也很好地保证了顺序处理这一特性