Method and apparatus for generating user-level difference information about two data sets

• US 7,624,106 B1
• Filed: 09/29/2004
• Issued: 11/24/2009
• Est. Priority Date: 09/29/2004
• Status: Active Grant

• Current Assignee: Network Appliance Incorporated (NetApp, Inc.)
• Original Assignee: Network Appliance Incorporated (NetApp, Inc.)
• Inventors: Taylor, William R., Manley, Stephen L.
• Primary Examiner(s): Breene; John E
• Assistant Examiner(s): Bullock; Joshua
• Application Number:
  US10/954,381
• Time in Patent Office: 1,882 Days
• Field of Search: 707/200, 707203-204, 707/201, 707/202, 707/10, 707/6, 714/6
• US Class Current: 707/786
• CPC Class Codes: G06F 11/2082 Data synchronisation
• CPC Class Codes: G06F 16/16 File or folder operations, e.g. details of user interfaces specifically adapted to file systems
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

A method and apparatus to generate information representing differences between two data sets are described. Information representing differences between a first data set and a second data set is acquired, where the first and second data sets each include multiple nodes. A traversal map that identifies nodes for which a difference has been detected between the first and second data sets is generated, and then during an output phase, a hierarchy of nodes is traversed to generate output indicating user-level differences between the first and second data sets. The traversal map is used to avoid traversing at least some of the nodes in the hierarchy during the output phase. A child map may be generated to represent parent-child relationships between the nodes and used during the output phase to prefetch certain nodes in the hierarchy.

Claims

1. A computer implemented method comprising:

acquiring information representing differences between a first data set and a second data set, the first and second data sets each including a plurality of nodes;

building a traversal map that identifies only nodes for which a difference has been detected between the first and second data sets;

traversing a hierarchy of nodes by successively examining nodes in the hierarchy to generate an output including user-level difference information about the first and second data sets, wherein said traversing includes using the traversal map to avoid traversing at least some of the nodes in the hierarchy by ignoring nodes not represented in the traversal map during said traversing;

building a child map that includes information identifying parent-child relationships of nodes of the first and second data sets; and

using the child map to prefetch nodes during said traversing.

2. A method as recited in claim 1, wherein the user-level difference information is human readable and comprises path/name information for files and directories of the first and second data sets.

3. A method as recited in claim 1, wherein said traversing further comprises:

using a depth-first algorithm in conjunction with the traversal map to traverse the hierarchy of nodes.

4. A method as recited in claim 1, wherein the traversal map identifies nodes which have changed or which are parents of nodes that have changed.

5. A method as recited in claim 1, wherein said acquiring difference information relating to the first and second data sets comprises acquiring non-user level difference information relating to the first and second data sets;

the method further comprising generating the user-level difference information relating to the first and second data sets.

6. A computer implemented method of generating user-level difference information relating to a first data set and a second data set, the method comprising the steps of:

A) acquiring difference information relating to the first and second data sets, the first and second data sets each structured as a hierarchy of nodes, each hierarchy of nodes including a root, each node being a file or a directory;

B) identifying nodes which represent differences between the first and second data sets based on the change information;

C) for each node which represents a difference between the first and second data sets,

1) indicating difference information for the node in a change map,

2) creating an entry representing the node in a traversal map,

3) creating an entry representing the parent of the node in the traversal map if such an entry does not already exist in the traversal map,

4) creating an entry in a child map, indicating that the node is a child of the parent, and

5) repeating steps

     3) and

     4) until reaching the root or a node already represented in the traversal map; and

D) traversing trees representing the first and second data sets by successively examining nodes in the hierarchy to generate a human-readable or computer application-readable output including user-level difference information between the first and second data sets, while using the traversal map and a depth-first algorithm to avoid traversing at least some nodes of the trees during said traversing.

7. A method as recited in claim 6, wherein the user-level difference information is path/name information for files and directories of the first and second data sets.

8. A method as recited in claim 6, wherein said receiving difference information relating to the first and second data sets comprises receiving non-user level difference information relating to the first and second data sets;

the method further comprising generating user-level difference information relating to the first and second data sets.

9. A method as recited in claim 6, further comprising, using the child map to prefetch nodes during said traversing.

10. A method as recited in claim 6, wherein said generating output includes, for each node in the tree which represents a change between the first and second data sets:

1) writing user-level difference information for a current node to an output file based on information in the change map;

2) determining whether the current node is represented in the traversal map;

3) if the current node is not represented in the traversal map, then skipping all descendants of the current node in said generating output; and

4) if the current node is represented in the traversal map, then continuing said generating output from a child of the current node.

11. A processing system comprising:

a processor; and

a memory accessible to the processor and containing software which, when executed by the processor, causes the processing system to perform a process including

