原文：Making the Tokio scheduler 10x faster

[译]10倍提升Tokio调度器的性能

我们一直在为Rust的异步运行时库Tokio进行下一个重大版本的努力。今天，调度器的完全重写作为一个PR提交了。结果是巨大的性能和延迟改进。一些基准测试显示了10倍的加速！一直不太清楚对于这种改进对于“全栈“使用案例的影响有多大，因此我们还测试了这些调度器改进对于Hyper和Tonic等使用案例的影响（剧透：效果非常好）。

为了准备开发新的调度器，我花了时间搜索有关调度器实现的资源。除了现有的实现之外，我没有找到太多相关资料。我还发现现有实现的源代码难以阅读。为了解决这个问题，我尽量使Tokio的新调度器实现尽可能清晰。我还写了这篇详细的文章来介绍调度器的实现，希望对其他处于类似开发位置的人有帮助。

文章从调度器设计的高级概述开始，包括抢占式调度器。然后详细介绍了新的Tokio调度器中所做的具体优化。

这些优化包括：

新的 std::future 任务系统
更好的运行队列
优化消息传递模式
任务窃取限制
减少跨线程同步
减少内存分配
减少原子引用计数

主要的主题是“减少”。毕竟， there is no code faster than no code.

这篇文章还介绍了对新调度器进行的测试。编写正确的并发、无锁代码非常困难。与其快速但有bug，尤其是与内存安全相关的bug，不如慢但正确。然而，最好的选择是既快速又正确，因此我们编写了一个名为loom的并发测试工具。

在开始之前，我想表达一下我的感激之情：

@withoutboats和其他致力于 Rust 的 async / await 功能的人。你做的非常出色。这是一个杀手级功能。
@cramertj 和其他设计 std::task 的人。与我们之前的相比，这是一个巨大的进步。另外，你那里的工作非常棒。
Buoyant，Linkerd 的开发者，更重要的是我的雇主。感谢您让我在这项工作上花费如此多的时间。需要服务网格的读者，请查看 Linkerd。它将很快包含本文中讨论的所有优点。
Go，拥有一个很棒的调度器实现。

先去喝杯咖啡，让自己舒服一点——这篇文章会很长。

调度器，它们是如何工作的？

调度器的作用是进行任务调度。一个应用程序被分解成工作单元，我们称之为任务。当任务能够取得进展时，它是可运行的；当任务在外部资源上被阻塞时，它不再可运行（或者处于空闲状态）。任务是相互独立的，因此任意数量的可运行任务可以并发执行。调度器负责执行处于运行状态的任务，直到它们转换回空闲状态。执行一个任务意味着分配CPU时间——这是一种给需要给任务分配的全局资源。

这篇文章讨论了用户空间调度器，即在操作系统线程上运行的调度器（这些线程又由内核空间调度器驱动）。Tokio调度器执行Rust的future，可以将其视为“异步绿色线程“。这是M:N线程模型，其中许多用户空间任务在少数操作系统线程上进行多路复用。

有很多不同的调度器建模方式，每种方式都有其优缺点。在最基本的层面上，调度器可以被建模为一个运行队列和一个处理器，处理器负责处理队列中的任务。处理器是在一个线程上运行的一段代码。以下是伪代码：

1
2
3

while let Some(task) = self.queue.pop() {
    task.run();
}

当任务变为可运行时，它被插入到运行队列中。

虽然可以设计一个系统，其中资源、任务和处理器都存在于单个线程上，但Tokio选择使用多个线程。我们生活在一个拥有多个CPU的世界。设计一个单线程的调度器将导致硬件利用不足。我们希望能够使用所有的CPU。有几种方法可以实现这一点：

多处理器共用一个全局运行队列
多处理器，每个处理器都有自己的运行队列

多处理器共用一个全局运行队列

在这个模型中，有一个单一的全局运行队列。当任务变为可运行状态时，它们被推送到队列的尾部。有多个处理器，每个处理器在单独的线程上运行。每个处理器从队列的头部弹出任务，如果没有任务可用，则阻塞线程。

运行队列必须支持多个生产者和多个消费者。常用的算法是一种侵入式链表。侵入式意味着任务结构包含指向运行队列中下一个任务的指针，而不是使用链表节点包装任务。这样，可以避免在推入和弹出操作中进行内存分配。可以使用无锁的推入操作，但弹出操作需要使用互斥锁^[1]来协调消费者。

