Method and apparatus for efficient propagation of large datasets under failure conditions

• US 7,158,985 B1
• Filed: 04/09/2003
• Issued: 01/02/2007
• Est. Priority Date: 04/09/2003
• Status: Expired due to Fees

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Liskov, Barbara
• Primary Examiner(s): Wong; Don
• Assistant Examiner(s): Black; Linh
• Application Number:
  US10/409,851
• Time in Patent Office: 1,364 Days
• Field of Search: 707 1-1041
• US Class Current: 1/1
• CPC Class Codes: G06F 11/2023 Failover techniques
• CPC Class Codes: G06F 11/2048 where the redundant components share neither address space nor persistent storage
• CPC Class Codes: G06F 11/2097 maintaining the standby controller/processing unit updated initialisation or re-synchronisation thereof G06F11/1658 and subgroups
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

A network of nodes caches replicated datasets in which dataset changes are efficiently propagated as a set of changes even under failure conditions. A master node and a plurality of subordinate nodes in the network each maintain a copy of the dataset and a change log storing change events in the dataset in that node. The change log further includes a rename chain having a plurality of linked rename records created in response to a new master gaining control of the dataset. The master node computes and propagates dataset changes to the subordinate nodes as a set of change events. If the master node fails, one of the subordinate nodes becomes temporary master and continues to propagate dataset changes using its dataset and its change log in response to update requests from other nodes where the update request contains information from the change log of the requestor node.

Claims

1. In a computerized device, a method for maintaining a stored dataset replicated from a master dataset, comprising the steps of:

maintaining a change log of changes made to the stored dataset where each change is recorded as an event in a list of events, the list of events including an indicator chain where each link in the indicator chain is an indicator of dataset commonality;

providing an update request to a responder node to update the stored dataset, the update request including a first reference to the list of events and a second reference to the indicator chain;

receiving an update response from the responder node, the update response including information about a responder dataset derived from the first reference and the second reference; and

reconciling the change log and the update response to update the stored dataset whereby the stored dataset is substantially current to the master dataset.

2. The method of claim 1 wherein the indicator chain is a rename chain wherein each link is a rename record including a new dataset name and an associated old dataset name.

3. The method of claim 2 wherein the second reference to the indicator chain comprises a most recent rename record.

4. The method of claim 2 wherein the second reference to the indicator chain comprises a plurality of rename records in the indicator chain.

5. The method of claim 2 wherein the stored dataset has a stored name and wherein the update response includes a new rename record, the step of reconciling further comprises changing the stored name of the stored dataset according to the new rename record.

6. The method of claim 1 wherein the first reference is a most recent event in the change log;

wherein the second reference matches an indicator in a responder indicator chain at the responder node; and

wherein the update response contains change events that follow the most recent event;

the step of reconciling further comprises steps of;

adding the change events contained in the update response to the change log; and

modifying the stored dataset according to the change log including the change events.

7. The method of claim 1 wherein the first reference is the most recent event in the change log;

wherein the second reference matches an indicator in an indicator chain at the responder node; and

wherein the update response contains change events based on a third reference to the list of events that is less recent than the first reference; and

wherein the step of reconciling further comprises the steps of;

a) placing events from the change log between the third reference and the first reference into an undo set;

b) updating the change log by processing the update response change event by change event;

c) comparing each change event from the update response with the undo set, and if a match to an event in the undo set is found, then deleting the event from the undo set;

d) updating the stored dataset according to the updated change log; and

e) if undo set entries remain after the computerized device has processed the entries in the update,

i) providing a second update request to the responder node;

ii) receiving a second update response from the responder node;

iii) reconciling the change log and the second update response; and

iv) updating the stored dataset according to the reconciled change log.

8. The method of claim 7 wherein the second update request is a request for a complete dataset.

9. The method of claim 7 wherein the second update request is a request for information about each remaining event in the undo set.

10. The method of claim 1 wherein the first reference is the most recent event in the change log;

wherein the second reference matches an indicator in an indicator chain at the responder node; and

wherein the update response contains entries based on a third reference to the list of events that is less recent than the first reference; and

