Traversing data in a repeatable manner

• US 20060235847A1
• Filed: 04/14/2005
• Published: 10/19/2006
• 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
• Granted Patent: US 7,657,579 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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 comprising:

receiving a first list of items in a first level of the data;

sorting the first list in an order;

processing the data of the first level in the order of the sorted first list; and

if another level of data is encountered during processing;

receiving a second list of items in the encountered level;

sorting the second list in an order; and

processing the data in the order of the second list.

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 traversing the hierarchical data to reach a 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 level of data.

6. A method as recited in claim 1, wherein hierarchical data is a saveset comprising a file system or a portion thereof.

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

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

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

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

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

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

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

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

15. A method as recited in claim 14, wherein the canonical order comprises ordering based on one or more of the following:

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

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

17. A method as recited in claim 1, wherein processing the data of the first level includes backing up data associated with the data of the first level.

18. A method as recited in claim 1, wherein processing the data of the first level includes logging data associated with the data of the first level.

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

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

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

22. 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.

23. 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.

24. A system for processing hierarchical data comprising:

a processor configured to;

receive a first list of items in a first level of the data,

sort the first list in an order,

process the data of the first level in the order of the sorted first list, and

if another level of data is encountered during processing;

receive a second list of items in the encountered level,

sort the second list in an order, and

process the data in the order of the second list; and

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

25. A system as recited in claim 24, 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.

26. A system as recited in claim 24, 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 traversing the hierarchical data to reach a restart point;

and process 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.

27. A system as recited in claim 26, 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.

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

receiving a first list of items in a first level of the data;

sorting the first list in an order;

processing the data of the first level in the order of the sorted first list; and

if another level of data is encountered during processing;

receiving a second list of items in the encountered level;

sorting the second list in an order; and

processing the data in the order of the second list.

29. A computer program product as recited in claim 28, 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.

30. A computer program product as recited in claim 28, 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 traversing the hierarchical data to reach a 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.

31. A computer program product as recited in claim 30, 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.