[1]：从技术上讲，实现一个无锁的多消费者队列是可能的。然而，在实践中，为了正确避免锁的开销往往比使用互斥锁还要大。

这种方法在实现通用线程池时常被使用，因为它具有几个优势：

任务被公平地调度
实现相对简单，可以将现成的队列与上述所述的处理器循环配对使用

关于公平性的一点说明。调度公平性意味着任务按照先进先出的原则进行调度。首先转换为可运行状态的任务会被首先执行。通用调度器尽力保持公平性，但在某些情况下，比如使用分叉-合并来并行计算，唯一重要的因素是最终结果的计算速度，而不是每个子任务的公平性。

这种调度器模型有一个缺点。所有处理器都竞争队列的头部。对于通用线程池来说，通常这并不是一个致命问题。处理器执行任务所花费的时间远远超过从运行队列中弹出任务所花费的时间。当任务执行的时间较长时，队列竞争会减少。然而，Rust的异步任务在从运行队列中弹出后执行的时间非常短。在这种情况下，由于队列竞争带来的开销变得显著。

并发性和硬件与软件协同运行

为了使程序能够获得最佳的运行时性能，我们必须设计它以利用硬件的操作方式。“硬件与软件协同运行”（mechanical sympathy）这个术语是由马丁·汤普森（他的博客虽然已经不再更新，但仍包含许多相关知识）应用于软件领域的。

详细讨论现代硬件如何处理并发超出了本文的范围。从一个较高层面来看，硬件通过提供更多的CPU核心（我的笔记本有6个！）而不是提高速度来获得更高的性能。每个核心可以在极短的时间内执行大量的计算。相对而言，像缓存和内存访问这样的操作需要更长的时间。因此，为了使应用程序运行快速，我们必须最大化每个内存访问所执行的CPU指令数量。虽然编译器可以为我们做很多工作，但作为开发者，我们确实需要考虑诸如结构体布局和内存访问模式等因素。

当涉及到并发线程时，在并发变动发生在同一缓存行或请求顺序一致性之前，行为与单线程相似。之后，CPU的缓存一致性协议将开始工作，以确保每个CPU的缓存保持最新。

这一切都是显而易见的：尽量避免跨线程同步，因为它会导致性能下降。

多处理器，每个处理器都有自己的运行队列

另一种调度器模型是使用多个单线程调度器。每个处理器都有自己的运行队列，并且任务被固定到特定的处理器上。这样可以完全避免同步的问题。由于Rust的任务模型要求能够从任何线程中将任务入队，因此仍然需要一种线程安全的方式将任务注入调度器中。可以使用每个处理器的运行队列支持线程安全的推送操作（MPSC），或者每个处理器有两个运行队列：一个是非同步队列，另一个是线程安全队列。

这是Seastar所使用的策略。由于几乎完全避免了同步，这种策略可以非常快速。然而，它并非万能解决方案。除非工作负载完全均匀，否则某些处理器会变为空闲，而其他处理器则处于负载状态，导致资源未充分利用。这是因为任务被固定到特定的处理器上。当单个处理器上的一批任务被批量调度时，即使其他处理器处于空闲状态，该单个处理器也要负责处理这一批任务。

大多数“真实世界”的工作负载都不是均匀的。因此，通用调度器通常避免使用这种模型。

工作窃取调度器

工作窃取调度器基于分片调度器模型，并解决了资源未充分利用的问题。每个处理器维护自己的运行队列。可运行的任务被推送到当前处理器的运行队列中，处理器从本地运行队列中执行任务。然而，当一个处理器变为空闲时，它会检查兄弟处理器的运行队列，并尝试从它们那里窃取任务。只有当处理器无法从兄弟运行队列中获取任务时，它才会进入休眠状态。

在模型层面上，这是一种“两全其美”的方法。在负载下，处理器独立运行，避免了同步开销。在负载不均匀的情况下，调度器能够重新分配任务。由于这个特性，工作窃取调度器是Go、Erlang、Java等语言的选择。

这种方法的缺点是它更加复杂；运行队列算法必须支持窃取操作，并且需要一些跨处理器的同步来保持运行的平稳性。如果实现不正确，工作窃取模型的开销可能会超过所获得的好处。

