A sequential indexing scheme for flash-based embedded systems

ABSTRACT

NAND Flash has become the most popular stable storage medium for embedded systems. As on-board storage capacity increases, the need for efficient indexing techniques arises. Such techniques are very challenging to design due to a combination of NAND Flash constraints (for example the block-erase-before-page-rewrite constraint and limited number of erase cycles) and embedded system constraints (for example tiny RAM and resource consumption predictability). Previous work adapted traditional indexing methods to cope with Flash constraints by deferring index updates using a log and batching them to decrease the number of rewrite operations in Flash memory. However, these methods were not designed with embedded system constraints in mind and do not address them. In this paper, we propose a new alternative for indexing Flash-resident data that specifically addresses the embedded context. This approach, called PBFilter, organizes the index structure in a purely sequential way. Key lookups are sped up thanks to two principles called Summarization and Partitioning. We instantiate these principles with data structures and algorithms based on Bloom Filters and show the effectiveness of this approach through a comprehensive performance study.

REFERENCES

• 1: Nicolas Anciaux , Mehdi Benzine , Luc Bouganim , Kévin Jacquemin , Philippe Pucheral , Shaoyi Yin, Restoring the Patient Control over Her Medical History, Proceedings of the 2008 21st IEEE International Symposium on Computer-Based Medical Systems, p.132-137, June 17-19, 2008 [doi>10.1109/CBMS.2008.101]
• 2: Nicolas Anciaux , Luc Bouganim , Philippe Pucheral , Patrick Valduriez, DiSC: Benchmarking Secure Chip DBMS, IEEE Transactions on Knowledge and Data Engineering, v.20 n.10, p.1363-1377, October 2008 [doi>10.1109/TKDE.2008.67]
• 3: Andrew Birrell , Michael Isard , Chuck Thacker , Ted Wobber, A design for high-performance flash disks, ACM SIGOPS Operating Systems Review, v.41 n.2, p.88-93, April 2007 [doi>10.1145/1243418.1243429]
• 4: Bityutskiy, A-B., JFFS3 Design Issues. Tech. report, Nov. 2005.
• 5: Burton H. Bloom, Space/time trade-offs in hash coding with allowable errors, Communications of the ACM, v.13 n.7, p.422-426, July 1970 [doi>10.1145/362686.362692]
• 6: Dekart SRL.: Dekart Smart Container, 2007. http://www.dekart.com/products/integrated/smart container
• 7: Dillinger, P. C., and Manolios, P. Fast and Accurate Bitstate Verification for SPIN. 11th Int. Spin Workshop on Model Checking Software, LNCS 2989, 2004.
• 8: G. H. Gonnet , R. Baeza-Yates, Handbook of algorithms and data structures: in Pascal and C (2nd ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1991
• 9: Hamid L. New directions for removable USB mass storage, Press release, 2006. http://www.itwales.com/997893.htm
• 10: Intel Corporation, Understanding the Flash Translation Layer (FTL) specification. 1998.
• 11: 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
• 12: Adam Kirsch , Michael Mitzenmacher, Less hashing, same performance: building a better bloom filter, Proceedings of the 14th conference on Annual European Symposium, p.456-467, September 11-13, 2006, Zurich, Switzerland [doi>10.1007/11841036_42]
• 13: Sang-Won Lee , Bongki Moon, Design of flash-based DBMS: an in-page logging approach, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247488]
• 14: Ajay Mani , Manjunath Rajashekhar , Philip Levis, TINX: a tiny index design for flash memory on wireless 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.1182888]
• 15: Michael Mitzenmacher, Compressed bloom filters, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.144-150, August 2001, Newport, Rhode Island, United States [doi>10.1145/383962.384004]
• 16: Suman Nath , Aman Kansal, FlashDB: dynamic self-tuning database for NAND flash, Proceedings of the 6th international conference on Information processing in sensor networks, April 25-27, 2007, Cambridge, Massachusetts, USA [doi>10.1145/1236360.1236412]
• 17: 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]
• 18: Wu, C., Chang, L., and Kuo, T. An Efficient B-Tree Layer for Flash-Memory Storage Systems. Int. Conf. on Real-Time and Embedded Computing Systems and Applications (RTCSA), 2003.
• 19: Yao, A. On Random 2--3 Trees. Acta Informatica, 9 (1978).
• 20: S. B. Yao, Approximating block accesses in database organizations, Communications of the ACM, v.20 n.4, p.260-261, April 1977 [doi>10.1145/359461.359475]
• 21: Yin, S., Pucheral, P., Meng X. PBFilter: Indexing Flash-Resident Data through Partitioned Summaries. Tech. Rep. RR-6548. INRIA. 2008.
• 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