昨天 Amplitude 发布了一篇关于扩展分析系统的文章，背景是使用 Set 数据类型。原文在这里：https://amplitude.com/blog/2015/08/25/scaling-analytics-at-amplitude/

在 Hacker News 上，有人提问为什么不直接用 Redis：https://news.ycombinator.com/item?id=10118413

Amplitude 的开发者有他们不使用 Redis 的理由，总的来说，如果你面对的是一个非常具体的问题，并希望以最优的方式来扩展它，那么去实现一套垂直的专属方案是合理的。我并不反对重复造轮子，有时你需要的就是一个非常特殊的轮子，而通用系统可能无法提供。此外，自己动手还能让你完全掌控自己的成果，激发创造力，增强作为开发者对自身能力的信心，也让你在未来遇到任何 bug 时都能独立调试，无需外部帮助。

当然，另一方面，从零开始编写系统软件是一件非常复杂的事，如果想持续演进，就需要不断投入开发；如果没有专门的团队来维护，就意味着得到一份停滞不前、不再演进的代码。如果系统非常垂直和专用，那么新系统很可能只能解决整个应用问题中的一小部分，却还要作为一个额外的组件来维护。此外，如果它主要由一两位程序员创建，而这些人后来离开了公司，那么后续的修复和演进就会成为一个大难题：既没有可观的外部社区，也找不到最初的开发者。

说到底，自研这件事本身无所谓好坏，要看具体情况。当然，能否判断什么时候值得从零开始、什么时候不值得，是一种需要判断力的事。优秀的开发者都明白这一点。

在我看来，无论 Amplitude 开发者最终的方案是什么，了解他们的思考过程以及为何不使用 Redis 都是很有意思的。他们提出的担忧之一就是 Redis 中 Set 数据类型的开销。我认为这种担忧是有道理的，Redis 的 Set 本可以更节省内存，而就在读到 Amplitude 这篇文章的几周前，我就已经开始探索提升 Set 内存效率的方法。今天我想和大家分享一下这些计划。

数据类型的双重表示

最初，数据结构都是朴素的实现，基本上就是按算法教材建议的那样：数据结构的每个节点都是动态分配的。分配开销、臃肿的指针、糟糕的缓存局部性，是这种基础方案的主要瓶颈。

后来我和 Pieter Noordhuis 为 Redis 的抽象数据类型实现了专门的版本，以实现极高的内存效率：通过单次分配来容纳几十甚至几百个元素，有时还会采用特制的编码来更充分地利用空间。这些版本的数据结构在某些操作上的时间复杂度为 O(N)，或者仅限于特定格式（数字）或大小的元素。

举个例子，当你创建一个 Hash 时，它起初会以一种对少量元素非常省内存的方式来表示。之后如果元素数量达到某个阈值，就会被转换为真正的哈希表。这意味着 Redis 数据类型的内存效率很大程度上取决于它所存储的元素数量。

下一步：Redis 列表

曾几何时，Twitter 的开发者们意识到，没有必要从用单次分配的数组来表示 List 中的元素，直接跳到内存效率低得多的真正链表。中间其实有一种折中方案：由多个小数组组成的链表，每个数组存放少量元素。他们的实现没有处理在中间删除元素时的碎片整理。过去我和 Pieter 也曾探讨过这种方案是否值得，但我们感觉整理碎片所付出的代价可能无法被节省的空间所抵消，而一个不做碎片整理的实现作为通用的 Redis 列表实现又过于脆弱：在中间删除几个元素，内存占用就会发生剧烈变化。

幸运的是，Matt Stancliff 以非常出色的方式实现了这个想法，包括碎片整理部分，经过一些实验，他证明新实现在性能上至少不亚于 Redis 当时的实现，而在内存占用方面则要好得多。此外，列表的内存效率不再取决于列表的大小，而且只需要维护单一的表示形式。

列表有点特殊，因为用小数组组成的链表确实是一种最优的表示方式，但它未必能轻易套用到其他数据类型上。能否为集合和其他数据类型也做类似的事情呢？

Redis 集合

集合的内存占用有点特殊。与其他所有由字符串组成的 Redis 数据结构不同，集合没有针对字符串集合的专门表示。因此即使是很小的集合也会消耗大量内存。实际上专门的表示是存在的，而且非常优秀，但仅在集合完全由数字组成且较小时才有效：在这种情况下，我们会用一种名为“intset”的特殊编码来表示集合。它是一个有序的整数线性数组，因此可以用二分查找来判断成员是否存在。数组会根据集合中最大的元素自动调整每个元素的大小，因此像包含字符串 1、20、30、15 这样的集合，每个元素只需占用一个字节再加上少量开销，因为这些字符串都可以表示为数字，且落在 8 位范围内。然而，只要往集合中加入一个“a”，它就会被转换成一个完整的哈希表：

