System and method for discovery based data recovery in a store and forward replication process

• US 5,832,514 A
• Filed: 06/26/1996
• Issued: 11/03/1998
• Est. Priority Date: 06/26/1996
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Norin, Scott, Benson, Max Loell, Shakib, Darren Arthur
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): HOMERE, JEAN RAYMOND
• Application Number:
  US08/670,588
• Time in Patent Office: 860 Days
• Field of Search: 395/610, 395/200.03, 395/200.19, 395/182.11, 395/183.17, 395/620, 395/619, 395/618, 395/200.31, 395/200.39, 395/185.1, 707/10, 707/203, 707/202, 707/204
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1464 for networked environments
• CPC Class Codes: G06F 11/1469 Backup restoration techniques
• CPC Class Codes: G06F 16/1844 Management specifically adapted to replicated file systems
• CPC Class Codes: H04L 51/00 User-to-user messaging in packet-switching networks, transmitted according to store-and-forward or real-time protocols, e.g. e-mail
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

Systems and methods for discovery based data recovery in a store and forward replication system are presented. Data loss is discovered by comparing a list of changes made to a local copy of a replica object with a list of changes received over the network from other nodes also having a copy of the replica object. When the list of changes received contains changes that the local list does not, the local system knows its copy of the replica object is not up-to-date. Missing changes are then requested from other systems having the missing data. In making the request, care is taken to minimize the cost incurred in recovering the missing data and to balance network traffic among several other nodes, if possible.

Claims

1. In a network having a plurality of nodes, a method for discovering data missing from a local copy of a replica object replicated at one of said nodes, and for recovering the missing data, the method comprising the steps of:

keeping, at a local node, a local change set comprising a list of changes that have been made to a local copy of a replica object, said replica object replicated at at least one other node in the network, said list of changes comprising both changes made at said local node and changes made at said at least one other node that have been received by said local node and applied to said local copy of said replica object;

sending said local change set to said at least one other node;

receiving a change set from said at least one other node, said received change set comprising a list of changes including both changes made by said at least one other node to a copy of said replica object replicated at said at least one other node and changes received by said at least one other node from any other node and applied to said copy of said replica object replicated at said at least one other node; and

discovering at said local node any data missing from the local copy of the replica object by comparing the received change set to the local change set to identify changes listed in the received change set, but not listed in the local change set.

2. A method for discovering and recovering missing data as recited in claim 1 further comprising the step of requesting changes, listed in said received change set but not listed in said local change set, from at least a selected one of said plurality of nodes.

3. A method for discovering and recovering missing data as recited in claim 2 wherein a specified time elapses between the step of comparing the received change set to the local change set and the step of requesting changes listed in the received change set but not listed in the local change set.

4. A method for discovering and recovering missing data as recited in claim 2 wherein the changes listed in the received change set but not listed in the local change set are requested from a node selected in accordance with a node selection criteria which minimizes the time required to receive the requested changes according to a designated minimization criteria.

5. A method for discovering and recovering missing data as recited in claim 4 wherein the node selection criteria also balances the requests among the one or more other nodes according to a designated balancing criteria.

6. A method for discovering and recovering missing data as recited in claim 1 further comprising the step of entering changes found in the received change set but not found in the local change set into a backfill set.

7. A method for discovering and recovering missing data as recited in claim 6 further comprising the step of associating a time delay value with the changes entered into the backfill set.

8. A method for discovering and recovering missing data as recited in claim 1 further comprising the step of comparing the received change set with a backfill set comprising a list of changes missing from said local node.

9. A method for discovering and recovering missing data as recited in claim 1 further comprising the step of sending a message to one or more other nodes which comprises the local change set.

10. A method for discovering and recovering missing data as recited in claim 1 further comprising the step of sending an information request message to one or more other nodes, said information request message comprising a request for change sets located at said one or more other nodes.

11. A method for discovering and recovering missing data as recited in claim 1 wherein the replica object comprises at least one data object of a data set.

12. A method for discovering and recovering missing data as recited in claim 1 wherein the replica object comprises properties of a data set.

13. In a network having a plurality of nodes, a method for discovering data missing from a local copy of a replica object replicated at one of said nodes, and for recovering the missing data, the method comprising the steps of:

keeping, at a local node, a local change set comprising a list of changes that have been made to a local copy of a replica object, said replica object replicated at at least one other node in the network, said list of changes comprising both changes made at said local node and changes made at said at least one other node that have been received by said local node and applied to said local copy of said replica object;

sending said local change set to said at least one other node;

receiving a change set from said at least one other node, said received change set comprising a list of changes including both changes made at said at least one other node to a copy of said replica object replicated at said at least one other node and changes received by said at least one other node from any other node and applied to said copy of said replica object replicated at said at least one other node;

discovering at said local node any data missing from the local copy of the replica object by comparing the received change set to the local change set to determine if the received change set contains changes not found in the local change set;

entering the changes listed in the received change set but not listed in the local change set into a backfill set comprising a list of changes missing from the local change set;

selecting at least one of the at least one other node according to a specified criteria designed to minimize the cost of receiving changes missing from the local change set; and

sending a message to said selected at least one of the at least one other node requesting the changes missing from the local change set.

14. A method for discovering and recovering missing data as recited in claim 13 further comprising the step of waiting a specified time prior to the step of sending a message requesting the changes missing from the local change set.

15. A method for discovering and recovering missing data as recited in claim 14 further comprising the step of comparing the received change set to the backfill set.

16. A method for discovering and recovering missing data as recited in claim 15 further comprising the step of removing from said backfill set the changes listed in the received change set and also listed in the backfill set.

