System and apparatus for optimally trading off the replication overhead and consistency level in distributed applications

• US 20080028006A1
• Filed: 07/26/2006
• Published: 01/31/2008
• Est. Priority Date: 07/26/2006
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Xia, Honghui, Liu, Zhen, Yang, Hao, Ye, Fan
• Granted Patent: US 7,506,011 B2
• Time in Patent Office: Days
• US Class Current: 707/204
• CPC Class Codes: G06F 16/273 Asynchronous replication or reconciliation
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99953 Recoverability
• CPC Class Codes: Y10S 707/99955 Archiving or backup

Abstract

Methods and systems are provided for optimally trading off replication overhead and consistency levels in distributed data replication where nodes are organized in a hierarchy. The root node has the original data that need to be replicated at all other nodes, and the replicated copies have a freshness threshold that must be satisfied. The data are propagated through periodic updates in the hierarchy. Each node periodically sends data to its child nodes. Given the freshness threshold, an algorithm and its distributed protocol can determine the optimal update period for each link of the hierarchy such that the freshness threshold is satisfied for every node and the overall replication overhead is minimized. The systems and methods can be used in any scenario where replicated data have consistency requirements, such as in a replicate overlay assisted resource discovery system.

Claims

1. A method for updating replicated data stored in a plurality of nodes organized in a hierarchy and linked through networks, the method comprising:

defining a freshness threshold for any data stored at any given node within the network hierarchy of nodes; and

determining an update period across each one of a plurality of links between the nodes in the network hierarchy for data stored at each node such that the freshness threshold is satisfied for all data stored at any given node and overhead associated with updating data is minimized; and

updating data stored at the nodes in accordance with the determined update periods.

2. The method of claim 1, wherein the plurality of nodes comprises servers arranged in a tree hierarchy.

3. The method of claim 1, wherein the plurality of nodes are arranged in a tree hierarchy.

4. The method of claim 3, wherein the step of determining the update period further comprises:

communicating, from each node in the hierarchy of nodes to a parent node, its current data update period and a sum of all data update periods from its parent node to one or more leaf nodes, the current data update period comprising a period of time in which a parent node of a given node should send a data update to that node; and

adjusting the communicated current data update periods and update period summations so that the freshness threshold is satisfied at every leaf node within the hierarchy of nodes.

5. The method of claim 3, wherein the step of determining the update period further comprises:

maintaining state data at each node within the hierarchy of nodes, the state data at a given node comprising;

a current data update period associated with that node and expressing the period at which its parent node should send a data update; and

a summation of the data update periods from its parent node to any descendent leaf node of that node; and

maintaining at each non-leaf node a scale factor associated with each child node of the non-leaf node.

6. The method of claim 5, further comprising, communicating the state data maintained at each node up through the hierarchy of nodes to a root node.

7. The method of claim 6, wherein the step of communicating the state data through the hierarchy further comprises:

calculating, at each node within the hierarchy of nodes receiving communicated state data from its children nodes, a data update period for the receiving node using the data update periods in the communicated state data if all sums of the data update periods communicated in the state data are equal.

8. The method of claim 6, wherein the step of communicating the state data through the hierarchy further comprises:

determining at a given node that all of the sums of the data update periods communicated in the state data are not equal;

picking an arbitrary child node of the given node;

using the sum of the data update periods associated with the arbitrary child node to calculate a scale factor for every other child node;

using the calculated scale factors to calculate updated state data for all of the children of the given node; and

communicating the updated state data from the given node up through the hierarchy of nodes.

9. The method of claim 6, further comprising:

receiving state data at a root node from all children nodes of that root node; and

making adjustments to the state data received at the root node to ensure that the freshness threshold is achieved at every leaf node of the root node.

10. The method of claim 9, wherein the step of making adjustments further comprises adjusting summation update periods at each leaf node to equal the defined freshness threshold.

11. The method of claim 9, wherein the step of making adjustments further comprises:

adjusting the summation update periods associated with each leaf node to a common equal value;

comparing the common equal value to the freshness threshold;

obtaining a scale factor as the ratio of the freshness threshold to the common equal value; and

adjusting current update period at each leaf node using the scale factor.

12. The method of claim 11, further comprising:

communicating the scale factor to each child node of the root node;

adjusting current update period for each child using the scale factor.

13. A computer-readable medium containing a computer-readable code that when read by a computer causes the computer to perform a method for updating replicated data stored in a plurality of nodes organized in a hierarchy and linked through networks, the method comprising:

defining a freshness threshold for any data stored at any given node within the network hierarchy of nodes; and

determining an update period across each one of a plurality of links between the nodes in the network hierarchy for data stored at each node such that the freshness threshold is satisfied for all data stored at any given node and the overhead associated with updating data is minimized; and

updating data stored at the nodes in accordance with the determined update periods.

14. The computer-readable medium of claim 13, wherein the plurality of nodes are arranged in a tree hierarchy.

15. The computer-readable medium of claim 14, wherein the step of determining the update period further comprises:

communicating, from each node in the hierarchy of nodes to a parent node, its current data update period and a sum of all data update periods from its parent node to one or more leaf nodes, the current data update period comprising a period of time in which a parent node of a given node should send a data update to that node; and

adjusting the communicated current data update periods and update period summations so that the freshness threshold is satisfied at every leaf node within the hierarchy of nodes.

16. The computer-readable medium of claim 15, wherein the step of determining the update period further comprises:

maintaining state data at each node within the hierarchy of nodes, the state data at a given node comprising;

a current data update period associated with that node and expressing the period at which its parent node should send a data update; and

a summation of the data update periods from its parent node to any descendent leaf node of that node; and

maintaining at each non-leaf node a scale factor associated with each child node of the non-leaf node.

17. The computer-readable medium of claim 16, wherein the method further comprises, communicating the state data maintained at each node up through the hierarchy of nodes to a root node.

18. The computer-readable medium of claim 17, wherein the step of communicating the state data through the hierarchy further comprises:

calculating, at each node within the hierarchy of nodes receiving communicated state data from its children nodes, a data update period for the receiving node using the data update periods in the communicated state data if all sums of the data update periods communicated in the state data are equal.

19. The computer-readable medium of claim 17, wherein the step of communicating the state data through the hierarchy further comprises:

determining at a given node that all of the sums of the data update periods communicated in the state data are not equal;

picking an arbitrary child node of the given node;

using the sum of the data update periods associated with the arbitrary child node to calculate a scale factor for every other child node;

using the calculated scale factors to calculate updated state data for all of the children of the given node; and

communicating the updated state data from the given node up through the hierarchy of nodes.

20. The computer-readable medium of claim 17, wherein the method further comprises:

receiving state data at a root node from all children nodes of that root node; and

making adjustments to the state data received at the root node to ensure that the freshness threshold is achieved at every leaf node of the root node by;

adjusting the summation update periods associated with each leaf node to a common equal value;

comparing the common equal value to the freshness threshold;

obtaining a scale factor as the ratio of the freshness threshold to the common equal value;

adjusting current update period at each leaf node using the scale factor;

communicating the scale factor to each child node of the root node; and

adjusting current update period for each child using the scale factor.