考虑以下情况：处理器 A 当前正在运行一个任务，并且其运行队列为空。处理器 B 空闲，尝试窃取任务但失败，于是进入休眠状态。然后，处理器 A 正在执行的任务生成了 20 个新任务。目标是让处理器 B 唤醒并窃取其中的一些新生成任务。为了实现这一点，工作窃取调度器需要一些启发式算法，当处理器观察到队列中有新的任务时，它会向休眠的兄弟处理器发送信号。当然，这会引入额外的同步操作，因此必须将此操作最小化。

总结：

最小化同步是有益的
工作窃取是通用调度器的首选算法
每个处理器基本上是独立的，但在窃取任务时需要一些同步操作

Tokio 0.1 调度器

Tokio在2018年3月首次发布了其工作窃取调度器。这是基于一些假设的第一次尝试，但后来证明是不正确的。

首先，Tokio 0.1调度器假设如果处理器线程闲置一段时间，应该关闭它们。最初，该调度器旨在成为Rust futures的“通用”线程池执行器。当最初编写调度器时，Tokio还处于“tokio-core”的阶段。在那个时候，模型是基于I/O的任务将在与I/O选择器（epoll、kqueue、iocp等）共同运行的单个线程上执行。而更多的CPU绑定工作可以交给线程池处理。在这种情况下，活动线程的数量应该是灵活的，并且关闭闲置线程是有意义的。然而，模型转变为在工作窃取调度器上运行所有的异步任务，这种情况下，保持少量的线程一直活跃更加合理。

其次是它使用了crossbeam双端队列实现。这个实现是基于Chase-Lev deque的，但是出于下面描述的原因，它并不适合用于调度独立的异步任务。

第三点是实现过于复杂。部分原因是因为这是我第一次实现调度器。此外，我过于急于在代码路径中使用原子操作，而在这些情况下使用互斥锁会更好。一个重要的教训是，在许多情况下，互斥锁是最佳选择。

最后，原始实现中存在许多小的效率问题。Rust的异步模型在早期发生了重大变化，但库在这些年中保持了API的稳定性。这导致了一些累积的技术债务，现在需要加以偿还。

随着Tokio接近其第一个重大突破性发布，我们可以利用这些年来学到的经验来还清所有的技术债务。这是一个令人兴奋的时刻！

下一代 Tokio 调度器

现在是时候深入了解新调度器中发生的变化了。

新的任务系统

首先，需要强调一点，这并不是 Tokio 的一部分，但对于实现所获得的一些优势来说非常重要：这是由 Taylor Cramer 主要设计的std 中包含的新任务系统。该系统提供了调度器必须实现的钩子，以执行 Rust 异步任务，并且设计得非常出色。它比先前的版本更轻量且更灵活。

Waker结构体由资源持有，并用于发出任务可运行的信号并将其推入调度器的运行队列。在新的任务系统中，Waker 结构体的大小为两个指针宽度，而之前要大得多。缩小大小对于尽量减少复制 Waker 值的开销以及在结构体中占用更少空间非常重要，这样可以在缓存线中容纳更多关键数据。自定义虚函数表的设计使得可以进行许多优化，稍后将进行讨论。

更好的运行队列

运行队列是调度器的核心。因此，它可能是最关键的组件，需要正确地实现。原始的 Tokio 调度器使用了 crossbeam 的双端队列（deque）实现，它是单生产者、多消费者的双端队列。任务被推送到队列的一端，值则从另一端弹出。大部分情况下，推送值的线程会进行弹出操作，然而，其他线程偶尔会通过弹出值的方式进行“窃取”。该双端队列由一个数组和一组跟踪头部和尾部的索引组成。当队列已满时，向其推送值将导致存储空间的增长。这将分配一个新的、更大的数组，并将值移动到新的存储中。

队列的动态增长能力带来了复杂性和开销成本。在推送和弹出操作中必须考虑到这种增长。此外，在增长时，释放原始数组也带来了额外的困难。在垃圾回收语言中，旧数组会超出作用域，并最终由垃圾回收器释放。然而，Rust 并不带有垃圾回收器。这意味着我们需要负责释放数组，但是线程可能正在同时访问内存。Crossbeam 的解决方案是使用基于 epoch 的回收策略。虽然不是非常昂贵，但它确实在热点路径上增加了不小的开销。每个操作现在必须在进入和退出临界区时发出原子 RMW（读-修改-写）操作，以向其他线程发出信号，表明内存正在使用中，并避免释放。

由于增长运行队列的成本，值得研究是否真的需要增长队列。这个问题促使了调度器的重写。新调度器的策略是使用每个进程固定大小的队列。当队列已满时，不会再增长本地队列，而是将任务推送到一个全局的、多消费者、多生产者的队列中。处理器需要偶尔检查这个全局队列，但频率比本地队列要低得多。

