BFQ (预算公平队列)

BFQ 是一个比例份额 I/O 调度器，具有一些额外的低延迟能力。除了 cgroup 支持（blkio 或 io 控制器）之外，BFQ 的主要功能是

  • BFQ 保证高系统和应用程序响应能力，以及对时间敏感的应用程序（如音频或视频播放器）的低延迟；

  • BFQ 在进程或组之间分配带宽，而不仅仅是时间（在需要保持高吞吐量时切换回时间分配）。

在其默认配置中，BFQ 优先考虑延迟而不是吞吐量。因此，当需要实现更低的延迟时，BFQ 构建的调度可能会导致较低的吞吐量。如果对于给定的设备，您的主要或唯一目标是在任何时候都实现最大可能的吞吐量，则请通过将 low_latency 设置为 0 来关闭该设备的所有低延迟启发式方法。有关如何为延迟和吞吐量之间的期望权衡配置 BFQ，或如何最大化吞吐量的详细信息，请参阅第 3 节。

与每个 I/O 调度器一样，BFQ 会为每个 I/O 请求处理增加一些开销。为了了解这种开销，BFQ 的总的、单锁保护的、每个请求的处理时间（即，请求插入、调度和完成挂钩的执行时间之和）例如，在 Intel Core i7-2760QM@2.40GHz 上为 1.9 微秒（笔记本电脑的旧 CPU；时间使用简单的代码检测来测量，并使用 S 套件 [1] 的 throughput-sync.sh 脚本，在性能分析模式下）。为了将此结果置于上下文中，blk-mq 中最轻量级的 I/O 调度器 mq-deadline 的总的、单锁保护的、每个请求的执行时间为 0.7 微秒（mq-deadline 大约 800 行代码，而 BFQ 大约 10500 行代码）。

调度开销进一步限制了 CPU 可以处理的最大 IOPS（这已经受到 I/O 堆栈其余部分执行的限制）。为了了解 BFQ 的限制，在慢速或中等 CPU 上，以下是启用完全分层支持时（即，设置了 CONFIG_BFQ_GROUP_IOSCHED），但未设置 CONFIG_BFQ_CGROUP_DEBUG 的情况下（第 4-2 节），三种不同 CPU 的 BFQ 限制，分别在普通笔记本电脑、旧台式机和廉价嵌入式系统上： - Intel i7-4850HQ：400 KIOPS - AMD A8-3850：250 KIOPS - ARM CortexTM-A53 八核：80 KIOPS

如果设置了 CONFIG_BFQ_CGROUP_DEBUG（当然启用了完全分层支持），则 BFQ 的可持续吞吐量会降低，因为所有 blkio.bfq* 统计信息都会被创建和更新（第 4-2 节）。对于 BFQ，这会导致在与上述相同的系统上实现以下最大可持续吞吐量：- Intel i7-4850HQ：310 KIOPS - AMD A8-3850：200 KIOPS - ARM CortexTM-A53 八核：56 KIOPS

BFQ 也适用于多队列设备。

1. BFQ 何时有用？

BFQ 在个人和服务器系统上提供以下好处。

1-1 个人系统

交互式应用程序的低延迟

无论实际的后台工作负载如何，BFQ 都能保证，对于交互式任务，存储设备实际上与空闲状态一样响应迅速。例如，即使正在执行以下一个或多个后台工作负载

  • 正在读取、写入或复制一个或多个大型文件，

  • 正在编译源代码文件树，

  • 一个或多个虚拟机正在执行 I/O，

  • 软件更新正在进行中，

  • 索引守护程序正在扫描文件系统并更新其数据库，

启动应用程序或从应用程序中加载文件所花费的时间与存储设备空闲时的时间大致相同。作为比较，使用 CFQ、NOOP 或 DEADLINE，在相同条件下，应用程序会遇到高延迟，甚至变得无响应，直到后台工作负载终止（在 SSD 上也是如此）。

软实时应用程序的低延迟

