DATA SYNCHRONIZATION AND CONSISTENCY ACROSS DISTRIBUTED REPOSITORIES

• US 20100257149A1
• Filed: 04/03/2009
• Published: 10/07/2010
• Est. Priority Date: 04/03/2009
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Cognigni, Giorgio, Villani, Massimo, Gangemi, Rosario
• Granted Patent: US 8,260,742 B2
• Time in Patent Office: Days
• US Class Current: 707/698
• 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;

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;

comparing the first hash value and the second hash value;

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

retrieving a third hash value of a first data unit associated with the first root node and a fourth hash value of a second data unit associated with the second root node, wherein the first data unit is stored in the first secondary repository and the second data unit is stored in the primary repository;

comparing the third and the fourth hash values;

determining that the third hash value is not equal to the fourth hash value; and

modifying the first data unit in the first secondary repository to be synchronized with the second data unit of the primary repository.

2. The method of claim 1, wherein the modifying the first data unit in the first secondary repository comprises:

directing the primary repository to transfer the second data unit 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, further comprising:

retrieving a fifth hash value of a first child node of the first root node in the first tree structure and a sixth hash values of a second child node of the second root node in the second tree structure;

comparing the fifth hash value and the sixth hash value;

determining that the fifth hash value is not equal to the sixth hash value;

retrieving a seventh hash value of a third data unit associated with the first child node and an eighth hash value of a fourth data unit associated with the second child node, wherein the third data unit is stored in the first secondary repository and the fourth data unit is stored in the primary repository;

comparing the seventh and the eighth hash values;

determining that the seventh hash value is not equal to the eighth hash value; and

modifying the third data unit in the first secondary repository to be synchronized with the fourth data unit of the primary repository.

5. The method of claim 1, wherein said modifying the first data unit in the first secondary repository to be synchronized with the second data unit of the primary repository comprises one of inserting the second data unit, deleting the first data unit, and modifying the first data unit.

6. The method of claim 1 further comprising computing a hash of a concatenation of hash values of child nodes that comprise the root node and hash values of data units associated with the root node to generate the first hash value.

7. The method of claim 1 further comprising

computing a hash of a concatenation of hash values of child nodes that comprise the root node and the hash values of at least the modified first data unit to generate a recomputed the first hash value based on said modifying the first data unit in the first secondary repository to be synchronized with the second data unit of the primary repository.

8. A method comprising:

retrieving a first hash value associated with a first root node in a first tree structure of a secondary repository, wherein the secondary repository comprises a first machine-readable storage medium encoded with the first tree structure;

comparing the first retrieved hash value with a second hash value, wherein the second hash value is associated with a second root node in a second tree structure of a primary repository, wherein the primary repository comprises a second machine-readable storage medium encoded with the second tree structure;

determining that the first and the second hash values are equal; and

generating an indication that the primary repository and the secondary repository are synchronized.

9. The method of claim 8, 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.

10. The method of claim 9 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.

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

12. The method of claim 11, 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.

13. A computer program product comprising a computer readable storage medium having computer readable code embodied therewith, said computer readable code comprising:

computer readable code configured to generate a tree structure, comprising a set of nodes, associated with a data repository based, at least in part, on a set of data units of the data repository, wherein the set of nodes comprises a first node associated with at least a first and a second data unit of the data repository and a second node that is a child of the first node;

computer readable code configured to compute a hash of a concatenation of hash values of at least a third and a fourth data unit of the data repository to generate a first hash value of the second node, wherein the second node is associated with at least the third and the fourth data units of the data repository;

computer readable code configured to compute a hash of a concatenation of the first hash value of the second node and the hash values of the first and the second data units of the data repository to generate a second hash value of the first node; and

computer readable code configured to associate the second hash value with the first node.

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

computer readable code configured to determine if the second hash value of the first node matches a third hash value of a third node of a second tree structure of a secondary data repository, wherein the third node is associated with a first plurality of data units of the secondary data repository and wherein the data repository comprises a primary data repository that corresponds to the secondary data repository;

computer readable code configured to determine if the hash values of the first and second data units match hash values of the first plurality of data units if the second and the third hash values do not match;

computer readable code configured to cause synchronization of the first node and the third node if the hash values of the first and second data units do not match the hash value of the first plurality of data units;

computer readable code configured to determine if the first hash value and a fourth hash value match if the hash value of the first and second data units match the hash values of the first plurality of data unit and the second and the third hash values do not match, wherein the fourth hash value is associated with a fourth node in the second tree structure and the fourth node corresponds to the second node; and

computer readable code configured to cause synchronization of the second node and the fourth node if the first hash value and the fourth hash value do not match, wherein the second node has no children

15. The computer program product of claim 14, wherein the computer readable code configured to cause synchronization of the first node and the third node comprises the computer readable code being configured to,

direct the secondary data repository to be modified to conform to the primary data repository with respect to the first and second data units and the first plurality of data units.

16. The computer program product of claim 14, 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.

17. The computer program product of claim 16, 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.

18. The computer program product of claim 16, 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.

19. 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;

retrieve a second hash value of a second root node in a second tree structure associated with a primary repository;

compare the first hash value and the second hash value;

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

retrieve a third hash value of a first data unit associated with the first root node and a fourth hash value of a second data unit associated with the second root node, wherein the first data unit is stored in the secondary repository and the second data unit is stored in the primary repository;

compare the third and the fourth hash values;

determine that the third hash value is not equal to the fourth hash value; and

modify the first data unit in the secondary repository to be synchronized with the second data unit of the primary repository.

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