早期的实验使用有界的多生产者多消费者队列替换了crossbeam队列，但由于push和pop操作都需要进行大量的同步，这并没有带来太多的改进。关于工作窃取的使用情况，需要记住的一点是，在有负载的情况下，队列几乎没有争用，因为每个处理器只访问自己的队列。

在这个阶段，我选择更仔细地阅读Go的源代码，并发现他们使用了一个固定大小的单生产者、多消费者队列。这个队列令人印象深刻的地方在于它的工作所需的同步非常少。于是，我决定将这个算法适应到Tokio调度器中，并进行了一些修改。值得注意的是，Go实现在其原子操作中使用了顺序一致性（根据我对Go的有限了解）。在Tokio调度器中实现的版本还减少了一些在不太频繁的代码路径中的复制操作。

队列的实现是一个循环缓冲区，使用数组来存储值。原子整数用于跟踪头部和尾部的位置。

struct Queue {
    /// Concurrently updated by many threads.
    /// 由许多线程同时更新。
    head: AtomicU32,

    /// Only updated by producer thread but read by many threads.
    /// 仅由生产者线程更新，但被许多线程读取。
    tail: AtomicU32,

    /// Masks the head / tail position value to obtain the index in the buffer.
    /// 通过掩码对头部/尾部位置值进行处理，以获取在缓冲区中的索引。
    mask: usize,

    /// Stores the tasks.
    /// 存储任务。
    buffer: Box<[MaybeUninit<Task>]>,
}

将任务推入队列是由单个线程完成的：

loop {
    let head = self.head.load(Acquire);

    // safety: this is the **only** thread that updates this cell.
    // 安全的：这是唯一更新此单元的线程。
    let tail = self.tail.unsync_load();
    
    // 判断队列是否已满
    if tail.wrapping_sub(head) < self.buffer.len() as u32 {
        // Map the position to a slot index.
        // 将位置映射到slot索引。
        let idx = tail as usize & self.mask;

        // Don't drop the previous value in `buffer[idx]` because
        // it is uninitialized memory.
        // 不要丢弃`buffer[idx]`中的先前值，因为它是未初始化的内存。
        self.buffer[idx].as_mut_ptr().write(task);

        // Make the task available
        // 使任务可用
        self.tail.store(tail.wrapping_add(1), Release);

        return;
    }

    // The local buffer is full. Push a batch of work to the global
    // queue.
    // 本地缓冲区已满。将一批工作推送到全局队列中。
    match self.push_overflow(task, head, tail, global) {
        Ok(_) => return,
        // Lost the race, try again
        // 竞争失败，重试。
        Err(v) => task = v,
    }
}

请注意，在这个push函数中，仅有一个带有Acquire顺序的加载操作和一个带有Release顺序的存储操作。没有读-修改-写操作（compare_and_swap、fetch_and等），也没有顺序一致性。这很重要，因为在x86芯片上，所有加载/存储操作本身就是“原子”的。因此，在CPU级别上，该函数没有同步操作。使用原子操作会影响编译器，因为它会阻止某些优化，但仅此而已。第一个load操作很可能可以安全地使用Relaxed顺序，但在切换后没有可衡量的收益。

当队列已满时，将调用push_overflow函数。该函数将本地队列中一半的任务移动到全局队列中。全局队列是一个由互斥锁保护的侵入式链表。被移动到全局队列的任务首先被链接在一起，然后获取互斥锁，并通过更新全局队列的尾指针将所有任务插入其中。这样可以保持关键部分的长度较小。

如果您熟悉原子内存顺序的细节，您可能会注意到上述push函数存在潜在的“问题“。使用Acquire顺序的原子load操作非常弱。它可能返回过期的值，即并发的窃取操作可能已经增加了self.head的值，但执行push操作的线程在缓存中有一个旧值，因此它没有注意到窃取操作。这对算法的正确性并没有问题。在push的快速路径中，我们只关心本地运行队列是否已满。考虑到当前线程是唯一可以将任务推入运行队列的线程，过期的load将导致看到的运行队列比实际更满。它可能错误地确定队列已满并进入push_overflow函数，但此函数包含了更强的原子操作。如果push_overflow确定队列实际上没有满，它将返回一个Err，并重新尝试push操作。这是push_overflow将运行队列的一半移动到全局队列的另一个原因。通过移动一半的队列，“运行队列为空“的误报发生的频率要少得多。

