一个核心问题

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 Data 和 The 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 算法诞生的背景，从而让读者知其然，亦知其所以然。