[toc]

在这里插入图片描述

block/mq-deadline.c 多队列截止时间调度器(Multi-Queue Deadline I/O Scheduler) 兼顾吞吐量与延迟的经典算法

历史与背景

这项技术是为了解决什么特定问题而诞生的？

截止时间（Deadline）I/O调度器的诞生是为了解决一个根本性的矛盾：最大化I/O吞吐量与保证请求的公平性和低延迟之间的冲突。

  • 最大化吞吐量：对于机械硬盘（HDD），最高效的方式是处理物理上连续的请求，以最小化昂贵的磁头寻道时间。这意味着应该对请求进行排序和批处理。
  • 保证公平性与低延迟：如果系统只顾着处理连续的大块写操作，那么一个关键的小块读操作（例如，应用程序等待此数据才能继续运行）可能会被“饿死”（starve），等待很长时间才能被服务，导致应用卡顿。

Deadline调度器通过一个优雅的设计来解决这个矛盾：它在默认情况下会合并和排序请求以优化吞吐量，但同时为每个请求设置一个**“截止时间”。如果一个请求在这个时间窗口内没有被服务，它就会被赋予高优先级，强制调度器去处理它，从而防止饥饿并保证了一个可预测的最大延迟**。

它的发展经历了哪些重要的里程碑或版本迭代？

  1. 经典Deadline调度器：最初，Deadline是为传统的单队列块层设计的。它在全局范围内对所有I/O请求进行排序，对于当时的单核CPU和单队列HDD来说非常有效。
  2. blk-mq的挑战：随着多核CPU和高速多队列SSD（特别是NVMe）的普及，单队列模型成为了性能瓶颈。Linux内核引入了多队列块层（blk-mq），它为每个CPU核心和硬件队列都提供了独立的提交路径，极大地减少了锁竞争。
  3. mq-deadline的诞生（关键里程碑）：经典的Deadline调度器无法在blk-mq框架下工作。因此，block/mq-deadline.c 就是为blk-mq框架重新实现的Deadline调度器。其核心算法思想保持不变，但实现方式从管理一个全局队列，变为了在每个硬件派发队列（struct blk_mq_hw_ctx）上独立运行一个Deadline调度器实例。这使得它能够适应现代硬件，并在多队列环境中继续发挥作用。

目前该技术的社区活跃度和主流应用情况如何？

mq-deadline是一个非常成熟、稳定且代码简洁的I/O调度器。虽然在许多现代发行版中，它可能不再是所有设备的默认调度器（例如，NVMe通常默认使用none，SATA设备可能默认bfq或kyber），但它仍然是一个非常重要且广泛使用的选项。

  • 数据库社区：由于其低CPU开销和可预测的延迟，mq-deadline长期以来一直是MySQL、PostgreSQL等数据库工作负载的官方推荐调度器。
  • 虚拟化和服务器环境：在需要简单、公平且能有效防止I/O饥饿的场景中，它是一个可靠的选择。

核心原理与设计

它的核心工作原理是什么？

mq-deadline为每个硬件队列维护了几个关键的数据结构来组织I/O请求：

  • 两个红黑树 (Red-Black Trees)：一个用于读请求，一个用于写请求。这两个树都按请求的起始逻辑块地址（LBA）排序。这是实现吞吐量优化的关键，调度器可以从树中轻松地找到下一个物理上连续的请求。
  • 两个FIFO链表 (FIFO Lists)：一个用于读请求，一个用于写请求。这两个链表按请求的截止时间排序。这是实现延迟保证的关键。

调度（派发）逻辑 (deadline_dispatch_requests) 如下：

  1. 检查截止时间：调度器首先检查FIFO链表。是否存在已经超过截止时间的请求？
    • 如果存在，优先处理读FIFO中的过期请求，然后是写FIFO。这确保了没有任何请求会无限期等待，并且读操作（通常是同步的、阻塞应用的）有更高优先级。
  2. 选择连续请求：如果没有任何请求过期，调度器就会从红黑树中选择下一个请求来处理，以最大化吞吐量。它会优先从读请求树中选择，以期尽快完成阻塞应用的读操作。
  3. 批处理：为了进一步优化，调度器会尝试在一个方向上（例如，LBA递增）派发一个批次的连续请求，直到遇到一个方向相反的请求或队列为空。