软实时应用程序（如音频和视频播放器/流媒体）也享有低延迟和低丢包率，无论后台 I/O 工作负载如何。因此，这些应用程序几乎不会因后台工作负载而出现任何故障。

代码开发任务的更高速度

如果碰巧并行执行一些额外的工作负载，那么 BFQ 执行的典型代码开发任务（编译、检出、合并等）的 I/O 相关组件的速度比 CFQ、NOOP 或 DEADLINE 快得多。

高吞吐量

在硬盘上，BFQ 的吞吐量比 CFQ 高出高达 30%，比 DEADLINE 和 NOOP 高出高达 150%，在我们的测试中考虑的所有顺序工作负载都是如此。对于随机工作负载以及在基于闪存的设备上的所有工作负载，BFQ 的吞吐量与其它调度程序大致相同。

强大的公平性、带宽和延迟保证

BFQ 根据 I/O 绑定应用程序的权重比例，在它们之间分配设备吞吐量，而不仅仅是设备时间，无论任何工作负载和设备参数如何。从这些带宽保证中，可以通过一个简单的公式计算出每个 I/O 请求的严格延迟保证。如果未配置为严格的服务保证，则 BFQ 会切换到基于时间的资源共享（仅限）以用于那些可能导致吞吐量损失的应用程序。

1-2 服务器系统

服务器系统的大多数好处都源于与上述相同的服务属性。特别是，无论是否正在提供额外的（可能是繁重的）工作负载，BFQ 都能保证

  • 音频和视频流的零或极低抖动和丢包率；

  • 快速检索网页和嵌入式对象；

  • 在实时转储应用程序（例如，数据包日志记录）中实时记录数据；

  • 本地和远程访问服务器的响应速度。

2. BFQ 如何工作？