wherein the step of maintaining a change log further comprises storing at least one pre-state of the change log;

the step of reconciling further comprises the steps of;

undoing the change log according to a most recent pre-state; and

reconciling the undone change log and the update response to modify the stored dataset.

11. The method of claim 1 wherein the update response is a complete dataset, the update response further comprising a partial change log to be used by the computerized device as a new change log, wherein the step of reconciling further comprises the steps of:

replacing the stored dataset with the complete dataset; and

replacing the change log with the partial change log.

27. The method according to claim 2 wherein maintaining comprises:

maintaining a change log of changes made to the stored dataset where each change is recorded as an event in a list of events, the list of events including an indicator chain of at least one link, where each link in the indicator chain is a record of the name of the stored dataset including a new dataset name and an associated previous dataset name;

and wherein receiving comprises;

receiving an update response from the responder node, the update response including information about a responder dataset derived from the first reference and the second reference, such that the update response is generated by comparing the indicator chain of the stored dataset, taken from the second reference in the update request, with an indicator chain of the responder dataset.

28. The method according to claim 27 wherein maintaining comprises:

adding a link to the indicator chain every time the master dataset is processed by a different node, wherein the link includes the previous dataset name and a new dataset name.

12. In a computerized device, a method for maintaining a stored dataset to be replicated to at least one other node, comprising the steps of:

maintaining a change log of changes made to the stored dataset where each change is recorded as an event in a list of events, the list of events including an indicator chain where each link in the indicator chain is an indicator of dataset commonality;

detecting that a master node storing a master dataset has become non-functional;

accessing a manifest file in response to detecting that the master node has become non-functional;

computing change events from the manifest file;

recording the change events in the change log; and

updating the stored dataset according to the change log.

13. The method of claim 12 wherein the step of recording change events further comprises the step of adding an indicator to the list of events and linked to the indicator chain.

14. The method of claim 12 wherein the indicator chain is a rename chain wherein each link is a rename record including a new dataset name and an associated old dataset name, the method further comprising the steps of:

renaming the stored dataset;

creating a new rename record in response to the renaming step; and

adding the new rename record to the change log.

15. The method of claim 14 wherein the step of renaming the stored dataset further comprises making a new dataset name based on a name of the computerized device.

16. In a computerized device, a method for maintaining a stored dataset to be replicated to at least one other node, comprising the steps of:

maintaining a change log of changes made to the stored dataset where each change is recorded as an event in a list of events, the list of events including an indicator chain where each link in the indicator chain is an indicator of dataset commonality;

receiving an update request from a requesting node storing a replicated dataset, the update request including a first reference to a change log event in a requesting node change log and a second reference to an indicator in a requesting node indicator chain; and

providing an update response to the requesting node including information about the stored dataset derived from the change log based on the first reference and the second reference.

17. The method of claim 16 wherein the indicator chain is a rename chain wherein each link is a rename record including a new dataset name and an associated old dataset name.

18. The method of claim 17 wherein the second reference to the indicator chain comprises a most recent rename record.

19. The method of claim 17 wherein the second reference to the indicator chain comprises a plurality of rename records in the indicator chain.

20. The method of claim 16 wherein the step of providing an update further comprises:

finding a first match for the first reference in the change log;

finding a second match for the second reference in a most recent link in the indicator chain; and

making an update to send to the requesting node including entries from the change log based on the first reference and the second reference.

21. The method of claim 16 wherein the second reference includes a plurality of rename records, and wherein the step of providing an update further comprises:

comparing the second reference to the indicator chain;

if no match in the indicator chain is found, then providing the stored data set to the requesting node;

if a match in the indicator chain is found, then looking for a corresponding event in the change log;

if a corresponding event is found, then making an update to send to the requesting node including events more recent than the corresponding event; and

if a corresponding event is not found, then providing the stored dataset to the requesting node.

22. A method for maintaining consistency among replicated datasets in a system having a master node and a plurality of subordinate nodes, wherein the master node stores a master dataset and each of the plurality of subordinate node stores a subordinate dataset, the method comprising the steps of:

