← Documents Documentation/block/blk-mq.rst GitHub 원문 ↗

Linux 6.18.37 · Block

Multi-Queue Block IO Queueing Mechanism (blk-mq)

blk-mq의 software·hardware queue 계층, I/O scheduling과 tag 기반 완료 방식을 설명합니다.

Source pathDocumentation/block/blk-mq.rst
Source versionLinux v6.18.37
TranslationDUJINLABS 전문 번역 + 해설

요약·해설과 원문, 전문 번역을 서로 분리했습니다. API 이름, symbol, source path는 원문 표기를 사용합니다.

1. 요약·해설

원문의 핵심 논리와 kernel programming 관점의 보충 설명입니다. 아래의 전문 번역과는 별도로 작성했습니다.

요약과 해설

blk-mq.rst:1-153

`blk-mq`는 CPU-local software queue와 device-facing hardware queue를 분리해 shared lock contention을 줄이고 modern storage의 parallelism을 활용합니다.

request는 상황에 따라 hardware queue로 바로 가거나 merge·scheduling을 위해 software staging queue를 거칩니다. hardware resource가 부족하면 `hctx->dispatch`에서 재시도하며, 완료 request는 integer tag로 식별합니다.

2. 영어 원문 전체

번역 기준이 된 Linux v6.18.37 원문입니다. 줄 번호는 이 버전의 파일 좌표입니다.

