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

• US 7,506,011 B2
• Filed: 07/26/2006
• Issued: 03/17/2009
• Est. Priority Date: 07/26/2006
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Xia, Honghui, Liu, Zhen, Yang, Hao, Ye, Fan
• Primary Examiner(s): Pham; Hung Q
• Assistant Examiner(s): Spieler; William
• Application Number:
  US11/493,373
• Publication Number:
  US 20080028006A1
• Time in Patent Office: 965 Days
• Field of Search: 707/100, 707/204, 707/2, 707/200, 707/203
• US Class Current: 1/1
• 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 computer-implemented method for updating replicated data stored in a plurality of nodes organized in a hierarchy and linked through networks, the method comprising:

defining a maximum period of use before data is refreshed for any data stored at any given node within a plurality of nodes comprising servers arranged in a tree hierarchy;

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

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

a summation of the data update periods from the parent node of the given node to any descendent leaf node of the given node;

communicating the state data maintained at each node up through the tree hierarchy of nodes to a root node in the tree hierarchy;

calculating, at each node within the hierarchy of nodes receiving communicated state data from its children nodes, a new data update period for the receiving node using the current data update periods in the communicated state data if all summations of the current data update periods communicated in the state data for any path from the parent node of the receiving node to any descendent leaf node are equal;

picking, for each node where all of the summations of the current data update periods communicated in the state data for any path from the parent node of the receiving node to any descendent leaf node are not equal, an arbitrary child node of that 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 of that node;

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

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

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

making adjustments to the state data received at the root node to ensure that the maximum period of use is not exceeded at every leaf node of the root node; and

communicating adjustments to the state data down through the tree hierarchy to each leaf node.