요약·해설과 원문, 전문 번역을 서로 분리했습니다. API 이름, symbol, source path는 원문 표기를 사용합니다.
1. 요약·해설
원문의 핵심 논리와 kernel programming 관점의 보충 설명입니다. 아래의 전문 번역과는 별도로 작성했습니다.
2. 영어 원문 전체
번역 기준이 된 Linux v6.18.37 원문입니다. 줄 번호는 이 버전의 파일 좌표입니다.
원문 전체 펼치기
==========================
BFQ (Budget Fair Queueing)
==========================
BFQ is a proportional-share I/O scheduler, with some extra
low-latency capabilities. In addition to cgroups support (blkio or io
controllers), BFQ's main features are:
- BFQ guarantees a high system and application responsiveness, and a
low latency for time-sensitive applications, such as audio or video
players;
- BFQ distributes bandwidth, not just time, among processes or
groups (switching back to time distribution when needed to keep
throughput high).
In its default configuration, BFQ privileges latency over
throughput. So, when needed for achieving a lower latency, BFQ builds
schedules that may lead to a lower throughput. If your main or only
goal, for a given device, is to achieve the maximum-possible
throughput at all times, then do switch off all low-latency heuristics
for that device, by setting low_latency to 0. See Section 3 for
details on how to configure BFQ for the desired tradeoff between
latency and throughput, or on how to maximize throughput.
As every I/O scheduler, BFQ adds some overhead to per-I/O-request
processing. To give an idea of this overhead, the total,
single-lock-protected, per-request processing time of BFQ---i.e., the
sum of the execution times of the request insertion, dispatch and
completion hooks---is, e.g., 1.9 us on an Intel Core [email protected]
(dated CPU for notebooks; time measured with simple code
instrumentation, and using the throughput-sync.sh script of the S
suite [1], in performance-profiling mode). To put this result into
context, the total, single-lock-protected, per-request execution time
of the lightest I/O scheduler available in blk-mq, mq-deadline, is 0.7
us (mq-deadline is ~800 LOC, against ~10500 LOC for BFQ).
Scheduling overhead further limits the maximum IOPS that a CPU can
process (already limited by the execution of the rest of the I/O
stack). To give an idea of the limits with BFQ, on slow or average
CPUs, here are, first, the limits of BFQ for three different CPUs, on,
respectively, an average laptop, an old desktop, and a cheap embedded
system, in case full hierarchical support is enabled (i.e.,
CONFIG_BFQ_GROUP_IOSCHED is set), but CONFIG_BFQ_CGROUP_DEBUG is not
set (Section 4-2):
- Intel i7-4850HQ: 400 KIOPS
- AMD A8-3850: 250 KIOPS
- ARM CortexTM-A53 Octa-core: 80 KIOPS
If CONFIG_BFQ_CGROUP_DEBUG is set (and of course full hierarchical
support is enabled), then the sustainable throughput with BFQ
decreases, because all blkio.bfq* statistics are created and updated
(Section 4-2). For BFQ, this leads to the following maximum
sustainable throughputs, on the same systems as above:
- Intel i7-4850HQ: 310 KIOPS
- AMD A8-3850: 200 KIOPS
- ARM CortexTM-A53 Octa-core: 56 KIOPS
BFQ works for multi-queue devices too.
.. The table of contents follow. Impatients can just jump to Section 3.
.. CONTENTS
1. When may BFQ be useful?
1-1 Personal systems
1-2 Server systems
2. How does BFQ work?
3. What are BFQ's tunables and how to properly configure BFQ?
4. BFQ group scheduling
4-1 Service guarantees provided
4-2 Interface
1. When may BFQ be useful?
==========================
BFQ provides the following benefits on personal and server systems.
1-1 Personal systems
--------------------
Low latency for interactive applications
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Regardless of the actual background workload, BFQ guarantees that, for
interactive tasks, the storage device is virtually as responsive as if
it was idle. For example, even if one or more of the following
background workloads are being executed:
- one or more large files are being read, written or copied,
- a tree of source files is being compiled,
- one or more virtual machines are performing I/O,
- a software update is in progress,
- indexing daemons are scanning filesystems and updating their
databases,
starting an application or loading a file from within an application
takes about the same time as if the storage device was idle. As a
comparison, with CFQ, NOOP or DEADLINE, and in the same conditions,
applications experience high latencies, or even become unresponsive
until the background workload terminates (also on SSDs).
Low latency for soft real-time applications
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Also soft real-time applications, such as audio and video
players/streamers, enjoy a low latency and a low drop rate, regardless
of the background I/O workload. As a consequence, these applications
do not suffer from almost any glitch due to the background workload.
Higher speed for code-development tasks
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
If some additional workload happens to be executed in parallel, then
BFQ executes the I/O-related components of typical code-development
tasks (compilation, checkout, merge, etc.) much more quickly than CFQ,
NOOP or DEADLINE.
High throughput
^^^^^^^^^^^^^^^
On hard disks, BFQ achieves up to 30% higher throughput than CFQ, and
up to 150% higher throughput than DEADLINE and NOOP, with all the
sequential workloads considered in our tests. With random workloads,
and with all the workloads on flash-based devices, BFQ achieves,
instead, about the same throughput as the other schedulers.
Strong fairness, bandwidth and delay guarantees
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
BFQ distributes the device throughput, and not just the device time,
among I/O-bound applications in proportion to their weights, with any
workload and regardless of the device parameters. From these bandwidth
guarantees, it is possible to compute a tight per-I/O-request delay
guarantees by a simple formula. If not configured for strict service
guarantees, BFQ switches to time-based resource sharing (only) for
applications that would otherwise cause a throughput loss.
1-2 Server systems
------------------
Most benefits for server systems follow from the same service
properties as above. In particular, regardless of whether additional,
possibly heavy workloads are being served, BFQ guarantees:
* audio and video-streaming with zero or very low jitter and drop
rate;
* fast retrieval of WEB pages and embedded objects;
* real-time recording of data in live-dumping applications (e.g.,
packet logging);
* responsiveness in local and remote access to a server.
2. How does BFQ work?
=====================
BFQ is a proportional-share I/O scheduler, whose general structure,
plus a lot of code, are borrowed from CFQ.
- Each process doing I/O on a device is associated with a weight and a
`(bfq_)queue`.
- BFQ grants exclusive access to the device, for a while, to one queue
(process) at a time, and implements this service model by
associating every queue with a budget, measured in number of
sectors.
- After a queue is granted access to the device, the budget of the
queue is decremented, on each request dispatch, by the size of the
request.
- The in-service queue is expired, i.e., its service is suspended,
only if one of the following events occurs: 1) the queue finishes
its budget, 2) the queue empties, 3) a "budget timeout" fires.
- The budget timeout prevents processes doing random I/O from
holding the device for too long and dramatically reducing
throughput.
- Actually, as in CFQ, a queue associated with a process issuing
sync requests may not be expired immediately when it empties. In
contrast, BFQ may idle the device for a short time interval,
giving the process the chance to go on being served if it issues
a new request in time. Device idling typically boosts the
throughput on rotational devices and on non-queueing flash-based
devices, if processes do synchronous and sequential I/O. In
addition, under BFQ, device idling is also instrumental in
guaranteeing the desired throughput fraction to processes
issuing sync requests (see the description of the slice_idle
tunable in this document, or [1, 2], for more details).
- With respect to idling for service guarantees, if several
processes are competing for the device at the same time, but
all processes and groups have the same weight, then BFQ
guarantees the expected throughput distribution without ever
idling the device. Throughput is thus as high as possible in
this common scenario.
- On flash-based storage with internal queueing of commands
(typically NCQ), device idling happens to be always detrimental
to throughput. So, with these devices, BFQ performs idling
only when strictly needed for service guarantees, i.e., for
guaranteeing low latency or fairness. In these cases, overall
throughput may be sub-optimal. No solution currently exists to
provide both strong service guarantees and optimal throughput
on devices with internal queueing.
- If low-latency mode is enabled (default configuration), BFQ
executes some special heuristics to detect interactive and soft
real-time applications (e.g., video or audio players/streamers),
and to reduce their latency. The most important action taken to
achieve this goal is to give to the queues associated with these
applications more than their fair share of the device
throughput. For brevity, we call it just "weight-raising" the whole
sets of actions taken by BFQ to privilege these queues. In
particular, BFQ provides a milder form of weight-raising for
interactive applications, and a stronger form for soft real-time
applications.
- BFQ automatically deactivates idling for queues born in a burst of
queue creations. In fact, these queues are usually associated with
the processes of applications and services that benefit mostly
from a high throughput. Examples are systemd during boot, or git
grep.
- As CFQ, BFQ merges queues performing interleaved I/O, i.e.,
performing random I/O that becomes mostly sequential if
merged. Differently from CFQ, BFQ achieves this goal with a more
reactive mechanism, called Early Queue Merge (EQM). EQM is so
responsive in detecting interleaved I/O (cooperating processes),
that it enables BFQ to achieve a high throughput, by queue
merging, even for queues for which CFQ needs a different
mechanism, preemption, to get a high throughput. As such, EQM is a
unified mechanism to achieve a high throughput with interleaved
I/O.
- Queues are scheduled according to a variant of WF2Q+, named
B-WF2Q+, and implemented using an augmented rb-tree to preserve an
O(log N) overall complexity. See [2] for more details. B-WF2Q+ is
also ready for hierarchical scheduling, details in Section 4.
- B-WF2Q+ guarantees a tight deviation with respect to an ideal,
perfectly fair, and smooth service. In particular, B-WF2Q+
guarantees that each queue receives a fraction of the device
throughput proportional to its weight, even if the throughput
fluctuates, and regardless of: the device parameters, the current
workload and the budgets assigned to the queue.
- The last, budget-independence, property (although probably
counterintuitive in the first place) is definitely beneficial, for
the following reasons:
- First, with any proportional-share scheduler, the maximum
deviation with respect to an ideal service is proportional to
the maximum budget (slice) assigned to queues. As a consequence,
BFQ can keep this deviation tight, not only because of the
accurate service of B-WF2Q+, but also because BFQ *does not*
need to assign a larger budget to a queue to let the queue
receive a higher fraction of the device throughput.
- Second, BFQ is free to choose, for every process (queue), the
budget that best fits the needs of the process, or best
leverages the I/O pattern of the process. In particular, BFQ
updates queue budgets with a simple feedback-loop algorithm that
allows a high throughput to be achieved, while still providing
tight latency guarantees to time-sensitive applications. When
the in-service queue expires, this algorithm computes the next
budget of the queue so as to:
- Let large budgets be eventually assigned to the queues
associated with I/O-bound applications performing sequential
I/O: in fact, the longer these applications are served once
got access to the device, the higher the throughput is.
- Let small budgets be eventually assigned to the queues
associated with time-sensitive applications (which typically
perform sporadic and short I/O), because, the smaller the
budget assigned to a queue waiting for service is, the sooner
B-WF2Q+ will serve that queue (Subsec 3.3 in [2]).
- If several processes are competing for the device at the same time,
but all processes and groups have the same weight, then BFQ
guarantees the expected throughput distribution without ever idling
the device. It uses preemption instead. Throughput is then much
higher in this common scenario.
- ioprio classes are served in strict priority order, i.e.,
lower-priority queues are not served as long as there are
higher-priority queues. Among queues in the same class, the
bandwidth is distributed in proportion to the weight of each
queue. A very thin extra bandwidth is however guaranteed to
the Idle class, to prevent it from starving.
3. What are BFQ's tunables and how to properly configure BFQ?
=============================================================
Most BFQ tunables affect service guarantees (basically latency and
fairness) and throughput. For full details on how to choose the
desired tradeoff between service guarantees and throughput, see the
parameters slice_idle, strict_guarantees and low_latency. For details
on how to maximise throughput, see slice_idle, timeout_sync and
max_budget. The other performance-related parameters have been
inherited from, and have been preserved mostly for compatibility with
CFQ. So far, no performance improvement has been reported after
changing the latter parameters in BFQ.
In particular, the tunables back_seek-max, back_seek_penalty,
fifo_expire_async and fifo_expire_sync below are the same as in
CFQ. Their description is just copied from that for CFQ. Some
considerations in the description of slice_idle are copied from CFQ
too.
per-process ioprio and weight
-----------------------------
Unless the cgroups interface is used (see "4. BFQ group scheduling"),
weights can be assigned to processes only indirectly, through I/O
priorities, and according to the relation:
weight = (IOPRIO_BE_NR - ioprio) * 10.
Beware that, if low-latency is set, then BFQ automatically raises the
weight of the queues associated with interactive and soft real-time
applications. Unset this tunable if you need/want to control weights.
slice_idle
----------
This parameter specifies how long BFQ should idle for the next I/O
request, when certain sync BFQ queues become empty. By default
slice_idle is a non-zero value. Idling has a double purpose: boosting
throughput and making sure that the desired throughput distribution is
respected (see the description of how BFQ works, and, if needed, the
papers referred there).
As for throughput, idling can be very helpful on highly seeky media
like single spindle SATA/SAS disks where we can cut down on overall
number of seeks and see improved throughput.
Setting slice_idle to 0 will remove all the idling on queues and one
should see an overall improved throughput on faster storage devices
like multiple SATA/SAS disks in hardware RAID configuration, as well
as flash-based storage with internal command queueing (and
parallelism).
So depending on storage and workload, it might be useful to set
slice_idle=0. In general for SATA/SAS disks and software RAID of
SATA/SAS disks keeping slice_idle enabled should be useful. For any
configurations where there are multiple spindles behind single LUN
(Host based hardware RAID controller or for storage arrays), or with
flash-based fast storage, setting slice_idle=0 might end up in better
throughput and acceptable latencies.
Idling is however necessary to have service guarantees enforced in
case of differentiated weights or differentiated I/O-request lengths.
To see why, suppose that a given BFQ queue A must get several I/O
requests served for each request served for another queue B. Idling
ensures that, if A makes a new I/O request slightly after becoming
empty, then no request of B is dispatched in the middle, and thus A
does not lose the possibility to get more than one request dispatched
before the next request of B is dispatched. Note that idling
guarantees the desired differentiated treatment of queues only in
terms of I/O-request dispatches. To guarantee that the actual service
order then corresponds to the dispatch order, the strict_guarantees
tunable must be set too.
There is an important flip side to idling: apart from the above cases
where it is beneficial also for throughput, idling can severely impact
throughput. One important case is random workload. Because of this
issue, BFQ tends to avoid idling as much as possible, when it is not
beneficial also for throughput (as detailed in Section 2). As a
consequence of this behavior, and of further issues described for the
strict_guarantees tunable, short-term service guarantees may be
occasionally violated. And, in some cases, these guarantees may be
more important than guaranteeing maximum throughput. For example, in
video playing/streaming, a very low drop rate may be more important
than maximum throughput. In these cases, consider setting the
strict_guarantees parameter.
slice_idle_us
-------------
Controls the same tuning parameter as slice_idle, but in microseconds.
Either tunable can be used to set idling behavior. Afterwards, the
other tunable will reflect the newly set value in sysfs.
strict_guarantees
-----------------
If this parameter is set (default: unset), then BFQ
- always performs idling when the in-service queue becomes empty;
- forces the device to serve one I/O request at a time, by dispatching a
new request only if there is no outstanding request.
In the presence of differentiated weights or I/O-request sizes, both
the above conditions are needed to guarantee that every BFQ queue
receives its allotted share of the bandwidth. The first condition is
needed for the reasons explained in the description of the slice_idle
tunable. The second condition is needed because all modern storage
devices reorder internally-queued requests, which may trivially break
the service guarantees enforced by the I/O scheduler.
Setting strict_guarantees may evidently affect throughput.
back_seek_max
-------------
This specifies, given in Kbytes, the maximum "distance" for backward seeking.
The distance is the amount of space from the current head location to the
sectors that are backward in terms of distance.
This parameter allows the scheduler to anticipate requests in the "backward"
direction and consider them as being the "next" if they are within this
distance from the current head location.
back_seek_penalty
-----------------
This parameter is used to compute the cost of backward seeking. If the
backward distance of request is just 1/back_seek_penalty from a "front"
request, then the seeking cost of two requests is considered equivalent.
So scheduler will not bias toward one or the other request (otherwise scheduler
will bias toward front request). Default value of back_seek_penalty is 2.
fifo_expire_async
-----------------
This parameter is used to set the timeout of asynchronous requests. Default
value of this is 250ms.
fifo_expire_sync
----------------
This parameter is used to set the timeout of synchronous requests. Default
value of this is 125ms. In case to favor synchronous requests over asynchronous
one, this value should be decreased relative to fifo_expire_async.
low_latency
-----------
This parameter is used to enable/disable BFQ's low latency mode. By
default, low latency mode is enabled. If enabled, interactive and soft
real-time applications are privileged and experience a lower latency,
as explained in more detail in the description of how BFQ works.
DISABLE this mode if you need full control on bandwidth
distribution. In fact, if it is enabled, then BFQ automatically
increases the bandwidth share of privileged applications, as the main
means to guarantee a lower latency to them.
In addition, as already highlighted at the beginning of this document,
DISABLE this mode if your only goal is to achieve a high throughput.
In fact, privileging the I/O of some application over the rest may
entail a lower throughput. To achieve the highest-possible throughput
on a non-rotational device, setting slice_idle to 0 may be needed too
(at the cost of giving up any strong guarantee on fairness and low
latency).
timeout_sync
------------
Maximum amount of device time that can be given to a task (queue) once
it has been selected for service. On devices with costly seeks,
increasing this time usually increases maximum throughput. On the
opposite end, increasing this time coarsens the granularity of the
short-term bandwidth and latency guarantees, especially if the
following parameter is set to zero.
max_budget
----------
Maximum amount of service, measured in sectors, that can be provided
to a BFQ queue once it is set in service (of course within the limits
of the above timeout). According to what was said in the description of
the algorithm, larger values increase the throughput in proportion to
the percentage of sequential I/O requests issued. The price of larger
values is that they coarsen the granularity of short-term bandwidth
and latency guarantees.
The default value is 0, which enables auto-tuning: BFQ sets max_budget
to the maximum number of sectors that can be served during
timeout_sync, according to the estimated peak rate.
For specific devices, some users have occasionally reported to have
reached a higher throughput by setting max_budget explicitly, i.e., by
setting max_budget to a higher value than 0. In particular, they have
set max_budget to higher values than those to which BFQ would have set
it with auto-tuning. An alternative way to achieve this goal is to
just increase the value of timeout_sync, leaving max_budget equal to 0.
4. Group scheduling with BFQ
============================
BFQ supports both cgroups-v1 and cgroups-v2 io controllers, namely
blkio and io. In particular, BFQ supports weight-based proportional
share. To activate cgroups support, set BFQ_GROUP_IOSCHED.
4-1 Service guarantees provided
-------------------------------
With BFQ, proportional share means true proportional share of the
device bandwidth, according to group weights. For example, a group
with weight 200 gets twice the bandwidth, and not just twice the time,
of a group with weight 100.
BFQ supports hierarchies (group trees) of any depth. Bandwidth is
distributed among groups and processes in the expected way: for each
group, the children of the group share the whole bandwidth of the
group in proportion to their weights. In particular, this implies
that, for each leaf group, every process of the group receives the
same share of the whole group bandwidth, unless the ioprio of the
process is modified.
The resource-sharing guarantee for a group may partially or totally
switch from bandwidth to time, if providing bandwidth guarantees to
the group lowers the throughput too much. This switch occurs on a
per-process basis: if a process of a leaf group causes throughput loss
if served in such a way to receive its share of the bandwidth, then
BFQ switches back to just time-based proportional share for that
process.
4-2 Interface
-------------
To get proportional sharing of bandwidth with BFQ for a given device,
BFQ must of course be the active scheduler for that device.
Within each group directory, the names of the files associated with
BFQ-specific cgroup parameters and stats begin with the "bfq."
prefix. So, with cgroups-v1 or cgroups-v2, the full prefix for
BFQ-specific files is "blkio.bfq." or "io.bfq." For example, the group
parameter to set the weight of a group with BFQ is blkio.bfq.weight
or io.bfq.weight.
As for cgroups-v1 (blkio controller), the exact set of stat files
created, and kept up-to-date by bfq, depends on whether
CONFIG_BFQ_CGROUP_DEBUG is set. If it is set, then bfq creates all
the stat files documented in
Documentation/admin-guide/cgroup-v1/blkio-controller.rst. If, instead,
CONFIG_BFQ_CGROUP_DEBUG is not set, then bfq creates only the files::
blkio.bfq.io_service_bytes
blkio.bfq.io_service_bytes_recursive
blkio.bfq.io_serviced
blkio.bfq.io_serviced_recursive
The value of CONFIG_BFQ_CGROUP_DEBUG greatly influences the maximum
throughput sustainable with bfq, because updating the blkio.bfq.*
stats is rather costly, especially for some of the stats enabled by
CONFIG_BFQ_CGROUP_DEBUG.
Parameters
----------
For each group, the following parameters can be set:
weight
This specifies the default weight for the cgroup inside its parent.
Available values: 1..1000 (default: 100).
For cgroup v1, it is set by writing the value to `blkio.bfq.weight`.
For cgroup v2, it is set by writing the value to `io.bfq.weight`.
(with an optional prefix of `default` and a space).
The linear mapping between ioprio and weights, described at the beginning
of the tunable section, is still valid, but all weights higher than
IOPRIO_BE_NR*10 are mapped to ioprio 0.
Recall that, if low-latency is set, then BFQ automatically raises the
weight of the queues associated with interactive and soft real-time
applications. Unset this tunable if you need/want to control weights.
weight_device
This specifies a per-device weight for the cgroup. The syntax is
`minor:major weight`. A weight of `0` may be used to reset to the default
weight.
For cgroup v1, it is set by writing the value to `blkio.bfq.weight_device`.
For cgroup v2, the file name is `io.bfq.weight`.
[1]
P. Valente, A. Avanzini, "Evolution of the BFQ Storage I/O
Scheduler", Proceedings of the First Workshop on Mobile System
Technologies (MST-2015), May 2015.
http://algogroup.unimore.it/people/paolo/disk_sched/mst-2015.pdf
[2]
P. Valente and M. Andreolini, "Improving Application
Responsiveness with the BFQ Disk I/O Scheduler", Proceedings of
the 5th Annual International Systems and Storage Conference
(SYSTOR '12), June 2012.
Slightly extended version:
http://algogroup.unimore.it/people/paolo/disk_sched/bfq-v1-suite-results.pdf
[3]
https://github.com/Algodev-github/S
3. 한국어 전문 번역
영어 원문의 문단 순서와 의미를 유지한 전체 번역입니다. 코드, 함수명, symbol과 URL은 원문 표기를 유지합니다.
BFQ의 목적과 처리 비용
1-59`BFQ (Budget Fair Queueing)`는 proportional-share I/O scheduler이며 추가적인 low-latency 기능을 제공합니다. `blkio` 또는 `io` controller를 통한 cgroup 지원과 함께 다음 두 기능이 핵심입니다.
- system과 application의 높은 responsiveness를 보장하고 audio·video player 같은 time-sensitive application의 latency를 낮춥니다.
- process 또는 group 사이에 device time만이 아니라 bandwidth를 분배합니다. throughput을 높여야 할 때는 time distribution으로 되돌아갑니다.
기본 설정에서 BFQ는 throughput보다 latency를 우선합니다. 낮은 latency를 위해 throughput이 줄어드는 schedule을 만들 수 있습니다. 특정 device에서 항상 가능한 최대 throughput만 원한다면 `low_latency`를 `0`으로 설정해 모든 low-latency heuristic을 끄십시오. latency·throughput tradeoff와 최대 throughput 설정은 Section 3에서 설명합니다.
다른 I/O scheduler처럼 BFQ도 request 처리 overhead를 더합니다. request insertion·dispatch·completion hook의 실행 시간을 합친 single-lock-protected per-request 시간은 Intel Core [email protected]에서 약 `1.9 us`였습니다. simple code instrumentation과 S suite [1]의 `throughput-sync.sh`를 performance-profiling mode로 사용한 수치입니다.
비교하면 `blk-mq`에서 가장 가벼운 I/O scheduler인 `mq-deadline`의 같은 실행 시간은 `0.7 us`입니다. code 규모는 mq-deadline 약 `800 LOC`, BFQ 약 `10500 LOC`입니다.
scheduling overhead는 I/O stack 나머지 부분의 비용과 함께 CPU가 처리할 수 있는 최대 IOPS도 제한합니다. full hierarchy support인 `CONFIG_BFQ_GROUP_IOSCHED`를 켠 세 system의 지속 가능한 BFQ 처리량은 다음과 같습니다.
| CPU / system class | `CONFIG_BFQ_CGROUP_DEBUG` unset | `CONFIG_BFQ_CGROUP_DEBUG` set |
|---|---|---|
| Intel i7-4850HQ, average laptop | `400 KIOPS` | `310 KIOPS` |
| AMD A8-3850, old desktop | `250 KIOPS` | `200 KIOPS` |
| ARM CortexTM-A53 Octa-core, cheap embedded | `80 KIOPS` | `56 KIOPS` |
`CONFIG_BFQ_CGROUP_DEBUG`를 켜면 모든 `blkio.bfq*` statistic을 생성·갱신하므로 지속 가능한 throughput이 감소합니다. BFQ는 multi-queue device에서도 동작합니다.
문서 구성
60-72원문의 목차는 다음 네 영역과 하위 절로 구성됩니다.
- 1. BFQ가 유용한 경우: personal system과 server system
- 2. BFQ 동작 방식
- 3. BFQ tunable과 올바른 설정
- 4. BFQ group scheduling: service guarantee와 interface
personal system에서의 이점
73-136BFQ는 personal system과 server system 모두에 이점을 제공하며, personal system에서는 interactive application latency를 특히 낮춥니다. 실제 background workload와 관계없이 storage device가 idle인 것과 거의 같은 responsiveness를 interactive task에 보장합니다.
다음 background workload가 하나 이상 실행 중이어도 이 특성을 유지합니다.
- 큰 file 하나 이상을 read, write 또는 copy
- source-file tree compile
- virtual machine 하나 이상의 I/O
- software update
- indexing daemon의 filesystem scan과 database update
따라서 application 시작이나 application 안에서 file load에 걸리는 시간은 device가 idle일 때와 비슷합니다. 같은 조건의 `CFQ`, `NOOP`, `DEADLINE`에서는 SSD에서도 background workload가 끝날 때까지 latency가 높아지거나 application이 응답하지 않을 수 있습니다.
audio·video player 또는 streamer 같은 soft real-time application도 background I/O workload와 관계없이 낮은 latency와 drop rate를 얻으므로 background workload로 인한 glitch가 거의 없습니다.
추가 workload가 병렬 실행될 때 compile, checkout, merge 같은 일반 code-development task의 I/O component도 `CFQ`, `NOOP`, `DEADLINE`보다 훨씬 빠르게 실행합니다.
hard disk의 sequential workload에서는 CFQ보다 최대 30%, DEADLINE과 NOOP보다 최대 150% 높은 throughput을 달성했습니다. random workload와 flash-based device의 모든 workload에서는 다른 scheduler와 대체로 같은 throughput을 냅니다.
BFQ는 workload와 device parameter에 관계없이 I/O-bound application의 weight에 비례해 device time이 아니라 device throughput을 분배합니다. 이 bandwidth guarantee에서 간단한 formula로 tight per-I/O-request delay guarantee를 계산할 수 있습니다. strict service guarantee로 설정하지 않았다면 bandwidth share 때문에 throughput이 감소하는 application에만 time-based resource sharing으로 전환합니다.
server system에서의 이점
137-154server system의 이점도 같은 service property에서 나옵니다. 추가로 무거운 workload를 처리하는지와 관계없이 BFQ는 다음을 보장합니다.
- audio·video streaming의 jitter와 drop rate가 0 또는 매우 낮음
- WEB page와 embedded object의 빠른 retrieval
- packet logging 같은 live-dumping application의 real-time data recording
- server에 대한 local·remote access responsiveness
budget scheduling과 B-WF2Q+
155-295BFQ는 general structure와 많은 code를 CFQ에서 가져온 proportional-share I/O scheduler입니다. device에서 I/O를 수행하는 각 process는 weight와 `(bfq_)queue`에 연결됩니다.
BFQ는 한 번에 한 queue, 즉 한 process에 일정 시간 device 독점 access를 부여합니다. 각 queue에는 sector 수로 측정한 budget이 있고, service를 받은 뒤 request를 dispatch할 때마다 request size만큼 budget을 줄입니다.
in-service queue는 다음 사건 중 하나가 발생할 때만 expire되어 service가 중단됩니다.
- queue가 budget을 모두 사용함
- queue가 비어 있음
- `budget timeout` 발생
`budget timeout`은 random I/O process가 device를 너무 오래 점유해 throughput을 크게 낮추는 일을 막습니다. CFQ처럼 sync request를 내는 process의 queue는 비었을 때 즉시 expire되지 않을 수 있습니다. BFQ는 잠시 device를 idle 상태로 두어 process가 제때 새 request를 내면 계속 service받게 합니다.
device idling은 synchronous sequential I/O에서 rotational device와 command queueing이 없는 flash device의 throughput을 높이는 경우가 많습니다. BFQ에서는 sync request process에 원하는 throughput fraction을 보장하는 수단이기도 하며 자세한 내용은 `slice_idle` 설명과 [1, 2]에 있습니다.
동시에 경쟁하는 process가 여럿이어도 모든 process와 group의 weight가 같다면 BFQ는 device를 idle시키지 않고 예상 throughput 분배를 보장합니다. 이 흔한 상황에서는 throughput을 최대한 유지합니다.
internal command queueing, 보통 `NCQ`를 사용하는 flash storage에서는 device idling이 항상 throughput에 해롭습니다. BFQ는 low latency나 fairness 같은 service guarantee에 반드시 필요할 때만 idling합니다. 이때 전체 throughput은 최적보다 낮을 수 있으며, internal queueing device에서 강한 service guarantee와 최적 throughput을 동시에 제공하는 해법은 현재 없습니다.
기본값인 low-latency mode에서는 interactive application과 soft real-time application을 감지해 latency를 줄이는 heuristic을 실행합니다. 핵심은 관련 queue에 fair share보다 많은 device throughput을 주는 `weight-raising`입니다. interactive application에는 완만하게, soft real-time application에는 더 강하게 적용합니다.
BFQ는 queue가 한꺼번에 생성되는 burst에서 태어난 queue에는 idling을 자동으로 끕니다. 이런 queue는 대개 boot 중 `systemd`나 `git grep`처럼 high throughput의 이점이 큰 application·service process에 연결되기 때문입니다.
CFQ처럼 BFQ도 섞어서 보면 대부분 sequential이 되는 interleaved random I/O queue를 merge합니다. BFQ의 `Early Queue Merge (EQM)`은 cooperating process를 더 빠르게 감지해, CFQ가 preemption을 써야 높은 throughput을 얻는 queue에도 merge 하나로 높은 throughput을 제공합니다.
queue scheduling에는 augmented rb-tree로 구현한 `WF2Q+` variant인 `B-WF2Q+`를 사용해 전체 complexity를 `O(log N)`으로 유지합니다. 자세한 내용은 [2]에 있으며 hierarchical scheduling도 지원합니다.
`B-WF2Q+`는 이상적으로 완전히 fair하고 smooth한 service와의 deviation을 작게 제한합니다. device throughput이 변해도 각 queue가 weight에 비례한 throughput fraction을 받으며 device parameter, 현재 workload, queue budget에 의존하지 않습니다.
budget independence에는 두 이점이 있습니다. 첫째, proportional-share scheduler의 이상적 service 대비 최대 deviation은 최대 budget에 비례하지만 BFQ는 높은 throughput share를 주려고 queue budget을 키울 필요가 없습니다. 정확한 `B-WF2Q+` service와 함께 deviation을 작게 유지할 수 있습니다.
둘째, BFQ는 process 요구와 I/O pattern에 가장 맞는 budget을 자유롭게 고를 수 있습니다. simple feedback-loop algorithm은 throughput을 높이면서 time-sensitive application의 tight latency guarantee를 유지하도록 queue expiration 때 다음 budget을 계산합니다.
- sequential I/O를 수행하는 I/O-bound application queue에는 결국 큰 budget을 줍니다. device access를 얻은 뒤 오래 service할수록 throughput이 높기 때문입니다.
- sporadic하고 짧은 I/O를 내는 time-sensitive application queue에는 결국 작은 budget을 줍니다. service를 기다리는 queue의 budget이 작을수록 `B-WF2Q+`가 더 빨리 service합니다([2] Subsec 3.3).
모든 process와 group의 weight가 같을 때는 idling 대신 preemption으로 예상 throughput을 분배해 이 흔한 상황의 throughput을 크게 높입니다. `ioprio` class는 strict priority 순서로 service하므로 높은 priority queue가 남아 있는 동안 낮은 priority queue는 service하지 않습니다. 같은 class 안에서는 weight에 비례해 bandwidth를 나누되 starvation 방지를 위해 Idle class에도 아주 적은 추가 bandwidth를 보장합니다.
tunable 개요와 process weight
296-326대부분 BFQ tunable은 latency·fairness 같은 service guarantee와 throughput에 영향을 줍니다. tradeoff는 `slice_idle`, `strict_guarantees`, `low_latency`를, throughput 최대화는 `slice_idle`, `timeout_sync`, `max_budget`을 보십시오.
나머지 performance parameter는 CFQ에서 상속되어 주로 compatibility를 위해 남았습니다. 지금까지 BFQ에서 이 값을 바꿔 performance가 개선되었다는 보고는 없습니다. `back_seek_max`, `back_seek_penalty`, `fifo_expire_async`, `fifo_expire_sync` 설명은 CFQ의 설명을 그대로 가져왔고 `slice_idle` 설명 일부도 같습니다.
cgroup interface를 쓰지 않으면 process weight는 I/O priority를 통해서만 간접 지정하며 관계식은 다음과 같습니다.
weight = (IOPRIO_BE_NR - ioprio) * 10.`low_latency`가 설정되면 BFQ가 interactive·soft real-time application queue의 weight를 자동으로 올립니다. weight를 직접 제어해야 한다면 이 tunable을 해제하십시오.
slice_idle의 throughput·보장 tradeoff
327-380`slice_idle`은 일부 sync BFQ queue가 비었을 때 다음 I/O request를 기다리며 BFQ가 idle할 시간을 지정합니다. 기본값은 0이 아니며, idling은 throughput 향상과 원하는 throughput 분배 준수라는 두 목적을 가집니다.
single-spindle SATA/SAS disk처럼 seek가 많은 media에서는 전체 seek 수를 줄여 throughput을 높일 수 있습니다. 반대로 `slice_idle=0`은 모든 queue idling을 없애므로 hardware RAID의 여러 SATA/SAS disk나 internal command queueing과 parallelism을 가진 flash storage에서 전체 throughput이 좋아질 수 있습니다.
일반적으로 SATA/SAS disk와 그 software RAID에서는 idling을 유지하는 편이 유용합니다. 하나의 LUN 뒤에 spindle이 여러 개 있는 host hardware RAID·storage array나 빠른 flash storage에서는 `slice_idle=0`이 더 좋은 throughput과 받아들일 만한 latency를 낼 수 있습니다.
하지만 weight나 I/O-request length가 서로 다를 때 service guarantee를 강제하려면 idling이 필요합니다. queue A가 queue B의 request 하나마다 여러 request를 service받아야 한다고 가정하면, A가 빈 직후 새 request를 내는 사이에 B request가 끼어 dispatch되지 않도록 idling해야 A가 차등 share를 잃지 않습니다.
idling만으로 보장하는 차등 처리는 I/O-request dispatch 순서에 한정됩니다. 실제 service 순서도 dispatch 순서를 따르게 하려면 `strict_guarantees`도 설정해야 합니다.
throughput에도 유리한 경우를 제외하면 idling은 특히 random workload에서 throughput을 크게 낮출 수 있습니다. BFQ는 throughput에 유리하지 않은 idling을 가능한 한 피합니다. 그 결과와 `strict_guarantees`에서 설명할 문제 때문에 단기 service guarantee가 가끔 깨질 수 있습니다.
video playback·streaming처럼 최대 throughput보다 매우 낮은 drop rate가 더 중요하다면 `strict_guarantees` 설정을 고려하십시오.
slice_idle_us와 strict_guarantees
381-407`slice_idle_us`는 `slice_idle`과 같은 parameter를 microsecond 단위로 제어합니다. 어느 쪽으로든 idling behavior를 설정할 수 있고, 이후 다른 tunable의 sysfs 값도 새 값으로 갱신됩니다.
기본값이 unset인 `strict_guarantees`를 설정하면 BFQ는 다음을 수행합니다.
- in-service queue가 비면 항상 idling합니다.
- outstanding request가 없을 때만 새 request를 dispatch해 device가 한 번에 I/O request 하나만 service하도록 강제합니다.
weight 또는 I/O-request size가 서로 다를 때 각 BFQ queue가 할당된 bandwidth share를 받으려면 두 조건이 모두 필요합니다. 첫 조건의 이유는 `slice_idle` 설명과 같고, 둘째 조건은 modern storage device가 내부 queue의 request를 reorder해 I/O scheduler의 service guarantee를 쉽게 깨뜨릴 수 있기 때문입니다.
`strict_guarantees`를 설정하면 throughput에 영향을 줄 수 있습니다.
back seek와 FIFO timeout
408-441| Tunable | 단위·기본값 | 동작 |
|---|---|---|
| `back_seek_max` | Kbytes | 현재 head location보다 뒤쪽 sector를 다음 request로 간주할 수 있는 최대 backward seek distance |
| `back_seek_penalty` | default `2` | backward request distance가 front request의 `1/back_seek_penalty`이면 두 seek cost를 같게 봅니다. 그렇지 않으면 front request 쪽으로 bias합니다. |
| `fifo_expire_async` | default `250ms` | asynchronous request timeout |
| `fifo_expire_sync` | default `125ms` | synchronous request timeout. sync request를 async보다 우선하려면 `fifo_expire_async`에 비해 이 값을 낮춥니다. |
low_latency·timeout_sync·max_budget
442-494`low_latency`는 BFQ low-latency mode를 켜거나 끕니다. 기본값은 enabled이며 interactive·soft real-time application을 우대해 앞의 algorithm 설명처럼 latency를 낮춥니다.
bandwidth 분배를 완전히 제어하려면 이 mode를 끄십시오. 켜져 있으면 낮은 latency를 보장하는 핵심 수단으로 BFQ가 privileged application의 bandwidth share를 자동으로 늘립니다.
목표가 high throughput뿐인 경우에도 끄십시오. 일부 application I/O를 우대하면 throughput이 줄 수 있습니다. non-rotational device에서 가능한 최고 throughput을 내려면 `slice_idle=0`도 필요할 수 있으며, 그 대가로 fairness와 low latency에 대한 강한 보장을 포기합니다.
`timeout_sync`는 service 대상으로 선택된 task(queue)에 줄 수 있는 최대 device time입니다. seek cost가 큰 device에서는 이 시간을 늘리면 보통 최대 throughput이 높아지지만, 단기 bandwidth·latency guarantee의 granularity는 거칠어지며 특히 `max_budget`이 0일 때 그렇습니다.
`max_budget`은 in-service BFQ queue에 제공할 수 있는 sector 단위 최대 service 양이며 `timeout_sync` 한도 안에서 적용됩니다. 값이 클수록 sequential I/O request 비율에 따라 throughput이 늘지만 단기 bandwidth·latency guarantee의 granularity가 거칠어집니다.
기본값 `0`은 auto-tuning을 활성화합니다. BFQ가 estimated peak rate에 따라 `timeout_sync` 동안 service할 수 있는 최대 sector 수로 `max_budget`을 정합니다.
일부 device에서는 사용자가 `max_budget`을 0보다 큰 값, 특히 auto-tuning보다 큰 값으로 명시해 더 높은 throughput을 얻었다고 보고했습니다. 같은 목표는 `max_budget=0`을 유지하고 `timeout_sync`를 늘리는 방법으로도 달성할 수 있습니다.
BFQ group scheduling 보장
495-525BFQ는 cgroups-v1 `blkio`와 cgroups-v2 `io` controller를 모두 지원하며 weight 기반 proportional share를 제공합니다. cgroup 지원을 활성화하려면 `BFQ_GROUP_IOSCHED`를 설정합니다.
BFQ에서 proportional share는 group weight에 따른 실제 device bandwidth share입니다. 예를 들어 weight 200 group은 weight 100 group보다 device time뿐 아니라 bandwidth를 두 배 받습니다.
BFQ는 깊이에 제한 없는 hierarchy(group tree)를 지원합니다. 각 group의 child는 weight에 비례해 parent group 전체 bandwidth를 나눕니다. 각 leaf group의 process는 process `ioprio`를 바꾸지 않는 한 group 전체 bandwidth에서 같은 share를 받습니다.
group에 bandwidth guarantee를 제공하느라 throughput이 지나치게 낮아지면 resource-sharing guarantee가 일부 또는 전부 bandwidth에서 time으로 바뀔 수 있습니다. 이 전환은 process 단위입니다. leaf group process를 bandwidth share대로 service할 때 throughput loss를 일으키면 BFQ는 그 process만 time-based proportional share로 되돌립니다.
cgroup interface와 debug statistic
526-555특정 device에 BFQ bandwidth proportional sharing을 적용하려면 BFQ가 그 device의 active scheduler여야 합니다.
각 group directory의 BFQ 전용 cgroup parameter와 statistic file 이름은 `bfq.`로 시작합니다. 전체 prefix는 cgroups-v1에서 `blkio.bfq.`, cgroups-v2에서 `io.bfq.`입니다. 예를 들어 group weight parameter는 `blkio.bfq.weight` 또는 `io.bfq.weight`입니다.
cgroups-v1 `blkio` controller에서 생성·갱신하는 정확한 stat file 집합은 `CONFIG_BFQ_CGROUP_DEBUG`에 따라 달라집니다. 설정하면 `Documentation/admin-guide/cgroup-v1/blkio-controller.rst`에 문서화된 모든 stat file을 만들고, 설정하지 않으면 다음 네 file만 만듭니다.
blkio.bfq.io_service_bytes
blkio.bfq.io_service_bytes_recursive
blkio.bfq.io_serviced
blkio.bfq.io_serviced_recursive`blkio.bfq.*` statistic 갱신 비용, 특히 `CONFIG_BFQ_CGROUP_DEBUG`가 켜는 일부 statistic의 비용이 크므로 이 config 값은 BFQ가 지속할 수 있는 최대 throughput에 큰 영향을 줍니다.
group parameter와 참고문헌
556-606각 group에는 다음 parameter를 설정할 수 있습니다.
| Parameter | 범위·syntax | cgroup v1 / v2와 동작 |
|---|---|---|
| `weight` | `1..1000`, `default: 100` | parent 안에서 cgroup의 default weight입니다. v1은 `blkio.bfq.weight`, v2는 `io.bfq.weight`에 쓰며 v2 값 앞에 선택적으로 `default `를 붙일 수 있습니다. |
| `weight_device` | `minor:major weight`; `0`은 default로 reset | device별 cgroup weight입니다. v1은 `blkio.bfq.weight_device`, v2 file은 `io.bfq.weight`입니다. |
tunable 절 앞부분의 ioprio와 weight 사이 linear mapping은 그대로 유효하지만 `IOPRIO_BE_NR*10`보다 큰 모든 weight는 ioprio 0으로 mapping됩니다. `low_latency`가 켜져 있으면 interactive·soft real-time queue의 weight를 BFQ가 자동으로 올리므로 직접 제어하려면 이 tunable을 끕니다.
[1] P. Valente, A. Avanzini, "Evolution of the BFQ Storage I/O Scheduler", First Workshop on Mobile System Technologies (MST-2015), May 2015: http://algogroup.unimore.it/people/paolo/disk_sched/mst-2015.pdf
[2] P. Valente, M. Andreolini, "Improving Application Responsiveness with the BFQ Disk I/O Scheduler", 5th Annual International Systems and Storage Conference (SYSTOR '12), June 2012. Slightly extended version: http://algogroup.unimore.it/people/paolo/disk_sched/bfq-v1-suite-results.pdf
[3] https://github.com/Algodev-github/S
요약과 해설
bfq-iosched.rst:1-606BFQ는 queue weight에 비례해 실제 device bandwidth를 분배하면서 interactive·soft real-time workload의 latency를 낮추는 proportional-share I/O scheduler입니다.
강한 service guarantee에는 idling과 request serialization 비용이 따릅니다. `slice_idle`, `strict_guarantees`, `low_latency`, `timeout_sync`, `max_budget`을 storage 특성과 목표에 맞게 조정해야 합니다.