원문 전체 펼치기
1 .. SPDX-License-Identifier: GPL-2.0
2
3 ================================================
4 Multi-Queue Block IO Queueing Mechanism (blk-mq)
5 ================================================
6
7 The Multi-Queue Block IO Queueing Mechanism is an API to enable fast storage
8 devices to achieve a huge number of input/output operations per second (IOPS)
9 through queueing and submitting IO requests to block devices simultaneously,
10 benefiting from the parallelism offered by modern storage devices.
11
12 Introduction
13 ============
14
15 Background
16 ----------
17
18 Magnetic hard disks have been the de facto standard from the beginning of the
19 development of the kernel. The Block IO subsystem aimed to achieve the best
20 performance possible for those devices with a high penalty when doing random
21 access, and the bottleneck was the mechanical moving parts, a lot slower than
22 any layer on the storage stack. One example of such optimization technique
23 involves ordering read/write requests according to the current position of the
24 hard disk head.
25
26 However, with the development of Solid State Drives and Non-Volatile Memories
27 without mechanical parts nor random access penalty and capable of performing
28 high parallel access, the bottleneck of the stack had moved from the storage
29 device to the operating system. In order to take advantage of the parallelism
30 in those devices' design, the multi-queue mechanism was introduced.
31
32 The former design had a single queue to store block IO requests with a single
33 lock. That did not scale well in SMP systems due to dirty data in cache and the
34 bottleneck of having a single lock for multiple processors. This setup also
35 suffered with congestion when different processes (or the same process, moving
36 to different CPUs) wanted to perform block IO. Instead of this, the blk-mq API
37 spawns multiple queues with individual entry points local to the CPU, removing
38 the need for a lock. A deeper explanation on how this works is covered in the
39 following section (`Operation`_).
40
41 Operation
42 ---------
43
44 When the userspace performs IO to a block device (reading or writing a file,
45 for instance), blk-mq takes action: it will store and manage IO requests to
46 the block device, acting as middleware between the userspace (and a file
47 system, if present) and the block device driver.
48
49 blk-mq has two group of queues: software staging queues and hardware dispatch
50 queues. When the request arrives at the block layer, it will try the shortest
51 path possible: send it directly to the hardware queue. However, there are two
52 cases that it might not do that: if there's an IO scheduler attached at the
53 layer or if we want to try to merge requests. In both cases, requests will be
54 sent to the software queue.
55
56 Then, after the requests are processed by software queues, they will be placed
57 at the hardware queue, a second stage queue where the hardware has direct access
58 to process those requests. However, if the hardware does not have enough
59 resources to accept more requests, blk-mq will place requests on a temporary
60 queue, to be sent in the future, when the hardware is able.
61
62 Software staging queues
63 ~~~~~~~~~~~~~~~~~~~~~~~
64
65 The block IO subsystem adds requests in the software staging queues
66 (represented by struct blk_mq_ctx) in case that they weren't sent
67 directly to the driver. A request is one or more BIOs. They arrived at the
68 block layer through the data structure struct bio. The block layer
69 will then build a new structure from it, the struct request that will
70 be used to communicate with the device driver. Each queue has its own lock and
71 the number of queues is defined by a per-CPU or per-node basis.
72
73 The staging queue can be used to merge requests for adjacent sectors. For
74 instance, requests for sector 3-6, 6-7, 7-9 can become one request for 3-9.
75 Even if random access to SSDs and NVMs have the same time of response compared
76 to sequential access, grouped requests for sequential access decreases the
77 number of individual requests. This technique of merging requests is called
78 plugging.
79
80 Along with that, the requests can be reordered to ensure fairness of system
81 resources (e.g. to ensure that no application suffers from starvation) and/or to
82 improve IO performance, by an IO scheduler.
83
84 IO Schedulers
85 ^^^^^^^^^^^^^
86
87 There are several schedulers implemented by the block layer, each one following
88 a heuristic to improve the IO performance. They are "pluggable" (as in plug
89 and play), in the sense of they can be selected at run time using sysfs. You
90 can read more about Linux's IO schedulers `here
91 <https://www.kernel.org/doc/html/latest/block/index.html>`_. The scheduling
92 happens only between requests in the same queue, so it is not possible to merge
93 requests from different queues, otherwise there would be cache trashing and a
94 need to have a lock for each queue. After the scheduling, the requests are
95 eligible to be sent to the hardware. One of the possible schedulers to be
96 selected is the NONE scheduler, the most straightforward one. It will just
97 place requests on whatever software queue the process is running on, without
98 any reordering. When the device starts processing requests in the hardware
99 queue (a.k.a. run the hardware queue), the software queues mapped to that
100 hardware queue will be drained in sequence according to their mapping.
101
102 Hardware dispatch queues
103 ~~~~~~~~~~~~~~~~~~~~~~~~
104
105 The hardware queue (represented by struct blk_mq_hw_ctx) is a struct
106 used by device drivers to map the device submission queues (or device DMA ring
107 buffer), and are the last step of the block layer submission code before the
108 low level device driver taking ownership of the request. To run this queue, the
109 block layer removes requests from the associated software queues and tries to
110 dispatch to the hardware.
111
112 If it's not possible to send the requests directly to hardware, they will be
113 added to a linked list (``hctx->dispatch``) of requests. Then,
114 next time the block layer runs a queue, it will send the requests laying at the
115 ``dispatch`` list first, to ensure a fairness dispatch with those
116 requests that were ready to be sent first. The number of hardware queues
117 depends on the number of hardware contexts supported by the hardware and its
118 device driver, but it will not be more than the number of cores of the system.
119 There is no reordering at this stage, and each software queue has a set of
120 hardware queues to send requests for.
121
122 .. note::
123
124 Neither the block layer nor the device protocols guarantee
125 the order of completion of requests. This must be handled by
126 higher layers, like the filesystem.
127
128 Tag-based completion
129 ~~~~~~~~~~~~~~~~~~~~
130
131 In order to indicate which request has been completed, every request is
132 identified by an integer, ranging from 0 to the dispatch queue size. This tag
133 is generated by the block layer and later reused by the device driver, removing
134 the need to create a redundant identifier. When a request is completed in the
135 driver, the tag is sent back to the block layer to notify it of the finalization.
136 This removes the need to do a linear search to find out which IO has been
137 completed.
138
139 Further reading
140 ---------------
141
142 - `Linux Block IO: Introducing Multi-queue SSD Access on Multi-core Systems <http://kernel.dk/blk-mq.pdf>`_
143
144 - `NOOP scheduler <https://en.wikipedia.org/wiki/Noop_scheduler>`_
145
146 - `Null block device driver <https://www.kernel.org/doc/html/latest/block/null_blk.html>`_
147
148 Source code documentation
149 =========================
150
151 .. kernel-doc:: include/linux/blk-mq.h
152
153 .. kernel-doc:: block/blk-mq.c
154