127.0.0.1:6379> sadd myset 1 2 3 4 5
(integer) 5
127.0.0.1:6379> object encoding myset
"intset"
127.0.0.1:6379> sadd myset a
(integer) 1
127.0.0.1:6379> object encoding myset
"hashtable"

整数集合在 Redis 中是一种非常常用的数据类型，因此拥有这种优化确实很有用。但为什么我们没有像其他数据类型那样，为由非数字字符串组成的小集合提供专门的表示呢？当时我们的想法是，让一个数据类型拥有*三种*表示从 Redis 内部实现的角度来看并不是好事。如果你查看 t_zset.c 或 t_set.c，就会发现处理多种表示需要格外小心。你越想把对 N 种表示的处理抽象掉，就越难以利用某些优化。此外，列表的经验表明，有可能用单一的表示形式兼具所有优点。你在扫描包含 N 个元素的小聚合体上损失的，都能通过更好的缓存局部性赢回来，因此那些看起来像是悲剧性的时间/空间权衡的尝试，实际上并非如此。

专用化的 Redis 哈希表

大的哈希、非数字（或较大的）集合以及大的有序集合，目前都是由哈希表来表示的。其实现就在 dict.c 文件中。这是一个以相当简单的方式实现的哈希表，使用链地址法来解决冲突。这个哈希表实现中特殊的只有两点：它在 rehash 时从不阻塞，rehash 过程是增量进行的。这是我在获得 VMware 赞助最初几个月里做的，当然在延迟方面是一个巨大的改进。dict.c 还实现了一个由 Pieter Noordhuis 发明的名为“scanning”的特殊原语，它是一个基于游标的迭代器，没有额外开销也无需状态，但能提供合理的保证。除此之外，Redis 的哈希表期望键和值都是指向某物的指针，并需要提供用于比较和释放键、以及释放值的方法。

这正是你设计通用哈希表时想要的方式：到处都是指针和方法（函数指针）来处理值。然而 Redis 的数据结构有一个有趣的特性：复杂数据结构中的每个元素在语义上始终是字符串。哈希是字符串字段到字符串值的映射，集合是字符串的无序集合，依此类推。

如果我们实现一个专门用于存储字符串键和字符串值的哈希表会怎样呢？嗯……看起来有一种简单的方法可以让这样的哈希表变得非常省内存。我们可以把负载因子设为大于 1 的值，例如 10，这样如果哈希表中有 5 个桶，每个桶平均就会包含 10 个元素。

于是每个桶就会类似于一个由键值项组成的线性数组，带有前缀长度，与我们目前用于小数据类型编码的方式非常相似。比如：

0: <3>foo<3>bar<5>hello<6>world!<0>
1: <8>user:103<3>811 … <0>
2: … <0>

依此类推。编码可以是专门定制的，也可以直接使用像 MessagePack 这样的现有格式。这样一来，你在每个桶中多做的那点工作，有望通过获得的更好局部性得到补偿。

在这个数据结构之上实现 scanning 和增量 rehash 也是可行的，我已经做了初步分析，虽然不能直接照搬 dict.c 中的实现，但可以找到其他方法来达到同样的效果。

需要注意的是，从技术上讲，在这样的哈希表中存储指针也是可能的：从哈希表实现的角度来看，它们只是字符串，并且可以在哈希表类型中标明这些是指针，需要特殊处理（例如需要释放值的函数指针等）。不过是否值得这样做，只有通过测试才能知道。

不过，要将它用于比集合更广泛的场景，或者至少要*只*使用这种表示、从而去掉我们目前拥有的小数据结构表示，还有一些问题必须解决。例如，当前的小数据结构表示有一个非常有意思的特性：它们本身就已经是自身的序列化形式，无需额外处理：我们利用这一点将数据存入 RDB 文件、在 Redis Cluster 节点间传输数据等等。专用化的哈希表最好也具备同样的特性，或者至少每个桶本身就已经是无需后处理即可的序列化格式。如果做不到这一点，我们也可以仅在扩容后用这种新字典来替代通用的哈希表，这本身就已经是很大的胜利。

结论

这还是一个初步的想法，需要一些时间来完善设计、通过实现来验证，并进行深入的负载测试，以确保在某些合理的负载下不会出现严重的性能回退。如果一切顺利，我们最终可能会得到一个比以往内存效率高得多的 Redis 服务器。这样的哈希表还可以用来存储 Redis 的主字典，从而让每个键的开销变得小得多。