Raft是一种常见的分布式共识算法，分布式场景下多个参与方之间需要对某一件事情达成共识，最常见的应用就是数据达成一致性。

分布式共识算法有bully,raft,zab,paxos等等，分布式共识算法在区块链中也有广泛应用。今天要介绍的就是大名鼎鼎的Raft算法。Raft算法是k8s中etcd组件所采用的一致性算法。协议本质上继承了Paxos算法，核心思想是“少数服从多数”。

Raft介绍

Raft提供了一种在计算系统集群中分布状态机的通用方法，确保集群中的每个节点都同意一系列相同的状态转换。它有许多开源参考实现，具有Go，C++，Java和 Scala中的完整规范完整规范实现。

一个Raft集群包含若干个服务器节点，通常是5个，这允许整个系统容忍2个节点的失效，每个节点处于以下三种状态之ー。

角色/状态： 

• follower（跟随者）：所有节点都以 follower 的状态开始。如果没收到 leader 消息则会变成 candidate 状态；
• candidate（候选人）：会向其他节点“拉选票”，如果得到大部分的票则成为 leader ，这个过程就叫做 Leader选举( Leader Election)；
• leader（领导者）：所有对系统的修改都会先经过 leader（这跟主从架构不一样，可能是主先收到数据，也可能是从先收到数据）。

两种timeout：

• election timeout：随机150-300ms等待Leader的消息，避免冲突，未收到消息则转变为后候选人；
• heartbeat timeout：；

Raft一致性算法

Raft通过选出一个 leader来简化日志副本的管理，例如，日志项( log entry)只允许从 leader 流向 followers

Raft算法可以分解成三个子问题：

• Leader election（领导选举）：原来的 leader 挂掉后，必须选出一个新的 leader（heartbeat的timeout）；
• Log replication（日志复制）：leader 从客户端接收日志，并复制到整个集群中心；
• Safety（安全性）：如果有任意的 server 将日志项回放到状态机中了，那么其他的 server只会回放相同的日志项。

Raft动画演示

地址：http://thesecretlivesofdata.com/raft/

动画主要包含三部分：

第一部分介绍简单版的领导者选举和日志复制的过程；

第二部分介绍讦细版的领导者选举和日志复制的过程；

第三部分介绍如果遇到网络分区（脑裂），raft算法是如何恢复网络一致的。

Raft选举流程

每个节点随机等待时间，未在timeout内收到Leader消息则变为候选人，开始新的任期（term）并给自己投票。发送Request Vote给其他节点。如果节点收到消息时未在该Term内投过票，则重置ellection timeout并发送Vote。得到绝大多数票的候选人称为Leader。

心跳包保活，未保活则会重新选举。

Raft日志复制

Leader收到Client的数据，将“指令+数据”通过条目的方式写入log。log不会被直接提交到数据库，而是复制（append entry）给 followers，跟随着一样作为条目写入log并返回消息（Appended entry）。接着Leader提交数据，然后通知 followers 提交数据。此时集群倒成了数据一致性。

最后Leader返回消息给client。

Raft分区解决

5个节点发生网络分区会各自重新选举，然后2个节点或者更少节点的集群无法完成选举或者是老Leader无法得到大多数节点的Appended Entries消息，则会无法提交数据，也就没有办法返回消息给client。当网络分区消失时，则会进入log回滚和一致性过程，未提交的数据会被回滚，同步为已经提交的版本（老Leader发现另外一个集群的Term更新，因此选择后者）。

开源项目

开源项目可以参考百度的braft（C++）或者蚂蚁的SOFAJRaft算法库（Java）。