3. 한국어 전문 번역

영어 원문의 문단 순서와 의미를 유지한 전체 번역입니다. 코드, 함수명, symbol과 URL은 원문 표기를 유지합니다.

blk-mq 개요

1-10

이 문서는 `SPDX-License-Identifier: GPL-2.0`으로 배포됩니다.

`Multi-Queue Block IO Queueing Mechanism (blk-mq)`은 빠른 storage device가 modern storage의 parallelism을 활용하도록 하는 API입니다. 여러 I/O request를 동시에 queueing하고 block device에 submit하여 매우 높은 초당 input/output operation 수, 즉 `IOPS`를 달성하게 합니다.

도입 배경

11-40

kernel 개발 초기부터 magnetic hard disk가 사실상의 표준이었습니다. Block I/O subsystem은 random access penalty가 큰 이 device에서 가능한 최고의 performance를 내는 데 초점을 맞췄습니다. storage stack의 어느 layer보다 훨씬 느린 기계식 가동 부품이 bottleneck이었기 때문입니다. hard disk head의 현재 위치에 맞춰 read/write request를 정렬하는 것이 대표적인 최적화입니다.

그러나 기계식 부품과 random access penalty가 없고 높은 병렬 접근 성능을 제공하는 `Solid State Drive`와 `Non-Volatile Memory`가 발전하면서 stack의 bottleneck이 storage device에서 operating system으로 이동했습니다. 이런 device 설계의 parallelism을 활용하기 위해 multi-queue mechanism이 도입되었습니다.

이전 설계는 block I/O request를 저장하는 queue 하나와 lock 하나를 사용했습니다. 여러 processor가 하나의 lock을 공유해 cache의 dirty data와 lock bottleneck을 만들었으므로 SMP system에서 잘 확장되지 않았습니다. 서로 다른 process 또는 CPU 사이를 이동하는 같은 process가 block I/O를 수행하려 할 때 congestion도 발생했습니다.

`blk-mq` API는 대신 CPU local entry point를 가진 여러 queue를 만들고 개별 lock을 사용해 공유 lock의 필요를 없앱니다. 구체적인 동작은 다음 `Operation` 절에서 설명합니다.

I/O request의 기본 경로

41-61

userspace가 block device에 I/O를 수행하면, 예를 들어 file을 read하거나 write하면 `blk-mq`가 동작합니다. userspace와 file system이 있다면 그 file system, 그리고 block device driver 사이의 middleware로서 block device용 I/O request를 저장하고 관리합니다.

`blk-mq`에는 `software staging queue`와 `hardware dispatch queue`라는 두 queue group이 있습니다. request가 block layer에 도착하면 가능한 가장 짧은 경로인 hardware queue 직접 전송을 먼저 시도합니다. 다만 `IO scheduler`가 layer에 연결되어 있거나 request merge를 시도하려는 경우에는 software queue로 보냅니다.

software queue에서 처리한 request는 hardware가 직접 접근해 처리하는 2단계 queue인 hardware queue에 놓입니다. hardware에 추가 request를 받을 resource가 부족하면 `blk-mq`는 request를 임시 queue에 두었다가 hardware가 처리할 수 있을 때 나중에 전송합니다.

software staging queue와 plugging

62-83

block I/O subsystem은 driver로 직접 보내지 않은 request를 `struct blk_mq_ctx`로 표현되는 software staging queue에 추가합니다. request 하나는 하나 이상의 `BIO`로 구성됩니다. 이들은 `struct bio` data structure로 block layer에 도착하고, block layer는 device driver와 통신하는 데 사용할 새 `struct request`를 만듭니다. 각 queue에는 자체 lock이 있으며 queue 수는 per-CPU 또는 per-node 기준으로 정합니다.

