Dynamic File Allocation in Disk Arrays.

Gerhard Weikum, Peter Zabback, Peter Scheuermann: Dynamic File Allocation in Disk Arrays. SIGMOD Conference 1991: 406-415
  author    = {Gerhard Weikum and
               Peter Zabback and
               Peter Scheuermann},
  editor    = {James Clifford and
               Roger King},
  title     = {Dynamic File Allocation in Disk Arrays},
  booktitle = {Proceedings of the 1991 ACM SIGMOD International Conference on
               Management of Data, Denver, Colorado, May 29-31, 1991},
  publisher = {ACM Press},
  year      = {1991},
  pages     = {406-415},
  ee        = {, db/conf/sigmod/WeikumZS91.html},
  crossref  = {DBLP:conf/sigmod/91},
  bibsource = {DBLP,}


Large arrays of small disks are being considered as a promising approach to high performance I/O architectures. In this paper we deal with the problem of data placement in such a disk array. The prevalent approach is to decluster large files across a number of disks so as to minimize the access time to a file and balance the I/O load across the disks. The data placement problem entails determining the number of disks and the set of disks across which a file is declustered. Unlike previous work, this paper does not assume that all files are allocated at the same time but rather considers dynamic file creations, This makes the placement problem considerably harder because each placement decision has to take into account the current allocation state and the access frequencies of the disks and the existing files. As a result, file creation may involve partial reorganization on one or more disks. The paper proposes heuristic algorithms for the placement of dynamically created files. The algorithms provide a good compromise between maximizing I/O performance of the disk array and minimizing the work invested in partial reorganizations. The paper presents preliminary performance results of various alternative algorithms under a synthetic workload.

Copyright © 1991 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 2, SIGMOD '75-'92" and ...

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

Printed Edition

James Clifford, Roger King (Eds.): Proceedings of the 1991 ACM SIGMOD International Conference on Management of Data, Denver, Colorado, May 29-31, 1991. ACM Press 1991 BibTeX , SIGMOD Record 20(2), June 1991

Online Edition: ACM Digital Library

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


Dina Bitton, Jim Gray: Disk Shadowing. VLDB 1988: 331-338 BibTeX
Haran Boral, William Alexander, Larry Clay, George P. Copeland, Scott Danforth, Michael J. Franklin, Brian E. Hart, Marc G. Smith, Patrick Valduriez: Prototyping Bubba, A Highly Parallel Database System. IEEE Trans. Knowl. Data Eng. 2(1): 4-24(1990) BibTeX
George P. Copeland, William Alexander, Ellen E. Boughter, Tom W. Keller: Data Placement In Bubba. SIGMOD Conference 1988: 99-108 BibTeX
George P. Copeland, Tom W. Keller: A Comparison Of High-Availability Media Recovery Techniques. SIGMOD Conference 1989: 98-109 BibTeX
David J. DeWitt, Shahram Ghandeharizadeh, Donovan A. Schneider, Allan Bricker, Hui-I Hsiao, Rick Rasmussen: The Gamma Database Machine Project. IEEE Trans. Knowl. Data Eng. 2(1): 44-62(1990) BibTeX
Shahram Ghandeharizadeh, David J. DeWitt: A Multiuser Performance Analysis of Alternative Declustering Strategies. ICDE 1990: 466-475 BibTeX
Shahram Ghandeharizadeh, David J. DeWitt: Hybrid-Range Partitioning Strategy: A New Declustering Strategy for Multiprocessor Database Machines. VLDB 1990: 481-492 BibTeX
Garth A. Gibson, Lisa Hellerstein, Richard M. Karp, Randy H. Katz, David A. Patterson: Failure Correction Techniques for Large Disk Arrays. ASPLOS 1989: 123-132 BibTeX
David K. Gifford, Alfred Z. Spector: The TWA Reservation System. Commun. ACM 27(7): 649-665(1984) BibTeX
Jim Gray, Bob Horst, Mark Walker: Parity Striping of Disk Arrays: Low-Cost Reliable Storage with Acceptable Throughput. VLDB 1990: 148-161 BibTeX
Mark F. Hornick, Stanley B. Zdonik: A Shared, Segmented Memory System for an Object-Oriented Database. ACM Trans. Inf. Syst. 5(1): 70-95(1987) BibTeX
Scott E. Hudson, Roger King: Cactis: A Self-Adaptive, Concurrent Implementation of an Object-Oriented Database Management System. ACM Trans. Database Syst. 14(3): 291-321(1989) BibTeX
Randy H. Katz, John K. Ousterhout, David A. Patterson, Michael Stonebraker: A Project on High Performance I/O Subsystems. IEEE Data Eng. Bull. 11(1): 40-47(1988) BibTeX
Tobin J. Lehman, Bruce G. Lindsay: The Starburst Long Field Manager. VLDB 1989: 375-383 BibTeX
Miron Livny, Setrag Khoshafian, Haran Boral: Multi-Disk Management Algorithms. SIGMETRICS 1987: 69-77 BibTeX
Edward Omiecinski, Peter Scheuermann: A Parallel Algorithm for Record Clustering. ACM Trans. Database Syst. 15(4): 599-624(1990) BibTeX
John K. Ousterhout, Hervé Da Costa, David Harrison, John A. Kunze, Michael D. Kupfer, James G. Thompson: A Trace-Driven Analysis of the UNIX 4.2 BSD File System. SOSP 1985: 15-24 BibTeX
David A. Patterson, Garth A. Gibson, Randy H. Katz: A Case for Redundant Arrays of Inexpensive Disks (RAID). SIGMOD Conference 1988: 109-116 BibTeX
A. L. Narasimha Reddy, Prithviraj Banerjee: An Evaluation of Multiple-Disk I/O Systems. IEEE Trans. Computers 38(12): 1680-1690(1989) BibTeX
Kenneth Salem, Hector Garcia-Molina: Disk Striping. ICDE 1986: 336-342 BibTeX
Behrokh Samadi: TUNEX: A Knowledge-Based System for Performance Tuning of the UNIX Operating System. IEEE Trans. Software Eng. 15(7): 861-874(1989) BibTeX
Hans-Jörg Schek, H.-Bernhard Paul, Marc H. Scholl, Gerhard Weikum: The DASDBS Project: Objectives, Experiences, and Future Prospects. IEEE Trans. Knowl. Data Eng. 2(1): 25-43(1990) BibTeX
Peter Scheuermann, Young Chul Park, Edward Omiecinski: Heuristic Reorganization of Clustered Files. FODO 1989: 16-30 BibTeX
Michael Stonebraker: The Case for Shared Nothing. IEEE Database Eng. Bull. 9(1): 4-9(1986) BibTeX
Michael Stonebraker, Randy H. Katz, David A. Patterson, John K. Ousterhout: The Design of XPRS. VLDB 1988: 318-330 BibTeX
Tandem Database Group - NonStop SQL: A Distributed, High-Performance, High-Availability Implementation of SQL. HPTS 1987: 60-104 BibTeX
Gerhard Weikum: Set-Oriented Disk Access to Large Complex Objects. ICDE 1989: 426-433 BibTeX

