Thomas Kissinger
Wolfgang Lehner
Abstract
Growing memory capacities and the increasing number of cores on modern hardware enforces the design of new in-memory indexing structures that reduce the number of memory transfers and minimizes the need for locking to allow massive parallel access. However, most applications depend on hard durability constraints requiring a persistent medium like SSDs, which shorten the latency and throughput gap between main memory and hard disks. In this paper, we present our winning solution of the SIGMOD Programming Contest 2011. It consists of an in-memory indexing structure that provides a balanced read/write performance as well as non-blocking reads and single-lock writes. Complementary to this index, we describe an SSD-optimized logging approach to fit hard durability requirements at a high throughput rate.
- SIGMOD Programming Contest 2011. http://db.csail.mit.edu/sigmod11contest/.Google Scholar
- R. Bayer and E. McCreight. Organization and Maintenance of Large Ordered Indexes, pages 245--262. Software pioneers, New York, NY, USA, 2002. Google ScholarDigital Library
- M. Böhm, B. Schlegel, P. B. Volk, U. Fischer, D. Habich, and W. Lehner. Efficient In-Memory Indexing with Generalized Prefix Trees. In BTW, pages 227--246, 2011.Google Scholar
- L. Bouganim, B. T. Jónsson, and P. Bonnet. uFLIP: Understanding Flash IO Patterns. In CIDR, 2009.Google Scholar
- S. Chen. FlashLogging: Exploiting Flash Devices for Synchronous Logging Performance. In SIGMOD, pages 73--86, 2009. Google ScholarDigital Library
- B. K. Debnath, S. Sengupta, and J. Li. FlashStore: High Throughput Persistent Key-Value Store. PVLDB, 3(2):1414--1425, 2010. Google ScholarDigital Library
- B. K. Debnath, S. Sengupta, and J. Li. SkimpyStash: RAM Space Skimpy Key-Value Store on Flash-based Storage. In SIGMOD, pages 25--36, 2011. Google ScholarDigital Library
- P. L. Lehman and s. B. Yao. Efficient Locking for Concurrent Operations on B-Trees. ACM Trans. Database Syst., 6:650--670, December 1981. Google ScholarDigital Library
- P. E. McKenney and J. D. Slingwine. Read-Copy Update: Using Execution History to Solve Concurrency Problems.Google Scholar
- J. Rao and K. A. Ross. Making B+-Trees Cache Conscious in Main Memory. SIGMOD Rec., 29:475--486, May 2000. Google ScholarDigital Library
Index Terms
- A high-throughput in-memory index, durable on flash-based SSD: insights into the winning solution of the SIGMOD programming contest 2011
Recommendations
Flash-Aware RAID Techniques for Dependable and High-Performance Flash Memory SSD
Solid-state disks (SSDs), which are composed of multiple NAND flash chips, are replacing hard disk drives (HDDs) in the mass storage market. The performances of SSDs are increasing due to the exploitation of parallel I/O architectures. However, ...
A hybrid SSD with PRAM and NAND Flash memory
The speed of computing processor has been improved dramatically with multi-core architecture. However, the overall computer system performance shows slow improvement because of the sluggish speed of storage system. Several researches have been done to ...
Constructing Large, Durable and Fast SSD System via Reprogramming 3D TLC Flash Memory
MICRO '52: Proceedings of the 52nd Annual IEEE/ACM International Symposium on MicroarchitectureNAND flash memory based SSDs have been widely studied and adopted. The scaling of SSD has evolved from plannar (2D) to 3D stacking. Compared with 2D SSD, 3D SSD stacks more layers into one block, constructing one block with more flash pages. For ...
Comments