Data synchronization and consistency across distributed repositories

• US 8,260,742 B2
• Filed: 04/03/2009
• Issued: 09/04/2012
• Est. Priority Date: 04/03/2009
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Cognigni, Giorgio, Gangemi, Rosario, Villani, Massimo
• Primary Examiner(s): Bétit, Jacob F
• Assistant Examiner(s): Shanmugasundaram, Kannan
• Application Number:
  US12/418,187
• Publication Number:
  US 20100257149A1
• Time in Patent Office: 1,250 Days
• Field of Search: None
• US Class Current: 707/620
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor

Abstract

Data associated with the services in a service oriented architecture are stored in a primary repository and replicated across secondary repositories. Functionality can be implemented to efficiently synchronize data across the primary repository and the secondary repositories. Data synchronization can comprise calculating and comparing hash values of one or more nodes, based in part on concatenated hash values of child nodes and data that comprise the one or more nodes, of a tree structure representing data stored in the repositories.

Claims

1. A method comprising:

retrieving a first hash value of a first root node in a first tree structure associated with a first secondary repository, wherein the first secondary repository comprises a first machine-readable storage medium encoded with the first tree structure, wherein the first root node is associated with a first plurality of data units and comprises a first plurality of hash values, wherein the first plurality of hash values were computed from the first plurality of data units, wherein the first hash value is computed based on the first plurality of hash values and a second plurality of hash values of child nodes of the first root node;

retrieving a second hash value of a second root node in a second tree structure associated with a primary repository, wherein the primary repository comprises a second machine-readable storage medium encoded with the second tree structure, wherein the second root node is associated with a second plurality of data units and comprises a third plurality of hash values computed from the second plurality of data units, wherein the second hash value is computed based on the third plurality of hash values and a fourth plurality of hash values of child nodes of the second root node;

comparing the first hash value and the second hash value;

determining that the first hash value is not equal to the second hash value;

comparing the first plurality of hash values against respective ones of the third plurality hash values;

for each hash value of the first plurality of hash values that does not match a respective one of the third plurality of hash values, modifying a data unit of the first plurality of data units, which was used to compute the hash value of the first plurality of hash values, in the first secondary repository to be synchronized with a data unit of the second plurality of data units, which was used to compute the respective one of the third plurality of hash values, of the primary repository;

retrieving a first of the second plurality of hash values of a first child node of the first root node in the first tree structure and a first of the fourth plurality of hash values of a second child node of the second root node in the second tree structure, wherein the first child node is associated with a third plurality of data units and the second plurality of hash values were computed from at least the third plurality of data units, and the second child node is associated with a fourth plurality of data units and the fourth plurality of hash values were computed from at least the forth plurality of data units;

comparing the first of the second plurality of hash values and the first of the fourth plurality of hash values;

determining whether the first of the second plurality of hash values and the first of the fourth plurality of hash values are not equal;

comparing a fifth plurality of hash values computed from the third plurality of data units with respective ones of a sixth plurality of hash values computed from the fourth plurality of data units to detect inconsistencies responsive to determining that the first of the second plurality of hash values and the first of the fourth plurality of hash values are not equal;

synchronizing the third plurality of data units to be consistent with the fourth plurality of data units in accordance with inconsistencies detected from said comparing the fifth plurality of hash values with respective ones of the sixth plurality of hash values; and

indicating that the primary repository and the first secondary repository are synchronized after determining others of the second plurality of hash values are equal to respective ones of the fourth plurality of hash values.

2. The method of claim 1, wherein for each hash value of the first plurality of hash values that does not match a respective one of the third plurality of hash values, the modifying the data unit of the first plurality of data units in the first secondary repository to be synchronized with the data unit of the second plurality of data units of the primary repository comprises:

for each hash value of the first plurality of hash values that does not match a respective one of the third plurality of hash values, directing the primary repository to transfer the data unit of the second plurality of data units of the primary repository to the first secondary repository.

3. The method of claim 1, wherein the tree structure comprises a B-tree.

