BFQ (Budget Fair Queueing)详情

99%内容通过google翻译自 原文：https://www.kernel.org/doc/html/latest/block/bfq-iosched.html

1 简介

Linux块设施request层存在两种模型: 单队列（single-queue)和多队列（multi-queue)。single-queue IO调度器有三种：noop, deadline和cfq; multi-queue IO调度器有三种：bfq，kyber和mq-deadline。目前最新Linux内核中multi-queue模型已完全取代single-queue模型。

BFQ(Budget Fair Queueing)是一个按比例共享存储资源的IO调度器, 除了支持cgroups（blkio或者io控制器）之外，BFQ的主要功能还包括：

1. 与CFQ按时间片分配带宽不同，BFQ按预算（服务数据量，扇区为单位）在进程或者组之间分配带宽（在需要时切换回时间分配，以保持高吞吐量）；

2. 保证对系统和应用程序的快速响应，以及软实时应用程序（如音视频播放器）的低推迟；

2 BFQ适用场景

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

2.1 保证交互式应用的低推迟

不论实际的后端工作量如何，BFQ都会保证，对于交互式任务，存储设施实际上就像闲置一样响应。 例如，即便正在执行以下一个或者多个后端工作负载：

1 正在读取，写入或者复制一个或者多个大文件

2 正在被编译大型工程

3 一个或者多个虚拟机正在执行I / O

4 正在进行软件升级

5 索引守护程序正在扫描文件系统并升级其数据库

启动应用程序或者从应用程序内部加载文件所花费的时间大约与存储设施处于空闲状态相同。相比之下，在相同条件下使用CFQ，NOOP或者DEADLINE，应用程序会遇到高推迟，甚至在后端工作负载终止之前（甚至在SSD上）也变得无响应。

2.2 保证软实时应用的低推迟

而且，无论后端I / O工作负载如何，诸如音频和视频播放器/流媒体之类的软实时应用程序都具备低推迟和低丢帧率。 因而，不论后端工作负载多高，这些应用程序几乎不会出现任何故障。

2.3 加快代码开发任务的速度

假如碰巧并行执行少量额外的工作负载，那么BFQ会比CFQ，NOOP或者DEADLINE更快地执行典型代码开发任务（编译，签出，合并等）中与I / O相关的组件。

2.4 提高吞吐量

在测试硬盘的顺序读写负载时，BFQ实现的吞吐量比CFQ高出30％，比DEADLINE和NOOP高出150％。 在测试闪存的随机读写负载时，BFQ可以实现与其余调度程序大致相同的吞吐量。

2.5 保证严格的公平性，带宽和推迟

不论I/O密集型程序的工作负载类型和设施参数是啥，BFQ根据它们的权重按比例分配设施吞吐量（而不仅仅是时间片）。根据这些带宽保证，可以通过一个简单的公式来计算每个I/O请求严格推迟保证。假如未配置严格推迟服务保证，则BFQ切换到（仅）基于时间片的资源共享，否则会影响程序的吞吐量。

服务器系统受益于上述大部分特性。尤其是，无论服务器系统当前的工作负载多么繁重，BFQ都能保证：

1 音频和视频流具备零或者非常低的抖动和掉帧率；

2 Web页面快速检索；

3 应用程序数据的实时转储；

4 本地和远程访问服务器的响应能力。

3 工作方式

BFQ调度算法的大体结构和大部分代码CFQ借鉴于CFQ。

1?每个I/O进程都有其权重和bfq_queue队列。

2?每个bfq_queue（I/O进程）每次独占访问I/O设施期间，都只能传输指定预算量（按扇区计量）的数据。（即预算耗完后， BFQ算法重新调度新的bfq_queue访问I/O设施）

????2.1 当队列被调度访问I/O设施后，每次像I/O设施派发请求时，队列的budget预算都会减去request的大小。

? ? 2.2?仅当发生以下事件之一时，服务中队列才到期，即当前服务队列将被挂起：1）队列预算耗完，2）队列中无请求了，3）触发“预算超时（budget timeout）”。

? ? ? ? 2.2.1?预算超时可防止执行随机I / O的进程过长占用I/O设施而导致吞吐量明显降低。

