Logical logging to extend recovery to new domains

ABSTRACT

Recovery can be extended to new domains at reduced logging cost by exploiting “logical” log operations. During recovery, a logical log operation may read data values from any recoverable object, not solely from values on the log or from the updated object. Hence, we needn't log these values, a substantial saving. In [8], we developed a redo recovery theory that deals with general log operations and proved that the stable database remains recoverable when it is explained in terms of an installation graph. This graph was used to derived a write graph that determines a flush order for cached objects that ensures that the database remains recoverable. In this paper, we introduce a refined write graph that permits more flexible cache management that flushes smaller sets of objects. Using this write graph, we show how: (i) the cache manager can inject its own operations to break up atomic flush sets; and (ii) the recovery process can avoid redoing operations whose effects aren't needed by exploiting generalized recovery LSNs. These advances permit more cost-effective recovery for, e.g., files and applications.

REFERENCES

• 1: Bernstein, P. Goodman, N. and Hadzilacos, V. Recover~ Algorithms for Database Systems. IFIP World Computer Congres:;, (Sept. 83) 799-807.
• 2: Crus, R. Data recovery in IBM Database 2. IBM Systems Journal 23,2 (1984) 178-188.
• 3: 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]
• 4: Jim Gray , Andreas Reuter, Transaction Processing: Concepts and Techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1992
• 5: 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]
• 6: Vijay Kumar , Meichun Hsu, Recovery mechanisms in database systems, Prentice-Hall, Inc., Upper Saddle River, NJ, 1998
• 7: David B. Lomet, Persistent Applications Using Generalized Redo Recovery, Proceedings of the Fourteenth International Conference on Data Engineering, p.154-163, February 23-27, 1998
• 8: David B. Lomet , Mark R. Tuttle, Redo Recovery after System Crashes, Proceedings of the 21th International Conference on Very Large Data Bases, p.457-468, September 11-15, 1995
• 9: Lomet, D. and Tuttle, M. A Formal Treatment of Redo Recovery with Pragmatic Implications. Tech. Report (in preparatioJa).
• 10: Lomet, D. Media Recovery When Using Logical Log Operations. (submitted for publication).
• 11: C. Mohan , Don Haderle , Bruce Lindsay , Hamid Pirahesh , Peter Schwarz, ARIES: a transaction recovery method supporting fine-granularity locking and partial rollbacks using write-ahead logging, ACM Transactions on Database Systems (TODS), v.17 n.1, p.94-162, March 1992 [doi>10.1145/128765.128770]
• 12: Rob Strom , Shaula Yemini, Optimistic recovery in distributed systems, ACM Transactions on Computer Systems (TOCS), v.3 n.3, p.204-226, Aug. 1985 [doi>10.1145/3959.3962]

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

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