Distributed file organization with scalable cost/performance

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 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.

REFERENCES

• BS85: Amnon Barak , Amnon Shiloh, A distributed load-balancing policy for a multicomputer, Software—Practice & Experience, v.15 n.9, p.901-913, Sept. 1985 [doi>10.1002/spe.4380150905]
• CS92: Donald D. Chamberlin , Frank B. Schmuck, Dynamic Data Distribution (D3) in a Shared-Nothing Multiprocessor Data Store, Proceedings of the 18th International Conference on Very Large Data Bases, p.163-174, August 23-27, 1992
• Dev93: Robert Devine, Design and Implementation of DDH: A Distributed Dynamic Hashing Algorithm, Proceedings of the 4th International Conference on Foundations of Data Organization and Algorithms, p.101-114, October 13-15, 1993
• DG92: David DeWitt , Jim Gray, Parallel database systems: the future of high performance database systems, Communications of the ACM, v.35 n.6, p.85-98, June 1992 [doi>10.1145/129888.129894]
• ED88: R. J. Enbody , H. C. Du, Dynamic hashing schemes, ACM Computing Surveys (CSUR), v.20 n.2, p.850-113, June 1988 [doi>10.1145/46157.330532]
• ELZ86: Derek L. Eager , Edward D. Lazowska , John Zahorjan, Adaptive load sharing in homogeneous distributed systems, IEEE Transactions on Software Engineering, v.12 n.5, p.662-675, May 1986
• FNPS79: Ronald Fagin , Jurg Nievergelt , Nicholas Pippenger , H. Raymond Strong, Extendible hashing—a fast access method for dynamic files, ACM Transactions on Database Systems (TODS), v.4 n.3, p.315-344, Sept. 1979 [doi>10.1145/320083.320092]
• Gr91: Jim Gray, Benchmark Handbook: For Database and Transaction Processing Systems, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1992
• HW94: Yixiu Huang , Ouri Wolfson, Object Allocation in Distributed Databases and Mobile Computers, Proceedings of the Tenth International Conference on Data Engineering, p.20-29, February 14-18, 1994
• JK93: Theodore Johnson , Padmashree Krishna, Lazy updates for distributed search structure, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.337-346, May 25-28, 1993, Washington, D.C., United States
• Lar88: Per-Ake Larson, Dynamic hash tables, Communications of the ACM, v.31 n.4, p.446-457, April 1988 [doi>10.1145/42404.42410]
• LLM88: M.J. Litzkow, M. Livny, M.W. Mutka, Condor- A Hunter of Idle Workstations, 8th International Conference on Distributed Computing Systems (DCS), San Jose, 1988.
• LNS93: Witold Litwin , Marie-Anne Neimat , Donovan A. Schneider, LH: Linear Hashing for distributed files, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.327-336, May 25-28, 1993, Washington, D.C., United States
• MS91: Gabriel Matsliach , Oded Shmueli, An efficient method for distributing search structures, Proceedings of the first international conference on Parallel and distributed information systems, p.159-167, December 1991, Miami, Florida, United States
• RS84: K Ramamohanarao , R Sacks-Davis, Recursive linear hashing, ACM Transactions on Database Systems (TODS), v.9 n.3, p.369-391, Sept. 1984 [doi>10.1145/1270.1285]
• SPW90: C. Severance , S. Pramanik , P. Wolberg, Distributed linear hashing and parallel projection in main memory databases, Proceedings of the sixteenth international conference on Very large databases, p.674-682, September 1990, Brisbane, Australia
• Sch92: H. Schwetman, CSIM Reference Manual (Revision 16), Microelectronics and Computer Technology Corporation, Austin, 1992.
• WDJ91: Christopher B. Walton , Alfred G. Dale , Roy M. Jenevein, A Taxonomy and Performance Model of Data Skew Effects in Parallel Joins, Proceedings of the 17th International Conference on Very Large Data Bases, p.537-548, September 03-06, 1991
• WJ92: Ouri Wolfson , Sushil Jajodia, Distributed algorithms for dynamic replication of data, Proceedings of the eleventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.149-163, June 02-05, 1992, San Diego, California, United States [doi>10.1145/137097.137858]
• WSZ91: Gerhard Weikum , Peter Zabback , Peter Scheuermann, Dynamic file allocation in disk arrays, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.406-415, May 29-31, 1991, Denver, Colorado, United States

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Distributed databases

Additional Classification:
  E. Data
  E.2 DATA STORAGE REPRESENTATIONS
      Subjects: Hash-table representations
  E.5 FILES
      Subjects: Organization/structure

General Terms:
Algorithms, Experimentation, Performance