I/O 调度：CFQ → mq-deadline → BFQ → kyber

打开你 Linux 服务器的终端，执行：

cat /sys/block/nvme0n1/queue/scheduler

你会看到类似 [none] mq-deadline kyber bfq 的输出。方括号里的就是当前激活的 I/O 调度器。如果是 NVMe SSD 并且内核版本够新，大概率是 none——意思是不使用任何调度器。

这很反直觉。操作系统教科书花了整整一章讲 I/O 调度的电梯算法、SCAN、C-SCAN、LOOK。然后 NVMe 出来了，说：不需要了。

但事情没这么简单。none 适用于 NVMe，却不适用于 HDD、SATA SSD、eMMC、UFS。理解”什么时候需要调度，什么时候不需要”，需要先理解 I/O 调度器存在的根本原因——以及这个原因如何随硬件演进而消失。

下面这张架构图展示了从单队列到多队列的根本变革：

一、历史背景：单队列时代为什么需要 I/O 调度

机械硬盘的物理限制

HDD 的读写需要磁头移动到目标磁道（寻道，seek）并等待盘片旋转到目标扇区（旋转延迟，rotational latency）。寻道时间通常 3-10ms，旋转延迟（7200 RPM 盘片）平均 4.2ms。

这意味着一次随机 I/O 需要 7-15ms。如果应用发出 1000 个随机读请求，按 FIFO 顺序执行需要 7-15 秒。但如果把这些请求按磁道号排序（类似电梯），磁头只需要从外到内扫描一次，寻道时间可以从 7ms/次降到 0.5ms/次，总时间降到约 0.5 秒。

I/O 调度器存在的根本原因是弥补机械硬盘”随机访问昂贵、顺序访问廉价”的物理特性。

早期电梯算法的演变

最原始的做法是 FIFO，但 FIFO 在 HDD 上性能灾难般地差。于是出现了一系列经典算法：

• SSTF（Shortest Seek Time First）：每次选离当前磁头最近的请求，吞吐高但可能饿死远端请求。
• SCAN（电梯算法）：磁头从一端扫到另一端，然后反向扫描。消除饥饿，但两端请求等待时间不均。
• C-SCAN（Circular SCAN）：磁头只单向扫描，到底后直接跳回起点。等待时间更均匀。
• LOOK / C-LOOK：SCAN/C-SCAN 的实际实现——磁头不需要真的走到盘片边缘，到最远请求处就可以折返。

这些算法解决了”排序”问题，但没有解决”公平性”和”延迟保证”问题。一个大文件的顺序读可以独占磁头数秒钟，让其他进程的小 I/O 请求饿死。Linux 需要更精巧的调度器。

Linux 单队列 I/O 栈（kernel < 3.13）

在 blk-mq 出现之前，Linux 的块设备层是单队列架构：

应用层 → 文件系统 → 页缓存 → 通用块层(generic_make_request)
                                    ↓
                            单请求队列 (request_queue)
                                    ↑
                            一把全局自旋锁 (queue_lock)
                                    ↓
                            I/O 调度器 (elevator)
                                    ↓
                            块设备驱动 → 硬件

所有 CPU 核心提交的 I/O 请求，无论来自哪个进程、哪个文件系统，都必须获取同一把 queue_lock 才能进入请求队列。在双核、四核时代这不是问题；但到了 16 核、32 核甚至 64 核的服务器上，锁争用本身就成了性能瓶颈——即使底层设备足够快，软件层也喂不饱它。

在这个单队列架构上，Linux 先后实现了三个经典调度器：noop、deadline、CFQ。

二、CFQ：完全公平队列调度

设计原理

CFQ（Completely Fair Queuing，Jens Axboe，2004-2006）是 Linux 2.6.18 到 5.0 之间的默认 I/O 调度器。它的核心目标是：在多进程共享磁盘时，保证每个进程获得公平的 I/O 带宽份额。

CFQ 的设计哲学直接借鉴了 CPU 调度器 CFS 的”完全公平”思想——每个进程应该获得与其权重成正比的 I/O 时间。

核心数据结构

CFQ 为每个提交 I/O 的进程（更准确地说，是每个 cfq_queue，由 cgroup + ionice 优先级 + 同步/异步方向共同决定）维护一个独立的请求队列。这些队列被组织在一棵红黑树中，按照”虚拟服务时间”排序，服务时间最少的队列优先被调度。

cfq_data (per-device)
├── service_tree[IDLE]    → 红黑树，存 idle 优先级的 cfq_queue
├── service_tree[BE]      → 红黑树，存 best-effort 优先级的 cfq_queue
├── service_tree[RT]      → 红黑树，存 real-time 优先级的 cfq_queue
│
├── cfq_queue (进程 A, BE/4, sync)
│   ├── sort_list: 按扇区号排序的请求链表
│   └── fifo_list: 按到达时间排序的请求链表
│
├── cfq_queue (进程 B, RT/2, sync)
│   ├── sort_list
│   └── fifo_list
│
└── cfq_queue (进程 C, IDLE, async)
    ├── sort_list
    └── fifo_list

时间片轮转

调度器轮流给每个活跃的 cfq_queue 分配一个时间片（默认同步队列 100ms，异步队列 40ms）。在时间片内，调度器只从该队列中取请求下发，队列内部的请求按扇区号排序以最大化顺序性。

时间片耗尽后，调度器切换到红黑树中下一个”虚拟服务时间最小”的队列。这保证了长期公平性——每个进程获得的磁盘时间与其 ionice 权重成正比。

ionice 优先级

CFQ 支持三个 I/O 优先级类别，通过 ionice 命令设置：

# 实时优先级（最高），级别 0-7
ionice -c 1 -n 0 dd if=/dev/sda of=/dev/null bs=1M

# 尽力优先级（默认），级别 0-7
ionice -c 2 -n 4 tar czf backup.tar.gz /data

# 空闲优先级（最低），只在没有其他 I/O 时才执行
ionice -c 3 find / -name "*.log" -delete

