Devesh Agrawal
Abstract
Flash memories are in ubiquitous use for storage on sensor nodes, mobile devices, and enterprise servers. However, they present significant challenges in designing tree indexes due to their fundamentally different read and write characteristics in comparison to magnetic disks.
In this paper, we present the Lazy-Adaptive Tree (LA-Tree), a novel index structure that is designed to improve performance by minimizing accesses to flash. The LA-tree has three key features: 1) it amortizes the cost of node reads and writes by performing update operations in a lazy manner using cascaded buffers, 2) it dynamically adapts buffer sizes to workload using an online algorithm, which we prove to be optimal under the cost model for raw NAND flashes, and 3) it optimizes index parameters, memory management, and storage reclamation to address flash constraints. Our performance results on raw NAND flashes show that the LA-Tree achieves 2x to 12x gains over the best of alternate schemes across a range of workloads and memory constraints. Initial results on SSDs are also promising, with 3x to 6x gains in most cases.
- L. Arge. The buffer tree: A Technique for Designing Batched External Data Structures. In Algorithmica 37(1):1--24, 2003.Google Scholar
- L. Arge, K. Hinrichs et al. Efficient bulk operations on dynamic R-trees. In Algorithmica 33(1):104--128, 2002.Google ScholarDigital Library
- A. Birrell, M. Isard et al. A Design for High Performance Flash Disks. In SIGOPS Operating system review, 41(2), 2007. Google ScholarDigital Library
- N. Agrawal, V. Prabhakaran et al. Design Tradeoffs for SSD Performance. In USENIX 2008. Google ScholarDigital Library
- Y. Diao, D. Ganesan et al. Rethinking data management for storage-centric sensor networks. In CIDR 2007.Google Scholar
- MSP-SATA7525. http://mtron.net/Upload_Data/Spec/ASIC/PRO/SATA/MSP-SATA7525_rev0.4.pdfGoogle Scholar
- J. Gray, and B. Fitzgerald. Flash Disk Opportunity for Server Applications. In ACM Queue 2008 4(6). Google ScholarDigital Library
- Enea polyhedra flashlite. http://www.enea.com.Google Scholar
- G. Mathur, P. Desnoyers et al. Ultra-Low Power Data Storage for Sensor Networks. In IPSN-SPOTS, 2006. Google ScholarDigital Library
- G. Graefe. The Five-minute Rule Twenty Years Later, and How Flash Memory Changes the Rules. In DAMON 2007. Google ScholarDigital Library
- J. M. Hellerstein, J. F. Naughton et al. Generalized Search Trees for Database Systems. In VLDB, 1995. Google ScholarDigital Library
- S. Huddleston and K. Mehlhorn. A new data structure for representing sorted lists. Acta Informatica, 17, 1982.Google Scholar
- H-Store: A Next Generation OLTP DBMS. http://db.cs.yale.edu/hstore/.Google Scholar
- J.-U. Kang, H. Jo et al. A superblock-based flash translation layer for nand flash memory. In EMSOFT 2006. Google ScholarDigital Library
- D. Kang, D. Jung et al. μ-tree: an ordered index structure for NAND flash memory. In EMSOFT 2007. Google ScholarDigital Library
- A. Borodin and E. Y. Ran. Online computation and competitive analysis. Published by Cambridge University Press, 1998 Google ScholarDigital Library
- I. Koltsidas, S. D. Viglas. Flashing Up the Storage Layer. In VLDB 2008. Google ScholarDigital Library
- S. Lee and B. Moon. Design of flash-based DBMS: an in-page logging approach. In SIGMOD 2007. Google ScholarDigital Library
- S. Lee, B. Moon et al. A Case for Flash Memory SSD in Enterprise Database Applications. In SIGMOD 2008. Google ScholarDigital Library
- Y. Li, B. He et al. Tree Indexing on Flash Disks. In ICDE 2009. Google ScholarDigital Library
- S. Nath and A. Kansal. FlashDB: dynamic self-tuning database for NAND flash. In IPSN 2007. Google ScholarDigital Library
- Toshiba TC58DVG02A1FT00 NAND flash chip datasheet. http://toshiba.com/taec, 2003.Google Scholar
- C. Wu, T. Wei, and L. P. Chang. An efficient B-tree layer implementation for flash-memory storage systems. Trans. on Embedded Computing Systems, 6(3), 2007. Google ScholarDigital Library
- J. Zhou and K. A. Ross. Buffering accesses to memory-resident index structures. In VLDB 2003. Google ScholarDigital Library
- D. Agrawal, S. Singh, D. Ganesan, R. Sitaraman, and Y. Diao. Flash-Optimized Index Structures for Embedded Systems. TR 2008-08, UMass Amherst CS Dept, 2008.Google Scholar
Index Terms
- Lazy-Adaptive Tree: an optimized index structure for flash devices
Recommendations
Lazy-split B+-tree: a novel B+-tree index scheme for flash-based database systems
Flash memory is rapidly being deployed as a data storage medium for embedded systems and tablet computers due to its shock resistance, fast access, and low power consumption, etc. However, it has some intractable characteristics, such as erase-before-...
Improving Flash-Based Disk Cache with Lazy Adaptive Replacement
For years, the increasing popularity of flash memory has been changing storage systems. Flash-based solid-state drives (SSDs) are widely used as a new cache tier on top of hard disk drives (HDDs) to speed up data-intensive applications. However, the ...
Lazy-RTGC: A Real-Time Lazy Garbage Collection Mechanism with Jointly Optimizing Average and Worst Performance for NAND Flash Memory Storage Systems
Due to many attractive and unique properties, NAND flash memory has been widely adopted in mission-critical hard real-time systems and some soft real-time systems. However, the nondeterministic garbage collection operation in NAND flash memory makes it ...
Comments