BFQ 是一个比例份额 I/O 调度器，其一般结构以及许多代码都借用了 CFQ。

  • 在设备上执行 I/O 的每个进程都与一个权重和一个 (bfq_)queue 相关联。

  • BFQ 在一段时间内为每个队列（进程）授予对设备的独占访问权限，并通过将每个队列与一个预算（以扇区数衡量）相关联来实现此服务模型。

    • 在队列被授予对设备的访问权限后，该队列的预算会在每次请求调度时，按请求的大小递减。

    • 只有在发生以下事件之一时，才会使正在服务的队列过期，即暂停其服务：1) 队列用完预算，2) 队列变空，3) “预算超时”触发。

      • 预算超时可防止执行随机 I/O 的进程占用设备过长时间，从而大幅降低吞吐量。

      • 实际上，与 CFQ 中一样，与发出同步请求的进程关联的队列可能不会在其变空时立即过期。相反，BFQ 可能会使设备闲置一小段时间间隔，以便该进程有机会在及时发出新请求的情况下继续获得服务。如果进程执行同步和顺序 I/O，则设备闲置通常会提高旋转设备和非排队闪存设备的吞吐量。此外，在 BFQ 下，设备闲置还有助于保证发出同步请求的进程的所需吞吐量分数（有关更多详细信息，请参阅本文档中的 slice_idle 可调参数的说明，或 [1, 2]）。

        • 关于闲置以实现服务保证，如果多个进程同时竞争设备，但所有进程和组都具有相同的权重，则 BFQ 可保证预期的吞吐量分配，而不会使设备闲置。因此，在这种常见情况下，吞吐量会尽可能高。

      • 在具有内部命令排队的基于闪存的存储（通常是 NCQ）上，设备闲置通常总是不利于吞吐量。因此，对于这些设备，BFQ 仅在严格需要服务保证时才执行闲置，即为了保证低延迟或公平性。在这些情况下，整体吞吐量可能不是最优的。目前没有解决方案可以在具有内部排队的设备上提供强大的服务保证和最佳吞吐量。

    • 如果启用了低延迟模式（默认配置），BFQ 会执行一些特殊的启发式方法来检测交互式和软实时应用程序（例如，视频或音频播放器/流媒体），并减少它们的延迟。为实现此目标而采取的最重要措施是使与这些应用程序关联的队列获得超过其设备吞吐量的公平份额。为简洁起见，我们将其称为 BFQ 为特权这些队列而采取的整套操作的“权重提升”。特别是，BFQ 为交互式应用程序提供一种较温和的权重提升形式，为软实时应用程序提供一种较强的形式。

    • BFQ 会自动停用在队列创建爆发中诞生的队列的闲置。实际上，这些队列通常与主要受益于高吞吐量的应用程序和服务进程关联。例如启动期间的 systemd 或 git grep。

    • 与 CFQ 一样，BFQ 合并执行交错 I/O 的队列，即执行如果合并则大多会变为顺序的随机 I/O。与 CFQ 不同，BFQ 通过一种称为早期队列合并 (EQM) 的更具反应性的机制来实现此目标。EQM 在检测交错 I/O（协作进程）方面非常灵敏，这使得 BFQ 能够通过队列合并来实现高吞吐量，即使对于那些 CFQ 需要另一种机制（抢占）才能获得高吞吐量的队列也是如此。因此，EQM 是一种统一的机制，可以通过交错 I/O 实现高吞吐量。

    • 队列根据 WF2Q+ 的变体进行调度，该变体名为 B-WF2Q+，并使用增强的 rb-tree 实现以保留 O(log N) 的整体复杂性。有关更多详细信息，请参阅 [2]。B-WF2Q+ 也已为分层调度做好准备，详细信息见第 4 节。

    • B-WF2Q+ 保证与理想的、完全公平的、平稳的服务之间的严格偏差。特别是，B-WF2Q+ 保证每个队列都会接收到与其权重成比例的设备吞吐量的一部分，即使吞吐量波动，并且无论：设备参数、当前工作负载以及分配给队列的预算如何。

    • 最后一个预算独立属性（尽管一开始可能违反直觉）绝对是有益的，原因如下

      • 首先，对于任何比例份额调度器，与理想服务的最大偏差都与分配给队列的最大预算（切片）成正比。因此，BFQ 可以保持这种偏差严格，不仅是因为 B-WF2Q+ 的精确服务，还因为 BFQ 不需要 向队列分配更大的预算，以使队列获得更高的设备吞吐量分数。

      • 其次，对于每个进程（队列），BFQ 可以自由选择最适合进程需求或最能利用进程 I/O 模式的预算。特别是，BFQ 使用一个简单的反馈循环算法更新队列预算，该算法可以在提供严格的延迟保证给时间敏感型应用的同时，实现高吞吐量。当服务中的队列过期时，该算法会计算该队列的下一个预算，以便

        • 让较大的预算最终分配给与执行顺序 I/O 的 I/O 密集型应用程序相关的队列：事实上，这些应用程序一旦获得设备访问权限，服务时间越长，吞吐量就越高。

        • 让较小的预算最终分配给与时间敏感型应用程序相关的队列（它们通常执行零星且较短的 I/O），因为分配给等待服务的队列的预算越小，B-WF2Q+ 服务该队列的速度就越快（[2] 中的第 3.3 节）。

  • 如果多个进程同时竞争设备，但所有进程和组的权重相同，那么 BFQ 可以保证预期的吞吐量分配，而不会让设备空闲。它使用抢占代替。因此，在这种常见情况下，吞吐量会高得多。

  • ioprio 类按照严格的优先级顺序进行服务，即，只要存在更高优先级的队列，就不会服务较低优先级的队列。在同一类别的队列中，带宽按照每个队列的权重比例进行分配。但是，会为 Idle 类保证非常少的额外带宽，以防止其饥饿。

3. BFQ 的可调参数是什么，以及如何正确配置 BFQ？

