Lazy Redis is better Redis

2015-09-26

惰性 Redis 才是更好的 Redis

大家都知道 Redis 是单线程的。了解得更深入的人会告诉你，实际上 Redis 算是单线程的，因为它也有线程来执行某些在磁盘上的慢操作。到目前为止，多线程操作都专注于 I/O，因此我们那个用于在另一个线程上执行异步任务的小型库被命名为 bio.c：基本上就是 Background I/O。

不过前段时间我提交了一个 issue，承诺实现一个很多人都想要、我自己也包括在内的 Redis 新特性，叫作“lazy free(惰性释放)”。原始 issue 在这里：https://github.com/antirez/redis/issues/1748。

这个 issue 的核心是，Redis 的 DEL 操作通常是阻塞的。因此，如果你向 Redis 发送“DEL mykey”，而你的 key 恰好包含 5000 万个对象，服务器将会阻塞数秒，在此期间无法处理任何请求。从历史上看，这主要被接受为 Redis 设计的一个副作用，但在某些使用场景中，它确实构成了限制。DEL 并不是唯一会阻塞的命令，但它比较特殊，因为我们通常会说：只要使用 O(1) 和 O(log_N) 命令，Redis 就会非常快。你当然可以使用 O(N) 命令，但要注意，这并不是我们优化的场景，要做好出现延迟尖峰的准备。

这听起来很合理，但与此同时，即使是通过快速操作创建的对象，也终究需要被删除。而在这种情况下，Redis 会阻塞。

第一次尝试

在单线程服务器中，让操作变得非阻塞的简单方法，是增量地执行操作，而不是让整个系统停下来。因此，如果要释放 100 万次分配，与其在一个 for() 循环中阻塞所有操作，不如例如每毫秒释放 1000 个元素。所使用的 CPU 时间相同，或者会稍多一点，因为增加了更多逻辑，但从用户的角度看，延迟会好得多。甚至可能原本就没有使用释放每毫秒 1000 个元素所需的那些 CPU 周期。避免阻塞数秒才是关键。Redis 内部的许多机制都是这样工作的：LRU eviction(LRU 淘汰)和 key 过期是两个明显的例子，此外还有很多，例如哈希表的 incremental rehashing(增量重新哈希)。

所以这是我尝试做的第一件事：创建一个新的定时器函数，在那里执行回收。对象会先被放入一个链表中，在每次调用定时器函数时，缓慢而增量地回收。要让它运行良好，需要一些技巧。例如，使用哈希表实现的对象也采用 Redis SCAN 命令内部使用的同一种机制进行增量回收：在字典中设置一个游标，逐个遍历并释放元素。这样，每次调用定时器时，就不必释放整个哈希表。游标会告诉我们上次退出定时器函数时进行到哪里，下次重新进入时从那里继续。

自适应很难

你知道这其中最难的部分是什么吗？这一次，我们要增量执行的是一项非常特殊的任务：释放内存。因此，如果我们在增量释放内存的同时，服务器内存增长得非常快，那么为了保证延迟，我们最终可能会消耗数量无上限的内存。这非常糟糕。比如想象一下：

WHILE 1
    SADD myset element1 element2 … many many many elements
    DEL myset
END

如果后台删除 myset 的速度比我们的 SADD 调用每次添加大量元素的速度慢，那么内存使用量就会永远增长。

不过经过几次实验，我找到了一个让它运行得非常好的办法。定时器函数使用了两个思路，以便根据内存压力进行自适应调整：

检查内存趋势：是在上升还是下降？据此调整释放的积极程度。
同样根据“1”的结果调整定时器本身的频率：当需要释放的内容很少时，不要让事件循环不断被打断，从而浪费 CPU 时间。同时，在确实需要时，定时器频率可以达到约 300 HZ。

下面是实现这些思路的函数中如今已经不存在的一小段代码：

/* Compute the memory trend, biased towards thinking memory is raising
 * for a few calls every time previous and current memory raise. */