实时（RT）类别的队列总是先于尽力（BE）类别被调度，BE 先于空闲（IDLE）。同一类别内，级别数字越小优先级越高。IDLE 类别在高负载时可能几乎得不到磁盘时间。

同步队列与异步队列

CFQ 区分同步和异步 I/O：

• 同步 I/O：进程发出请求后阻塞等待结果（典型的 read() 调用）。每个进程有自己的同步队列。
• 异步 I/O：请求写入页缓存后进程立即返回，由内核后台刷盘。所有进程共享若干异步队列（按优先级划分）。

同步队列获得更多的时间片和更高的调度优先级，因为同步 I/O 直接影响进程响应时间。

预期调度（Anticipatory Scheduling）

CFQ 继承了 Anticipatory Scheduler 的核心思想：当一个进程的队列暂时为空时，不立即切换到下一个进程，而是等待一小段时间（默认约 8ms），“预期”该进程马上会发出下一个请求。

进程 A 的队列: [req1(sector 100), req2(sector 105), req3(sector 110)]
进程 B 的队列: [req4(sector 50000), req5(sector 50010)]
进程 C 的队列: [req6(sector 200), req7(sector 210)]

CFQ 时间片轮转:
  → A 的时间片: 处理 req1, req2, req3（连续扇区，很快）
  → A 的队列空了，等待 8ms（"预期" A 会发新请求）
  → 如果 A 在 8ms 内发了 req8(sector 115)，继续处理（避免了到 sector 50000 的寻道）
  → 超时，切换到 B
  → B 的时间片: 处理 req4, req5
  → 切换到 C
  → ...

在 HDD 上，这种预期等待非常值得——一次从 sector 110 到 sector 50000 的寻道需要约 8ms，如果等 8ms 能避免这次寻道，那就是净赚。但在 SSD 上，随机访问延迟只有 50-100us，等 8ms 是纯粹的浪费。

CFQ 为什么被淘汰

CFQ 在 Linux 5.0（2019 年 3 月）中被移除，原因有三：

1. SSD 普及：CFQ 的核心优化（预期调度、寻道最小化）在 SSD 上全部失效，反而增加延迟。
2. blk-mq 不兼容：CFQ 的设计强依赖单请求队列和全局锁，无法适配多队列架构。
3. 复杂度过高：CFQ 的代码超过 5000 行，维护成本巨大，而它的收益在现代硬件上越来越小。

CFQ 的死亡不是因为它设计得差——恰恰相反，它是 HDD 时代最精巧的调度器。它的死亡是因为它的核心假设（寻道昂贵）被硬件演进否定了。

三、deadline 调度器：简单即正义

设计哲学

Deadline 调度器（Jens Axboe，2002）的设计哲学与 CFQ 截然不同：不追求完全公平，只保证不饿死任何请求。

它的核心思想极其简洁：正常情况下按扇区号排序以最大化顺序性，但如果任何请求等待时间超过了截止时间（deadline），立即处理它。

四个队列

Deadline 维护四个队列：

读排序队列 (read_sort_list)  ← 按扇区号排序的红黑树
读 FIFO 队列 (read_fifo)      ← 按到达时间排序的链表
写排序队列 (write_sort_list)  ← 按扇区号排序的红黑树
写 FIFO 队列 (write_fifo)     ← 按到达时间排序的链表

每个请求同时存在于两个队列中：一个排序队列（用于顺序优化）和一个 FIFO 队列（用于超时检测）。

读写分离与截止时间

读请求的默认截止时间是 500ms，写请求是 5000ms。为什么差 10 倍？

• 读是同步的：进程调用 read() 后阻塞等待，读延迟直接等于用户感知的响应延迟。
• 写是异步的：数据先写入页缓存，write() 立即返回。真正写入磁盘是后台行为，用户感知不到。

因此，deadline 调度器在绝大多数时间优先处理读请求，只在写请求即将超过截止时间时才”插队”处理写请求。

批处理机制

Deadline 不是每次只取一个请求——它使用批处理（batching）。一旦决定处理某个方向（读或写）的请求，它会连续从该方向的排序队列中取出多个请求（默认 writes_starved = 2，即连续服务 2 批读后必须服务 1 批写），直到切换方向。

批处理的好处是减少读写切换的开销。在 HDD 上，从读模式切换到写模式需要磁头重新定位，批量处理同方向请求可以最大化顺序性。

饥饿避免

Deadline 的饥饿避免机制分两层：

1. FIFO 截止时间：任何请求等待时间超过截止时间（读 500ms、写 5s）时，立即被提升到最高优先级。这保证了最坏情况下的延迟上界。
2. 写饥饿计数器（writes_starved）：即使没有写请求超时，连续服务了 writes_starved 批读请求后，也必须切换到写请求。默认值为 2，即读写比例最多 2:1。

为什么简单反而好

Deadline 调度器的代码只有约 800 行，是 CFQ 的六分之一。但在绝大多数工作负载下，它的性能与 CFQ 相当甚至更好。原因：

1. 低开销：没有 per-process 队列、没有红黑树的频繁插入删除、没有预期等待逻辑。
2. 确定性：行为可预测——你知道最坏情况下读延迟不超过 500ms。
3. 适应性广：在 HDD 上提供足够的排序优化，在 SSD 上开销足够低。

这就是为什么 deadline 在 CFQ 被移除后成为了 HDD/SATA SSD 的默认推荐调度器。

四、noop/none：不调度才是最优解

noop（单队列时代）

noop 是最简单的调度器——一个 FIFO 队列加请求合并。如果两个相邻的请求访问连续的扇区，合并成一个大请求；除此之外不做任何排序或优先级处理。

在单队列时代，noop 适用于两个场景：

1. SSD：不需要寻道优化，排序是纯开销。
2. 虚拟机：底层宿主机已经有自己的 I/O 调度器，虚拟机里再调度一次是多余的（双重调度问题）。

