The costs and limits of availability for replicated services

ABSTRACT

As raw system and network performance continues to improve at exponential rates, the utility of many services is increasingly limited by availability rather than performance. A key approach to improving availability involves replicating the service across multiple, wide-area sites. However, replication introduces well-known tradeoffs between service consistency and availability. Thus, this paper explores the benefits of dynamically trading consistency for availability using a continuous consistency model. In this model, applications specify a maximum deviation from strong consistency on a per-replica basis. In this paper, we: i) evaluate availability of a prototype replication system running across the Internet as a function of consistency level, consistency protocol, and failure characteristics, ii) demonstrate that simple optimizations to existing consistency protocols result in significant availability improvements (more than an order of magnitude in some scenarios), iii) use our experience with these optimizations to prove tight upper bounds on the availability of services, and iv) show that maximizing availability typically entails remaining as close to strong consistency as possible during times of good connectivity, resulting in a communication versus availability trade-off.

REFERENCES

• 1: Generalized Isolation Level Definitions, Proceedings of the 16th International Conference on Data Engineering, p.67, February 28-March 03, 2000
• 2: Y. Amir , A. Wool, Evaluating quorum systems over the Internet, Proceedings of the The Twenty-Sixth Annual International Symposium on Fault-Tolerant Computing (FTCS '96), p.26, June 25-27, 1996
• 3: Mary G. Baker , John H. Hartman , Michael D. Kupfer , Ken W. Shirriff , John K. Ousterhout, Measurements of a distributed file system, Proceedings of the thirteenth ACM symposium on Operating systems principles, p.198-212, October 13-16, 1991, Pacific Grove, California, United States
• 4: Daniel Barbara , Hector Garcia-Molina, The vulnerability of vote assignments, ACM Transactions on Computer Systems (TOCS), v.4 n.3, p.187-213, Aug. 1986 [doi>10.1145/6420.6421]
• 5: Philip A. Bernstein , Vassco Hadzilacos , Nathan Goodman, Concurrency control and recovery in database systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1987
• 6: A. Brown and D. Patterson. Towards Maintainability, Availability, and Growth Benchmarks: A Case Study of Software RAID Systems. In Proceedings of the PO00 USENIX Annual Technical Conference, June 2000.
• 7: Support for Speculative Update Propagation and Mobility in Deno, Proceedings of the The 21st International Conference on Distributed Computing Systems, p.509, April 16-19, 2001
• 8: B. Chandra, M. Dahlin, L. Gao, and A. Nayate. End-to-End WAN Service Availability. In Proceedings of the 3rd Usenix Symposium on Internet Technologies and Systems, January 2001.
• 9: Brian A Coan , Brian M Oki , Elliot K Kolodner, Limitations on database availability when networks partition, Proceedings of the fifth annual ACM symposium on Principles of distributed computing, p.187-194, August 11-13, 1986, Calgary, Alberta, Canada [doi>10.1145/10590.10606]
• 10: J. Czyzyk, S. Mehrotra, M. Wagner, and S. Wright. PCx: Software for Linear Programming. Available at: http:www-fp.mcs, anl. govlotc/Tools/Pex/.
• 11: Krzysztof Diks , Evangelos Kranakis , Danny Krizanc , Bernard Mans , Andrzej Pelc, Optimal coteries and voting schemes, Information Processing Letters, v.51 n.1, p.1-6, July 12, 1994 [doi>10.1016/0020-0190(94)00064-6]
• 12: Michalis Faloutsos , Petros Faloutsos , Christos Faloutsos, On power-law relationships of the Internet topology, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.251-262, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 13: Armando Fox , Eric A. Brewer, Harvest, Yield, and Scalable Tolerant Systems, Proceedings of the The Seventh Workshop on Hot Topics in Operating Systems, p.174, March 28-30, 1999
• 14: Armando Fox , Steven D. Gribble , Yatin Chawathe , Eric A. Brewer , Paul Gauthier, Cluster-based scalable network services, Proceedings of the sixteenth ACM symposium on Operating systems principles, p.78-91, October 05-08, 1997, Saint Malo, France
• 15: 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]
• 16: R. Golding. A Weak-Consistency Architecture for Distributed Information Services. Computing Systems, 5(4):379-405, Fall 1992.
• 17: Jim Gray , Pat Helland , Patrick O'Neil , Dennis Shasha, The dangers of replication and a solution, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.173-182, June 04-06, 1996, Montreal, Quebec, Canada
• 18: John Hennessy, The Future of Systems Research, Computer, v.32 n.8, p.27-33, August 1999 [doi>10.1109/2.781631]
• 19: Donald B. Johnson , Larry Raab, A tight upper bound on the benefits of replication and consistency control protocols, Proceedings of the tenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.75-81, May 29-31, 1991, Denver, Colorado, United States [doi>10.1145/113413.113420]
• 20: Peter J. Keleher, Decentralized replicated-object protocols, Proceedings of the eighteenth annual ACM symposium on Principles of distributed computing, p.143-151, May 04-06, 1999, Atlanta, Georgia, United States [doi>10.1145/301308.301345]
• 21: James J. Kistler , M. Satyanarayanan, Disconnected operation in the Coda File System, ACM Transactions on Computer Systems (TOCS), v.10 n.1, p.3-25, Feb. 1992 [doi>10.1145/146941.146942]
• 22: Narayanan Krishnakumar , Arthur J. Bernstein, Bounded ignorance: a technique for increasing concurrency in a replicated system, ACM Transactions on Database Systems (TODS), v.19 n.4, p.586-625, Dec. 1994 [doi>10.1145/195664.195670]
• 23: Akhil Kumar , Arie Segev, Cost and availability tradeoffs in replicated data concurrency control, ACM Transactions on Database Systems (TODS), v.18 n.1, p.102-131, March 1993 [doi>10.1145/151284.151287]
• 24: Rivka Ladin , Barbara Liskov , Liuba Shrira , Sanjay Ghemawat, Providing high availability using lazy replication, ACM Transactions on Computer Systems (TOCS), v.10 n.4, p.360-391, Nov. 1992 [doi>10.1145/138873.138877]
• 25: Butler W. Lampson, How to Build a Highly Available System Using Consensus, Proceedings of the 10th International Workshop on Distributed Algorithms, p.1-17, October 09-11, 1996
• 26: Lily Barkovic Mummert , Mahadev Satyanarayanan, Exploiting weak connectivity in a distributed file system, 1996
• 27: B. Noble, B. Fleis, and M. Kim. A Case for Fluid Replication. In Proceedings of the 1999 Network Storage Symposium (Netstore), October 1999.
• 28: Brian D. Noble , M. Satyanarayanan , Giao T. Nguyen , Randy H. Katz, Trace-based mobile network emulation, Proceedings of the ACM SIGCOMM '97 conference on Applications, technologies, architectures, and protocols for computer communication, p.51-61, September 14-18, 1997, Cannes, France
• 29: T. W. Page, Jr. , R. G. Guy , J. S. Heidemann , D. H. Ratner , P. L. Reiher , A. Goel , G. H. Kuenning , G. J. Popek, Perspectives on optimistically replicated, peer-to-peer filing, Software—Practice & Experience, v.28 n.2, p.155-180, Feb. 1998 [doi>10.1002/(SICI)1097-024X(199802)28:2<155::AID-SPE155>3.0.CO;2-5]
• 30: Vern Paxson, End-to-end routing behavior in the Internet, Conference proceedings on Applications, technologies, architectures, and protocols for computer communications, p.25-38, August 28-30, 1996, Palo Alto, California, United States
• 31: Karin Petersen , Mike J. Spreitzer , Douglas B. Terry , Marvin M. Theimer , Alan J. Demers, Flexible update propagation for weakly consistent replication, Proceedings of the sixteenth ACM symposium on Operating systems principles, p.288-301, October 05-08, 1997, Saint Malo, France
• 32: Calton Pu , Avraham Leff, Replica control in distributed systems: as asynchronous approach, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.377-386, May 29-31, 1991, Denver, Colorado, United States
• 33: 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
• 34: Stefan Savage , Andy Collins , Eric Hoffman , John Snell , Thomas Anderson, The end-to-end effects of Internet path selection, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.289-299, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 35: D. B. Terry , M. M. Theimer , Karin Petersen , A. J. Demers , M. J. Spreitzer , C. H. Hauser, Managing update conflicts in Bayou, a weakly connected replicated storage system, Proceedings of the fifteenth ACM symposium on Operating systems principles, p.172-182, December 03-06, 1995, Copper Mountain, Colorado, United States
• 36: H. Yu and A. Vahdat. Design and Evaluation of a Continuous Consistency Model for Replicated Services. In Proceedings of Operating Systems Design and Implementation (OSDI), October 2000.
• 37: Haifeng Yu , Amin Vahdat, Efficient Numerical Error Bounding for Replicated Network Services, Proceedings of the 26th International Conference on Very Large Data Bases, p.123-133, September 10-14, 2000
• 38: Combining Generality and Practicality in a Conit-Based Continuous Consistency Model for Wide-Area Replication, Proceedings of the The 21st International Conference on Distributed Computing Systems, p.429, April 16-19, 2001
• 39: H. Yu and A. Vahdat. The Costs and Limits of Availability for Replicated Services. Technical Report CS-2001-03, Duke University, July 2001. Available from http://www.cs.duke.edu/vahdat/ps/tr-cs-2001-03.pdf.
• 40: Ellen W. Zegura , Kenneth L. Calvert , Michael J. Donahoo, A quantitative comparison of graph-based models for Internet topology, IEEE/ACM Transactions on Networking (TON), v.5 n.6, p.770-783, Dec. 1997 [doi>10.1109/90.650138]

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.4 Communications Management
          Subjects: Network communication

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.8 Performance

General Terms:
Performance