去年，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 相比，向 SortedSet 添加元素的最佳情况是 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。