article

Free access

Random I/O scheduling in online tertiary storage systems

Authors:

Bruce K. Hillyer,

Avi SilberschatzAuthors Info & Claims

ACM SIGMOD Record, Volume 25, Issue 2

Pages 195 - 204

https://doi.org/10.1145/235968.233332

Published: 01 June 1996 Publication History

Abstract

New database applications that require the storage and retrieval of many terabytes of data are reaching the limits for disk-based storage systems, in terms of both cost and scalability. These limits provide a strong incentive for the development of databases that augment disk storage with technologies better suited to large volumes of data. In particular, the seamless incorporation of tape storage into database systems would be of great value. Tape storage is two orders of magnitude more efficient than disk in terms of cost per terabyte and physical volume per terabyte; however, a key problem is that the random access latency of tape is three to four orders of magnitude slower than disk. Thus, to incorporate a tape bulk store in an online storage system, the problem of tape access latency must be solved. One approach to reducing the latency is careful I/O scheduling. The focus of this paper is on efficient random I/O scheduling for tape drives that use a serpentine track layout, such as the Quantum DLT and the IBM 3480 and 3590. For serpentine tape, I/O scheduling is problematic because of the complex relationships between logical block numbers, their physical positions on tape, and the time required for tape positioning between these physical positions. The results in this paper show that our scheduling schemes provide a significant improvement in the latency of random access to serpentine tape.

References

[1]

G. Carpaneto, M. Dellamico, and P. Toth. Exact solution of large scale, asymmetric traveling salesman problems; algorithm-750. A CM Transactions on Mathematical Software, 21(4):394- 415, December 1995.

Digital Library

[2]

Michael J. Carey, Laura M. Haas, and Miron Livny. Tapes hold data, too: challenges of tuples on tertiary store. In Proceedings SIGMOD International Conference on Management of Data, pages 413-417, Washington, DC, May 26-28 1993.

Digital Library

[3]

Ann L. Drapeau and Randy H. Katz. Striped tape arrays. In Procee&ngs of the Twelfth IEEE Symposium, on Mass Storage Systems {MSS93}, pages 257--265.

[4]

Exabyte Corporation, 1685 38th St., Boulder, CO. Medza Guide: D~g~tal 8ram Me&a, mkt- 12-01 edition, January 1993.

[5]

obert Geist and Stephen Daniel. A continuum of disk scheduling algorithms. A CM Transactzons on Computer Systems, 5(1):77-92, February 1987.

Digital Library

[6]

Le~na Golubchik, Rmhard R. Muntz, and Richard W. Watson. Analysis of striping techniques in robotic storage libraries. In Proceedzngs of the Fourteenth IEEE Symposium on Mass Storage Systems, pages 225-238, Monterey, CA, September 11-14 1995.

Digital Library

[7]

Bruce K. HilIyer and Avi Silberschatz. On the modehng and performance characteristics of a serpentine tape drive. In Proceedings of the 1996 A CM S,gmetvics Conference on Measurement and Modehng of Computer Systems, Philadelphia, PA, May 23-26 1996.

Digital Library

[8]

David Isaac. HierarchicM storage management for relational databases. In Proceedings of the Twelfth IEEE Sympos,um on Mass Storage Systems {MSS93}, pages 139-144.

[9]

Randy H. Katz, Thomas E. Anderson, John K. Ousterhout, and David A. Patterson. Robo-line storage: low latency, high capacity storage systems over geographically distributed networks. Technical Report Sequoia 2000 Technical Report $2K-91-3, University of California, Berkeley, Ocsober 1991.

Digital Library

[10]

Ben Kobler and John Berbert. NASA earth observing system data information system (EOS- DIS). In Proceedings of the Eleventh IEEE Symposzum on Mass Storage Systems, pages 18-19, Monterey, CA, October 7-10 1991.

[11]

John G. Kollias, Yannis Manolopoulos, and Christos H. Papadimitriou. The optimum execution order of queries in linear storage. Information Processzng Letters, 36(3):141-145, November 1 1990.

