昨天 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 的一系列理由，而且一般来说，如果你有一个非常具体的问题并希望以尽可能好的方式进行扩展，实现一个垂直解决方案是有道理的。我并不反对重复造轮子，有时你需要的正是非常特殊的轮子，而通用系统可能无法提供。此外，打造自己的解决方案能让你掌控自己的成果，激发创造力，增强你作为开发者对自身能力的信心，并使你在未来出现任何错误时都能够无需外部帮助自行调试。

另一方面，从零开始创建系统软件当然是一件非常复杂的事情，如果希望持续积极地开发它，就需要不断的投入；如果没有专门的团队，则意味着会得到一份停滞不前、不会演进的代码。如果它非常垂直和专业化，新系统很可能只能处理整个应用问题中的一小部分，而你却必须将其作为一个额外的组件来管理。此外，如果它主要是由一两个后来离开公司的程序员创建的，那么修复和演进它就会成为一个非常大的问题：既没有可观的外部社区，也没有原来的开发者。

基本上，在内部编写这些东西本身并无好坏之分，视情况而定。当然，能否判断何时值得从零开始实现、何时不值得，是一种敏感度的体现。优秀的开发者都明白这一点。

在我看来，无论 Amplitude 开发者最终的解决方案是什么，阅读他们的过程以及他们不使用 Redis 的原因都是很有趣的。他们提出的一个担忧是 Redis 中 Set 数据类型的开销。我认为他们有这样的担忧是合理的，Redis 集合本可以更加节省内存，而在阅读 Amplitude 文章的几周前，我就已经开始探索提高集合内存效率的方法。今天我想与大家分享这些计划。

数据类型的双重表示

原则上，存在朴素的数据结构，或多或少是按照算法教科书建议的方式实现的：数据结构的每个节点都是通过动态分配来实现的。分配开销、胖指针、糟糕的缓存局部性是这种基础方案的主要局限。

后来，我与 Pieter Noordhuis（皮特·诺德赫伊斯）一起为 Redis 抽象数据类型实现了专门的实现，以实现极高的内存效率，使用单次分配来容纳几十个甚至几百个元素，有时还采用特别的编码来更好地利用空间。这些数据结构的版本对某些操作具有 O(N) 的时间复杂度，或者有时仅限于具有特定格式（数字）或大小的元素。

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

下一步：Redis 列表

在某个时候，Twitter 的开发者意识到，没有理由从以单次分配的数组来表示 List 中的元素，转而使用实际的链表——后者的内存效率要低得多。中间有一种折中方案：由包含少量元素的数组组成的链表。他们的实现在中间删除元素时不会处理碎片整理。过去我和皮特·诺德赫伊斯曾试图弄清楚这是否值得，但我们隐约觉得碎片整理的开销可能无法被节省的空间所抵消，而一个不做碎片整理的这种想法的实现，作为 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 o t_set.c，就会发现处理多种表示需要一些细心。越想抽象掉对 N 种表示的处理，就越无法使用某些优化。此外，列表的故事表明，有可能拥有一种兼具所有优点的单一表示。你在扫描包含 N 个元素的小聚合体方面所损失的，会因为更好的缓存局部性而赢回来，因此可以尝试一些看起来像是悲剧性的时间/空间权衡，但实际上并非如此的事情。

特化 Redis 哈希表

大的哈希、非数字（或大的）集合以及大的有序集合，目前都是由哈希表表示的。其实现位于 dict.c 文件中。它是一个以相当简单的方式实现的哈希表，使用链地址法来解决冲突。这个哈希表实现中特殊的地方只有两点：它为了 rehash 而从不阻塞，rehash 过程是增量式处理的。这是我在 VMware 赞助的头几个月里做的，当然在延迟方面是一个很大的胜利。dict.c 还实现了一个名为“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 和增量式 rehashing 也是可行的，我做了初步分析，虽然不可能直接复制 dict.c 中的实现，但有可能找到其他方法来获得相同的效果。

需要注意的是，从技术上讲，在这样的哈希表中存储指针是可能的：从哈希表实现的角度来看，它们只是字符串，并且可以在哈希表类型中标明这些是需要特殊处理的指针（例如 free-value 函数指针之类）。然而，只有测试才能说明这是否值得。

然而，要将此用于集合以外的用途，或者至少为了*仅*使用这种表示而淘汰我们目前拥有的小表示形式，还有一些必须解决的问题。例如，当前的小表示有一个非常有趣的特性：它们本身已经是自身的序列化形式，无需额外工作：我们利用这一点将数据存储到 RDB 文件中，在 Redis Cluster 的节点之间传输数据等等。专门的哈希表最好也具有相同的特性，或者至少每个单独的桶应该已经是序列化格式而无需任何后处理工作。如果不是这样，我们也可以仅在扩容后用这种新字典来代替通用哈希表，这已经是一个很大的胜利。

结论

这是一个初步的想法，需要一些时间来改进设计，随后通过实现来验证，并进行深入的负载测试以保证在某些合理的工作负载下不会出现巨大的回退。如果一切顺利，我们最终可能会得到一个比过去节省大量内存的 Redis 服务器。这样的哈希表还可以用于存储主 Redis 字典，以使每个键的开销小得多。