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. A. Birrell et al. A design for high-performance flash disks. SIGOPS Oper. Syst. Rev., 41(2), 2007.
2. D. L. Black and D. D. Sleator. Competitive algorithms for replication and migration problems. Technical Report CMU-CS-89-201, 1989.
3. A. Borodin, N. Linial, and M. E. Saks. An optimal on-line algorithm for metrical task systems. J. ACM, 39(4), 1992.
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. G. Graefe. Query Evaluation Techniques for Large Databases. ACM Comput. Surv., 25(2), 1993.
7. G. Graefe. The five-minute rule twenty years later, and how flash memory chenges the rules. DAMON, 2007.
8. J. Kim et al. A space-efficient flash translation layer for compactflash systems. Transactions on Consumer Electronics., 2002.
9. S.-W. Lee and B. Moon. Design of flash-based DBMS: An in-page logging approach. In SIGMOD, 2007.
10. S.-W. Lee et al. A log buffer-based flash translation layer using fully-associative sector translation. Trans. on Embedded Computing Sys., 2007.
11. Microsoft Corp. Windows Vista Operating System: ReadyBoost.
12. S. Nath and A. Kansal. FlashDB: Dynamic Self-Tuning Database for NAND Flash. In IPSN, 2007.
13. M. Stonebraker. Operating system support for database management. Commun. ACM, 24(7):412--418, 1981.
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. C.-H. Wu, T.-W. Kuo, and L. P. Chang. An efficient b-tree layer implementation for flash-memory storage systems. Trans. on Embedded Computing Sys., 6(3), 2007.

Index Terms

• General and reference

  • Cross-computing tools and techniques

    • Performance

• Information systems

  • Information storage systems

    • Record storage systems

    • Storage management

• Software and its engineering

  • Software creation and management

    • Software verification and validation

      • Operational analysis

  • Software organization and properties

    • Contextual software domains

      • Operating systems

        • Communications management

          • Input / output

        • File systems management

        • Memory management

• Theory of computation

  • Design and analysis of algorithms

    • Online algorithms

      • Online learning algorithms

  • Models of computation

    • Interactive computation

  • Theory and algorithms for application domains

    • Machine learning theory

      • Online learning theory