一种面向重尾分布的SSD磁盘调度算法*

魏元豪1，吴小华2，吴庆波1，邵立松1

(1.国防科学技术大学计算机学院,湖南 长沙 410073;2.二炮装备研究院四所，北京 100085)

摘要：存储设备上的大量文件其长度呈重尾态分布，IO请求的响应延迟和请求大小有着密切关系，并且固态硬盘的IO操作不对称。基于以上几点，在内核NOOP调度算法的基础上提出一种针对重尾数据分布下的IO调度算法。该算法通过减少大量小片请求的等待时间，提高固态硬盘的性能。经实验验证，相比内核的NOOP调度算法，平均响应时间减少17%。

关键词：IO调度；固态硬盘；重尾分布

中图分类号：TP333 文献标志码：A

doi:10.3969/j.issn.1007-130X.2015.06.002

收稿日期：*2014-03-28;修回日期：2014-05-14

作者简介:

通信地址：410073 湖南省长沙市国防科学技术大学计算机学院

Address:College of Computer,National University of Defense Technology,Changsha 410073,Hunan,P.R.China

An I/O scheduling algorithm of SSD based on heavy-tailed distributions

WEI Yuan-hao1,WU Xiao-hua2,WU Qing-bo1,SHAO Li-song1

(1.College of Computer,National University of Defense Technology,Changsha 410073;

2.The Fourth Research Institute of the Second Artillery Equipment Academy,Beijing 100085,China)

Abstract:The size of the files stored in the network server has heavy-tailed feature. Access latency is dependent on the size of the accessed files, and the IO operations of Solid State Disk (SSD) are asymmetric. Therefore, based on the kernel NOOP scheduling algorithm, we propose an I/O scheduling algorithm of SSD based on the heavy-tailed distributions to improve the performance of SSD access by reducing the waiting time for lots of small files. Experimental results show that the proposed algorithm can reduce response time by 17% on average compared with the kernel NOOP scheduling algorithm.

Key words:IO scheduler;SSD;heavy-tailed distributions

1引言

网络和存储设备上存在的大量数据呈现出重尾分布规律[1]，决定了IO请求中必然大量存在小片数据的请求，偶发大块数据请求[2]。固态硬盘SSD(Solid State Disk)存在读写不对称和写惩罚缺陷[3]。内核中的Deadline和CFQ(Completely Fair Queuing)调度算法过于繁杂，不适用于固态硬盘[4]。NOOP(NO OPeration)调度算法不考虑扇区位置，直接派发请求，适用于随机IO设备，但没有针对数据的重尾特性加入相应优化机制。文献[5]中设计的FIOS(Force Control I/O Server)调度算法，同时兼顾了调度的公平性和SSD的性能。但是，作者更多地是从SSD角度出发设计调度算法，没有针对特定的应用场景对调度算法加以优化。文献[6]中设计的整个IO系统仍然是从SSD的内部结构出发的。

本文在分析了应用层以及通用块层请求块大小统计规律的基础上，面向数据的重尾分布特性，以NOOP算法为基础设计并实现适用于固态硬盘的HTIOS(Heavy-Tailed distributions IO Scheduler)调度算法。……