Raft，分布式共识算法，是工程上使用较为广泛的强一致性、去中心化、高可用的分布式协议。如redis-sentinel，etcd等都使用Raft协议解决分布式一致性的问题。

Nacos注册中心是阿里巴巴贡献的开源项目，兼具服务注册发现、动态配置管理、动态DNS等功能。nacos集群使用了raft协议，来解决分布式一致性问题。

一、Raft算法概述

Raft算法由leader节点来处理一致性问题。leader节点接收来自客户端的请求日志数据，然后同步到集群中其它节点进行复制，当日志已经同步到超过半数以上节点的时候，leader节点再通知集群中其它节点哪些日志已经被复制成功，可以提交到raft状态机中执行。

通过以上方式，Raft算法将要解决的一致性问题分为了以下几个子问题。

• leader选举：集群中必须存在一个leader节点。
• 日志复制：leader节点接收来自客户端的请求，然后将这些请求序列化成日志数据再同步到集群中其它节点。
• 安全性：如果某个节点已经将一条提交过的数据输入raft状态机执行了，那么其它节点不可能再将相同索引的另一条日志数据输入到raft状态机中执行。

Raft节点有三种状态，follower、candidate、leader。

• Leader：领导者，一个集群里只能存在一个Leader。
• Follower：跟随者，Follower是被动的，一个客户端的修改数据请求如果发送到Follower上面时，会首先由Follower重定向到Leader上。
• Candidate：参与者，一个节点切换到这个状态时，将开始进行一次新的选举。

各状态之间的转化如下图：

上图中标记了状态切换的6种路径，下面做一个简单介绍。

• start up：起始状态，节点刚启动的时候自动进入的是follower状态。
• times out, starts election：follower在启动之后，将开启一个选举超时的定时器，当这个定时器到期时，将切换到candidate状态发起选举。
• times out, new election：进入candidate 状态之后就开始进行选举，但是如果在下一次选举超时到来之前，都还没有选出一个新的leader，那么还会保持在candidate状态重新开始一次新的选举。
• receives votes from majority of servers：当candidate状态的节点，收到了超过半数的节点选票，那么将切换状态成为新的leader。
• discovers current leader or new term：candidate状态的节点，如果收到了来自leader的消息，或者更高任期号的消息，都表示已经有leader了，将切换回到follower状态。
• discovers server with higher term：leader状态下如果收到来自更高任期号的消息，将切换到follower状态。这种情况大多数发生在有网络分区的状态下。

关于Raft协议，首先，可以看一下动画，初步认识一下这个分布式公式算法的具体步骤。

http://thesecretlivesofdata.com/raft/

整个过程大致分为 Leader选举（Leader Election ）、日志复制（Log Replication） 两步。

二、Leader选举（Leader Election）

Raft算法是使用心跳机制来触发leader选举的。

①所有节点一开始都是follower状态，一定时间未收到leader的心跳，则进入candidate状态，参与选举；

②选出leader后，leader通过向follower发送心跳来表明存活状态，若leader故障，则整体退回到 ①中的状态；

③每次选举完成后，会产生一个term，term本身是递增的，充当了逻辑时钟的作用；

具体的选举过程：

等待heartbeat，若超时未等到，准备选举---->新增当前任期号（term），转变为candidate状态---->给自己投票，然后给其他节点发送投票请求---->等待选举结果。

每一次开始一次新的选举时，称为一个“任期”。每个任期都有一个对应的整数与之关联，称为“任期号”，任期号用单词“Term”表示，这个值是一个严格递增的整数值。

Raft节点之间通过RPC请求来互相通信，主要有以下两类RPC请求。RequestVote RPC用于candidate状态的节点进行选举之用，而AppendEntries RPC由leader节点向其他节点复制日志数据以及同步心跳数据的。

具体投票过程有三个约束：

（1）在同一任期内，单个节点最多只能投一票；

（2）候选人知道的信息不能比自己的少(Log与term)；

（3）first-come-first-served 先来先得。

选举的三种情况：

第一种情况，赢得选举之后，leader会给所有节点发送消息，避免其他节点触发新的选举

第二种情况，比如有三个节点A B C。A B同时发起选举，而A的选举消息先到达C，C给A投了一票，当B的消息到达C时，已经不能满足上面提到的第一个约束，即C不会给B投票，而A和B显然都不会给对方投票。A胜出之后，会给B,C发心跳消息，节点B发现节点A的term不低于自己的term，知道有已经有Leader了，于是转换成follower

