The binary search of distributed programming

2016-02-14

分布式编程中的二分查找

昨晚我又重新读了一遍 Martin Kleppmann（马丁·克莱普曼）写的 Redlock 分析（http://martin.kleppmann.com/2016/02/08/how-to-do-distributed-locking.html）。马丁在某处思考，是否有办法利用 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 生成 ID。否则，已经会有 3 个或更多实例的 current 值大于等于 $NEXTID，而我们就不可能获得多数。因此，生成的 ID 始终大于过去的 ID；同理，两个实例也不可能生成相同的 ID。

也许哪位好心的读者可以指出这个算法中的 bug，或者指出其他经过分析的系统中对该算法的分析。不过，鉴于上面的算法经过了调整，要在客户端一侧执行，实际上涉及更多进程，因此应当重新分析，以证明它与原算法等价。

为什么这是一个慢算法？

这个算法的问题在于并发访问。如果许多客户端同时尝试生成新的 ID，可能没有任何人能够获得多数，于是它们需要使用更大的数字再次重试。注意，这也意味着生成的 ID 序列中可能出现“空洞”，因此客户端可能生成出 1、2、6、10、11、21……这样的序列。因为并发访问导致的“脑裂”(split brain)状态可能会“烧掉”许多数字。

（注意，上面这句话中的“脑裂”(split brain)并不意味着节点之间存在不一致状态，只是意味着无法达到多数派，就某个给定的 ID 达成一致。通常，脑裂指的是配置冲突，例如多个节点都声称自己是主节点。不过，在 Raft 论文中，split brain 一词的含义与我在这里使用的相同。）

在不因并发访问而频繁失败的情况下，每秒能够生成多少个 ID，取决于网络 RTT 和并发客户端的数量。不过，有趣的是，可以通过创建一个与集群通信的“ID 服务器”，将新 ID 的生成逐个串行化，从而协调客户端的访问，使算法更具可扩展性。这不会造成单点故障，因为不需要只有一个 ID 服务器；可以运行几个服务器来实现冗余，让数百个客户端连接到它们。

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

当客户端很多且没有节点协调访问时，另一种方法是：如果算法的一轮执行失败，就使用随机化的指数延迟，再次联系各个节点。

为什么需要 fsync？

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

因此，对于 Redis，必须启用 AOF，并将 AOF fsync 策略设置为 always，以确保写入在回复客户端之前始终已经持久化。

这些 ID 能用来做什么

这样的一组 ID 具有一种称为 total ordering(全序)的属性，因此在不同场景中都非常有用。在分布式计算中，通常很难判断什么发生在前、什么发生在后。使用这些 ID，你总能知道某些事件的顺序。

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

这个算法的起源

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

非常感谢 Max Neunhoeffer（马克斯·诺伊恩霍弗）和马丁对这篇博客文章初稿提出的反馈。请注意，任何错误都由我本人负责。