劉正元: Linux 通用塊層之 IO 合併
作者簡介： 劉正元，來自天津麒麟 (kylinos.cn)， linux 內核愛好者，對內核 IO 子系統和內核調試工具這塊比較感興趣，向內核上游內核貢獻過一些, 目前在公司負責文件 IO 協議棧的調試調優。
相關閱讀：
劉正元: Linux 通用塊層之 DeadLine IO 調度器
所謂請求合併就是將進程內或者進程間產生的在物理地址上連續的多個 IO 請求合併成單個 IO 請求一併處理，從而提升 IO 請求的處理效率。在前面有關通用塊層介紹的系列文章當中我們或多或少地提及了 IO 請求合併的概念，本篇我們從頭集中梳理 IO 請求在 block layer 的來龍去脈，以此來增強對 IO 請求合併的理解。
首先來看一張圖，下面的圖展示了 IO 請求數據由用戶進程產生，到最終持久化存儲到物理存儲介質，其間在內核空間所經歷的數據流以及 IO 請求合併可能的觸發點。
從內核的角度而言，進程產生的 IO 路徑主要有圖中①②③所示的三條：
① 緩存 IO, 對應圖中的路徑①，系統中絕大部分 IO 走的這種形式，充分利用 filesystem 層的 page cache 所帶來的優勢， 應用程序產生的 IO 經系統調用落入 page cache 之後便可以直接返回，page cache 中的緩存數據由內核回寫線程在適當時機負責同步到底層的存儲介質之上，當然應用程序也可以主動發起回寫過程（如 fsync 系統調用）來確保數據儘快同步到存儲介質上，從而避免系統崩潰或者掉電帶來的數據不一致性。緩存 IO 可以帶來很多好處，首先應用程序將 IO 丟給 page cache 之後就直接返回了，避免了每次 IO 都將整個 IO 協議棧走一遍，從而減少了 IO 的延遲。其次，page cache 中的緩存最後以頁或塊爲單位進行回寫，並非應用程序向 page cache 中提交了幾次 IO, 回寫的時候就需要往通用塊層提交幾次 IO, 這樣在提交時間上不連續但在空間上連續的小塊 IO 請求就可以合併到同一個緩存頁中一併處理。再次，如果應用程序之前產生的 IO 已經在 page cache 中，後續又產生了相同的 IO，那麼只需要將後到的 IO 覆蓋 page cache 中的舊 IO，這樣一來如果應用程序頻繁的操作文件的同一個位置，我們只需要向底層存儲設備提交最後一次 IO 就可以了。最後，應用程序寫入到 page cache 中的緩存數據可以爲後續的讀操作服務，讀取數據的時候先搜索 page cache，如果命中了則直接返回，如果沒命中則從底層讀取並保存到 page cache 中，下次再讀的時候便可以從 page cache 中命中。
② 非緩存 IO（帶蓄流），對應圖中的路徑②，這種 IO 繞過文件系統層的 cache。用戶在打開要讀寫的文件的時候需要加上 “O_DIRECT” 標誌，意爲直接 IO，不讓文件系統的 page cache 介入。從用戶角度而言，應用程序能直接控制的 IO 形式除了上面提到的 “緩存 IO”，剩下的 IO 都走的這種形式，就算文件打開時加上了 ”O_SYNC” 標誌，最終產生的 IO 也會進入蓄流鏈表（圖中的 Plug List）。如果應用程序在用戶空間自己做了緩存，那麼就可以使用這種 IO 方式，常見的如數據庫應用。
③ 非緩存 IO（不帶蓄流），對應圖中的路徑③，內核通用塊層的蓄流機制只給內核空間提供了接口來控制 IO 請求是否蓄流，用戶空間進程沒有辦法控制提交的 IO 請求進入通用塊層的時候是否蓄流。嚴格的說用戶空間直接產生的 IO 都會走蓄流路徑，哪怕是 IO 的時候附上了 “O_DIRECT” 和 ”O_SYNC” 標誌（可以參考《Linux 通用塊層介紹（part1: bio 層）》中的蓄流章節），用戶間接產生的 IO，如文件系統日誌數據、元數據，有的不會走蓄流路徑而是直接進入調度隊列儘快得到調度。注意一點，通用塊層的蓄流只提供機制和接口而不提供策略，至於需不需要蓄流、何時蓄流完全由內核中的 IO 派發者決定。
應用程序不管使用圖中哪條 IO 路徑，內核都會想方設法對 IO 進行合併。內核爲促進這種合併，在 IO 協議棧上設置了三個最佳狙擊點：
Cache （頁高速緩存）
Plug List （蓄流鏈表）
Elevator Queue （調度隊列）
cache 合併
IO 處在文件系統層的 page cache 中時只有 IO 數據，還沒有 IO 請求（bio 或 request）, 只有 page cache 在讀寫的時候纔會產生 IO 請求。本文主要介紹 IO 請求在通用塊層的合併，因此對於 IO 在 cache 層的合併只做現象分析，不深入到內部邏輯和代碼細節。
如果是緩存 IO, 用戶進程提交的寫數據會積聚在 page cache 中。cache 保存 IO 數據的基本單位爲 page, 大小一般爲 4K, 因此 cache 又叫 “頁高速緩存”， 用戶進程提交的小塊數據可以緩存到 cache 中的同一個 page 中，最後回寫線程將一個 page 中的數據一次性提交給通用塊層處理。以 dd 程序寫一個裸設備爲例，每次寫 1K 數據，連續寫 16 次：
dd if=/dev/zero of=/dev/sdb bs=1k count=16
通過 blktrace 觀測的結果爲：
blktrace -d /dev/sdb -o - | blkparse -i -
bio 請求在通用塊層的處理情況主要是通過第六列反映出來的，如果對 blkparse 的輸出不太瞭解，可以 man 一下 blktrace。對照每一行的輸出來看看應用程序產生的寫 IO 經由 page cache 之後是如何派發到通用塊層的：
現階段只關注 IO 是如何從 page cache 中派發到通用塊層的，所以後面的瀉流、派發過程沒有貼出來。回寫線程–kworker 以 8 個扇區（扇區大小爲 512B, 8 個扇區爲 4K 對應一個 page 大小）爲單位將 dd 程序讀寫的 1K 數據塊派發給通用塊層處理。dd 程序寫了 16 次，回寫線程只寫了 4 次（對應四次 Q），page cache 的緩存功能有效的合併了應用程序直接產生的 IO 數據。
文件系統層的 page cache 對讀 IO 也有一定的作用，帶緩存的讀 IO 會觸發文件系統層的預讀機制，所謂預讀有專門的預讀算法，通過判斷用戶進程 IO 趨勢，提前將存儲介質上的數據塊讀入 page cache 中，下次讀操作來時可以直接從 page cache 中命中，而不需要每次都發起對塊設備的讀請求。還是以 dd 程序讀一個裸設備爲例，每次讀 1K 數據，連續讀 16 次：
dd if=/dev/sdb of=/dev/zero bs=1K count=16
通過 blktrace 觀測的結果爲：
blktrace -d /dev/sdb -o - | blkparse -i -
同樣只關注 IO 是如何從上層派發到通用塊層的，不關注 IO 在通用塊層的具體情況，先不考慮 P，I，U，D，C 等操作，那麼上面的輸出可以簡單解析爲：
讀操作是同步的，所以觸發讀請求的是 dd 進程本身。dd 進程發起了 16 次讀操作，總共讀取 16K 數據，但是預讀機制只向底層發送了兩次讀請求，分別爲 0+32(16K), 32+64(32K)，總共預讀了 16 + 32 = 48K 數據，並保存到 cache 中，多預讀的數據可以爲後續的讀操作服務。
plug 合併
在閱讀本節之前可以先回顧下 linuxer 公衆號中介紹 bio 和 request 的系列文章，熟悉 IO 請求在通用塊層的處理，以及蓄流 (plug) 機制的原理和接口。特別推薦宋寶華老師寫的《文件讀寫（BIO）波瀾壯闊的一生》，通俗易懂地介紹了一個文件 io 的生命週期。
每個進程都有一個私有的蓄流鏈表，進程在往通用塊層派發 IO 之前如果開啓了蓄流功能，那麼 IO 請求在被髮送給 IO 調度器之前都保存在蓄流鏈表中，直到泄流 (unplug) 的時候才批量交給調度器。蓄流的主要目的就是爲了增加請求合併的機會，bio 在進入蓄流鏈表之前會嘗試與蓄流鏈表中保存的 request 進行合併, 使用的接口爲 blk_attempt_plug_merge(). 本文是基於內核 4.17 分析的，源碼來源於 4.17-rc1。
代碼遍歷蓄流鏈表中的 request，使用 blk_try_merge 找到一個能與 bio 合併的 request 並判斷合併類型，蓄流鏈表中的合併類型有三種：ELEVATOR_BACK_MERGE，ELEVATOR_FRONT_MERGE，ELEVATOR_DISCARD_MERGE。普通文件 IO 操作只會進行前兩種合併，第三種是丟棄操作的合併，不是普通的 IO 的合併，故不討論。
**bio 後向合併 (****ELEVATOR_****BACK_MERGE)**
爲了驗證 IO 請求在通用塊層的各種合併形式，準備了以下測試程序，該測試程序使用內核原生支持的異步 IO 引擎，可異步地向內核一次提交多個 IO 請求。爲了減少 page cache 和文件系統的干擾，使用 O_DIRECT 的方式直接向裸設備派發 IO。
iotc.c
...
/* dispatch 3 4k-size ios using the io_type specified by user */
#define NUM_EVENTS 3
#define ALIGN_SIZE 4096
#define WR_SIZE 4096
enum io_type {
SEQUENCE_IO,/* dispatch 3 ios: 0-4k(0+8), 4-8k(8+8), 8-12k(16+8) */
REVERSE_IO,/* dispatch 3 ios: 8-12k(16+8), 4-8k(8+8),0-4k(0+8) */
INTERLEAVE_IO, /* dispatch 3 ios: 8-12k(16+8), 0-4k(0+8),4-8k(8+8) */ ,
IO_TYPE_END
};
int io_units[IO_TYPE_END][NUM_EVENTS] = {
{0, 1, 2}, /* corresponding to SEQUENCE_IO */
{2, 1, 0}, /* corresponding to REVERSE_IO */
{2, 0, 1} /* corresponding to INTERLEAVE_IO */
};
char io_opt = "srid:"; / acceptable options */
int main(int argc, char *argv[])
{
int fd;
io_context_t ctx;
struct timespec tms;
struct io_event events[NUM_EVENTS];
struct iocb iocbs[NUM_EVENTS],
*iocbp[NUM_EVENTS];
int i, io_flag = -1;;
void *buf;
bool hit = false;
char *dev = NULL, opt;
/* io_flag and dev got set according the options passed by user , don’t paste the code of parsing here to shrink space */
fd = open(dev, O_RDWR | __O_DIRECT);
/* we can dispatch 32 IOs at 1 systemcall */
ctx = 0;
io_setup(32, &ctx);
posix_memalign(&buf,ALIGN_SIZE,WR_SIZE);
/* prepare IO request according to io_type */
for (i = 0; i < NUM_EVENTS; iocbp[i] = iocbs + i, ++i)
io_prep_pwrite(&iocbs[i], fd, buf, WR_SIZE, io_units[io_flag][i] * WR_SIZE);
/* submit IOs using io_submit systemcall */
io_submit(ctx, NUM_EVENTS, iocbp);
/* get the IO result with a timeout of 1S*/
tms.tv_sec = 1;
tms.tv_nsec = 0;
io_getevents(ctx, 1, NUM_EVENTS, events, &tms);
return 0;
}
測試程序接收兩個參數，第一個爲作用的設備，第二個爲 IO 類型，定義了三種 IO 類型：SEQUENCE_IO（順序），REVERSE_IO（逆序），INTERLEAVE_IO（交替）分別用來驗證蓄流階段的 bio 後向合併、前向合併和泄流階段的 request 合併。爲了減少篇幅，此處貼出的源碼刪除了選項解析和容錯處理，只保留主幹，原版位於：https://github.com/liuzhengyuan/iotc。
爲驗證 bio 在蓄流階段的後向合併，用上面的測試程序 iotc 順序派發三個寫 io:
# ./iotc**-d** **/dev/sdb**** -s**
-d 指定作用的設備 sdb， -s 指定 IO 方式爲 SEQUENCE_IO（順序），表示順序發起三個寫請求： bio0(0 + 8), bio1(8 + 8), bio2(16 + 8)。通過 blktrace 來觀察 iotc 派發的 bio 請求在通用塊層蓄流鏈表中的合併情況：
blktrace -d /dev/sdb -o - | blkparse -i -
上面的輸出可以簡單解析爲：
第一個 bio(bio0) 進入通用塊層時，此時蓄流鏈表爲空，於是申請一個 request 並用 bio0 初始化，再將 request 添加進蓄流鏈表，同時告訴 blktrace 蓄流已正式工作。第二個 bio(bio1) 到來的時候會走 blk_attempt_plug_merge 的邏輯，嘗試調用 bio_attempt_back_merge 與蓄流鏈表中的 request 合併，發現正好能合併到第一個 bio 所在的 request 尾部，於是直接返回。第三個 bio(bio2) 的處理與第二個同理。通過蓄流合併之後，三個 IO 請求最終合併成了一個 request(0 + 24)。用一副圖來展示整個合併過程：
**bio 前向合併 (****ELEVATOR_****FRONT_MERGE)**
爲驗證 bio 在蓄流階段的前向合併，使用 iotc 逆序派發三個寫 io:
# ./iotc**-d** **/dev/sdb**** -****r**
-r 指定 IO 方式爲 REVERSE_IO（逆序），表示逆序發起三個寫請求： bio0(16 + 8),bio1(8 + 8), bio2(0 + 8)。blktrace 的觀察結果爲：
blktrace -d /dev/sdb -o - | blkparse -i -
上面的輸出可以簡單解析爲：
與前面的後向合併相比，唯一的區別是合併方式由之前的”M” 變成了現在的”F”，即在 blk_attempt_plug_merge 中走的是 bio_attempt_front_merge 分支。通過下面的圖來展示前向合併過程：
“plug 合併” 不會做 request 與 request 的進階合併，蓄流鏈表中的 request 之間的合併會在泄流的時候做，即在下面介紹的 “elevator 合併” 中做。
elevator 合併
上面講到的蓄流鏈表合併是爲進程內的 IO 請求服務的，每個進程只往自己的蓄流鏈表中提交 IO 請求，進程間的蓄流鏈表相互獨立，互不干涉。但是，多個進程可以同時對一個設備發起 IO 請求，那麼通用塊層還需要提供一個節點，讓進程間的 IO 請求有機會進行合併。一個塊設備有且僅有一個請求隊列（調度隊列），所有對塊設備的 IO 請求都需要經過這個公共節點，因此調度隊列（Elevator Queue）是 IO 請求合併的另一個節點。
先回顧一下通用塊層處理 IO 請求的核心函數：blk_queue_bio(), 上層派發的 bio 請求都會流經該函數，或將 bio 蓄流到 Plug List，或將 bio 合併到 Elevator Queue, 或將 bio 生成 request 直接插入到 Elevator Queue。blk_queue_bio() 的主要處理流程爲：
其中”A” 標識的 “合併到蓄流鏈表的 request 中” 就是上一章介紹的 “plug 合併”。bio 如果不能合併到蓄流鏈表中接下來會嘗試合併到 “B” 標識的” 合併到調度隊列的 request 中”。” 合併到調度隊列的 request 中” 只是 “elevator 合併” 的第一個點。你可能已經發現了 blk_queue_bio() 將 bio 合併到蓄流鏈表或者將 request 添加進蓄流鏈表之後就沒管了，從路徑①可以發現蓄流鏈表中的 request 最終都是要交給電梯調度隊列的，這正是”elevator 合併” 的第二個點，關於泄流的時機請參考我之前寫的《Linux 通用塊層介紹（part1: bio 層）》。下面分別介紹這兩個合併點：
bio 合併到 elevator
先看 B 表示的代碼段：
blk_queue_bio:
switch (elv_merge(q, &req, bio)) {
case ELEVATOR_BACK_MERGE:
if (!bio_attempt_back_merge(q, req, bio))
break;
elv_bio_merged(q, req, bio);
free = attempt_back_merge(q, req);
if (free)
__blk_put_request(q, free);
else
elv_merged_request(q, req, ELEVATOR_BACK_MERGE);
goto out_unlock;
case ELEVATOR_FRONT_MERGE:
if (!bio_attempt_front_merge(q, req, bio))
break;
elv_bio_merged(q, req, bio);
free = attempt_front_merge(q, req);
if (free)
__blk_put_request(q, free);
else
elv_merged_request(q, req, ELEVATOR_FRONT_MERGE);
goto out_unlock;
default:
break;
}
合併邏輯基本與”plug 合併” 相似，先調用 elv_merge 接口判斷合併類型，然後根據是後向合併或是前向合併分別調用 bio_attempt_back_merge 和 bio_attempt_front_merge 進行合併操作，由於操作對象從蓄流鏈表變成了電梯調度隊列，bio 合併完了之後還需額外幹幾件事：
1. 調用 elv_bio_merged, 該函數會調用電梯調度器註冊的 elevator_bio_merged_fn 接口來通知調度器做相應的處理，對於 deadline 調度器而言該接口爲 NULL。
- 尋找進階合併，參考我之前寫的《Linux 通用塊層介紹（part2: request 層）》中對進階合併的描述，如果 bio 產生了後向合併，則調用 attempt_back_merge 試圖進行後向進階合併，如果 bio 產生了前向合併，則調用 attempt_front_merge 企圖進行前向進階合併。deadline 的進階合併接口爲 deadline_merged_requests， 被合併的 request 會從調度隊列中刪除。通過下面的圖示來展示後向進階合併過程，前向進階合併同理。
3. 如果產生了進階合併，則被合併的 request 可以釋放了，參考上圖，可調用 blk_put_request 進行回收。如果只產生了 bio 合併，合併後的 request 的長度和扇區地址都會發生變化，需要調用 elv_merged_request->elevator_merged_fn 來更新合併後的請求在調度隊列的位置。deadline 對應的接口爲 deadline_merged_request，其相應的操作爲將合併的 request 先從調度隊列移出再重新插進去。
“bio 合併到 elevator” 的合併形式只會發生在進程間，即只有一個進程在 IO 的時候不會產生這種合併形式，原因在於進程在向調度隊列派發 IO 請求或者試圖與將 bio 與調度隊列中的請求合併的時候是持有設備的隊列鎖得，其他進程是不能往調度隊列派發請求，這也是通用塊層單隊列通道窄需要發展多隊列的主要原因之一，只有進程在將調度隊列中的 request 逐個派發給驅動層的時候纔會將設備隊列鎖重新打開，即只有當一個進程在將調度隊列中 request 派發給驅動的時候其他進程纔有機會將 bio 合併到還未派發完的 request 中。所以想通過簡單的 IO 測試程序來捕捉這種形式的合併比較困難，這對兩個 IO 進程的 IO 產生時序有非常高的要求，故不演示。有興趣的可以參考上面的 github 倉庫，裏面有 patch 對內核特定的請求派發位置加上延時來改變 IO 請求本來的時序，從而讓測試程序人爲的達到這種碰撞效果。
request 在泄流的時候合併到 elevator
通用塊層的泄流接口爲：blk_flush_plug_list()， 該接口主要的處理邏輯如下圖所示
其中請求合併發生的點在__elv_add_request()。blk_flush_plug_list 會遍歷蓄流鏈表中的每個 request，然後將每個 request 通過 _elv_add_request 接口添加到調度隊列中，添加的過程中會嘗試與調度隊列中已有的 request 進行合併。
__elv_add_request:
case ELEVATOR_INSERT_SORT_MERGE:
/*
* If we succeed in merging this request with one in the
* queue already, we are done - rq has now been freed,
* so no need to do anything further.
*/
if (elv_attempt_insert_merge(q, rq))
break;
/* fall through */
case ELEVATOR_INSERT_SORT:
BUG_ON(blk_rq_is_passthrough(rq));
rq->rq_flags |= RQF_SORTED;
q->nr_sorted++;
if (rq_mergeable(rq)) {
elv_rqhash_add(q, rq);
if (!q->last_merge)
q->last_merge = rq;
}
q->elevator->type->ops.sq.elevator_add_req_fn(q, rq);
break;
泄流時走的是 ELEVATOR_INSERT_SORT_MERGE 分支，正如註釋所說的先讓蓄流的 request 調用 elv_attempt_insert_merge 嘗試與調度隊列中的 request 合併，如果不能合併則落入到 ELEVATOR_INSERT_SORT 分支，該分支直接調用電梯調度器註冊的 elevator_add_req_fn 接口將新來的 request 插入到調度隊列合適的位置。其中 elv_rqhash_add 是將新加入到調度隊列的 request 做 hash 索引，這樣做的好處是加快從調度隊列尋找可合併的 request 的索引速度。
在泄流的時候調度隊列中既有其他進程產生的 request，也有當前進程從蓄流鏈表中派發的 request（blk_flush_plug_list 是先將所有 request 派發到調度隊列再一次性 queue_unplugged，而不是派發一個 request 就 queue_unplugged）。所以 “request 在泄流的時候合併到 elevator” 既是進程內的，也可以是進程間的。
elv_attempt_insert_merge 的實現只做 request 間的後向合併，即只會將一個 request 合併到調度隊列中的 request 的尾部。這對於單進程 IO 而言足夠了，因爲 blk_flush_plug_list 在泄流的時候已經將蓄流鏈表中的 request 進行了 list_sort（按扇區排序）。筆者曾經提交過促進進程間 request 的前向合併的 patch（見 github），但沒被接收，maintainer–Jens 的解析是這種 IO 場景很難發生，如果產生這種 IO 場景基本是應用程序設計不合理。通過增加時間和空間來優化一個並不常見的場景並不可取。
最後通過一個例子來驗證進程內 “request 在泄流的時候合併到 elevator”，進程間的合併同樣對請求派發時序有很強的要求，在此不演示，github 中有相應的測試 patch 和測試方法。iotc 使用下面的方式派發三個寫 io:
# ./iotc**-d** **/dev/sdb**** -****i**
-i 指定 IO 方式爲 INTERLEAVE_IO（交替），表示按扇區交替的方式發起三個寫請求： bio0(16 + 8),bio1(8 + 8), bio2(0 + 8)。blktrace 的觀察結果爲：
blktrace -d /dev/sdb -o - | blkparse -i -
上面的輸出可以簡單解析爲：
bio0(16 + 8) 先到達 plug list，bio1(0+8) 到達時發現不能與 plug list 中的 request 合併，於是申請一個 request 添加到 plug list。bio2(8+8) 到達時首先與 bio1 進行後向合併。之後進程觸發泄流，泄流接口函數會將 plug list 中的 request 排序，因此 request(0+16) 先派發到調度隊列，此時調度隊列爲空不能進行合併。然後派發 request(16+8), 派發時調用 elv_attempt_insert_merge 接口嘗試與調度隊列中的其他 request 進行合併，發現可以與 request(0+16) 進行後向合併，於是兩個 request 合併成一個，最後向設備驅動派發的只有一個 request(0+24)。整個過程可以用下面的圖來展示：
小結
通過 cache 、plug 和 elevator 自上而下的三層狙擊，應用程序產生的 IO 能最大限度的進行合併，從而提升 IO 帶寬，降低 IO 延遲，延長設備壽命。page cache 打頭陣，既做數據緩存又做 IO 合併，主要是針對小塊 IO 進行合併，因爲使用內存頁做緩存，所以合併後的最大 IO 單元爲頁大小，當然對於大塊 IO,page cache 也會將它拆分成以頁爲單位下發，這不影響最終的效果，因爲後面還有 plug 和 elevator 補刀。plug list 竭盡全力合併進程內產生的 IO, 從設備的角度而言進程內產生的 IO 相關性更強，合併的可能性更大，plug list 設計位於 elevator queue 之上而且又是每個進程私有的，因此 plug list 既有利於 IO 合併，又減輕了 elevator queue 的負擔。elevator queue 更多的是承擔進程間 IO 的合併，用來彌補 plug list 對進程間合併的不足，如果是帶緩存的 IO，這種 IO 合併基本上不會出現。從實際應用角度出發，IO 合併更多的是發生在 page cache 和 plug list 中。
本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/nqPWdhyk4BpusRINHGxNTQ