一種面向重尾分布的SSD磁盤調(diào)度算法*

魏元豪1，吳小華2，吳慶波1，邵立松1

(1.國防科學技術(shù)大學計算機學院,湖南 長沙 410073;2.二炮裝備研究院四所，北京 100085)

摘要：存儲設(shè)備上的大量文件其長度呈重尾態(tài)分布，IO請求的響應延遲和請求大小有著密切關(guān)系，并且固態(tài)硬盤的IO操作不對稱?；谝陨蠋c，在內(nèi)核NOOP調(diào)度算法的基礎(chǔ)上提出一種針對重尾數(shù)據(jù)分布下的IO調(diào)度算法。該算法通過減少大量小片請求的等待時間，提高固態(tài)硬盤的性能。經(jīng)實驗驗證，相比內(nèi)核的NOOP調(diào)度算法，平均響應時間減少17%。

關(guān)鍵詞：IO調(diào)度；固態(tài)硬盤；重尾分布

中圖分類號：TP333 文獻標志碼：A

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

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

作者簡介:

通信地址：410073 湖南省長沙市國防科學技術(shù)大學計算機學院

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引言

網(wǎng)絡(luò)和存儲設(shè)備上存在的大量數(shù)據(jù)呈現(xiàn)出重尾分布規(guī)律[1]，決定了IO請求中必然大量存在小片數(shù)據(jù)的請求，偶發(fā)大塊數(shù)據(jù)請求[2]。固態(tài)硬盤SSD(Solid State Disk)存在讀寫不對稱和寫懲罰缺陷[3]。內(nèi)核中的Deadline和CFQ(Completely Fair Queuing)調(diào)度算法過于繁雜，不適用于固態(tài)硬盤[4]。NOOP(NO OPeration)調(diào)度算法不考慮扇區(qū)位置，直接派發(fā)請求，適用于隨機IO設(shè)備，但沒有針對數(shù)據(jù)的重尾特性加入相應優(yōu)化機制。文獻[5]中設(shè)計的FIOS(Force Control I/O Server)調(diào)度算法，同時兼顧了調(diào)度的公平性和SSD的性能。但是，作者更多地是從SSD角度出發(fā)設(shè)計調(diào)度算法，沒有針對特定的應用場景對調(diào)度算法加以優(yōu)化。文獻[6]中設(shè)計的整個IO系統(tǒng)仍然是從SSD的內(nèi)部結(jié)構(gòu)出發(fā)的。

本文在分析了應用層以及通用塊層請求塊大小統(tǒng)計規(guī)律的基礎(chǔ)上，面向數(shù)據(jù)的重尾分布特性，以NOOP算法為基礎(chǔ)設(shè)計并實現(xiàn)適用于固態(tài)硬盤的HTIOS(Heavy-Tailed distributions IO Scheduler)調(diào)度算法。該算法將優(yōu)先響應讀請求和小片寫請求，對大塊寫請求依據(jù)大小排序處理，減少存儲系統(tǒng)的平均IO響應時間。第2節(jié)概述HTIOS算法的設(shè)計基礎(chǔ)，第3節(jié)算法實現(xiàn)，第4節(jié)給出了實驗驗證。

2算法設(shè)計依據(jù)

2.1數(shù)據(jù)的重尾分布規(guī)律

重尾分布被證明是復雜系統(tǒng)中普遍存在的、本質(zhì)的而且不可消除的特性[7]。文獻[8]證明了UNIX文件系統(tǒng)中的文件長度具有重尾分布特性。文獻[9]以香農(nóng)信息理論為基礎(chǔ)證明了網(wǎng)絡(luò)文件長度呈重尾態(tài)分布。大量文獻已經(jīng)證明，在網(wǎng)絡(luò)空間存在的海量數(shù)據(jù)是呈重尾態(tài)分布的。而重尾態(tài)分布具有以下分布規(guī)律：(1)樣本空間中大量的小抽樣觀察值和少量的大抽樣觀察值并存；(2)大抽樣值決定抽樣的均值和方差；(3)重尾分布表現(xiàn)出強烈的局部突發(fā)性[1]。

網(wǎng)絡(luò)空間的數(shù)據(jù)分布規(guī)律縮放到單個的Web服務器數(shù)據(jù)仍然是成立的[8]。由于應用的特殊性，Web服務器存在大量的HTML文件、圖片和少量的動畫，這樣客觀形成一個重尾場景。我們研究國內(nèi)主要媒體及電商的Web服務器均可以得到類似的分布規(guī)律。例如天貓網(wǎng)的Web服務器數(shù)據(jù)分布圖1所示。

Figure 1　Length distribution of Tmall Web files 圖1　天貓網(wǎng)Web服務器文件長度分布

這就表明這種重尾數(shù)據(jù)應用場景確實存在，而針對這種應用場景優(yōu)化系統(tǒng)軟件也是有必要的。

2.2操作系統(tǒng)IO層次

