The five-minute rule twenty years later, and how flash memory changes the rules

ABSTRACT

In 1987, Gray and Putzolo presented the five-minute rule, which was reviewed and renewed ten years later in 1997. With the advent of flash memory in the gap between traditional RAM main memory and traditional disk systems, the five-minute rule now applies to large pages appropriate for today's disks and their fast transfer bandwidths, and it also applies to flash disks holding small pages appropriate for their fast access latency.

Flash memory fills the gap between RAM and disks in terms of many metrics: acquisition cost, access latency, transfer bandwidth, spatial density, and power consumption. Thus, within a few years, flash memory will likely be used heavily in operating systems, file systems, and database systems. Research into appropriate system architectures is urgently needed.

The basic software architectures for exploiting flash in these systems are called "extended buffer pool" and "extended disk" here. Based on the characteristics of these software architectures, an argument is presented why operating systems and file systems on one hand and database systems on the other hand will best benefit from flash memory by employing different software architectures.

REFERENCES

• 1: Michael A. Bender , Erik D. Demaine , Martin Farach-Colton, Cache-Oblivious B-Trees, SIAM Journal on Computing, v.35 n.2, p.341-358, 2005 [doi>10.1137/S0097539701389956]
• 2: {BM 70} Rudolf Bayer, Edward M. McCreight: Organization and Maintenance of Large Ordered Indexes. SIGFIDET Workshop 1970: 107--141.
• 3: Rudolf Bayer , Karl Unterauer, Prefix B-trees, ACM Transactions on Database Systems (TODS), v.2 n.1, p.11-26, March 1977 [doi>10.1145/320521.320530]
• 4: {CDR 89} Michael J. Carey, David J. DeWitt, Joel E. Richardson, Eugene J. Shekita: Storage Management in EXODUS. Object-Oriented Concepts, Databases, and Applications 1989: 341--369.
• 5: Peter M. Chen , Edward K. Lee , Garth A. Gibson , Randy H. Katz , David A. Patterson, RAID: high-performance, reliable secondary storage, ACM Computing Surveys (CSUR), v.26 n.2, p.145-185, June 1994 [doi>10.1145/176979.176981]
• 6: David J. DeWitt , Jeffrey F. Naughton , Joseph Burger, Nested Loops Revisited, Proceedings of the 2nd International Conference on Parallel and Distributed Information Systems, p.230-242, January 20-23, 1993
• 7: {G 03} Goetz Graefe: Executing Nested Queries. BTW 2003: 58--77.
• 8: Goetz Graefe, Write-optimized B-trees, Proceedings of the Thirtieth international conference on Very large data bases, p.672-683, August 31-September 03, 2004, Toronto, Canada
• 9: Goetz Graefe, Implementing sorting in database systems, ACM Computing Surveys (CSUR), v.38 n.3, p.10-es, 2006 [doi>10.1145/1132960.1132964]
• 10: {G 07} Goetz Graefe: Master-detail clustering using merged indexes. Informatik -- Forschung und Entwicklung (2007).
• 11: {GF 07} Jim Gray, Bob Fitzgerald: FLASH Disk Opportunity for Server-Applications. http://research.microsoft.com/~gray/papers/FlashDiskPublic.doc.
• 12: Jim Gray , Goetz Graefe, The five-minute rule ten years later, and other computer storage rules of thumb, ACM SIGMOD Record, v.26 n.4, p.63-68, Dec. 1997 [doi>10.1145/271074.271094]
• 13: Jim Gray , Franco Putzolu, The 5 minute rule for trading memory for disc accesses and the 10 byte rule for trading memory for CPU time, ACM SIGMOD Record, v.16 n.3, p.395-398, Dec. 1987
• 14: Theo Haerder, Implementing a generalized access path structure for a relational database system, ACM Transactions on Database Systems (TODS), v.3 n.3, p.285-298, Sept. 1978 [doi>10.1145/320263.320284]
• 15: {H 07} James Hamilton: An Architecture for Modular Data Centers. CIDR 2007.
• 16: Theo Haerder , Andreas Reuter, Principles of transaction-oriented database recovery, ACM Computing Surveys (CSUR), v.15 n.4, p.287-317, December 1983 [doi>10.1145/289.291]
• 17: David Lomet, The evolution of effective B-tree: page organization and techniques: a personal account, ACM SIGMOD Record, v.30 n.3, September 2001 [doi>10.1145/603867.603878]
• 18: Jim Larus , Ravi Rajwar, Transactional Memory (Synthesis Lectures on Computer Architecture), Morgan & Claypool Publishers, 2007
• 19: Chris Nyberg , Tom Barclay , Zarka Cvetanovic , Jim Gray , Dave Lomet, AlphaSort: a cache-sensitive parallel external sort, The VLDB Journal — The International Journal on Very Large Data Bases, v.4 n.4, October 1995
• 20: John Ousterhout , Fred Douglis, Beating the I/O bottleneck: a case for log-structured file systems, ACM SIGOPS Operating Systems Review, v.23 n.1, p.11-28, Jan. 1989 [doi>10.1145/65762.65765]
• 21: Patrick E. O'Neil, The SB-tree: an index-sequential structure for high-performance sequential access, Acta Informatica, v.29 n.3, p.241-265, June 1992 [doi>10.1007/BF01185680]
• 22: {RSK 07} Suzanne Rivoire, Mehul Shah, Partha Ranganathan, Christos Kozyrakis: JouleSort: A Balanced Energy-Efficiency Benchmark. SIGMOD 2007.
• 23: 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]
• 24: Ambuj Shatdal , Chander Kant , Jeffrey F. Naughton, Cache Conscious Algorithms for Relational Query Processing, Proceedings of the 20th International Conference on Very Large Data Bases, p.510-521, September 12-15, 1994
• 25: {W 01} David Woodhouse: JFFS: the Journaling Flash File System. Ottawa Linux Symposium, Red Hat Inc, 2001.