Database computer system with application recovery and recovery log sequence numbers to optimize recovery

• US 5,933,838 A
• Filed: 04/04/1997
• Issued: 08/03/1999
• Est. Priority Date: 03/10/1997
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Lomet, David B.
• Primary Examiner(s): Amsbury, Wayne
• Assistant Examiner(s): ALAM, SHAHID AL
• Application Number:
  US08/826,610
• Time in Patent Office: 851 Days
• Field of Search: 707/202, 707/8, 707/204
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1471 involving logging of persistent data for recovery
• CPC Class Codes: G06F 2201/80 Database-specific techniques
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

This invention concerns a database computer system and method for making applications recoverable from system crashes. The application state (i.e., address space) is treated as a single object which can be atomically flushed in a manner akin to flushing individual pages in database recovery techniques. To enable this monolithic treatment of the application, executions performed by the application are mapped to logical loggable operations which can be posted to the stable log. Any modifications to the application state are accumulated and the application state is periodically flushed to stable storage using an atomic procedure. The application recovery integrates with database recovery, and effectively eliminates or at least substantially reduces the need for check pointing applications. In addition, optimization techniques are described to make the read, write, and recovery phases more efficient.

Claims

1. In a database computer system that tracks a recovery log sequence number for a corresponding object to identify a particular log record at which to begin replay to recover the object to a particular state following a system crash, a computer-implemented method comprising the following steps:

incrementally logging in a log record the recovery log sequence number; and

replaying, during recovery from a system crash, operations referenced in log records identified by the recovery log sequence number.

2. A computer programmed to perform the step of the computer-implemented method as recited in claim 1.

3. A computer-readable memory that directs a computer to perform the step in the method as recited in claim 1.

4. In a database computer system that tracks a recovery log sequence number for a corresponding object to identify a particular log record at which to begin replay to recover the object to a particular state following a system crash, a computer-implemented method comprising the following steps:

advancing the recovery log sequence number to a later log record subsequent to the particular log record, the later log record reflecting the object at a state in which computer application operations that write the object state are installed in the non-volatile memory, said advancing step advancing the recovery log sequence number regardless of whether the corresponding object is flushed to the non-volatile memory; and

replaying, during recovery from a system crash, operations referenced in log records that start at the later log record identified by the recovery log sequence number.

5. A computer-implemented method as recited in claim 4, further comprising the step of logging the advanced recovery log sequence number as a log record.

6. A computer-implemented method as recited in claim 4, further comprising the step of storing the recovery log sequence number in a data structure associated with the object.

7. A computer programmed to perform the step of the computer-implemented method as recited in claim 4.

8. A computer-readable memory that directs a computer to perform the step in the method as recited in claim 4.

9. In a database computer system that maintains a stable log having log records referencing computer application operations and that tracks a recovery log sequence number for a corresponding object to identify a particular log record in the stable log at which to begin replaying associated computer application operations to recover the object to a particular state following a system crash , a computer-implemented method comprising the following steps:

advancing the recovery log sequence number to a later log record subsequent to the particular log record, the later log record reflecting the object at a state in which the computer application operations that have written the object state are installed in the non-volatile memory, said advancing step advancing the recovery log sequence number regardless of whether the object is flushed to the non-volatile memory; and

in the event of a system crash, analyzing the stable log to locate the recovery log sequence number and redoing operations referenced in the stable log beginning at the later log record identified by the recovery log sequence number.

10. A computer-implemented method as recited in claim 9, wherein each log record is assigned a log sequence number, further comprising the step of applying a redo test to each log record by comparing the log sequence number to the recovery log sequence number, the redo test comprising:

(a) if the log sequence number of the log record is less than or equal to the recovery log sequence number, not redoing the operation in the log record; and

(b) if the log sequence number of the log record is greater than recovery log sequence number, redoing the operation in the log record.

11. A computer-implemented method as recited in claim 9, further comprising the step of logging the recovery log sequence number as a log record in the stable log.

12. A computer-implemented method as recited in claim 9, further comprising the step of storing the recovery log sequence number in a data structure associated with the object.

13. A computer programmed to perform the steps of the computer-implemented method as recited in claim 9.

14. A computer-readable memory that directs a computer to perform the steps in the method as recited in claim 9.

16. A computer-implemented method as recited in claim 14, further comprising the step of logging the recovery log sequence number.

17. A computer-implemented method as recited in claim 14, further comprising the step of storing the recovery log sequence number in a data structure associated with the application object.

18. A computer programmed to perform the steps of the computer-implemented method as recited in claim 14.

19. A computer-readable memory that directs a computer to perform the steps in the method as recited in claim 14.

15. In a database computer system having a non-volatile memory, a volatile main memory, and an application object which executes from the main memory, a computer-implemented method comprising the following steps:

initiating the application object;

executing the application object;

terminating the application object without flushing the application object to non-volatile memory;

logging logical operations associated with the initiating, executing, and terminating steps;

assigning log sequence numbers to the logged operations; and

setting a recovery log sequence number equal to the log sequence number of the operation associated with the terminating of the application object so that during recovery, the operations associated with the application object preceding the termination operation are not replayed; and

