Traversing data in a repeatable manner

• US 7,657,579 B2
• Filed: 04/14/2005
• Issued: 02/02/2010
• Est. Priority Date: 04/14/2005
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: EMC Corporation (Dell Technologies Inc.)
• Inventors: Reitmeyer, Richard, Maruyama, William, Farlee, Kevin
• Primary Examiner(s): Stevens; Robert
• Application Number:
  US11/107,995
• Publication Number:
  US 20060235847A1
• Time in Patent Office: 1,755 Days
• Field of Search: 707/7, 707/204, 711/161, 711/162
• US Class Current: 707/651
• CPC Class Codes: G06F 11/1438 Restarting or rejuvenating
• CPC Class Codes: G06F 11/1466 to make the backup process non-disruptive

Abstract

Traversing hierarchical data is disclosed. A first list of items in a first level of the data is received and sorted in an order. The data of the first level is processed in the order of the sorted first list. If any other level of data is encountered during processing, another list of items in the encountered level is received and sorted in an order. The data is processed in the order of the list.

Claims

1. A method of processing hierarchical data having a hierarchy comprising:

receiving a first list of items in a first level of the hierarchy of the hierarchical data, wherein the hierarchical data is a saveset comprising a file system or a portion thereof;

sorting the first list in an order based on an item attribute that is independent of a physical storage location at which a particular item is physically stored on a storage device;

processing the data of the first level in the order of the sorted first list, including by performing the following in sorted order for each of the items in the sorted first list;

backing up data associated with the item; and

after backup of the item has completed and prior to processing of a next item, generating a record indicating that backup associated with the item has completed; and

if another level of the hierarchy of the hierarchical data is encountered during processing of the first level;

discontinuing, at least temporarily, processing of items in the first list;

receiving a second list of items in the encountered level;

sorting the second list in the order based on the same item attribute used to sort the first list; and

processing the data of the second level in the order of the sorted second list, wherein said steps of receiving the second list of items, sorting the second list, and processing the data of the second level are performed prior to processing of items in the first list being resumed.

2. A method as recited in claim 1, further comprising resuming processing the hierarchical data in the event an operation with which said processing of the hierarchical data is being performed is interrupted, without restarting the operation from the beginning, including by determining a restart point based at least in part on the one or more generated records, traversing the hierarchical data to reach the restart point, and processing remaining elements of the hierarchical data, in the same order in which the hierarchical data was traversed prior to the interruption, as required to continue the operation.

3. A method as recited in claim 2, wherein traversing the hierarchical data to reach a restart point includes traversing, in the same order in which the hierarchical data was traversed prior to the interruption, at least a portion of the hierarchical data processed prior to the interruption.

4. A method as recited in claim 1, further comprising resuming processing data at the first level beginning with a next item in the order of the first list, if any, once processing of a last item in the second list has been completed.

5. A method as recited in claim 1, wherein the first list is stored in a first location in a stack data structure and the second list is stored in a second location in a stack data structure, wherein the first location is associated with the first level of data and the second location is associated with the second level of data.

6. A method as recited in claim 1, wherein hierarchical data comprises data organized as a tree, a directory, an array, or a linked list.

7. A method as recited in claim 1, wherein receiving the first list of items includes receiving data from a content listing process.

8. A method as recited in claim 1, wherein receiving the first list of items includes issuing one or more requests to read a directory.

9. A method as recited in claim 1, wherein the first level comprises a first directory and the second level comprises a second directory that is a subdirectory within the first directory.

10. A method as recited in claim 1, wherein the first level is a root directory of a saveset.

11. A method as recited in claim 1, wherein the first level is a more general level of the hierarchical data than the second level.

12. A method as recited in claim 1, wherein sorting the first list in an order comprises ordering the items in a repeatable order.

13. A method as recited in claim 1, wherein sorting the first list in an order comprises ordering the items in a canonical order.

14. A method as recited in claim 1, wherein the item attribute includes one or more of the following:

item type, item modification time, item creation time, item size, and inode number.

15. A method as recited in claim 1, wherein processing the data of the first level includes traversing the data of the first level.

16. A method as recited in claim 1, wherein any number of levels may be encountered during processing.

17. A method as recited in claim 1, wherein processing can be discontinued.

18. A method as recited in claim 1, wherein processing can resume from a last completed item if processing had been discontinued.

19. A method as recited in claim 1, wherein processing can resume from a last completed item if processing had been discontinued and a predetermined or dynamically configured amount of time has not passed since the discontinuation.