? ? ? ? 2.2.2?实际上，和CFQ中一样，与发出同步请求的进程关联的队列为空后，不会立即被调度切 ? ? 换。相反，BFQ可能会使设施空闲(device idling)一会儿，以防进程会及时发出新的请求，这样新来的请求就会立即派发到I/O设施。对于带旋转磁头的设施和非排队闪存设施，假如进程进行同步和顺序I / O，设施空闲（device idling）通常有利于吞吐量的提高。此外，在BFQ下，设施空闲还有助于使发出同步请求的进程所需的吞吐量得到保证。

? ? ? ? ? ? 2.2.2.1?关于出于服务保证考虑的空闲（device idling）机制，假如多个进程同时竞争访问设施，但是所有进程和组的权重都相同，则BFQ可以保证预期的吞吐量分配而无需使设施空闲。因而，在这种常见情况下，吞吐量会尽可能高。

? ? ? ? ? ? 2.2.2.2?在具备NCQ（Native Command Queue）的基于闪存的设施中，设施空闲则不利于吞吐量的提高。因而，对于这些设施，BFQ仅在需要严格服务保证（即保证低推迟或者公平）时才执行空闲。在这些情况下，总体吞吐量可能不是最佳的。当前没有处理方案可以在具备内部队列的设施上提供强大的服务保证和最佳吞吐量。

? ? 2.3?假如启用了低推迟模式（默认配置），则BFQ会执行少量特殊的试探法（启发式规则）来检测交互式和软实时应用程序（例如，视频或者音频播放器/流媒体）并减少其推迟。 为实现此目标而采取的最重要的措施是：不再公平分配带宽，而为这些应用程序分配相对多的带宽。BFQ为赋予这些队列特权而采取的措施简称为“提权”。尤其是，BFQ为交互式应用程序提供了较温和的提权形式，为软实时应用程序提供了更强的提权形式。

? ? 2.4?BFQ自动取消“突发队列群（a burst of queue creations）”的idle机制（device idle: 即便当前请求队列空了，宁愿不调度切换当前服务队列，由于旋转磁头耗时太长，等待磁头移动到另一个进程请求的指定位置的代价，相对重新调度切换的代价大一点）。实际上，这些“突发队列群”一般属于需要高吞吐量的应用程序，例如systemd或者git grep。

? ? 2.5?和CFQ相似，BFQ合并执行交错I / O的队列，即合并多个执行随机请求的进程的队列，假如合并的话，该I / O大多变成顺序的。然而与CFQ不同的是，BFQ通过一种更具方应性（a more reactive mechanism）的机制（称为“早期队列合并”（EQM））来实现此目标。 CFQ通过抢占机制以获取高吞吐量，EQM在检测交错的I / O（协作进程）时反应灵敏，使得BFQ也可以通过队列合并来实现高吞吐量。 因而，EQM是通过交错的I / O实现高吞吐量的统一机制。

? ? 2.6?队列是根据WF2Q +的一个变体B-WF2Q +进行调度的，并使用加强的rb-tree实现，使得调度算法总体复杂度为O（log N）。B-WF2Q +也能用于分层调度（hierarchical scheduling）。(B-WF2Q+完全没弄明白)

? ? 2.7?最后一个属性，预算独立（虽然可能首先是违背直觉的）绝对是有利的，起因如下：

? ? ? ? 2.7.1?首先，对于任何比例共享调度器，相对于理想服务的最大偏差与分配给队列的最大预算（片段）成比例。结果，BFQ可以使此偏差变得更小，这不仅是由于B-WF2Q +算法的精确性，而且由于BFQ不需要为队列分配更大的预算以使该队列取得更高的吞吐量

? ? ? ? 2.7.2?其次，对于每个进程（队列），BFQ可以自由选择最适合进程需求或者最佳利用进程I / O模式的预算。尤其是，BFQ使用简单的反馈循环算法升级队列预算，该算法可实现高吞吐量，同时仍为时间敏感型应用程序提供严格推迟保证。当服务中队列到期时，此算法将计算队列的下一个预算，以便：

? ? ? ? ? ? 2.7.2.1 最终将大笔预算分配给与执行密集顺序I / O的应用程序相关联的队列：实际上，一旦该队列调度到I/O设施,该队列的服务时间越长，吞吐量就越高

