Raft 算法的前世今生

一个核心问题

Raft 算法想解决的核心问题是分布式共识问题,什么是分布式共识问题呢 ?简而言之:分布式环境下系统集群存在很多节点,每个节点都可提出议案,我们需要:

  • 对多个节点提出的议案作裁决并得到一个一致的结论,然后让每个节点都感知到该结论,从而使集群状态一致

  • 允许一部分节点宕机后仍可正常工作,先前通过的议案仍可访问,集群状态保持一致

在 Raft 算法之前

在 Raft 算法提出之前,学术界早就已经有了 Paxos 算法 来解决分布式共识问题。Paxos 算法由 Leslie Lamport 于 1990 年提出。Lamport 在叙述 Paxos 算法时采用了一种非常奇特的方式:讲故事。Lamport 虚拟了一个叫 Paxos 的希腊城邦,这个岛按照议会民主制的政治模式来制定法律,其中有议员,议长和传纸条的服务员等几类角色。通过这种拟人化的角色和场景,Lamport 概述了议案制定的过程,即 Paxos 算法。论文投稿时,审稿人觉得这个算法很有趣但不是很重要(可能受限于当时计算机发展水平,分布式共识算法应用场景有限),Lamport 当时就觉得这些人毫无幽默感。时隔多年后,Lamport 的朋友因构建分布式系统的需要,正在寻找一种共识算法,于是发现了 Paxos 算法的重要性。当越来越多的人意识到 Paxos 算法的重要性后,Lamport 在 1998 年重新发表了之前的那篇论文 并一举受到重视。Lamport 后面发现还是很多人觉得 Paxos 算法难以理解,于是又将之前的论文做了简化并发表出来

到了 2006 年,Google 在两篇经典论文 Bigtable:A Distributed Storage System for Structured DataThe Chubby lock service for loosely-coupled distributed systems 中提及用 Paxos 算法实现了一个分布式锁服务 Chubby,于是 Paxos 算法开始进入工业界领域被广大技术人员熟知。

在分布式共识算法领域,Paxos 算法可以说是宗师级角色,统治该领域十余年,大多数共识算法都是在其基础上进行改进和优化,Raft 算法也不例外。正因如此,Chubby 的作者 Mike Burrows 曾说过(据说是他说的):只有一种分布式共识算法,那就是 Paxos,其他共识算法都只是 Paxos 算法的不完整版(大意)。

Paxos 算法的问题

Raft 算法的作者 Diego Ongaro 在研究 Paxos 算法时,深受其复杂性困扰。他觉得 Paxos 算法是一门极其难懂的算法,其工程化实践更是困难重重,原始的 Paxos 算法不经过一番修改是很难应用于工程之中,而修改后的 Paxos 算法又很难保证其正确性。他总结出 Paxos 算法有两个大问题:

  • 非常难于理解

    完整的 Paxos 算法很难让人建立起理解的直觉。Diego Ongaro 发现就算是经验丰富的专家,在理解 Paxos 算法的道路上也费了不少劲。而他也是直到读了一些 Paxos 算法的简化解释和开始开发自己的一致性算法时,才算真的掌握了 Paxos 算法,这过程花了足足一年。

  • 没有给工程实现提供一个好的基础

    目前还没有一个广泛被使用和认可的 multi-Paxos 算法。Lamport 的算法描述只提供了一个素描式的框架,其中隐去了很多细节。这导致很多对 multi-Paxos 的实现最终都是一个未被证明的协议。Paxos 算法形式化的描述对证明其正确性很有用,但在工程实现上则价值不大。

    Paxos 算法的内核采用的是对称的 peer-to-peer 方式,这是对真实世界决议的简化描述,但实际应用中很少采用。如果要在一组决议中达成一致,最简单也最快的方式就是选出一个 leader,由 leader 来协调决议。

    Paxos 算法自首次正式提出以来已经十多年时间了,开源社区几乎没有一个被广泛认可的算法实现,很多 Paxos 算法的实现都是对其完整版的近似。

正因如此,Diego Ongaro 打算自己开发一门新的共识算法,一门能够为教学和工程实践提供良好基础,并能等价于 Paxos 算法的共识算法。于是,他决定把 Understandability 作为这门算法的首要设计原则。这门新的共识算法就是 Raft 算法。

