Online maintenance of very large random samples on flash storage

ABSTRACT

Recent advances in flash media have made it an attractive alternative for data storage in a wide spectrum of computing devices, such as embedded sensors, mobile phones, PDA's, laptops, and even servers. However, flash media has many unique characteristics that make existing data management/analytics algorithms designed for magnetic disks perform poorly with flash storage. For example, while random (page) reads are as fast as sequential reads, random (page) writes and in-place data updates are orders of magnitude slower than sequential writes. In this paper, we consider an important fundamental problem that would seem to be particularly challenging for flash storage: efficiently maintaining a very large (100 MBs or more) random sample of a data stream (e.g., of sensor readings). First, we show that previous algorithms such as reservoir sampling and geometric file are not readily adapted to flash. Second, we propose B-FILE, an energy-efficient abstraction for flash media to store self-expiring items, and show how a B-FILE can be used to efficiently maintain a large sample in flash. Our solution is simple, has a small (RAM) memory footprint, and is designed to cope with flash constraints in order to reduce latency and energy consumption. Third, we provide techniques to maintain biased samples with a B-FILE and to query the large sample stored in a B-FILE for a subsample of an arbitrary size. Finally, we present an evaluation with flash media that shows our techniques are several orders of magnitude faster and more energy-efficient than (flash-friendly versions of) reservoir sampling and geometric file. A key finding of our study, of potential use to many flash algorithms beyond sampling, is that "semi-random" writes (as defined in the paper) on flash cards are over two orders of magnitude faster and more energy-efficient than random writes.

REFERENCES

• 1: Nitin Agrawal , Vijayan Prabhakaran , Ted Wobber , John D. Davis , Mark Manasse , Rina Panigrahy, Design tradeoffs for SSD performance, USENIX 2008 Annual Technical Conference on Annual Technical Conference, p.57-70, June 22-27, 2008, Boston, Massachusetts
• 2: Brian Babcock , Surajit Chaudhuri , Gautam Das, Dynamic sample selection for approximate query processing, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872822]
• 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: Surajit Chaudhuri , Gautam Das , Mayur Datar , Rajeev Motwani , Vivek R. Narasayya, Overcoming Limitations of Sampling for Aggregation Queries, Proceedings of the 17th International Conference on Data Engineering, p.534-542, April 02-06, 2001
• 5: Y. Diao, D. Ganesan, G. Mathur, and P. Shenoy. Rethinking data management for storage-centric sensor networks. In CIDR, 2007.
• 6: Fred Douglis , Ramón Cáceres , Frans Kaashoek , Kai Li , Brian Marsh , Joshua A. Tauber, Storage alternatives for mobile computers, Proceedings of the 1st USENIX conference on Operating Systems Design and Implementation, p.3-es, November 14-17, 1994, Monterey, California
• 7: Phillip B. Gibbons , Srikanta Tirthapura, Estimating simple functions on the union of data streams, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.281-291, July 2001, Crete Island, Greece [doi>10.1145/378580.378687]
• 8: M. Hachman. New Samsung notebook replaces hard drive with flash. http://www.extremetech.com/article2/0,1558,1966644,00.asp, May 2006.
• 9: Intel-Corporation. Understanding the Flash Translation Layer (FTL) specification. www.embeddedfreebsd.org/Documents/Intel-FTL.pdf, 1998.
• 10: Chris Jermaine , Anindya Datta , Edward Omiecinski, A Novel Index Supporting High Volume Data Warehouse Insertion, Proceedings of the 25th International Conference on Very Large Data Bases, p.235-246, September 07-10, 1999
• 11: Christopher Jermaine , Abhijit Pol , Subramanian Arumugam, Online maintenance of very large random samples, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007603]
• 12: Hyojun Kim , Seongjun Ahn, BPLRU: a buffer management scheme for improving random writes in flash storage, Proceedings of the 6th USENIX Conference on File and Storage Technologies, p.1-14, February 26-29, 2008, San Jose, California
• 13: Jongmin Lee , Sunghoon Kim , Hunki Kwon , Choulseung Hyun , Seongjun Ahn , Jongmoo Choi , Donghee Lee , Sam H. Noh, Block recycling schemes and their cost-based optimization in nand flash memory based storage system, Proceedings of the 7th ACM & IEEE international conference on Embedded software, September 30-October 03, 2007, Salzburg, Austria [doi>10.1145/1289927.1289956]
• 14: 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]
• 15: 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]
• 16: P. Miller. SimpleTech announces 512GB and 256GB 3.5-inch SSD drives. http://www.engadget.com/2007/04/18/, April 2007.
• 17: 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]
• 18: Frank Olken , Doron Rotem , Ping Xu, Random sampling from hash files, ACM SIGMOD Record, v.19 n.2, p.375-386, Jun. 1990
• 19: Patrick O'Neil , Edward Cheng , Dieter Gawlick , Elizabeth O'Neil, The log-structured merge-tree (LSM-tree), Acta Informatica, v.33 n.4, p.351-385, 1996 [doi>10.1007/s002360050048]
• 20: William Pugh, Skip lists: a probabilistic alternative to balanced trees, Communications of the ACM, v.33 n.6, p.668-676, June 1990 [doi>10.1145/78973.78977]
• 21: D. Reinsel and J. Janukowicz. Datacenter SSDs: Solid footing for growth. Samsung white paper. www.samsung.com/global/business/semiconductor/products/flash/ssd/pdf/datacenter_ssds.pdf, January 2008.
• 22: SyCard. CF extend 180 CompactFlash Flexible Extender Card. http://www.sycard.com/cfextl 80.html, 2008.
• 23: Jeffrey S. Vitter, Random sampling with a reservoir, ACM Transactions on Mathematical Software (TOMS), v.11 n.1, p.37-57, March 1985 [doi>10.1145/3147.3165]
• 24: Jeffrey Scott Vitter, An efficient algorithm for sequential random sampling, ACM Transactions on Mathematical Software (TOMS), v.13 n.1, p.58-67, March 1987 [doi>10.1145/23002.23003]
• 25: Jeffrey Scott Vitter, External memory algorithms and data structures: dealing with massive data, ACM Computing Surveys (CSUR), v.33 n.2, p.209-271, June 2001 [doi>10.1145/384192.384193]
• 26: Chin-Hsien Wu , Li-Pin Chang , Tei-Wei Kuo, An efficient R-tree implementation over flash-memory storage systems, Proceedings of the 11th ACM international symposium on Advances in geographic information systems, p.17-24, November 07-08, 2003, New Orleans, Louisiana, USA [doi>10.1145/956676.956679]
• 27: Yahoo!-Finance. Zeus-IOPS solid state drives surge to 512GB. http://biz.yahoo.com/pz/070418/117663.html, April 2007.
• 28: 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

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.2 Information Storage
          Subjects: File organization

Additional Classification:
  E. Data
  E.5 FILES
      Subjects: Organization/structure; Sorting/searching

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
      H.3.4 Systems and Software
          Subjects: Performance evaluation (efficiency and effectiveness)

General Terms:
Algorithms, Design, Management, Performance