? ? ? ? ? ? 2.7.2.2 最终将小预算分配给与时间敏感性应用程序关联的队列（通常执行零星的和短时间的I / O），由于分配给等待服务的队列的预算越小，B-WF2Q +将越早地为其队列服务

3?假如多个进程同时竞争设施，但所有进程和组的权重相同，则BFQ可以保证预期的吞吐量分配，而不使用device idling机制。相反它使用抢占。在这种常见情况下，吞吐量会更高。

4?严格遵照ioprio优先级提供服务，即只需存在较高优先级的队列，就不为较低优先级的队列提供服务。在同一类队列中，带宽根据每个队列的权重按比例分配。不过为防止idle ioprio类饿死，依然为其空闲类保留额外的一些带宽。

4 BFQ参数调优

大多数BFQ可调参数都会影响服务保证（基本上是推迟和公平性）和吞吐量。 有关如何在二者之间折衷取舍请参考slice_idle，strict_guarantees和low_latency参数。有关如何最大程度提高吞吐量，?请参考slice_idle，timeout_sync和max_budget参数。其余与性能相关的参数已继承，并且主要是为了与CFQ兼容而保留的。 到目前为止，在BFQ中更改后一个参数后，尚未报告性能改进。

特别是，下面的back_seek-max，back_seek_penalty，fifo_expire_async和fifo_expire_sync可调参数与CFQ中的相同。 它们只是从CFQ的文档中复制而来。slice_idle形容中的少量注意事项也是从CFQ复制来的。

4.1?per-process ioprio and weight

以下公式根据ioprio（I / O优先级）计算分配给I/O进程的权重：

weight =（IOPRIO_BE_NR-ioprio）* 10

请注意，假如设置了low-latency参数，则BFQ会自动提高交互式和软实时应用程序的队列的权重。假如需要控制权重，请取消设置low-latency参数。

4.2 slice_idle

此参数指定当某些同步BFQ队列为空时，BFQ对于下一个I / O请求应空闲的时间。 默认情况下，slice_idle为非零值。 空闲（Idling）具备双重目的：提高吞吐量并确保所需的吞吐量分配。

至于吞吐量，空转在诸如单轴SATA / SAS磁盘等寻道代价较高的介质上非常有用，我们可以通过减少寻道的总数从而提高吞吐量。

将slice_idle设置为0将取消队列上的所有空闲，从而在整体上提高了更快的存储设施的吞吐量，例如硬件RAID配置中的多个SATA / SAS磁盘，以及具备内部命令队列（和并行性）的基于闪存的存储。

因而，根据存储介质和工作负载类型，设置slice_idle = 0可能会很有用。 通常，对于SATA / SAS磁盘和启用slice_idle的SATA / SAS磁盘的软件RAID很有用。 对于单个LUN（基于主机的硬件RAID控制器或者用于存储阵列）后面有多个主轴的任何配置，或者具备基于闪存的快速存储，设置slice_idle = 0可能会带来更好的吞吐量和可接受的推迟。

但是，在权重不同或者I / O请求长度不同的情况下，为了使服务保证得到强制执行，有必要进行空闲。 要理解起因，假设给定的BFQ队列A必需为每个服务于另一个队列B的请求获取多个I / O请求。空闲可确保，假如A在变空后稍有新的I / O请求，则没有 B在中间调度，因而A不会失去在调度下一个请求B之前取得多个请求的可能性。请注意，空闲仅在I / O请求派发方面保证了所需的队列差异解决。为了保证明际的服务顺序与派发顺序一致，还必需设置strict_guarantees可调参数。

空闲（idling）有一个重要的弊端：除了上述对吞吐量也有好处的情况之外，空转会严重影响吞吐量。一个重要的例子是随机工作量。因为这个问题，当对吞吐量也没有好处时，BFQ倾向于尽可能避免空闲。因为此行为，以及为strict_guarantee可调项形容的其余问题，有时可能会违背短期服务保证。 并且，在某些情况下，这些保证可能比保证最大吞吐量更为重要。 例如，在视频播放/流式传输中，非常低的丢帧率可能比最大吞吐量更重要。在这些情况下，请考虑设置strict_guarantees参数