大多数 BFQ 可调参数会影响服务保证（基本上是延迟和公平性）和吞吐量。有关如何在服务保证和吞吐量之间选择所需权衡的完整详细信息，请参阅参数 slice_idle、strict_guarantees 和 low_latency。有关如何最大化吞吐量的详细信息，请参阅 slice_idle、timeout_sync 和 max_budget。其他与性能相关的参数是从 CFQ 继承而来，并且主要为了与 CFQ 兼容而保留。到目前为止，在 BFQ 中更改后者的参数后，尚未报告任何性能改进。

特别是，下面的可调参数 back_seek-max、back_seek_penalty、fifo_expire_async 和 fifo_expire_sync 与 CFQ 中的相同。它们的描述只是从 CFQ 的描述中复制而来。slice_idle 描述中的一些考虑因素也是从 CFQ 中复制而来。

每个进程的 ioprio 和权重

除非使用 cgroups 接口（请参阅“4. BFQ 组调度”），否则只能通过 I/O 优先级间接为进程分配权重，并且根据关系：weight = (IOPRIO_BE_NR - ioprio) * 10。

请注意，如果设置了 low-latency，则 BFQ 会自动提高与交互式和软实时应用程序相关的队列的权重。如果您需要/想要控制权重，请取消设置此可调参数。

slice_idle

此参数指定当某些同步 BFQ 队列变为空时，BFQ 应该为空闲下一个 I/O 请求的时间。默认情况下，slice_idle 是一个非零值。空闲具有双重目的：提高吞吐量并确保遵守所需的吞吐量分配（请参阅 BFQ 工作方式的描述，如果需要，请参阅那里引用的论文）。

对于吞吐量而言，在高度寻道介质（如单轴 SATA/SAS 磁盘）上，空闲非常有帮助，在这种介质上，我们可以减少整体寻道次数并看到吞吐量得到改善。

将 slice_idle 设置为 0 将删除队列上的所有空闲，并且在更快的存储设备（如硬件 RAID 配置中的多个 SATA/SAS 磁盘）以及具有内部命令队列（和并行性）的基于闪存的存储上，应该会看到整体吞吐量得到改善。

因此，根据存储和工作负载，将 slice_idle=0 设置为 0 可能很有用。一般来说，对于 SATA/SAS 磁盘和 SATA/SAS 磁盘的软件 RAID，保持启用 slice_idle 应该很有用。对于在单个 LUN（基于主机的硬件 RAID 控制器或存储阵列）后面有多个轴的任何配置，或使用基于闪存的快速存储，将 slice_idle=0 设置为 0 可能会最终获得更好的吞吐量和可接受的延迟。

但是，在存在差异化权重或差异化 I/O 请求长度的情况下，需要空闲来强制执行服务保证。要了解原因，假设给定的 BFQ 队列 A 必须为每个为另一个队列 B 服务的请求提供多个 I/O 请求。空闲确保如果 A 在变空后稍微发出一个新的 I/O 请求，则不会在中间分派 B 的任何请求，因此 A 不会失去在分派 B 的下一个请求之前分派多个请求的可能性。请注意，空闲仅在 I/O 请求分派方面保证对队列进行所需的差异化处理。要保证实际的服务顺序然后与分派顺序对应，还必须设置 strict_guarantees 可调参数。

空闲有一个重要的负面影响：除了上述也有利于吞吐量的情况外，空闲会严重影响吞吐量。一个重要的情况是随机工作负载。由于这个问题，当空闲对吞吐量也没有好处时（如第 2 节所述），BFQ 倾向于尽可能避免空闲。由于这种行为，以及为 strict_guarantees 可调参数描述的进一步问题，短期服务保证可能会偶尔被违反。并且，在某些情况下，这些保证可能比保证最大吞吐量更重要。例如，在视频播放/流式传输中，非常低的丢帧率可能比最大吞吐量更重要。在这些情况下，请考虑设置 strict_guarantees 参数。

slice_idle_us

以微秒为单位控制与 slice_idle 相同的调优参数。可以使用任一可调参数来设置空闲行为。之后，另一个可调参数将反映 sysfs 中新设置的值。

