Clotho: decoupling memory page layout from storage organization

ABSTRACT

As database application performance depends on the utilization of the memory hierarchy, smart data placement plays a central role in increasing locality and in improving memory utilization. Existing techniques, however, do not optimize accesses to all levels of the memory hierarchy and for all the different workloads, because each storage level uses different technology (cache, memory, disks) and each application accesses data using different patterns. Clotho is a new buffer pool and storage management architecture that decouples in-memory page layout from data organization on non-volatile storage devices to enable independent data layout design at each level of the storage hierarchy. Clotho can maximize cache and memory utilization by (a) transparently using appropriate data layouts in memory and non-volatile storage, and (b) dynamically synthesizing data pages to follow application access patterns at each level as needed. Clotho creates in-memory pages individually tailored for compound and dynamically changing workloads, and enables efficient use of different storage technologies (e.g., disk arrays or MEMS-based storage devices). This paper describes the Clotho design and prototype implementation and evaluates its performance under a variety of workloads using both disk arrays and simulated MEMS-based storage devices.

References

1. {1} A. Ailamaki, D. J. DeWitt, M. D. Hill, and M. Skounakis. Weaving relations for cache performance. International Conference on Very Large Databases, pages 169-180. Morgan Kaufmann Publishing, Inc., 2001.
2. {2} A. Ailamaki, D. J. DeWitt, M. D. Hill, and D. A. Wood. DBMSs on a modern processor: where does time go? International Conference on Very Large Databases, pages 266-277. Morgan Kaufmann Publishing, Inc., 1999.
3. {3} P. A. Boncz, S. Manegold, and M. L. Kersten. Database architecture optimized for the new bottleneck: memory access. International Conference on Very Large Databases, pages 54-65. Morgan Kaufmann Publishers, Inc., 1999.
4. {4} M. J. Carey et al. Shoring up persistent applications. ACM SIGMOD International Conference on Management of Data. 1994.
5. {5} L. R. Carley et al. Single-chip computers with microelectromechanical systems-based magnetic memory. Journal of Applied Physics, 87(9):6680-6685, 1 May 2000.
6. {6} X. Chen and X. Zhang. Coordinated data prefetching by utilizing reference information at both proxy and web servers. Performance Evaluation Review, 29(2):32-38. ACM, September 2001.
7. {7} G. P. Copeland and S. Khoshafian. A decomposition storage model. ACM SIGMOD International Conference on Management of Data, pages 268-279. ACM Press, 1985.
8. {8} The DiskSim Simulation Environment (Version 3.0). http://-www.pdl.cmu.edu/DiskSim/index.html.
9. {9} R. A. Hankins and J. M. Patel. Data morphing: an adaptive, cache-conscious storage technique. International Conference on Very Large Databases, pages 1-12. VLDB, 2003.
10. {10} S. Manegold, P. A. Boncz, and M. L. Kersten. Generic database cost models for hierarchical memory systems. International Conference on Very Large Databases, pages 191-202. Morgan Kaufmann Publishers, Inc., 2002.
11. {11} C. Mohan et al. ARIES: a transaction recovery method supporting fine-granularity locking and partial rollbacks using write-ahead logging. ACM Transactions on Database Systems, 17(1):94-162, March 1992.
12. {12} D. A. Patterson, G. Gibson, and R. H. Katz. A case for redundant arrays of inexpensive disks (RAID). ACM SIGMOD International Conference on Management of Data, pages 109-116, 1-3 June 1988.
13. {13} R. Ramakrishnan and J. Gehrke. Database management systems, number 3rd edition. McGraw-Hill, 2003.
14. {14} R. Ramamurthy, D. J. DeWitt, and Q. Su. A case for fractured mirrors. International Conference on Very Large Databases, pages 430-441. Morgan Kaufmann Publishers, Inc., 2002.
15. {15} J. Schindler, A. Ailamaki, and G. R. Ganger. Lachesis: robust database storage management based on device-specific performance characteristics. International Conference on Very Large Databases, pages 706-717. Morgan Kaufmann Publishing, Inc., 2003.
16. {16} J. Schindler et al. Atropos: a disk array volume manager for orchestrated use of disks. Conference on File and Storage Technologies, pages 159-172. USENIX Association, 2004.
17. {17} J. Schindler, J. L. Griffin, C. R. Lumb, and G. R. Ganger. Track-aligned extents: matching access patterns to disk drive characteristics. Conference on File and Storage Technologies, pages 259-274. USENIX Association, 2002.
18. {18} S. W. Schlosser, J. L. Griffin, D. F. Nagle, and G. R. Ganger. Designing computer systems with MEMS-based storage. Architectural Support for Programming Languages and Operating Systems. 2000.
19. {19} S. W. Schlosser, J. Schindler, A. Ailamaki, and G. R. Ganger. Exposing and exploiting internal parallelism in MEMS-based storage. Technical Report CMU-CS-03-125. Carnegie-Mellon University, Pittsburgh, PA, March 2003.
20. {20} M. Shao and A. Ailamaki. DBMbench: Microbenchmarking database systems in a small, yet real world. Technical Report CMU-CS-03-161. Carnegie-Mellon University, Pittsburgh, PA, October 2003.
21. {21} P. Vettiger et al. The "Millipede" - more than one thousand tips for future AFM data storage. IBM Journal of Research and Development , 44(3):323-340, 2000.
22. {22} H. Yu, D. Agrawal, and A. E. Abbadi. Tabular placement of relational data on MEMS-based storage devices. International Conference on Very Large Databases, pages 680-693, 2003.
23. {23} J. Zhou and K. A. Ross. A Multi-resolution Block Storage Model for Database Design. International Database Engineering & Applications Symposium, 2003.

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

          • Buffering

        • File systems management

        • Memory management