「靡不有初，鲜克有终」

【译】server design

Posted 2022-06-18 20:31:22 ‐ 30 min read

原文

介绍

本文章的目的是分享我在过去这些年开发多种应用的经验，'server' 只能近似总结这多种应用。更加精确的表达是，我开发的应用被设计为每秒处理大量分离消息或者请求。网络服务器最适合描述这种应用，但是不是所有的应用都在服务端。因此为了简化处理，因为 "高性能请求处理程序" 这个标题太蠢了，我们只用 “server” 代称好了。

我关注的不是轻量级并发应用，即使在单个应用上多任务处理已经相当普遍。你正在阅读这篇文章的浏览器就是并行处理程序，但是这种程度的并发不存在很多有趣的挑战。当请求处理程序达到基础设施性能瓶颈的时候会出现很多有趣的挑战，所以提升基础设施容量可以提升性能。浏览器运行几个 tab 不会达到这种限制。这篇文章关注的重点不在于小流量的应用，而在于大流量的应用，如何在硬件限制下做到这一点很重要。

有些人肯定会对我的建议产生异议，或者认为他们有更好的方案。没问题，我不是想成为完全正确的声音，这些只是我工作过程中总结的方法，不仅包括性能方面，还包括调试难度和代码可扩展性。你的经验可能是不一样的，如果有什么可以对你产生帮助那再好不过，但请注意，这里的建议确实都可以用其他方式来代替，我也曾经尝试过，你的故事可能就是其中之一，如果你觉得应该展示出来，读者可能会很无聊。你不想伤害他们，对吗？

文章的剩余部分分为四个主要部分：

  1. 数据复制
  2. 上下文切换
  3. 内存分配
  4. 锁竞争

最后还有一些细枝末节的内容，但是上面的四个部分才是性能杀手。如果你处理请求的应用没有数据拷贝，没有上下文切换，没有频繁的内存分配，没有锁竞争，即使有一些其他的小问题，服务也会有很好的性能。

数据复制

这部分比较短，因为大多数人已经了解过这个方面了。每个人都知道数据拷贝不好，对吧。但是事实上，这个显然性是因为你很早就在计算机的相关课程中学习到了这部分内容，而这知识因为几十年前有人开始提出这个词发生的。如今，它已经覆盖在每个学校的课程和每个非正式的指南中，同时市场发现 "zero copy" 是一个很好的流行语。

尽管数据拷贝显然是坏的，人们还是会经常忽略这个问题。最重要的一点是数据拷贝通常是隐式的或者伪装的。你确定你的代码在调用驱动程序或者其他代码的时候是否会进行数据拷贝吗？可能会比你想象的多。猜猜 programmed I/O 表示什么。一个伪装而不是隐式的例子是 hash function，它有所有拷贝数据的访问操作以及计算。一旦有人指出 hash 存在复制，显然需要避免它，据我所知，有一群聪明人通过艰难的方式解决这个问题。如果你真的想要解决数据拷贝，要么是因为确实损害到了你应用的性能，要么是你在你的 ppt 上要写 zero copy ，你需要追踪很多东西并不宣传它们。

避免数据拷贝的方法是使用间接性，传递 buffer 的描述，而不是仅仅 buffer 指针。每个 buffer 描述包括：

  • 指针以及指针指向 buffer 的长度
  • 指针和长度，或者 offset 和长度，描述 buffer 真正被填充的部分
  • list 中前向和后向的 buffer 描述
  • 引用计数

现在不需要拷贝数据，只需要增加引用计数。这可以在一些场景下工作的很好，包括典型的网络协议栈，但是这需要较大的头部空间。通常来说，在 list 的头和尾增加 buffer ，臧家整个 buffer 的引用，或者销毁整个 buffer 是容易的。在中间增加，销毁，或者引用部分 buffer 是比较困难的。尝试分割合并 buffer 会使你感到沮丧。

我不建议你在所有场景应用这种方法。为什么？因为当你要遍历所有的描述链时会很痛苦，这比数据复制更糟糕。我发现最好的方法是在程序中标示大对象，然后单独分配管理，也不用复制，也不用跟其他数据一起管理。

最后一个关于数据拷贝的观点：不要过度优化。我看到过为了避免数据拷贝导致代码更糟糕的例子，比如强制上下文切换或者打断一个大的 I/O 请求。数据拷贝是昂贵的，当你觉得需要优化性能时确实应该优先考虑它，但是要有一个度，如果为了避免很少的数据拷贝导致代码复杂了一倍，这是得不偿失的。

上下文切换