none（多队列时代）

blk-mq 时代的 none 比单队列的 noop 更彻底——它连 FIFO 队列都省了。请求从 per-CPU 软件队列直接映射到硬件分发队列，中间不经过任何调度逻辑。

仍然保留的操作只有一个：请求合并（merge）。如果新请求的扇区范围与队列中已有请求相邻，合并成一个大请求。这是几乎无开销的优化，所以保留。

什么场景下 none 最优

# 检查设备是否为 NVMe
cat /sys/block/nvme0n1/queue/rotational
# 0 表示非旋转设备

# 检查当前队列深度
cat /sys/block/nvme0n1/queue/nr_requests
# NVMe 通常 1023 或更高

# 检查硬件队列数
ls /sys/block/nvme0n1/mq/ | wc -l
# NVMe 通常等于 CPU 核数

none 最优的条件：

• 设备本身有强大的内部调度逻辑（NVMe SSD 的 FTL）。
• 设备支持足够深的硬件队列（NVMe 的 64K 深度）。
• 不需要软件层面的公平性保证（单租户场景）。
• 延迟敏感，不能容忍调度器引入的额外延迟。

none 不够的场景

• 多租户/容器化：多个容器共享同一块 NVMe，某个容器的突发 I/O 可能饿死其他容器。需要 BFQ 或 cgroup I/O 控制。
• 读写混合负载：数据库同时有大量读查询和后台写入（compaction/checkpoint），需要 mq-deadline 保证读优先。
• tail latency 敏感：NVMe 在高队列深度下 P99 延迟可能飙升，需要 kyber 做流量控制。
• HDD：旋转设备上使用 none 意味着放弃寻道优化，性能灾难。

五、blk-mq 多队列架构：从单队列到多队列的根本变革

为什么单队列必须被替换

2013 年前后，硬件的发展让单队列架构的瓶颈暴露无遗：

• NVMe SSD 的出现：Intel DC P3600 等第一代数据中心 NVMe 能做到 100 万+ IOPS。但单队列的全局锁争用使得 Linux 块层在 32 核服务器上只能跑出 20 万 IOPS——80% 的性能被锁吃掉了。
• 多核 CPU 的普及：服务器从 4 核发展到 32 核、64 核甚至 128 核。每多一个核心，锁争用就多一分。
• NUMA 架构：跨 NUMA 节点的锁获取延迟特别高，进一步加剧瓶颈。

blk-mq 的两层队列设计

Jens Axboe 在 2013 年提出了 blk-mq（multi-queue block layer），在 Linux 3.13 合并。核心思想是两层队列：

第一层：软件暂存队列（Software Staging Queues / blk_mq_ctx）

• 每个 CPU 核心一个，无锁（每个 CPU 只访问自己的队列）。
• 应用提交的 bio 在这一层被转换为 request，并进行初步的请求合并。
• 数量 = CPU 核心数。

第二层：硬件分发队列（Hardware Dispatch Queues / blk_mq_hw_ctx / hctx）

• 与设备的硬件提交队列一一对应。
• NVMe 设备通常暴露与 CPU 核心数相同的硬件队列，所以软件队列和硬件队列可以 1:1 映射。
• SATA/SAS 设备通常只有 1 个硬件队列，所以多个软件队列映射到同一个硬件队列。

                         blk-mq 架构
    ┌─────────────────────────────────────────────────┐
    │                                                 │
    │  CPU 0        CPU 1        CPU 2       CPU N    │
    │    │            │            │           │      │
    │    v            v            v           v      │
    │ [sw_ctx_0]  [sw_ctx_1]  [sw_ctx_2]  [sw_ctx_N] │  ← 软件队列（无锁）
    │    │            │            │           │      │
    │    │     ┌──────┘    ┌──────┘           │      │
    │    v     v           v                  v      │
    │ [  hctx_0  ]    [  hctx_1  ]    [  hctx_M  ]  │  ← 硬件队列
    │    │                 │                  │      │
    └────┼─────────────────┼──────────────────┼──────┘
         v                 v                  v
    ┌─────────────────────────────────────────────┐
    │         NVMe Controller / SCSI HBA          │
    └─────────────────────────────────────────────┘

调度器在 blk-mq 中的位置

在 blk-mq 架构中，I/O 调度器是可选的，插入在软件队列和硬件队列之间：

1. 无调度器（none）：请求从软件队列直接进入硬件分发队列。路径最短，延迟最低。
2. 有调度器：调度器从软件队列中拉取请求，按自己的策略排序/合并/限流后，再送入硬件分发队列。

与单队列时代不同，blk-mq 的调度器不需要应对全局锁的问题——它只需要处理从多个软件队列汇聚来的请求流。

关键代码路径

一个 I/O 请求在 blk-mq 中的完整路径：

// 1. 应用发起 I/O
submit_bio(bio);

// 2. 进入通用块层
blk_mq_submit_bio(bio);
    // 2a. 尝试请求合并（plug list / 调度器队列）
    // 2b. 分配 request 结构体
    blk_mq_get_request();
    // 2c. 获取当前 CPU 的软件队列
    ctx = blk_mq_get_ctx(cpu);

// 3. 如果有调度器
if (q->elevator) {
    // 插入调度器内部队列
    elevator_insert(rq);
    // 调度器决定何时、以什么顺序下发
    blk_mq_sched_dispatch_requests(hctx);
}

// 4. 如果没有调度器（none）
else {
    // 直接插入 hctx 的 dispatch list
    blk_mq_try_issue_directly(hctx, rq);
}

// 5. 硬件队列下发到设备
hctx->ops->queue_rq(hctx, rq);

blk-mq 带来的性能提升

在同一台 32 核服务器 + NVMe SSD 上：

六倍的 IOPS 提升，大部分来自消除锁争用。

六、mq-deadline：多队列版 deadline

从 deadline 到 mq-deadline