Linux操作系統(tǒng)的IO層次可以概括為如圖2所示的結(jié)構(gòu)。文件系統(tǒng)層在文件級別實現(xiàn)對數(shù)據(jù)的管理，而文件又被組織為不同粒度的邏輯塊。如ext4文件系統(tǒng)的邏輯塊大小為4 KB。IO請求經(jīng)過文件系統(tǒng)層被均勻切分為4 KB粒度的塊請求。由于小文件通常在 KB級別，大量小文件在10 KB以下。所以,對小文件的IO請求在通用塊層被合并的概率很小。而大文件通常在MB級別，大的視頻文件可以在GB級別。所以，對大文件的IO請求在通用塊層很容易被相鄰合并成大塊的數(shù)據(jù)請求。

Figure 2　Linux system’s IO hiberarchy 圖2　Linux系統(tǒng)IO層次

我們將從電商網(wǎng)站下載獲得的數(shù)據(jù)作為樣本空間，將樣本空間置于SSD上并做隨機IO。測試用固態(tài)硬盤為Kingston SVP200S37A/120 GB。得到的通用塊層的(塊請求)request大小分布圖如圖3所示。

Figure 3　Size of generic block layer request distribution 圖3　通用塊層request大小分布

由此實驗知，經(jīng)過文件系統(tǒng)對應用層IO請求的4 KB粒度均勻化，以及通用塊層的相鄰合并后，request大小依然表現(xiàn)出應用層的數(shù)據(jù)重尾分布特性。因此，在IO調(diào)度層對IO請求做出優(yōu)化是合理的。

2.3request塊大小與響應時間關(guān)系

在上述實驗環(huán)境下，對樣本空間做隨機讀寫。并對request延遲進行統(tǒng)計，放大10倍后的結(jié)果如圖4所示。

Figure 4　Relationship between request delay and size 圖4　request延遲及大小分布關(guān)系

圖4測試結(jié)果表明，請求大小和請求延遲有著非常緊密的統(tǒng)計關(guān)系。絕大多數(shù)的小片數(shù)據(jù)請求響應延遲很短。對圖4再做5倍放大，結(jié)果如圖5所示。圖5中1 320～1 360中間有大量的小片request請求被大塊request阻塞延遲，并與隨后的大塊request請求造成更大的擁塞波峰。進一步針對SSD的讀實驗結(jié)果如圖6所示。結(jié)果顯示，讀請求延遲的變化不大。

Figure 5　5 times enlarged Figure 4 圖5　5倍放大圖4

Figure 6　Delay of read request 圖6　讀請求延遲

以上實驗表明，重尾數(shù)據(jù)下突發(fā)性的大塊數(shù)據(jù)寫請求會造成SSD響應延遲陡然增大，極易出現(xiàn)局部性能崩塌。因此，調(diào)度算法中應該針對這一特征進行優(yōu)化。

3HTIOS調(diào)度算法

基于第2節(jié)的分析，本文在HTIOS調(diào)度算法中針對重尾數(shù)據(jù)分布下突發(fā)性的大塊寫請求予以優(yōu)化。

3.1排序優(yōu)化

不同大小的請求按不同順序處理，其平均響應延遲差距巨大。圖7模擬請求先后順序不同造成的延遲差異。

Figure 7　Sort optimization 圖7　排序優(yōu)化效果

令大塊數(shù)據(jù)請求延遲為t，而小片數(shù)據(jù)請求延遲為r，則不難計算出前者的平均延遲為(4t+6r)/4，而后者為(t+9r)/4。當t遠大于r的時候，排序優(yōu)化效果就會非常明顯。

由第2節(jié)實驗知，讀請求和小片寫請求延遲都很小，HTIOS算法中將這兩類請求優(yōu)先派發(fā)。重尾數(shù)據(jù)分布下的突發(fā)性大塊數(shù)據(jù)請求，其響應延遲陡然增加。所以，針對大塊的寫請求在HTIOS中依據(jù)大小排序，并依序派發(fā)。

為避免大塊寫請求過度饑餓，本文借鑒Deadline算法，加入饑餓閾值。當大塊寫請求被饑餓次數(shù)到達閾值時，泄流大塊寫請求?；谡埱蟠笮〉呐判蜿犃袃?yōu)先處理小請求，而如果不斷有小請求加入，大塊請求會長時間得不到響應，甚至餓死。本文借鑒Deadline算法引入超時時間，為寫請求加入時間戳。HTIOS調(diào)度算法檢測并派發(fā)超時請求，保證不會有請求被餓死。

3.2算法實現(xiàn)

HTIOS調(diào)度算法流程如圖8所示。如果有超時請求，調(diào)度器直接將超時請求派發(fā)出去；沒有超時請求時，優(yōu)先派發(fā)讀請求或小片寫請求。只有當大塊寫請求饑餓或者沒有高優(yōu)先級請求時，調(diào)度器才派發(fā)大塊寫請求。