对比每个人都知道数据拷贝是糟糕的，我非常惊讶的发现人们对于上下文切换消耗的性能的忽视。在我的经验中，上下文切换会导致比数据拷贝更加的性能暴跌，系统开始花费大量的时间从一个线程切换到另一个而不是做一些具体的工作。惊奇的事情就是，在某种层面，导致过度上下文切换的原因是显而易见的。第一种情况就是工作线程数量大于处理器数量。随着线程数比处理器数的提高，上下文切换的次数也在提升，如果幸运的话这是线性的，但是通常是指数的。这个简单事实解释了为了每个连接都新建一个线程的设计为什么可扩展性很差。可扩展系统的唯一现实选择是限制活动线程数量，使其小于或者等于处理器数量。这种方法的一个流行变体是只使用一个线程，虽然这种方法确实避免了上下文抖动，也避免了使用锁，同时也无法利用多核的能力来达到更高的吞吐量，因此也不是一个合理方法，除非程序无法达到 CPU 限制（通常因为网络 I/O 限制）。

线程较少的程序需要找到一个方法使得一个线程可以处理多个连接。通常需要一个“前端”使用 select/poll, asynchronous I/O, signals or completion ports, 背后使用事件驱动结构。很多“宗教战争”已经打响，同时会持续打下去，为了争论哪种“前端” API 是最佳的。Dan Kegel 的 C10K 文章是一个很好的材料。个人来讲，我认为 select/poll 和 signal 很丑陋，所以我更喜欢使用 AIO 或者 completion port，但是这并不重要。他们都可以工作的很好（可能除了 select），不需要做太多的事情来影响“前端”。

多线程事件服务最简单的概念模型核心存在一个队列，请求被一个或者多个 listener 线程监听然后放到队列里，然后一个或者多个 worker 线程会从队列获取请求然后处理。概念上这是个好模型，但是人们经常以错误方式实现代码！因为第二种造成上下文切换的情况是在线程间迁移任务。有些人甚至通过要求原始线程来响应请求加剧这个错误--保证每个请求存在两次上下文切换。使用“对称”方法很重要，这种方法可以，给定线程可以从 listener 线程到 worker 线程再到 listener 线程而不需要切换上下文。这是否设计划分线程之间谁为 listener 还是整个线程池轮训作为 listener 并不重要。

通常，不可能知道在未来某一时刻有多少线程处于活动状态。毕竟，请求可以在任何时候收到任何连接，或者用于维护任务的“后台”线程可以选在在那个时刻唤醒。如果你不知道有多少线程处于活动状态，那么如何限制有多少处于活动状态？根据我的经验，最有效也是最简单的方法：使用计数信号量，每个线程在执行实际工作时都必须持有信号量。如果已经达到线程限制，每个 listen 线程在唤醒后可能发生一次上下文切换，然后阻塞在信号量，但是一旦所有 listen 线程都以这种方式阻塞，它们就不会继续竞争资源，直到某个 worker 线程退出，因此系统影响可以忽略不计。更重要的是，这种方法维护线程--大部分事件都在休眠，因此不计入活动线程--比大多数替代方案优雅。

一旦请求处理过程被划分为两个阶段（listener 和 worker）通过不同线程处理不同阶段，自然可以将处理过程划分为多余两个阶段。因此，在最简单的形式中，请求处理变成了在一个方向上的依次调用阶段，然后在另一个方向（回复）。但是事情可能会变得复杂。一个阶段可能表示涉及到不同阶段的两个处理路径之间的分叉，或者它可能生成一个回复而不是继续调用后续阶段。因此，每个阶段都需要能够为请求指定“接下来发生什么”。存在三种可能，由阶段函数返回值表示：

  • 请求需要传递到另一个阶段（返回值是ID 或者指针）
  • 请求已经完成（特定的 request done 返回值）
  • 请求被阻塞（特定 request blocked 返回值）。等于前面的情况，除了请求不会被释放然后会稍后继续在另一个线程处理。

请注意，在这个模型中，请求排队实在阶段内完成的，而不是在阶段之间。这避免了经常将请求放在后继阶段的队列中，然后立即调用后继阶段并再次将请求出队的常见愚蠢行为；我称之为大量的队列活动，锁定，毫无意义。

如果这种将复杂任务划分为多个较小的部分看起来很熟悉，因为这个方法很古老。这个方法源于 CAR 在 1978 年提出的 CSP 概念。然而，当 Hoare 创造术语 CSP 时，他的意思是抽象数学意义上的进程，并且 CSP 进程不需要与同名的操作系统实体关联。在我看来，在单个 OS 线程中通过类线程的协程实现 CSP 的常用方法给用户带来了并发的问题但是没有带来可扩展性。