mq-deadline 是经典 deadline 调度器在 blk-mq 框架下的重新实现。核心算法不变——读写分离队列、截止时间保证、扇区排序——但实现细节有显著差异。

与单队列 deadline 的关键差异

1. 请求来源变化

单队列 deadline 从全局请求队列中取请求；mq-deadline 需要从多个 per-CPU 软件队列中”拉取”请求到自己的内部排序队列。

// mq-deadline 的 insert 回调
static void dd_insert_request(struct blk_mq_hw_ctx *hctx,
                              struct request *rq,
                              bool at_head)
{
    struct deadline_data *dd = hctx->queue->elevator->elevator_data;
    const int data_dir = rq_data_dir(rq);

    // 插入排序队列（红黑树，按扇区号）
    deadline_add_rq_rb(&dd->sort_list[data_dir], rq);

    // 同时插入 FIFO 队列（链表，按到达时间）
    // 设置截止时间 = 当前时间 + fifo_expire
    rq->fifo_time = jiffies + dd->fifo_expire[data_dir];
    list_add_tail(&rq->queuelist, &dd->fifo_list[data_dir]);
}

2. 锁粒度不同

单队列 deadline 共享全局 queue_lock；mq-deadline 使用自己的内部锁（dd->lock），这把锁只保护调度器的内部数据结构，不与 I/O 提交路径争用。

3. zone lock 支持

mq-deadline 增加了对 zoned block device（SMR 磁盘、ZNS SSD）的支持。这类设备要求同一 zone 内的写请求必须按顺序执行，mq-deadline 通过 dd->zone_lock 位图来保证这一点。

4. 可调参数

# 查看 mq-deadline 的可调参数
ls /sys/block/sda/queue/iosched/
# fifo_batch       — 每批处理的请求数（默认 16）
# front_merges     — 是否允许前向合并（默认 1）
# read_expire      — 读截止时间，单位 ms（默认 500）
# write_expire     — 写截止时间，单位 ms（默认 5000）
# writes_starved   — 连续读批次上限（默认 2）

# 调优示例：数据库场景，缩短读截止时间
echo 100 > /sys/block/sda/queue/iosched/read_expire
echo 1000 > /sys/block/sda/queue/iosched/write_expire

适用场景

mq-deadline 是 HDD 和 SATA SSD 的最佳默认选择：

• HDD：扇区排序减少寻道，截止时间防止饿死。
• SATA SSD：队列深度有限（NCQ 32），轻量排序仍有益处。
• 数据库服务器：读优先策略天然适合 OLTP 负载。

七、BFQ：预算公平队列调度

与 CFQ 的本质区别

BFQ（Budget Fair Queuing，Paolo Valente，2017 年合并进 Linux 主线）经常被误解为”CFQ 的多队列版本”。虽然 BFQ 确实继承了 CFQ 的公平调度理念，但它的核心机制完全不同。

Budget-based 调度

CFQ 给每个队列分配一个时间片（如 100ms），在时间片内该队列独占磁盘。问题是：SSD 上 100ms 可以完成数千个 I/O，而 HDD 上 100ms 可能只完成几十个。时间片对不同设备的”公平”含义完全不同。

BFQ 改用扇区数作为预算单位。每个进程获得固定扇区数的预算（如 8192 个扇区 = 4MB），消耗完预算后让出调度权，无论花了多少时间。这在不同速度的设备上都能保证一致的公平性。

BFQ 预算分配示例：

进程 A（交互进程）: budget = 2048 sectors (1MB)
    → 发出 50 个 4KB 读请求后预算耗尽
    → 因为是交互进程，下次调度时预算恢复得更快

进程 B（批处理进程）: budget = 16384 sectors (8MB)
    → 发出 400 个 4KB 写请求后预算耗尽
    → 因为是批处理进程，预算更大但调度优先级更低

关键：两者获得的扇区数是按权重公平分配的

B-WF2Q+ 算法

BFQ 使用 B-WF2Q+（Budget Worst-case Fair Weighted Fair Queueing Plus）算法来决定队列的调度顺序。这是一个在理论上有严格公平性保证的算法：

• 每个队列有一个”虚拟起始时间”和”虚拟完成时间”。
• 调度器总是选择虚拟起始时间最小的队列。
• 权重越高的队列，虚拟时间推进得越慢，从而获得更多的服务机会。

交互进程检测

BFQ 跟踪每个进程的 I/O 模式来判断它是否是交互进程：

• 交互进程特征：短时间内发出少量 I/O（如打开文件、加载资源），然后长时间空闲（等待用户输入）。I/O 突发间隔大、每次突发量小。
• 非交互进程特征：持续不断地发出 I/O（大文件复制、数据库 compaction、日志写入）。

BFQ 通过统计”I/O 突发之间的思考时间”来区分两者。交互进程获得：

• 更高的调度优先级：立即响应，不需要等待当前进程的预算耗尽。
• 更小的预算：交互进程一次只需要少量 I/O，小预算足矣，快速响应后让出调度权。
• 空闲等待（idling）：BFQ 在交互进程的队列空时短暂等待，赌它马上会发出下一个请求。

为什么 Android 选择 BFQ

Android 设备的存储（eMMC/UFS）性能远不如数据中心 NVMe SSD，随机读写延迟在 200us-2ms 之间。在这种设备上：

1. 前台应用需要低延迟：用户点击应用图标后，前台应用的 I/O（加载 DEX 文件、读取资源）必须立即被处理。
2. 后台服务会抢带宽：Google Play 更新、系统备份、日志收集等后台 I/O 很容易淹没前台 I/O。
3. BFQ 的交互检测天然适合：前台应用表现为”交互进程”（短突发、长间隔），BFQ 自动优先调度它们。

Google 在 Android 14 的 CDD（Compatibility Definition Document）中明确建议使用 BFQ 或 mq-deadline。实测数据显示，在搭载 eMMC 5.1 的中低端设备上，BFQ 比 none 可以将应用冷启动时间缩短 15-25%。

