Handling Heterogeneity in Shared-Disk File Systems

ABSTRACT

We develop and evaluate a system for load management in shared-disk file systems built on clusters of heterogeneous computers. The system generalizes load balancing and server provisioning. It balances file metadata workload by moving file sets among cluster server nodes. It also responds to changing server resources that arise from failure and recovery and dynamically adding or removing servers. The system is adaptive and self-managing. It operates without any a-priori knowledge of workload properties or the capabilities of the servers. Rather, it continuously tunes load placement using a technique called adaptive, non-uniform (ANU) randomization. ANU randomization realizes the scalability and metadata reduction benefits of hash-based, randomized placement techniques. It also avoids hashing's drawbacks: load skew, inability to cope with heterogeneity, and lack of tunability. Simulation results show that our load-management algorithm performs comparably to a prescient algorithm.

REFERENCES

• 1: Khalil Amiri , David Petrou , Gregory R. Ganger , Garth A. Gibson, Dynamic function placement for data-intensive cluster computing, Proceedings of the Annual Technical Conference on 2000 USENIX Annual Technical Conference, p.25-25, June 18-23, 2000, San Diego, California
• 2: Darrell C. Anderson , Jeffery S. Chase , Amin M. Vahdat, Interposed request routing for scalable network storage, Proceedings of the 4th conference on Symposium on Operating System Design & Implementation, p.18-18, October 22-25, 2000, San Diego, California
• 3: [3] L. Aversa and A. Bestavros. Load balancing a cluster of web servers using distributed packet rewriting. In Proceedings of the IEEE International Performance, Computing, and Communications Conference, 2000.
• 4: Amnon Barak , Shai Guday , Richard G. Wheeler, The MOSIX Distributed Operating System: Load Balancing for UNIX, Springer-Verlag New York, Inc., Secaucus, NJ, 1993
• 5: [5] G. Bell and J. Gray. High Performance Computing: Crays, Clusters and Centers. What Next? Technical Report MSR-TR- 2001-76, Microsoft Research, 2001.
• 6: [6] P. J. Braam. The Lustre storage architecture. Technical Report available at - http://www.lustre.org/docs.html, Lustre, 2002.
• 7: André Brinkmann , Kay Salzwedel , Christian Scheideler, Compact, adaptive placement schemes for non-uniform requirements, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, August 10-13, 2002, Winnipeg, Manitoba, Canada [doi>10.1145/564870.564878]
• 8: Randal Chilton Burns , Darrell D. Long, Data management in a distributed file system for storage area networks, University of California, Santa Cruz, 2000
• 9: Valeria Cardellini , Michele Colajanni , Philip S. Yu, Geographic Load Balancing for Scalable Distributed Web Systems, Proceedings of the 8th International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems, p.20, August 29-September 01, 2000
• 10: 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
• 11: [11] G. R. Ganger, B. L. Worthington, R. Y. Hou, and Y. N. Patt. Disk subsystem load balancing: Disk striping vs. conventional data placement. In Proceedings of the International Conference on System Sciences, 1993.
• 12: Mor Harchol-Balter , Allen B. Downey, Exploiting process lifetime distributions for dynamic load balancing, ACM Transactions on Computer Systems (TOCS), v.15 n.3, p.253-285, Aug. 1997 [doi>10.1145/263326.263344]
• 13: John H. Howard , Michael L. Kazar , Sherri G. Menees , David A. Nichols , M. Satyanarayanan , Robert N. Sidebotham , Michael J. West, Scale and performance in a distributed file system, ACM Transactions on Computer Systems (TOCS), v.6 n.1, p.51-81, Feb. 1988 [doi>10.1145/35037.35059]
• 14: [14] J. R. Jump. YACSIM reference manual. Rice University, version 2.1.1 edition, 1993.
• 15: Eric Dean Katz , Michelle Butler , Robert McGrath, A scalable HTTP server: the NCSA prototype, Computer Networks and ISDN Systems, v.27 n.2, p.155-164, Nov. 1994
• 16: [16] K. Li and J. Dorband. A task scheduling algorithm for heterogeneous processing. In Proceedings of the Symposium on High Performance Computing, 1997.
• 17: Witold Litwin , Marie-Anna Neimat , Donovan A. Schneider, LH*—a scalable, distributed data structure, ACM Transactions on Database Systems (TODS), v.21 n.4, p.480-525, Dec. 1996 [doi>10.1145/236711.236713]
• 18: An adaptive load balancing algorithm for heterogeneous distributed systems with multiple task classes, Proceedings of the 16th International Conference on Distributed Computing Systems (ICDCS '96), p.629, May 27-30, 1996
• 19: Manish Mehta , David J. DeWitt, Data placement in shared-nothing parallel database systems, The VLDB Journal — The International Journal on Very Large Data Bases, v.6 n.1, p.53-72, February 1997 [doi>10.1007/s007780050033]
• 20: J. Menon , D. A. Pease , R. Rees , L. Duyanovich , B. Hillsberg, IBM Storage Tank-- A heterogeneous scalable SAN file system, IBM Systems Journal, v.42 n.2, p.250-267, April 2003
• 21: Michael Mitzenmacher, On the analysis of randomized load balancing schemes, Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, p.292-301, June 23-25, 1997, Newport, Rhode Island, United States [doi>10.1145/258492.258521]
• 22: Michael Mitzenmacher, How Useful Is Old Information?, IEEE Transactions on Parallel and Distributed Systems, v.11 n.1, p.6-20, January 2000 [doi>10.1109/71.824633]
• 23: Michael Mitzenmacher, The Power of Two Choices in Randomized Load Balancing, IEEE Transactions on Parallel and Distributed Systems, v.12 n.10, p.1094-1104, October 2001 [doi>10.1109/71.963420]
• 24: L. Mummert , M. Satyanarayanan, Long term distributed file reference tracing: implementation and experience, Software—Practice & Experience, v.26 n.6, p.705-736, June 1996 [doi>10.1002/(SICI)1097-024X(199606)26:6<705::AID-SPE29>3.3.CO;2-F]
• 25: S. Petri , H. Langendörfer, Load balancing and fault tolerance in workstation clusters migrating groups of communicating processes, ACM SIGOPS Operating Systems Review, v.29 n.4, p.25-36, Oct. 1995 [doi>10.1145/219282.219288]
• 26: [26] K. W. Preslan, A. P. Barry, J. E. Brassow, G. M. Erickson, E. Nygaard, C. J. Sabol, S. R. Soltis, D. C. Teigland, and M. T. O'Keefe. A 64-bit, shared disk file system for Linux. In Proceedings of the IEEE Mass Storage Systems Symposium, 1999.
• 27: Antony I. T. Rowstron , Peter Druschel, Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems, Proceedings of the IFIP/ACM International Conference on Distributed Systems Platforms Heidelberg, p.329-350, November 12-16, 2001
• 28: Yasushi Saito , Brian N. Bershad , Henry M. Levy, Manageability, availability and performance in Porcupine: a highly scalable, cluster-based mail service, Proceedings of the seventeenth ACM symposium on Operating systems principles, p.1-15, December 12-15, 1999, Charleston, South Carolina, United States
• 29: Mahadev Satyanarayanan , James J. Kistler , Puneet Kumar , Maria E. Okasaki , Ellen H. Siegel , David C. Steere, Coda: A Highly Available File System for a Distributed Workstation Environment, IEEE Transactions on Computers, v.39 n.4, p.447-459, April 1990 [doi>10.1109/12.54838]
• 30: Frank B. Schmuck , Roger L. Haskin, GPFS: A Shared-Disk File System for Large Computing Clusters, Proceedings of the Conference on File and Storage Technologies, p.231-244, January 28-30, 2002
• 31: [31] P. Shenoy and H. Vin. Efficient striping techniques for multimedia file servers. In Proceedings of the International Workshop on Network and Operating System Support for Digital Audio and Video, 1997.
• 32: Shweta Sinha , Manish Parashar, Adaptive Runtime Partitioning of AMR Applications on Heterogeneous Clusters, Proceedings of the 3rd IEEE International Conference on Cluster Computing, p.435, October 08-11, 2001
• 33: Ion Stoica , Robert Morris , David Karger , M. Frans Kaashoek , Hari Balakrishnan, Chord: A scalable peer-to-peer lookup service for internet applications, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.149-160, August 2001, San Diego, California, United States
• 34: Chandramohan A. Thekkath , Timothy Mann , Edward K. Lee, Frangipani: a scalable distributed file system, Proceedings of the sixteenth ACM symposium on Operating systems principles, p.224-237, October 05-08, 1997, Saint Malo, France
• 35: [35] D. Walsh, B. Lyon, G. Sager, J. Chang, D. Goldberg, S. Kleiman, T. Lyon, R. Sandberg, and P. Weiss. Overview of the Sun network file system. In Proceedings of the 1985 Winter Usenix Technical Conference, January 1985.
• 36: [36] J. Watts, M. Rieffel, and S. Taylor. Dynamic management of heterogenous resources. In Proceeding of the High Performance Computing Conference: Grand Challenges in Computer Simulation, 1998.
• 37: Jerrell Watts , Stephen Taylor, A Practical Approach to Dynamic Load Balancing, IEEE Transactions on Parallel and Distributed Systems, v.9 n.3, p.235-248, March 1998 [doi>10.1109/71.674316]
• 38: M. H. Willebeek-LeMair , A. P. Reeves, Strategies for Dynamic Load Balancing on Highly Parallel Computers, IEEE Transactions on Parallel and Distributed Systems, v.4 n.9, p.979-993, September 1993 [doi>10.1109/71.243526]
• 39: Chengzhong Xu , Francis C. Lau, Load Balancing in Parallel Computers: Theory and Practice, Kluwer Academic Publishers, Norwell, MA, 1997
• 40: S. Zhou, A Trace-Driven Simulation Study of Dynamic Load Balancing, IEEE Transactions on Software Engineering, v.14 n.9, p.1327-1341, September 1988 [doi>10.1109/32.6176]
• 41: Songnian Zhou , Xiaohu Zheng , Jingwen Wang , Pierre Delisle, Utopia: a load sharing facility for large, heterogeneous distributed computer systems, Software—Practice & Experience, v.23 n.12, p.1305-1336, Dec. 1993 [doi>10.1002/spe.4380231203]
• 42: [42] H. Zhu, T. Yang, Q. Zheng, D. Watson, O. H. Ibarra, and T. R. Smith. Adaptive load sharing for clustered digital library servers. International Journal on Digital Libraries, 2(4), 2000.