Digital Library

[12]

E. L. LaMer, J. K. Lenstra, A. H. G. Rinnooy Kan, and D. B. Shmoys. The Traveling Salesman Problem. Wiley, Chichester, 1985.

[13]

David Maier and David M. Hansen. Bambi meets Godzilla: object databases for scientific computing. In Proceedings of the seventh International Working Conference on Scientific and oCtat~stcal Database Management, pages 176-184, Charlottesville, VA, September 28-30 1994. IEEE Computer Society Press.

Digital Library

[14]

Jussi Myllymaki and Miron Livny. Disk-tape joins: synchronizing disk and tape access. In Proceedings of the 1995 A CM S~gmetmcs Conference on Measurement and Modehng of Computer Systems, pages 279-290, Ottawa, Canada, May 15-19 1995.

Digital Library

[15]

Proceedings of the Twelfth IEEE Symposzum on Mass Storage Systems, Monterey, CA, April 26- 29 1993.

[16]

Quantum Corporation, 715 Sycamore Ave., Milpitas, CA 95035. Quantum DLT~O00 / DLT4500 / DLT~700 S Tape Mini-L~brary Product Manual, 81-108336-01, 1995.

[17]

Sunita Sarawagi. Query processing in tertiary memory databases. In Proceedings of the 21 st International Conference on Very Large Databases, pages 585-596, Zurich, Switzerland, September 11-15 1995.

Digital Library

[18]

Sunita Sarawagi and Michael Stonebraker. Execution reordering in tertiary memory databases. 1996. http://http.cs.berkeley.edu/gunita/.

[19]

Avi Silberschatz, Michael Stonebraker, and Jeff Ullman. Database systems: achievements and opportunities. Communications of the A CM, 34(10):110-120, October 1991.

Digital Library

[20]

Michael Stonebraker. Managing persistent objects in a multi-level store. In Proceedings SIG- MOD International Conference on Management of Data, pages 2-11, Denver, CO, May 29-31 1991.

Digital Library

[21]

Bruce L. Worthington, Gregory R. Ganger, and Yale N. Patt. Scheduling algorithms for modern disk drives. In Proceedings of the i99~ A CM Szgmetmcs Conference on Measurement and Modeling of Computer Systems, pages 241- 251, Nashville, TN, May 16-20 1994.

Digital Library

[22]

C.K. Wong. Minimizing expected head movement in one-dimensional and two-dimensional mass storage systems. A CM Computzng Surveys, 12(2):167-178, June 1980.

Digital Library

Cited By

Papantonakis PPnevmatikatos DPapaefstathiou IManifavas C(2013)Fast, FPGA-based Rainbow Table creation for attacking encrypted mobile communications2013 23rd International Conference on Field programmable Logic and Applications10.1109/FPL.2013.6645525(1-6)Online publication date: Sep-2013
https://doi.org/10.1109/FPL.2013.6645525
He DMandagere NDu D(2007)Design and Implementation of a Network Aware Object-based Tape Device24th IEEE Conference on Mass Storage Systems and Technologies (MSST 2007)10.1109/MSST.2007.4367970(143-156)Online publication date: Sep-2007
https://doi.org/10.1109/MSST.2007.4367970
Mościński JNikolow DPogoda MSłota R(2006)Storing large volumes of structured scientific data on tertiary storageHigh-Performance Computing and Networking10.1007/BFb0100704(1262-1265)Online publication date: 17-Nov-2006
https://doi.org/10.1007/BFb0100704
Show More Cited By

Recommendations

Random I/O scheduling in online tertiary storage systems
SIGMOD '96: Proceedings of the 1996 ACM SIGMOD international conference on Management of data

New database applications that require the storage and retrieval of many terabytes of data are reaching the limits for disk-based storage systems, in terms of both cost and scalability. These limits provide a strong incentive for the development of ...
Tertiary storage: an evaluation of new applications
Tertiary Storage: An Evaluation of New Applications

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGMOD Record

