Raft 实现指北-开篇

Raft 是一种解决分布式共识问题的算法。何为分布式共识问题?在此之前,还得说说分布式系统中的基础模型。基础模型是对分布式算法的一个定性的评估(分类)标准,它说明了算法的作用范围,可解决什么问题。

基础模型

基础模型也可以称为算法的属性,这里主要关心两个部分:定时模型(Timing Model)、失效模式(Failure Model)、失效检测器(Failure Detectors)[1]。

定时模型是研究分布式系统的网络传输时延特性,分布式系统通过消息传递来进行通信,根据消息在网络中传递时间是否有上界,可以将消息系统分类为:同步模型(Synchronous Model)异步模型(Asynchronous Model)[2]。在同步模型中,消息传递时间是已知的,每个进程的速度也是确定的,即每个进程执行一个算法步骤耗时是确定的。在异步模型中,每个组件自行决定算法步骤的执行顺序,每一步的耗时也没有保证[1]。注意,这里的同步异步要与编程中出现的同步异步加以区分。

失效模式是对分布式系统中节点失效种类的假设。最基础的是崩溃-结束(crash-stop)失效模式,节点一直正常运行,直至崩溃,节点崩溃后不会恢复。相较于崩溃-结束失效模式,另一种崩溃-恢复(crash-recovery)失效模式更为常见,即节点崩溃后,会被恢复。值得一提的是崩溃-恢复模式中,一个节点恢复时,并不等同于没崩溃的原始节点(比如 Raft 算法动态调整系群组关系,某个节点被另一个新加入节点顶替)。一种更复杂的失效模式叫做拜占庭失效模式或者任意失效模式(Byzantine or arbitrary failures mode):进程有可能向同伴发送错误的信息;进程可能是冒充的;应答给其他进程的数据是正确的,但是篡改了本地数据库的内容,等等[2]。设计分布式系统时,失效模式必须考虑进去,通常来说,我们并不需要考虑拜占庭失效模式。

上述两种属性能够描述分布式系统所处的问题,另外还有部分属性用于对系统工作方式进行分类,失效检测器便是这样的一种属性。失效检测器是对报告系统状态的抽象,即检测节点是否已经崩溃(或者怀疑是否崩溃)。失效检测器是在异步系统中解决共识问题的关键。在著名的FLP论文中指出,在异步的分布式系统中,如果进程有可能失效,那么就不可能达成共识。要达成共识,就必须为系统引入一个能够规避上述问题的失效检测器[1]。

分布式共识问题

分布式共识问题,简单说,就是在一个或多个进程提议了一个值应当是什么后,使系统中所有进程对这个值达成一致意见。为了达到共识,每个进程都提出自己的提议(propose),最终通过共识算法,所有正确运行的进程决定(decide)相同的值[2]。

在同步、可靠的系统中,想要多个节点达成一致比较容易。实际的分布式场景多为异步模型,FLP不可能性说明:没有任何算法可以在存在任何故障的异步系统中确保达到共识,绕过不可能性结论的办法是考虑部分同步系统,利用故障屏蔽、故障检测器或随机化手段避开异步系统模型[2]。

分布式问题最常见的应用场景是多副本状态机(Replicated state machine)。多副本状态机是指多台机器具有完全相同的状态,并且运行有完全相同的确定性状态机[2]。多副本状态机主要用于解决分布式系统中的容错问题,因为副本冗余了状态机,只要保证大多数副本存活且一致,就能向外部提供服务。多副本状态机的实现思想:状态机的每个副本上都保存有完全相同的操作日志,保证所有副本状态机按照相同的顺序执行操作,这样由于状态机是确定性的,则一定会得到相同的状态[2]。具体的实现方式主要分为两种[3]:

  • 日志复制:由 primary 机接受操作日志,并广播给 backup 机,backup 机需要跟 primary 机的操作日志保持一致;
  • 状态重演:操作日志由多个副本共享,每个副本通过重新执行操作日志从放状态;

Raft 算法

有三种非常具有代表性的分布式共识算法:分别是 Viewstamped Replication 、Raft 和大名鼎鼎的 Paxos 算法,前两个工作本身就是基于多副本状态机的场景完成的,而 Paxos 算法是作为独立的分布式共识算法提出,并给出了使用该算法实现多副本状态机的范例[2]。

Raft 是一种为了管理复制日志的一致性算法。它提供了和 Paxos 算法相同的功能和性能,但是它的算法结构和 Paxos 不同,使得 Raft 算法更加容易理解并且更容易构建实际的系统。为了提升可理解性,Raft 将一致性算法分解成了几个关键模块,例如领导人选举、日志复制和安全性。同时它通过实施一个更强的一致性来减少需要考虑的状态的数量。从一个用户研究的结果可以证明,对于学生而言,Raft 算法比 Paxos 算法更加容易学习。Raft 算法还包括一个新的机制来允许集群成员的动态改变,它利用重叠的大多数来保证安全性[4]。

与其他共识算法相比,Raft 算法有三个特点[4]:

  • 强领导者:和其他一致性算法相比,Raft 使用一种更强的领导能力形式。比如,日志条目只从领导者发送给其他的服务器。这种方式简化了对复制日志的管理并且使得 Raft 算法更加易于理解。
  • 领导选举:Raft 算法使用一个随机计时器来选举领导者。这种方式只是在任何一致性算法都必须实现的心跳机制上增加了一点机制。在解决冲突的时候会更加简单快捷。
  • 成员关系调整:Raft 使用一种共同一致的方法来处理集群成员变换的问题,在这种方法下,处于调整过程中的两种不同的配置集群中大多数机器会有重叠,这就使得集群在成员变换的时候依然可以继续工作。

虽然这篇文章标题有“Raft 实现”关键字,但并不会讲 Raft 算法的原理,这只是 Raft 的功能实现介绍,所以我建议在继续阅读之前,先学习一下 Raft 算法:寻找一种易于理解的一致性算法(扩展版)

挖坑

一个基础的 Raft 功能只需要实现选举和日志复制,但这远远不够。想要应用到实际的工程中,还需要实现日至压缩、成员关系调整,才算完整的 Raft 实现。这里给出个 Raft 功能清单,实际上也是本系列文章希望实现的功能:

  • leader election
  • prevote
  • log replication
  • log compaction & snapshot
  • linearizable read(read index & lease)
  • membership change
  • leadership transfer

拥有上述功能可以算上一个工业级的 Raft 实现,不过在实际应用中,还会有许多工业上的优化技巧比如 Batch 和 Pipeline,具体有哪些可以优化的,放到以后的章节详述。

这是我在学习 Raft 算法,并以之为基础实现分布式系统过程中的学习总结。在接下来的几篇文章中,将按照上述清单依次谈谈对应的实现方法和优化原理。实现方法参考优秀的开源实现:etcd/raft 以及其各语言移植版本。

Reference

  1. WHAT WE TALK ABOUT WHEN WE TALK ABOUT DISTRIBUTED SYSTEMS
  2. 分布式共识(Consensus):Viewstamped Replication、Raft以及Paxos
  3. The design of a practical system for Fault-Tolerant Virtual Machines
  4. 寻找一种易于理解的一致性算法(扩展版)
  5. 分布式系统编程,你到哪一级了?
Hiển thị bình luận từ Gitment