20. A method as recited in claim 1, wherein processing can resume from a last completed item if processing had been discontinued and the hierarchical data has not been modified since the discontinuation.

21. A method as recited in claim 1, wherein the steps of discontinuing, receiving the second list of items, sorting the second list, and processing the data of the second level in the event another level of the hierarchy of the hierarchical data is encountered is performed recursively.

22. A system for processing hierarchical data having a hierarchy comprising:

a processor configured to;

receive a first list of items in a first level of the hierarchy of the hierarchical data, wherein the hierarchical data is a saveset comprising a file system or a portion thereof,

sort the first list in an order based on an item attribute that is independent of a physical storage location at which a particular item is physically stored on a storage device,

process the data of the first level in the order of the sorted first list, including by performing the following for each of the items in the sorted first list;

backing up data associated with the item; and

after backup of the item has completed and prior to processing of a next item, generating a record indicating that backup associated with the item has completed, and

if another level of the hierarchy of the hierarchical data is encountered during processing of the first level;

discontinue, at least temporarily, processing of items in the first list;

receive a second list of items in the encountered level,

sort the second list in the order based on the same item attribute used to sort the first list, and

process the data of the second level in the order of the sorted second list, wherein said steps of receiving the second list of items, sorting the second list, and processing the data of the second level are performed prior to processing of items in the first list being resumed; and

a memory coupled to the processor and configured to provide instructions to the processor.

23. A system as recited in claim 22, wherein the processor is further configured to resume processing data at the first level beginning with a next item in the order of the first list, if any, once processing of a last item in the second list has been completed.

24. A system as recited in claim 22, wherein the processor is further configured to resume processing the hierarchical data in the event an operation with which said processing of the hierarchical data is being performed is interrupted, without restarting the operation from the beginning, including by determining a restart point based at least in part on the one or more generated records, traversing the hierarchical data to reach the restart point, and processing remaining elements of the hierarchical data, in the same order in which the hierarchical data was traversed prior to the interruption, as required to continue the operation.

25. A system as recited in claim 24, wherein traversing the hierarchical data to reach a restart point includes traversing, in the same order in which the hierarchical data was traversed prior to the interruption, at least a portion of the hierarchical data processed prior to the interruption.

26. A system as recited in claim 22, wherein the item attribute includes one or more of the following:

item type, item modification time, item creation time, item size, and inode number.

27. A computer program product for processing hierarchical data having a hierarchy, the computer program product being embodied in a computer readable storage medium and comprising computer instructions for:

receiving a first list of items in a first level of the hierarchy of the hierarchical data, wherein the hierarchical data is a saveset comprising a file system or a portion thereof;

sorting the first list in an order based on an item attribute that is independent of a physical storage location at which a particular item is physically stored on a storage device;

processing the data of the first level in the order of the sorted first list, including by performing the following for each of the items in the sorted first list;

backing up data associated with the item; and

after backup of the item has completed and prior to processing of a next item, generating a record indicating that backup associated with the item has completed; and

if another level of the hierarchy of the hierarchical data is encountered during processing of the first level;

discontinuing, at least temporarily, processing of items in the first list;

receiving a second list of items in the encountered level;

sorting the second list in the order based on the same item attribute used to sort the first list; and

processing the data of the second level in the order of the sorted second list, wherein said steps of receiving the second list of items, sorting the second list, and processing the data of the second level are performed prior to processing of items in the first list being resumed.

28. A computer program product as recited in claim 27, further comprising resuming processing data at the first level beginning with a next item in the order of the first list, if any, once processing of a last item in the second list has been completed.

29. A computer program product as recited in claim 27, further comprising resuming processing the hierarchical data in the event an operation with which said processing of the hierarchical data is being performed is interrupted, without restarting the operation from the beginning, including by determining a restart point based at least in part on the one or more generated records, traversing the hierarchical data to reach the restart point, and processing remaining elements of the hierarchical data, in the same order in which the hierarchical data was traversed prior to the interruption, as required to continue the operation.

30. A computer program product as recited in claim 29, wherein traversing the hierarchical data to reach a restart point includes traversing, in the same order in which the hierarchical data was traversed prior to the interruption, at least a portion of the hierarchical data processed prior to the interruption.

31. A computer program product as recited in claim 27, wherein the item attribute includes one or more of the following:

item type, item modification time, item creation time, item size, and inode number.