maintaining a change log in the master node and in each of the subordinate nodes, the change log in each node storing changes made in the dataset in that node where the changes are recorded as a list of events, the list of events including an indicator chain where each link in the indicator chain is an indicator of dataset commonality;

detecting at one of the subordinate nodes that the master node is non-functional;

selecting among the subordinate nodes a temporary master;

the temporary master adding an indicator to its list of events and linked to its indicator chain in response to becoming temporary master;

the temporary master accessing a manifest file;

the temporary master updating its dataset according to the manifest file;

the temporary master recording change events from the updating step in its change log;

receiving at the temporary master an update request from another subordinate node, the update request including a first reference to a change log event in the other subordinate node'"'"'s change log and a second reference to an indicator in the other subordinate node'"'"'s indicator chain;

the temporary master providing an update to the other subordinate node including information about the dataset of the temporary master derived from the change log of the temporary master based on the first reference and the second reference;

receiving at the temporary master an update request from the master node, the update request including a third reference to a master node change log event and a fourth reference to an indicator in the master node'"'"'s indicator chain;

the temporary master providing a master node update to the master node including information about the dataset of the temporary master derived from the change log of the temporary master based on the third reference and the fourth reference; and

the temporary master returning control of the system to the master node.

23. A computerized device to maintain a stored dataset replicated from a master dataset, comprising:

a memory;

a storage device storing the dataset and a change log having changes to the dataset recorded as a list of events, the list of events further including an indicator chain where each link in the indicator chain is an indicator of dataset commonality; and

a controller coupled to the storage device and the memory, the controller configured to maintain the change log, to provide an update request to a responder node to update the stored dataset, the update request including a first reference to the list of events and a second reference to the indicator chain, the controller to receive an update response from the responder node, the update response including information about a responder dataset derived from the first reference and the second reference, and the controller to reconcile the change log and the update response to update the stored dataset whereby the stored dataset is made substantially current to the master dataset.

24. A computerized device to maintain a stored dataset to be replicated to at least one other node, comprising:

a memory;

a storage device storing the dataset and a change log having changes to the dataset recorded as a list of events, the list of events further including an indicator chain where each link in the indicator chain is an indicator of dataset commonality; and

a controller coupled to the storage device and the memory, the controller configured to access a manifest file to compute dataset changes, to maintain a change log by including the computed dataset changes, to receive an update request from a requesting node storing a replicated dataset, the update request including a first reference to a change log event in a requesting node change log and a second reference to an indicator in a requesting node indicator chain, and to provide an update response to the requesting node including information about the stored dataset derived from the change log based on the first reference and the second reference.

25. A computer program product having a computer-readable medium including computer program logic encoded thereon that, when performed on a computer system having a coupling of a memory, a processor, and at least one communications interface, provides a method for maintaining a stored dataset replicated from a master dataset by performing the operations of:

maintaining a change log of changes made to the stored dataset where each change is recorded as an event in a list of events, the list of events including an indicator chain where each link in the indicator chain is an indicator of dataset commonality;

providing an update request to a responder node to update the stored dataset, the update request including a first reference to the list of events and a second reference to the indicator chain;

receiving an update response from the responder node, the update response including information about a responder dataset derived from the first reference and the second reference; and

reconciling the change log and the update response to update the stored dataset whereby the stored dataset is substantially current to the master dataset.

26. A computer program product having a computer-readable medium including computer program logic encoded thereon that, when performed on a computer system having a coupling of a memory, a processor, and at least one communications interface, provides a method for maintaining a stored dataset replicated from a master dataset to be replicated to at least one other node by performing the operations of:

maintaining a change log of changes made to the stored dataset where each change is recorded as an event in a list of events, the list of events including an indicator chain where each link in the indicator chain is an indicator of dataset commonality;

receiving an update request from a requesting node storing a replicated dataset, the update request including a first reference to a change log event in a requesting node change log and a second reference to an indicator in a requesting node indicator chain; and

providing an update response to the requesting node including information about the stored dataset derived from the change log based on the first reference and the second reference.