PASS: a simple, efficient parallelism-aware solid state drive I/O scheduler

Hong-yan LI; Nai-xue XIONG; Ping HUANG; Chao GUI

doi:10.1631/jzus.C1300258

Your Location：

Home >

Browse articles >

PASS: a simple, efficient parallelism-aware solid state drive I/O scheduler

Computer & Automation | Updated：2022-05-19

- PASS: a simple, efficient parallelism-aware solid state drive I/O scheduler
- PASS：一种简单、高效、并行感知的固态盘I/O调度器
- Frontiers of Information Technology & Electronic Engineering Vol. 15, Issue 5, Pages: 321-336(2014)
- Affiliations：
  
  1.Wuhan National Laboratory for Optoelectronics, School of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan 430070, China
  2.School of Information Management, Hubei University of Economics, Wuhan 430205, China
  3.School of Computer Science, Colorado Technical University, Colorado Spring, CO 80907, USA
- Author bio：
  
  [ "Hong-yan LI, hongyanli78@aliyun.com" ]
  [ "Nai-xue XIONG, xiongnaixue@gmail.com" ]
  [ "Ping HUANG, pinghp.hust@gmail.com" ]
  [ "Chao GUI, gui_chao@126.com" ]
- Funds：
- DOI：10.1631/jzus.C1300258
  CLC： TP333
- Received：16 September 2013，
  
  Revised：2014-;4-11，
  
  Published：2014-05
- Accepted：
Scan QR Code
Hong-yan LI, Nai-xue XIONG, Ping HUANG, et al. PASS: a simple, efficient parallelism-aware solid state drive I/O scheduler[J]. Frontiers of Information Technology & Electronic Engineering, 2014, 15(5): 321-336.
DOI：

Hong-yan LI, Nai-xue XIONG, Ping HUANG, et al. PASS: a simple, efficient parallelism-aware solid state drive I/O scheduler[J]. Frontiers of Information Technology & Electronic Engineering, 2014, 15(5): 321-336. DOI： 10.1631/jzus.C1300258.

摘要

研究目的

随着半导体技术的日益成熟，基于半导体技术的固态盘被越来越多地应用到存储系统。然而，由于固态盘与机械式磁盘性能特征不同，现有的面向机械式磁盘的软件不能充分利用固态盘的独有特性，影响固态盘的性能发挥。现有Linux内核中的块层I/O调度器都是面向机械式磁盘的，因此，本文提出一种优化的、充分利用固态盘内部丰富并行性的I/O调度器--PASS。

创新要点

利用SSD底层丰富的内部特征，指导上层软件的设计和实现更好协同性能。特别是，利用其内部丰富的并行性实现了一个简单、高效的固态硬盘I/O调度器作为Linux内核模块，可以替代块层的I/O调度器集成到内核中工作。其性能优于现有的I/O调度器，同时提高了SSD寿命。

方法提亮

将逻辑存储空间分成若干固定大小的区域，并以区域为调度单位轮流调度。每次发送请求时只向区域发送与其内部并行性相匹配的请求数量，避免发送过多请求，引起性能下降。并且，将读、写请求分开，避免相互干扰。

重要结论

针对固态盘内部丰富的并行性，优化设计块层I/O调度器PASS，有针对性地在内核I/O调度层进行优化，充分利用了固态盘内部并行操作单元之间和单元之内的并行性。基于多种工作负载的实验表明，PASS在性能上优于Linux内核中现有的四种I/O调度器。

Abstract

Emerging non-volatile memory technologies

especially flash-based solid state drives (SSDs)

have increasingly been adopted in the storage stack. They provide numerous advantages over traditional mechanically rotating hard disk drives (HDDs) and have a tendency to replace HDDs. Due to the long existence of HDDs as primary building blocks for storage systems

however

much of the system software has been specially designed for HDD and may not be optimal for non-volatile memory media. Therefore

in order to realistically leverage its superior raw performance to the maximum