4. The method of claim 1, wherein for each hash value of the first plurality of hash values that does not match a respective one of the third plurality of hash values, said modifying the data unit of the first plurality of data units in the first secondary repository to be synchronized with the data unit of the second plurality of data units of the primary repository comprises one of inserting the data unit of the second plurality of data units, deleting the data unit of the first plurality of data units, and modifying the data unit of the first plurality of data units.

5. The method of claim 1, wherein

the first hash value is a hash of a concatenation of the second plurality of hash values of the child nodes of the first root node and the first plurality of hash values of the first plurality of data units associated with the first root node, and

the second hash value is a hash of a concatenation of the fourth plurality of hash values of the child nodes of the second root node and the third plurality of hash values of the second plurality of data units associated with the second root node.

6. The method of claim 1 further comprising:

computing a hash of a concatenation of the second plurality of hash values of the child nodes of the first root node, modified hash values of the first plurality of hash values of the modified data units of the first plurality of data units, and other of the first plurality of hash values to generate a recomputed first hash value based on said for each hash value of the first plurality of hash values that does not match a respective one of the third plurality of hash values, modifying a data unit of the first plurality of data units in the first secondary repository to be synchronized with a data unit of the second plurality of data units of the primary repository.

7. The method of claim 1, further comprising:

receiving an indication that a second secondary repository is registered with the primary repository;

transmitting, to the second secondary repository, a common data model and a hash model.

8. The method of claim 7 further comprising the primary repository storing data in accordance with the common data model and the secondary repository storing data in accordance with the common data model.

9. The method of claim 7, further comprising the primary repository and the secondary repository calculating hash values in accordance with a hash algorithm indicated in the hash model.

10. The method of claim 9, further comprising the primary repository and the secondary repository calculating the hash values based on an input to the hash algorithm indicated in the hash model.

11. A computer program product comprising a non-transitory computer readable storage medium having computer readable code embodied therewith, said computer readable code configured to:

retrieve a first hash value of a first root node in a first tree structure associated with a first secondary repository, wherein the first root node is associated with a first plurality of data units and comprises a first plurality of hash values, wherein the first plurality of hash values were computed from the first plurality of data units, wherein the first hash value is computed based on the first plurality of hash values and a second plurality of hash values of child nodes of the first root node;

retrieve a second hash value of a second root node in a second tree structure associated with a primary repository, wherein the second root node is associated with a second plurality of data units and comprises a third plurality of hash values computed from the second plurality of data units, wherein the second hash value is computed based on the third plurality of hash values and a fourth plurality of hash values of child nodes of the second root node;

compare the first hash value and the second hash value;

determine that the first hash value is not equal to the second hash value;

compare the first plurality of hash values against respective ones of the third plurality hash values;

for each hash value of the first plurality of hash values that does not match a respective one of the third plurality of hash values, cause modification of a data unit of the first plurality of data units, which was used to compute the hash value of the first plurality of hash values, in the first secondary repository to be synchronized with a data unit of the second plurality of data units, which was used to compute the respective one of the third plurality of hash values, of the primary repository;

retrieve a first of the second plurality of hash values of a first child node of the first root node in the first tree structure and a first of the fourth plurality of hash values of a second child node of the second root node in the second tree structure, wherein the first child node is associated with a third plurality of data units and the second plurality of hash values were computed from at least the third plurality of data units, and the second child node is associated with a fourth plurality of data units and the fourth plurality of hash values were computed from at least the forth plurality of data units;

compare the first of the second plurality of hash values and the first of the fourth plurality of hash values;

determine whether the first of the second plurality of hash values and the first of the fourth plurality of hash values are not equal;

compare a fifth plurality of hash values computed from the third plurality of data units with respective ones of a sixth plurality of hash values computed from the fourth plurality of data units to detect inconsistencies responsive to the computer readable code determining that the first of the second plurality of hash values and the first of the fourth plurality of hash values are not equal;