BFQ 的代价

BFQ 的复杂度是所有 blk-mq 调度器中最高的——超过 6000 行代码。在高 IOPS 场景下：

# 在 NVMe 上对比 none 和 bfq
# 使用 fio 随机读 4KB, iodepth=128, 4 线程
# none:  1,200,000 IOPS, CPU usage 35%
# bfq:    820,000 IOPS, CPU usage 78%
# 差距：32% IOPS 损失，主要来自 BFQ 的 per-request 调度开销

结论：BFQ 适合中低速设备（eMMC/UFS/SATA SSD）上的交互场景，不适合高 IOPS 的 NVMe 服务器。

八、kyber：为 NVMe 而生的令牌调度器

设计理念

kyber（Omar Sandoval，2017）是一个极简调度器——总共约 500 行代码。它的设计哲学完全不同于前面所有调度器：

kyber 不排序、不合并、不追求公平——它只做一件事：用延迟反馈控制排队深度。

传统调度器试图对请求排序以最大化吞吐量。kyber 认为：NVMe 设备的内部控制器已经足够智能，软件不需要操心排序问题。软件需要操心的是不要给设备喂太多请求导致延迟飙升。

两个队列：同步与异步

kyber 把所有请求分为两类，各维护一个独立的令牌池：

• 同步（读）队列：延迟敏感。令牌上限较低，限制同时在设备中的读请求数量。
• 异步（写+discard）队列：延迟不敏感。令牌上限较高，允许更大的排队深度。

// kyber 的延迟目标（内核源码 block/kyber-iosched.c）
static const unsigned int kyber_latency_targets[] = {
    [KYBER_READ]    = 2000,     // 2ms 读延迟目标
    [KYBER_WRITE]   = 10000,    // 10ms 写延迟目标
    [KYBER_DISCARD] = 5000000,  // 5s discard 延迟目标
};

令牌机制

每个请求在下发到设备之前，必须获取对应类型的令牌。如果令牌池为空（已达到当前排队深度上限），请求必须等待。

请求到达 → 检查令牌池 → 有令牌？ → 获取令牌 → 下发到设备 → 完成后归还令牌
                           ↓
                        无令牌 → 排队等待

自适应限流

kyber 的核心创新是自适应调整令牌池大小。它持续监控设备的实际完成延迟，使用直方图统计 P50 和 P99 延迟：

• 延迟低于目标：增加令牌池大小（允许更大的排队深度，提高吞吐）。
• 延迟高于目标：减小令牌池大小（减少排队深度，降低延迟）。

调整逻辑使用简单的倍增/减半策略，类似 TCP 拥塞控制中的 AIMD（Additive Increase Multiplicative Decrease）。

// kyber 延迟采样和调整（简化）
static void kyber_timer_fn(struct timer_list *t)
{
    struct kyber_queue_data *kqd = from_timer(kqd, t, timer);

    for (int domain = 0; domain < KYBER_NUM_DOMAINS; domain++) {
        unsigned int p50, p99;
        // 从完成延迟直方图中计算 P50 和 P99
        kyber_stat_percentiles(kqd, domain, &p50, &p99);

        unsigned int target = kyber_latency_targets[domain];

        if (p99 > 2 * target || p50 > target) {
            // 延迟过高：减小排队深度（至少减到 1）
            kqd->domain_tokens[domain] =
                max(1U, kqd->domain_tokens[domain] / 2);
        } else if (p99 < target && p50 < target / 2) {
            // 延迟很低：增大排队深度
            kqd->domain_tokens[domain] =
                min(MAX_TOKENS, kqd->domain_tokens[domain] + 1);
        }
    }
}

为什么为 NVMe 而生

kyber 的设计完美匹配 NVMe 设备的特性：

1. 不排序：NVMe FTL 有自己的排序逻辑，软件排序是多余的。
2. 不做公平调度：服务器场景通常用 cgroup v2 的 io.max/io.latency 来做隔离，不需要调度器操心。
3. 控制 tail latency：NVMe 在高队列深度下的 P99 延迟可能是 P50 的 10 倍以上。kyber 通过限制排队深度来抑制 tail latency。
4. CPU 开销极低：没有排序、没有进程跟踪、没有复杂的数据结构操作。

kyber 的局限

• 不适合 HDD：HDD 需要扇区排序来减少寻道，kyber 完全不排序。
• 不保证公平性：如果多个进程竞争同一块 NVMe，kyber 不保证谁获得更多带宽。
• 不适合所有 NVMe 工作负载：如果你的 NVMe 负载很轻（远没到饱和），kyber 的令牌机制只是增加了一层不必要的间接层。

九、完整实现：简化版 deadline 调度器

下面用 C 实现一个简化版 deadline 调度器，包含读写分离队列、批处理和饥饿保护的完整逻辑。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <limits.h>

/* ---- 数据结构定义 ---- */

typedef enum { DIR_READ = 0, DIR_WRITE = 1 } io_dir_t;

typedef struct io_request {
    unsigned long sector;       /* 起始扇区号 */
    unsigned int  nr_sectors;   /* 扇区数量 */
    io_dir_t      dir;          /* 读/写方向 */
    unsigned long arrive_ms;    /* 到达时间（毫秒） */
    unsigned long deadline_ms;  /* 截止时间（毫秒） */
    struct io_request *sort_prev, *sort_next;  /* 排序链表 */
    struct io_request *fifo_prev, *fifo_next;  /* FIFO 链表 */
} io_request_t;

/* 双向链表头 */
typedef struct {
    io_request_t head;
} io_list_t;

typedef struct {
    io_list_t sort_list[2];     /* 按扇区排序的链表：[READ] 和 [WRITE] */
    io_list_t fifo_list[2];     /* 按到达时间排序的 FIFO：[READ] 和 [WRITE] */

    unsigned long fifo_expire[2]; /* 截止时间：读 500ms，写 5000ms */
    int writes_starved;           /* 连续读批次上限 */
    int writes_starved_counter;   /* 当前连续读批次计数 */

    int fifo_batch;               /* 每批处理请求数 */
    int batching;                 /* 当前批次已处理数 */
    io_dir_t current_dir;         /* 当前处理方向 */
    unsigned long last_sector[2]; /* 上次处理的扇区位置 */

    int total_dispatched;
} deadline_data_t;

