Raft

Raft透过选举领袖（英语：leader）的方式做共识算法。

在Raft集群（英语：Raft cluster）里，服务器可能会是这三种身份其中一个：领袖（英语：leader）、追随者（英语：follower），或是候选人（英语：candidate）^[2]:5。在正常情况下只会有一个领袖，其他都是追随者^[2]:5。而领袖会负责所有外部的请求，如果不是领袖的机器收到时，请求会被导到领袖^[2]:5。

通常领袖会借由固定时间发送消息，也就是“心跳（英语：heartbeat）”^[2]:5，让追随者知道集群的领袖还在运作。而每个追随者都会设计超时机制（英语：timeout），当超过一定时间没有收到心跳（通常是150 ms或300 ms^[2]:6），集群就会进入选举状态。

Raft将问题拆成数个子问题分开解决^[2]:1，让人更容易了解：

• 领袖选举（英语：Leader Election）
• 记录复写（英语：Log Replication）
• 安全性（英语：Safety）

领袖选举

在起始算法或领袖死机、断线的时候，就需要选举出新的领袖。

此时集群进入新的任期（英语：term）并开始选举，如果选举成功则新的领袖开始执行工作，反之则视此任期终止，开始新的任期并开始下一场选举。

选举是由候选人发动的。当领袖的心跳超时的时候，追随者就会把自己的任期编号（英语：term counter）加一、宣告竞选、投自己一票、并向其他服务器拉票。每个服务器在每个任期只会投一票，固定投给最早拉票的服务器。

如果候选人收到其他候选人的拉票、而且拉票的任期编号不小于自己的任期编号，就会自认落选，成为追随者，并认定来拉票的候选人为领袖。如果有候选人收到过半的选票就当选为新的领袖。如果超时仍没有选出新领袖，此任期自动终止，开始新的任期并开始下一场选举。

Raft每个服务器的超时期限是随机的，这降低伺服务同时竞选的几率，也降低因两个竞选人得票都不过半而选举失败的几率。

记录复写

记录复写的责任在领袖身上。

整个集群有个复写的状态机（英语：state machine），可执行外来的指令。领袖接收指令，将之写入自己记录中的新指令部分，然后把指令转发给追随者。如果有追随者没反应，领袖会不断重发指令、直到每个追随者都成功将新指令写入记录为止。

当领袖收到过半追随者确认写入的消息，就会把指令视为已存储（英语：committed）。当追随者发现指令状态变成已存储，就会在其状态机上执行该指令。

当领袖死机时，领袖的某些新指令可能还没复写到集群整体，造成集群的记录处于不一致的状态。新领袖会担起重返一致的责任，让每个追随者的记录都和它的一致，做法是：和每个追随者比对记录，找出两者一致的最后一笔指令，删除追随者之后的指令，把自己之后的指令拷贝给追随者。这个机制完成时，每个服务器的记录就会一致。

安全性

Raft的安全性规则

Raft保证以下的安全性：

• 选举安全性：每个任期最多只能选出一个领袖。
• 领袖附加性：领袖只会把新指令附加（英语：append）在记录尾端，不会改写或删除已有指令。
• 记录符合性：如果某个指令在两个记录中的任期和指令序号一样，则保证序号较小的指令也完全一样。
• 领袖完整性：如果某个指令在某个任期中存储成功，则保证存在于领袖该任期之后的记录中。
• 状态机安全性：如果某服务器在其状态机上执行了某个指令，其他服务器保证不会在同个状态上执行不同的指令。

前四项保证的原因详见上述算法，状态机安全性则借由下述选举流程的限制所达到。

追随者死机

当某台追随者死机时，所有给它的转发指令和拉票的消息都会因没有回应而失败，此时发送端会持续重送。当这台追随者引导重新加入集群，就会收到这些消息，追随者会重新回应，如果转发的指令已经写入，不会重复写入。

领袖死机

领袖死机或断线时，每个已存储指令必定已经写入到过半的服务器中，此时选举流程会让记录最完整的服务器胜选。其中一个因素是Raft候选人拉票时会揭露自己记录最新一笔的信息，如果服务器自己的记录比较新，就不会投票给候选人。

超时期限和可用性

因为Raft启动选举是基于超时，使得超时期限的选择至为关键。若遵守算法的时限需求

广播时间 << 超时期限 << 平均故障间隔

就能达到稳定性。这三个时间定义如下：

• 广播时间 是单一服务器发送消息给集群中每台服务器并得到回应的平均时间，需要测量得到。
• 超时期限 是发动选举的超时期限，由部署Raft集群的人选定。
• 平均故障间隔 是服务器发生故障之间的平均时间，可以测量或估计得到。

广播时间典型是 0.5ms 到 20ms，平均故障间隔通常是用周或月来计算的，所以可以将超时期限设在 10ms 到 500ms。

• Paxos算法
• 分布式计算

• 官方网站 （英文）