Random I/O scheduling in online tertiary storage systems

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

• CDT95: G. Carpaneto , M. Dell'Amico , P. Toth, Exact solution of large-scale, asymmetric traveling salesman problems, ACM Transactions on Mathematical Software (TOMS), v.21 n.4, p.394-409, Dec. 1995 [doi>10.1145/212066.212081]
• CHL93: Michael J. Carey , Laura M. Haas , Miron Livny, Tapes hold data, too: challenges of tuples on tertiary store, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.413-417, May 25-28, 1993, Washington, D.C., United States
• DK93: 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.
• Exa93: Exabyte Corporation, 1685 38th St., Boulder, CO. Medza Guide: D~g~tal 8ram Me&a, mkt- 12-01 edition, January 1993.
• GD87: Robert Geist , Stephen Daniel, A continuum of disk scheduling algorithms, ACM Transactions on Computer Systems (TOCS), v.5 n.1, p.77-92, Feb. 1987 [doi>10.1145/7351.8929]
• GMW95: L. Golubchik , R. R. Muntz , R. W. Watson, Analysis of striping techniques in robotic storage libraries, Proceedings of the 14th IEEE Symposium on Mass Storage Systems, p.225, September 11-14, 1995
• HS96: Bruce K. Hillyer , Avi Silberschatz, On the modeling and performance characteristics of a serpentine tape drive, Proceedings of the 1996 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.170-179, May 23-26, 1996, Philadelphia, Pennsylvania, United States
• Isa93: David Isaac. HierarchicM storage management for relational databases. In Proceedings of the Twelfth IEEE Sympos,um on Mass Storage Systems {MSS93}, pages 139-144.
• KAOP91: Randy H. Katz , Thomas E. Anderson , John K. Ousterhout , David A. Patterson, Rob-line Storage: Low Latency, High Capacity, University of California at Berkeley, Berkeley, CA, 1991
• KB91: 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.
• KMP90: J. G. Kollias , Y. Manolopoulos , C. H. Papadimitriou, The optimum execution order of queries in linear storage, Information Processing Letters, v.36 n.3, p.141-145, Nov. 1990 [doi>10.1016/0020-0190(90)90083-A]
• LLKS85: E. L. LaMer, J. K. Lenstra, A. H. G. Rinnooy Kan, and D. B. Shmoys. The Traveling Salesman Problem. Wiley, Chichester, 1985.
• MH94: David Maier , David M. Hansen, Bambi Meets Godzilla: Object Databases for Scientific Computing, Proceedings of the Seventh International Working Conference on Scientific and Statistical Database Management, p.176-184, September 28-30, 1994
• ML95: Jussi Myllymaki , Miron Livny, Disk-tape joins: synchronizing disk and tape access, Proceedings of the 1995 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, p.279-290, May 15-19, 1995, Ottawa, Ontario, Canada
• MSS93: Proceedings of the Twelfth IEEE Symposzum on Mass Storage Systems, Monterey, CA, April 26- 29 1993.
• Qua95: 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.
• Sar95: Sunita Sarawagi, Query Processing in Tertiary Memory Databases, Proceedings of the 21th International Conference on Very Large Data Bases, p.585-596, September 11-15, 1995
• SS96: Sunita Sarawagi and Michael Stonebraker. Execution reordering in tertiary memory databases. 1996. http://http.cs.berkeley.edu/gunita/.
• SSU91: Avi Silberschatz , Michael Stonebraker , Jeff Ullman, Database systems: achievements and opportunities, Communications of the ACM, v.34 n.10, p.110-120, Oct. 1991 [doi>10.1145/125223.125272]
• Sto91: Michael Stonebraker, Managing persistent objects in a multi-level store, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.2-11, May 29-31, 1991, Denver, Colorado, United States
• WGP94: Bruce L. Worthington , Gregory R. Ganger , Yale N. Patt, Scheduling algorithms for modern disk drives, Proceedings of the 1994 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.241-251, May 16-20, 1994, Nashville, Tennessee, United States
• Won80: C. K. Wong, Minimizing Expected Head Movement in One-Dimensional and Two-Dimensional Mass Storage Systems, ACM Computing Surveys (CSUR), v.12 n.2, p.167-178, June 1980 [doi>10.1145/356810.356814]

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

General Terms:
Algorithms, Measurement, Performance, Theory