刘正元: Linux 通用块层之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协议栈上设置了三个最佳狙击点：

l Cache （页高速缓存）

l Plug List （蓄流链表）

l 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

测试程序接收两个参数，第一个为作用的设备，第二个为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表示的代码段：

合并逻辑基本与”plug 合并”相似，先调用elv_merge接口判断合并类型，然后根据是后向合并或是前向合并分别调用bio_attempt_back_merge和bio_attempt_front_merge进行合并操作，由于操作对象从蓄流链表变成了电梯调度队列，bio合并完了之后还需额外干几件事：

1. 调用elv_bio_merged, 该函数会调用电梯调度器注册的elevator_bio_merged_fn接口来通知调度器做相应的处理，对于deadline调度器而言该接口为NULL。

2.寻找进阶合并，参考我之前写的《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与调度队列中的请求合并的时候是持有设备的队列锁得，其他进程是不能往调度队列派