下载掌阅APP，畅读海量书库
立即打开
在了解Raft算法前，先简述Paxos算法。Paxos算法最早于1989年提出，在20世纪八九十年代被广泛讨论。该算法强调一致性，将节点分为Client、Voters、Proposer、Learner和Leader等多种角色，对应于不同的职责权限。从步骤上来说，算法包含Prepare、Promise、Accept和Accepted等多个步骤。通过这些角色和步骤的定义，在节点中反复确认并达成一致性决策。经过理论证明，Paxos是可以满足一致性和分区容错的。谷歌公司曾在分布式数据库Chubby系统中应用Paxos算法，微软公司在搜索引擎Bing的并行计算系统中也尝试运用了Paxos算法。Paxos被诟病的原因是其逻辑过于复杂，难于理解，因此在教学和工程实践中，人们运用Paxos算法的困难较大。
Raft（Reliable、Replicated、Redundant和Fault-Tolerant）是Paxos的一种简化变种，同样追求的是分布式系统中的强一致性。假设节点的总数为 n ，Raft的最大容错节点数量为( n -1)/2。Raft算法主要分为两个基本步骤：Leader的选举以及Log同步。算法将节点分为两类：Leader和Follower。Raft算法中将时间划分为若干个分块（term），在每一个term中Leader不变，分块结束后，发起新的Leader选举。该算法也定义了一些机制以允许Follower在一些情况下发起Leader选举，例如长时间未收到任何请求时。
在每个term中，所有节点在唯一Leader的管理下执行Log同步的过程。当Leader收到来自客户端的新请求时，便将该新请求指令增补到日志中，并向所有节点发送日志刷新消息。日志中的指令按时间顺序排列编号，Log序列中每一个输入都包含其所对应的term编号以及指令本身。Follower收到日志刷新消息后，会向Leader发回响应信息。基于这些响应信息，Leader可以判定某个新的指令是否获得了超过半数的节点响应，如果是，则这条指令被认为成功地同步了。Leader会执行成功同步过的指令，并将执行结果返回到最初发起请求的客户端。由于Leader会持续刷新最新的Log同步信息，其中包含最新成功同步的指令序号，各个Follower可以将其和自己所存的Log序列进行比对，以判断自己是否曾错过了之前的消息指令，从而确保系统中的一致性。