Random I/O Scheduling in Online Tertiary Storage Systems.

Bruce Hillyer, Abraham Silberschatz: Random I/O Scheduling in Online Tertiary Storage Systems. SIGMOD Conference 1996: 195-204
  author    = {Bruce Hillyer and
               Abraham Silberschatz},
  editor    = {H. V. Jagadish and
               Inderpal Singh Mumick},
  title     = {Random I/O Scheduling in Online Tertiary Storage Systems},
  booktitle = {Proceedings of the 1996 ACM SIGMOD International Conference on
               Management of Data, Montreal, Quebec, Canada, June 4-6, 1996},
  publisher = {ACM Press},
  year      = {1996},
  pages     = {195-204},
  ee        = {, db/conf/sigmod/HillyerS96.html},
  crossref  = {DBLP:conf/sigmod/96},
  bibsource = {DBLP,}


New database applications that require the storage and retrieval of many terabytes of data are reaching the limits for disk-based storage systems, in 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.

Copyright © 1996 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

ACM SIGMOD Anthology

Online Version (ACM WWW Account required): Full Text in PDF Format

CDROM Version: Load the CDROM "Volume 1 Issue 1, SIGMOD '93-'97" and ...

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Printed Edition

H. V. Jagadish, Inderpal Singh Mumick (Eds.): Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data, Montreal, Quebec, Canada, June 4-6, 1996. ACM Press 1996 BibTeX , SIGMOD Record 25(2), June 1996

Online Edition: ACM Digital Library

[Index Terms]
[Full Text in PDF Format, 1143 KB]


Giorgio Carpaneto, Mauro Dell'Amico, Paolo Toth: Exact Solution of Large Scale Asymmetric Travelling Salesman Problems. ACM Trans. Math. Softw. 21(4): 394-409(1995) BibTeX
Michael J. Carey, Laura M. Haas, Miron Livny: Tapes Hold Data, Too: Challenges of Tuples on Tertiary Store. SIGMOD Conference 1993: 413-417 BibTeX
Ann L. Drapeau, Randy H. Katz: Striped Tape Arrays. IEEE Symposium on Mass Storage Systems 1993: 257-265 BibTeX
Robert Geist, Stephen Daniel: A Continuum of Disk Scheduling Algorithms. ACM Trans. Comput. Syst. 5(1): 77-92(1987) BibTeX
Leana Golubchik, Richard R. Muntz, Richard W. Watson: Analysis of Striping Techniques in Robotic Storage Libraries. IEEE Symposium on Mass Storage Systems 1995: 225-238 BibTeX
Bruce Hillyer, Abraham Silberschatz: On the Modeling and Performance Characteristics of a Serpentine Tape Drive. SIGMETRICS 1996: 170-179 BibTeX
David Isaac: Hierarchical Storage Management for Relational Databases. IEEE Symposium on Mass Storage Systems 1993: 139-144 BibTeX
Ben Kobler, John Berbert: NASA Earth Observing System Data Information System (EOSDIS). IEEE Symposium on Mass Storage Systems 1991: 18-19 BibTeX
John G. Kollias, Yannis Manolopoulos, Christos H. Papadimitriou: The Optimum Execution Order of Queries in Linear Storage. Inf. Process. Lett. 36(3): 141-145(1990) BibTeX
David Maier, David M. Hansen: Bambi Meets Godzilla: Object Databases for Scientific Computing. SSDBM 1994: 176-184 BibTeX
Jussi Myllymaki, Miron Livny: Disk-Tape Joins: Synchronizing Disk and Tape Access. SIGMETRICS 1995: 279-290 BibTeX
Sunita Sarawagi: Query Processing in Tertiary Memory Databases. VLDB 1995: 585-596 BibTeX
Abraham Silberschatz, Michael Stonebraker, Jeffrey D. Ullman: Database Systems: Achievements and Opportunities. Commun. ACM 34(10): 110-120(1991) BibTeX
Michael Stonebraker: Managing Persistent Objects in a Multi-Level Store. SIGMOD Conference 1991: 2-11 BibTeX
Bruce L. Worthington, Gregory R. Ganger, Yale N. Patt: Scheduling Algorithms for Modern Disk Drives. SIGMETRICS 1994: 241-252 BibTeX
C. K. Wong: Minimizing Expected Head Movement in One-Dimensional and Two-Dimensional Mass Storage Systems. ACM Comput. Surv. 12(2): 167-178(1980) BibTeX

Referenced by

  1. Olav Sandstå, Roger Midtstraum: Improving the Access Time Performance of Serpentine Tape Drives. ICDE 1999: 542-551
  2. Achim Kraiss, Peter Muth, Michael Gillmann: Tape-Disk Join Strategies under Disk Contention. ICDE 1999: 552-559
  3. Bruce Hillyer, Rajeev Rastogi, Abraham Silberschatz: Scheduling and Data Replication to Improve Tape Jukebox Performance. ICDE 1999: 532-541
  4. Achim Kraiss, Gerhard Weikum: Integrated Document Caching and Prefetching in Storage Hierarchies Based on Markov-Chain Predictions. VLDB J. 7(3): 141-162(1998)
  5. Theodore Johnson, Ethan L. Miller: Performance Measurements of Tertiary Storage Devices. VLDB 1998: 50-61
  6. Achim Kraiss, Gerhard Weikum: Vertical Data Migration in Large Near-Line Document Archives Based on Markov-Chain Predictions. VLDB 1997: 246-255
  7. Jie-Bing Yu, David J. DeWitt: Query Pre-Execution and Batching in Paradise: A Two-Pronged Approach to the Efficient Processing of Queries on Tape-Resident Raster Images. SSDBM 1997: 64-78
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:40:31 2009