臺灣博碩士論文加值系統

摘要
最近，以 NAND flash memory 為基礎的SSD 正快速的發展，其優點具有體積小、重量輕、抗震性佳、低耗電量。但同時NAND flash memory存在著一些缺點，例如，讀取與寫入速度不均、無法原地更新資料、寫入/抹除次數有限，而這些缺點明顯地都跟「寫入」的動作有關，進而造成NAND flash memory的效能表現不佳。

為了改善SSD的寫入效能，一個方法是在SSD內部加入一塊RAM，我們稱之為write buffer，對於經常被存取的熱門資料可以直接在write buffer進行資料的更新，減少對NAND flash memory的寫入動作。本論文提出了Host-hinted Write Buffer Management Scheme，藉由主機端的提示將相關的資訊傳達給device端，透過跨階層(host與device)合作，藉由分享資訊，達到提升整體效能的目的。

以往資料被寫入write buffer只侷限當page cache發生replacement，在本論文中，我們同時考慮Page cache的replacement以及Linux flush機制[11]對於資料寫入write buffer的影響，當write buffer空間不足需要選擇踢除資料時，參考page cache提供的資訊，協助write buffer在執行置換策略時能更精確地選擇踢除的資料。從實驗結果顯示，我們的方法可以成功提升write buffer的hit ratio與減少寫入flash memory的次數。

Abstract
Recently, NAND flash memory-based SSD is developing rapidly. It has many advantages such as small size, light weight, high shock resistance, low power consumption. However, due to certain physical characteristic of NAND flash memory, it has the asymmetric speed of read and write operations, inability to in-place updates, limited number of write and erase times, and these disadvantages are clearly related to the action of writing, thus resulting in poor performance of NAND flash memory.

To address the issue, one of the methods is adding a piece of RAM, which is known as write buffer, in SSDs. Consequently, we can update the hot data in the write buffer directly, so as to eliminate the frequencies of writing to NAND flash memory. In this these, we propose a Host-hinted Write Buffer Management Scheme. By exploiting the cross-layer information, we convey the related host information to the device to improve the performance of the whole system.

Previously, data is written to the write buffer only when the data is replaced in page cache. In the thesis, we simultaneously considers the replacement the Linux flush operation in page cache to the impact the write buffer management. Specially, when the write buffer is full and needs to select a victim block for replacement, we utilizes the information passed from the page cache to help the write buffer to select the most appropriate victim block for replacement. From the experimental results, our proposed scheme can successfully increase the hit ratio of write buffer and reduce the number of write operations to the flash memory.

目錄

第一章 緒論 1
1.1　簡介 1
1.2　研究動機 2
1.3　貢獻 2
1.4　論文架構 3
第二章 背景知識與相關研究 4
2.1　SSD 4
2.2　Flash Translation Layer 6
2.2.1　Address Mapping 7
2.2.2　Garbage Collection 9
2.2.3　Wear Leveling 11
2.3　Page cache 11
2.3.1　CFLRU 11
2.4　Flush 13
2.4.1 定量的flush機制 13
2.4.2 定時的flush機制 14
2.5　Write buffer 15
2.5.1　FAB(Flash-aware-buffer management policy) 15
2.5.2　BPLRU (Block Padding Least Recently Used) 16
2.5.3　RFFE 18
第三章 Page cache-Aware Write buffer Management Scheme 21
3.1　系統架構 21
3.2　Page-Cache-Aware Management 22
3.2.1 置換策略的資訊 22
3.2.2 定量flush機制的資訊 23
3.2.2 定時flush機制的資訊 25
3.2.3 Dirty page個數 26
3.3 Page-Cache-Aware Write Buffer Management 28
3.4 運作流程 33
第四章 實驗結果與討論 35
4.1 實驗環境 35
4.2 實驗結果 36
第五章 結論及未來工作 45
參考文獻 46

圖目錄

圖 2 - 1 SSD架構 6
圖 2 - 2 Flash Translation Layer 6
圖 2 - 3 Address mapping 7
圖 2 - 4 Data block與Log block對應 8
圖 2 - 5 Full merge and Partial merge and Switch merge 10
圖 2 - 6 CFLRU 架構 12
圖 2 - 7 定量Flush 13
圖 2 - 8 定時Flush 14
圖 2 - 9 FAB架構 16
圖 2 - 10　BPLRU架構 17
圖 2 - 11　Page Padding 17
圖 2 - 12　Pseudorandom 18
圖 2 - 13　RFFE架構 19
圖 2 - 14　RFFE Eviction_(1) 20
圖 2 - 15　RFFE Eviction_(2) 20
圖 3 - 1　系統架構圖 21
圖 3 - 2　增強的置換策略 23
圖 3 - 3　定量Flush預測 24
圖 3 - 4　定量Flush至Write buffer 24
圖 3 - 5　定時Flush預測 25
圖 3 - 6　定時Flush至Write buffer 26
圖 3 - 7　Dirty pages的個數 27
圖 3 - 8　Dirty pages的計算 28
圖 3 - 9　資料形式 29
圖 3 - 10　資料被referenced 29
圖 3 - 11 Dirty pages個數的用意 30
圖 3 - 12 Dirty pages個數一樣時 30
圖 3 - 13 參考Hint queue踢除Block_(1) 31
圖 3 - 14 參考Hint queue踢除Block_(2) 32
圖 3 - 15 參考Hint queue踢除Block_(3) 32
圖 3 - 16 Eviction Window 33
圖 3 - 17 運作架構圖 34
圖 4 - 1　Hit ratio (Financial1) 36
圖 4 - 2　Hit ratio (Iozone) 37

圖 4 - 3 Hit ratio (Financial2 + fileserver 50%Working set) 37
圖 4 - 4 Hit ratio (Financial2 + fileserver 75%Working set) 38
圖 4 - 5　Number of evictions(Financial1) 39
圖 4 - 6　Number of evictions(Iozone) 39
圖 4 - 7　Number of evictions(Financial2 + fileserver 50%Working set) 40
圖 4 - 8　Number of evictions(Financial2 + fileserver 75%Working set) 40
圖 4 - 9　Total cleaning time taken(Financial1) 41
圖 4 - 10　Total cleaning time taken(Iozone) 41
圖 4 - 11 Total cleaning time taken(Financial2 + fileserver 50%Working set) 42
圖 4 - 12　Total cleaning time taken(Financial2 + fileserver 75%Working set) 42
圖 4 - 13 Response time (Financial1) 43
圖 4 - 14　Response time (Iozone) 43
圖 4 - 15 Response time (Financial2 + fileserver 50%Working set) 44
圖 4 - 16　Response time (Financial2 + fileserver 75%Working set) 44



表目錄

表 2 - 1　快閃記憶體的基本操作 5
表 4 - 1　實驗對象 34
表 4 - 2　Trace特性說明 34
表 4 - 3　Eviction Window size 34

參考文獻
[1] H. Jo, J.-U. Kang, S.-Y. Park, J.-S. Kim, and J. Lee, “FAB: Flash-aware
buffer management policy for portable media players,” IEEE Trans.
Consumer Electron., vol. 52, no. 2, pp. 485–493, May 2006.
[2] H. Kim and S. Ahn, “BPLRU: A buffer management scheme for
improving random writes in flash storage,” in Proc. 6th USENIX Conf.
File Storage Technol., 2008, pp. 1–14.
[3] S.-Y. Park, D. Jung, J.-U. Kang, J.-S. Kim, and J. Lee, “CFLRU: A
replacement algorithm for flash memory,” in Proc. Int. Conf. Compil.,
Arch. Synth. Embed. Syst., 2006, pp. 234–241.
[4] J. Seol, H. Shim, J. Kim, and S. Maeng, “A buffer replacement algorithm
exploiting multi-chip parallelism in solid state disks,” in Proc. Int. Conf.
Compil., Arch., Synth. Embed. Syst., 2009, pp. 137–146.
[5] Wu, Guanying, Xubin He, and Ben Eckart. "An adaptive write buffer management scheme for flash-based ssds." ACM Transactions on Storage (TOS) 8.1 (2012).
[6] L. Shi, C. J. Xue, and X. Zhou, “Cooperating write buffer cache and
virtual memory management for flash memory based systems,” in Proc.
17th IEEE Real-Time Embed. Technol. Appl. Symp., Apr. 2011, pp. 147–
156.
[7] "DiskSim," http://www.pdl.cmu.edu/DiskSim/.
[8]L. Shi, J. Li, C. J. Xue, C. Yang, and X. Zhou, “EXLRU: A unified
write buffer cache management for flash memory,” in Proc. ACM Int.
Conf. Embed. Softw., 2011, pp. 339–348.
[9]J.S Park, H.K Bahn and K. Koh, "Buffer Cache Management for Combined MLC and SLC Flash Memories Using both Volatile and Nonvolatile RAMs", IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, pp.228-235, 2009.
[10]N. Megiddo, D.S. Modha, ARC: a self-tuning, low overhead replacement cache,in: Proc. the Second USENIX Conference on File and Storage Technologies (FAST),Mar.-Apr.2003.
[11]Understanding the Linux Kernel,3rd Edition: http://www.johnchukwuma.com/training/UnderstandingTheLinuxKernel3rdEdition.pdf.
[12]Z. Li, P. Jin, X. Su, K. Cui, and L. Yue, “CCF-LRU: A new buffer
replacement algorithm for flash memory,” IEEE Trans. Consumer Electron.,
vol. 55, no. 3, pp. 1351–1359, Aug. 2009.
[13]J. Seol, H. Shim, J. Kim, and S. Maeng, “A buffer replacement algorithm
exploiting multi-chip parallelism in solid state disks,” in Proc. Int. Conf.
Compil., Arch., Synth. Embed. Syst., 2009, pp. 137–146.
[14]Extending SSD Simulator to Support Shared Channel between Packages International Journal of Applied Engineering Research ISSN 0973-4562 Volume 11, Number 6 (2016) pp 3915-3919. http://www.ripublication.com
[15]NADN flash memory and NOR flash memory : https://read01.com/Pa4APP.html#.WZxPbVEjGUk
[16]Porkumaran Karantharaj and Arul Selvan Ramasamy RFFE: A Buffer Cache Management Algorithm for Flash-Memory-Based SSD to Improve Write Performance , in Proc IEEE. VOL. 38, NO. 3, SUMMER 2015