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.jianshu.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
网友评论