分布式与一致性协议之Raft算法(一)

Raft算法

概述

Raft算法属于Multi-Paxos算法，它在兰伯特Multi-Paxos思想的基础上做了一些简化和限制，比如日志必须是连续的，只支持领导者(Leader)、跟随者(Follwer)和候选人(Candidate)3种状态。在理解和算法实现上，Raft算法相对容易许多。
除此之外，Raft算法是现在分布式系统首选的共识算法。绝大多数选用Paxos算法的系统(比如Chubby、Spanner)都是在Raft算法发布前开发的，当时没有其他选择;而全新的系统大多选择了Raft算法(比如Etcd、Consul、CockroachDB)。
掌握了Raft算法，我们就可以得心应手地满足绝大部分场景的容错和一致性需求，比如分布式配置系统、分布式NoSQL存储等，轻松突破系统的单机限制。
如果要用一句话概括Raft算法，我觉得是这样的:从本质上说，Raft算法是通过一切以领导者为准的方式实现一系列值得共识和个节点日志的一致。这句话比较抽象，做个比喻:领导者就是Raft算法中的"霸道总裁",通过霸道的"一切以我为准"的方式。决定了日志中命令的值，也实现了个节点日志的一致。后面会以领导者选举、日志赋值、成员变更为核心，讲解Raft算法的原理。

在正式介绍之前，我们先来看一道思考题。
假设我们有一个由节点A、B、C组成的Raft集群(如图所示)，因为Raft算法是一切以领导者为准，所以如果集群中出现了多个领导者，就会出现不知道谁来做主的问题。在这样一个有多个节点的集群中，在节点故障、分区容错等异常情况下，Raft算法应该如何保证在同一个时间内集群中只有一个领导者呢?
在这里插入图片描述

Raft是如何选举领导者的

既然要选举领导者，要从哪些成员中选举呢？除了领导者，Raft算法还支持哪些成员身份呢？这是需要掌握的最基础的背景知识。

有哪些成员身份

在这里插入图片描述

成员身份，又叫作服务器节点状态。Raft算法支持跟随者、候选人和领导者3种状态。为了方便理解，
我们使用不同的图形表示不同的状态，如图u宋史，在任何时候，每一个服务器节点都处于这3个状态中的其中1个

1.跟随者:相当于普通群众，默默地接收和处理来自领导者的消息，当领导者心跳信息超时的时候，它会主动站出来，推荐自己当候选人
2.候选人:候选人将向其他节点发送请求投票(RequestVote) RPC消息，通知其他节点来投票，如果它赢得了大多数选票，那么它将晋升为领导者
3.领导者:一切以我为准，平常的主要工作包含三部分，处理写请求、管理日志复制和不断发送心跳信息，通知其他节点"我是领导者，你们现在不要发起新的选举，找个新领导者来替代我"
需要注意的是，Raft算法是强领导者模型，集群中只能有一个"霸道总裁"。

选举领导者的过程

那么如何从3个成员中选出领导者呢?
首先，在初始状态下，集群中所有的节点都处于跟随者的状态，如图所示。
在这里插入图片描述

Raft算法实现了随机超时时间的特性。也就是说，每个节点等待领导者节点心跳信息的超时时间间隔是随机的。
通过上图可以看到，集群中没有领导者，而节点A的等待超时时间最小(150ms)，所以它会最先因为没有等到领导者的心跳信息而超时。
这个时候，节点A会增加自己的任期编号，并推荐自己为候选人，先给自己投一张选票，然后先其他阶段发送请求投票RPC消息，请他们选举自己为领导者，如图所示在这里插入图片描述