The Five-Minute Rule 20 Years Later

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The Five-Minute Rule 20 Years Later: and How Flash Memory Changes the Rules

Full text

Digital Edition , Html

Html (25 KB), Pdf

Pdf (258 KB)

Source

Queue archive
Volume 6 , Issue 4 (July/August 2008) table of contents
Enterprise Flash Storage

FEATURE: Q focus: Flash Storage table of contents

Pages 40-52

Year of Publication: 2008

ISSN:1542-7730

Author

Goetz Graefe

Hewlett-Packard Laboratories

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 482, Downloads (12 Months): 2760, Citation Count: 0

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1413254.1413264 What is a DOI?

ABSTRACT

The old rule continues to evolve, while flash memory adds two new rules. In 1987, Jim Gray and Gianfranco Putzolu published their now-famous five-minute rule for trading off memory and I/O capacity. Their calculation compares the cost of holding a record (or page) permanently in memory with the cost of performing disk I/O each time the record (or page) is accessed, using appropriate fractions of prices for RAM chips and disk drives. The name of their rule refers to the break-even interval between accesses. If a record (or page) is accessed more often, it should be kept in memory; otherwise, it should remain on disk and read when needed.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	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
	2	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]
	3	Jim Larus , Ravi Rajwar, Transactional Memory (Synthesis Lectures on Computer Architecture), Morgan & Claypool Publishers, 2007
	4	Hamilton, J. 2007. An architecture for modular data centers. CIDR (Conference on Innovative Data Systems Research).
	5	Gray, J., Fitzgerald, B. Flash Disk Opportunity for Server-Applications; http://research.microsoft.com/~gray/papers/FlashDiskPublic.doc.
	6	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]
	7	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]
	8	See reference 7.
	9	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]
	10	Woodhouse, D. 2001. JFFS: the Journaling Flash File System. Ottawa Linux Symposium. Red Hat Inc.
	11	See reference 1.
	12	See reference 1.
	13	See reference 2.
	14	See reference 1.
	15	See reference 5.
	16	See reference 1.
	17	See reference 2.
	18	Graefe, G. 2007. Master-detail clustering using merged indexes. Informatik ¿ Forschung und Entwicklung 21 (3-4): 127-145.
	19	Michael J. Carey , David J. DeWitt , Joel F. Richardson , Eugene J. Shekita, Storage management for objects in EXODUS, Object-oriented concepts, databases, and applications, ACM, New York, NY, 1989 [doi>10.1145/63320.66509]
	20	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]
	21	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
	22	See reference 21.
	23	See reference 2.
	24	Bayer, R., McCreight, E.M. 1970. Organization and maintenance of large ordered indexes. SIGFIDET Workshop: 107-141.
	25	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]
	26	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]
	27	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]
	28	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]
	29	Goetz Graefe, Implementing sorting in database systems, ACM Computing Surveys (CSUR), v.38 n.3, p.10-es, 2006 [doi>10.1145/1132960.1132964]
	30	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
	31	Suzanne Rivoire , Mehul A. Shah , Parthasarathy Ranganathan , Christos Kozyrakis, JouleSort: a balanced energy-efficiency benchmark, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247522]
	32	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
	33	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
	34	Graefe, G. 2003. Executing nested queries. BTW: 58-77.
	35	See reference 24.
	36	See reference 18.
	37	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]