ACM SIGMOD Record Volume 25, Issue 2

June 1996

557 pages

ISSN:0163-5808

DOI:10.1145/235968

Chairman:
T. H. Merrett
McGill Univ.
,
Editors:
H. V. Jagadish,
Inderpal Singh Mumick

Issue’s Table of Contents

SIGMOD '96: Proceedings of the 1996 ACM SIGMOD international conference on Management of data
June 1996
560 pages
ISBN:0897917944
DOI:10.1145/233269
Editor:
Jennifer Widom
Stanford Univ., Stanford, CT

Copyright © 1996 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 1996

Published in SIGMOD Volume 25, Issue 2

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

30
Total Citations
View Citations
547
Total Downloads

Downloads (Last 12 months)99
Downloads (Last 6 weeks)17

Reflects downloads up to 08 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Papantonakis PPnevmatikatos DPapaefstathiou IManifavas C(2013)Fast, FPGA-based Rainbow Table creation for attacking encrypted mobile communications2013 23rd International Conference on Field programmable Logic and Applications10.1109/FPL.2013.6645525(1-6)Online publication date: Sep-2013
https://doi.org/10.1109/FPL.2013.6645525
He DMandagere NDu D(2007)Design and Implementation of a Network Aware Object-based Tape Device24th IEEE Conference on Mass Storage Systems and Technologies (MSST 2007)10.1109/MSST.2007.4367970(143-156)Online publication date: Sep-2007
https://doi.org/10.1109/MSST.2007.4367970
Mościński JNikolow DPogoda MSłota R(2006)Storing large volumes of structured scientific data on tertiary storageHigh-Performance Computing and Networking10.1007/BFb0100704(1262-1265)Online publication date: 17-Nov-2006
https://doi.org/10.1007/BFb0100704
Dashti A(2001)WARP:Warp Around Data Placement Technique for Serpentine Tapes2001 Eighteenth IEEE Symposium on Mass Storage Systems and Technologies10.1109/MSS.2001.10028(339-339)Online publication date: Apr-2001
https://doi.org/10.1109/MSS.2001.10028
ChanHo Moon Hyunchul Kang (2001)Heuristic algorithms for I/O scheduling for efficient retrieval of large objects from tertiary storageProceedings 12th Australasian Database Conference. ADC 200110.1109/ADC.2001.904477(145-152)Online publication date: 2001
https://doi.org/10.1109/ADC.2001.904477
Słota RKosch HNikolow DPogoda1 MBreidler KPodlipnig S(2001)MMSRS - Multimedia Storage and Retrieval System for a Distributed Medical Information SystemHigh Performance Computing and Networking10.1007/3-540-45492-6_52(517-524)Online publication date: 12-Jun-2001
https://doi.org/10.1007/3-540-45492-6_52
Dashti AShahabi C(2000)Data placement techniques for serpentine tapesProceedings of the 33rd Annual Hawaii International Conference on System Sciences10.1109/HICSS.2000.927005(10)Online publication date: 2000
https://doi.org/10.1109/HICSS.2000.927005
More SChoudhary A(2000)Scheduling Queries for Tape-Resident DataEuro-Par 2000 Parallel Processing10.1007/3-540-44520-X_181(1292-1301)Online publication date: 18-Aug-2000
https://doi.org/10.1007/3-540-44520-X_181
Kraiss AMuth PGillmann M(1999)Tape-disk join strategies under disk contentionProceedings 15th International Conference on Data Engineering (Cat. No.99CB36337)10.1109/ICDE.1999.754971(552-559)Online publication date: 1999
https://doi.org/10.1109/ICDE.1999.754971
Prabhakar SAgrawal DEl Abbadi ASingh A(1997)Scheduling tertiary I/O in database applicationsDatabase and Expert Systems Applications. 8th International Conference, DEXA '97. Proceedings10.1109/DEXA.1997.617416(722-727)Online publication date: 1997
https://doi.org/10.1109/DEXA.1997.617416
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Figures

Tables

Media

View Issue’s Table of Contents