它的主要优势体现在哪些方面？

  • 低CPU开销：其算法相对简单，相比于复杂的BFQ调度器，CPU占用率更低。
  • 防止请求饥饿：截止时间机制是防止任何请求（特别是读请求）被大量写请求饿死的硬保证。
  • 良好的读延迟：通过明确地优先处理读请求和过期的读请求，它为读密集型应用提供了良好的响应时间。
  • 简单可预测：其行为模式相对简单，易于理解和预测，这对于需要稳定、可复现性能的数据库等应用非常重要。

它存在哪些已知的劣势、局限性或在特定场景下的不适用性？

  • 无服务质量（QoS）区分：它平等地对待来自所有进程的I/O请求，无法像CFQ或BFQ那样为不同进程分配不同的I/O带宽或优先级。
  • 对HDD优化更多：其核心的LBA排序思想主要源于优化HDD的磁头寻道。对于几乎没有寻道惩罚的现代SSD，这种排序的收益较小。
  • 对于桌面环境可能不是最优：在桌面环境中，BFQ调度器通过复杂的启发式算法来区分交互式应用和后台应用，通常能提供更好的用户体验。

使用场景

在哪些具体的业务或技术场景下，它是首选解决方案？

  • 数据库服务器（OLTP/OLAP）：这是mq-deadline的经典应用场景。数据库通常自己管理I/O，它们需要的是一个轻量级、能保证读延迟下限、防止写操作饿死读操作的调度器。
  • I/O密集型的服务器应用：对于任何关键服务，如果其性能瓶颈在于存储I/O，并且需要一个可预测的延迟上限，mq-deadline是一个非常可靠的选择。
  • 虚拟化环境：在需要为多个虚拟机提供公平、无饥饿的磁盘访问时，mq-deadline的简单性和公平性使其成为一个不错的备选方案。

是否有不推荐使用该技术的场景？为什么？

  • 超高速NVMe SSD：对于顶级的NVMe设备，其内部硬件调度能力非常强大，延迟极低。在这种情况下，任何软件调度器的开销都可能成为瓶颈。因此，none调度器（一个简单的FIFO passthrough）通常是这些设备的最佳选择，以实现最高的IOPS。
  • 桌面或多媒体系统：在这些场景下，用户体验（如应用的启动速度、UI的响应）至关重要。BFQ调度器通过其复杂的预算和公平队列机制，能更好地保证交互式应用的I/O优先级，通常是更好的选择。
  • 需要精细化I/O控制的场景：如果需要使用cgroups来限制特定服务的磁盘I/O带宽，那么BFQ是必需的，因为mq-deadline不具备这种按进程组进行资源分配的能力。

对比分析

请将其 与 其他相似技术 进行详细对比。

特性 mq-deadline none bfq (Budget Fair Queueing) kyber
核心原理 截止时间 + LBA排序 简单的FIFO，无重排 复杂的预算和权重，为每个进程创建队列 基于延迟目标的请求派发
CPU开销 低 最低 高 中等
主要目标 平衡吞吐量与延迟 最大化IOPS/吞吐量，最低延迟 公平性和交互性 控制和稳定I/O延迟在目标值
最佳适用硬件 SATA SSD, HDD, 企业级SSD 超高速NVMe SSD HDD, SATA SSD, 桌面环境 NVMe/SATA SSD, 混合工作负载
防止饥饿 是（通过截止时间） 否（理论上可能） 是（通过公平队列） 是（通过延迟目标）
cgroups I/O控制 否 否

MQ-Deadline I/O 调度器模块：定义与注册

本代码片段展示了 mq-deadline I/O 调度器在 Linux 内核中的定义和注册过程。其核心功能是：通过填充一个 elevator_type 结构体（mq_deadline），将 Deadline 调度算法的所有核心操作（如请求插入、分发、合并等）以函数指针的形式封装起来，并在模块加载时 (deadline_init)，将这个完整的调度器“插件”注册到内核的块设备 I/O 调度框架（elevator framework）中，使其成为一个可供系统选择和使用的 I/O 调度策略。

实现原理分析

