Paxos made live: an engineering perspective

ABSTRACT

We describe our experience in building a fault-tolerant data-base using the Paxos consensus algorithm. Despite the existing literature in the field, building such a database proved to be non-trivial. We describe selected algorithmic and engineering problems encountered, and the solutions we found for them. Our measurements indicate that we have built a competitive system.

REFERENCES

• 1: Mike Burrows, The Chubby lock service for loosely-coupled distributed systems, Proceedings of the 7th symposium on Operating systems design and implementation, November 06-08, 2006, Seattle, Washington
• 2: Fay Chang , Jeffrey Dean , Sanjay Ghemawat , Wilson C. Hsieh , Deborah A. Wallach , Mike Burrows , Tushar Chandra , Andrew Fikes , Robert E. Gruber, Bigtable: a distributed storage system for structured data, Proceedings of the 7th symposium on Operating systems design and implementation, November 06-08, 2006, Seattle, Washington
• 3: Cristian, F. Reaching agreement on processor-group membership in synchronous distributed systems. Distributed Computing 4, 4 (1991), 175--188.
• 4: 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
• 5: C. Gray , D. Cheriton, Leases: an efficient fault-tolerant mechanism for distributed file cache consistency, Proceedings of the twelfth ACM symposium on Operating systems principles, p.202-210, November 1989
• 6: Johnson, S. C. Yacc: Yet another compiler-compiler.
• 7: Lamport, Shostak, and Pease. The byzantine generals problem. In Advances in Ultra-Dependable Distributed Systems, N. Suri, C. J. Walter, and M. M. Hugue (Eds.), IEEE Computer Society Press. 1995.
• 8: Leslie Lamport, The part-time parliament, ACM Transactions on Computer Systems (TOCS), v.16 n.2, p.133-169, May 1998 [doi>10.1145/279227.279229]
• 9: Lamport, L. Paxos made simple. ACM SIGACT News 32, 4 (Dec. 2001), 18--25.
• 10: 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
• 11: Edward K. Lee , Chandramohan A. Thekkath, Petal: distributed virtual disks, Proceedings of the seventh international conference on Architectural support for programming languages and operating systems, p.84-92, October 01-04, 1996, Cambridge, Massachusetts, United States
• 12: John MacCormick , Nick Murphy , Marc Najork , Chandramohan A. Thekkath , Lidong Zhou, Boxwood: abstractions as the foundation for storage infrastructure, Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation, p.8-8, December 06-08, 2004, San Francisco, CA
• 13: Hanspeter Mössenböck, A generator for production quality compilers, Proceedings of the third international workshop on Compiler compilers, p.42-55, February 1991, Schwerin, Germany
• 14: Brian M. Oki , Barbara H. Liskov, Viewstamped replication: a general primary copy, Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, p.8-17, August 15-17, 1988, Toronto, Ontario, Canada [doi>10.1145/62546.62549]
• 15: T. J. Parr , R. W. Quong, ANTLR: a predicated-LL(k) parser generator, Software—Practice & Experience, v.25 n.7, p.789-810, July 1995 [doi>10.1002/spe.4380250705]
• 16: Roberto De Prisco , Butler W. Lampson , Nancy A. Lynch, Revisiting the Paxos Algorithm, Proceedings of the 11th International Workshop on Distributed Algorithms, p.111-125, September 24-26, 1997
• 17: Fred B. Schneider, Implementing fault-tolerant services using the state machine approach: a tutorial, ACM Computing Surveys (CSUR), v.22 n.4, p.299-319, Dec. 1990 [doi>10.1145/98163.98167]
• 18: von Neumann, J. Probabilistic logics and synthesis of reliable organisms from unreliable components. Automata Studies (1956), 43--98.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.5 Reliability
          Subjects: Fault-tolerance

Additional Classification:
  B. Hardware
  B.4 INPUT/OUTPUT AND DATA COMMUNICATIONS
      B.4.5 Reliability, Testing, and Fault-Tolerance**

General Terms:
Experimentation, Performance, Reliability

Keywords:
Paxos, experiences, fault-tolerance, implementation