根据 Raft 中文翻译和各种来源,按照自己更好理解的方式进行重新组织和增加一些说明 [TOC] TL;DR 根据作者的话来说,Raft 算法是为了 寻找一种易于理解的一致性算法,作为管理复制日志的一致性算法,提供了和 Paxos 算法相同的功能和性能。(顺带吐槽 Paxos 难以理解) Raft 算法为了能够更佳方便理解,采用两种通常适用的技术: Raft 算法被分成领导人选举,日志复制,安全性和角色改变几个部分 通过减少状态的数量来简化需要考虑的状态空间,使得系统更加连贯并且在可能的时候消除不确定性 1. 复制状态机 一致性算法是从复制状态机的背景下提出的。一组服务器上的状态机产生相同状态的副本,并且在一些机器宕掉的情况下也可以继续运行。复制状态机在分布式系统中被用于解决很多容错的问题 大规模的系统中通常都有一个集群领导者,像 GFS、HDFS 和 RAMCloud,典型应用就是一个独立的的复制状态机去管理领导选举和存储配置信息并且在领导人宕机的情况下也要存活下来。比如 Chubby 和 ZooKeeper。 图 1 :复制状态机的结构。一致性算法管理着来自客户端指令的复制日志。状态机从日志中处理相同顺序的相同指令,所以产生的结果也是相同的 复制状态机通常都是基于复制日志实现的,如图 1。每一个服务器存储一个包含一系列指令的日志,并且按照日志的顺序进行执行。每一个日志都按照相同的顺序包含相同的指令,所以每一个服务器都执行相同的指令序列。因为每个状态机都是确定的,每一次执行操作都产生相同的状态和同样的序列 保证复制日志相同就是一致性算法的工作了。在一台服务器上,一致性模块接收客户端发送来的指令然后增加到自己的日志中去。它和其他服务器上的一致性模块进行通信来保证每一个服务器上的日志最终都以相同的顺序包含相同的请求,尽管有些服务器会宕机。一旦指令被正确的复制,每一个服务器的状态机按照日志顺序处理他们,然后输出结果被返回给客户端。因此,服务器集群看起来形成一个高可靠的状态机 实际系统中使用的一致性算法通常含有以下特性: 安全性保证(绝对不会返回一个错误的结果):在非拜占庭错误情况下,包括网络延迟、分区、丢包、冗余和乱序等错误都可以保证正确。 可用性:集群中只要有大多数的机器可运行并且能够相互通信、和客户端通信,就可以保证可用。因此,一个典型的包含 5 个节点的集群可以容忍两个节点的失败。服务器被停止就认为是失败。他们当有稳定的存储的时候可以从状态中恢复回来并重新加入集群。 不依赖时序来保证一致性:物理时钟错误或者极端的消息延迟只有在最坏情况下才会导致可用性问题。 通常情况下,一条指令可以尽可能快的在集群中大多数节点响应一轮远程过程调用时完成。小部分比较慢的节点不会影响系统整体的性能 2. Raft 一致性算法 Raft 算法将系统中的角色限定为: 领导者(Leader)、跟从者(Follower)和候选人(Candidate) Raft 通过选举一个领导者,然后给予他全部的管理复制日志的责任来实现一致性。领导人从客户端接收日志条目,把日志条目复制到其他服务器上,并且当保证安全性的时候告诉其他的服务器应用日志条目到他们的状态机中。拥有一个领导人大大简化了对复制日志的管理。 领导人可以决定新的日志条目需要放在日志中的什么位置而不需要和其他服务器商议,并且数据都从领导人流向其他服务器 一个领导人可以宕机,可以和其他服务器失去连接,这时一个新的领导人会被选举出来 Raft 算法通过领导人的方式,将一致性问题分解成了三个相对独立的子问题: 领导选举(Leader election):一个新的领导人需要被选举出来,当现存的领导人宕机的时候 日志复制(Log replication):领导人必须从客户端接收日志然后复制到集群中的其他节点,并且强制要求其他节点的日志保持和自己相同。 安全性(Safety):在 Raft 中安全性的关键是状态机安全:如果有任何的服务器节点已经应用了一个确定的日志条目到它的状态机中,那么其他服务器节点不能在同一个日志索引位置应用一个不同的指令。 为了一些可用性问题,额外考虑了:……

阅读全文