staging queue에서는 인접 sector request를 merge할 수 있습니다. 예를 들어 sector `3-6`, `6-7`, `7-9`에 대한 request를 `3-9` request 하나로 합칠 수 있습니다. SSD와 NVM은 random access와 sequential access의 response time이 같더라도 sequential access request를 묶으면 개별 request 수가 줄어듭니다. 이 request merge 기법을 `plugging`이라고 합니다.

이와 함께 `IO scheduler`가 system resource의 fairness를 보장하도록, 예를 들어 어떤 application도 starvation을 겪지 않도록 request를 재정렬하거나 I/O performance를 개선할 수 있습니다.

I/O scheduler

84-101

block layer에는 각각 IO performance 개선 heuristic을 따르는 여러 scheduler가 구현되어 있습니다. 이들은 plug-and-play 의미에서 `pluggable`하며 sysfs를 통해 runtime에 선택할 수 있습니다. Linux `IO scheduler`에 관한 자세한 내용은 https://www.kernel.org/doc/html/latest/block/index.html 에 있습니다.

scheduling은 같은 queue의 request 사이에서만 이루어집니다. 서로 다른 queue의 request를 merge하면 cache trashing이 발생하고 각 queue에 lock이 필요해지므로 그렇게 할 수 없습니다. scheduling을 마친 request는 hardware로 전송할 수 있습니다.

선택 가능한 scheduler 중 `NONE scheduler`는 가장 단순합니다. 재정렬하지 않고 process가 실행 중인 software queue에 request를 그대로 놓습니다. device가 hardware queue의 request 처리를 시작해 hardware queue를 run하면, 그 hardware queue에 mapping된 software queue를 mapping 순서대로 drain합니다.

hardware dispatch queue

102-127

`struct blk_mq_hw_ctx`로 표현되는 hardware queue는 device driver가 device submission queue 또는 device DMA ring buffer를 mapping하는 데 사용하는 구조체입니다. low-level device driver가 request ownership을 넘겨받기 전 block layer submission code의 마지막 단계입니다. 이 queue를 run할 때 block layer는 연결된 software queue에서 request를 제거하고 hardware로 dispatch하려고 시도합니다.

request를 hardware에 직접 보낼 수 없으면 request linked list인 `hctx->dispatch`에 추가합니다. 다음번 block layer가 queue를 run할 때 먼저 준비되어 있던 request에 공정한 dispatch 기회를 보장하도록 `dispatch` list의 request를 우선 전송합니다.

hardware queue 수는 hardware와 device driver가 지원하는 hardware context 수에 따라 달라지지만 system core 수보다 많지는 않습니다. 이 단계에서는 재정렬하지 않으며, 각 software queue에는 request를 보낼 hardware queue 집합이 있습니다.

block layer와 device protocol 어느 쪽도 request 완료 순서를 보장하지 않습니다. 완료 순서는 filesystem 같은 상위 layer가 처리해야 합니다.

tag 기반 완료와 참고 자료

128-147

어느 request가 완료되었는지 나타내기 위해 모든 request에는 `0`부터 dispatch queue size까지 범위의 integer tag를 부여합니다. block layer가 이 tag를 생성하고 device driver가 나중에 재사용하므로 중복 identifier를 새로 만들 필요가 없습니다.

driver에서 request가 완료되면 완료 사실을 알리기 위해 tag를 block layer로 돌려보냅니다. 따라서 어느 I/O가 완료되었는지 찾는 linear search가 필요하지 않습니다.

더 읽을 자료는 다음과 같습니다.

  • `Linux Block IO: Introducing Multi-queue SSD Access on Multi-core Systems`: http://kernel.dk/blk-mq.pdf
  • `NOOP scheduler`: https://en.wikipedia.org/wiki/Noop_scheduler
  • `Null block device driver`: https://www.kernel.org/doc/html/latest/block/null_blk.html

source code 문서

148-153

source code API 문서는 `include/linux/blk-mq.h`와 `block/blk-mq.c`의 kernel-doc에서 생성합니다.