WABE: Rethinking B-epsilon-tree to Minimize Write-amplification on NAND Flash Memory

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：26

、訪客IP：3.133.154.2

姓名

彭懷德(Huai-De Peng) 查詢紙本館藏

畢業系所

資訊工程學系

論文名稱

(WABE: Rethinking B-epsilon-tree to Minimize Write-amplification on NAND Flash Memory)

相關論文

★ 重新思考虛擬記憶體管理的方式以開放通道式固態硬碟最大限度地減少深度學習推薦系統演算法的讀寫流量	★ 開啟製程相似檢查方法在組裝超級塊上以最小化額外的寫入延遲
★ LaDy: Enabling Locality-aware Deduplication Technology on Shingled Magnetic Recording Drives	★ On Minimizing Writing Overhead to Establish a Low-latency LSM-tree on Skyrmion-based Racetrack Memory
★ Rethinking Bϵ tree Indexing Structure over NVM with the Support of Multi-write Modes	★ Prophet’s Insight: Unleashing Deduplication System Performance in Multi-tier Storage Systems
★ Freeing the Power of High Parallelism: Accelerating the Bϵ-Tree Indexing Scheme Performance on Open-Channel SSD	★ Applying Content-Defined Chunking to OCSSD-based Deduplication Systems
★ GraLoc: Preserving Graph Locality to Minimize Read and Write Amplification on NAND Flash Memory	★ On Minimizing Writing Overhead to Establish a Low-latency LSM-tree on Skyrmion-based Racetrack Memory

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

至系統瀏覽論文 (2026-1-4以後開放)

摘要(中)

固態硬碟(Solid state drive)已被廣泛使用在現代存儲設備中，因為它具有出色的存取性能和高能效，而開放通道式固態硬碟(Open-channel solid state drive)是一種新型態的固態硬碟，具有潛力改善傳統固態硬碟較大的尾延遲，且能達成可預測的讀寫延遲。另一方面B-epsilon-tree (B^ε Tree)是一種特殊的寫入優化數據結構之一。我們觀察到B^ε Tree可能導致固態硬碟上嚴重的寫入放大問題，為了減輕寫入放大的影響，透過重新思考B^ε Tree的設計。我們提出了WABE，它由一個輔助索引結構與雙刷新選擇器組成以最大限度地減少上固態硬碟的寫入放大。廣泛的實驗表明 WABE在固態硬碟上的顯著減輕了62–91.4%寫入請求大小與基線的B^ε Tree相比。

摘要(英)

Solid state drive (SSDs) has been widely used in modern storage devices because of its excellent access performance and large bandwidth, and Open-channel solid state drive (OCSSD) is a new type SSDs have the potential to improve the large tail latency of traditional SSDs and can achieve predictable I/O latency. On the other hand, B-epsilon-tree (B^ε Tree) is one of the special write-optimized data structures. We observed that B^ε Tree may cause serious write amplification problems on SSDs. In order to mitigate the impact of write amplification, we rethink the design of B^ε Tree and propose WABE, which consists of an auxiliary index structure and propose dual flush selectors to minimize write amplification on SSDs. According to the experimental results, WABE significantly reduces the write request size by 62–91.4% on SSDs compared with the baseline B^ε Tree.

關鍵字(中)

★ 存儲設備
★ 開放通道式固態硬碟
★ B-epsilon-tree
★ 寫入放大

關鍵字(英)

論文目次

Chapter 1 Introduction 1
Chapter 2 Background and Motivation 4
2.1 OCSSD 4
2.2 B^ε Trees 6
2.2.1 Operation of B^ε Trees 8
2.2.2 Flush mechanism 10
2.3 Motivation 11
Chapter 3 Methodology 13
3.1 The Overview of WABE Scheme13
3.1.1 WABE metadata design 16
3.1.2 Write append and remap 17
3.2 Root flush selector 21
3.3 Internal flush selector 24
Chapter 4 Experiment and Evaluation 26
4.1 Experiment Setup 26
4.2 Trace Information 28
4.3 Evaluation Metrics and Result 28
4.3.1 Write Request Average Size 29
4.3.2 Write Average Latency 33
5 Conclusion 37
Reference 38

參考文獻

