Design of flash-based DBMS: an in-page logging approach

ABSTRACT

The popularity of high-density flash memory as data storage media has increased steadily for a wide spectrum of computing devices such as PDA's, MP3 players, mobile phones and digital cameras. More recently, computer manufacturers started launching new lines of mobile or portable computers that did away with magnetic disk drives altogether, replacing them with tens of gigabytes of NAND flash memory. Like EEPROM and magnetic disk drives, flash memory is non-volatile and retains its contents even when the power is turned off. As its capacity increases and price drops, flash memory will compete more successfully with lower-end, lower-capacity disk drives. It is thus not inconceivable to consider running a full database system on the flash-only computing platforms or running an embedded database system on the lightweight computing devices. In this paper, we present a new design called in-page logging (IPL) for flash memory based database servers. This new design overcomes the limitations of flash memory such as high write latency, and exploits unique characteristics of flash memory to achieve the best attainable performance for flash-based database servers. We show empirically that the IPL approach can yield considerable performance benefit over traditional design for disk-based database servers. We also show that the basic design of IPL can be elegantly extended to support transactional database recovery.

REFERENCES

• 1: Brad Adelberg , Ben Kao , Hector Garcia-Molina, Database Support for Efficiently Maintaining Derived Data, Proceedings of the 5th International Conference on Extending Database Technology: Advances in Database Technology, p.223-240, March 25-29, 1996
• 2: Andrew Birrel, Michael Isard, Chuck Thacker, and Ted Wobber. A Design for High-Performance Flash Disks. Technical Report MSR-TR-2005-176, Microsoft Research, December 2005.
• 3: Christophe Bobineau , Luc Bouganim , Philippe Pucheral , Patrick Valduriez, PicoDMBS: Scaling Down Database Techniques for the Smartcard, Proceedings of the 26th International Conference on Very Large Data Bases, p.11-20, September 10-14, 2000
• 4: R. Bonilla-Lucas , P. Plachta , A. Sachedina , D. Jimenez-Gonzalez , C. Zuzarte , J.-L. Larriba-Pey, Characterization of the data access behavior for TPC-C traces, Proceedings of the 2004 IEEE International Symposium on Performance Analysis of Systems and Software, p.115-122, March 10-12, 2004
• 5: Hui Dai , Michael Neufeld , Richard Han, ELF: an efficient log-structured flash file system for micro sensor nodes, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031516]
• 6: Fred Douglis, Ramon Caceres, Frans Kaashoek, Kai Li, Brian Marsh, and Joshua A. Tauber. Storage Alternatives for Mobile Computers. In Proceedings of the USENIX 1st Symposium on Operating Systems Design and Implementation (OSDI--94), Monterey, CA, USA, November 1994.
• 7: Julian Dyke and Steve Shaw. Pro Oracle Database 10g RAC on Linux: Installation, Administration, and Performance. Apress, 2006.
• 8: Eran Gal , Sivan Toledo, Algorithms and data structures for flash memories, ACM Computing Surveys (CSUR), v.37 n.2, p.138-163, June 2005 [doi>10.1145/1089733.1089735]
• 9: Goetz Graefe. Write-Optimized B-Trees. In Proceedings of the 30th VLDB Conference, pages 672--683, Toronto, Canada, September 2004.
• 10: Jim Gray and Andreas Reuter. Transaction Processing: Concepts and Techniques. Morgan Kaufmann, 1993.
• 11: MTRON Media Experts Group. MSD-P Series Production Specification. Technical Report Version 0.7 sv, MTRON Co. Ltd., October 2006.
• 12: Mark Hachman.New Samsung Notebook Replaces Hard Drive With Flash. http://www.extremetech. com, May 2006.
• 13: Theo Haerder , Andreas Reuter, Principles of transaction-oriented database recovery, ACM Computing Surveys (CSUR), v.15 n.4, p.287-317, December 1983 [doi>10.1145/289.291]
• 14: Windsor W. Hsu , Alan Jay Smith , Honesty C. Young, I/O reference behavior of production database workloads and the TPC benchmarks—an analysis at the logical level, ACM Transactions on Database Systems (TODS), v.26 n.1, p.96-143, March 2001 [doi>10.1145/383734.383737]
• 15: Atsushi Inoue and Doug Wong. NAND Flash Applications Design Guide. Technical Report Revision 2.0, Toshiba America Electronic Components, Inc., March 2004.
• 16: Intel. Understanding the Flash Translation Layer (FTL) Specification. Application Note AP-684, Intel Corporation, December 1998.
• 17: Gye-Jeong Kim , Seung-Cheon Baek , Hyun-Sook Lee , Han-Deok Lee , Moon Jeung Joe, LGeDBMS: a small DBMS for embedded system with flash memory, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 18: Jesung Kim, Jong Min Kim, Sam H. Noh, Sang Lyul Min, and Yookun Cho. A Space-Efficient Flash Translation Layer for CompactFlash Systems. IEEE Transactions on Consumer Electronics, 48(2):366--375, May 2002.
• 19: Katsutaka Kimura and Takashi Kobayashi. Trends in High-Density Flash Memory Technologies. In IEEE Conference on Electron Devices and Solid-State Circuits, pages 45--50, Hong Kong, December 2003.
• 20: C. Mohan , Don Haderle , Bruce Lindsay , Hamid Pirahesh , Peter Schwarz, ARIES: a transaction recovery method supporting fine-granularity locking and partial rollbacks using write-ahead logging, ACM Transactions on Database Systems (TODS), v.17 n.1, p.94-162, March 1992 [doi>10.1145/128765.128770]
• 21: Linda Dailey Paulson, Technology News: Will Hard Drives Finally Stop Shrinking?, Computer, v.38 n.5, p.14-16, May 2005 [doi>10.1109/MC.2005.172]
• 22: Mendel Rosenblum.The Design and Implementation of a Log--Structured File System.PhD thesis, UC Berkeley, 1991.
• 23: Mendel Rosenblum , John K. Ousterhout, The design and implementation of a log-structured file system, Proceedings of the thirteenth ACM symposium on Operating systems principles, p.1-15, October 13-16, 1991, Pacific Grove, California, United States
• 24: Rajkumar Sen and Krithi Ramamritham. Efficient Data Management on Lightweight Computing Devices. In Proceedings of the 21st Inter. Conference on Data Engineering, Tokyo, Japan, April 2005.
• 25: Michael Stonebraker, The Design of the POSTGRES Storage System, Proceedings of the 13th International Conference on Very Large Data Bases, p.289-300, September 01-04, 1987
• 26: Michael Stonebraker , Greg Kemnitz, The POSTGRES next generation database management system, Communications of the ACM, v.34 n.10, p.78-92, Oct. 1991 [doi>10.1145/125223.125262]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.2 Physical Design

General Terms:
Algorithms, Design, Performance, Reliability

Keywords:
flash-memory database server, in-page logging