Stabilizers: a modular checkpointing abstraction for concurrent functional programs

ABSTRACT

Transient faults that arise in large-scale software systems can often be repaired by re-executing the code in which they occur. Ascribing a meaningful semantics for safe re-execution in multi-threaded code is not obvious, however. For a thread to correctly rexecute a region of code, it must ensure that all other threads which have witnessed its unwanted effects within that region are also reverted to a meaningful earlier state. If not done properly, data inconsistencies and other undesirable behavior may result. however, automatically determining what constitutes a consistent global checkpoint is not straightforward since thread interactions are a dynamic property of the program.In this paper, we present a safe and efficient checkpointing mechanism for Concurrent ML (CML) that can be used to recover from transient faults. We introduce a new linguistic abstraction called stabilizers that permits the specification of per-thread monitors and the restoration of globally consistent checkpoints. Safe global states are computed through lightweight monitoring of communication events among threads (e.g. message-passing operations or updates to shared variables).Our experimental results on several realistic, multithreaded, server-style CML applications, including a web server and a windowing toolkit, show that the overheads to use stabilizers are small, and lead us to conclude that they are a viable mechanism for defining safe checkpoints in concurrent functional programs.

REFERENCES

• 1: Atul Adya , Robert Gruber , Barbara Liskov , Umesh Maheshwari, Efficient optimistic concurrency control using loosely synchronized clocks, ACM SIGMOD Record, v.24 n.2, p.23-34, May 1995
• 2: Saurabh Agarwal , Rahul Garg , Meeta S. Gupta , Jose E. Moreira, Adaptive incremental checkpointing for massively parallel systems, Proceedings of the 18th annual international conference on Supercomputing, June 26-July 01, 2004, Malo, France [doi>10.1145/1006209.1006248]
• 3: Micah Beck , James S. Plank , Gerry Kingsley, Compiler-Assisted Checkpointing, University of Tennessee, Knoxville, TN, 1994
• 4: Greg Bronevetsky , Daniel Marques , Keshav Pingali , Paul Stodghill, Automated application-level checkpointing of MPI programs, Proceedings of the ninth ACM SIGPLAN symposium on Principles and practice of parallel programming, June 11-13, 2003, San Diego, California, USA
• 5: Greg Bronevetsky , Daniel Marques , Keshav Pingali , Peter Szwed , Martin Schulz, Application-level checkpointing for shared memory programs, Proceedings of the 11th international conference on Architectural support for programming languages and operating systems, October 07-13, 2004, Boston, MA, USA
• 6: Roberto Bruni , Hernán Melgratti , Ugo Montanari, Theoretical foundations for compensations in flow composition languages, Proceedings of the 32nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.209-220, January 12-14, 2005, Long Beach, California, USA
• 7: G. Candea, S. Kawamoto, Y. Fujiki, G. Friedman, and A. Fox. Microreboot - A Technique for Cheap Recovery. In 6th Symposium on Operating Systems Design and Implementation, San Francisco, California, 2004.
• 8: Yuqun Chen , James S. Plank , Kai Li, CLIP: a checkpointing tool for message-passing parallel programs, Proceedings of the 1997 ACM/IEEE conference on Supercomputing (CDROM), p.1-11, November 15-21, 1997, San Jose, CA [doi>10.1145/509593.509626]
• 9: Jan Christiansen , Frank Huch, Searching for deadlocks while debugging concurrent haskell programs, Proceedings of the ninth ACM SIGPLAN international conference on Functional programming, September 19-21, 2004, Snow Bird, UT, USA
• 10: Panos K. Chrysanthis , Krithi Ramamritham, ACTA: the SAGA continues, Database transaction models for advanced applications, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1992
• 11: William R. Dieter , James E. Lumpp Jr, A User-level Checkpointing Library for POSIX Threads Programs, Proceedings of the Twenty-Ninth Annual International Symposium on Fault-Tolerant Computing, p.224, June 15-18, 1999
• 12: Kevin Donnelly , Matthew Fluet, Transactional events, Proceedings of the eleventh ACM SIGPLAN international conference on Functional programming, September 16-21, 2006, Portland, Oregon, USA
• 13: E. N. (Mootaz) Elnozahy , Lorenzo Alvisi , Yi-Min Wang , David B. Johnson, A survey of rollback-recovery protocols in message-passing systems, ACM Computing Surveys (CSUR), v.34 n.3, p.375-408, September 2002 [doi>10.1145/568522.568525]
• 14: John Field , Carlos A. Varela, Transactors: a programming model for maintaining globally consistent distributed state in unreliable environments, Proceedings of the 32nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.195-208, January 12-14, 2005, Long Beach, California, USA
• 15: Matthew Flatt , Robert Bruce Findler, Kill-safe synchronization abstractions, Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation, June 09-11, 2004, Washington DC, USA
• 16: Jim Gray and Andreas Reuter. Transaction Processing. Morgan-Kaufmann, 1993.
• 17: Tim Harris , Keir Fraser, Language support for lightweight transactions, Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications, October 26-30, 2003, Anaheim, California, USA
• 18: Tim Harris , Simon Marlow , Simon Peyton-Jones , Maurice Herlihy, Composable memory transactions, Proceedings of the tenth ACM SIGPLAN symposium on Principles and practice of parallel programming, June 15-17, 2005, Chicago, IL, USA [doi>10.1145/1065944.1065952]
• 19: Maurice Herlihy , Victor Luchangco , Mark Moir , William N. Scherer, III, Software transactional memory for dynamic-sized data structures, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.92-101, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872048]
• 20: http://www.mlton.org.
• 21: D. Hulse, On Page-Based Optimistic Process Checkpointing, Proceedings of the 4th International Workshop on Object-Orientation in Operating Systems, p.24, August 14-15, 1995
• 22: Selective Checkpointing and Rollbacks in Multithreaded Distributed Systems, Proceedings of the The 21st International Conference on Distributed Computing Systems, p.39, April 16-19, 2001
• 23: H. T. Kung , John T. Robinson, On optimistic methods for concurrency control, ACM Transactions on Database Systems (TODS), v.6 n.2, p.213-226, June 1981 [doi>10.1145/319566.319567]
• 24: K. Li , J. F. Naughton , J. S. Plank, Real-time, concurrent checkpoint for parallel programs, Proceedings of the second ACM SIGPLAN symposium on Principles & practice of parallel programming, p.79-88, March 14-16, 1990, Seattle, Washington, United States
• 25: John H. Reppy, Concurrent programming in ML, Cambridge University Press, New York, NY, 1999
• 26: Martin C. Rinard, Effective fine-grain synchronization for automatically parallelized programs using optimistic synchronization primitives, ACM Transactions on Computer Systems (TOCS), v.17 n.4, p.337-371, Nov. 1999 [doi>10.1145/329466.329486]
• 27: Michael F. Ringenburg , Dan Grossman, AtomCaml: first-class atomicity via rollback, Proceedings of the tenth ACM SIGPLAN international conference on Functional programming, September 26-28, 2005, Tallinn, Estonia
• 28: Asser N. Tantawi , Manfred Ruschitzka, Performance analysis of checkpointing strategies, ACM Transactions on Computer Systems (TOCS), v.2 n.2, p.123-144, May 1984 [doi>10.1145/190.357398]
• 29: Andrew P. Tolmach , Andrew W. Appel, Debugging standard ML without reverse engineering, Proceedings of the 1990 ACM conference on LISP and functional programming, p.1-12, June 27-29, 1990, Nice, France [doi>10.1145/91556.91564]
• 30: Andrew P. Tolmach , Andrew W. Appel, Debuggable concurrency extensions for standard ML, Proceedings of the 1991 ACM/ONR workshop on Parallel and distributed debugging, p.120-131, May 20-21, 1991, Santa Cruz, California, United States
• 31: Adam Welc , Suresh Jagannathan , Antony Hosking, Safe futures for Java, Proceedings of the 20th annual ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, October 16-20, 2005, San Diego, CA, USA
• 32: Adam Welc, Suresh Jagannathan, and Antony L. Hosking. Transactional Monitors for Concurrent Objects. In European Conference on Object-Oriented Programming, pages 519--542, 2004.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Concurrent programming structures

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
  D.3 PROGRAMMING LANGUAGES
      D.3.1 Formal Definitions and Theory
          Subjects: Semantics

General Terms:
Design, Experimentation, Languages, Measurement, Performance, Reliability

Keywords:
checkpointing, concurrent ML, concurrent programming, error recovery, exception handling, transactions