从deadline调度看elevator

前言

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调度层
  • 块设备驱动层

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

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

后者就是引入MD和DM概念，比如RAID支持

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

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

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

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

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

前置知识之IO请求

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

见下图

bio-request

先从bio往下（bio_vec、segment）看起

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

这些segment由struct page组成：page可以作为一种寻址上的抽象，提供逻辑块号

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

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

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

同样，掌管众多request的request_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机制

batching和starved是运行时维护的字段，而fifo_batch和writes_starved则是一个限定的阈值，后者分别为16和2

batching

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

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

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

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

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

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

starved

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

小疑问：前向合并

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

合并的判断就很简单了，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

🔙 🔝