[1] Y. Luo, M. Lin, Y. Pan, and Z. Xu. Dual locality-based flash translation layer for nand flash-based consumer electronics. IEEE Transactions on Consumer Electronics, 68(3):281–290, 2022.
[2] M.-C. Yang, Y.-M. Chang, C.-W. Tsao, P.-C. Huang, Y.-H. Chang, and T.-W. Kuo. Garbage collection and wear leveling for flash memory: Past and future. In 2014 International Conference on Smart Computing, pages66–73. IEEE, 2014.
[3] Matias Bjørling, Javier Gonzalez, Philippe Bonnet. LightNVM: The Linux Open-Channel SSD Subsystem. in the Proceedings of the 15th USENIX Conference on File and Storage Technologies (FAST ’17), pages 359, February 27–March 2, 2017.
[4] Michael A. Bender, Martin Farach-Colton, William Jannen, Rob Johnson, Bradley C. Kuszmaul, Donald E. Porter, Jun Yuan, and Yang Zhan. An Introduction to B^ε-trees and Write-Optimization.;login Usenix:, Vol. 40, No. 5, pages 22, October 2015.
[5] Hongwei Qin, Dan Feng, Wei Tong∗, Jingning Liu, Yutong Zhao.QBLK: Towards Fully Exploiting the Parallelism of Open-Channel SSDs. 2019 Design, Automation & Test in Europe Conference & Exhibition (DATE), pages 1064, 25-29 March 2019.
[6] Jhuyeong Jhin, Hyukjoong Kim, Dongkun Shin. Optimizing Host-level Flash Translation Layer with Considering Storage Stack of Host Systems. IMCOM ′18: The 12th International Conference on Ubiquitous Information Management and Communication, January 5 - 7, 2018.
[7] William Jannen, Jun Yuan, Yang Zhan, Amogh Akshintala,John Esmet, Yizheng Jiao, Ankur Mittal, Prashant Pandey, and Phaneendra Reddy, Leif Walsh, Michael Bender, Martin Farach-Colton, Rob Johnson, Bradley C, Kuszmaul, Donald E. Porter.BetrFS: A Right-Optimized Write-Optimized File System. In the Proceedings of the 13th USENIX Conference on File and Storage Technologies (FAST ’15), February 16–19, 2015.
[8] Yang Zhan, Alex Conway, Yizheng Jiao, Eric Knorr, Michael A. Bender, Martin Farach-Colton, William Jannen, Rob Johnson, Donald E. Porter, Jun Yuan. The Full Path to Full-Path Indexing.In the Proceedings of the 16th USENIX Conference on File and Storage Technologies, pages 124-125, February 12–15, 2018.
[9] G. S. Brodal and R. Fagerberg. Lower bounds for external memory dictionaries. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2003.
[10] A. L. Buchsbaum, M. Goldwasser,S. Venkatasubramanian, and J. R. Westbrook. “On external memory graph traversal," in Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 859-860, 2000.
[11] Yifan Qiao, Xubin Chen, Ning Zheng, Jiangpeng Li, and Yang Liu, Tong Zhang. Closing the B+-tree vs. LSM-tree Write Amplification Gap on Modern Storage Hardware with Built-in Transparent Compression. In the Proceedings of the 20th USENIX Conference on File and Storage Technologies, February 22–24, 2022.
[12] Tokutek, Inc. TokuDB: MySQL Performance, MariaDB Performance. http://www.tokutek.com/products/tokudb-for-mysql/.
[13] Y. Hu, H. Jiang, D. Feng, L. Tian, H. Luo, and S. Zhang. Performance impact and interplay of ssd parallelism through advanced commands, allocation strategy and data granularity. In Proceedings of the international conference on Supercomputing, pages 96–107, 2011.
[14] O. Eytan, D. Harnik, E. Ofer, R. Friedman, and R. Kat. It’s time to revisit lru vs. fifo. In 12th USENIX Workshop on Hot Topics in Storage and File Systems(HotStorage 20), 2020.
[15] TPC-H. http://www.tpc.org/tpch/.
[16] Brian F. Cooper, Adam Silberstein, Erwin Tam, Raghu Ramakrishnan, and Russell Sears. Benchmarking cloud serving systems with ycsb. In Proceedings of the 1st ACM Symposium on Cloud Computing, page 143–154, New York, NY, USA, 2010.

指導教授

陳增益

審核日期

2023-1-4

推文