Systems and/or methods for rapid recovery from write-ahead logs

• US 8,683,262 B1
• Filed: 06/21/2013
• Issued: 03/25/2014
• Est. Priority Date: 06/21/2013
• Status: Active Grant

• Current Assignee: Software AG USA Incorporated (Software AG)
• Original Assignee: Terracotta, Inc. (Software AG)
• Inventors: Subbiah, Saravanan, Dennis, Chris, Wu, Timothy, Scott, Myron
• Primary Examiner(s): Baderman, Scott
• Assistant Examiner(s): Bryan, Jason
• Application Number:
  US13/923,880
• Time in Patent Office: 277 Days
• Field of Search: None
• US Class Current: 714/16
• CPC Class Codes: G06F 11/1471 involving logging of persistent data for recovery
• CPC Class Codes: G06F 16/90 Details of database functions independent of the retrieved data types

Abstract

Certain example embodiments provide a single pass, reverse chronological approach to write-ahead log recovery, enabling space- and time-efficient the recovery of stored data from large write-ahead logs to a transient storage medium. The techniques described herein can in certain instances enable fast and efficient recovery, even in scenarios where at the time of a failure requiring such a recovery the live log is potentially multiple terabytes or larger in size. Certain example embodiments make use of a filtering mechanism (e.g., involving potentially stateful delete, skip, and/or transaction filters), a key/value property (allowing a live set of data, once identified, to be applied in any arbitrary order), etc. A simplified environment with a small closed set of mutative operations allows for the performing of recovery backwards by scanning the log from the most recent written record backwards in time (and, in other words, finishing with the oldest record).

Claims

1. A recovery method for a computer system including a processor and a memory that has encountered a fault, the method comprising:

loading to the memory actions taken by the computer system from a write-ahead log maintained on a non-transitory computer readable storage medium, the write-ahead log storing the actions in chronological order;

running the actions stored in the memory through at least one filter in order to identify irrelevant actions that do not need to be replayed in order to recover from the fault;

replaying, using the processor, the actions from the memory until the entire log is replayed in reverse-chronological order, except for identified irrelevant actions that do not need to be replayed, wherein the replaying comprises causing the computer system to take a subset of the same actions stored in the memory again; and

transitioning the computer system from a recovery state to a normal operation state, following the replaying.

2. The method of claim 1, wherein there is no data dependency between actions recorded in the write-ahead log, and the log is maintained such that older actions cannot invalidate newer actions.

3. The method of claim 1, wherein:

the write-ahead log is divided into a plurality of physical segments;

wherein the loading is practiced by;

loading the segments from the write-ahead log into the memory in reverse-chronological order,

dividing the segments, once in memory, into logical partitions,

identifying boundaries in the logical partitions,

dividing the actions in the logical partitions into commit lists, and

reversing the order of the actions in the commit lists; and

wherein the replaying comprises iterating over the actions in the commit lists.

4. The method of claim 1, wherein the write-ahead log is divided into a plurality of physical files having sequential names representing a serial time series.

5. The method of claim 1, wherein each said action has a corresponding type belonging to the list comprising including insert, remove, and update actions.

6. The method of claim 5, wherein each said action has a unique log sequence number (LSN) associated therewith.

7. The method of claim 6, further comprising:

when remove and update type actions are being replayed, logging in a list of actions that should be blocked from replay, the LSN of the removed/updated action;

in connection with the replaying, determining whether the LSN for the action about to be replayed is present in the list of actions that should be blocked from replay and, if so, ignoring the action and removing the LSN from the list of actions that should be blocked.

8. The method of claim 1, wherein each said filter has a corresponding type belonging to the list comprising skip, transaction, and delete filters.

9. The method of claim 1, wherein the actions loaded from the write-ahead log are mutative actions on objects that occurred between a predetermined time before the fault, and the fault.

10. The method of claim 1, wherein the write-ahead log stores entries for the actions, and each individual entry includes a field that can be used to reference a previous entry that that entry invalidates.

11. The method of claim 10, wherein the field is a key/value pair that identifies an operation type and a unique identifier of the previous entry.

12. A non-transitory computer readable-storage medium tangibly storing instructions that, when performed by a processor of a computer system that needs to be recovered as a result of a fault taking place, at least:

load actions taken by the computer system from a disk-backed log that stores the actions in chronological order, to memory of the computer system, wherein the actions loaded from the log are mutative actions that occurred within a time period of interest defined as being between a predetermined time before the fault and the fault;

run the actions stored in the memory through at least one filter in order to identify irrelevant actions that do not need to be replayed in order to recover from the fault;

replay, using the processor, the actions from the memory until the entire log for the time period of interest is replayed in reverse-chronological order, except for the identified irrelevant actions that do not need to be replayed, wherein the replay comprises causing the computer system to take a subset of the same actions stored in the memory again; and

transition the computer system from a recovery state to a normal operation state, following the replay,

wherein there is no data dependency between actions recorded in the log and the log is maintained such that older actions cannot invalidate newer actions.

13. A computer system operable in normal and recovery modes, comprising:

a processor and a memory;

a non-transitory computer readable storage medium tangibly storing a log that stores actions of preselected types taken by the computer system in chronological order;

recovery program logic configured to operate in connection with the processor when the computer system is in recovery mode to load actions from the log into the memory and filter out irrelevant actions that do not need to be replayed;

an object manager configured to cooperate with the processor when the computer system is in recovery mode to restore objects in memory in reverse-chronological order by replaying the actions from the memory in reverse-chronological order, wherein the replaying comprises causing the computer system to take a subset of the same actions stored in the memory again,

wherein the processor is further configured to (a) place the computer system in recovery mode when a fault is detected and (b) transition the computer system from recovery mode to normal mode once the object manager has finished replaying all of the actions that occurred within a time period of interest leading up to the fault, except for the filtered out irrelevant actions.

14. The computer system of claim 13, wherein there is no data dependency between actions recorded in the log and/or the log is maintained such that older actions cannot invalidate newer actions.

15. The computer system of claim 13, wherein the log is divided into a plurality of physical files having sequential names representing a serial time series.

16. The computer system of claim 13, wherein each said action has a corresponding type belonging to the list comprising including insert, remove, and update actions.

17. The computer system of claim 16, wherein each said action has a unique log sequence number (LSN) associated therewith.

18. The computer system of claim 17, wherein:

the recovery program logic is further configured to log in a list of actions that should be blocked from replay, the LSN of removed and updated actions;

the object manager, in connection with action replays, is further configured to determine whether the LSN for the action about to be replayed is present in the list of actions that should be blocked from replay and, if so, ignore that action and remove its LSN from the list of actions that should be blocked.

19. The computer system of claim 13, wherein each said filter is a skip, transaction, or delete filter.

20. The computer system of claim 13, wherein the log stores entries for the actions, each given entry including a field that can be used to reference a previous entry that the given entry invalidates by storing a key/value pair identifying an operation type and a unique identifier of the previous entry.