generating user-level information that represents differences between a first data set and a second data set, the first and second data sets each structured as a hierarchy of nodes,

building a traversal map that identifies nodes of one or both of the first and second data sets, each node in the traversal map being a node for which a difference has been detected between the first and second data sets,

traversing a hierarchical structure by successively examining nodes in the hierarchy to generate and output user-level difference information representing differences between the first and second data sets, wherein said traversing includes referring to the traversal map during said traversing and ignoring nodes which are not represented in the traversal map,

building a child map that includes information identifying parent-child relationships of nodes of the first and second data sets; and

using the child map to prefetch nodes during said traversing.

12. A processing system as recited in claim 11, wherein the processing system comprises a storage server.

13. A processing system as recited in claim 12, wherein the storage server is a file server.

14. A processing system as recited in claim 11, further comprising:

a storage interface through which to communicate with an array of storage devices for purposes of reading data from, or writing data to, the storage devices; and

a network interface through which to communicate with a plurality of clients over a network;

the processing system being configured to service requests from the clients relating to data stored in the array of storage devices.

15. A processing system as recited in claim 11, wherein the user-level difference information is pathname information for files and directories of the first and second data sets.

16. A processing system as recited in claim 11, wherein the user-level difference information comprises path/name information for files and directories of the first and second data sets.

17. A processing system as recited in claim 11, wherein said traversing further comprises:

using a depth-first algorithm in conjunction with the traversal map to traverse the hierarchical structure.

18. A processing system as recited in claim 11, wherein the traversal map identifies nodes which have changed or which are parents of nodes that have changed.

19. A storage system comprising:

means for servicing a request from a client to access data stored in a set of storage devices;

means for acquiring information representing differences between a first data set and a second data set, at least one of the first and second data sets being stored in the set of storage devices, the first and second data sets each structured as a hierarchy of nodes;

means for building a traversal map that identifies only nodes for which a difference has been detected between the first and second data sets;

means for traversing a hierarchy of nodes representing the first or second data set by successively examining nodes in the hierarchy, to generate an output including user-level difference information about the first and second data sets, including using the traversal map to avoid traversing at least some nodes such that nodes not represented in the traversal map are skipped during said traversing;

means for building a child map that includes information identifying parent-child relationships of nodes of the first and second data sets; and

means for using the child map to prefetch nodes during said traversing.

20. A storage system as recited in claim 19, wherein the output indicating user-level differences comprises path/name information for files and directories of the first and second data sets.

21. A storage system as recited in claim 19, wherein said means for traversing further comprises:

means for using a depth-first algorithm in conjunction with the traversal map to traverse the hierarchy of nodes.

22. A storage system as recited in claim 19, wherein the traversal map identifies nodes which have changed or which are parents of nodes that have changed.

23. A storage system as recited in claim 19, wherein said means for acquiring difference information relating to the first and second data sets comprises means for acquiring non-user level difference information relating to the first and second data sets;

the storage system further comprising means for generating user-level difference information relating to the first and second data sets.

24. A computer implemented method comprising:

acquiring information representing differences between a first data set and a second data set, the first and second data sets each including a plurality of nodes;

building a third data set that identifies only nodes for which a difference has been detected between the first and second data sets;

processing a hierarchy of nodes by successively examining nodes in the hierarchy to generate an output including file path and file name information for the first and second data sets, including using the third data set to identify nodes in the hierarchy that do not need to be processed for the purpose of generating said output, and skipping the nodes that are not identified in said processing;

building a child map that includes information identifying parent-child relationships of nodes of the first and second data sets; and

using the child map to prefetch nodes during said processing.

25. A method as recited in claim 24, wherein the output is human readable and comprises path and name information for files and directories of the first and second data sets.

26. A method as recited in claim 24, wherein said processing further comprises:

using a depth-first algorithm in conjunction with the third data set to traverse the hierarchy of nodes.

27. A method as recited in claim 24, wherein the third data set identifies nodes which have changed or which are parents of nodes that have changed.

28. A method as recited in claim 24, wherein said acquiring difference information relating to the first and second data sets comprises acquiring non-user level difference information relating to the first and second data sets;

the method further comprising generating the user-level difference information relating to the first and second data sets.

29. A computer implemented method comprising:

acquiring non-user-level difference information representing differences between a first data set and a second data set, the first and second data sets each including a plurality of nodes;

building a traversal map that identifies only nodes for which a difference has been detected between the first and second data sets; and

traversing a hierarchy of nodes by successively examining nodes in the hierarchy in a depth-first order, to generate an output including user-level difference information about the first and second data sets based on the non-user-level difference information, while skipping nodes not represented in the traversal map during said traversing;

building a child map that includes information identifying parent-child relationships of nodes of the first and second data sets; and

using the child map to prefetch nodes during said traversing.