本地的出队操作（由拥有队列的处理器执行）也是轻量级的：

loop {
    let head = self.head.load(Acquire);

    // safety: this is the **only** thread that updates this cell.
    // 安全：这是唯一一个更新此单元的线程。
    let tail = self.tail.unsync_load();

    if head == tail {
        // queue is empty
        // 队列为空
        return None;
    }

    // Map the head position to a slot index.
    // 将位置映射到slot索引。
    let idx = head as usize & self.mask;

    let task = self.buffer[idx].as_ptr().read();

    // Attempt to claim the task read above.
    // 尝试获取上面读取的任务。
    let actual = self
        .head
        .compare_and_swap(head, head.wrapping_add(1), Release);

    if actual == head {
        return Some(task.assume_init());
    }
}

在这个函数中，有一个原子加载操作和一个带有释放内存顺序的 compare_and_swap 。主要开销来自 compare_and_swap 。

steal函数与pop函数类似，但是需要对self.tail进行原子加载。与push_overflow类似，窃取操作将尝试获取队列的一半而不是单个任务。这具有一些很好的特性，我们稍后会详细讨论。

最后还有一个缺失的部分，那就是消费全局队列。该队列用于处理处理器本地队列的溢出，以及从非处理器线程向调度器提交任务。如果处理器负载较重，即本地运行队列中有任务，处理器将在执行本地队列中的大约60个任务后尝试从全局队列中弹出任务。它还会在处于“搜索“状态时检查全局队列，下面将对此进行描述。

优化消息传递模式

使用Tokio编写的应用通常采用许多小型、独立的任务进行建模。这些任务之间将使用消息传递进行通信。这种模式类似于其他语言，如Go和Erlang。鉴于这种模式的普遍性，调度器尝试对其进行优化是很有意义的。

假设有任务A和任务B。任务A当前正在执行并通过一个通道向任务B发送消息。通道是任务B当前被阻塞在上面的资源，因此发送消息的操作将导致任务B转换为可运行状态，并将其推入当前处理器的运行队列。处理器然后将从运行队列中弹出下一个任务，执行它，并重复此过程直到达到任务B。

问题在于发送消息和任务B执行之间可能存在显着的延迟。此外，当消息发送时，“热“数据（例如消息）存储在CPU的缓存中，但是在任务B被调度时，相关的缓存很可能已经被清除。

为了解决这个问题，新的Tokio调度器实现了一种优化（也在Go和Kotlin的调度器中找到）。当一个任务转换为可运行状态时，不是将其推送到运行队列的末尾，而是将其存储在一个特殊的“下一个任务“槽中。处理器在检查运行队列之前总是先检查这个槽。当将一个任务插入到这个槽中时，如果槽中已经有一个任务，旧的任务将被从槽中移除并推送到运行队列的末尾。在消息传递的情况下，这会使接收消息的任务被安排为下一个要运行的任务。

任务窃取限制

在工作窃取调度器中，当一个处理器的运行队列为空时，该处理器将尝试从兄弟处理器中窃取任务。为此，会随机选择一个兄弟处理器作为起始点，然后在该兄弟处理器上执行窃取操作。如果没有找到任务，就尝试下一个兄弟处理器，直到找到任务为止。

实际上，当许多处理器同时完成对其运行队列的处理是很常见的情况。这种情况通常发生在一批工作到达时（例如当 epoll 被轮询以获取套接字准备就绪状态）。处理器被唤醒，获取任务并执行它们，然后完成任务。这导致所有处理器在同一时间尝试进行窃取，也就是说有许多线程试图访问相同的队列。这会产生竞争。随机选择起始点有助于减少竞争，但竞争仍然很严重。

为了解决这个问题，新的调度器限制了执行窃取操作的并发处理器的数量。我们将处理器尝试进行窃取的状态称为“搜索工作“，简称为“搜索“状态（稍后会详细介绍）。这个优化通过使用一个原子整数来实现，处理器在开始搜索时递增该整数，在退出搜索状态时递减。最大搜索者数是总处理器数的一半。然而，这个限制是粗略的，而这是可以接受的。我们不需要对搜索者的数量有严格的限制，只需要一个节流机制。我们在精确性和算法效率之间进行了权衡。

一旦进入搜索状态，处理器会尝试从兄弟工作线程那里进行窃取，并检查全局队列。