Matt Welsh 的 SEDA 是现在更明智的发展方向的分阶段执行理念的例子。事实上，SEDA 是“正确服务器架构”的一个很好的例子，值得评论它的一些特征：

  • SEDA 的批处理倾向于一次通过一个阶段处理多个请求，而我的方法倾向于一次通过多个阶段处理单个请求
  • 在我看来，SEDA 的一个重大缺陷是每个阶段分配了单独的线程池，只有”后台“在阶段之间重新分配线程以响应负载。结果上面提到的两种上下文切换问题出现了
  • 在学术研究的背景下，在 Java 中实现 SEDA 可能是有意义的。不过在现实中，我认为这种选择可以说的不幸的。

内存分配

分配释放内存是非常常见的操作。同时有很多聪明的方法已经被发明出来作为一个通用的内存分配器。但是再多的聪明方案也无法弥补这样的事实，即这种普遍应用的分配器不可避免在某些情况下性能变得很差。因为对于如何避免系统的分配器的问题，我有三个建议。

建议一：预分配。我们都知道静态分配对于程序功能是糟糕的，但是还有很多形式的预分配是有益的。通常原因归结为这样的事实，一次分配优于多次分配，即使存在浪费。因此如果可以知道使用过程中不会超过 N 条，可以在程序开始申请 N 的有效空间。即使不是这种情况，在开始时预分配请求处理程序可能需要的所有空间可能也比根据需要每次申请空间可取；除了系统分配器可以一次分配多个连续空间的可能性外，也简化了错误恢复代码。如果内存比较紧缺，预分配可能不是一个好的方案，但是通常情况下这是个好选择。

建议二：对于经常分配释放的对象，使用后备列表。基本思路是将最近释放的对象放回后备列表而不是归还系统，如果很快又再次需要一个对象的空间，就不需要向系统申请内存，直接使用后备列表的内存即可。带来的额外好处就是可以实现从后备列表的转换，而不需要复杂的对象初始化过程。

通常不希望后备列表不受限制的增长，即使在程序空闲时也不归还给系统。因此，通常需要某种周期性的”清理器“任务来释放非活动对象，但是如果清理器引入了过度的锁机制和竞争，也是不可取的。因此一个好的折中方案是一个后备列表实际上分别锁定旧的和新的列表组成的系统。优先从新列表分配，然后从旧列表分配，然后系统分配是最后选择；对象总是归还到新的列表。清理器线程操作如下：

  1. lock 新和旧列表
  2. 保存旧列表的头
  3. 通过旧列表的头操作将原来的新列表挂上去
  4. unlock
  5. 释放旧列表的空闲对象

这种系统中的对象只会在一个清理器周期内不被需要才会被清理，但是总少于两个。最重要的是，清理器完成大部分工作时没有持有锁与常规线程竞争。理论上，相同方法可以推广到两阶段以上，但是我没有使用过。

使用后备列表的一个核心问题是列表指针会提高对象的大小。在我的经验中，大多数我使用后备列表的对象已经包含了列表指针，所有这可能是个无意义的点。即使后备列表需要额外的指针空间，也避免的调用系统分配器，是利大于弊的。

建议三：尽可能避免使用锁。锁竞争在分配内存上经常是个大消耗，即使使用后备列表。一个解决方案是使用私有的后备列表，这样不存在线程之间的竞争。比如，你可以给每个线程分配一个后备列表。因为处理器 cache 热点问题，每个处理器一个后备列表通常更好，但是只有线程不能被抢占时才有效。如有必要，私有后备列表可以与共享后备列表组合，以创建一个分配开销低的系统。 （译者注：jemalloc 的 arena）

锁竞争

众所周知，高效的锁方案很难设计。Scylla 是简单粗粒度锁，将可以或者应该并发的活动序列化，因此牺牲了性能和可扩展性；Charybdis 是复杂的细粒度锁，锁的空间和锁操作的时间再次削弱了性能。靠近 Scylla 的是死锁或者活锁，靠近 Charybdis 是竞态条件。在两者之间，存在很小的领域是高效正确的锁，或者有吗？因为锁会与程序的逻辑深度绑定，通常不可能设计一个通用的锁适配各种场景。这是人们为什么讨厌锁的原因，并且试图合理化他们的不可扩展的单线程方法。

几乎每个锁方案都以“一个锁定一切的大锁”开始，并希望性能不会太糟糕。当希望破灭时，总是这样的，大锁呗分解为更小的锁，然后继续祈祷，然后重复这个过程，直到性能够用。通常，每次迭代都会增加20-50%锁的复杂性和锁开销，换取5-10%锁竞争的减少。幸运的是，最终结果是性能获得提升，但是实际上性能反而下降也并不少见。设计者会摸不着头脑，“我把锁做的更细，为什么性能会变差？”

