The binary search of distributed programming

2016-02-14

分布式编程的二分查找

原文由 Salvatore Sanfilippo 于 2016-02-14 发布，订阅该博客

昨晚我在重读 Martin Kleppmann 写的 Redlock 分析（http://martin.kleppmann.com/2016/02/08/how-to-do-distributed-locking.html）。文中 Martin 提到，是否有一种好的方法可以用 Redis 来生成单调递增的 ID。

这个看似简单的问题，细看之下可能比初看时更复杂，因为它必须在所有情况下都保证一个安全性：生成的 ID 必须始终大于之前生成过的所有 ID，且同一个 ID 不能被多次生成。即使在发生网络分区和其他故障时，这一性质也必须成立。如果无法联系到多数节点，系统可以暂时不可用，但绝不能返回错误的结果（注意：正如后文会看到的，该算法在请求负载很高时还存在另一个活性问题）。

所以，为了多玩一下分布式系统算法，顺便在过程中多学一点东西，我试着去寻找一个解决方案。其实我已经知道有一种算法可以解决这个问题。它效率不高，不适合每秒生成大量 ID。许多复杂的分布式算法，比如 Raft 和 Paxos，都会把它作为其中一步，用来获得单调递增的 ID，并以此为基础来构建它们需要提供的全套特性。这个算法非常迷人，因为它极易理解和实现，而且能让人非常直观地明白为什么它是正确的。可以说，它就是分布式算法中的二分查找——足够简单，又足够巧妙，能让分布式编程的初学者产生恍然大悟的瞬间。

不过我不得不修改这个算法，以便让它能够在客户端实现。希望它仍然是正确的（欢迎指正）。虽然我并不打算用这个算法来改进 Redlock（见我之前的博文），但我认为尝试解决这类问题既是一次很好的练习，对于初次接触分布式系统、想在真实系统里找些简单问题练手的人来说，也可能是一篇有趣的读物。

它是如何工作的？

该算法的要求有以下两点：

支持 set_if_less_than() 操作的数据存储。
能够在写入时先将数据 fsync() 到磁盘，再向客户端回复的数据存储。

以上条件几乎涵盖了所有 *SQL 数据库、Redis 以及许多其他存储系统。

我们有一组 N 个节点，为了解释方便，假设 N = 5。我们通过将一个名为“current”的键设为 0 来初始化系统，用 Redis 的话来说，就是执行：

SET current 0

这需要在全部 5 个实例上都执行。这是初始化的一部分，只在初始化一个新的“集群”时才需要做。这一步可以跳过，但会让后续的解释更简单。

要生成一个新的 ID，我们按以下步骤操作：

从多数实例（当 N=5 时即 3 个或更多）获取“current”的值。
如果未能联系到 3 个实例，则回到第 1 步。
在获取到的值中取最大值，并将其加 1。我们称之为 $NEXTID

向所有能够联系到的节点发送如下写操作。

IF current < $NEXTID THEN
    SET current $NEXTID
    return $NEXTID
ELSE
    return NULL
END

如果有 3 个或更多实例返回 $NEXTID，则算法成功，我们成功生成了一个新的单调递增 ID。
否则，如果未达到多数，则回到第 1 步。

第 4 步中发送的操作可以很容易地翻译成一个简单的 Redis Lua 脚本：

local val = tonumber(redis.call('get',KEYS[1]))
local nextid = tonumber(ARGV[1])

if val < nextid then
    redis.call('set',KEYS[1],nextid)
    return nextid
else
    return nil
end

它安全吗？

除了它以某种变体形式被用于那些经过深入分析的算法中之外，我直观地认为它可行的原因在于：

如果我们能够获得多数“投票”，那么从定义上来说，任何其他客户端都不可能为大于或等于我们所生成的 ID 获得多数。否则，就意味着已经有 3 个或更多实例的 current 值 >= $NEXTID，我们就不可能再获得多数。因此，生成的 ID 总是大于过去的 ID，出于同样的原因，两个实例也不可能生成相同的 ID。

也许有热心的读者能指出该算法中的缺陷，或是提供该算法在其他已分析系统中的应用分析，不过鉴于上述版本已改编为在客户端执行，实际涉及的进程更多，应该重新进行分析才能证明其等价性。

为什么它是一个慢算法？

这个算法的问题在于并发访问。如果许多客户端同时尝试生成新的 ID，可能谁都无法获得多数，从而需要用更大的数字重试。还要注意，这也意味着生成的 ID 序列中可能会出现“空洞”，因此客户端可能会生成 1、2、6、10、11、21、……这样的序列。因为许多数字可能会在并发访问导致的脑裂状态下被“烧掉”。

（注意，上一句中的“脑裂”并不是指节点之间出现了不一致的状态，而是指无法就某个 ID 达成多数一致。通常脑裂指的是配置上的冲突，例如多个节点都声称自己是主节点。不过在 Raft 论文中，脑裂一词的用法与我在这里的含义相同）。

在不因并发访问而频繁失败的前提下，每秒能生成多少个 ID 取决于网络往返时间和并发客户端的数量。不过有意思的是，你可以通过创建一个与集群通信的“ID 服务器”来提高该算法的可扩展性，由它来协调客户端的访问，将新 ID 的生成一个接一个地串行化。这并不会造成单点故障，因为你不需要只有一个 ID 服务器，可以运行多个以实现冗余，让数百个客户端连接到它们。

使用这种方案每秒生成 5000 个 ID 应该是可行的，尤其是如果客户端以一种聪明的方式实现，尝试通过多路复用或多线程的方式同时向 5 个节点发送请求。

另一种适用于客户端众多且没有节点居中协调的方案是，如果一轮算法失败，就使用随机化和指数退避的延迟再去联系节点。

为什么需要 fsync？

在这里，每次写入时执行 fsync 是强制性的，因为如果节点宕机后重启，它们必须拥有“current”键的最新值。如果 current 的值回退，就可能违背我们的安全性——新生成的 ID 必须始终大于过去生成的所有 ID。不过，如果你使用完整复制的状态机来实现同样的目标，无论如何也需要 fsync（但你就不会有并发访问的问题。例如在正常情况下使用 Raft，你只有一个可以发送请求的 leader）。

因此，对于 Redis，必须开启 AOF 并将 AOF 的 fsync 策略设为 always，以确保每次写入都在回复客户端之前持久化。

这些 ID 有什么用

这样的一组 ID 具有一种被称为“全序”的特性，因此在不同场景下都非常有用。通常在分布式计算中，很难判断哪个事件先发生、哪个后发生。有了这些 ID，你就能始终知道某些事件的先后顺序。

举个简单的例子：不同的进程使用这个系统，可以各自计算一组条目，并将各自的子列表保存在本地存储中。最后，它们可以将多个列表合并，得到一个顺序正确的最终列表，就好像从一开始就有一个所有进程都能追加条目的单一共享列表一样。

这一算法的由来

这里描述的内容与 Paxos 的第一阶段和 Raft 的 leader 选举都非常相似。不过，它似乎只是 Lamport 时间戳的一个特例，其中利用多数来创建全序。

非常感谢 Max Neunhoeffer 和 Martin Kleppmann 对本文初稿提供的反馈。文中如有任何错误，均由我本人负责。