减少跨线程同步

兄弟通知是工作窃取调度器的另一个关键部分。这是处理器在观察到新任务时通知兄弟处理器的过程。如果兄弟处理器处于休眠状态，它会被唤醒并窃取任务。通知操作还有另一个关键的责任。回想一下，队列算法使用了弱的原子内存顺序（Acquire / Release）。由于原子内存顺序的工作方式，如果没有额外的同步，无法保证兄弟处理器能够看到队列中的任务以进行窃取。因此，通知操作还负责建立必要的同步，以便兄弟处理器能够看到任务并进行窃取。这些要求使得通知操作变得昂贵。目标是尽可能少地执行通知操作，同时确保不会导致CPU利用率不足，即处理器拥有任务但兄弟处理器无法窃取任务。过于积极的通知会导致惊群效应（Thundering Herd^[2]）问题。

[2]：译者注，举一个很简单的例子，当你往一群鸽子中间扔一粒谷子，所有的各自都被惊动前来抢夺这粒食物，但是最终注定只可能有一个鸽子满意的抢到食物，没有抢到的鸽子只好回去继续睡觉，等待下一粒谷子的到来。这里鸽子表示进程（线程），那粒谷子就是等待处理的事件。

原始的Tokio调度器对通知采取了一种简单的方法。每当有新的任务被推入运行队列时，会通知一个处理器。当一个处理器被通知并在唤醒时发现一个任务时，它会继续通知另一个处理器。这个逻辑很快导致所有处理器都被唤醒并开始搜索任务（引发争用）。很多时候，大多数处理器都找不到任务并重新进入休眠状态。

新的调度器在这方面有了显著改进，它借鉴了Go调度器中使用的相同技术。通知的时机与之前的调度器相同，但是只有在没有处理器处于搜索状态时才会进行通知（参见前面的部分）。当一个处理器被通知时，它会立即转换到搜索状态。当处于搜索状态的处理器发现新的任务时，它首先退出搜索状态，然后再通知另一个处理器。

这种逻辑的效果是限制处理器唤醒的速度。如果一批任务同时被调度（例如，当 epoll 轮询套接字准备就绪时），第一个任务将会通知一个处理器。该处理器现在处于搜索状态。批次中的其余调度任务不会通知处理器，因为至少有一个处理器处于搜索状态。被通知的处理器将从批次中窃取一半的任务，并通知另一个处理器。第三个处理器将被唤醒，从第一或第二个处理器中获取任务并窃取其中的一半。这样可以平滑地增加处理器的数量，并快速地平衡任务负载。

减少内存分配

新的Tokio调度器每个生成的任务只需要进行一次内存分配，而旧的调度器则需要两次分配。以前，Task结构大致如下：

struct Task {
    /// All state needed to manage the task
    /// 用于管理任务的所有状态
    state: TaskState,

    /// The logic to run is represented as a future trait object.
    /// 执行逻辑表示为一个Future的特征对象。
    future: Box<dyn Future<Output = ()>>,
}

Task结构体也会被分配在一个Box中。长期以来，这一点一直是我想要解决的问题（我在2014年首次尝试解决这个问题）。自从旧的Tokio调度器以来，有两件事情发生了变化。首先，std::alloc稳定了。其次，Future任务系统转换为显式的vtable策略。这两个变化是最终消除每个任务双重分配低效性所需的两个缺失的部分。

现在，Task结构表示为：

struct Task<T> {
    header: Header,
    future: T,
    trailer: Trailer,
}

Header和Trailer都是用于支持任务的状态，但它们分为“热”数据（header）和“冷”数据（trailer），也就是经常访问的数据和很少使用的数据。热数据放置在结构体的开头，并尽可能保持较小的大小。当CPU解引用任务指针时，它会一次加载一个缓存行大小的数据（介于64到128字节之间）。我们希望这些数据尽可能相关。

减少原子引用计数

最后一个我们将讨论的优化是新调度器如何减少所需的原子引用计数数量。任务结构体存在许多未决的引用：调度器和每个waker都持有一个句柄。管理这些内存的常见方法是使用原子引用计数。这种策略需要在每次克隆引用时进行原子操作，并在每次释放引用时进行原子操作。当最后一个引用超出范围时，内存将被释放。

在旧的 Tokio 调度器中，每个waker都持有对任务句柄的计数引用。大致如下：

struct Waker {
    task: Arc<Task>,
}