4.3 slice_idle_us

与slice_idle作用相同，但以微秒为单位。它们任意一个均可用于设置空闲行为，之后另一个参数将会在sysfs中反映新设置的值。

4.4?strict_guarantees

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

????1 当服务中的队列为空时，总是执行idling；

?????2通过仅在没有未完成的请求时才调度新请求，来强制设施每次只服务一个I / O请求。

在存在不同的权重或者I / O请求大小的情况下，需要同时满足上述两个条件才能确保每个BFQ队列得到其分配的带宽份额。出于对slice_idle可调参数的形容中说明的起因，需要第一个条件。 之所以需要第二个条件，是由于所有现代存储设施都会对内部排队的请求进行重新排序，这可能会轻易破坏I / O调度程序所实施的服务保证。

设置strict_guarantee可能会显著影响吞吐量。

4.5?back_seek_max

这指定了以KB为单位的向后搜索的最大“距离”。距离是从当前磁头位置到距离远的扇区之间的距离。

此参数允许调度程序在“向后”方向上预测请求，假如它们在距当前头部位置的距离内，则将它们视为待派发的“下一个”请求。

4.6?back_seek_penalty

此参数用于计算反向搜索的成本。假如请求的向后距离仅是“前”请求的1 / back_seek_penalty，则将两个请求的寻觅成本视为等效。

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

4.7?fifo_expire_async

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

4.8?fifo_expire_sync

该参数用于设置同步请求的超时时间。缺省值为124ms。为了使同步请求优先于异步请求，该值会小于fifo_expire_async。

4.9?low_latency

此参数用于启用/禁用BFQ的低推迟模式。 默认情况下，启用低推迟模式。假如启用了此功能，则交互式和软实时应用程序将取得特权，并具备较低的推迟。

假如需要完全控制带宽分配，请禁用此模式。实际上，假如启用了此功能，BFQ会自动添加特权应用程序的带宽份额，这是保证特权应用程序较低推迟的主要手段。

假如您的唯一目标是实现高吞吐量，请禁用此模式。实际上，为某些应用程序的I / O赋予特权可能会导致吞吐量较低。为了在非旋转设施上实现最大可能的吞吐量，也可能需要将slice_idle设置为0（以牺牲公平性和低延时的严格保证为代价）。

4.10?timeout_sync

选择任务进行服务后，可以赋予任务（队列）的最大设施服务时间。在寻道成本较高的设施上，添加时间通常会添加最大吞吐量。但另一方面，添加此时间会粗化短期带宽和等待时间保证的粒度，尤其是假如max_budget参数设置为零时。

4.11?max_budget

设置可以提供给BFQ队列的最大服务量（以扇区为单位）（当然在timeout_sync超时范围内）。较大的值与按顺序发出的I / O请求的百分比成比例地添加了吞吐量。 较大值的代价是它们会使短期带宽和推迟保证的粒度变粗。

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

对于特定设施，有些客户偶尔会报告通过显式设置max_budget（即，将max_budget设置为大于0的值）达到更高的吞吐量。特别是，他们设置的max_budget值比BFQ自动调整的值还要高。实现此目标的另一种方法是只添加timeout_sync的值，而使max_budget等于0。

4.12?weights

只读参数，用于显示当前活动的BFQ队列的权重。

5 参考文献

1?https://lwn.net/Articles/738449/

2?https://algo.ing.unimo.it/people/paolo/disk_sched/

3 Improving Application Responsiveness with the BFQ Disk I/O Scheduler: ?https://core.ac.uk/download/pdf/54000085.pdf

4?https://kernel.dk/blk-mq.pdf

5?https://www.songma.com/p/3b7d1d478c01

6?https://www.kernel.org/doc/html/latest/block/bfq-iosched.html

7 Evolution of the BFQ Storage-I/O Scheduler: https://algo.ing.unimo.it/people/paolo/disk_sched/mst-2015.pdf

8 New version of BFQ, benchmark suite and experimental results: https://algo.ing.unimo.it/people/paolo/disk_sched/bf1-v1-suite-results.pdf

9 High Throughput Disk Scheduling with Fair Bandwidth Distribution: https://algo.ing.unimo.it/people/paolo/disk_sched/bfq-techreport.pdf?