共识（raft）算法

大家好，我是讯享网，很高兴认识大家。

一、引言

Raft是一个共识算法（consensus algorithm），所谓共识，就是多个节点对某个事情达成一致的看法，即使是在部分节点故障、网络延时、网络分割的情况下。这些年最为火热的加密货币（比特币、区块链）就需要共识算法，而在分布式系统中，共识算法更多用于提高系统的容错性。

二、算法介绍

【百度百科】Raft是一种共识算法，旨在替代Paxos。它通过逻辑分离比Paxos更容易理解，但它也被正式证明是安全的，并提供了一些额外的功能。Raft提供了一种在计算系统集群中分布状态机的通用方法，确保集群中的每个节点都同意一系列相同的状态转换。Raft 通过选举一个高贵的领导人，然后给予他全部的管理复制日志的责任来实现一致性。

Raft通过当选的领导者达成共识。集群中的服务器是领导者或追随者，并且在选举的精确情况下可以是候选者（领导者不可用）。领导者负责将日志复制到关注者。它通过发送心跳消息定期通知追随者它的存在。每个跟随者都有一个超时（通常在150到300毫秒之间），它定期接收领导者的心跳。接收到心跳时重置超时时间。如果没有收到心跳，则关注者将其状态更改为候选人并开始领导选举。

每个 server 都可能会在 3 个身份之间切换：

领导者（Leader）
候选者（Candidate）
跟随者（Follower）

而影响他们身份变化的则是选举。
当所有服务器初始化的时候，都是跟随者，这个时候需要一个领导者，所有人都变成候选者，直到有人成功当选领导者。
在这里插入图片描述
讯享网

每个节点上都有一个倒计时器 (Election Timeout)，时间随机在 150ms 到 300ms 之间。有几种情况会重设 Timeout：

收到选举的请求
收到 Leader 的 Heartbeat (后面会讲到)

在 Raft 运行过程中，最主要进行两个活动：

选主 Leader Election
复制日志 Log Replication

三、算法详解

1.Raft 算法选主的具体流程：

第一步，在最初，还没有一个主节点的时候，所有节点的身份都是Follower。每一个节点都有自己的计时器，当计时达到了超时时间（Election Timeout），该节点会转变为Candidate。
在这里插入图片描述

第二步，成为Candidate的节点，会首先给自己投票，然后向集群中其他所有的节点发起请求，要求大家都给自己投票。
在这里插入图片描述

第三步，其他收到投票请求且还未投票的Follower节点会向发起者投票，发起者收到反馈通知后，票数增加。
在这里插入图片描述

第四步，当得票数超过了集群节点数量的一半，该节点晋升为Leader节点。Leader节点会立刻向其他节点发出通知，告诉大家自己才是老大。收到通知的节点全部变为Follower，并且各自的计时器清零。
在这里插入图片描述

这里需要说明一点，每个节点的超时时间都是不一样的。比如A节点的超时时间是3秒，B节点的超时时间是5秒，C节点的超时时间是4秒。这样一来，A节点将会最先发起投票请求，而不是所有节点同时发起。为什么这样设计呢？设想如果所有节点同时发起投票，必然会导致大家的票数差不多，形成僵局，谁也当不成老大。那么，成为Leader的节点是否就坐稳了老大的位置呢？并不是。Leader节点需要每隔一段时间向集群其他节点发送心跳通知，表明你们的老大还活着。
一旦Leader节点挂掉，发不出通知，那么计时达到了超时时间的Follower节点会转变为Candidate节点，发起选主投票，周而复始…
在这里插入图片描述