分布式一致性算法与分布式共识算法_共识一致性算法

raft 算法

redis 的哨兵选举机制，使用了 raft 算法，Raft 本来是一个用户管理日志一致性的协议。在大多数哨兵认定主机客观下线之后，就需要进行性的哨兵选举了

大致按照如下顺序：

• 每个做主观下线的 sentinel 节点向其他 sentinel 节点发送命令，要求将自己设置为领导者，并且投自己一票
• 接收到的 sentinel 可以同意或者拒绝
• 如果该 sentinel 节点发现自己的票数已经超过半数并且超过了 quorum
• 如果此过程选举出了多个领导者，那么将等待一段时重新进行选举。选出 Leader 后 Leader 会从从机中选举出合适的丛机进行故障转移

raft 他其实重点侧重于在一群机器中选择出一个老大，而且他最初的目的是管理日志一致性，即这个老大原本应该会受到请求，并且把请求作为日志条目加入到它的日志中，然后并行的向其他服务器发起请求以复制日志条目。当这条日志被复制到大多数服务器上，Leader 将这条日志应用到它的状态机并向客户端返回执行结果。redis 只借鉴了它前半部分，舍弃了后半部分

Paxos 算法

Paxos 算法是基于消息传递且具有高度容错特性的一致性算法，是目前公认的解决分布式一致性问题最有效的算法之一，其解决的问题就是在分布式系统中如何就某个值（决议）达成一致

paxos 算法是分布式共识算法，它和 2PC、3PC 的区别是它实现的是最终一致性，即算法执行后，允许部分节点没有更新值的状态存在，以此它更适合去处理一些业务相关的数据，而 2PC 则偏向处理集群管理相关的功能

paxos 算法属于操作转移，可以类比记录了一些日志来存放数据，如同 redolog 一样；而 2PC 则是状态转移，即同步的是值

算法过程

简单来说就是将集群分为提案者、决策者和记录者，集群一起维护了一个单调递增的方案 ID，通过半数投票的方式，来界定方案中的日志是否需要记录。以下是具体算法流程

准备阶段：每个提案者在提出提案时都会首先获取到一个具有全局唯一性的、递增的提案编号 N，然后将该编号赋予其要提出的提案，在第一阶段是只将提案编号发送给所有的表决者；

表决者在收到某提案后，会将该提案编号 N 记录在本地，每个表决者仅会通过编号大于自己本地增大编号的提案，在批准提案时表决者会将以前接受过的最大编号的提案作为响应反馈给 Proposer

执行阶段：如果提案者收到了超过半数的批准，那么此时提案者会给所有的参与者发送真正的提案，这个时候提案者会发送提案的内容和提案编号

表决者收到提案请求后会再次比较本身已经批准过的最大提案编号和该提案编号，如果该提案编号大于等于已经批准过的最大提案编号，那么就执行该提案（此时执行提案内容但不提交），随后将情况返回给提案者，如果不满足则不回应或者返回 NO

当提案者收到超过半数的 accept，那么它这个时候会向所有的参与者发送提案的提交请求让它们强制执行该提案；提案者如果没有收到超过半数的 accept，那么它将会将递增该提案的编号，然后重新进入准备阶段

死循环问题：该算法有一个死循环问题，有多个提案者时，它们会互相递增提案编号导致谁也执行不了，解决方法就是只设定一个提案者即可

Gossip 协议

Gossip 算法如其名，在办公室，只要一个人八卦一下，在有限的时间内所有的人都会知道该八卦的信息，这种方式也与病毒传播类似，因此 Gossip 有众多的别名，如“闲话算法”、“疫情传播算法”、“病毒感染算法”、“谣言传播算法”。但 Gossip 并不是一个新东西，之前的泛洪查找、路由算法都归属于这个范畴，不同的是 Gossip 给这类算法提供了明确的语义、具体实施方法及收敛性证明

Gossip 算法又被称为反熵（Anti-Entropy），熵是物理学上的一个概念，代表杂乱无章，而反熵就是在杂乱无章中寻求一致，这充分说明了 Gossip 的特点：在一个有界网络中，每个节点都随机地与其它节点通信，经过一番杂乱无章的通信，最终所有节点的状态都会达成一致。每个节点可能知道所有其它节点，也可能仅知道几个邻居节点，只要这些节可以通过网络连通，最终它们的状态都是一致的

要注意到的一点是，即使有的节点因宕机而重启，有新节点加入，但经过一段时间后，这些节点的状态也会与其他节点达成一致，也就是说，Gossip 天然具有分布式容错的优点

ZAB 协议

ZooKeeper 在解决分布式数据一致性问题自己写了一个协议叫 ZAB，该协议可以更好的支持崩溃恢复

崩溃恢复模式

当新建一个集群或者 Leader 挂掉之后会进入该模式，流程如下：

开始时我们按一定顺序启动集群中的机器，被启动的机器会首先投票给自己，投票内容为服务器的 myid 和 ZXID（服务器保存的最大提案 id），然后将消息广播出去，所有机器在收到投票信息后会将投票信息与自己的作比较。首先它会比较 ZXID，ZXID 大的优先为 Leader，如果相同则比较 myid，myid 大的优先作为 Leader

执行以上过程直到某台机器的票数超过半数，该机器成为 Leader

崩溃恢复需要满足的要求

Zab 协议崩溃恢复要求满足以下两个要求：

1）确保已经被 Leader 提交的提案必须最终被所有的 Follower 服务器提交
2）确保丢弃已经被 Leader 提出的但是没有被提交的提案

消息广播模式

当集群中存在 Leader 时，自动进入消息广播模式，流程如下：

客户端发起一个写操作请求，从机收到请求后会将该请求发给主机

Leader 服务器将求转化为事务提案，同时为每个提案分配一个全局的 ID，Leader 服务器为每个Followe 服务器分配一个单独的队列，然后将需要广播的提案依次放到队列中，并且根据 FIFO 策略进行消息发送

Follower 接收到提案后，会首先将其以事务日志的方式写入本地磁盘中，写入成功后 Leader 反馈一个响应消息

Leader 接收到超过半数以上 Follower 的成功响应消息后，即认为消息发送成功，发送提交消息，自身也会完成事务提交

Leader 服务器与每一个 Follower 服务器之间都维护了一个单独的 FIFO 消息队列进行收发消息，使用队列消息可以保证数据传输的顺序性。请求处理的顺序不同就会导致数据的不同，从而产生数据不一致问题