if (prev_mem < mem) mem_trend = 1;
mem_trend *= 0.9; /* Make it slowly forget. */
int mem_is_raising = mem_trend > .1;

/* Free a few items. */
size_t workdone = lazyfreeStep(LAZYFREE_STEP_SLOW);

/* Adjust this timer call frequency according to the current state. */
if (workdone) {
    if (timer_period == 1000) timer_period = 20;
    if (mem_is_raising && timer_period > 3)
        timer_period--; /* Raise call frequency. */
    else if (!mem_is_raising && timer_period < 20)
        timer_period++; /* Lower call frequency. */
} else {
    timer_period = 1000;    /* 1 HZ */
}

这是个不错的技巧，而且运行得非常好。但我们仍然得有点遗憾：必须在单线程中执行这项操作。为了妥善处理它，需要大量逻辑；而且，当惰性释放周期非常繁忙时，每秒操作数会降到正常水平的约 65%。

在另一个线程中释放对象会简单得多：如果有一个线程专门忙于执行释放操作，那么释放通常几乎总是比向数据集添加新值更快。当然，负责调用分配器的主线程与执行惰性释放的线程之间会存在一些竞争，但 Redis 花在内存分配上的时间只占一小部分，而花在 I/O、命令分发、缓存未命中等方面的时间要多得多。

不过，实现多线程惰性释放有一个大问题：Redis 本身。其内部设计完全偏向于在各处共享对象。毕竟它们是引用计数的，对吧？那为什么不尽可能多地共享呢？这样可以节省内存和时间。举几个例子：如果执行 SUNIONSTORE，最终得到的目标集合中会有共享对象。同样，客户端输出缓冲区中有对象列表，用来将要发送到 socket 的回复，因此在执行 SMEMBERS 之类的调用期间，集合中的所有成员最终都可能被共享到输出缓冲区列表中。所以，共享对象听起来非常有用、可爱、美妙、棒极了。

但是，等等，这里还有更多问题。如果在执行 SUNIONSTORE 之后重新加载数据库，对象就会变成非共享的，因此内存可能会突然增长到比原来更多。这可不太好。而且，当我们向客户端发送回复时，会发生什么？对于较小的对象，我们实际上会把它们拼接成普通缓冲区，否则执行许多次 write() 调用并不高效！（顺便提示一下，writev() 也帮不上忙。）所以我们大多数时候本来就在进行复制。而在编程中，某个东西如果没有用却存在，那它很可能就是个问题。

事实上，每次你需要访问一个值时，如果这个 key 包含聚合数据类型，就必须遍历下面这些结构：

key -> value_obj -> hash table -> robj -> sds_string

那么，何不彻底去掉“robj”结构，将聚合值转换为只由 SDS 字符串组成的哈希表（或跳跃表）呢？（SDS 是 Redis 内部用于处理字符串的库。）但这里有一个问题。想象一下像 SADD myset myvalue 这样的命令。比如，我们不能直接取得 client->argv[2]，然后在实现这个集合的哈希表中引用它。值有时必须被复制，不能重用客户端参数向量中已经存在的值，因为那些值是在解析命令时创建的。不过 Redis 的性能主要受缓存未命中影响，因此少一次间接访问或许可以弥补这一点？

于是我开始着手这个新的 lazyfree 分支，并在 Twitter 上不带任何上下文地发推文，让所有人都以为我不是绝望了就是疯了（最后有几个人问这到底是什么 WTF lazyfree 东西）。那么我做了什么？

将客户端输出缓冲区改为只使用动态字符串，而不是 robj 结构。创建回复时，值总是会被复制。
将所有 Redis 数据类型转换为使用 SDS 字符串，而不是共享的 robj 结构。听起来很简单？经过数周时间，修改了约 800 行极易引发 bug 的代码。但现在所有测试都通过了。
将 lazyfree 重写为多线程实现。

