使用Rust为1100万并发用户扩展Elixir

在过去的一年里，Discorde的后端基础设施团队一直在努力提高我们核心实时通信基础设施的可扩展性和性能。

我们承担的一个大项目是改变我们更新会员列表的方式(屏幕右侧所有漂亮的人)。我们不需要为成员列表中的每个人发送更新，只需向下发送成员列表中可见部分的更新即可。这有明显的好处，比如更少的网络流量，更少的CPU使用量，更长的电池续航时间；不胜枚举。

然而，这给服务器端带来了一个大问题：我们需要一种能够容纳数十万个条目的数据结构，以一种特殊的方式进行排序，可以接受和处理大量的突变，并且可以返回添加和删除内容的索引。

ELXIR是一种函数式语言；它的数据结构是不可变的。这对于代码推理和支持您在编写Elixir时享受到的大规模并发性非常有用。不可变数据结构的双刃剑是，突变是通过采用现有数据结构和操作并创建全新的数据结构来建模的，该数据结构是将该操作应用于现有数据结构的结果。

这意味着，当某人加入一个拥有10万名成员的服务器(内部称为行会)时，我们将不得不构建一个包含100,001名成员的新列表。BEAM VM速度相当快，而且每天都在变得更快。它试图在可能的情况下利用持久数据结构，但在我们运营的规模上，这些大型列表的更新速度还不够快。

两名工程师接受了挑战，制造出一种纯粹的万灵丹数据结构，它可以容纳大的排序集，并支持快速变异操作。这说起来容易做起来难，所以让我们戴上计算机科学的头盔，深入数据结构设计的洞穴。

ELXIR附带一个名为MapSet的Set实现。MapSet是建立在Map数据结构之上的通用数据结构。它对许多集合操作很有用，但是它不能保证排序，而排序是成员列表的一个关键要求。这几乎排除了MapSet作为竞争者的可能性。

接下来是令人敬畏的列表类型：使用帮助器包装列表，该帮助器将强制唯一性，并在插入新元素后对列表进行排序。这种方法的一个快速基准显示，对于5,000个元素的小列表，插入时间在500𝜇s到3,000𝜇s之间测量。这已经太慢了，无法实现。

更糟糕的是，插入的性能随列表的大小和在列表中的位置深度而变化。最糟糕的情况是在250,000个项目列表的末尾添加一个新元素，这个列表大约有170,000个𝜇：基本上是永恒的。

Erlang附带了一个名为ordsets的模块。Ordset是有序集，所以听起来我们找到了问题的解决方案：让我们打破基准测试来检查可行性。当列表很小时，性能看起来相当不错，介于0.008𝜇和288𝜇之间。遗憾的是，当测试的大小增加到250,000时，最坏情况下的性能会增加到27,000𝜇，这比我们的自定义列表实现快了五倍，但仍然不够快。

在用尽了该语言附带的所有明显的候选程序之后，我们粗略地搜索了一下包，看看是否有人已经解决了这个问题并将其开源。检查了几个包，但它们都没有提供所需的属性和性能。值得庆幸的是，在过去的60年里，计算机科学领域一直在优化存储和排序数据的算法和数据结构，因此有很多关于如何继续进行的想法。

在小尺寸的情况下，这些数据集表现得非常好。也许有某种方法可以让我们将一堆非常小的指令集链接在一起，并在访问特定位置时快速访问正确的指令集。如果你侧着头，使劲眯着眼睛，这看起来就像是跳过列表，而这正是你所实现的。

这种新数据结构的第一个化身非常简单。OrderedSet是单元格列表的包装器，每个单元格内部都有一个较小的命令集：命令集的第一项、命令集的最后一项和项数的计数。这允许OrderedSet快速遍历单元格列表以找到合适的单元格，然后执行非常快速的命令集操作。通过在遍历实现中利用编译时间保护，您可以在阻碍命令集的最坏情况下获得相当好的性能。在250,000个条目列表末尾插入条目的速度从27,000𝜇下降到5,000𝜇，比原始命令集快5倍，比朴素列表实现快34倍。

旧的最差情况更好一些，但新的最差情况是在列表开头插入；一个250,000个项目列表以19,000个𝜇记录。什么？！

