Raft算法是管理复制日志的一致性算法。
一致性的算法是让分布式系统表现的像单机系统一样,即使系统中有一些机器损坏了,也一样可以正常运行。
Raft设计出来是为了实现工程上的可用,避免Paxos算法的复杂性,从In Search of an Understandable Consensus Algorithm (Extended Version)这篇论文也可以看出,Raft部分原因也是为教学设计。论文很长,并且也已经有中译版,权且把这篇文章当作一篇导读。
在Raft算法中,集群像HDFS一样是主从架构,每一台机器的状态都唯一依赖于日志,而日志只来源于Master节点。日志中包含中一系列的命令,命令都包含着唯一编号,编号只会递增,不会减少或发生变更,而机器会根据命令不断地执行下去,所以只要日志保持一致,每台机器最终都会保证在统一状态。这也就是复制状态机。
Raft算法将一致性问题拆分成了领导选取(leader election)、日志复制(log replication)、安全(safety)和成员变化(membership changes)四个小问题,分别给出了解答。
如上文所述,Raft算法必须要有一个Master节点,那么Master节点必须要有一个选取地过程,以保证Master宕机后,也能在其它节点运行。Raft算法将集群中机器地角色分为了三种:
三者地状态变化如下图:
简单来说,Follower会只会接收请求,当Follower接受不到请求时,会变成一个Candidate发起一次Election,获得绝大数票的Candidate会成为Leader。在Election的过程中会遵循下面几条原则:
Leader把每一条请求作为新的日志条目加入到它的日志中去,然后并行的向其他服务器发起 AppendEntries RPC ,要求其它服务器复制这个条目。当这个条目被安全的复制之后,Leader会将这个条目应用到它的状态机中并且会向客户端返回执行结果。如果Follower发生意外(崩溃、运行缓慢、网络丢包等),领导人会无限的重试 AppendEntries RPC(甚至在它向客户端响应之后)以保证所有的Follower最终存储了所有的日志条目。
日志的结构中不仅包含具体的操作,还包含本次插入的前一个位置的index和Term(任期),从而保证:
简而言之一句话:Leader负责一致性检查,同时让所有的Follower都和自己保持一致。
有了上面所述,继而引发安全问题,如何保证日志是可靠的:
安全性第一条限制 Candidate在拉票时需要携带自己本地已经持久化的最新的日志信息,等待投票的节点如果发现自己本地的日志信息比竞选的Candidate更新,则拒绝给他投票。
安全性第二条限制 只允许Leader提交(commit)当前Term的日志。
Raft将节点的增删抽象成配置的变更,当Leader收到配置变更的消息之后,它就将新的配置Cnew作为一个特殊的Raft Entry发送到其他的Follower上面,任何节点只要收到了这个Entry,就开始直接使用Cnew。当Cnew这个Log被 committed,那么这次配置变更就结束了。 值得注意的是:
为了避免日志一直不断地增长,Raft使用了Snapshot机制,Snapshot之前地日志都可以丢弃。 Raft算法为了解决Snapshot地性能问题,给出了三个解决方案:
这篇导读简单地概括了Raft算法,但是在Raft论文中更加详细地提到了性能优化、Raft正确性证明和选举地详细过程,甚至给出伪代码等等,同时TiDB、MongoDB等分布式数据库都采用了Raft算法,并且在此之上做了大量地优化,同样Raft算法也拥有了大量地开源实现库,具体地可以参考官网继续学习。
https://raft.github.io/raft.pdf http://www.infoq.com/cn/articles/raft-paper https://www.jianshu.com/p/138b4d267084 https://www.jianshu.com/p/99562bfec5c2 https://zhuanlan.zhihu.com/p/27910576