Design of optimal distributed file systems: a framework for research

ABSTRACT

In this paper, the problem of determining an optimal location strategy for an individual program execution is considered. In addition, we propose a heuristic approach for the dynamic file allocation problem. In order to reduce the complexity of the optimization problems, a cluster-based approach is used.To access the data files of a distributed file system, a user initiates a program execution. Based on the current allocation of the program and data files as well as the knowledge about the characteristics of the programs, a first optimization calculates the optimal cluster for each individual program execution. The objective of this optimization is the minimization of the intercluster traffic of an individual program execution. Within the optimal cluster, a simple load-balancing strategy is used to determine the corresponding executing node.A second optimization looks for file allocations where the global intercluster traffic is minimized subject to the following constraints: minimal number of file copies, availability, and storage capacity.Experimental results showing the efficiency of the proposed algorithms are examined, and the implications of the model for the design of very large distributed file systems are discussed.

REFERENCES

• 1: [1] Adam, N.R., Tewari, R.: Regeneration with Virtual Copies for Replicated Databases. Proc. 11th IEEE Int. Conf. on Distributed Computing Systems, Arlington, TX, May 1991. Los Alamitos, CA: IEEE Comp. Soc. Press, pp. 429-436.
• 2: [2] Akoka, J.: Design of Optimal Distributed Database Systems. Proc. 1st Int. Symp. on Distributed Data Base, Paris, France, 1980, pp. 229-245.
• 3: [3] Banawan, S.A.: An Evaluation of Load Sharing in Locally Distributed Systems. Dept. of Computer Science, Univ. of Washington, Seattle, WA, Technical Report 87-08-02, Aug. 1987.
• 4: Daniel Barbara , Hector Garcia-Molina , Annemarie Spauster, Increasing availability under mutual exclusion constraints with dynamic vote reassignment, ACM Transactions on Computer Systems (TOCS), v.7 n.4, p.394-426, Nov. 1989 [doi>10.1145/75104.75107]
• 5: Joshua J. Bloch , Dean S. Daniels , Alfred Z. Spector, A weighted voting algorithm for replicated directories, Journal of the ACM (JACM), v.34 n.4, p.859-909, Oct. 1987 [doi>10.1145/31846.31847]
• 6: Uwe M. Borghoff, A Priority-Driven, Consistency-Preserving Strategy for the Relocation Problem of Replicated Files, Architektur von Rechensystemen, Tagungsband, 11. ITG/GI-Fachtagung, p.365-375, March 07-09, 1990
• 7: Uwe M. Borghoff, Voting and relocation strategies preserving consistency among replicated files, Proceedings of the third international conference on database theory on Database theory, p.318-332, November 1990, Paris, France
• 8: Uwe M. Borghoff, Catalogue of Distributed File-Operating Systems, Springer-Verlag New York, Inc., Secaucus, NJ, 1991
• 9: [9] Borghoff, U.M.: Fehlertoleranz in verteilten Dateisystemen: Eine Übersicht über den heutigen Entwicklungsstand bei den Votierungsverfahren. Informatik-Spektrum 14:1, 15-27 (Feb. 1991).
• 10: [10] Carroll, J.L., Long, D.D.E., Pâris, J.-F.: Block-level Consistency of Replicated Files. Proc. 7th IEEE Int. Conf. on Distributed Computing Systems, Berlin, Germany, Sep. 1987. Los Alamitos, CA: IEEE Comp. Soc. Press, pp. 146-153.
• 11: [11] Casey, R.G.: Allocation of Copies of a File in an Information Network. Proc. Spring Joint Computer Conf. 40, 1972. Arlington, VA: AFIPS Press, pp. 617-625.
• 12: [12] Ceri, S., Martella, G., Pelagatti, G.: Optimal File Allocation in a Computer Network: A Solution Based on the Knapsack Problem. Computer Networks, pp. 345-357 (1982).
• 13: [13] Chen, P.P.S., Akoka, J.: Optimal Design of Distributed Information Systems. IEEE Transactions on Computers c-20:12, 1068-1080 (Dec. 1980).
• 14: [14] Chu, W.W.: Optimal File Allocation in a Multiple Computer System. IEEE Transactions on Computers c-18:10, 885-889 (Oct. 1969).
• 15: [15] Chu, W.W.: Optimal File Allocation in a Computer Network. In: Abramson, N., Kuo, F.F. (eds.): Computer Communication Systems, 1973. Englewood Cliffs, NJ: Prentice-Hall, pp. 82-84.
• 16: [16] Coffman, E.G., Gelenbe, E., Plateau, B.: Optimization of the Number of Copies of Files in a Distributed Database. IEEE Transactions on Software Engineering SE-7:1, 78-84 (Jan. 1981).
• 17: Dančo Davčev , Walter A. Burkhard, Consistency and recovery control for replicated files, Proceedings of the tenth ACM symposium on Operating systems principles, p.87-96, December 1985, Orcas Island, Washington, United States
• 18: Susan B. Davidson , Hector Garcia-Molina , Dale Skeen, Consistency in a partitioned network: a survey, ACM Computing Surveys (CSUR), v.17 n.3, p.341-370, Sept. 1985 [doi>10.1145/5505.5508]
• 19: Susan B. Davidson, Optimism and consistency in partitioned distributed database systems, ACM Transactions on Database Systems (TODS), v.9 n.3, p.456-481, Sept. 1984 [doi>10.1145/1270.1499]
• 20: Lawrence W. Dowdy , Derrell V. Foster, Comparative Models of the File Assignment Problem, ACM Computing Surveys (CSUR), v.14 n.2, p.287-313, June 1982 [doi>10.1145/356876.356883]
• 21: 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
• 22: [22] Eswaran, K.P.: Placement of Records in a File and File Allocation in a Computer Network. Proc. IFIP Conf. Information Processing 74, Stockholm, Schweden, Aug. 1974. Amsterdam, New York: North-Holland, pp. 304-307.
• 23: [23] Garcia-Molina, H., Abbott, R.K.: Reliable Distributed Database Management. Proc. IEEE 75:5, 601-620 (May 1987).
• 24: Hector Garcia-Molina , Daniel Barbara, How to assign votes in a distributed system, Journal of the ACM (JACM), v.32 n.4, p.841-860, Oct. 1985 [doi>10.1145/4221.4223]
• 25: B. Gavish, Optimization models for configuring distributed computer systems, IEEE Transactions on Computers, v.36 n.7, p.773-793, July 1987 [doi>10.1109/TC.1987.1676975]
• 26: Bezalel Gavish , Hasan Pirkul, Computer and Database Location in Distributed Computer Systems, IEEE Transactions on Computers, v.35 n.7, p.583-590, July 1986 [doi>10.1109/TC.1986.1676799]
• 27: Erol Gelenbe , David Finkel , Satish K. Tripathi, On the availability of a distributed computer system with failing components, Proceedings of the 1985 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.6-13, August 1985, Austin, Texas, United States
• 28: [28] Gerbessiotis, A.B., Kollias, J.G.: Towards an Optimal Allocation of Fragments of Relations. In: Speth, R. (ed.): Proc. EUTECO '88 - Research into Networks and Distributed Applications, Vienna, Austria, Apr. 1988. Amsterdam, New York: North-Holland.
• 29: David K. Gifford, Weighted voting for replicated data, Proceedings of the seventh ACM symposium on Operating systems principles, p.150-162, December 10-12, 1979, Pacific Grove, California, United States [doi>10.1145/800215.806583]
• 30: Enrique Grapa , Geneva G. Belford, Some theorems to aid in solving the file allocation problem, Communications of the ACM, v.20 n.11, p.878-882, Nov. 1977 [doi>10.1145/359863.359895]
• 31: Anna Hac, A Distributed Algorithm for Performance Improvement Through File Replication, File Migration, and Process Migration, IEEE Transactions on Software Engineering, v.15 n.11, p.1459-1470, November 1989 [doi>10.1109/32.41337]
• 32: [32] Hac, A., Jin, X.: Dynamic Load Balancing in a Distributed System Using a Decentralized Algorithm. Proc. 7th IEEE Int. Conf. on Distributed Computing Systems, Berlin, Germany, Sep. 1987. Los Alamitos, CA: IEEE Comp. Soc. Press, pp. 170-177.
• 33: Anna Hac , Xiaowei Jin , Jo-Han Soo, Algorithms for file replication in a distributed system, Journal of Systems and Software, v.14 n.3, p.173-181, March 1991 [doi>10.1016/0164-1212(91)90064-D]
• 34: [34] Hac, A., Johnson, T.J.: Dynamic Load Balancing Through Process and Read-Site Placement in a Distributed System. AT & T Bell Techn. Journal, pp. 72-85 (Oct. 1988).
• 35: Maurice Herlihy, A quorum-consensus replication method for abstract data types, ACM Transactions on Computer Systems (TOCS), v.4 n.1, p.32-53, Feb. 1986 [doi>10.1145/6306.6308]
• 36: [36] Jacqmot, C., Milgrom, E., Joosen, W., Berbers, Y.: UNIX and Load Balancing: A Survey. Proc. Europ. UNIX Systems User Group Conf. Spring '89, Brussels, Belgium, Apr. 1989. Buntingford Herts, UK: EUUG, pp. 1-15.
• 37: Sushil Jajodia, Managing Replicated Files in Partitioned Distributed Database Systems, Proceedings of the Third International Conference on Data Engineering, p.412-418, February 03-05, 1987
• 38: Sushil Jajodia , David Mutchler, Enhancements to the Voting Algorithm, Proceedings of the 13th International Conference on Very Large Data Bases, p.399-406, September 01-04, 1987
• 39: [39] Kurose, J.F., Simha, R.: A Microeconomic Approach to Optimal File Allocation. Proc. 6th IEEE Int. Conf. on Distributed Computing Systems, Cambridge, MA, May 1986. Los Alamitos, CA: IEEE Comp. Soc. Press, pp. 28-35.
• 40: [40] Kurose, J.F., Simha, R.: Second Derivative Algorithms for Optimal Resource Allocation in Distributed Computer Systems. Proc. 7th IEEE Int. Conf. on Distributed Computing Systems, Berlin, Germany, Sep. 1987. Los Alamitos, CA: IEEE Comp. Soc, Press, pp. 56-63.
• 41: [41] Laning, L.J., Leonard, M.S.: File Allocation in a Distributed Computer Communication Network. IEEE Transactions on Computers c-32:3, 232-244 (Mar. 1983).
• 42: [42] Levin, K.D., Morgan, H.L.: Optimizing Distributed Data Bases - A Framework for Research. Proc. AFIPS Nat. Computer Conf. 44, 1975. Arlington, VA: AFIPS Press, pp. 473-478.
• 43: [43] Litzkow, M.J., Livny, M., Mutka, M.W.: Condor - A Hunter of Idle Workstations. Proc. 8th IEEE Int. Conf. on Distributed Computing Systems, San Jose, CA, Jun. 1988. Los Alamitos, CA: IEEE Comp. Soc. Press, pp. 104-111.
• 44: [44] Long, D.D.E.: The Management of Replication in a Distributed System. Dept. of Computer and Information Science, Univ. of California, Santa Cruz, CA, Technical Report UCSC/CRL 88/07, 1988.
• 45: Samy Mahmoud , J. S. Riordon, Optimal allocation of resources in distributed information networks, ACM Transactions on Database Systems (TODS), v.1 n.1, p.66-78, March 1976 [doi>10.1145/320434.320449]
• 46: Howard L. Morgan , K. Dan Levin, Optimal program and data locations in computer networks, Communications of the ACM, v.20 n.5, p.315-322, May 1977 [doi>10.1145/359581.359591]
• 47: Jehan-François Pâris , Darrell D. E. Long, Efficient Dynamic Voting Algorithms, Proceedings of the Fourth International Conference on Data Engineering, p.268-275, February 01-05, 1988
• 48: [48] Pattipati, K.R., Wolf, J.L.: A File Assignment Problem Model for Extended Local Area Network Environments. Proc. 10th IEEE Int. Conf. on Distributed Computing Systems, Paris, France, May 1990. Los Alamitos, CA: IEEE Comp. Soc. Press, pp. 554-561.
• 49: [49] Pirkul, H.: An Integer Programming Model for the Allocation of Databases in a Distributed Computer System. Europ. Journal of Operational Research 26, 401-411 (1986).
• 50: S. Ram , R. E. Marsten, A Model for Database Allocation Incorporating a Concurrency Control Mechanism, IEEE Transactions on Knowledge and Data Engineering, v.3 n.3, p.389-395, September 1991 [doi>10.1109/69.91051]
• 51: [51] Ramamoorthy, C.V., Wah, B.W.: The Isomorphism of Simple File Allocation. IEEE Transactions on Computers c-32:3, 221-232 (Mar. 1983).
• 52: [52] Ramesh, R., Ryan, B.: Optimal File Allocation and Report Assignment in Distributed Information Networks. Naval Research Logistics 37:1, 165-181 (Feb. 1990).
• 53: G. C. Shoja, A distributed facility for load sharing and parallel processing among workstations, Journal of Systems and Software, v.14 n.3, p.163-172, March 1991 [doi>10.1016/0164-1212(91)90063-C]
• 54: Ushio Sumita , Olivia R. Liu Sheng, Analysis of query processing in distributed database systems with fully replicated files: hierarchical approach, Performance Evaluation, v.8 n.3, p.223-238, June 1988 [doi>10.1016/0166-5316(88)90005-3]
• 55: Robert H. Thomas, A Majority consensus approach to concurrency control for multiple copy databases, ACM Transactions on Database Systems (TODS), v.4 n.2, p.180-209, June 1979 [doi>10.1145/320071.320076]
• 56: [56] Wah, B.W.: File Placement on Distributed Computer Systems. IEEE Computer 17:1, 23-33 (Jan. 1984).
• 57: [57] Wang, Y.-T., Morris, R.J.T.: Load Sharing in Distributed Systems. IEEE Transactions on Computers c-34:3, 204-217 (Mar. 1985).
• 58: V. Kevin Moore Whitney, A study of optimal file site assignment and communication network configuration in remote-access computer message processing and communication systems, University of Michigan, Ann Arbor, MI, 1970
• 59: C. Murray Woodside , Satish K. Tripathi, Optimal allocation of file servers in a local network environment, IEEE Transactions on Software Engineering, v.12 n.8, p.844-848, Aug. 1986

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.3 File Systems Management
          Subjects: Distributed file systems

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Allocation/deallocation strategies
      D.4.7 Organization and Design
          Subjects: Distributed systems

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

General Terms:
Algorithms, Design, Performance