如果您考虑一下数据结构，这是有意义的。当您将一项插入到OrderedSet的前面时，它会在第一个Cell中结束，但该Cell是满的，因此它会将其最后一项逐出到下一个Cell，但该Cell是满的，因此它会将其最后一项逐出到Next Cell，依此类推。在这一点上，大多数工程师会耸耸肩，说“你不能既有蛋糕又吃蛋糕”，但在意见不一的情况下，我们正在挑战量子蛋糕技术的极限。

问题是，当空间被填满时，操作可能会从一个Cell级联到另一个Cell。如果我们能做些更聪明的事呢？如果我们允许单元格膨胀和拆分，并在列表中间动态插入新单元格，会怎么样？这样做的成本稍高，但好处是，最糟糕的情况是信元拆分，而不是2N个信元操作，其中N是信元的数量。

在较小的列表大小下，这个新的Dynamic OrderedSet可以在列表中4个𝜇到34个𝜇之间的任意位置执行插入。当我们把尺寸扩大到25万件时，真正的考验来了。在列表开头插入花费了…。。鼓声…。。4个𝜇s。看起来很快。但请记住，上一次我们让一个数字变快了，我们又让另一个数字变慢了。也许现在名单的末尾很可怕，最好检查一下。

在列表大小为250,000项的情况下，在列表末尾插入一项需要640𝜇。看起来我们有赢家了。

这个解决方案适用于最多25万名会员的公会，但这是扩展的限制。对于很多人来说，这将是故事的结局。但不和谐组织一直在利用铁锈让事情发展得更快，我们提出了一个问题：“我们能用铁锈来加快速度吗？”

Rust不是一种函数式语言，它可以让您很高兴地改变数据结构。它也没有运行时，并提供“零成本抽象”。如果我们能以某种方式让拉斯特来管理这套设备，它的表现可能会好得多。

我们的核心服务不是用Rust写的，它们是基于长生不老药的。长生不老药很好地实现了这一目的，幸运的是，BEAM VM还有另一个妙招。BEAM VM具有三种类型的功能：

内置于语言中并充当用户空间函数的构建块的函数。这些被称为BIF或内置函数。

然后是NIF或原生实现的功能。这些函数是用C或Rust构建的，并编译到BEAM VM中。调用这些函数就像调用BIF一样，但您可以控制它的功能。

有一个很棒的长生不老药项目叫“铁匠”。它在Elixir和Rust端提供了很好的支持，以创建行为良好的安全NIF，并且使用Rust的保证不会导致VM崩溃或内存泄漏。

我们留出了一周的时间，看看这是否值得我们付出努力。到了周末，我们可以衡量的概念证明非常有限。第一批基准非常有希望。向集合中添加条目的最好情况是0.4Erlang s，最差情况是2.85Erlang s，而OrderedSet的最差情况是4𝜇到640Erlang s。这只是一个使用整数的基准，但它足以增强对更广泛的𝜇术语的支持，并完善其余功能。

随着这个峰值显示出如此多的前景，我们继续构建对大多数Erlang术语的支持，以及成员列表所需的所有功能。现在是再次制定基准的时候了。我们把商品数量一路增加到100万件。测试机搅拌了几分钟，最后打印出结果：SortedSet最好的情况是0.61𝜇，最坏的情况是3.68𝜇，测试了从5,000到1,000,000个项目的多种大小的集合。

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

铁锈支持的NIF在不牺牲易用性或内存的情况下提供了巨大的性能优势。由于图书馆的所有操作都在1毫秒的阈值以下，我们可以只使用内置的Rustler保证，而不需要担心减少或减少。在调用者看来，SortedSet模块只是一个执行速度非常快的香草药剂模块。

今天，铁锈支持的SortedSet为每一个不和谐的行会提供动力：从计划去日本旅行的3人行会到20万人正在享受最新的有趣游戏。

自从部署SortedSet以来，我们看到性能在没有影响内存压力的情况下全面提升。我们了解到，铁锈和长生不老药可以并排工作，在极其严格的性能约束下运行。我们仍然可以将我们的核心实时通信逻辑保留在更高级别的灵丹妙药中，因为它具有出色的保证和容易的并发性，并且在需要时可以下降到Rust中。

如果你需要一个高速变异友好的SortedSet，我们已经发布了一个开源的SortedSet。

如果你对使用像Elixir和Rust这样的强大工具来解决难题感兴趣，那就去看看我们的招聘页面吧。