the existing upper layer software has to be re-evaluated or re-designed. To this end

in this paper

we propose PASS

an optimized I/O scheduler at the Linux block layer to accommodate the changing trend of underlying storage devices toward flash-based SSDs. PASS takes the rich internal parallelism in SSDs into account when dispatching requests to the device driver in order to achieve high performance. Specifically

it partitions the logical storage space into fixed-size regions (preferably the component package sizes) as scheduling units. These scheduling units are serviced in a round-robin manner and for every chance that the chosen dispatching unit issues only a batch of either read or write requests to suppress the excessive mutual interference. Additionally

the requests are sorted according to their visiting addresses while waiting in the dispatching queues to exploit high sequential performance of SSD. The experimental results with a variety of workloads have shown that PASS outperforms the four Linux off-the-shelf I/O schedulers by a degree of 3% up to 41%

while at the same time it improves the lifetime significantly

due to reducing the internal write amplification.

关键词

Keywords

references

N. Agrawal , , , V. Prabhakaran , , , T. Wobber , , , 等 . . Design tradeoffs for SSD performance . . Proc. USENIX Annual Technical Conf. , , 2008 . . p.57 - - 70 . . . .

D. Andersen , , , J. Franklin , , , M. Kaminsky , , , 等 . . Fawn: a fast array of wimpy nodes . . Proc. 22nd ACM Symp. on Operating Systems Principles , , 2009 . . p.1 - - 14 . . DOI: 10.1145/1629575.1629577 http://doi.org/10.1145/1629575.1629577 . .

A. Badam , , , V.S. Pai . . SSDAlloc: hybrid SSD/RAM memory management made easy . . Proc. 8th USENIX Symp. on Networked Systems Design and Implementation , , 2011 . . p.16 . .

M. Bhadkamkar , , , J. Guerra , , , L. Useche , , , 等 . . BORG: block-reorganization for self-optimizing storage systems . . Proc. 7th Conf. on File and Storage Technologies , , 2009 . . p.183 - - 196 . . . .

S. Boboila , , , P. Desnoyers . . Write endurance in flash drives: measurements and analysis . . Proc. 8th USENIX Conf. on File and Storage Technologies , , 2010 . . p.115 - - 128 . . . .

A.M. Caulfield , , , L.M. Grupp , , , S. Swanson . . Gordon: using flash memory to build fast, power-efficient clusters for data-intensive applications . . Proc. 14th Int. Conf. on Architectural Support for Programming Languages and Operating Systems , , 2009 . . p.217 - - 228 . . DOI: 10.1145/1508284.1508270 http://doi.org/10.1145/1508284.1508270 . .

A.M. Caulfield , , , Arup de , , , J. Coburn , , , 等 . . Moneta: a high-performance storage array architecture for next- generation, non-volatile memories . . Proc. 43rd Annual IEEE/ACM Int. Symp. on Microarchitecture , , 2010 . . p.385 - - 395 . . DOI: 10.1109/MICRO.2010.33 http://doi.org/10.1109/MICRO.2010.33 . .

A.M. Caulfield , , , T.I. Mollov , , , L.A. Eisner . . Providing safe, user space access to fast, solid state disks . . Proc. 17th Int. Conf. on Architectural Support for Programming Languages and Operating Systems , , 2012 . . p.387 - - 400 . . DOI: 10.1145/2150976.2151017 http://doi.org/10.1145/2150976.2151017 . .

F. Chen , , , D.A. Koufaty , , , X. Zhang . . Understanding intrinsic characteristics and system implications of flash memory based solid state drives . . Proc. 11th Int. Joint Conf. on Measurement and Modeling of Computer Systems , , 2009 . . p.181 - - 192 . . DOI: 10.1145/1555349.1555371 http://doi.org/10.1145/1555349.1555371 . .