strict_guarantees

如果设置此参数（默认值：未设置），则 BFQ

  • 当服务中的队列变为空时始终执行空闲；

  • 强制设备一次服务一个 I/O 请求，仅当没有未完成的请求时才分派新请求。

在存在差异化的权重或 I/O 请求大小的情况下，需要上述两个条件来保证每个 BFQ 队列都获得其分配的带宽份额。需要第一个条件的原因在 slice_idle 可调参数的描述中进行了解释。需要第二个条件是因为所有现代存储设备都会对内部排队的请求进行重新排序，这可能会轻易破坏 I/O 调度程序强制执行的服务保证。

设置 strict_guarantees 显然可能会影响吞吐量。

back_seek_max

这指定了以 Kbytes 为单位给出的向后寻道的最大“距离”。距离是指从当前磁头位置到向后方向的扇区的空间量。

此参数允许调度程序预测“向后”方向的请求，并将其视为“下一个”，如果它们与当前磁头位置的距离在此距离内。

back_seek_penalty

此参数用于计算向后寻道的成本。如果请求的向后距离仅为“向前”请求的 1/back_seek_penalty，则认为两个请求的寻道成本是等效的。

因此，调度程序不会偏向一个或另一个请求（否则调度程序将偏向向前请求）。back_seek_penalty 的默认值为 2。

fifo_expire_async

此参数用于设置异步请求的超时时间。此参数的默认值为 250 毫秒。

fifo_expire_sync

此参数用于设置同步请求的超时时间。此参数的默认值为 125 毫秒。为了支持同步请求而不是异步请求，此值应相对于 fifo_expire_async 减少。

low_latency

此参数用于启用/禁用 BFQ 的低延迟模式。默认情况下，启用低延迟模式。如果启用，则会优先考虑交互式和软实时应用程序，并体验较低的延迟，如 BFQ 工作方式的描述中更详细地解释的那样。

如果您需要完全控制带宽分配，请禁用此模式。事实上，如果启用此模式，BFQ 会自动增加特权应用程序的带宽份额，作为保证其较低延迟的主要手段。

此外，正如本文档开头所强调的那样，如果您的唯一目标是实现高吞吐量，请禁用此模式。事实上，相对于其余应用程序优先考虑某些应用程序的 I/O 可能会导致吞吐量降低。为了在非旋转设备上实现尽可能高的吞吐量，可能还需要将 slice_idle 设置为 0（代价是放弃对公平性和低延迟的任何有力保证）。

timeout_sync

一旦选中任务（队列）进行服务，可以分配给任务（队列）的最大设备时间量。在寻道成本较高的设备上，增加此时间通常会增加最大吞吐量。另一方面，增加此时间会使短期带宽和延迟保证的粒度变粗，尤其是当以下参数设置为零时。

max_budget

一旦 BFQ 队列投入使用，可以为该队列提供的最大服务量（以扇区为单位），当然是在上述超时的限制内。根据算法描述中所述，较大的值会使吞吐量与发出的顺序 I/O 请求的百分比成比例地增加。较大值的代价是它们会使短期带宽和延迟保证的粒度变粗。

默认值为 0，它启用自动调整：BFQ 根据估计的峰值速率，将 max_budget 设置为在 timeout_sync 期间可以服务的最大扇区数。

对于特定设备，一些用户偶尔报告说，通过显式设置 max_budget 可以达到更高的吞吐量，即将 max_budget 设置为大于 0 的值。特别是，他们将 max_budget 设置为高于 BFQ 通过自动调整设置的值。实现此目标的另一种方法是仅增加 timeout_sync 的值，而保持 max_budget 等于 0。

4. 使用 BFQ 进行组调度

BFQ 支持 cgroups-v1 和 cgroups-v2 IO 控制器，即 blkio 和 io。特别是，BFQ 支持基于权重的比例共享。要激活 cgroups 支持，请设置 BFQ_GROUP_IOSCHED。

