Yinan Li
Qiong Luo
Abstract
Large flash disks, or solid state drives (SSDs), have become an attractive alternative to magnetic hard disks, due to their high random read performance, low energy consumption and other features. However, writes, especially small random writes, on flash disks are inherently much slower than reads because of the erase-before-write mechanism.
To address this asymmetry of read-write speeds in tree indexing on the flash disk, we propose FD-tree, a tree index designed with the logarithmic method and fractional cascading techniques. With the logarithmic method, an FD-tree consists of the head tree -- a small B+-tree on the top, and a few levels of sorted runs of increasing sizes at the bottom. This design is write-optimized for the flash disk; in particular, an index search will potentially go through more levels or visit more nodes, but random writes are limited to a small area -- the head tree, and are subsequently transformed into sequential ones through merging into the lower runs. With the fractional cascading technique, we store pointers, called fences, in lower level runs to speed up the search. Given an FD-tree of n entries, we analytically show that it performs an update in O(logB n) sequential I/Os and completes a search in O(logB n) random I/Os, where B is the flash page size. We evaluate FD-tree in comparison with representative B+-tree variants under a variety of workloads on three commodity flash SSDs. Our results show that FD-tree has a similar search performance to the standard B+-tree, and a similar update performance to the write-optimized B+-tree variant. As a result, FD-tree dominates the other B+-tree index variants on the overall performance on flash disks as well as on magnetic disks.
- D. Agrawal, D. Ganesan, R. Sitaraman, Y. Diao, and S. Singh. Lazy-adaptive tree: An optimized index structure for flash devices. PVLDB, 2(1):361--372, 2009. Google Scholar
Digital Library
- L. Arge. The buffer tree: A new technique for optimal i/o-algorithms. In WADS, 1995. Google ScholarDigital Library
- J. L. Bentley. Decomposable searching problems. Inf. Process. Lett., 8(5), 1979.Google ScholarCross Ref
- L. Bouganim, B. T. Jónsson, and P. Bonnet. uflip: Understanding flash io patterns. In CIDR, 2009.Google Scholar
- B. Chazelle and L. J. Guibas. Fractional cascading: I. a data structuring technique. Algorithmica, 1(2), 1986.Google Scholar
- F. Chen, D. Koufaty, and X. Zhang. Understanding intrinsic characteristics and system implications of flash memory based solid state drives. In SIGMETRICS, 2009. Google ScholarDigital Library
- S. Chen. Flashlogging: Exploiting flash devices for synchronous logging performance. In SIGMOD Conference, 2009. Google ScholarDigital Library
- D. Comer. The ubiquitous b-tree. ACM Comput. Surv., 11(2), 1979. Google ScholarDigital Library
- E. Gal and S. Toledo. Algorithms and data structures for flash memories. ACM Comput. Surv., 37(2), 2005. Google ScholarDigital Library
- G. Graefe. Write-optimized b-trees. In VLDB, 2004. Google ScholarDigital Library
- G. Graefe. The five-minute rule 20 years later: and how flash memory changes the rules. ACM Queue, 6(4):40--52, 2008. Google ScholarDigital Library
- J. Gray and B. Fitzgerald. Flash disk opportunity for server applications. ACM Queue, 6(4):18--23, 2008. Google ScholarDigital Library
- J. M. Hellerstein, M. Stonebraker, and J. R. Hamilton. Architecture of a database system. Foundations and Trends in Databases, 1(2), 2007. Google ScholarDigital Library
- H. V. Jagadish, P. P. S. Narayan, S. Seshadri, S. Sudarshan, and R. Kanneganti. Incremental organization for data recording and warehousing. In VLDB, 1997. Google ScholarDigital Library
- C. Jermaine, A. Datta, and E. Omiecinski. A novel index supporting high volume data warehouse insertion. In VLDB, 1999. Google ScholarDigital Library
- K. Kimura and T. Kobayashi. Trends in high-density flash memory technologies. In IEEE Conference on Electron Devices and Solid-State Circuits, 2003.Google ScholarCross Ref
- S.-W. Lee and B. Moon. Design of flash-based dbms: an in-page logging approach. In SIGMOD Conference, 2007. Google ScholarDigital Library
- S.-W. Lee, B. Moon, C. Park, J.-M. Kim, and S.-W. Kim. A case for flash memory ssd in enterprise database applications. In SIGMOD Conference, 2008. Google ScholarDigital Library
- Y. Li, B. He, Q. Luo, and K. Yi. Tree indexing on flash disks. In ICDE, 2009. Google ScholarDigital Library
- C. Manning. Yaffs: the nand-specific flash file system. 2002.Google Scholar
- P. Muth, P. E. O'Neil, A. Pick, and G. Weikum. Design, implementation, and performance of the lham log-structured history data access method. In VLDB, 1998. Google ScholarDigital Library
- D. Myers. On the use of nand flash memory in high-performance relational databases. MIT Msc Thesis, 2008.Google Scholar
- S. Nath and A. Kansal. Flashdb: dynamic self-tuning database for nand flash. In IPSN, 2007. Google ScholarDigital Library
- P. E. O'Neil, E. Cheng, D. Gawlick, and E. J. O'Neil. The log-structured merge-tree (lsm-tree). Acta Inf., 33(4), 1996. Google ScholarDigital Library
- M. Rosenblum and J. K. Ousterhout. The design and implementation of a log-structured file system. ACM Trans. Comput. Syst., 10(1), 1992. Google ScholarDigital Library
- D. Tsirogiannis, S. Harizopoulos, M. A. Shah, J. L. Wiener, and G. Graefe. Query processing techniques for solid state drives. In SIGMOD Conference, 2009. Google ScholarDigital Library
- D. Woodhouse. Jffs: The journalling flash file system. In Ottawa Linux Symposium, 2001.Google Scholar
- C.-H. Wu, T.-W. Kuo, and L. P. Chang. An efficient b-tree layer implementation for flash-memory storage systems. In RTCSA, 2003.Google Scholar
Index Terms
- Tree indexing on solid state drives
Recommendations
Read/write-optimized tree indexing for solid-state drives
Flash-memory-based solid-state drives (SSDs) are used widely for secondary storage. To be effective for SSDs, traditional indices have to be redesigned to cope with the special properties of flash memory, such as asymmetric read/write latencies (fast ...
High performance & low latency in solid-state drives through redundancy
INFLOW '13: Proceedings of the 1st Workshop on Interactions of NVM/FLASH with Operating Systems and WorkloadsSolid-state drives are becoming increasingly popular in enterprise storage systems, playing the role of large caches and permanent storage. Although SSDs provide faster random access than hard-drives, their performance under read/write workloads is ...
Comments