cause synchronization of the third plurality of data units to be consistent with the fourth plurality of data units in accordance with inconsistencies detected from the computer readable code comparing the fifth plurality of hash values with respective ones of the sixth plurality of hash values; and

indicate that the primary repository and the first secondary repository are synchronized after determining others of the second plurality of hash values are equal to respective ones of the fourth plurality of hash values.

12. The computer program product of claim 11, wherein for each hash value of the first plurality of hash values that does not match a respective one of the third plurality of hash values, the computer readable code configured to cause modification of the data unit of the first plurality of data units in the first secondary repository to be synchronized with the data unit of the second plurality of data units of the primary repository comprises the computer readable code being configured to,

for each hash value of the first plurality of hash values that does not match a respective one of the third plurality of hash values, direct the primary repository to transfer the data unit of the second plurality of data units of the primary repository to the first secondary repository.

13. The computer program product of claim 11, wherein the computer readable code further comprises:

computer readable code configured to receive an indication that a secondary repository is registered with the data repository; and

computer readable code configured to transmit, to the secondary data repository, a common data model and a hash model to which the data repository conforms.

14. The computer program product of claim 13, wherein the computer readable code further comprises computer readable code configured to cause the data repository and the secondary data repository to store data in accordance with the common data model.

15. The computer program product of claim 13, wherein the computer readable code further comprises computer readable code configured to cause the data repository and the secondary data repository to calculate hash values in accordance with a hash algorithm indicated in the hash model.

16. An apparatus comprising:

a processor unit;

a memory unit coupled to the processor unit; and

a synchronization unit configured to

retrieve a first hash value of a first root node in a first tree structure associated with a secondary repository, wherein the first root node is associated with a first plurality of data units and comprises a first plurality of hash values, wherein the first plurality of hash values were computed from the first plurality of data units, wherein the first hash value is computed based on the first plurality of hash values and a second plurality of hash values of child nodes of the first root node;

retrieve a second hash value of a second root node in a second tree structure associated with a primary repository, wherein the second root node is associated with a second plurality of data units and comprises a third plurality of hash values computed from the second plurality of data units, wherein the second hash value is computed based on the third plurality of hash values and a fourth plurality of hash values of child nodes of the second root node;

compare the first hash value and the second hash value;

determine that the first hash value is not equal to the second hash value;

compare the first plurality of hash values against respective ones of the third plurality hash values;

for each hash value of the first plurality of hash values that does not match a respective one of the third plurality of hash values, modify a data unit of the first plurality of data units, which was used to compute the hash value of the first plurality of hash values, in the first secondary repository to be synchronized with a data unit the first of the second plurality of data units, which was used to compute the respective one of the third plurality of hash values, of the primary repository;

retrieve a first of the second plurality of hash values of a first child node of the first root node in the first tree structure and a first of the fourth plurality of hash values of a second child node of the second root node in the second tree structure, wherein the first child node is associated with a third plurality of data units and the second plurality of hash values were computed from at least the third plurality of data units, and the second child node is associated with a fourth plurality of data units and the fourth plurality of hash values were computed from at least the forth plurality of data units;

compare the first of the second plurality of hash values and the first of the fourth plurality of hash values;

determine whether the first of the second plurality of hash values and the first of the fourth plurality of hash values are not equal;

compare a fifth plurality of hash values computed from the third plurality of data units with respective ones of a sixth plurality of hash values computed from the fourth plurality of data units to detect inconsistencies responsive to determining that the first of the second plurality of hash values and the first of the fourth plurality of hash values are not equal;

synchronize the third plurality of data units to be consistent with the fourth plurality of data units in accordance with inconsistencies detected from said comparing the fifth plurality of hash values with respective ones of the sixth plurality of hash values; and

indicate that the primary repository and the first secondary repository are synchronized after determining others of the second plurality of hash values are equal to respective ones of the fourth plurality of hash values.

17. The apparatus of claim 16, wherein the synchronization unit comprises a machine-readable storage medium.