A model for characterizing the scalability of distributed systems

ABSTRACT

Scalability is an important issue in the construction of distributed systems. A number of theoretical and experimental studies have been made on scalability of distributed systems. However, they have been either studies on specific technologies or have studied scalability in isolation. The main conjecture of our work is that scalability must be perceived along with the related issues of availability, synchronization and consistency. In this context, we propose a scalability model which characterizes scalability as being dependent on these factors as well as the workload and faultload. The model is generic and can be used to compare scalability of similar systems. We illustrate this by a comparison between NFS and AFS, two well known distributed file systems. The model is also useful in identifying scalability bottlenecks in distributed systems. We have applied the model to optimize Virat, a wide-area shared object space that we have built.

REFERENCES

• 1: Sanjay Ghemawat , Howard Gobioff , Shun-Tak Leung, The Google file system, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
• 2: Mahadev Satyanarayanan, The Influence of Scale on Distributed File System Design, IEEE Transactions on Software Engineering, v.18 n.1, p.1-8, January 1992 [doi>10.1109/32.120311]
• 3: Maarten van Steen , Philip Homburg , Andrew S. Tanenbaum, Globe: A Wide-Area Distributed System, IEEE Concurrency, v.7 n.1, p.70-78, January 1999 [doi>10.1109/4434.749137]
• 4: Robbert Van Renesse , Kenneth P. Birman , Werner Vogels, Astrolabe: A robust and scalable technology for distributed system monitoring, management, and data mining, ACM Transactions on Computer Systems (TOCS), v.21 n.2, p.164-206, May 2003 [doi>10.1145/762483.762485]
• 5: Prasad Jogalekar , Murray Woodside, Evaluating the Scalability of Distributed Systems, IEEE Transactions on Parallel and Distributed Systems, v.11 n.6, p.589-603, June 2000 [doi>10.1109/71.862209]
• 6: J. A. Rolia , K. C. Sevcik, The Method of Layers, IEEE Transactions on Software Engineering, v.21 n.8, p.689-700, August 1995 [doi>10.1109/32.403785]
• 7: J. E. Neilson , C. M. Woodside , D. C. Petriu , S. Majumdar, Software Bottlenecking in Client-Server Systems and Rendezvous Networks, IEEE Transactions on Software Engineering, v.21 n.9, p.776-782, September 1995 [doi>10.1109/32.464543]
• 8: Douglas C. Schmidt , Hans Rohnert , Michael Stal , Dieter Schultz, Pattern-Oriented Software Architecture: Patterns for Concurrent and Networked Objects, John Wiley & Sons, Inc., New York, NY, 2000
• 9: Paul Brebner , Jeffrey Gosper, How scalable is J2EE technology?, ACM SIGSOFT Software Engineering Notes, v.28 n.3, May 2003 [doi>10.1145/773126.773139]
• 10: Seth Gilbert , Nancy Lynch, Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web services, ACM SIGACT News, v.33 n.2, June 2002 [doi>10.1145/564585.564601]
• 11: Haifeng Yu , Amin Vahdat, The costs and limits of availability for replicated services, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 12: Florin Sultan , Thu D. Nguyen , Liviu Iftode, Lazy Garbage Collection of Recovery State for Fault-Tolerant Distributed Shared Memory, IEEE Transactions on Parallel and Distributed Systems, v.13 n.10, p.1085-1098, October 2002 [doi>10.1109/TPDS.2002.1041885]
• 13: Nicholas Carriero , David Gelernter, Linda in context, Communications of the ACM, v.32 n.4, p.444-458, April 1989 [doi>10.1145/63334.63337]
• 14: Michael Stumm , Songnian Zhou, Algorithms Implementing Distributed Shared Memory, Computer, v.23 n.5, p.54-64, May 1990 [doi>10.1109/2.53355]
• 15: A Vijay Srinivas, D Janakiram, and Raghevendra Koti. Virat: An Internet Scale Distributed Shared Object, Event and Service Space. Technical Report IITM-CSE-DOS-2004-03, Distributed & Object Systems Lab, Indian Institute of Technology, Madras, 2004.
• 16: A Vijay Srinivas, Raghavendra Koti, A Uday Kumar, and D Janakiram. Realizing Large Scale Distributed Event Style Interactions. In Proceedings of the European Conference on Object Oriented Programming (ECOOP) Workshop on Communication Abstractions for Distributed Systems. Oslo, Norway, 2004.
• 17: Chi Zhang , Zheng Zhang, Trading Replication Consistency for Performance and Availability: an Adaptive Approach, Proceedings of the 23rd International Conference on Distributed Computing Systems, p.687, May 19-22, 2003
• 18: Mustaque Ahamad , Rammohan Kordale, Scalable Consistency Protocols for Distributed Services, IEEE Transactions on Parallel and Distributed Systems, v.10 n.9, p.888-903, September 1999 [doi>10.1109/71.798314]
• 19: R. Sandberg, D. Goldberg, S. Kleiman, D. Walsh, and B. Lyon. Design and Implementation of the Sun Network Filesystem. In USENIX Association Summer Conference, Portland, USA, 1985.
• 20: Mahadev Satyanarayanan, The Influence of Scale on Distributed File System Design, IEEE Transactions on Software Engineering, v.18 n.1, p.1-8, January 1992 [doi>10.1109/32.120311]
• 21: Mirjana Spasojevic , M. Satyanarayanan, An empirical study of a wide-area distributed file system, ACM Transactions on Computer Systems (TOCS), v.14 n.2, p.200-222, May 1996 [doi>10.1145/227695.227698]

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.8 Performance
          Subjects: Modeling and prediction

Additional Classification:
  C. Computer Systems Organization
  C.0 GENERAL
      Subjects: Modeling of computer architecture
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed applications

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.3 File Systems Management
          Subjects: Distributed file systems; File organization
      D.4.7 Organization and Design
          Subjects: Distributed systems
      D.4.8 Performance
          Subjects: Operational analysis

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.5 Model Development

General Terms:
Performance