/* ---- 链表操作 ---- */

static void list_init(io_list_t *list)
{
    list->head.sort_prev = list->head.sort_next = &list->head;
    list->head.fifo_prev = list->head.fifo_next = &list->head;
}

static int list_empty_sort(io_list_t *list)
{
    return list->head.sort_next == &list->head;
}

static int list_empty_fifo(io_list_t *list)
{
    return list->head.fifo_next == &list->head;
}

/* 按扇区号插入排序链表 */
static void sort_insert(io_list_t *list, io_request_t *rq)
{
    io_request_t *pos = list->head.sort_next;
    while (pos != &list->head && pos->sector < rq->sector)
        pos = pos->sort_next;
    /* 在 pos 之前插入 */
    rq->sort_next = pos;
    rq->sort_prev = pos->sort_prev;
    pos->sort_prev->sort_next = rq;
    pos->sort_prev = rq;
}

/* 在 FIFO 尾部插入 */
static void fifo_insert(io_list_t *list, io_request_t *rq)
{
    rq->fifo_next = &list->head;
    rq->fifo_prev = list->head.fifo_prev;
    list->head.fifo_prev->fifo_next = rq;
    list->head.fifo_prev = rq;
}

/* 从两个链表中移除请求 */
static void remove_request(io_request_t *rq)
{
    rq->sort_prev->sort_next = rq->sort_next;
    rq->sort_next->sort_prev = rq->sort_prev;
    rq->fifo_prev->fifo_next = rq->fifo_next;
    rq->fifo_next->fifo_prev = rq->fifo_prev;
}

/* ---- 调度器核心逻辑 ---- */

static void dd_init(deadline_data_t *dd)
{
    memset(dd, 0, sizeof(*dd));
    for (int i = 0; i < 2; i++) {
        list_init(&dd->sort_list[i]);
        list_init(&dd->fifo_list[i]);
    }
    dd->fifo_expire[DIR_READ]  = 500;   /* 读截止 500ms */
    dd->fifo_expire[DIR_WRITE] = 5000;  /* 写截止 5000ms */
    dd->writes_starved = 2;
    dd->fifo_batch = 16;
    dd->current_dir = DIR_READ;
}

/* 添加请求到调度器 */
static void dd_add_request(deadline_data_t *dd, io_request_t *rq,
                           unsigned long now_ms)
{
    rq->deadline_ms = now_ms + dd->fifo_expire[rq->dir];
    rq->arrive_ms = now_ms;
    sort_insert(&dd->sort_list[rq->dir], rq);
    fifo_insert(&dd->fifo_list[rq->dir], rq);
}

/* 检查 FIFO 头部是否已超时 */
static int fifo_expired(io_list_t *fifo, unsigned long now_ms)
{
    if (list_empty_fifo(fifo))
        return 0;
    io_request_t *head = fifo->head.fifo_next;
    return now_ms >= head->deadline_ms;
}

/* 从排序链表中选择距离 last_sector 最近的后续请求 */
static io_request_t *next_sorted(io_list_t *sort, unsigned long last_sector)
{
    if (list_empty_sort(sort))
        return NULL;
    io_request_t *pos = sort->head.sort_next;
    while (pos != &sort->head && pos->sector < last_sector)
        pos = pos->sort_next;
    if (pos == &sort->head)
        pos = sort->head.sort_next;  /* wrap around */
    return pos;
}

/* 核心调度：选择下一个要处理的请求 */
static io_request_t *dd_dispatch(deadline_data_t *dd, unsigned long now_ms)
{
    io_request_t *rq = NULL;
    io_dir_t dir;

    /* 步骤1：检查读 FIFO 是否有超时请求 */
    if (fifo_expired(&dd->fifo_list[DIR_READ], now_ms)) {
        rq = dd->fifo_list[DIR_READ].head.fifo_next;
        dd->current_dir = DIR_READ;
        dd->batching = 0;
        goto dispatch;
    }

    /* 步骤2：检查写 FIFO 是否有超时请求 */
    if (fifo_expired(&dd->fifo_list[DIR_WRITE], now_ms)) {
        rq = dd->fifo_list[DIR_WRITE].head.fifo_next;
        dd->current_dir = DIR_WRITE;
        dd->batching = 0;
        goto dispatch;
    }

    /* 步骤3：当前批次未结束，继续同方向 */
    if (dd->batching < dd->fifo_batch) {
        dir = dd->current_dir;
        rq = next_sorted(&dd->sort_list[dir], dd->last_sector[dir]);
        if (rq)
            goto dispatch;
    }

    /* 步骤4：当前方向无请求或批次结束，考虑切换方向 */
    /* 写饥饿检查：连续读了 writes_starved 批后必须写 */
    if (dd->current_dir == DIR_READ) {
        dd->writes_starved_counter++;
        if (dd->writes_starved_counter >= dd->writes_starved
            && !list_empty_sort(&dd->sort_list[DIR_WRITE])) {
            dir = DIR_WRITE;
            dd->writes_starved_counter = 0;
        } else {
            dir = DIR_READ;
        }
    } else {
        dir = DIR_READ;  /* 写完一批后回到读 */
    }

    /* 步骤5：从选定方向取请求 */
    rq = next_sorted(&dd->sort_list[dir], dd->last_sector[dir]);
    if (!rq) {
        /* 选定方向没有请求，换另一个方向 */
        dir = 1 - dir;
        rq = next_sorted(&dd->sort_list[dir], dd->last_sector[dir]);
    }
    if (!rq)
        return NULL;  /* 两个方向都没有请求 */

    dd->current_dir = dir;
    dd->batching = 0;

dispatch:
    remove_request(rq);
    dd->last_sector[rq->dir] = rq->sector + rq->nr_sectors;
    dd->batching++;
    dd->total_dispatched++;
    return rq;
}

