Distributed File Organization with Scalable Cost/Performance.

@inproceedings{DBLP:conf/sigmod/VingralekBW94,
  author    = {Radek Vingralek and
               Yuri Breitbart and
               Gerhard Weikum},
  editor    = {Richard T. Snodgrass and
               Marianne Winslett},
  title     = {Distributed File Organization with Scalable Cost/Performance},
  booktitle = {Proceedings of the 1994 ACM SIGMOD International Conference on
               Management of Data, Minneapolis, Minnesota, May 24-27, 1994},
  publisher = {ACM Press},
  year      = {1994},
  pages     = {253-264},
  ee        = {http://doi.acm.org/10.1145/191839.191889, db/conf/sigmod/VingralekBW94.html},
  crossref  = {DBLP:conf/sigmod/94},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

This paper presents a distributed file organization for record-structured, disk-resident files with key-based exact-match access. The file is organized into buckets that are spread across multiple servers, where a server may hold multiple buckets. Client requests are serviced by mapping keys onto buckets and looking up the corresponding server in an address table. Dynamic growth in terms of file size and access load is supported by bucket splits and bucket migration onto other existing or newly acquired servers.

The significant and challenging problem addressed here is how to achieve scalability so that both the file size and the client throughput can be scaled up by linearly increasing the number of servers and dynamically redistributing data. Unlike previous work with similar objectives, our data redistribution considers explicitly the cost/performance ratio of the system by aiming to minimize the number of servers that are acquired to provide the required performance. A new server is acquired only if the overall server utilization in the system does not drop below a specified threshold. Preliminary simulation results show that the goal of scalability with controlled cost/performance is indeed achieved to a large extent.

Copyright © 1994 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

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

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/smod9397 or /cdrom

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD1 or /dvd

Printed Edition

Online Edition: ACM Digital Library

References

[BS85]

Amnon Barak, Amnon Shiloh: A Distributed Load-balancing Policy for a Multicomputer. Softw., Pract. Exper. 15(9): 901-913(1985)

[CS92]

Donald D. Chamberlin, Frank B. Schmuck: Dynamic Data Distribution (D³) in a Shared-Nothing Multiprocessor Data Store. VLDB 1992: 163-174

[Dev93]

Robert Devine: Design and Implementation of DDH: A Distributed Dynamic Hashing Algorithm. FODO 1993: 101-114

[DG92]

David J. DeWitt, Jim Gray: Parallel Database Systems: The Future of High Performance Database Systems. Commun. ACM 35(6): 85-98(1992)

[ED88]

Richard J. Enbody, H. C. Du: Dynamic Hashing Schemes. ACM Comput. Surv. 20(2): 85-113(1988)

[ELZ86]

Derek L. Eager, Edward D. Lazowska, John Zahorjan: Adaptive Load Sharing in Homogeneous Distributed Systems. IEEE Trans. Software Eng. 12(5): 662-675(1986)

[FNPS79]

Ronald Fagin, Jürg Nievergelt, Nicholas Pippenger, H. Raymond Strong: Extendible Hashing - A Fast Access Method for Dynamic Files. ACM Trans. Database Syst. 4(3): 315-344(1979)

[Gr91]

Jim Gray (Ed.): The Benchmark Handbook for Database and Transaction Systems (1st Edition). Morgan Kaufmann 1991
Contents

[HW94]

Yixiu Huang, Ouri Wolfson: Object Allocation in Distributed Databases and Mobile Computers. ICDE 1994: 20-29

[JK93]

Theodore Johnson, Padmashree Krishna: Lazy Updates for Distributed Search Structure. SIGMOD Conference 1993: 337-346

[Lar88]

Per-Åke Larson: Dynamic Hash Tables. Commun. ACM 31(4): 446-457(1988)

[LLM88]

Michael J. Litzkow, Miron Livny, Matt W. Mutka: Condor - A Hunter of Idle Workstations. ICDCS 1988: 104-111

[LNS93]

Witold Litwin, Marie-Anne Neimat, Donovan A. Schneider: LH* - Linear Hashing for Distributed Files. SIGMOD Conference 1993: 327-336

[MS91]

Gabriel Matsliach, Oded Shmueli: An Efficient Method for Distributing Search Structures. PDIS 1991: 159-166

[RS84]

Kotagiri Ramamohanarao, Ron Sacks-Davis: Recursive Linear Hashing. ACM Trans. Database Syst. 9(3): 369-391(1984)

[SPW90]

Charles Severance, Sakti Pramanik, P. Wolberg: Distributed Linear Hashing and Parallel Projection in Main Memory Databases. VLDB 1990: 674-682

[Sch92]

...

[WDJ91]

Christopher B. Walton, Alfred G. Dale, Roy M. Jenevein: A Taxonomy and Performance Model of Data Skew Effects in Parallel Joins. VLDB 1991: 537-548

[WJ92]

Ouri Wolfson, Sushil Jajodia: Distributed Algorithms for Dynamic Replication of Data. PODS 1992: 149-163

[WSZ91]

Gerhard Weikum, Peter Zabback, Peter Scheuermann: Dynamic File Allocation in Disk Arrays. SIGMOD Conference 1991: 406-415