17. A method for discovering and recovering missing data as recited in claim 16 further comprising the step of entering into said local change set the changes listed in the received change set and also listed in the backfill set.

18. A method for discovering and recovering missing data as recited in claim 17 further comprising the step of sending to one or more other nodes a message comprising the local change set.

19. A method for discovering and recovering missing data as recited in claim 18 further comprising the step of sending to said one or more other nodes a message comprising a request for change sets located at said one or more other nodes.

20. In a network having a plurality of nodes, a method for discovering data missing from a local copy of a replica object replicated at one of said nodes, and for recovering the missing data, the method comprising the steps of:

keeping at a local node a local change set comprising a list of changes that have been made to a local copy of a replica object, said replica object replicated at at least one other node in the network, said list of changes comprising both changes made at said local node and changes made at said at least one other node that have been received by said local node and applied to said local copy of said replica object;

broadcasting from said local node to one or more other nodes in the network an information request message, said information request message comprising a request for a change set from said one or more other nodes;

receiving at said local node said requested change set from said one or more other nodes; and

discovering at said local node any data missing from said local copy of the replica object comparing the received change set to the local change set to identify changes listed in the received change set, but not listed in the local change set.

21. A method for discovering and recovering missing data as recited in claim 20 wherein the information request message is broadcast from the local node when the local node is first started.

22. A method for discovering and recovering missing data as recited in claim 20 wherein the information request message also contains a copy of a local change set kept by the local node.

23. In a network system comprising a plurality of replica nodes, each logically connected to one another, an article of manufacture for use in a local replica node having a copy of a designated replica object, each replica node comprising a CPU, said article of manufacture comprising:

program storage means, accessible by the CPU, for storing and providing to the CPU program code means, said program code means comprising;

means for storing a local change set comprising changes made to a local copy of a designated replica object, said changes originating at either of said local replica node or any other replica node;

means for sending said local change set to other replica nodes;

means for receiving from said other replica nodes at least one received change set containing changes made to copies of the designated replica object at said other replica nodes and changes received by said other replica nodes from any other replica node and applied to said copies of the designated replica object; and

means for comparing said at least one received change set to said local change set in order to discover data missing from said local copy of the designated replica object.

24. An article of manufacture as recited in claim 23 wherein the program code means further comprises means for requesting from other replica nodes data missing from the local change set.

25. An article of manufacture as recited in claim 23 wherein the program code means further comprises means for requesting from other replica nodes change sets stored at said other systems.

26. An article of manufacture as recited in claim 23 wherein the means for sending said local change set to other replica nodes uses one-way, unacknowledged communication messages to transfer the local change set.

27. An article of manufacture as recited in claim 23 wherein the program code means further comprises means for storing a backfill set comprising a list of changes missing from said local change set.

28. An article of manufacture as recited in claim 23 wherein the program code means further comprises means for scheduling requests for data missing from the local change set.

29. An article of manufacture as recited in claim 23 wherein the program code means further comprises means for designating a replica node which does not respond to a request as inactive.

30. An article of manufacture as recited in claim 23 wherein the program code means further comprises means to select a replica node that will be used to fill a request for data missing from the local change set.

31. An article of manufacture as recited in claim 30 wherein said means to select a replica node that will be used to fill a request for data comprises means to select the replica node based on minimization, according to a specified criteria, of the cost incurred to receive said missing data.

32. An article of manufacture as recited in claim 23 wherein the replica object comprises at least one data object of a data set.

33. An article of manufacture as recited in claim 23 wherein the replica object comprises the properties of a data set.

34. In a network system comprising a plurality of replica nodes, each logically connected to one another, an article of manufacture for use in a local replica node having a local copy of a designated replica object, each replica node comprising a CPU, said article of manufacture comprising:

program storage means, accessible by the CPU, for storing and providing to the CPU program code means, said program code means comprising;

means for storing a local change set comprising changes made to a local copy of a designated replica object, said changes originating at either of said local replica node or any other replica node;

means for sending said local change set to the other replica nodes;

means for receiving from said other replica nodes at least one received change set containing changes made to copies of the designated replica object at said other replica nodes and changes received by said other replica nodes from any other replica node and applied to said copies of the designated replica object;

means for comparing said at least one received change set to said local change set in order to discover data missing from said local copy of the designated replica object; and

means for requesting from said other replica nodes data missing from said local copy of the designated replica object.

35. An article of manufacture as recited in claim 34 wherein the program code means further comprises means for storing a backfill set comprising a list of changes missing from said local change set.

36. An article of manufacture as recited in claim 35 wherein the program code means further comprises means for scheduling requests for data missing from the local change set.

37. An article of manufacture as recited in claim 36 wherein the program code means further comprises means for selecting which replica node will be used to request data missing from the local change set.

38. An article of manufacture as recited in claim 37 wherein the means for selecting which replica node will be used to request data comprises means for selecting the replica node based on minimization, according to a specified criteria, of the cost incurred in receiving said missing data.

39. An article of manufacture as recited in claim 38 wherein the program code means further comprises means for designating a replica node which does not respond to a request as inactive.

40. An article of manufacture as recited in claim 39 wherein the program code means further comprises means for requesting from other replica nodes change sets stored at said other replica nodes.

41. An article of manufacture as recited in claim 34 wherein the program code means further comprises means for tracking objects deleted from a replica.

42. An article of manufacture as recited in claim 34 wherein the program code means further comprises means for removing and tracking expired data.

43. An article of manufacture as recited in claim 42 wherein the means for removing and tracking expired data comprises:

means for removing, from said local change set, data which has expired; and

means for tracking which data has expired and been removed from said local change set.