/* ---- 测试驱动 ---- */

int main(void)
{
    deadline_data_t dd;
    dd_init(&dd);

    /* 模拟：创建一组读写请求 */
    io_request_t requests[20];
    memset(requests, 0, sizeof(requests));

    /* 8 个读请求，扇区分散 */
    unsigned long read_sectors[] = {1000, 200, 8000, 500, 3000, 100, 6000, 1500};
    for (int i = 0; i < 8; i++) {
        requests[i].sector = read_sectors[i];
        requests[i].nr_sectors = 8;
        requests[i].dir = DIR_READ;
    }

    /* 8 个写请求 */
    unsigned long write_sectors[] = {4000, 700, 9000, 300, 5000, 2000, 7000, 150};
    for (int i = 0; i < 8; i++) {
        requests[8 + i].sector = write_sectors[i];
        requests[8 + i].nr_sectors = 8;
        requests[8 + i].dir = DIR_WRITE;
    }

    /* 添加所有请求（模拟它们在 t=0 到达） */
    for (int i = 0; i < 16; i++)
        dd_add_request(&dd, &requests[i], 0);

    /* 添加一个"超时"读请求（模拟 arrive_ms=0 但截止时间已过） */
    requests[16].sector = 50000;
    requests[16].nr_sectors = 8;
    requests[16].dir = DIR_READ;
    dd_add_request(&dd, &requests[16], 0);
    requests[16].deadline_ms = 0;  /* 强制超时 */

    printf("=== Deadline 调度器模拟 ===\n\n");
    printf("%-4s %-6s %-10s %-10s\n", "序号", "方向", "扇区号", "调度原因");
    printf("---- ------ ---------- ----------\n");

    unsigned long now = 1;  /* 模拟当前时间 > 0，触发超时检测 */
    io_request_t *rq;
    int seq = 1;
    while ((rq = dd_dispatch(&dd, now)) != NULL) {
        const char *reason;
        if (seq == 1 && rq->sector == 50000)
            reason = "FIFO超时";
        else if (dd.batching == 1 && dd.current_dir != (seq > 1 ? DIR_READ : DIR_WRITE))
            reason = "方向切换";
        else
            reason = "排序顺序";

        printf("%-4d %-6s %-10lu %s\n",
               seq++,
               rq->dir == DIR_READ ? "READ" : "WRITE",
               rq->sector,
               rq->dir == DIR_READ ? "读" : "写");
    }

    printf("\n共调度 %d 个请求\n", dd.total_dispatched);
    return 0;
}

编译运行：

gcc -O2 -o deadline_sim deadline_sim.c && ./deadline_sim

这个实现展示了 deadline 调度器的三个核心机制：

1. 扇区排序：同方向请求按扇区号顺序处理，最大化顺序性。
2. FIFO 超时：超过截止时间的请求被优先处理，防止饿死。
3. 批处理 + 写饥饿保护：连续处理同方向请求（批处理），但通过 writes_starved 计数器保证写请求不被无限推迟。

十、工程陷阱表

在生产环境中配置 I/O 调度器时，以下是最常见的陷阱：

持久化配置的正确方式

# /etc/udev/rules.d/60-ioscheduler.rules

# 旋转盘（HDD）：使用 mq-deadline
ACTION=="add|change", KERNEL=="sd[a-z]*", ATTR{queue/rotational}=="1", \
    ATTR{queue/scheduler}="mq-deadline"

# 非旋转盘（SATA SSD）：使用 mq-deadline
ACTION=="add|change", KERNEL=="sd[a-z]*", ATTR{queue/rotational}=="0", \
    ATTR{queue/scheduler}="mq-deadline"

# NVMe：使用 none
ACTION=="add|change", KERNEL=="nvme[0-9]*", ATTR{queue/scheduler}="none"

# eMMC/UFS（嵌入式设备）：使用 bfq
ACTION=="add|change", KERNEL=="mmcblk[0-9]*", ATTR{queue/scheduler}="bfq"

# 立即生效（无需重启）
udevadm control --reload-rules && udevadm trigger

十一、性能实测数据

测试环境

• HDD：Seagate Exos 7E10（7200 RPM，SATA 6Gbps）
• SATA SSD：Samsung 870 EVO 1TB（SATA 6Gbps，V-NAND TLC）
• NVMe SSD：Samsung 980 PRO 1TB（PCIe 4.0 x4，Elpis 控制器）
• CPU：AMD EPYC 7763（64 核 128 线程）
• 内存：256GB DDR4 3200
• 内核：Linux 6.6.32
• 测试工具：fio 3.37，ioengine=io_uring

随机读 4KB（iodepth=32，单线程）

随机读 4KB（iodepth=128，4 线程，高压力）

混合读写（70/30，4KB，iodepth=32，4 线程）

顺序写 128KB（iodepth=32，单线程）

关键观察

1. HDD 上 mq-deadline 全面最优：扇区排序减少寻道，IOPS 比 none 高 17-19%，读延迟低 17%。这完全符合预期——旋转盘需要排序。

2. NVMe 上 none 吞吐最高：没有调度开销。但在高压力场景下，kyber 的 P99 延迟最低（145us vs none 的 180us），P999 优势更明显（520us vs 850us）。kyber 的延迟反馈控制在高负载时价值显著。

3. BFQ 的 CPU 开销在 NVMe 上清晰可见：高压力随机读场景下，BFQ 比 none 降了 32% 的 IOPS。这个开销来自 B-WF2Q+ 算法的 per-request 调度决策。

4. 顺序写差异很小：顺序写场景下所有调度器差异不大（< 5%），因为请求本身已经是有序的，调度器没什么需要优化的。