F. Chen , , , R. Lee , , , X.. Zhang . . Essential roles of exploiting internal parallelism of flash memory based solid state drives in high-speed data processing . . Proc. 17th IEEE Int. Symp. on High Performance Computer Architecture , , 2011a . . p.266 - - 277 . . DOI: 10.1109/HPCA.2011.5749735 http://doi.org/10.1109/HPCA.2011.5749735 . .

F. Chen , , , T. Luo , , , X. Zhang . . CAFTL: a content-aware flash translation layer enhancing the lifespan of flash memory based solid state drives . . Proc. 9th USENIX Conf. on File and Storage Technologies , , 2011b . . p.1 - - 14 . . . .

M. Dunn , , , A.L.N. Reddy . . A New I/O Scheduler for Solid State Devices . . PhD Thesis, Texas A & M University, Texas, USA , , 2009 . . .

E. Gal , , , S. Toledo . . Algorithms and data structures for flash memories . . ACM Comput. Surv. , , 2005 . . 37 ( ( 2 ): ): 138 - - 163 . . DOI: 10.1145/1089733.1089735 http://doi.org/10.1145/1089733.1089735 . .

L.M. Grupp , , , J.D. Davis , , , S. Swanson . . The bleak future of NAND flash memory . . Proc. 10th USENIX Conf. on File and Storage Technologies , , 2012 . . p.2 . .

A. Gupta , , , R. Pisolkar , , , B. Urgaonkar , , , 等 . . Leveraging value locality in optimizing NAND flash-based SSDs . . Proc. 9th USENIX Conf. on File and Storage Technologies , , 2011 . . p.91 - - 103 . . . .

X.Y. Hu , , , E. Eleftheriou , , , R. Haas , , , 等 . . Write amplification analysis in flash-based solid state drives . . Proc. SYSTOR: the Israeli Experimental Systems Conf. , , 2009 . . p.10 DOI: 10.1145/1534530.1534544 http://doi.org/10.1145/1534530.1534544 . .

Y. Hu , , , H. Jiang , , , D. Feng , , , 等 . . Performance impact and interplay of SSD parallelism through advanced commands, allocation strategy and data granularity . . Proc. 25th Int. Conf. on Supercomputing , , 2011 . . p.96 - - 107 . . DOI: 10.1145/1995896.1995912 http://doi.org/10.1145/1995896.1995912 . .

H. Huang , , , W. Hung , , , K.G. Shin . . FS2: dynamic data replication in free disk space for improving disk performance and energy consumption . . Proc. 20th ACM Symp. on Operating Systems Principles , , 2005 . . p.263 - - 276 . . DOI: 10.1145/1095810.1095836 http://doi.org/10.1145/1095810.1095836 . .

S. Iyer , , , P. Druschel . . Anticipatory scheduling: a disk scheduling framework to overcome deceptive idleness in synchronous I/O . . 18th ACM Symp. on Operating Systems Principles , , 2001 . . p.117 - - 130 . . DOI: 10.1145/502059.502046 http://doi.org/10.1145/502059.502046 . .

J. Kim , , , Y. Oh , , , E. Kim , , , 等 . . Disk schedulers for solid state drives . . Proc. 7th ACM Int. Conf. on Embedded Software , , 2009 . . p.295 - - 304 . . DOI: 10.1145/1629335.1629375 http://doi.org/10.1145/1629335.1629375 . .

R. Koller , , , R. Rangaswami . . I/O deduplication: utilizing content similarity to improve I/O performance . . Proc. 8th USENIX Conf. on File and Storage Technologies , , 2010 . . p.16 DOI: 10.1145/10.1145/1837915.1837921 http://doi.org/10.1145/10.1145/1837915.1837921 . .

RS. Liu , , , C.L. Yang , , , W. Wu . . Optimizing NAND flash-based SSDs via retention relaxation . . Proc. 10th USENIX Conf. on File and Storage Technologies , , 2012 . . p.11 DOI: 10.1145/FAST.2010.1837921 http://doi.org/10.1145/FAST.2010.1837921 . .