在我看来，事情变糟了，因为上述方法从根本上被误导了。将“解决方案空间”想像成山脉，高点代表好的方案，低点代表差的方案。问题是“一个大锁”的起点重视被各种山谷，马鞍，较小的山峰和死角与较高的山峰隔开。这是一个经典的全局优化问题，试图从这样的起点达到更高的山峰，只采取小步骤并且不下坡是行不通的。我们需要一种完全不同的方法接近高峰。

首先是做一个程序和锁的地图，该地图有两个轴：

  • 竖轴表示代码。如果你使用分阶段而不是分支的结构，你应该已经有一个划分，像是每个人都知道的 OSI 模型表示网络协议栈一样。
  • 横轴代表数据。每个阶段，每个请求都应该分配一个数据集，并且自己的资源与其他集分开。

现在你有一个表格了，每个 cell 表示在特定的处理过程中的特定数据集。重要的是下面的规则：两个请求不应该竞争除非他们在同一个处理过程和同一个数据集。如果你可以管理这些，你已经赢了一半争论。

一旦你定义了这个表格，每个类型的锁可以被标定，下一个目标是确保生成的点尽可能沿两个轴均匀分布。不幸的是，这部分依赖程序。你需要利用你对程序的了解像钻石切割机一样找到程序阶段和数据集的分界线。有时一开始就很明显，有时很难找到，但是回溯中更明显。将代码划分为多个阶段在程序设计时是比较复杂的，因此不太好给出具体建议，但是可以有一些划分数据集的建议：

  • 如果你的请求与数字，hash 或者事务 id 绑定，你可以很简单按照这些划分数据集
  • 有时，最好根据哪个数据集有最多的可用资源而不是请求的内在属性来动态将请求分配给数据集。把它想象成现代 CPU 中的多个整数单元，这些人对系统离散数据流的一两个事件有所了解
  • 通常确保每个阶段的数据集分配不同很有帮助，这样可以保证在一个阶段会竞争的请求在另一个阶段不会发生

如果你已经垂直和水平划分了你的锁空间，并确保锁活动均匀的分布在生成的 cell 中，你可以确定你的锁状态很好。不过还可以更进一步。你还记得小步方法吗，我们之前嘲笑过这种方法？它也有自己的位置，因为现在你在一个很好的点开始而不是糟糕的点。用比喻的术语来说，你可能在最高峰的斜坡，但可能不再山顶。现在是时候收集竞争统计信息，看看你需要做哪些改进，以不同方法拆分阶段和数据集，然后统计信息，持续迭代，直到你满意。如果你做到了，你可以在山顶欣赏风景了。

其他方面

上述我已经覆盖了服务设计中四个主要性能问题。当然还存在一些特定服务需要考虑的重要问题。大多数情况下，这些需要考虑你的平台和环境：

  • 你的存储子系统在大/小请求的性能如何？序列换对比随机？read-ahead vs write ahead 呢？
  • 你使用的网络协议性能如何？你可以通过设置参数或者 flag 获得更好的性能吗？你可以使用 TCP_CORK, MSG_PUSH 或者 Nagle-toggling trick 来避免小包吗？
  • 你的系统支持扩散读写吗（scatter/gatter I/O(readv/writev)）？使用这个可以提升性能，也可以减轻使用 buffer chain 的痛苦。
  • 你的 page size 是多少？你的 cache-line size 是多少？值得做一些对齐操作吗？你的系统调用或者上下文切换具体消耗是多少，有相关的其他东西吗？
  • 你的读写锁会造成饥饿吗？你的事件会造成惊群效应吗？你的睡眠/唤醒会有这样让人讨厌的行为吗（很常见）即当 X 唤醒 Y 时，即使 X 仍有事情要做，上下文切换到 Y 也会立即发生。

我确定我可以顺着这个脉络想到许多问题，你也可以。在特定情况下，可能不需要做什么，但是考虑一下也不失严谨。如果你不知道答案，你可以通过系统文档找到答案。如果没有文档，你可以写一个测试程序或者小的性能测试程序来自己找到答案，写这种程序是一项很有用的技能。如果你写的代码要运行在多平台，其中很多问题你应该抽象到每个平台库相关，然后支持特定功能的平台获得性能提升。

“知道答案”理论也适用于你的代码，搞清楚代码的高层抽象，然后在不同环境测试耗时。这与传统分析不一样，这是测量而不是实现，底层优化通常是最后的选择。