Multi-level recovery

ABSTRACT

Multi-level transactions have received considerable attention as a framework for high-performance concurrency control methods. An inherent property of multi-level transactions is the need for compensating actions, since state-based recovery methods do no longer work correctly for transaction undo. The resulting requirement of operation logging adds to the complexity of crash recovery. In addition, multi-level recovery algorithms have to take into account that high-level actions are not necessarily atomic, e.g., if multiple pages are updated in a single action. In this paper, we present a recovery algorithm for multi-level transactions. Unlike typical commercial database systems, we have striven for simplicity rather than employing special tricks. It is important to note, though, that simplicity is not achieved at the expense of performance. We show how a high-performance multi-level recovery algorithm can be systematically developed based on few fundamental principles. The presented algorithm has been implemented in the DASDBS database kernel system.

REFERENCES

• BBG89: Catriel Beeri , Philip A. Bernstein , Nathan Goodman, A model for concurrency in nested transactions systems, Journal of the ACM (JACM), v.36 n.2, p.230-269, April 1989 [doi>10.1145/62044.62046]
• BF89: Peter Brössler , Bernd Freisleben, Transactions on Persistent Objects, Proceedings of the Third International Workshop on Persistent Object Systems, p.303-318, January 10-13, 1989
• BHG87: Philip A. Bernstein , Vassco Hadzilacos , Nathan Goodman, Concurrency control and recovery in database systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1987
• BSW88: Catriel Beeri , Hans-Jörg Schek , Gerhard Weikum, Multi-Level Transaction Management, Theoretical Art or Practical Need ?, Proceedings of the International Conference on Extending Database Technology: Advances in Database Technology, p.134-154, March 14-18, 1988
• CFR89: Cart, M., Ferrie, J., Richy, H., An Optimistic Multi-Level Concurrency Control for Nested Typed Objects, 2nd Int. Conf. on Data and Knowledge Systems for Manufacturing and Engineering, 1989
• Cu88: Curtis, R.B., Informix-Turbo, IEEE COMPCON, 1988
• DeL87: DeLeon, M., Sequential Correctness, Atomicity and Persistence in Database Systems - A Model and a Proof Paradigm, M.Sc. Thesis (in Hebrew), The Hebrew University at Jerusalem, 1987
• EB84: Klaus Elhardt , Rudolf Bayer, A database cache for high performance and fast restart in database systems, ACM Transactions on Database Systems (TODS), v.9 n.4, p.503-525, Dec. 1984 [doi>10.1145/1994.1995]
• FLMW88: Fekete, A., Lynch, N., Merritt, M., Weihl, W., Commutativity-Based Locking for Nested Transactions, Technical Report, MIT, Cambridge (Mass.), 1988
• GS87: Hector Garcia-Molina , Kenneth Salem, Sagas, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.249-259, May 27-29, 1987, San Francisco, California, United States
• Gr81: Jim Gray , Paul McJones , Mike Blasgen , Bruce Lindsay , Raymond Lorie , Tom Price , Franco Putzolu , Irving Traiger, The Recovery Manager of the System R Database Manager, ACM Computing Surveys (CSUR), v.13 n.2, p.223-242, June 1981 [doi>10.1145/356842.356847]
• HH88: Thanasis Hadzilacos , Vassos Hadzilacos, Transaction synchronisation in object bases, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.193-200, March 1988, Austin, Texas, United States [doi>10.1145/308386.308438]
• HM88: Hasse, C., Muth, P., Design, Implementation, and Evaluation of a High Performance Multi-Level Recovery Strategy for the Darmstadt Database Kernel System, M.Sc. Thesis (in German), University of Darmstadt, 1988
• HR83: Theo Haerder , Andreas Reuter, Principles of transaction-oriented database recovery, ACM Computing Surveys (CSUR), v.15 n.4, p.287-317, December 1983 [doi>10.1145/289.291]
• Had88: Vassos Hadzilacos, A theory of reliability in database systems, Journal of the ACM (JACM), v.35 n.1, p.121-145, Jan. 1988 [doi>10.1145/42267.42272]
• Ko83: Henry F. Korth, Locking Primitives in a Database System, Journal of the ACM (JACM), v.30 n.1, p.55-79, Jan. 1983 [doi>10.1145/322358.322363]
• Ma87: Martin, B.E., Modeling Concurrent Activities with Nested Objects, Int. Conf. on Distributed Computing Systems, 1987
• MGG86: J. Eliot B Moss , Nancy D. Griffeth , Marc H. Graham, Abstraction in recovery management, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.72-83, May 28-30, 1986, Washington, D.C., United States
• MLC87: J. Eliot B. Moss , Bruce Leban , Panos K. Chrysanthis, Finer Grained Concurrency for the Database Cache, Proceedings of the Third International Conference on Data Engineering, p.96-103, February 03-05, 1987
• MHLPS89: Mohan, C., Haderle, D., Lindsay, B., Pirahesh, H., Schwarz, P., ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging, IBM Research Report RJ6649, San Jose, 1989
• Ong84: Kee S. Ong, Synapse approach to database recovery, Proceedings of the 3rd ACM SIGACT-SIGMOD symposium on Principles of database systems, April 02-04, 1984, Waterloo, Ontario, Canada [doi>10.1145/588011.588024]
• O’N86: Patrick E. O'Neil, The Escrow transactional method, ACM Transactions on Database Systems (TODS), v.11 n.4, p.405-430, Dec. 1986 [doi>10.1145/7239.7265]
• PSSWD87: H. B. Paul , H. J. Schek , M. H. Scholl, Architecture and implementation of the Darmstadt database kernel system, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.196-207, May 27-29, 1987, San Francisco, California, United States
• RGN90: Thomas C. Rakow , Junzhong Gu , Erich J. Neuhold, Serializability in Object-Oriented Database Systems, Proceedings of the Sixth International Conference on Data Engineering, p.112-120, February 05-09, 1990
• SG88: Dennis Shasha , Nathan Goodman, Concurrent search structure algorithms, ACM Transactions on Database Systems (TODS), v.13 n.1, p.53-90, March 1988 [doi>10.1145/42201.42204]
• SPSW90: H. -J. Schek , H. -B. Paul , M. H. Scholl , G. Weikum, The DASDBS Project: Objectives, Experiences, and Future Prospects, IEEE Transactions on Knowledge and Data Engineering, v.2 n.1, p.25-43, March 1990 [doi>10.1109/69.50904]
• SS84: Peter M. Schwarz , Alfred Z. Spector, Synchronizing shared abstract types, ACM Transactions on Computer Systems (TOCS), v.2 n.3, p.223-250, Aug. 1984 [doi>10.1145/989.1188]
• We88: W. E. Weihl, Commutativity-Based Concurrency Control for Abstract Data Types, IEEE Transactions on Computers, v.37 n.12, p.1488-1505, December 1988 [doi>10.1109/12.9728]
• We89: William E. Weihl, The impact of recovery on concurrency control, Selected papers of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.157-184, August 1993, Philadelphia, Pennsylvania, United States
• WS84: Gerhard Weikum , Hans-Jörg Schek, Architectural Issues of Transaction Management in Multi-Layered Systems, Proceedings of the 10th International Conference on Very Large Data Bases, p.454-465, August 27-31, 1984
• Wei86: Gerhard Weikum, A theoretical foundation of multi-level concurrency control, Proceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.31-43, March 24-26, 1986, Cambridge, Massachusetts, United States [doi>10.1145/6012.15401]
• Wei87a: Weikum, G., Principles and Realization Strategies of Multi-Level Transaction Management, Technical Report, University of Darmstadt, 1987
• Wei87b: Gerhard Weikum, Enhancing Concurrency in Layered Systems, Proceedings of the 2nd International Workshop on High Performance Transaction Systems, p.200-219, September 28-30, 1987
• Wei89: Gerhard Weikum, Set-Oriented Disk Access to Large Complex Objects, Proceedings of the Fifth International Conference on Data Engineering, p.426-433, February 06-10, 1989
• Za87: Zabback, P,, Implementation of the Log Manager of the DASDBS Multi-Level Transaction Architecture, M.$c. Thesis (in German), University of Darmstadt, 1987

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.2 Physical Design
          Subjects: Recovery and restart

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Concurrency

General Terms:
Algorithms, Design, Management, Performance, Theory