Flashing up the storage layer

ABSTRACT

In the near future, commodity hardware is expected to incorporate both flash and magnetic disks. In this paper we study how the storage layer of a database system can benefit from the presence of both kinds of disk. We propose using the flash and the magnetic disk at the same level of the memory hierarchy and placing a data page to only one of these disks according to the workload of the page. Pages with a read-intensive workload are placed on the flash disk, while pages with a write-intensive workload are placed on the magnetic disk. We present a family of on-line algorithms to decide the optimal placement of a page and study their theoretical properties. Our system is self-tuning, i.e., our algorithms adapt page placement to changing workloads. We also present a buffer replacement policy that takes advantage of the asymmetric I/O properties of the two types of storage media to reduce the total I/O cost. Our experimental evaluation shows remarkable I/O performance improvement over both flash-only and magnetic-only systems. These results, we believe, exhibit both the potential and necessity of such algorithms in future database systems.

REFERENCES

• 1: 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]
• 2: D. L. Black and D. D. Sleator. Competitive algorithms for replication and migration problems. Technical Report CMU-CS-89-201, 1989.
• 3: Allan Borodin , Nathan Linial , Michael E. Saks, An optimal on-line algorithm for metrical task system, Journal of the ACM (JACM), v.39 n.4, p.745-763, Oct. 1992 [doi>10.1145/146585.146588]
• 4: T.-S. Chung et al. System software for flash memory: A survey. In EUC, 2006.
• 5: Fusion-IO, Inc. The ioDrive. http://fusionio.com.
• 6: Goetz Graefe, Query evaluation techniques for large databases, ACM Computing Surveys (CSUR), v.25 n.2, p.73-169, June 1993 [doi>10.1145/152610.152611]
• 7: Goetz Graefe, The five-minute rule twenty years later, and how flash memory changes the rules, Proceedings of the 3rd international workshop on Data management on new hardware, June 15-15, 2007, Beijing, China [doi>10.1145/1363189.1363198]
• 8: J. Kim et al. A space-efficient flash translation layer for compactflash systems. Transactions on Consumer Electronics., 2002.
• 9: 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]
• 10: Sang-Won Lee , Dong-Joo Park , Tae-Sun Chung , Dong-Ho Lee , Sangwon Park , Ha-Joo Song, A log buffer-based flash translation layer using fully-associative sector translation, ACM Transactions on Embedded Computing Systems (TECS), v.6 n.3, p.18-es, July 2007 [doi>10.1145/1275986.1275990]
• 11: Microsoft Corp. Windows Vista Operating System: ReadyBoost.
• 12: 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]
• 13: Michael Stonebraker, Operating system support for database management, Communications of the ACM, v.24 n.7, p.412-418, July 1981 [doi>10.1145/358699.358703]
• 14: J. Westbrook. Randomized algorithms for multiprocessor page migration. In DIMACS Series in Discrete Mathematics and Theoretical Computer Science, volume 7, pages 135--150, 1992.
• 15: Wikipedia. Hybrid drive. http://en.wikipedia.org/wiki/Hybrid_drive.
• 16: Wikipedia. Multi level cell. http://en.wikipedia.org/wiki/Multi-level_Cell.
• 17: Chin-Hsien Wu , Tei-Wei Kuo , Li Ping Chang, An efficient B-tree layer implementation for flash-memory storage systems, ACM Transactions on Embedded Computing Systems (TECS), v.6 n.3, p.19-es, July 2007 [doi>10.1145/1275986.1275991]

INDEX TERMS

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

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
      D.4.4 Communications Management
          Subjects: Input/output
      D.4.8 Performance
          Subjects: Operational analysis

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Online computation

General Terms:
Algorithms, Design, Management