第三种情况， 没有任何节点获得majority投票，可能是平票的情况。加入总共有四个节点（A/B/C/D），Node C、Node D同时成为了candidate，但Node A投了Node D一票，NodeB投了Node C一票，这就出现了平票 split vote的情况。这个时候大家都在等啊等，直到超时后重新发起选举。如果出现平票的情况，那么就延长了系统不可用的时间,因此raft引入了randomized election timeouts来尽量避免平票情况

数据的处理：

对于事务操作，请求会转发给leader；

非事务操作上，可以任意一个节点来处理；

三、日志复制（Log Replication）

日志复制的流程大体如下：

• 每个客户端的请求都会被重定向发送给leader，这些请求最后都会被输入到raft算法状态机中去执行。
• leader在收到这些请求之后，会首先在自己的日志中添加一条新的日志条目。
• 在本地添加完日志之后，leader将向集群中其他节点发送AppendEntries RPC请求同步这个日志条目，当这个日志条目被成功复制之后，leader节点将会将这条日志输入到raft状态机中，然后应答客户端。

Raft日志的组织形式如下图所示：

每个日志条目包含以下成员：

1. index：日志索引号，即图中最上方的数字，是严格递增的。

2. term：日志任期号，就是在每个日志条目中上方的数字，表示这条日志在哪个任期生成的。

3. command：日志条目中对数据进行修改的操作。

一条日志如果被leader同步到集群中超过半数的节点，那么被称为“成功复制”，这个日志条目就是“已被提交（committed）”。如果一条日志已被提交，那么在这条日志之前的所有日志条目也是被提交的，包括之前其他任期内的leader提交的日志。如上图中索引为7的日志条目之前的所有日志都是已被提交的日志。

四、为什么 Raft 通常推荐使用奇数节点而不是偶数节点？

Raft 一般会使用奇数个节点，比如 3，5，7 等等。这是因为 raft 是 一种基于多节点投票选举机制的共识算法，通俗地说，只有超过半数节点在线才能提供服务。这里超过半数的意思是N/2+1（而不是N/2），举例来说，3 节点集群需要 2 个以上节点在线，5 节点集群需要 3 个以上节点在线，等等。对于偶数节点的集群，2 节点集群需要 2 节点同时在线，4 节点集群需要 3 节点在线，以此类推。实际上不只是 Raft，所有基于 Quorum 的共识算法大体上都是这么个情况，例如 Paxos，Zookeeper 什么的，本文仅以 Raft 为例讨论。

共识算法要解决的核心问题是什么呢？

是分布式系统中单个节点的不可靠造成的不可用或者数据丢失。Raft 保存数据冗余副本来解决这两个问题，当少数节点发生故障时，剩余的节点会自动重新进行 leader 选举（如果需要）并继续提供服务，而且 log replication 流程也保证了剩下的节点（构成 Quorum，法定人数）总是包含了故障前成功写入的最新数据，因此也不会发生数据丢失。

我们对比一下 3 节点的集群和 4 节点的集群，Quorum 分别是 2 和 3，它们能容忍的故障节点数都是 1。如果深究的话，从概率上来说 4 节点集群发生 2 节点同时故障的可能性要更高一些。于是我们发现，相对于 3 节点集群，4 节点集群消耗更多的硬件资源，却换来了更差的可用性，显然不是个好选择。

五、Nacos Naming服务一致性实现

Naming服务支持两种类型的数据存储：临时和永久数据。永久数据一旦创建之后会一直存在，除非显式删除；临时数据创建之后和所有者的生命周期绑定，需要创建者不断发送心跳信息来保证数据的有效性。

1. RaftConsistencyServiceImpl类

RaftConsistencyServiceImpl类提供的是基于Raft协议的永久数据存储方案。nacos naming服务内部实现了一个简化的Raft协议。每个节点通过本地文件系统保存所有数据，通过Raft协议选择Leader并同步数据。Raft协议通过保证数据在各naming节点的一致性来保证naming服务的高可用。

2. DistroConsistencyServiceImpl类

DistroConsistencyServiceImpl用于存储临时数据。由于nacos的临时数据需要通过创建者不断得发送心跳数据来保活，因此在存储上反而比较简单。naming服务并不会在文件系统或者数据库中持久化存储临时数据，它通过心跳包来保证数据的有效性。

naming服务使用一种“分区”算法来管理临时数据。它把所有数据分为若干个block，每个naming节点只负责一个block内数据的创建/删除/同步。通过数据同步，每个naming节点最终都会持有完整的数据集合。