此代码是内核 I/O 调度器“电梯”框架中一个具体调度策略的实现范例。它本身不包含算法的执行逻辑，而是以一种声明式的方式，向块设备层“描述”了 mq-deadline 调度器的全部行为。

  1. struct elevator_type：调度器的蓝图:

    • mq_deadline 结构体是整个调度器的核心定义。它像一个“虚函数表”，将抽象的调度操作映射到具体的实现函数。
    • .ops: 这是最重要的成员，它是一个包含了十几个函数指针的 elevator_ops 结构。每个函数指针都对应一个 I/O 调度过程中的关键节点：
      • insert_requests: 当新的 I/O 请求从上层传来时，此函数被调用，负责将请求插入到调度器的内部数据结构中（对于 Deadline 算法，是读/写 FIFO 队列和按截止时间排序的红黑树）。
      • dispatch_request: 当设备可以接受新的 I/O 请求时，此函数被调用，负责从其数据结构中选择一个“最佳”的请求分发给设备驱动。
      • request_merge, bio_merge: 实现请求合并的逻辑，以提高效率。
      • init_sched, exit_sched: 分别在调度器为一个设备实例化和销毁时被调用，用于分配和释放私有数据。
    • .elevator_name: “mq-deadline”，是调度器的唯一标识符，用户空间可以通过这个名字来选择它。
    • .elevator_owner: THIS_MODULE，将此调度器与当前内核模块绑定，用于正确的引用计数管理。

  2. 模块化注册与注销:

    • deadline_init 函数在模块加载时被调用。它只做一件事：调用 elv_register(&mq_deadline)。这个函数会将 mq_deadline 结构体添加到一个全局的调度器类型列表中，使其对系统可见和可用。
    • deadline_exit 函数在模块卸载时被调用。它对称地调用 elv_unregister(&mq_deadline)，将调度器从全局列表中移除，并确保所有正在使用此调度器的设备都能安全地切换到其他调度器。
    • 这种 register/unregister 的模式是内核中实现可插拔子系统（如文件系统、调度器、网络协议）的标准方法。

代码分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
// 定义一个 elevator_type 结构体，用于向块层描述 mq-deadline 调度器。
static struct elevator_type mq_deadline = {
	// .ops 成员包含了调度器所有核心操作的函数指针。
	.ops = {
		.depth_updated		= dd_depth_updated,    // 队列深度更新时的回调
		.limit_depth		= dd_limit_depth,      // 限制队列深度的回调
		.insert_requests	= dd_insert_requests,  // 插入新请求的核心逻辑
		.dispatch_request	= dd_dispatch_request, // 从队列中选择并分发请求的核心逻辑
		.prepare_request	= dd_prepare_request,  // 准备分发请求前的回调
		.finish_request		= dd_finish_request,   // 请求完成后的回调
		.next_request		= elv_rb_latter_request, // 在红黑树中查找后一个请求
		.former_request		= elv_rb_former_request, // 在红黑树中查找前一个请求
		.bio_merge		= dd_bio_merge,        // bio 合并逻辑
		.request_merge		= dd_request_merge,    // request 合并逻辑
		.requests_merged	= dd_merged_requests,  // 多个请求被合并后的回调
		.request_merged		= dd_request_merged,   // 单个请求被合并后的回调
		.has_work		= dd_has_work,         // 检查调度器是否有工作要做
		.init_sched		= dd_init_sched,       // 为设备初始化调度器实例
		.exit_sched		= dd_exit_sched,       // 销毁设备上的调度器实例
	},

#ifdef CONFIG_BLK_DEBUG_FS
	// 如果配置了 debugfs，则提供用于调试的属性文件。
	.queue_debugfs_attrs = deadline_queue_debugfs_attrs,
#endif
	.elevator_attrs = deadline_attrs,   // 用于 sysfs 的调度器可调参数
	.elevator_name = "mq-deadline",     // 调度器的唯一名称
	.elevator_alias = "deadline",       // 调度器的别名
	.elevator_owner = THIS_MODULE,      // 将调度器与本内核模块关联
};
// 为模块设置一个别名，便于系统识别。
MODULE_ALIAS("mq-deadline-iosched");

/**
 * @brief deadline_init - mq-deadline 调度器模块的初始化函数。
 * @return int: 成功返回0，失败返回错误码。
 */
static int __init deadline_init(void)
{
	// 向内核的电梯框架注册 mq_deadline 调度器。
	return elv_register(&mq_deadline);
}

/**
 * @brief deadline_exit - mq-deadline 调度器模块的退出函数。
 */
static void __exit deadline_exit(void)
{
	// 从内核的电梯框架中注销 mq_deadline 调度器。
	elv_unregister(&mq_deadline);
}

// 注册模块的初始化和退出函数。
module_init(deadline_init);
module_exit(deadline_exit);

// 模块元数据。
MODULE_AUTHOR("Jens Axboe, Damien Le Moal and Bart Van Assche");
MODULE_LICENSE("GPL");
MODULE_DESCRIPTION("MQ deadline IO scheduler");