impl Waker {
    fn wake(&self) {
        let task = self.task.clone();
        task.scheduler.schedule(task);
    }
}

当任务被唤醒时，引用会被克隆（原子递增）。然后，引用会被推入运行队列。当处理器接收到任务并执行完毕后，会丢弃引用，导致原子递减。这些原子操作会累积起来。

这个问题先前已经被std::future任务系统的设计者们所发现。观察到，在调用Waker::wake时，原始的waker引用通常不再需要。这允许在将任务推入运行队列时重新使用原子引用计数。std::future任务系统现在包括两个“wake“ API：

wake ，需要 self
wake_by_ref 需要 &self

这个API设计推动调用者使用wake，避免了原子递增操作。现在的实现变成了：

impl Waker {
    fn wake(self) {
        task.scheduler.schedule(self.task);
    }

    fn wake_by_ref(&self) {
        let task = self.task.clone();
        task.scheduler.schedule(task);
    }
}

这种方式避免了额外的引用计数开销，只有在可以获取唤醒器所有权的情况下才能实现。根据我的经验，几乎总是希望使用&self进行唤醒。使用self进行唤醒可以防止唤醒器的重复使用（在资源发送多个值的情况下很有用，例如通道、套接字等），同时在需要self的情况下实现线程安全的唤醒更加困难（有关详细信息将在另一篇文章中介绍）。

新的调度器通过避免在wake_by_ref中进行原子增加操作，从而完全规避了“使用self唤醒”的问题，使其与wake(self)一样高效。为了实现这一点，调度器维护了一个包含所有当前活动任务（尚未完成）的列表。该列表代表了将任务推入运行队列所需的引用计数。

这种优化的困难之处在于确保调度器不会在可以确保任务不再被推入运行队列之前从列表中删除任何任务。关于如何管理这个问题的具体细节超出了本文的范围，但我建议您在源代码中进一步研究这个问题。

使用 Loom 无畏（不安全）并发

编写正确的、并发的、无锁的代码确实非常困难。缓慢而正确比快速而错误要好，特别是如果这些错误与内存安全有关。最好的选择是快速和正确。新调度器进行了一些非常激进的优化，避免使用大多数std类型，以便编写更专门的版本。在新调度器中存在相当多的unsafe代码。

有几种测试并发代码的方法。一种方法是让用户为您进行测试和调试（确实是一个吸引人的选项）。另一种方法是编写在循环中运行的单元测试，并希望能捕捉到错误。也可以尝试使用 ThreadSanitizer (TSAN)。当然，如果这样能捕捉到错误，那么很难重新复现该错误，除非再次运行循环测试。此外，要运行多长时间的循环测试呢？十秒钟？十分钟？十天？这曾经是使用 Rust 测试并发代码的状态。

我们并不认为现状是可以接受的。我们希望在发布代码时能够获得信心（或者尽可能获得信心）——尤其是对于并发的、无锁的代码。可靠性是Tokio用户期望的特性之一。

为了满足我们的需求，我们开发了一个名为 Loom 的新工具。Loom 是一个并发代码的置换测试工具。测试代码编写方式与普通测试相同，但在使用 Loom 执行时，它会以多种方式运行测试，对测试能够在多线程环境中遇到的所有可能的执行和行为进行置换。它还验证正确的内存访问、内存释放等操作。

作为一个例子，这里是一个用于新调度器的 Loom 测试：

#[test]
fn multi_spawn() {
    loom::model(|| {
        let pool = ThreadPool::new();

        let c1 = Arc::new(AtomicUsize::new(0));

        let (tx, rx) = oneshot::channel();
        let tx1 = Arc::new(Mutex::new(Some(tx)));

        // Spawn a task
        let c2 = c1.clone();
        let tx2 = tx1.clone();
        pool.spawn(async move {
            spawn(async move {
                if 1 == c1.fetch_add(1, Relaxed) {
                    tx1.lock().unwrap().take().unwrap().send(());
                }
            });
        });

        // Spawn a second task
        pool.spawn(async move {
            spawn(async move {
                if 1 == c2.fetch_add(1, Relaxed) {
                    tx2.lock().unwrap().take().unwrap().send(());
                }
            });
        });

        rx.recv();
    });
}

代码看起来很正常，但是在 loom::model 块内部的代码将会运行非常多次（可能达到百万次），每次运行都会略微变化行为。线程的确切顺序也会每次不同。此外，对于每个原子操作，Loom 将尝试 C++11 内存模型允许的所有不同行为。回想一下之前提到的原子加载操作（Acquire）相对较弱，可能返回过期的值。Loom 测试将尝试加载的每个可能值。

