Checkpoint recovery using a B-tree intent log with syncpoints

• US 8,745,005 B1
• Filed: 09/29/2006
• Issued: 06/03/2014
• Est. Priority Date: 09/29/2006
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: EMC Corporation (Dell Technologies Inc.)
• Inventors: Sethi, Pranit, DeSouter, Marc
• Primary Examiner(s): BURKE, JEFF A
• Application Number:
  US11/536,952
• Time in Patent Office: 2,804 Days
• Field of Search: 707/204, 707/644, 707/648, 707/640, 707/674
• US Class Current: 707/648
• CPC Class Codes: G06F 11/1471 involving logging of persistent data for recovery

Abstract

A networked data storage system includes a primary volume and a pointer-based virtual secondary volume. The secondary volume has B-tree checkpoints of the state of a primary filesystem of the primary volume. Intermediate syncpoints are declared between checkpoint checkpoints. The syncpoints are logical locations on the secondary volume where the B-tree is known to be in a consistent state. The frequency of syncpoints may be set by an administrator in units of blocks, i.e., a syncpoint to be taken every n blocks. Before performing a B-tree split, entire images of the leaves and parent node involved in the split are written to an intent log in a relatively fast transaction that may comprise a single I/O operation to contiguous memory. Movement of data between leaf nodes and changes to the parent nodes as a result of the split operation proceed asynchronously. In the event of a reboot before the split operation is complete, the intent log is used to complete the split transaction from the most recent syncpoint. When a new syncpoint is declared, the intent log and dirty leaves are flushed.

Claims

1. Apparatus for facilitating recovery of a secondary volume having data indicative of changes made to data on a primary volume comprising:

monitoring circuitry that identifies a synchronization point where a secondary volume B-tree is known to be consistent;

circuitry that writes, in response only to an impending B-tree split, all B-tree nodes involved in the impending split into an intent log before the split is performed, the intent log thereby being indicative of inconsistency in the secondary volume B-tree since a most recently identified synchronization point; and

circuitry which, in response to a failure or reboot occurring when movement of data between B-tree leaf nodes or update of a B-tree parent node is incomplete, uses the intent log to complete the split by finding the synchronization point, instantiating the B-tree, replaying the intent log, and inserting snapped blocks into appropriate leaves of the instantiated B-tree.

2. The apparatus of claim 1 wherein the secondary volume B-tree includes data indicative of changes made to a filesystem on the primary volume.

3. The apparatus of claim 2 further including circuitry that asynchronously writes nodes to the B-tree in response to the split.

4. The apparatus of claim 3 wherein the intent log stores an indication of the split of the B-tree which is in progress.

5. The apparatus of claim 4 wherein the intent log is flushed when the B-tree split is complete.

6. The apparatus of claim 4 wherein the intent log includes an image of leaf nodes and parent nodes that will result from the split.

7. The apparatus of claim 6 wherein the intent log is written in a single I/O operation.

8. The apparatus of claim 6 wherein the intent log is written to contiguous locations in memory.

9. Computer program code stored on computer readable media, and executable by a computer, for facilitating recovery of a secondary volume having data indicative of changes made to data on a primary volume, comprising:

logic that identifies a synchronization point where a secondary volume B-tree is known to be consistent;

logic that writes, in response only to an impending B-tree split, all B-tree nodes involved in the split into an intent log before the split is performed, the intent log thereby being indicative of inconsistency in the secondary volume B-tree since a most recently identified synchronization point; and

logic which, in response to a failure or reboot occurring when movement of data between B-tree leaf nodes or update of a B-tree parent node is incomplete, uses the intent log to complete the split by finding the synchronization point, instantiating the B-tree, replaying the intent log, and inserting snapped blocks into appropriate leaves of the instantiated B-tree.

10. The program code of claim 9 wherein the secondary volume B-tree includes data indicative of changes made to a filesystem on the primary volume.

11. The program code of claim 10 further including logic that asynchronously writes nodes to the B-tree in response to a split.

12. The program code of claim 11 wherein the intent log logic stores an indication of a split of the B-tree which is in progress.

13. The program code of claim 12 wherein the intent log logic flushes the intent log when the B-tree split is complete.

14. The program code of claim 12 wherein the intent log logic stores, in the intent log, an image of leaf nodes and parent node that will result from the split.

15. The program code of claim 14 wherein the intent log logic causes the intent log to be written in a single I/O operation.

16. The program code of claim 14 wherein the intent log is written to contiguous locations in memory.

17. A method for facilitating recovery of a secondary volume B-tree having data indicative of changes made to data on a primary volume, comprising the steps of:

in response to an indication that a first leaf node of the B-tree is ready to split, allocating a second leaf node to the B-tree;

initiating splitting the first leaf node in memory into the first and second leaf nodes;

writing, in response only to the impending B-tree split, an image of the leaf nodes and parent node that will result from the split into an intent log; and

in response to a failure or reboot occurring when movement of data between the leaf nodes or update of the parent node is incomplete, using the intent log to complete the split by finding a most recent synchronization point, instantiating the B-tree, replaying the intent log, and inserting snapped blocks into appropriate leaves of the instantiated B-tree.

18. The method of claim 17 wherein the primary volume data set is a filesystem, and including the further step of identify a synchronization point where the B-tree structure is known to be consistent before writing into the intent log.

19. The method of claim 18 wherein the intent log is indicative of inconsistency in the B-tree since a most recently identified synchronization point.

20. The method of claim 19 including the further step of, in response to initiation of a recovery operation, finding the most recent synchronization point.