Raft是一种为了管理日志复制的一致性算法。它提供了和Paxos算法相同的功能和性能,但是它的算法结构和Paxos不同,使得Raft算法更加容易理解并且更容易构建实际的系统。为了提升可理解性,Raft将一致性算法分解成几个关键的模块,例如领导选举,日志复制和安全性。同时它通过实施一个更强的一致性来减少需要考虑的状态和数量。从一个用户研究的结果可以证明,对于学生而言,Raft算法比Paxos算法更容易学。Raft算法还包括了新的机制来允许集群成员的动态改变,让利用重叠的大多数来保证安全性。
Raft算法概述Raft算法是从多副本状态机的角度提出,用于管理多副本状态机的日志复制,它一致性分解为多个子问题:领导选举(Leader election),日志复制(Log replication),安全性(Safety),日志压缩(Log compaction),成员变更(Menbership change)等。同时,Raft算法使用了更强的假设来减少需要考虑的状态,使之变得更加容易理解。
Raft讲系统中的角色分为领导者(Leader),跟从者(Follower)和候选人(Candidate):
Leader: 接收客户端请求,并向Follower同步请求日志。当日志同步到大都数节点上后告告诉Follower提交日志。
Follower:接收并持久化Leader同步的日志,在Leader告诉它的日志提交之后,提交日志。
Candidate:Leader选举过程中的临时角色。
Raft要求系统在任意时刻最多只有一个Leader,正常工作期间Leader和Followers。
Raft算法角色状态转换如下:
跟随者只响应来自其他服务器的请求。如果跟随者接收不到消息,那么它就会变成候选人并发起一次选举。获得集群中大多数选票的候选人将成为领导者。在一个任期内,领导人直到自己宕机了。
Raft算法时间被划分成为一个个的任期(Term),每个任期(Term)开始都是一次Leader选举。选举成功后,领导人会管理整个集群直到任期(Term)结束。有时候会选举失败,那么任期(Term)就会没有领导者,而结束。任期(Term)之间的切换可以在不同的时间不同的服务器上观察到。
Raft算法中服务器之间节点通信使用远程调用(RPCs).而在etcd的实现当中v2版本用的http,而v3版本采用的是grpc(本身是跨平台)。并且基本的一致性算法只是用了两种类型的Rpcs。请求投票(RequestVote)RPCs由候选人发起。然后附加条目数(AppendEntries)由Leader发起。用来复制日志和提供一种心跳机制。为了服务器之间传输快照增加了第三种RPCs。当服务器没有及时收到RPC的响应时,会进行重试,并且它们能够并行发起RPCs来获取最佳性能。
复制状态机一组服务器上的状态机产生相同状态的副本,并且在一些机器宕掉的情况下也可以继续运行。复制状态机在分布式系统中被用于解决很多容错的问题。例如,大规模的系统中通常都有一个集群领导者,像 GFS、HDFS 和 RAMCloud,典型应用就是一个独立的的复制状态机去管理领导选举和存储配置信息并且在领导人宕机的情况下也要存活下来。比如 Chubby 和 ZooKeeper。
复制状态机的结构。一致性算法管理着来自客户端指令的复制日志。状态机从日志中处理相同顺序的相同指令,所以产生的结果也是相同的。
复制状态机通常都是基于复制日志实现的,如图 1。每一个服务器存储一个包含一系列指令的日志,并且按照日志的顺序进行执行。每一个日志都按照相同的顺序包含相同的指令,所以每一个服务器都执行相同的指令序列。因为每个状态机都是确定的,每一次执行操作都产生相同的状态和同样的序列。
保证复制日志相同就是一致性算法的工作了。在一台服务器上,一致性模块接收客户端发送来的指令然后增加到自己的日志中去。它和其他服务器上的一致性模块进行通信来保证每一个服务器上的日志最终都以相同的顺序包含相同的请求,尽管有些服务器会宕机。一旦指令被正确的复制,每一个服务器的状态机按照日志顺序处理他们,然后输出结果被返回给客户端。因此,服务器集群看起来形成一个高可靠的状态机。
实际系统中使用的一致性算法通常含有以下特性: