臺灣博碩士論文加值系統

近年來，相對於傳統機械式硬碟，NAND快閃記憶體具有更高的存取性能和能源效率，因而被視為是機械式硬碟的有力競爭者。然而，由於NAND快閃記憶體特有的硬體特性，例如：頁面一次性寫入、批量抹除特性或寫入磨耗效應等，需要特有的管理機制，藉以提升資料之存取效能、可靠性及裝置壽命。傳統上，快閃儲存裝置的管理機制通常以裝置上的韌體形式實現，稱作快閃記憶體轉譯層。由於快閃記憶體轉譯層係由快閃儲存裝置上的控制器執行，只能取用裝置上計算能力、緩衝區等有限的運算資源，且無法利用如應用程式之資料存取模式等主機端資訊幫助管理，因而嚴重限制了快閃儲存裝置的性能。
為克服傳統快閃儲存裝置的固有限制，近年來已有多種相關技術被提出，如開放通道固態硬碟（open-channel solid-state disk, OCSSD）等。藉由將快閃記憶體轉譯層之大部份管理工作轉由主機端之處理器執行，開放通道固態硬碟得以利用主機端豐沛的運算資源，從而得以有效的提升快閃儲存裝置的效能與可靠性。然而，由於開放通道固態硬碟未對主機端之資料存取行為做任何限制，不但使得快閃記憶體轉譯層之設計更為複雜，且需要額外的緩衝區等運算資源。如何在不影響快閃儲存裝置的資料存取效能、主機端相容性與存取便利性的情況下，有效簡化在主機端執行之快閃記憶體轉譯層之設計，遂成一重要之研究議題。
為進一步簡化快閃記憶體的管理工作，新一代的開放通道固態硬碟採用了嶄新的存取介面，稱為分區命名空間固態硬碟（zoned namespace SSD, ZNS SSD）。藉由將固態硬碟的邏輯位址空間劃分為多個等大的分區（zone）分別管理，並限制各分區中的區塊只能被循序的寫入，便完全不再需要回收寫入資料後的儲存空間，這有效簡化了快閃記憶體轉譯層的設計。同時，僅有常被存取分區的元資料會隨需載入（on-demand loading）到主記憶體中，也可避免消耗過多主機端的主記憶體空間。然而，為應對不可避免的快閃記憶體壞塊（bad block），需要為分區預留額外的儲存空間以供替換。然而，由於快閃記憶體製程變異的問題，預留相同比例的額外空間，往往可能使某些壞塊較多的分區很快便無法使用，而影響到裝置之整體使用壽命；同時，對於某些幾無壞塊的分區，預留之額外空間卻顯多餘，而造成儲存空間的浪費。
基於上述觀察，在本論文中，我們針對分區命名空間固態硬碟提出了一個簡單、低成本卻高彈性的分區管理策略，擴充了既有緩衝分區的管理機制。藉由總體考量資料之存取模式、快閃記憶體的製程變異等因素，我們所提出之策略可同時提升空間利用率、裝置使用壽命以及資料存取的效能。透過一系列的分析和實驗，我們所提出機制之效果與可靠性均得到了妥善的驗證。

In recent years, due to the considerably higher access performance and run-time energy efficiency, NAND flash memory has become a competitive alternative to mechanical hard disks. However, due to the intrinsic characteristics of NAND flash memory, such as write-once property, bulk erase property, and wear-leveling effect, dedicated management mechanisms are indispensable to improve the access performance, data reliability, and device lifetime. Conventionally, these management mechanisms are often realized in the form of on-device firmware called the flash translation layer (FTL). However, as the FTL is executed by the controller on the flash storage device, it is often limited by the relative scarce on-device computation resources, such as the weaker processing power of the on-device controller and limited on-device buffer. Moreover, the device-side FTL cannot obtain or make use of the host-side knowledge, such as the data access patterns of applications, to assist its management tasks. All these issues have considerably limited the performance, reliability, and lifetime of flash memory devices, which must be addressed.
To overcome the natural limitations of conventional flash storage device, there have been quite a few relevant technologies proposed, such as the open-channel solid-state disks (OCSSDs). By offloading a majority part of the management tasks onto the host, OCSSDs can make use of the abundant computation resources on the host, thereby significantly improving the performance and reliability of flash storage devices. Nevertheless, OCSSDs do not impose any constraints on the data accesses of flash storage devices, which not only unnecessarily complicate the FTL designs of flash storage devices but also impose extra demands on the device-side RAM buffers. How to simplify the FTL designs without sacrificing the performance and convenience of data accesses, as well as the device compatibility, therefore becomes a research highlight.
To further simplify the management of flash memory, the latest generation of OCSSDs, the zoned namespace solid-state disks (ZNS SSDs), have been proposed. In particular, ZNS SSDs introduce a new access interface, which partitions the logical block address (LBA) space into a plural of equisized zones, and limits the logical blocks (LBs) in the same zone to be sequentially written in the ascending LBA order. As a zone becomes full, host applications may choose to reset the whole zone, before which the remaining live data must be manually migrated to other zones. Therefore, the host-side FTL does not need to perform the automatic garbage collection, which is the major source of the design complexities. Meanwhile, only the metadata of the frequently/recently written or read zones need to be on-demand loaded into the host-side RAM buffer, which reduces the overheads of the main memory space of the host machine. However, to replace the potentially emerging bad blocks, each zone must be allocated a fixed ratio of extra storage space on the flash memory. Due to the process variation of different flash blocks, the fixed ratio of extra storage space cannot replace all the bad blocks in some zones and incur unnecessary space overheads in some others, which leaves plenty of room for improvement.
To address the problems of existing management designs of ZNS SSDs, we present a simple, low-cost, and highly-flexible management strategy for zones, which generalizes the prior zone buffer designs. By jointly considering the patterns of data accesses and the process variation of flash blocks, the proposed strategy can effectively enhance the space utilization, device lifetime, and access performance. Our proposed strategy is then validated by a series of analytical and experimental studies, where the results are quite encouraging.

摘 要 i
ABSTRACT iii
Acknowledgements v
Table of Contents vi
List of Tables vii
List of Figures viii
Chapter 1 INTRODUCTION 1
Chapter 2 BACKGROUND: ZONED NAMESPACE SOLID-STATE DISKS (ZNS SSDS) 5
Chapter 3 SYSTEM ARCHITECTURE, PROBLEM DEFINITION, AND MOTIVATIONS 10
Chapter 4 ELASTIC ZONE MANAGEMENT FOR ZONED NAMESPACE SSDS 13
4.1 Overview 13
4.2 Working Principles of Elastic Zones 14
4.3 Management of Elastic Zones 18
4.4 Implementation Remarks 21
Chapter 5 EXPERIMENTAL STUDIES 23
5.1 Analytical Studies 23
5.2 Experimental Settings 24
5.3 Performance Results 25
Chapter 6 CONCLUSION AND FUTURE WORK 27
REFERENCES 28

[1]NVM Express® Base Specification. https://nvmexpress.org/developers/nvme-specification/.
[2]NVM Express Base Specification 2.0b. https://nvmexpress.org/wp-content/uploads/NVM-Express-Base-Specification-2.0b-2021.12.18-Ratified.pdf.
[3]P. O’Neil, E. Cheng, D. Gawlick, and E. O’Neil, "The log-structured merge-tree (LSM-tree)," Acta Informatica, vol. 33, no. 4, pp. 351-385, 1996.
[4]D. Lomet and C. Luo, "Efficiently reclaiming space in a log structured store," in 2021 IEEE 37th International Conference on Data Engineering (ICDE), 2021: IEEE, pp. 792-803.
[5]F. Mei, Q. Cao, H. Jiang, and L. Tian, "LSM-tree managed storage for large-scale key-value store," IEEE Transactions on Parallel and Distributed Systems, vol. 30, no. 2, pp. 400-414, 2018.
[6]P. Wang et al., "An efficient design and implementation of LSM-tree based key-value store on open-channel SSD," in Proceedings of the Ninth European Conference on Computer Systems, 2014, pp. 1-14.
[7]B. Fan, D. G. Andersen, M. Kaminsky, and M. D. Mitzenmacher, "Cuckoo filter: Practically better than bloom," in Proceedings of the 10th ACM International on Conference on emerging Networking Experiments and Technologies, 2014, pp. 75-88.
[8]B. Debnath, S. Sengupta, J. Li, D. J. Lilja, and D. H. Du, "BloomFlash: Bloom filter on flash-based storage," in 2011 31st International Conference on Distributed Computing Systems, 2011: IEEE, pp. 635-644.
[9]D. Eppstein, "Cuckoo filter: Simplification and analysis," arXiv preprint arXiv:1604.06067, 2016.
[10]H. Chen, L. Liao, H. Jin, and J. Wu, "The dynamic cuckoo filter," in 2017 IEEE 25th International Conference on Network Protocols (ICNP), 2017: IEEE, pp. 1-10.
[11]R. Pagh and F. F. Rodler, "Cuckoo hashing," Journal of Algorithms, vol. 51, no. 2, pp. 122-144, 2004.
[12]K. Huang and T. Yang, "Tagged Cuckoo Filters," in 2021 International Conference on Computer Communications and Networks (ICCCN), 2021: IEEE, pp. 1-10.
[13]S. Jeong, K. Lee, S. Lee, S. Son, and Y. Won, "{I/O} Stack Optimization for Smartphones," in 2013 USENIX Annual Technical Conference (USENIX ATC 13), 2013, pp. 309-320.
[14]R. Chen, Y. Wang, J. Hu, D. Liu, Z. Shao, and Y. Guan, "Unified non-volatile memory and NAND flash memory architecture in smartphones," in The 20th Asia and South Pacific Design Automation Conference, 2015: IEEE, pp. 340-345.
[15]M. O. Ojo, S. Giordano, G. Procissi, and I. N. Seitanidis, "A review of low-end, middle-end, and high-end IoT devices," IEEE Access, vol. 6, pp. 70528-70554, 2018.
[16]J. Zhang, D. Donofrio, J. Shalf, M. T. Kandemir, and M. Jung, "Nvmmu: A non-volatile memory management unit for heterogeneous gpu-ssd architectures," in 2015 International Conference on Parallel Architecture and Compilation (PACT), 2015: IEEE, pp. 13-24.
[17]Z. Fan, A. Haghdoost, D. H. Du, and D. Voigt, "I/o-cache: A non-volatile memory based buffer cache policy to improve storage performance," in 2015 IEEE 23rd International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems, 2015: IEEE, pp. 102-111.
[18]V. Seshadri, O. Mutlu, M. A. Kozuch, and T. C. Mowry, "The evicted-address filter: A unified mechanism to address both cache pollution and thrashing," in 2012 21st International Conference on Parallel Architectures and Compilation Techniques (PACT), 2012: IEEE, pp. 355-366.
[19]J. P. Casmira and D. R. Kaeli, "Modelling cache pollution," International Journal of Modelling and Simulation, vol. 18, no. 2, pp. 132-138, 1998.
[20]S. Khan, D. Bailey, and G. S. Gupta, "Simulation of triple buffer scheme (comparison with double buffering scheme)," in 2009 Second International Conference on Computer and Electrical Engineering, 2009, vol. 2: IEEE, pp. 403-407.
[21]G. N. Frederickson, "An optimal algorithm for selection in a min-heap," Information and Computation, vol. 104, no. 2, pp. 197-214, 1993.
[22]NVM Express. 2022. Zoned Namespace Command Set Specification. https://nvmexpress.org/wp-content/uploads/NVMZoned-Namespace-Command-Set-Specification-1.1b-2022.01.05- Ratified.pdf.
[23]Damien Le Moal, ZBC/ZAC Support in Linux, Western Digital, 2016. Available online at: https://www.snia.org/sites/default/files/SDC/2016/presentations/smr/ DamienLeMoal_ZBC-ZAC_Linux.pdf.
[24]P. O’Neil, E. Cheng, D. Gawlick, and E. O’Neil, "The log-structured merge-tree (LSM-tree)," Acta Informatica, vol. 33, no. 4, pp. 351-385, 1996.
[25]J. Li, Q. Wang, and P. P. Lee, "Efficient LSM-Tree Key-Value Data Management on Hybrid SSD/HDD Zoned Storage," arXiv preprint arXiv:2205.11753, 2022.