FlashDB: dynamic self-tuning database for NAND flash

ABSTRACT

FlashDB is a self-tuning database optimized for sensor networks using NAND flash storage. In practical systems flash is used in different packages such as on-board flash chips, compact flash cards, secure digital cards and related formats. Our experiments reveal non-trivial differences in their access costs. Furthermore, databases may be subject to different types of workloads. We show that existing databases for flash are not optimized for all types of flash devices or for all workloads and their performance is thus suboptimal in many practical systems. FlashDB uses a novel self-tuning index that dynamically adapts its storage structure to workload and underlying storage device. We formalize the self-tuning nature of an index as a two-state task system and propose a 3-competitive online algorithm that achieves the theoretical optimum. We also provide a framework to determine the optimal size of an index node that minimizes energy and latency for a given device. Finally, we propose optimizations to further improve the performance of our index. We prototype and compare different indexing schemes on multiple flash devices and workloads, and show that our indexing scheme outperforms existing schemes under all workloads and flash devices we consider.

REFERENCES

• 1: AZAR, Y., FEIGE, U., AND NATH, S. On the work function algorithm for two state task systems. Tech. Rep. MSR-TR-2007-20, Microsoft Corporation, February 2007.
• 2: BLACK, D. L., AND SLEATOR, D. D. Competitive algorithms for replication and migration problems. Tech. Rep. CMU-CS-89-201, Carnegie Mellon University, 1989.
• 3: A. Borodin , N. Linial , M. Saks, An optimal online algorithm for metrical task systems, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.373-382, January 1987, New York, New York, United States [doi>10.1145/28395.28435]
• 4: BURKE, J., ESTRIN, D., HANSEN, M., PARKER, A., RAMANATHAN, N., REDDY, S., AND SRIVASTAVA, M. B. Participatory sensing. In ACM Sensys Workshop on World-Sensor-Web (2006).
• 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: Peter Desnoyers , Deepak Ganesan , Prashant Shenoy, TSAR: a two tier sensor storage architecture using interval skip graphs, Proceedings of the 3rd international conference on Embedded networked sensor systems, November 02-04, 2005, San Diego, California, USA [doi>10.1145/1098918.1098923]
• 7: DIAO, Y., GANESAN, D., MATHUR, G., AND SHENOY, P. Re-thinking data management for storage-centric sensor networks. In Third Biennial Conference on Innovative Data Systems Research (CIDR), Asilomar (January 2007).
• 8: Lewis Girod , Martin Lukac , Vlad Trifa , Deborah Estrin, The design and implementation of a self-calibrating distributed acoustic sensing platform, Proceedings of the 4th international conference on Embedded networked sensor systems, October 31-November 03, 2006, Boulder, Colorado, USA [doi>10.1145/1182807.1182815]
• 9: Jim Gray , Goetz Graefe, The five-minute rule ten years later, and other computer storage rules of thumb, ACM SIGMOD Record, v.26 n.4, p.63-68, Dec. 1997 [doi>10.1145/271074.271094]
• 10: Bret Hull , Vladimir Bychkovsky , Yang Zhang , Kevin Chen , Michel Goraczko , Allen Miu , Eugene Shih , Hari Balakrishnan , Samuel Madden, CarTel: a distributed mobile sensor computing system, Proceedings of the 4th international conference on Embedded networked sensor systems, October 31-November 03, 2006, Boulder, Colorado, USA [doi>10.1145/1182807.1182821]
• 11: INTEL. Intel mote 2. http://www.intel.com/research/downloads/imote overview.pdf.
• 12: KANSAL, A., XIAO, L., AND ZHAO, F. Relevance metrics for coverage extension using community collected cell-phone camera imagery. In ACM Sensys Workshop on World-Sensor-Web: Mobile Device Centric Sensor Networks and Applications (October 2006), pp. 12--16.
• 13: Dimitrios Lymberopoulos , Andreas Savvides, XYZ: a motion-enabled, power aware sensor node platform for distributed sensor network applications, Proceedings of the 4th international symposium on Information processing in sensor networks, April 24-27, 2005, Los Angeles, California
• 14: Gaurav Mathur , Peter Desnoyers , Deepak Ganesan , Prashant Shenoy, Capsule: an energy-optimized object storage system for memory-constrained sensor devices, Proceedings of the 4th international conference on Embedded networked sensor systems, October 31-November 03, 2006, Boulder, Colorado, USA [doi>10.1145/1182807.1182827]
• 15: MICROSOFT. "sql server 2005 everywhere edition". http://www.microsoft.com/sql/ctp sqlserver2005everywhereedition.mspx.
• 16: NATH, S., AND KANSAL, A. Flashdb: Dynamic self-tuning database for nand flash. Tech. Rep. MSR-TR-2006-168, Microsoft Corporation, 2006.
• 17: Richard Pon , Maxim A. Batalin , Jason Gordon , Aman Kansal , Duo Liu , Mohammad Rahimi , Lisa Shirachi , Yan Yu , Mark Hansen , William J. Kaiser , Mani Srivastava , Gaurav Sukhatme , Deborah Estrin, Networked infomechanical systems: a mobile embedded networked sensor platform, Proceedings of the 4th international symposium on Information processing in sensor networks, April 24-27, 2005, Los Angeles, California
• 18: Mendel Rosenblum , John K. Ousterhout, The design and implementation of a log-structured file system, ACM Transactions on Computer Systems (TOCS), v.10 n.1, p.26-52, Feb. 1992 [doi>10.1145/146941.146943]
• 19: SAMSUNG. Samsung K9K1G08R0B 128M x 8 bit NAND Flash Memeory.
• 20: Abraham Silberschatz , Henry F. Korth , S. Sudarshan , Allen B. Tucker, Database Systems Concepts, McGraw-Hill, Inc., New York, NY, 1997
• 21: WU, C.-H., CHANG, L.-P., AND KUO, T.-W. An efficient b-tree layer for flash-memory storage systems. In RTCSA (2003).
• 22: Demetrios Zeinalipour-Yazti , Song Lin , Vana Kalogeraki , Dimitrios Gunopulos , Walid A. Najjar, Microhash: an efficient index structure for fash-based sensor devices, Proceedings of the 4th conference on USENIX Conference on File and Storage Technologies, p.3-3, December 13-16, 2005, San Francisco, CA
• 23: Pei Zhang , Christopher M. Sadler , Stephen A. Lyon , Margaret Martonosi, Hardware design experiences in ZebraNet, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031522]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Indexing methods

General Terms:
Algorithms, Design, Measurement, Performance

Keywords:
B⁺-tree, NAND flash, indexing, log-structured index, self-tuning index