Rust代替Elixir实现好友列表下发(体量1100W)

去年，Discord的后端基础设施团队努力提高核心实时通信基础设施的可扩展性和性能。

我们进行的一个大项目是改变我们更新会员列表的方式（屏幕右侧的那些漂亮的头像）。我们可以直接发送会员列表中可见部分的更新(分页)，而不是为会员列表中的每个人发送更新。这样做的好处很明显，例如网络流量更少，CPU使用率更低，电池寿命更长等等。

然而，这在服务器端造成了一个大问题：我们需要一个能够容纳数十万个条目的数据结构，以一种可以处理大量更新的方式进行排序，并且可以上报会员的位置索引添加和删​​除。

Elixir是一种函数式语言，它的数据结构是不可变的。这对推理代码并支撑大量并发性都非常好。不可变数据结构的双刃剑。现有的数据结构的更新是通过创建全新数据结构来实现的，该全新数据结构是将该操作应用于现有的数据结构的结果。

这意味着当有人加入服务器（内部称为公会）并拥有100,000名成员的成员列表时，我们必须构建一个包含100,001名成员的新列表。 BEAM VM非常快速，并且 每天都在变得更快 。Elixir试图在可能的情况下利用 persistent data structure ，但在我们运营的规模上，这些大型列表无法足够快地更新。

将Elixir推至极限

两位工程师接受了制作纯Elixir数据结构的挑战，该数据结构可以容纳大型sorted sets并支持快速更新操作。这说起来容易做起来难。

Elixir附带一个名为MapSet的set实现。 MapSet是构建在Map数据结构之上的通用数据结构。它对许多Set操作很有用，但它不能保证有序，但这是成员列表的关键要求，排除MapSet。

接下来将是古老的List类型：对List做一层封装，强制保证唯一性并在插入新元素后对列表进行排序。这种方法的压测数据表明，对于小型列表(5,000个元素) ,插入时间在500μs和3,000μs之间。这太慢了，不可行。

更糟糕的是，插入的性能与列表的大小和列表中的位置深度成正比。在250,000个元素的末尾添加一个新元素，大约170,000μs：基本上是恒定的。

两次失败，但BEAM尚未退出竞争。

Erlang附带一个名为ordsets的模块。 Ordsets是有序sets，所以听起来我们找到了解决问题的方法：让我们压测一下以检查可行性。当列表很小时，性能看起来相当不错，测量范围在0.008μs和288μs之间。遗憾的是，当测试的大小增加到250,000时，最坏情况下的性能提高到27,000μs，这比我们的自定义List实现速度提高了五倍，但仍然不够快。

尝试了语言附带的所有候选者，粗略地搜索了lib，看看其他人是否已经解决了这个问题并开源。看了一些lib，但它们都没有提供所需的属性和性能。值得庆幸的是，计算机科学领域一直在优化用于存储和分类数据的算法和数据结构，因此有很多关于如何进行的想法。

SkipList

ordset在小数据下表现非常出色。也许有一些方法可以将一堆非常小的ordsets链接在一起，并在访问特定位置时快速访问正确的ordset。这类似于一个 skiplist 。

这个新数据结构的第一个版本非常简单。 OrderedSet是一个Cell列表的封装，每个Cell内部都是一个小的ordset：ordset的第一项，ordset的最后一项，以及count。这允许OrderedSet快速遍历Cells列表以找到适当的Cell，然后执行非常快速的ordset操作。在250,000项目列表的末尾插入项目从27,000μs降至5,000μs，比原始ordsets快5倍，比原始List实现快34​​倍。

性能有所提升，但是在列表的头部Cell创建250,000个元素，单个插入时间仍为19,000μs。

这是有道理的。当你在OrderedSet的前面插入一个项目时，它会在第一个Cell中结束，但是Cell已经满了，所以它将它的最后一个项目驱逐到下一个Cell，但是Cell已经满了，所以它将它的最后一个项目驱逐到下一个Cell，依此类推。

OrderedSet

问题在于，当元素填满时，操作会从Cell级联到下一个Cell。如果我们允许Cell分裂，在列表中间动态插入新Cell呢？好处是：最坏的情况是Cell分裂，而不是级联。

优化后的情况：

在小列表时，这个新的OrderedSet可以在列表中的任何点执行4μs和34μs之间的插入，不错。我们将尺寸调整到250,000。在列表的开头插入，第一个插入为4μs，后面会逐惭变慢。最终在列表末尾插入一个项目需要640μs，看起来还行。

必须更快！

上面的解决方案适用于高达250,000名成员的公会，但我们想要更多！Discord一直在使用Rust来让事情变得更快，我们可以使用Rust来加快速度吗？

Rust不是一种函数式语言，可以使用可变数据结构。它也没有运行时并提供“zero-cost abstractions”。如果我们用Rust，它可能会表现得更好。

我们的核心服务不是用Rust编写的，它们是基于Elixir的。 Elixir非常适合调用Rust，幸运的是，BEAM VM还有另一个漂亮的技巧。 BEAM VM有三种类型的函数：

1. 用Erlang或Elixir编写的函数。这些是简单的用户空间函数。
2. 内置于语言中的函数，充当用户空间函数的构建块。这些被称为BIF或内置函数。
3. NIF或native函数。这些是使用C或Rust构建并编译到BEAM VM中的函数。调用这些函数就像调用BIF一样，但是你可以控制它的功能。

有一个名为 Rustler 的Elixir项目。它为Elixir和Rust提供了很好的支持，可以创建一个表现良好的安全的NIF，并保证使用Rust不会VM崩溃或内存泄漏。

我们预留了一个星期，看看这是否值得付出努力。到本周末，我们可以衡量一个非常有限的概念验证。第一个基准非常有希望。与OrderedSet的4μs至640μs相比，向其添加元素的最佳情况是0.4μs，最差情况为2.85μs。这只是使用integer的测试，但它足以证明优于Elixir的实现。

有了数据支撑，我们决定继续扩展程序支持更多的Elixir数据类型。最后我们的测试数据如下：日我们将数量一直增加到1,000,000。最后打印出结果：SortedSet最佳情况为0.61μs，最差情况为3.68μs，其基于多种大小的sets，从5,000到1,000,000项。

对于连续的第二次迭代，我们能够使最坏的情况与先前的迭代最佳情况一样好。

Rust支持的NIF提供了巨大的性能优势，而无需牺牲易用性或内存。

喜讯

今天，Rust版的SortedSet为每一个Discord公会提供支持：从计划到日本旅行的3人公会到享受最新、有趣的游戏的20万人公会。

自部署SortedSet以来，我们已经看到性能全面提升，不会对内存压力产生影响。我们了解到Rust和Elixir可以并肩工作，以极其严格的性能约束进行操作。我们仍然可以将我们的核心实时通信逻辑保留在更高级别的Elixir中，它具有出色的保护和简单的并发实现，同时在需要时可以使用Rust。

如果你需要一个对高速更新友好的SortedSet，我们已经发布了 SortedSet 作为一个开源库。