BFQ (Budget Fair Queueing)

BFQ是一个比例份额I/O调度器，具有一些额外的低延迟能力。除了cgroups支持（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 us（笔记本电脑的旧CPU；使用简单的代码检测以及S套件[1]的throughput-sync.sh脚本在性能分析模式下进行测量）。为了将此结果放入上下文中，blk-mq中最轻量级的I/O调度器mq-deadline的总的、单锁保护的、每个请求的执行时间为0.7 us（mq-deadline约为800 LOC，而BFQ约为10500 LOC）。

调度开销进一步限制了CPU可以处理的最大IOPS（已经受到其余I/O堆栈执行的限制）。为了给出BFQ限制的概念，在速度较慢或一般的CPU上，以下是三种不同CPU上BFQ的限制，分别是在一台普通的笔记本电脑、一台旧台式机和一个廉价的嵌入式系统上，如果启用了完全分层支持（即设置了CONFIG_BFQ_GROUP_IOSCHED），但未设置CONFIG_BFQ_CGROUP_DEBUG（第4-2节）： - 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都能保证

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

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

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

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

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，该I/O变得主要是顺序的。与CFQ不同，BFQ通过一种更具反应性的机制来实现此目标，该机制称为早期队列合并（EQM）。EQM在检测交错I/O（协作进程）方面非常灵敏，从而使BFQ可以通过队列合并来实现高吞吐量，即使对于CFQ需要一种不同的机制（抢占）来获得高吞吐量的队列也是如此。因此，EQM是一种用于通过交错I/O实现高吞吐量的统一机制。

    • 根据WF2Q+的一种变体（名为B-WF2Q+）调度队列，并使用增强的rb树来实现，以保留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]中的Subsec 3.3）。

  • 如果多个进程同时争用设备，但所有进程和组的权重相同，那么BFQ保证预期的吞吐量分配，而无需使设备空闲。而是使用抢占。然后在这种常见情况下，吞吐量会高得多。

  • ioprio类以严格的优先级顺序提供服务，即只要有较高优先级的队列，较低优先级的队列就不会获得服务。在同一类队列中，带宽的分配与每个队列的权重成比例。但是，为了防止空闲类饿死，保证了非常小的额外带宽。

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可能很有用。通常，对于SATA / SAS磁盘和SATA / SAS磁盘的软件RAID，保持slice_idle启用应该很有用。对于任何在单个LUN后面具有多个轴的配置（基于主机的硬件RAID控制器或存储阵列）或具有基于闪存的快速存储的配置，将slice_idle = 0可能会导致更好的吞吐量和可接受的延迟。

但是，如果存在差异化的权重或差异化的I/O请求长度，则空闲对于强制实施服务保证是必要的。要了解原因，请假设给定的BFQ队列A必须为每个为另一个队列B服务的请求提供多个I/O请求。空闲确保，如果A在变为空之后不久就提出了新的I/O请求，则不会在中间调度B的请求，因此A不会失去在调度B的下一个请求之前调度多个请求的可能性。请注意，空闲仅在I/O请求调度的范围内保证队列的期望差异化处理。要保证实际的服务顺序随后与调度顺序对应，还必须设置strict_guarantees可调参数。

空闲也有一个重要的不利方面：除了上述对吞吐量也有益的情况外，空闲可能会严重影响吞吐量。一个重要的情况是随机工作负载。由于此问题，BFQ倾向于尽可能避免空闲，因为它对吞吐量也没有好处（如第2节所述）。由于这种行为，以及为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

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

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

back_seek_penalty

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

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

fifo_expire_async

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

fifo_expire_sync

此参数用于设置同步请求的超时。此参数的默认值为125ms。如果需要优先于异步请求的同步请求，则应相对于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设置为高于BFQ通过自动调整设置的值。特别是，他们已将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保持最新的stat文件的确切集取决于是否设置了CONFIG_BFQ_CGROUP_DEBUG。如果设置了该选项，则bfq会创建块IO控制器中记录的所有stat文件。相反，如果未设置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。

请记住，如果设置了low-latency，则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调度器提高应用程序响应能力”，第5届年度国际系统和存储会议（SYSTOR '12）论文集，2012年6月。

略有扩展的版本

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

[3]

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