结果是，Redis 现在更加节省内存，因为数据结构的实现中不再到处使用 robj 结构（不过在大量共享发生的代码路径中仍然会使用它们，例如命令分发和复制期间）。多线程惰性释放运行得很好，回收内存的速度比增量版本更快；即使我非常喜欢增量版本的实现，而且与多线程版本相比，它也并没有糟糕到哪里去。不过现在，你可以删除一个巨大的 key，而性能下降几乎可以忽略，这非常有用。但最有意思的是，到目前为止我测试过的所有操作中，Redis 现在都更快了。减少一次间接访问在这里确实带来了胜利。即使在无关的基准测试中，它也会更快，只是因为客户端输出缓冲区现在更简单、更快。最后，我从这个分支中删除了增量惰性释放的实现，只保留多线程版本。

关于 API 的说明

不过 API 怎么办？我们仍然有一个会阻塞的 DEL，默认行为也保持不变，因为 Redis 中的 DEL 意味着：立即回收内存。我不喜欢改变这一点。因此现在有了一个新命令 UNLINK，它更明确地说明了对值所做的事情。

UNLINK 是一个智能命令：它会计算一个对象的释放成本，如果成本非常小，就直接执行 DEL 应有的行为，尽快释放对象。否则，对象会被发送到后台队列中处理。从 key 空间语义的角度看，这两个命令完全相同。

FLUSHALL / FLUSHDB 的非阻塞变体也已经实现，但还没有提升到 API 层面；它们只会接受一个 LAZY 选项，给出该选项后就会改变行为。

不只是惰性释放

现在，聚合数据类型的值已经完全取消共享，客户端输出缓冲区中也不再包含共享对象，因此有很多可以利用的地方。例如，Redis 终于可以实现多线程 I/O，让不同客户端由不同线程提供服务。这意味着，只有访问数据库时才需要全局锁，而客户端的读写系统调用，甚至客户端所发送命令的解析，都可以在不同线程中进行。这种设计类似于 memcached，也是我期待实现和测试的一种设计。

此外，现在还可以在另一个线程中执行聚合数据类型上的某些慢操作，这样只有少数 key 会被“阻塞”，其他所有客户端都可以继续运行。实现方式与我们目前处理阻塞操作的方式非常相似（参见 blocking.c），再加上一个哈希表，用于记录当前哪些 key 正忙，以及被哪个客户端占用。因此，如果某个客户端请求类似 SMEMBERS 的操作，就可以只锁定对应的 key，处理请求并创建输出缓冲区，之后再释放该 key。只有尝试访问同一个 key 的客户端会在该 key 被锁定时阻塞。

所有这些都需要更加彻底的内部改动，但这里的底线是：我们又少了一个禁忌。我们可以用更少的缓存未命中和更小的聚合数据类型内存占用来弥补对象复制的时间，因此现在可以自由地思考采用 share-nothing design(无共享设计)的多线程 Redis，而这正是唯一一种能够轻松超越单线程 Redis 的设计。过去，如果把多线程 Redis 理解为在数据结构和对象中加入一组互斥锁来实现并发访问，那么它一直被视为一个糟糕的想法；但幸运的是，还有其他方案可以兼得两者的优点。而且，如果我们愿意，仍然可以像过去一样，让主线程处理所有快速操作。从性能角度看，这应该只会带来收益，代价则是一些可控的复杂性。

预计时间

我改动了很多内部实现，这不是明天就能上线的东西。因此我的计划是，把我们已经放入 unstable 的 3.2. 称为当前版本，完成将其推进到 Release Candidate 状态的工作，然后将这个分支合并到 unstable，目标版本是 3.4。

不过在合并之前，必须非常仔细地检查是否存在速度回归。显然还有更多工作要做。

如果你想试一试，可以查看 Github 上的“lazyfree”分支。顺便提醒一下，我目前正在非常积极地开发它，因此某些功能可能会在某些时候完全无法运行。