A Novel B-Tree Index with Cascade Memory Nodes for Improving Sequential Write Performance on Flash Storage Devices
Source abstract
Abstract
Flash storage devices such as solid-state drives and multimedia cards have been widely used in various applications because of their fast access speed, low power consumption, and high reliability. They consist of NAND flash memories that perform slow block erasures before overwriting data on a prewritten page. This characteristic can lead to performance degradation when applying the original B-tree on the flash storage device without any changes. Although various B-trees have been proposed for flash memory, they still require many flash operations that degrade overall performance. To address the problem, we propose a novel B-tree index structure that reduces the number of write operations and improves the sequential writes by employing cascade memory nodes. The proposed B-tree index structure delays the updates for the modified B-tree nodes and later performs batch writes in a cascade manner. Also, when records with continuous key values are sequentially inserted, the proposed B-tree index structure does not split the leaf node so that it improves write throughput and page utilization. Through mathematical analysis and experimental results, we show that the proposed B-tree index structure always yields better performance than existing techniques.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Advanced Data Storage Technologies · Caching and Content Delivery · Algorithms and Data Compression
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
FW Nextgen Tech, SK Hynix, Icheon 467010, Korea
Department of Computer Science and Engineering, Hanyang University, Ansan 15588, Korea
Funding
National Research Foundation of Korea
References (48)
Show source-provided references
1. Grupp, L.M., Davis, J.D., and Swanson, S. (2012, January 15–17). The Bleak Future of NAND Flash Memory. Proceedings of the 10th USENIX Conference on File and Storage Technologies (FAST), San Jose, CA, USA.
2. Harari, E. (2012, January 19–23). Flash Memory—The Great Disruptor!. Proceedings of the 2012 IEEE International Solid-State Circuits Conference Digest of Technical Papers (ISSCC), San Francisco, CA, USA.
3. NAND Flash Memory: Challenges and Opportunities10.1109/MC.2013.190 ↗
4. (2019, December 12). Samsung Electronics. Available online: https://www.alldatasheet.com/.
5. Algorithms and Data Structures for Flash Memories10.1145/1089733.1089735 ↗
6. A Survey of Flash Translation Layer10.1016/j.sysarc.2009.03.005 ↗
7. A Survey of Address Translation Technologies for Flash Memories10.1145/2512961 ↗
8. Ubiquitous B-Tree10.1145/356770.356776 ↗
9. Batory, D.S. (May, January 29). B+ Trees and Indexed Sequential Files: A Performance Comparison. Proceedings of the 1981 ACM SIGMOD International Conference on Management of Data (SIGMOD ‘81), Ann Arbor, MI, USA.10.1145/582318.582323 ↗
10. (2019, December 12). Reiserfs. Available online: http://reiser4.wiki.kernel.org/.
11. (2019, December 13). XFS. Available online: http://xfs.org/.
12. (2019, December 17). Btrfs. Available online: http://btrfs.wiki.kernel.org/.
13. (2019, October 27). Postgresql. Available online: http://www.postgresql.org/.
14. (2019, August 11). Mysql. Available online: http://www.mysql.com/.
15. (2019, August 11). Sqlite. Available online: http://www.sqlite.org/.
16. Ban, A. (1995). Flash File System. (No. 5,404,485), U.S. Patent.
17. Kim, G.Y., and Urgaonkar, B. (2008). DFTL: A Flash Translation Layer Employing Demand-Based Selective Caching of Page-Level Address Mappings, Department of Computer Science and Engineering, The Penn-sylvania State University.
18. Light Weight Sector Mapping Scheme for NAND-Based Block Devices10.1109/TCE.2010.5505983 ↗
19. Ma, D., Feng, J., and Li, G. (2011, January 12–16). LazyFTL: A Page-Level Flash Translation Layer Optimized for NAND Flash Memory. Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data, Athens, Greece.10.1145/1989323.1989325 ↗
20. Ban, A. (1999). Flash File System Optimized for Page-Mode Flash Technologies. (No. 5,937,425), U.S. Patent.
21. Shinohara, T. (1999). Flash Memory Card with Block Memory Address Arrangement. (No. 5,905,993), U.S. Patent.
22. Estakhri, P., Ganjuei, A.R., and Iman, B. (2000). Moving Sectors within a Block of Information in a Flash Memory Mass Storage Architecture. (No. 6,145,051), U.S. Patent.
23. Estakhri, P. (2003). Block Management for Mass Storage. (No. 6,567,307), U.S. Patent.
24. A Space-Efficient Flash Translation Layer for Compactflash Systems10.1109/TCE.2002.1010143 ↗
25. A Log Buffer-Based Flash Translation Layer Using Fully-Associative Sector Translation10.1145/1275986.1275990 ↗
26. HFTL: Hybrid Flash Translation Layer Based on Hot Data Identification for Flash Memory10.1109/TCE.2009.5373762 ↗
27. An Efficient B-Tree Layer Implementation for Flash-Memory Storage Systems10.1145/1275986.1275991 ↗
28. Flash-Optimized B+-Tree10.1007/s11390-010-9341-1 ↗
29. An Efficient Index Buffer Management Scheme for Implementing a B-Tree on NAND Flash Memory10.1016/j.datak.2010.03.004 ↗
30. As B-Tree: A Study of an Efficient B+-Tree for SSDs
31. A B-Tree Index Extension to Enhance Response Time and the Life Cycle of Flash Memory10.1016/j.ins.2009.05.007 ↗
32. Tree Indexing on Solid State Drives10.14778/1920841.1920990 ↗
33. An Adaptive Endurance-Aware B+-Tree for Flash Memory Storage Systems10.1109/TC.2013.158 ↗
34. Bityuckiy, A.B. (2019, October 27). JFFS3 Design Issues, Memory Technology Device (MTD) Subsystem for Linux. Available online: http://linux-mtd.infradead.org/tech/JFFS3design.pdf.
35. Kang, D., Jung, D., Kang, J.-U., and Kim, J.-S. (October, January 30). μ-Tree: An Ordered Index Structure for NAND Flash Memory. Proceedings of the 7th ACM & IEEE International Conference on Embedded Software (EMSOFT ‘07), Salzburg, Austria.
36. μ*-Tree: An Ordered Index Structure for NAND Flash Memory with Adaptive Page Layout Scheme10.1109/TC.2012.20 ↗
37. IPL B-Tree for Flash Memory Database Systems
38. Lee, S.-W., and Moon, B. (2007, January 12–14). Design of Flash-Based DBMS: An in-Page Logging Approach. Proceedings of the 2007 ACM SIGMOD International Conference on Management of Data, Beijing, China.10.1145/1247480.1247488 ↗
39. Dynamic In-Page Logging for B+-Tree Index10.1109/TKDE.2011.32 ↗
40. Lazy-Adaptive Tree: An Optimized Index Structure for Flash Devices10.14778/1687627.1687669 ↗
41. LSB-Tree: A Log-Structured B-Tree Index Structure for NAND Flash SSDs10.1007/s10617-014-9139-4 ↗
42. Block-Based Multi-Version B-Tree for Flash-Based Embedded Database Sys-tems10.1109/TC.2014.2308213 ↗
43. Roselli, D.S., Lorch, J.R., and Anderson, T.E. (2000, January 18–23). A Comparison of File System Workloads. Proceedings of the 2000 USENIX Annual Technical Conference, San Diego, CA, USA.
44. Leung, A.W., Pasupathy, S., Goodson, G.R., and Miller, E.L. (2008, January 22–27). Measurement and Analysis of Large-Scale Network File System Workloads. Proceedings of the USENIX Annual Technical Conference, Boston, MA, USA.
45. LSF: A New Buffer Replacement Scheme for Flash Memory-Based Portable Media Players10.1109/TCE.2013.6490251 ↗
46. Lee, S.-W., Moon, B., Park, C., Kim, J.-M., and Kim, S.-W. (2008, January 10–12). A Case for Flash Memory SSD in Enterprise Database Applications. Proceedings of the 2008 ACM SIG-MOD International Conference on Management of Data, Vancouver, BC, Canada.10.1145/1376616.1376723 ↗
47. (2019, October 27). The OPENSSD Project. Available online: http://www.openssd-project.org/.
48. SNIA (2019, October 27). Advancing Storage and Information Technology. Available online: http://www.snia.org/.