4-1 提供的服务保证

对于 BFQ，比例共享意味着根据组权重对设备带宽进行真正的比例共享。例如，权重为 200 的组获得的带宽是权重为 100 的组的两倍，而不仅仅是两倍的时间。

BFQ 支持任何深度的层次结构（组树）。带宽在组和进程之间以预期的方式分配：对于每个组，该组的子项根据其权重共享该组的全部带宽。特别是，这意味着，对于每个叶子组，该组的每个进程都获得整个组带宽的相同份额，除非修改了该进程的 ioprio。

如果为组提供带宽保证会过度降低吞吐量，则组的资源共享保证可能会部分或完全从带宽切换到时间。此切换是按进程发生的：如果叶子组的某个进程以接收其带宽份额的方式提供服务会导致吞吐量损失，则 BFQ 将切换回仅基于时间的比例共享来服务该进程。

4-2 接口

要使用 BFQ 获取给定设备的带宽的比例共享，BFQ 当然必须是该设备的活动调度程序。

在每个组目录中，与 BFQ 特定的 cgroup 参数和统计信息关联的文件名以“bfq.”前缀开头。因此，对于 cgroups-v1 或 cgroups-v2，BFQ 特定文件的完整前缀是“blkio.bfq.”或“io.bfq.”。例如，用于设置组的 BFQ 权重的组参数是 blkio.bfq.weight 或 io.bfq.weight。

至于 cgroups-v1（blkio 控制器），由 bfq 创建并保持最新的统计信息文件的确切集合取决于是否设置了 CONFIG_BFQ_CGROUP_DEBUG。如果已设置，则 bfq 将创建 块 IO 控制器中记录的所有统计信息文件。相反，如果未设置 CONFIG_BFQ_CGROUP_DEBUG，则 bfq 仅创建以下文件

blkio.bfq.io_service_bytes
blkio.bfq.io_service_bytes_recursive
blkio.bfq.io_serviced
blkio.bfq.io_serviced_recursive

CONFIG_BFQ_CGROUP_DEBUG 的值会极大地影响 bfq 可以维持的最大吞吐量，因为更新 blkio.bfq.* 统计信息相当昂贵，特别是对于 CONFIG_BFQ_CGROUP_DEBUG 启用的某些统计信息。

参数

对于每个组，可以设置以下参数

weight

指定 cgroup 在其父组内的默认权重。可用值：1..1000（默认值：100）。

对于 cgroup v1，通过将值写入 blkio.bfq.weight 来设置。

对于 cgroup v2，通过将值写入 io.bfq.weight 来设置。（带有可选的前缀 default 和一个空格）。

在可调整部分开头描述的 ioprio 和权重之间的线性映射仍然有效，但是所有高于 IOPRIO_BE_NR*10 的权重都将映射到 ioprio 0。

请记住，如果设置了低延迟，则 BFQ 会自动提高与交互式和软实时应用程序关联的队列的权重。如果需要/想要控制权重，请取消设置此可调整项。

weight_device

指定 cgroup 的每个设备权重。语法为 minor:major weight。可以使用权重 0 重置为默认权重。

对于 cgroup v1，通过将值写入 blkio.bfq.weight_device 来设置。

对于 cgroup v2，文件名是 io.bfq.weight。

[1]

P. Valente, A. Avanzini, “BFQ 存储 I/O 调度程序的演变”, 第一届移动系统技术研讨会 (MST-2015) 会议论文集，2015 年 5 月。

http://algogroup.unimore.it/people/paolo/disk_sched/mst-2015.pdf

[2]

P. Valente 和 M. Andreolini，“通过 BFQ 磁盘 I/O 调度程序提高应用程序的响应能力”，第五届年度国际系统和存储会议 (SYSTOR '12) 会议论文集，2012 年 6 月。

稍加扩展的版本

http://algogroup.unimore.it/people/paolo/disk_sched/bfq-v1-suite-results.pdf

[3]

https://github.com/Algodev-github/S