RAFT 协议简介

2018-04-13 Friday     misc

Paxos 一直是分布式协议的标准,但是 Paxos 难于理解,更难以实现,例如 Google 的分布式锁系统 Chubby 在实现 Paxos 协议时就遇到很多坑。

来自 Stanford 的新的分布式协议研究称为 RAFT,它是一个为真实世界应用建立的协议,主要注重协议的落地性和可理解性。

简介

RAFT 算法在许多方面和现有的一致性算法都很相似,其独有的特性如下:

  • 强领导者,日志只从领导者发送给其它从服务器,简化了对日志复制的管理。
  • 领导选举,在所有一致性算法的心跳机制上增加了一个随机计时器来选举领导者,从而可以更加简单快捷地解决冲突。
  • 日志一致,简单来说就是通过 Term 和 Index 保证所有的日志及其顺序全局唯一,同时不允许存在空洞 (Paxos允许)。
  • 成员变更,使用一种共同一致的方法来处理集群成员变换的问题,在变更过程中集群依然可以继续工作。

复制状态机

一致性算法实际上是基于这一模型的,需要保证复制日志相同,简单来说就是初始状态相同,以相同的顺序处理指令,那么各个节点会产生相同的状态以及状态序列。目前使用比较多的是基于日志的复制方式,这一复制过程也被称为原子广播。

实际系统中使用的一致性算法通常含有以下特性:

  • 安全性 safty,也就是在非拜占庭错误情况下,包括网络延迟、分区、丢包、冗余和乱序等错误都可以保证正确。
  • 可用性 livness,集群中只要多数机器、客户端可以相互通讯,那么集群就是可用的,如果机器异常崩溃,大部分场景可以从持久化中恢复。
  • 非时序依赖,通常不会因为物理时钟、消息延迟导致可用性问题。

拜占庭问题

这一问题实际上是 Lamport 老爷子在 《The Byzantine Generals Problem》中提出的,这实际上是一个虚构的故事,准确来说是研究分布式系统容错性的时候编出的一个故事。

不同的版本可能会略有出入,简单如下。

假设有9位将军投票,其中1名叛徒。8名忠诚的将军中出现了4人投进攻,4人投撤离的情况。这时候叛徒可能故意给4名投进攻的将领送信表示投票进攻,而给4名投撤离的将领送信表示投撤离。这样一来在4名投进攻的将领看来,投票结果是5人投进攻,从而发起进攻;而在4名投撤离的将军看来则是5人投撤离。这样各支军队的一致协同就遭到了破坏。

拜占庭将军问题更像是一个错误模型,简单地说,Byzantine Generals Problem 是针对所谓的 Byzantine Failure 来说的,而 Byzantine Failure 是指分布式系统中的某一恶意节点允许做任意事情去干扰系统的正常运行 (包括选择性不传递消息、选择性伪造消息等),如何保证在这一场景下确保整个系统不会异常。

简单来说,就是在缺少可信的中央节点和可信任的通道的情况下,分布在网络中的各个节点如何达成共识的问题。

Practical Byzantine Fault Tolerance, PBFT

经典的 PBFT 的解决方案是需要所有节点均交换数据,有明显的扩展性问题。

Proof of Work, POW

在出现比特币之前,解决分布式系统一致性问题主要是 PAXOS 及其衍生算法,仅适用于中心化的分布式系统,这样的系统的没有不诚实的节点,也就是不会发送虚假错误消息,但允许出现网络不通或宕机出现的消息延迟。

在区块链的实现中通过 POW 来解决这一问题。

RAFT 算法

算法中的大部分工作是为了消除不确定性,例如不允许日志有空洞。为了方便理解,将算法分成了几个模块,包括了领导选举、日志复制、安全性、成员变更。

日志管理主要是通过 Leader 负责,从客户端接收日志,并将日志复制到其它从服务器上,同时通知其它从服务器什么时候将日志应用到状态机上,通过这一机制大大简化了对复制日志的管理。

Leader 会直接决定日志存放的位置,而不需要和其它服务器进行协商,当 Leader 宕机后,会从其它服务器上重新选举出来。

关于 Term

也就是一个任期,此时的 Leader 不变,每次都会通过发送的消息进行同步更新,如果当前服务器保存的 term 较小,那么就会更新到更大的值。

其中 term 的标识从 1 开始单调递增,而且总是以选举开始,总的时间不定,可能无限长,也可能只有选举时间。而且因为网络的延迟,各个节点看到相同term的时间点不同,极端情况下可能会有丢失某个 term 的情况。

Term 相当于不依赖墙上时钟的逻辑时间,同样可以用来做一些常规的判断,例如判断是否是一个过期的 Leader、如果收到了一个过期的请求则直接丢弃。

如果 Candidate 和 Leader 发现自己的 term 过期,那么会自动切换到 Follower 状态。

参考

常见参考

官方地址 raft.github.io,常见的参考地址有:

  1. Github RAFT 中文翻译,比较不错的中文翻译,仅供参考;
  2. In Search of an Understandable Consensus Algorithm(Extended Version) 简版论文,也可以参考 本地文档
  3. 从理论应用到实践的论文 Raft consensus algorithm,也就是作者的博士毕业论文,本地文档
  4. 关于实现的细节补充可以参考 Four modifications for the Raft consensus algorithm FM-RAFT,以及 本地文档

其它

一些常见一致性算法可以参考 Github Awesome Consensus



如果喜欢这里的文章,而且又不差钱的话,欢迎打赏个早餐 ^_^


About This Blog

Recent Posts

Categories

Related Links

  • RTEMS
    RTEMS
  • GNU
  • Linux Kernel
  • Arduino

Search


This Site was built by Jin Yang, generated with Jekyll, and hosted on GitHub Pages
©2013-2018 – Jin Yang