commencing replay of the logged operations, following a system crash at the operation having the log sequence number identified by the recovery log sequence number.

20. In a database computer system having a non-volatile memory, a volatile main memory, and an application object which executes from the main memory, and wherein the non-volatile memory includes a stable log, a computer-implemented method comprising the following steps:

executing the application object to perform operations which read data from, and write data to, a data object;

posting to the stable log a log record for each operation involving the reading or writing of data, the log record containing a reference to either the application object or the data object to identify that referenced object as a source for the data that is read from or written to;

assigning a log sequence number (LSN) to each log record;

defining a recovery log sequence number for the application object (rLSN_A) to identify a first log record associated with the application object and a recovery log sequence number for the data object (rLSN_O) to identify a second log record associated with the data object, the rLSN_A and rLSN_O being used to help determine at which point in the stable log to begin replaying the operations during recovery from a system crash to restore the application and data objects to their operation states just prior to the crash;

occasionally flushing the application object to non-volatile memory to install the operations performed by the application object, said flushing step further resulting in the installation of operations that wrote data to the data object;

advancing the rLSN_A to identify a third log record subsequent to the first log record;

advancing the rLSN_O to identify a fourth log record subsequent to the second log record, the fourth log record reflecting the data object at a state in which the operations that wrote the object state are installed in the non-volatile memory;

analyzing the stable log, during recovery from a system crash, to find the rLSN_A and the rLSN_O ;

determining, during the recovery, a minimum recovery log sequence number rLSN_min that is the earlier of the rLSN_A and the rLSN_O ; and

applying a redo test to each log record in the stable log, starting at the log record identified by the rLSN_min, by comparing the LSN of the log record pertaining to an object to the rLSN_O for that object, the redo test comprising;

(a) if the LSN≦

rLSN_O, not redoing the operation in the log record; and

(b) if the LSN>

rLSN_O, redoing the operation in the log record.

21. A computer-implemented method as recited in claim 20, further comprising the step of logging the rLSN_A and the rLSN_O as log records in the stable log.

22. A computer-implemented method as recited in claim 20, further comprising the step of storing the rLSN_A and the rLSN_O in a data structure associated with the object.

23. A computer programmed to perform the steps of the computer-implemented method as recited in claim 20.

24. A computer-readable memory that directs a computer to perform the steps in the method as recited in claim 20.

25. A database computer system comprising:

a volatile main memory;

a non-volatile memory that persists across a system crash;

a processing unit coupled to the main memory and the non-volatile memory;

an application object stored in the volatile main memory and executable on the processing unit;

a resource manager which interacts with the application object to mediate communication between the application object and a data object so that, during a write operation, the resource manager writes data from the application object to the data object;

the resource manager being configured to log, in a log record on the non-volatile memory, operations performed by the application object and assign a log sequence number (LSN) to each log record;

the resource manager further defining a recovery log sequence number for the application object (rLSN_A) to identify a first log record associated with the application object and a recovery log sequence number for the data object (rLSN_O) to identify a second log record associated with the data object, the rLSN_A and rLSN_O being used to help determine at which point in the stable log to begin replaying the operations during recovery from a system crash to restore the application and data objects;

the resource manager including a cache manager to occasionally flush the application object to non-volatile memory to install the operations performed by the application object, including operations that wrote data to the data object, whereupon flushing the application object, the cache manager advances both the rLSN_A and the rLSN_O to subsequent log records that reflect the application and data objects at states in which the operations that wrote their states are installed in the non-volatile memory;

the resource manager further including a recovery manager that is invoked following a system crash, the recovery manager analyzing the stable log to find the rLSN_A and the rLSN_O and determining a minimum recovery log sequence number rLSN_min that is the earlier of the rLSN_A and the rLSN_O, the recovery manager applying a redo test to each log record in the stable log, starting at the log record having identified by the rLSN_min, by comparing the LSN of the log record pertaining to an object to the rLSN_O for that object, the redo test comprising;

(a) if the LSN≦

rLSN_O, the recovery manager doe not redo the operation in the log record, and

(b) if the LSN>

rLSN_O, the recovery manager redoes the operation in the log record.

26. For use on a database computer system having a non-volatile memory, a volatile main memory, and a processor, a resource manager comprising:

a cache manager executable on the processor to track objects active in the main memory and to manage flushing of objects from the main memory to the non-volatile memory, the cache manager being configured to maintain a recovery log sequence number (rLSN) for each corresponding object to identify a particular log record at which to begin replay to recover the corresponding object to a particular state following a system crash, the cache manager advancing the rLSN for the corresponding object to a subsequent log record that reflects the corresponding object at a state in which computer application operations that wrote that object state are installed in the non-volatile memory, regardless of whether the corresponding object is flushed to the non-volatile memory; and

a recovery manager that is invoked following a system crash, the recovery manager replaying, during recovery from the system crash, operations referenced in log records that start at the subsequent log record identified by the rLSN.

27. A computer-readable medium storing a cache manager as recited in claim 26.