ACM SIGMOD Anthology VLDB dblp.uni-trier.de

Redo Recovery after System Crashes.

David B. Lomet, Mark R. Tuttle: Redo Recovery after System Crashes. VLDB 1995: 457-468
@inproceedings{DBLP:conf/vldb/LometT95,
  author    = {David B. Lomet and
               Mark R. Tuttle},
  editor    = {Umeshwar Dayal and
               Peter M. D. Gray and
               Shojiro Nishio},
  title     = {Redo Recovery after System Crashes},
  booktitle = {VLDB'95, Proceedings of 21th International Conference on Very
               Large Data Bases, September 11-15, 1995, Zurich, Switzerland},
  publisher = {Morgan Kaufmann},
  year      = {1995},
  isbn      = {1-55860-379-4},
  pages     = {457-468},
  ee        = {db/conf/vldb/LometT95.html},
  crossref  = {DBLP:conf/vldb/95},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

This paper defines a framework for explaining redo recovery after a systemcrash. In this framework, an installation graph explains the order in which operations must be installed into the stable database if it is to remain recoverable. This installation graph is a significantly weaker ordering on operations than the conflict graph from concurrency control. We use the installation graph to devise (i) a cache management algorithm for writing data from the volatile cache to the stable database, (ii) the specification of a REDO test used to choose the operations on the log to replay during recovery, and (iii) an idempotent recovery algorithm based on this test; and we prove that these cache management and recovery algorithms are correct. Most pragmatic recovery methods depend on constraining the kinds of operations that can appear in the log, but our framework allows arbitrary loggedoperations. We use our framework to explain pragmatic methods that constrain the logged operations to reading and writing single pages, and then using this new understanding to relax these constraints. The result is a new class of logged operations having a recovery method with practical advantages over current methods.

Copyright © 1995 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.


Online Paper

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 5, VLDB '89-'97" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Printed Edition

Umeshwar Dayal, Peter M. D. Gray, Shojiro Nishio (Eds.): VLDB'95, Proceedings of 21th International Conference on Very Large Data Bases, September 11-15, 1995, Zurich, Switzerland. Morgan Kaufmann 1995, ISBN 1-55860-379-4
Contents BibTeX

References

[1]
Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman: Concurrency Control and Recovery in Database Systems. Addison-Wesley 1987, ISBN 0-201-10715-5
Contents BibTeX
[2]
Richard A. Crus: Data Recovery in IBM Database 2. IBM Systems Journal 23(2): 178-188(1984) BibTeX
[3]
Klaus Elhardt, Rudolf Bayer: A Database Cache for High Performance and Fast Restart in Database Systems. ACM Trans. Database Syst. 9(4): 503-525(1984) BibTeX
[4]
Jim Gray: Notes on Data Base Operating Systems. Advanced Course: Operating Systems 1978: 393-481 BibTeX
[5]
Jim Gray, Paul R. McJones, Mike W. Blasgen, Bruce G. Lindsay, Raymond A. Lorie, Thomas G. Price, Gianfranco R. Putzolu, Irving L. Traiger: The Recovery Manager of the System R Database Manager. ACM Comput. Surv. 13(2): 223-243(1981) BibTeX
[6]
Jim Gray, Andreas Reuter: Transaction Processing: Concepts and Techniques. Morgan Kaufmann 1993, ISBN 1-55860-190-2
Contents BibTeX
[7]
Theo Härder, Andreas Reuter: Principles of Transaction-Oriented Database Recovery. ACM Comput. Surv. 15(4): 287-317(1983) BibTeX
[8]
Dean Kuo: Model and Verification of a Data Manager Based on ARIES. ICDT 1992: 231-245 BibTeX
[9]
...
[10]
David B. Lomet: MLR: A Recovery Method for Multi-level Systems. SIGMOD Conference 1992: 185-194 BibTeX
[11]
David B. Lomet, Betty Salzberg: Access Method Concurrency with Recovery. SIGMOD Conference 1992: 351-360 BibTeX
[12]
...
[13]
...
[14]
C. Mohan, Donald J. Haderle, Bruce G. Lindsay, Hamid Pirahesh, Peter M. Schwarz: ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging. ACM Trans. Database Syst. 17(1): 94-162(1992) BibTeX
[15]
...
[16]
Kurt Rothermel, C. Mohan: ARIES/NT: A Recovery Method Based on Write-Ahead Logging for Nested Transactions. VLDB 1989: 337-346 BibTeX
[17]
Gerhard Weikum: A Theoretical Foundation of Multi-Level Concurrency Control. PODS 1986: 31-43 BibTeX
[18]
Gerhard Weikum, Christof Hasse, Peter Brössler, Peter Muth: Multi-Level Recovery. PODS 1990: 109-123 BibTeX

Referenced by

  1. David B. Lomet: High Speed On-line Backup When Using Logical Log Operations. SIGMOD Conference 2000: 34-45
  2. Roger S. Barga, David B. Lomet, Thomas Baby, Sanjay Agrawal: Persistent Client-Server Database Sessions. EDBT 2000: 462-477
  3. C. Mohan: Repeating History Beyond ARIES. VLDB 1999: 1-17
  4. David B. Lomet, Mark R. Tuttle: Logical Logging to Extend Recovery to New Domains. SIGMOD Conference 1999: 73-84
  5. Roger S. Barga, David B. Lomet: Phoenix: Making Applications Robust. SIGMOD Conference 1999: 562-564
  6. David B. Lomet, Roger S. Barga, Surajit Chaudhuri, Per-Åke Larson, Vivek R. Narasayya: The Microsoft Database Research Group. SIGMOD Record 27(3): 81-85(1998)
  7. David B. Lomet, Gerhard Weikum: Efficient and Transparent Application Recovery in Client-Server Information Systems. SIGMOD Conference 1998: 460-471
  8. David B. Lomet: Persistent Applications Using Generalized Redo Recovery. ICDE 1998: 154-163
  9. Chendong Zou, Betty Salzberg: Towards Efficient Online Database Reorganization. IEEE Data Eng. Bull. 19(2): 33-40(1996)
  10. Chendong Zou, Betty Salzberg: On-line Reorganization of Sparsely-populated B+trees. SIGMOD Conference 1996: 115-124
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Proceedings: Copyright © by VLDB Endowment,
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:46:06 2009