使用Patricia Trie压缩树优化nanomsg中的订阅场景

原文链接：https://250bpm.com/blog:19/

当我编写ZeroMQ的订阅子系统时，我的假设是在任何时候都会有数千个订阅，或者在最坏的情况下是数万个订阅。这一假设反映了我在金融服务业的背景，在那里，订阅主要用于订阅股票报价。你订阅的主题是股票的名称，通常有数以万计的股票，即使你考虑到期货和期权等衍生品。

然而，事实证明，有不同的场景。最近，我使用ZeroMQ管理100000000多个订阅的用户进行了交谈。（嗨，伙计们！）但很高兴该算法在设置中仍然有效，比我最初的估计高出四个数量级。

思考这样的用例会引发两个基本问题：首先，订阅转发是否能够处理这样的订阅负载，以及当发布者和订阅者之间的连接断开并重新建立时会发生什么？第二，我们是否可以以更节省内存的方式存储订阅，以便在内存耗尽之前处理更多订阅？

在这篇文章中，我将忽略前一个问题（这是一个复杂的问题，我们还没有一个完美的答案），而专注于后一个问题。

当然，存储订阅的内存占用对于最大限度地减少处理大型订阅集所需的服务器数量非常重要。这反过来转化为更低的成本，包括资本和运营费用。

然而，即使是小的订阅集（那些可以放在一个盒子里的订阅集），最大限度地减少内存占用也是有意义的。具体来说，当订阅集增长到操作系统开始将其交换到磁盘上的程度时，应用程序的响应时间可能会增加到基本上不可用的程度。

在低延迟环境中，同样的参数适用于CPU缓存：一旦订阅集增长到可以存储在CPU缓存中的位置之外，消息过滤将不得不访问物理内存，并且延迟比以前高得多。

话虽如此，现在让我们看看订阅匹配在ZeroMQ中是如何工作的，以及它在nanomsg中是如何改进的。

在ZeroMQ中，用于存储订阅的结构是一个trie（字典树：https://en.wikipedia.org/wiki/Trie）：

格式的低效性是显而易见的：如果订阅由长度超过一个字符的元素组成（如英语单词、股票代码等），则为每个字符分配一个trie节点是极其浪费的。

为了改善内存占用，nanomsg使用patricia trie（压缩树：https://en.wikipedia.org/wiki/Radix_tree）代替：

通过在单个节点而不是单个字符中存储字符串，我们可以最大限度地减少存储订阅集所需的节点数量。在上面的例子中，节点的数量从28（简单trie）下降到7（patricia trie），即下降到25%！

在订阅往往很长的情况下，trie的终端分支通常相当长。在这种情况下，切换到patricia trie将分配的节点数量减少到10%甚至更少：

虽然patricia trie在减少trie中的节点数量方面非常有效，但还有另一个指标会影响内存占用，即节点结构本身的大小。

ZeroMQ为每个节点分配一个固定大小的数据结构，如果（且仅当）节点有多个子节点，它会为子节点分配一张指针表。该表由子级表示的字符编制索引。下图显示了订阅“A”和“F”的表示形式：

可以看出，格式是以这样一种方式优化的，即不必分配256个指针的数组，每个可能的后续字符一个指针（这意味着每个节点有多达2kB的内存！），而是分配一个从最低的现有字符开始，到最高的现有后续字符结束的数组。虽然这种优化节省了大量空间，但它并不完美。例如，如果两个订阅是“A”和“z”，指针将占用0.5kB。

为了缓解这个问题，nanomsg引入了两种不同类型的节点。有一个“密集”节点（用于具有9+个子节点），与ZeroMQ中的节点基本相同；并且有一个“稀疏”节点（用于具有1-8个子节点）可以消除所有的NULL指针：

这样，订阅“A”和“z”只需要16个字节来存储子指针（而不是ZeroMQ中的464个）。

其主要思想是，内存贪婪的“密集”节点（每个节点高达2kB）相对罕见，具有典型的订阅集（<1%），并且大多数trie由“稀疏”节点组成（每个节点最高64字节）。

最后，应该指出的是，指针表和节点本身被分配在一个块中，而在ZeroMQ中，两者被分别分配。这是一个小的优化，但它加快了一些场景。此外，考虑到每个节点只有一个块头而不是两个块头，内存占用会稍微好一些。此外，当分配的块的数量下降50%时，内存碎片往往不会那么严重。

我对新算法所做的少量测试表明，对于典型的订阅集，它将内存使用量降低到ZeroMQ使用量的10%以下。