5. SATA SSD 上 mq-deadline 微弱领先：SATA SSD 的队列深度有限（NCQ 32），轻量排序仍有微弱正面效果。但差距已经很小，用 none 也完全可接受。

基准测试脚本

#!/bin/bash
# io-scheduler-bench.sh
# 用法: sudo bash io-scheduler-bench.sh /dev/nvme0n1

DEVICE="${1:?用法: $0 <设备路径>}"
DEVNAME=$(basename "$DEVICE")
SCHEDULERS="none mq-deadline bfq kyber"

echo "设备: $DEVICE"
echo "可用调度器: $(cat /sys/block/$DEVNAME/queue/scheduler)"
echo "---"

for sched in $SCHEDULERS; do
    echo "$sched" > /sys/block/$DEVNAME/queue/scheduler 2>/dev/null
    current=$(cat /sys/block/$DEVNAME/queue/scheduler | grep -o '\[.*\]' | tr -d '[]')
    if [ "$current" != "$sched" ]; then
        echo "[$sched] 不可用，跳过"
        continue
    fi
    echo "=== 调度器: $current ==="

    # 随机读 4KB
    echo -n "  随机读 4KB (iodepth=32): "
    fio --name=randread --filename=$DEVICE --direct=1 --rw=randread \
        --bs=4k --ioengine=io_uring --iodepth=32 --numjobs=1 \
        --runtime=30 --time_based --group_reporting \
        --output-format=json 2>/dev/null | \
        python3 -c "
import sys, json
d = json.load(sys.stdin)['jobs'][0]['read']
print(f\"IOPS={d['iops']:.0f}, lat_avg={d['lat_ns']['mean']/1e6:.2f}ms, P99={d['clat_ns']['percentile']['99.000000']/1e3:.0f}us\")
"

    # 混合读写
    echo -n "  混合读写 70/30 (iodepth=32, 4j): "
    fio --name=randrw --filename=$DEVICE --direct=1 --rw=randrw \
        --rwmixread=70 --bs=4k --ioengine=io_uring --iodepth=32 \
        --numjobs=4 --runtime=30 --time_based --group_reporting \
        --output-format=json 2>/dev/null | \
        python3 -c "
import sys, json
d = json.load(sys.stdin)['jobs'][0]
r, w = d['read'], d['write']
print(f\"read_IOPS={r['iops']:.0f}, write_IOPS={w['iops']:.0f}, read_P99={r['clat_ns']['percentile']['99.000000']/1e3:.0f}us\")
"
    echo
done

选型速查

十二、个人观点与未来展望

I/O 调度器的消亡曲线

I/O 调度器的历史是一部硬件驱动的消亡史：

HDD 时代 (2000s):
    寻道昂贵（7-15ms）→ 复杂排序 (CFQ, 预期调度, per-process 队列)
    调度器是性能的关键差异因素，好的调度器能提升 10 倍性能
         ↓
SATA SSD 时代 (2010s):
    随机 OK（50-100us）但带宽有限 → 适度调度 (deadline, 读优先)
    调度器仍有价值，但收益从 10 倍降到 10-20%
         ↓
NVMe SSD 时代 (2017-now):
    随机和顺序差异小、内部调度强 → 不调度 (none) 或轻量控制 (kyber)
    调度器的最佳策略是"不存在"或"尽量少干预"
         ↓
CXL / 远端内存时代 (2025+):
    延迟差异大（本地 vs 远端）、拓扑复杂 → ???
    可能需要新一代"拓扑感知"的 I/O 调度

CFQ 的教训

CFQ 是一个精妙绝伦的算法——5000+ 行代码，红黑树、预期调度、per-process 队列、三级优先级、时间片轮转。它在 HDD 上的效果确实很好。但硬件演进让它的核心假设（“寻道昂贵”）失效后，整个算法就变得无关紧要了。

这给了我两个教训：

**第一，在系统设计中，总是问自己”这个假设在 5 年后还成立吗？“** CFQ 假设”寻道昂贵”，这在 2004 年完全正确，但到了 2014 年（SSD 普及）就开始动摇，2019 年（NVMe 主流）彻底失效。如果一个设计的价值建立在某个可能消失的硬件特性上，那就把这个依赖隔离出来，让它可以被轻松替换。

第二，简洁比精巧更经得起时间考验。 kyber 的 500 行代码和 deadline 的 800 行代码，在硬件世代更替中存活了下来；CFQ 的 5000 行代码被整个移除。不是因为 CFQ 写得差，而是因为复杂的设计有更多的假设，而每个假设都是一个潜在的失效点。

未来可能的方向

1. io_uring + 调度器的融合：io_uring 的 SQPOLL 模式已经在绕过传统的 I/O 提交路径。未来可能出现直接在 io_uring 层面做调度决策的方案，完全跳过块层。

2. CXL 时代的新挑战：CXL 2.0/3.0 允许远端内存和存储通过 PCIe 互联。本地 NVMe 延迟 10us，远端 CXL 存储延迟可能 500us-1ms。这种异构延迟环境可能需要新的调度策略。

3. 机器学习辅助调度：已经有学术工作（如 MQFQ）尝试用在线学习来动态调整调度参数。但在内核中引入 ML 推理的开销和确定性问题是巨大的工程挑战。

4. 硬件卸载：未来的智能 NIC/DPU 可能在硬件层面做 I/O 调度，彻底消除软件开销。

最后的思考

I/O 调度器最有趣的不是算法本身，而是它让我们看到了系统软件与硬件共同进化的完整过程。每一代调度器都是对当时硬件特性的最优适配，但没有一个能永恒。在系统软件的世界里，没有最好的算法，只有最适合当前硬件的算法。而”当前”，总是在变。

系列导航： - 上一篇：进程调度：从 CFS 到 EEVDF 的哲学演变 - 下一篇：伙伴系统与 SLUB 分配器

相关阅读： - 定时器算法：时间轮、最小堆与层级时间轮 - B-tree 深度解剖