这意味着 Loom 能够全面测试并发代码的不同行为和内存访问模式，以验证其正确性和可靠性。通过遍历不同的执行路径和内存模型行为，Loom 提供了一种可靠的测试方法，以确保代码在各种情况下都能正确运行。

loom 是在处理新调度程序时使用的非常宝贵的工具。它捕获了其他单元测试、手动测试和压力测试遗漏的 10 多个错误。

敏锐的读者可能会对“测试所有可能的排列“的说法提出质疑，这种质疑是正确的。简单的行为排列会导致阶乘级别的组合爆炸，任何非平凡的测试都将无法完成。这个问题已经被研究了多年，存在许多算法来管理组合爆炸。Loom 的核心算法基于动态部分顺序约简。该算法能够剪除导致相同执行的排列。即使如此，状态空间可能会变得过大，在合理的时间内（几分钟）无法完成。Loom 还允许使用有界的动态部分顺序约简来限制搜索空间。

总而言之，由于使用 Loom 进行了大量测试，我对调度程序的正确性更有信心。

优化结果

现在，我们已经了解了调度器的概念以及新的Tokio调度器是如何取得巨大性能提升的。然而，由于新的调度器还很新，尚未进行大规模的实际测试。以下是我们目前所了解的情况。

首先，新的调度器在微基准测试中表现得更快。以下是新调度器在一些基准测试中的改进情况：

Old scheduler

test chained_spawn ... bench:   2,019,796 ns/iter (+/- 302,168)
test ping_pong     ... bench:   1,279,948 ns/iter (+/- 154,365)
test spawn_many    ... bench:  10,283,608 ns/iter (+/- 1,284,275)
test yield_many    ... bench:  21,450,748 ns/iter (+/- 1,201,337)

New scheduler

test chained_spawn ... bench:     168,854 ns/iter (+/- 8,339)
test ping_pong     ... bench:     562,659 ns/iter (+/- 34,410)
test spawn_many    ... bench:   7,320,737 ns/iter (+/- 264,620)
test yield_many    ... bench:  14,638,563 ns/iter (+/- 1,573,678)

benchmarks包括：

chained_spawn 测试递归地生成一个新任务，即生成一个任务，生成一个任务，生成一个任务，….
ping_pong 分配一个 oneshot 通道，生成一个在该通道上发送消息的任务。原始任务等待接收消息。这是最接近“真实世界”的基准
spawn_many 测试将任务注入调度器，即从调度器上下文外部生成任务
yield_many 测试唤醒自己的任务

从旧调度器到新调度器的改进非常令人印象深刻。然而，这如何延续到“现实世界”。很难准确地说，但我确实尝试过使用新的调度器运行 Hyper 基准测试。

这是使用 wrk -t1 -c50 -d10 进行基准测试的“hello world”Hyper 服务器：

Old scheduler

Running 10s test @ http://127.0.0.1:3000
  1 threads and 50 connections
  Thread Stats   Avg      Stdev     Max   +/- Stdev
    Latency   371.53us   99.05us   1.97ms   60.53%
    Req/Sec   114.61k     8.45k  133.85k    67.00%
  1139307 requests in 10.00s, 95.61MB read
Requests/sec: 113923.19
Transfer/sec:      9.56MB

New scheduler

Running 10s test @ http://127.0.0.1:3000
  1 threads and 50 connections
  Thread Stats   Avg      Stdev     Max   +/- Stdev
    Latency   275.05us   69.81us   1.09ms   73.57%
    Req/Sec   153.17k    10.68k  171.51k    71.00%
  1522671 requests in 10.00s, 127.79MB read
Requests/sec: 152258.70
Transfer/sec:     12.78MB

这一切使得每秒请求数增加了34％，仅仅通过切换调度器！当我第一次看到这个结果时，我感到非常高兴。最初，我预计增长大约为5％至10％，所以这个结果远超出了我的期望。然后，我感到有些难过，因为这也意味着旧的Tokio调度器并不那么出色，但没关系。接着，我想起Hyper已经在TechEmpower基准测试中名列前茅。我非常期待新的调度器将如何影响这些排名。

Tonic，一个gRPC客户端和服务器，获得了约10％的加速，这是相当令人印象深刻的成果，尤其考虑到Tonic尚未进行高度优化。