前言

Linux内核中的elevator layer就是IO调度层

之所以把IO视为电梯,是因为它的物理特性和生活上的电梯差不多:

  • 消费者(电梯)远跟不上生产者(乘客等待上下楼)的速度
  • 寻址方式说是随机访问(到哪都行),但其实条件苛刻(反方向哪怕只差一个楼层,也可能等半天)

deadline是elevator层中提供的一种具体调度算法,它只需实现elevator通用框架提供的一些接口即可

deadline作为本篇主角的原因是:

  • 这个比较好懂(CFQ BFQ写的什么鬼)
  • 知道IO优化面临的问题,和对应的解决方案
  • 流程较短,顺便了解一下block layer

注:由于历史原因,本文基于4.18.20

前置知识之块IO层

尽管deadline算法只有500行,但是直接看源码也是一头雾水的——你连它从哪里来,到哪里去都不知道,甚至连回调接口的参数类型也不知道是什么意思,这代码怎么读?

因此先上架构图(水时长)

block-io

可以看到,block IO分为三层:

  • 通用块层
  • IO调度层
  • 块设备驱动层

通用块层和块设备驱动层我也没关注过

前者大概是用于对具体设备做出一个抽象层,提供磁盘描述符、设备号映射机制等作用

后者就是引入MDDM概念,比如RAID支持

我们目前关注的,就是elevator,它的调度

从代码上来说,就是上层(VFS、mapper layer、具体文件系统)通过submit_bio()构造了一个IO请求bio

流经到IO调度层,经过elevator的调整(合并、排序)转换为另一个IO请求request

再下发到更下层的IO栈,此时IO请求可能已经成为一个面向驱动的命令,还是别的概念

好,现在知道了它的来源和去处

前置知识之IO请求

既然说到IO请求,那就需要理清一下前面提到的bio和request的关系

见下图

bio-request

先从bio往下(bio_vecsegment)看起

bio是由众多bio_vec维护,bio_vec描述一个段segment:从哪开始,长度多少

这些segmentstruct page组成:page可以作为一种寻址上的抽象,提供逻辑块号

可以注意到,一个bio多个bio_vec,它们各自指向的segment是允许离散的:因为它们访问的是逻辑块

但是落地到物理扇区,还是需要连续的,这就是bi_sector实际指向的位置。要得到它,是先要初始化好segment,再通过具体文件系统和mapper layer的配合才能拿到这些sector值(这是另一个故事了)

request,则可以有多个bio组成,通过bio间的bi_next字段就能找到属于这个request的所有bio

同样,掌管众多requestrequest_queue也可通过queuelist字段访问到属于它的所有request

elevator通用框架

elevator经过有哪些通用流程就不细说了(我也没看啊,天天催干活哪来这么多时间看)

需要了解的是,框架给了很多接口(下表为节选),并且调度器只需要实现一部分即可

接口 注释
elevator_merge_fn called to query requests for merge with a bio
elevator_merge_req_fn called when two requests get merged. the one which gets merged into the other one will be never seen by I/O scheduler again. IOW, after being merged, the request is gone.
elevator_merged_fn called when a request in the scheduler has been involved in a merge. It is used in the deadline scheduler for example, to reposition the request if its sorting order has changed.
elevator_dispatch_fn* fills the dispatch queue with ready requests. I/O schedulers are free to postpone requests by not filling the dispatch queue unless @force is non-zero. Once dispatched, I/O schedulers are not allowed to manipulate the requests - they belong to generic dispatch queue.
elevator_add_req_fn* called to add a new request into the scheduler
elevator_former_req_fn  
elevator_latter_req_fn These return the request before or after the one specified in disk sort order. Used by the block layer to find merge possibilities.
elevator_completed_req_fn called when a request is completed.

最常见的就是add_req操作,把一个request加入到IO调度队列里头

或者merge操作,把bio合入到request中,或者两个request之间合并

最后是dispatch操作,把request派发到下层的派发队列(dispatch queue)中

这里需要澄清的是,elevator层的调度发生于IO调度队列:这个“队列”是个抽象的概念,它可以是个数组、红黑树,也可以为空,取决于具体调度实现算法(后面就会看到deadline的IO调度队列形式)

而上述注释中的dispatch queue,我这里翻译为派发队列,可以认为进入到这个队列就是往下层走,逐渐脱离elevator层

deadline数据结构

elevator通用框架为具体调度算法提供自定义数据结构的机制

可以通过struct elevator_queue中的void *elevator_data字段获取