Figure 8　Flowchart of HTIOS 圖8　HTIOS算法流程圖

4性能測評

測試環(huán)境為：Linux 2.6.32內(nèi)核，Sparc處理器，4 GB內(nèi)存，固態(tài)硬盤為Kingston SVP200S37A/ 120 GB。實驗中的負載為每個進程400次的隨機IO操作，實驗設(shè)計并發(fā)量分別為20、40、60。

內(nèi)核中四種調(diào)度器，只有NOOP調(diào)度器是為隨機存儲設(shè)備設(shè)計的。NOOP與其他三種調(diào)度器的平均延遲對比如圖9所示，可見NOOP存在一定優(yōu)勢。

Figure 9　Performance comparison of kernel IO algorithm 圖9　內(nèi)核IO調(diào)度算法性能對比

如圖10所示為HTIOS調(diào)度算法相比NOOP的優(yōu)化效果。

Figure 10　Performance comparison between HTIOS and NOOP 圖10　HTIOS與NOOP性能對比

三種并發(fā)量下HTIOS調(diào)度算法比NOOP算法的優(yōu)化比分別為9%、17%和15%。在低并發(fā)量時，調(diào)度隊列相對較空閑，所以大塊請求對小片請求的遲滯作用較小。在較高并發(fā)環(huán)境下調(diào)度隊列相對繁忙，故而大塊數(shù)據(jù)請求極易阻塞后續(xù)小片數(shù)據(jù)請求。所以，并發(fā)量為20時的優(yōu)化比,較之并發(fā)量為40時的優(yōu)化比略小。過度擁擠的調(diào)度隊列，空間被大多數(shù)小請求占據(jù)，大塊請求無論何時發(fā)生都會擁塞后面小請求。故而優(yōu)化效果隨著并發(fā)量的逐漸增加呈減小趨勢。實驗結(jié)果中，并發(fā)量增加到60后優(yōu)化比有所下降。

5結(jié)束語

固態(tài)硬盤提高了存儲系統(tǒng)的性能，打破了機械硬盤的物理屏障。重尾態(tài)數(shù)據(jù)的突發(fā)性大塊寫請求，極易造成其后的小片數(shù)據(jù)請求被長時間遲滯。本文針對數(shù)據(jù)的重尾分布特性，設(shè)計并實現(xiàn)了HTIOS

調(diào)度算法。不同并發(fā)量的負載測試表明，HTIOS調(diào)度算法可以有效地減小固態(tài)硬盤在重尾態(tài)數(shù)據(jù)下的平均響應時間，因此，有效地改善了重尾數(shù)據(jù)下固態(tài)硬盤存儲系統(tǒng)的IO性能。

參考文獻:

[1]Crovella M E,Taqqu M S,Bestavros A. Heavy-tailed probability distributions in the World Wide Web[M]//A Practical Guide to Heavy Tails:Statistical Technique and Applications,1998:3-25.

[2]Crovella M E. Self-similarity in World Wide Web traffic:Evidence and possible causes[C]//Proc of IEEE/ACM Transactions on Networking,1997:835-846.

[3]Kang J U,Kim J S,Park C,et al. A multi-channel architecture for high-performance NAND flash-based storage system[J]. Journal of Systems Architecture,2007,53:644-658.

[4]Love R. Linux kernel development [M]. Beijing:China Machine Press,2013.

[5]Park S,Shen Kai. FIOS:A fair,efficient flash I/O scheduler[C]//Proc of the 10th VSENIX Conference on File and Starage Technologies,2012:1-15.

[6]Kang S,Park H,Yoo C. Performance enhancement of I/O scheduler for solid state devices[C]//Proc of IEEE International Conference on Consumer Electronics,2011:31-32.

[7]Shao Li-song.Research on Internet end-to-end congestion control algorithms[D].Changsha:National University of Defense Technilogy,2006.(in Chinese)

[8]Kihong P,Kim G,Crovella M. On the relationship between file sizes,transport protocols,and self-similar network traffic[C]//Proc of the 1996 International Conference on Network Protocols,1996:171-180.

[9]Fabrikant A,Koutsoupias E,Papadimitriou C H.Heuristically optimized trade-offs:A new paradigm for power-laws in the Internet[C]//Proc of Internet Colloqium on Automata,Languages,and Programming(ICALP),2002:110-122.

[10]Park S,Kim Y,Urgaonkar B,et al. A comprehensive study of energy efficiency and performance of flash-based SSD [J]. Journal of Systems Architecture,2011,57:354-365.

參考文獻：附中文

[7]邵立松. 互聯(lián)網(wǎng)端到端擁塞控制算法研究[D].長沙：國防科學技術(shù)大學，2006.

魏元豪(1986-),男,河南鶴壁人，碩士生，研究方向為固態(tài)硬盤性能優(yōu)化。E-mail:weiyuanhao@126.com

WEI Yuan-hao,born in 1986,MS candidate,his research interest includes performance optimization of solid state drive.