The SMART way to migrate replicated stateful services

ABSTRACT

Many stateful services use the replicated state machine approach for high availability. In this approach, a service runs on multiple machines to survive machine failures. This paper describes SMART, a new technique for changing the set of machines where such a service runs, i.e., migrating the service. SMART improves upon existing techniques in three important ways. First, SMART allows migrations that replace non-failed machines. Thus, SMART enables load balancing and lets an automated system replace failed machines. Such autonomic migration is an important step toward full autonomic operation, in which administrators play a minor role and need not be available twenty-four hours a day, seven days a week. Second, SMART can pipeline concurrent requests, a useful performance optimization. Third, prior published migration techniques are described in insufficient detail to admit implementation, whereas our description of SMART is complete. In addition to describing SMART, we also demonstrate its practicality by implementing it, evaluating our implementation's performance, and using it to build a consistent, replicated, migratable file system. Our experiments demonstrate the performance advantage of pipelining concurrent requests, and show that migration has only a minor and temporary effect on performance.

REFERENCES

• 1: Atul Adya , William J. Bolosky , Miguel Castro , Gerald Cermak , Ronnie Chaiken , John R. Douceur , Jon Howell , Jacob R. Lorch , Marvin Theimer , Roger P. Wattenhofer, Farsite: federated, available, and reliable storage for an incompletely trusted environment, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060291]
• 2: Kenneth P. Birman, Replication and fault-tolerance in the ISIS system, Proceedings of the tenth ACM symposium on Operating systems principles, p.79-86, December 1985, Orcas Island, Washington, United States
• 3: Miguel Castro , Barbara Liskov, Practical Byzantine fault tolerance, Proceedings of the third symposium on Operating systems design and implementation, p.173-186, February 1999, New Orleans, Louisiana, United States
• 4: Gregory V. Chockler , Idid Keidar , Roman Vitenberg, Group communication specifications: a comprehensive study, ACM Computing Surveys (CSUR), v.33 n.4, p.427-469, December 2001 [doi>10.1145/503112.503113]
• 5: X. Défago , A. Schiper , N. Sergent, Semi-Passive Replication, Proceedings of the The 17th IEEE Symposium on Reliable Distributed Systems, p.43, October 20-23, 1998
• 6: Danny Dolev , Dalia Malki, The Transis approach to high availability cluster communication, Communications of the ACM, v.39 n.4, p.64-70, April 1996 [doi>10.1145/227210.227227]
• 7: Jeremy Elson , Lewis Girod , Deborah Estrin, Fine-grained network time synchronization using reference broadcasts, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060304]
• 8: R. Friedman , A. Vaysburd, Fast Replicated State Machines Over Partitionable Networks, Proceedings of the 16th Symposium on Reliable Distributed Systems (SRDS '97), p.130, October 22-24, 1997
• 9: 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
• 10: R. Guerraoui , A. Schiper, Consensus service: a modular approach for building agreement protocols in distributed systems, Proceedings of the The Twenty-Sixth Annual International Symposium on Fault-Tolerant Computing (FTCS '96), p.168, June 25-27, 1996
• 11: J. Howell and J. Douceur. Replicated virtual machines. Technical report MSR-TR-2005-119, Microsoft Research, 2005.
• 12: J. Howell, J. R. Lorch, and J. Douceur. Correctness of Paxos with replica-set-specific views. Technical report MSR-TR-2004-45, Microsoft Research, 2004.
• 13: 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]
• 14: L. Lamport. Paxos made simple. ACM SIGACT News, 32(4):18--25, Dec. 2001.
• 15: Leslie Lamport, Specifying Systems: The TLA+ Language and Tools for Hardware and Software Engineers, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2002
• 16: 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
• 17: Nancy A. Lynch , Alexander A. Shvartsman, RAMBO: A Reconfigurable Atomic Memory Service for Dynamic Networks, Proceedings of the 16th International Conference on Distributed Computing, p.173-190, October 28-30, 2002
• 18: J. MacCormick, N. Murphy, M. Najork, C. A. Thekkath, and L. Zhou. Boxwood: Abstractions as the foundation for storage infrastructure. In Proc. 6th OSDI, pages 105--120, San Francisco, CA, Dec. 2004.
• 19: Jean-Philippe Martin , Lorenzo Alvisi, A Framework for Dynamic Byzantine Storage, Proceedings of the 2004 International Conference on Dependable Systems and Networks (DSN'04), p.325, June 28-July 01, 2004
• 20: B. M. Oki, VIEWSTAMPED REPLICATION FOR HIGHLY AVAILABLE DISTRIBUTED SYSTEMS, Massachusetts Institute of Technology, Cambridge, MA, 1988
• 21: Rodrigo Rodrigues , Miguel Castro , Barbara Liskov, BASE: using abstraction to improve fault tolerance, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 22: 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]
• 23: C. A. Thekkath. Personal communication. 2005.
• 24: R. van Renesse and F. B. Schneider. Chain replication for supporting high throughput and availability. In Proc. 6th OSDI, pages 91--104, San Francisco, CA, Dec. 2004.
• 25: Jian Yin , Jean-Philippe Martin , Arun Venkataramani , Lorenzo Alvisi , Mike Dahlin, Separating agreement from execution for byzantine fault tolerant services, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
• 26: H. Yu and A. Vahdat. Consistent and automatic replica regeneration. In Proc. 1st NSDI, pages 323--336, San Francisco, CA, Mar. 2004.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

General Terms:
Algorithms, Reliability

Keywords:
migration, paxos, reconfiguration, replicated state machine, replication