Hongchan Roh
Sang-Won Lee
Abstract
Previous research addressed the potential problems of the hard-disk oriented design of DBMSs of flashSSDs. In this paper, we focus on exploiting potential benefits of flashSSDs. First, we examine the internal parallelism issues of flashSSDs by conducting benchmarks to various flashSSDs. Then, we suggest algorithm-design principles in order to best benefit from the internal parallelism. We present a new I/O request concept, called psync I/O that can exploit the internal parallelism of flashSSDs in a single process. Based on these ideas, we introduce B+-tree optimization methods in order to utilize internal parallelism. By integrating the results of these methods, we present a B+-tree variant, PIO B-tree. We confirmed that each optimization method substantially enhances the index performance. Consequently, PIO B-tree enhanced B+-tree's insert performance by a factor of up to 16.3, while improving point-search performance by a factor of 1.2. The range search of PIO B-tree was up to 5 times faster than that of the B+-tree. Moreover, PIO B-tree outperformed other flash-aware indexes in various synthetic workloads. We also confirmed that PIO B-tree outperforms B+-tree in index traces collected inside the Postgresql DBMS with TPC-C benchmark.
- N. Agrawal, V. Prabhakaran, T. Wobber, J. D. Davis, M. S. Manasse, and R. Panigrahy. Design tradeoffs for SSD performance. In USENIX, pages 57--70, 2008. Google Scholar
Digital Library
- F. Chen, D. A. Koufaty, and X. Zhang. Understanding intrinsic characteristics and system implications of flash memory based solid state drives. In SIGMETRICS, pages 181--192, 2009. Google ScholarDigital Library
- F. Chen, R. Lee, and X. Zhang. Essential roles of exploiting internal parallelism of flash memory based solid state drives in high-speed data processing. In HPCA, pages 266--277, 2011. Google ScholarDigital Library
- Corsair. F120. http://www.corsair.com/solid-statedrives/force-series/cssd-F120gb2-brkt.html.Google Scholar
- Fusion-io. Iodrive. http://community.fusionio.com/media/p/853.aspx.Google Scholar
- 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
- R. A. Hankins, T. A. Diep, M. Annavaram, B. Hirano, H. Eri, H. Nueckel and J. P. Shen. Scaling and characterizing database workloads: bridging the gap between research and practice. In MICRO, pages 151--164, 2003. Google ScholarDigital Library
- Y. Hu, H. Jiang, D. Feng, L. Tian, H. Luo and S. P. Zhang. Performance impact and interplay of SSD parallelism through advanced commands, allocation strategy and data granularity. In ICS, pages 96--107, 2011. Google ScholarDigital Library
- Intel. intel x25-e. http://download.intel.com/design/ash/nand/extreme/319984.pdf.Google Scholar
- Intel. intel x25-m. http://download.intel.com/design/ash/nand/mainstream/Specification322296.pdf.Google Scholar
- J. H. Kim, D. Jung, J. S. Kim and J. Huh. A methodology for extracting performance parameters in solid state disks (SSDs). In MASCOTS, pages 1--10, 2009.Google Scholar
- Y.-R. Kim, K.-Y. Whang, and I.-Y. Song. Page-differential logging: an efficient and DBMS-independent approach for storing data into flash memory. In SIGMOD, pages 363--374, 2010. Google ScholarDigital Library
- S.-W. Lee and B. Moon. Design of flash-based DBMS: an in-page logging approach. In SIGMOD, pages 55--66, 2007. Google ScholarDigital Library
- S.-W. Lee, B. Moon, and C. Park. Advances in flash memory SSD technology for enterprise database applications. In SIGMOD, pages 863--870, 2009. Google ScholarDigital Library
- P. L. Lehman, S. B. Yao. Efficient locking for concurrent operations on b-trees. ACM TODS, 6(4):650--670, 1981. Google ScholarDigital Library
- Y. Li, B. He, J. Yang, Q. Luo, and K. Yi. Tree indexing on solid state drives. PVLDB, 3(1):1195--1206, 2010. Google ScholarDigital Library
- Micron. RealSSD P300. http://www.micron.com/getdocument/?documentId=5557.Google Scholar
- C. Mohan, D. J. Haderle, B. G. Lindsay, H. Pirahesh and P. M. Schwarz. ARIES: a transaction recovery method supporting fine-granularity locking and partial rollbacks using write-ahead logging. ACM TODS, 17(1):94--162, 1992. Google ScholarDigital Library
- G.-J. Na, S.-W. Lee, and B. Moon. Dynamic in-page logging for flash-aware b-tree index. In CIKM, pages 1485--1488, 2009. Google ScholarDigital Library
- Ocz. Vertex2. http://www.ocztechnology.com/res/manuals/OCZ_Agility2_Product_sheet_3.pdf.Google Scholar
- S. Y. Park, E. Seo, J. Y. Shin, S. Maeng and J. Lee. Exploiting internal parallelism of flash-based SSDs. Computer Architecture Letters, 9(1):9--12, 2010. Google ScholarDigital Library
- Transaction Processing Performance Council. TPC benchmark C, standard specification version 5.Google Scholar
- C.-H. Wu, T.-W. Kuo, and L.-P. Chang. An efficient b-tree layer implementation for flash-memory storage systems. ACM Trans. Embedded Comput. Syst., 6(3), 2007. Google ScholarDigital Library
Index Terms
- B+-tree index optimization by exploiting internal parallelism of flash-based solid state drives
Recommendations
Porting disk-based spatial index structures to flash-based solid state drives
AbstractIndexing data on flash-based Solid State Drives (SSDs) is an important paradigm recently applied in spatial data management. During last years, the design of new spatial access methods for SSDs, named flash-aware spatial indices, has attracted the ...
Efficient processing of XML path queries using the disk-based F&B Index
VLDB '05: Proceedings of the 31st international conference on Very large data basesWith the proliferation of XML data and applications on the Internet, efficient XML query processing techniques are in great demand. Answering queries using XML indexes is a natural approach. A number of XML indexes have been proposed in the literature: ...
T-Tree or B-Tree: Main Memory Database Index Structure Revisited
ADC '00: Proceedings of the Australasian Database ConferenceWhile the B-tree (or the B+-tree) is the most popular index structure in disk-based relational database systems, the T-tree has been widely accepted as a promising index structure for main memory databases where the entire database (or most of them) ...
Comments