Raft 算法的设计

Diego Ongaro 为了让 Raft 算法清晰易懂,采用了两种方式:

  • 分解为子问题

    Raft 算法将其整体划分成了几个子问题,每个子问题都可以独立解释。这样一来,理解 Raft 算法只需要相对独立地理解几个子问题即可。比如,Raft 算法被划分成了以下几个子问题:

    • Leader election:描述如何从集群的几个节点中选举出 Leader;

    • Log Replication:描述如何将日志同步到各个节点从而达成一致;

    • Safety:定义了一组约束条件来保证 Raft 算法的强一致性;

    • Membership changes:描述如何变更集群关系(增加或者减少节点);

  • 简化状态空间

    状态太多就会增加理解的困难程度。Raft 算法尽可能地确定各个环节的状态。典型地,Raft 算法采用 strong leader 的模型,每个日志的读写均由 Leader 从中主动协调,这样一来,整体系统的数据流将非常简单:从 Leader 流行 Follower。而且每个节点的状态也只有 3 种:Leader,Candidate 和 Follower。

通过上述两种技术手段的采用,Raft 算法成功地做到了 Understandability。作者在大学中同时教授 Raft 和 Paxos 算法并让学生完成相应的测试,结果 Raft 算法的学习效果要明显好于 Paxos 算法。

Raft 算法的命名

Raft 算法为什么取名为 Raft 呢 ?关于这个问题,Diego Ongaro 曾在 Google Groups 的 raft-dev 频道这么说到

我们选择取名为 Raft 是因为下面几个原因:

  • Raft 不是某几个单词首字母的缩写,但是我们想到了这么几个词:reliable(可靠的),replicated(可复制的),redundant(冗余的)和 fault-toleran (容错的);

  • 我们想到了 logs(算法中意为 “日志”,英文还有一个意思是 “原木”),我们将 “日志”(原木) 组合起来构建起了整套算法;

  • 我们把 Paxos 想象成了一个岛,并谋划着怎么逃离这个岛;

他们曾经想了很多名字,至于最后为什么以 Raft(英文为 “筏” 的意思)作为正式的名字,细节他们也记不清了。我猜他们应该是困在 Paxos 这个孤岛上太久,好不容易收集齐了木头,扎了木筏(raft),准备扬帆起航。

Raft 算法的风靡

可能很多人不太理解为什么 Diego Ongaro 要把 Understandability 作为算法设计的首要目的,我觉得这恰恰是这门算法独到和成功之处。在原本晦涩难懂的 Paxos 算法的基础上,重新设计一门清晰易懂的共识算法并非一件易事。其实,算法的易懂性带来了以下几个好处:

  • 工程实现的简单

    一个能力不错的工程师在充分理解了 Raft 算法后,都可以相对容易地用他擅长的编程语言快速实现算法的原型出来。时至今日,几乎每种主流编程语言都对 Raft 算法有一个实现版本,可看看这个列表

  • 社区传播性广

    每个人都能搞懂的东西总比复杂难懂的东西流传要广,这是毋庸置疑的。虽然 Raft 算法是 Diego Ongaro 在斯坦福大学的博士论文,但是其精简版(就是篇幅较短的那篇)并非曲高和寡。读者只要具备基本的计算机算法基础,花个几天时间(甚至更短),基本可以弄明白 Raft 算法的基本过程。懂的人多了,自然就形成了社区,社区越活越,为算法添砖加瓦的人就越多。

  • 易于应用和验证

    没有人敢把自己不理解的东西应用于生产环境中。正因 Raft 算法的清晰易懂,越来越多的开源项目尝试引入 Raft 算法来解决分布式一致性问题。特别地,在分布式存储领域,基于 Raft 算法构建的项目百花齐放,欣欣向荣。

总结

Raft 算法的流行和成功恐怕也是 Diego Ongaro 始料未及的。我认为,Raft 算法是值得每个工程师研究和细细品味的优秀算法。本篇文章花了不少篇幅叙述 Raft 算法的由来,目的是想让读者了解 Raft 算法诞生的背景,从而让读者知其然,亦知其所以然。