Y. Lu , , , J. Shu , , , W. Zheng . . Extending the lifetime of flash-based storage through reducing write amplification from file systems . . Proc. 11th USENIX Conf. on File and Storage Technologies , , 2013 . . p.257 - - 270 . . . .

C. Mina , , , K. Kimb , , , H. Choc , , , 等 . . SFS: random write considered harmful in solid state drives . . Proc. 10th USENIX Conf. on File and Storage Technologies , , 2012 . . p.12 . .

S. Park , , , K. Shen . . FIOS: a fair, efficient flash I/O scheduler . . Proc. 10th USENIX Conf. on File and Storage Technologies , , 2012 . . p.13 . .

J. Ren , , , Q. Yang . . Ⅱ-CASH: intelligently coupled array of SSDs and HDDs . . Proc. 17th IEEE Int. Symp. on High Performance Computer Architecture , , 2011 . . p.278 - - 289 . . DOI: 10.1109/HPCA.2011.5749736 http://doi.org/10.1109/HPCA.2011.5749736 . .

M. Rosenblum , , , J.K. Ousterhout . . The design and implementation of a log-structured file system . . ACM Trans. Comput. Syst. , , 1992 . . 10 ( ( 1 ): ): 26 - - 52 . . DOI: 10.1145/146941.146943 http://doi.org/10.1145/146941.146943 . .

M. Saxena , , , M.M. Swift , , , Y. Zhang . . Flashtier: a lightweight, consistent and durable storage cache . . Proc. European Conf. on Computer Systems , , 2012 . . p.267 - - 280 . . DOI: 10.1145/2168836.2168863 http://doi.org/10.1145/2168836.2168863 . .

J. Schindler , , , S. Shete , , , K.A. Smith . . Improving throughput for small disk requests with proximal I/O . . Proc. 9th USENIX Conf. on File and Storage Technologies , , 2011 . . p.133 - - 147 . . . .

M. Wachs , , , M. Abd-El-Malek , , , E. Thereska , , , 等 . . Argon: performance insulation for shared storage servers . . Proc. 5th USENIX Conf. on File and Storage Technologies , , 2007 . . p.61 - - 76 . . . .

G. Wu , , , X. He . . Reducing SSD read latency via NAND flash program and erase suspension . . Proc. 10th USENIX Conf. on File and Storage Technologies , , 2012a . . p.117 - - 123 . . . .

G. Wu , , , X. He . . Delta-FTL: improving SSD lifetime via exploiting content locality . . Proc. 7th European Conf. on Computer Systems , , 2012b . . p.253 - - 266 . . DOI: 10.1145/2168836.2168862 http://doi.org/10.1145/2168836.2168862 . .

G. Wu , , , X. He , , , N. Xie , , , 等 . . DiffECC: improving SSD read performance using differentiated error correction coding schemes . . Proc. 18th Annual Meeting of the IEEE/ACM Int. Symp. on Modeling, Analysis and Simulation of Computer and Telecommunications Systems , , 2010 . . p.57 - - 66 . . DOI: 10.1109/MASCOTS.2010.15 http://doi.org/10.1109/MASCOTS.2010.15 . .

Y. Xu , , , S. Jiang . . A scheduling framework that makes any disk schedulers non-work-conserving solely based on request characteristics . . Proc. 9th USENIX Conf. on File and Storage Technologies , , 2011 . . p.119 - - 132 . . . .

Views

Downloads

CSCD

Alert me when the article has been cited

Submit

Tools

Publicity Resources

A vision of post-exascale programming

Related Author

Ji-dong ZHAI

Wen-guang CHEN

Related Institution

Department of Computer Science and Technology, Tsinghua University

Chat

Address：Zhejiang University Press, 148 Tianmushan Road, Hangzhou, China Postal code：310028
Tel：+86-571-88273162 Email：fitee@zju.edu.cn
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.

⁰