Referenced by

  1. Peter Scheuermann, Gerhard Weikum, Peter Zabback: Data Partitioning and Load Balancing in Parallel Disk Systems. VLDB J. 7(1): 48-66(1998)
  2. Peter Zabback, Ibrahim H. Önyüksel, Peter Scheuermann, Gerhard Weikum: Database Reorganization in Parallel Disk Arrays with I/O Service Stealing. IEEE Trans. Knowl. Data Eng. 10(5): 855-858(1998)
  3. Manish Mehta, David J. DeWitt: Data Placement in Shared-Nothing Parallel Database Systems. VLDB J. 6(1): 53-72(1997)
  4. Toshihiro Nemoto, Masaru Kitsuregawa, Mikio Takagi: Analysis of Cassette Migration Activities in Scalable Tape Archiver. DASFAA 1997: 461-470
  5. Kiran J. Achyutuni, Edward Omiecinski, Shamkant B. Navathe: Two Techniques for On-Line Index Modification in Shared Nothing Parallel Databases. SIGMOD Conference 1996: 125-136
  6. Nick Koudas, Christos Faloutsos, Ibrahim Kamel: Declustering Spatial Databases on a Multi-Computer Architecture. EDBT 1996: 592-614
  7. Kazuhiko Mogi, Masaru Kitsuregawa: Hot Block Clustering for Disk Arrays with Dynamic Striping. VLDB 1995: 90-99
  8. Duen-Ren Liu, Shashi Shekhar: A Similarity Graph-Based Approach to Declustering Problems and Its Application towards Paralleling Grid Files. ICDE 1995: 373-381
  9. Peter Scheuermann, Gerhard Weikum, Peter Zabback: ``Disk Cooling'' in Parallel Disk Systems. IEEE Data Eng. Bull. 17(3): 29-40(1994)
  10. Radek Vingralek, Yuri Breitbart, Gerhard Weikum: Distributed File Organization with Scalable Cost/Performance. SIGMOD Conference 1994: 253-264
  11. Axel Mönkeberg, Peter Zabback, Christof Hasse, Gerhard Weikum: The COMFORT Prototype: A Step Toward Automated Database Performance Tuning. SIGMOD Conference 1993: 542-543
  12. Thomas A. Mück: The DiNG - A Parallel Multiattribute File System for Deductive Database Machines. DASFAA 1993: 115-122
  13. Bin Jiang: I/O-Efficiency of Shortest Path Algorithms: An Analysis. ICDE 1992: 12-19
  14. Hans-Jörg Schek, Marc H. Scholl, Gerhard Weikum: The Background of the DASDBS & COSMOS Projects. MFDBS 1991: 377-388
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:07 2009