在deadline中,它实现的数据结构如下所示

 struct deadline_data {
 	/*
 	 * run time data
 	 */
 
 	/*
 	 * requests (deadline_rq s) are present on both sort_list and fifo_list
 	 */
 	struct rb_root sort_list[2];	
 	struct list_head fifo_list[2];
 
 	/*
 	 * next in sort order. read, write or both are NULL
 	 */
 	struct request *next_rq[2];
 	unsigned int batching;		/* number of sequential requests made */
 	unsigned int starved;		/* times reads have starved writes */
 
 	/*
 	 * settings that change how the i/o scheduler behaves
 	 */
 	int fifo_expire[2];
 	int fifo_batch;
 	int writes_starved;
 	int front_merges;
 };
 

首先关注前两个字段,它们是实质的调度队列容器:

  • 两棵红黑树,读写请求各一棵
  • 两个FIFO队列,读写请求各一队
  • 一个request,既存在于红黑树,也存在于FIFO
  • 红黑树按sector作为key排序,而FIFO按超时时间插入

(注:由于超时的时间点是递增的,所以FIFO就是直接插入,先进先出)

易行有效的优化手段

我们从调度队列中注意到什么?deadline关注到几个优化的点:

  • sector排序
  • 请求超时阈值
  • 读写分离

sector排序算是IO调度的共识了,可以使得硬件尽可能提供顺序访问,提高IO的吞吐量

超时阈值很显然与deadline这个名词有关。固定的IO顺序访问策略虽然有助于提高吞吐量,但可能会使得某些非顺序的IO请求等待延迟过大。因此,我们需要为一个IO请求的最坏处理时间做出担保,当IO请求的等待延迟达到一定的阈值时,将会优先处理

读写分离是个有意思的观点。可以这么认为,在多数情况下,读请求是需要同步处理的,而写请求更多是异步处理,既读操作需要及时处理,否则易造成IO上的block现象。为此,红黑树和FIFO队列都分离出读容器和写容器,在一般情况下,更倾向于优先获取读容器内的request。以FIFO为例,这种读写优先级分离的思想仍然存在,FIFO中的读操作的超时时间是500ms,而写操作则宽容到5s

权衡利弊:batching和starved机制

batchingstarved是运行时维护的字段,而fifo_batchwrites_starved则是一个限定的阈值,后者分别为16和2

batching

先来看batching机制。这是关于IO顺序访问的workaround。

next_rq[2]数组用于维护下一个sector有序的读请求或写请求(每次红黑树删除结点时顺手拿出,降低时间复杂度常数),它们是互斥的,既下标0(读)或下标1(写)其一非空。

因此dispatch阶段直接从next_rq取出可用的请求即可,保持寻址一路向前。

这种做法产生的问题是:反方向的请求会造成饥饿。

deadline的解决方案是提供batching计数,最多允许优先直接从next_rqbatching次,超过则至少要强制且成功从FIFO中拿到一次请求后才重新计数(注意:这里FIFO同样是读写分离,并优先从读FIFO中拿出)

这种做法是满足deadline语义的同时重新确认顺序执行的起始sector,既解决反向请求问题的同时处理即将超时的任务,也不会对后续顺序请求造成失效

starved

再说starved机制。很显然前面的读写分离、读尊写卑的思想会导致写饥饿问题,因此时域上不好衡量的问题(等多久才给一次写请求的机会?)就从频域来看,每writes_starved次读请求后需要有一次写请求的参与。这方法是不是简单又实用?

小疑问:前向合并

IO请求合并一般分为前向合并和后向合并。比如说,把刚来的bio请求放入到requestbio链表最后面就是后向合并

合并的判断就很简单了,bio有sector位置,那就直接往红黑树里头查找对应的边界就好了

deadline只提供前向合并,开关由front_merges控制

其实我也想知道为什么不提供后向?

(kernel doc中的描述反而感觉有些矛盾)

看看代码

链接如下,相信对照前面的介绍基本都能看明白

block/deadline-iosched.c - Linux source code (v4.18.20) - Bootlin

总结

2018年退役的时候,偶然看到一本开源书的标题——500 lines or less

大意就是用500行甚至更短的代码干完一件了不起的事情

其实现在看到的deadline也是恰好500行的量级

那么它的500行教会你什么?

  • 基本的IO优化策略,对IO进行合并与排序
  • 针对排序执行的问题,引入超时保底以解决无法覆盖的极端场合
  • 最关键的指出读与写的不同特性,并依此提出优先级的概念
  • 发现并针对上述可能产生写饥饿的问题,提供缓解方案
  • 一些数据结构上的小技巧,做法很简单,但显然是经过考虑而设计的

说到底就是一个发现并解决问题的过程。500行左右就能做到,我觉得很了不起了

References

《存储技术原理分析》

https://www.kernel.org/doc/Documentation/block/deadline-iosched.txt