分布式Raft一致性算法

介绍

Raft是一种更为简单方便易于理解的分布式算法，主要解决了分布式中的一致性问题。相比传统的Paxos算法，Raft将大量的计算问题分解成为了一些简单的相对独立的子问题。

一致性算法是分布式系统的基石。在所有一致性算法中，Paxos 算法由莱斯利·兰伯特（Leslie Lamport）于 1990 年提出，是一种基于消息传递的一致性算法，被认为是类似算法中最有效的。

Paxos 算法虽然很有效，但原理较为复杂，截止目前，实现 Paxos 算法的开源软件很少，比较出名的有 Chubby、LibPaxos。此外，Zookeeper 采用的 ZAB（Zookeeper Atomic Broadcast）协议也是基于 Paxos 算法实现的，不过 ZAB 对 Paxos 进行了很多改进与优化，两者的设计目标也存在差异——ZAB 协议主要用于构建一个高可用的分布式数据主备系统，而 Paxos 算法则是用于构建一个分布式的一致性状态机系统。

由于 Paxos 算法过于复杂、实现困难，极大地制约了其应用，而分布式系统领域又亟需一种高效而易于实现的分布式一致性算法，在此背景下，Raft 算法应运而生。

Raft 算法在斯坦福 Diego Ongaro 和 John Ousterhout 于 2013 年发表的《In Search of an Understandable Consensus Algorithm》中提出。相较于 Paxos，Raft 通过逻辑分离使其更容易理解和实现，目前，已经有十多种语言的 Raft 算法实现框架，较为出名的有 etcd、Consul 。

raft算法的基础

raft角色

一个 Raft 集群包含若干节点，Raft 把这些节点分为三种状态：Leader、 Follower、Candidate，每种状态负责的任务也是不一样的。正常情况下，集群中的节点只存在 Leader 与 Follower 两种状态。

Leader（领导者）：负责日志的同步管理，处理来自客户端的请求，与Follower保持heartBeat（心跳）的联系；
Follower（追随者）：响应 Leader 的日志同步请求，响应Candidate的投票请求，以及把客户端请求到Follower的事务转发（重定向）给Leader；
Candidate（候选者）：负责选举投票，集群刚启动或者Leader宕机时，状态为Follower的节点将转为Candidate并发起选举，选举胜出（获得超过半数节点的投票）后，从Candidate转为Leader状态。

上面是三个角色之间的转换关系,大概如下:

Follower—> Candidate : 时间片用完,进入选举

Candidate—>Leader : 获得集群过半的投票

Candidate—>Follower : 发现集群里面已经有Leader了(因为集群在选举出Leader之后,Leader会向集群群发消息),或者进入新的任期

Leader—>Follower : 发现具有更高任期(term)的服务器,辞去领导者的职务

Term任期

Raft 算法将时间划分成为任意不同长度的任期（term）。任期用连续的数字进行表示。每一个任期的开始都是一次选举（election），一个或多个候选人会试图成为领导人。

Raft 算法保证在给定的一个任期最多只有一个领导人(选举安全特性)。

RPC

Raft 算法中服务器节点之间通信使用远程过程调用（RPC），并且基本的一致性算法只需要两种类型的 RPC，为了在服务器之间传输快照增加了第三种 RPC。

RPC有三种：

RequestVote RPC：候选人(Candidate)在选举期间发起。

AppendEntries RPC：领导人(Leader)发起的一种心跳机制，用于复制日志到追随者(Follower)

InstallSnapshot RPC: 领导者使用该RPC来发送快照给太落后的追随者(Follower)

raft 三个子问题

通常，Raft 集群中只有一个 Leader，其它节点都是 Follower。Follower 都是被动的，不会发送任何请求，只是简单地响应来自 Leader 或者 Candidate 的请求。Leader 负责处理所有的客户端请求（如果一个客户端和 Follower 联系，那么 Follower 会把请求重定向给 Leader）。

为简化逻辑和实现，Raft 将一致性问题分解成了三个相对独立的子问题。

选举（Leader Election）：当 Leader 宕机或者集群初创时，一个新的 Leader 需要被选举出来；
日志复制（Log Replication）：Leader 接收来自客户端的请求并将其以日志条目的形式复制到集群中的其它节点，并且强制要求其它节点的日志和自己保持一致；
安全性（Safety）：如果有任何的服务器节点已经应用了一个确定索引(index)的日志条目(entry)到它的状态机中，那么其它服务器节点不能在该索引位置应用一个不同的指令。

raft 五个特性

特性	解释
选举安全特性（Election Safety）	对于一个给定的任期号(term)，至多有一个领导者(Leader)被选举出来
领导者只增加原则（Leader Append-Only）	领导者节点绝对不会删除或者覆盖自己的日志，只会增加日志信息
日志匹配原则（Log Matching）	如果两个日志(log)都有一个索引(index)和任期(term)都相同的日志条目(entry)，那么我们就认为这个日志从头开始到这个索引位置之间的全部日志条目都是相同的
领导人完全特性（Leader Completeness）	如果某个日志条目在某个任期号中已经被提交（给该任期的领导者），那么该日志条目必然出现在更大任期号的所有领导者中
状态机安全特性（State Machine Safety）	如果一个服务器把一个已经给定索引(index)的日志条目应用到状态机中，那么其他任何的服务器在对该状态机应用日志条目时都不能再用这个索引

选举（Leader Election）

一个应用 Raft 协议的集群在刚启动（或 Leader 宕机）时，所有节点的状态都是 Follower，初始 Term（任期）为 0。同时启动选举定时器，每个节点的选举定时器超时时间都在 100~500 毫秒之间且并不一致（避免同时发起选举）。

Follower主动发起选举。步骤如下：

增加节点本地的 current term ，切换到candidate状态
投自己一票
并行给其他节点发送 RequestVote RPCs
等待其他节点的回复

投票者如何决定是否给一个选举请求投票呢，有以下约束：

在任一任期内，单个节点最多只能投一票
候选人知道的信息不能比自己的少
first-come-first-served 先来先得

在这个过程中，根据来自其他节点的消息，可能出现三种情况

收到majority的投票（含自己的一票），则赢得选举，成为leader
被告知别人已当选，那么自行切换到follower
一段时间内没有收到majority投票，则保持candidate状态，重新发出选举

第一种情况，赢得了选举之后，新的leader会立刻给所有节点发消息，广而告之，避免其余节点触发新的选举。

第二种情况，在收到Leader发送的心跳消息后，发现Leader的term不低于自己的term，知道有已经有Leader了，于是转换成follower。

第三种情况,当出现平票的局面,就会在超时后重新举行选举,这种情况降低了系统利用率.为了避免出现这种情况,raft引入了randomized election timeouts来避免平票的情况