One-way hash functions for distributed data synchronization

• US 6,470,329 B1
• Filed: 07/11/2000
• Issued: 10/22/2002
• Est. Priority Date: 07/11/2000
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Livschitz, Victoria V.
• Primary Examiner(s): Shah, Sanjiv
• Application Number:
  US09/613,642
• Time in Patent Office: 833 Days
• Field of Search: 707/1, 707/2, 707/6, 707/7, 707/10, 707/200, 707/201, 707/203, 707/101, 341/50, 342/127, 340/825.2, 709/248, 380/251, 380/259, 713/400
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2322 using timestamps
• CPC Class Codes: G06F 16/273 Asynchronous replication or reconciliation
• CPC Class Codes: G06F 16/9014 hash tables
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

A method for synchronizing two data sets includes computing a signature for a first data set in a first address space and a signature for a second data set in a second address space using a one-way hash function and comparing the signatures for the first and second data sets to determine whether they are identical. If the signatures are not identical, the method further includes identifying an area of difference between the first data set and the second data set and transferring data corresponding to the area of difference between the first data set and the second data set from the first data set to the second data set.

Claims

1. A method for synchronizing two data sets, comprising:

computing a signature for a first data set in a first address space and a signature for a second data set in a second address space using a one-way hash function;

comparing the signatures for the first and second data sets to determine whether they are identical; and

if the signatures are not identical, identifying an area of difference between the first data set and the second data set and transferring data corresponding to the area of difference between the first data set and the second data set from the first data set to the second data set.

2. The method of claim 1, wherein comparing the signatures for the first and second data sets to determine whether they are identical includes transferring the signature for the first data set from the first address space to the second address space.

3. The method of claim 1, wherein identifying an area of difference between the first data set and the second data set comprises dividing the first data set into at least two data blocks and the second data set into at least two data blocks and pairing each data block in the first data set with a corresponding data block in the second data set.

4. The method of claim 3, wherein identifying an area of difference between the first data set and the second data set further comprises identifying an area of difference between each pair of data blocks by computing the signature for each data block in the pair of data blocks using a one-way hash function and comparing the signature for the data blocks in the pair of data blocks to determine whether they are identical.

5. The method of claim 4, wherein comparing the signature for the data blocks in the pair of data blocks includes transferring the signatures of each data block divided out of the first data set from the first address space to the second address space.

6. The method of claim 4, wherein identifying an area of difference between each pair of data blocks further comprises eliminating the pair of data blocks from further consideration if the signatures of the data blocks in the pair of data blocks are identical.

7. The method of claim 6, wherein identifying an area of difference between each pair of data blocks further comprises checking the size of the data blocks in the pair of data blocks if the signatures are not identical to determine whether the data blocks are elementary data blocks.

8. The method of claim 7, wherein identifying an area of difference between each pair of data blocks further comprises subdividing each data block in the pair of data blocks into at least two data blocks if the data block is not an elementary data block and pairing each data block in the first of the pair of data blocks with a corresponding data block in the second of the pair of data blocks.

9. The method of claim 8, wherein identifying an area of difference between each pair of data blocks further comprises repeating identifying an area of difference between each pair of data blocks until all the remaining data blocks are elementary data blocks.

10. The method of claim 9, wherein transferring data corresponding to the areas of differences between the first data set and the second data set includes transferring the elementary data blocks from the first data set to the second data set.

11. A method for synchronizing two data sets, comprising:

computing a signature for a first data set in a first address space and a signature for a second data set in a second address space using a one-way hash function;

comparing the signatures for the first and second data sets to determine whether they are identical; and

if the signatures are not identical, dividing the first data set into two data blocks and the second data set into two data blocks, pairing each data block in the first data set with a corresponding data block in the second data set, and identifying an area of difference for each pair of data blocks by

computing the signature for each data block in the pair of data blocks using the one-way hash function and comparing the signature of the data blocks in the pair of data blocks to determine whether they are identical,

eliminating the pair of data blocks from further consideration if the signatures are identical,

checking the size of the data blocks to determine whether the data blocks are elementary data blocks if the signatures are not identical,

subdividing each data block into two data blocks and pairing each data block in the first of the pair of data blocks with a corresponding data block in the second of the pair of data blocks if the data blocks are not elementary data blocks,

repeating identifying an area of difference for each pair of data blocks until all remaining data blocks are elementary data blocks; and

transferring the elementary data blocks from the first data set to the second data set.

12. The method of claim 11, wherein comparing the signatures for the first and second data sets to determine whether they are identical includes transferring the signature for the first data set from the first address space to the second address space.

13. The method of claim 11, wherein comparing the signature of the data blocks includes transferring the signatures of each data block divided out of the first data set from the first address space to the second address space.

14. A method for synchronizing two data sets, comprising:

subdividing a first data set in a first address space and a second data set in a second address space into their respective elementary data blocks;

computing a signature for each elementary data block using a one-way hash function and storing the signatures of the elementary data blocks in the first data set in a first array and the signatures of the elementary data blocks in the second data set in a second array; and

comparing each signature in the first array to a corresponding signature in the second array to determine whether they are identical and, if they are not identical, transferring the corresponding data block from the first data set to the second data set.

15. The method of claim 14, wherein comparing each signature in the first array to a corresponding signature in the second array to determine whether they are identical includes transferring the first array from the first address space to the second address space.

16. A method for synchronizing two data sets, the method comprising:

subdividing a first data set in a first address space and a second data set in a second address space into their respective elementary data blocks;

computing a signature for each elementary data block using a first one-way hash function and storing the signatures of the elementary data blocks in the first data set in a first array and the signatures of the elementary data blocks in the second data set in a second array;

computing a signature for the first array and a signature for the second array using a second one-way hash function and comparing the signatures for the first and second arrays to determine whether they are identical;

if the signatures for the first and second arrays are not identical, identifying the unique signatures in the first and second arrays; and

transferring the elementary data blocks corresponding to the unique signatures from the first data set to the second data set.

17. The method of claim 16, wherein identifying the unique signatures in the first and second arrays comprises dividing the first array into two sub-arrays and the second array into two sub-arrays and pairing each sub-array from the first array with a corresponding sub-array from the second array.

18. The method of claim 16, further comprising identifying the area of difference between each pair of sub-arrays by computing the signature for each sub-array in the pair of sub-arrays using the second one-way hash function and comparing the signature of the sub-arrays in the pair of sub-arrays to determine whether they are identical.

19. The method of claim 18, wherein comparing the signature of the sub-arrays in the pair of sub-arrays includes transferring the signatures of each sub-array derived from the first array from the address space of the first data set to the address space of the second data set.

20. The method of claim 19, wherein identifying the area of difference between each pair of sub-arrays further comprises eliminating the pair of sub-arrays from further consideration if the signatures of the sub-arrays in the pair of sub-arrays are identical.

21. The method of claim 20, wherein identifying the area of difference between each pair of sub-arrays further comprises checking the size of the sub-arrays in the pair of sub-arrays if the signatures are not identical to determine whether the sub-arrays have more than one element.

22. The method of claim 21, wherein identifying the area of difference between each pair of sub-arrays further comprises subdividing each sub-array into two sub-arrays if the sub-array has more than one element and pairing each sub-array in the first of the pair of sub-arrays with a corresponding sub-array in the second of the pair of sub-arrays.

23. The method of claim 22, wherein identifying the unique signatures in the first and second arrays further comprises repeating identifying the area of difference between each pair of sub-arrays until all the remaining sub-arrays have only one element.

24. The method of claim 23, wherein transferring the elementary data blocks corresponding to the unique signatures from the first data set to the second data set includes identifying the elementary data blocks in the first data set which correspond to the remaining sub-arrays and transferring the elementary data blocks from the first data set to the second data set.

25. A data synchronization system, comprising:

a first agent having access to a first data set in a first address space;

a second agent having access to a second data set in a second address space; and

an engine which communicates with the first agent and the second agent when activated, the engine being configured to;

send a request to the first agent to compute a signature for the first data set in the first address space and a request to the second agent to compute a signature for the second data in the second address space using a one-way hash function;

transfer the signature for the first data set from the first address space to the second address space and send a request to the second agent to determine whether the signature for the first data set is identical to the signature for the second data set; and

identify an area of difference between the first data set and the second data set in collaboration with the first and second agents if the signatures of the data sets are not identical and, upon identifying the area of difference between the data sets, transfer data corresponding to the area of difference between the data sets from the first address space to the second address space and copy the data into the second data set.

26. The data synchronization system of claim 25, wherein the first agent, the second agent, and the engine each comprise a set of computer-executable instructions.

27. A data synchronization system, comprising:

a first agent having access to a first data set in a first address space;

a second agent having access to a second data set in a second address space; and

an engine which communicates with the first agent and the second agent when activated, the engine being configured to;

send a request to the first agent to subdivide the first data set into elementary data blocks, to compute a signature for each elementary data block using a one-way hash function, and to store the signatures of the elementary data blocks in a first array;

send a request to the second agent to subdivide the second data set into elementary data blocks, to compute a signature for each elementary block using the one-way hash function, and to store the signatures of the elementary data blocks in a second array;

transfer the first array from the first address space to the second address space and send a request to the second agent to compare each signature in the first array to a corresponding signature in the second array to determine whether they are identical and, if they are not identical, transfer the corresponding data block from the first data set to the second data set.

28. The data synchronization system of claim 27, wherein the first agent, the second agent, and the engine each comprise a set of computer-executable instructions.

29. A data synchronization system, comprising:

a first agent having access to a first data set in a first address space;

a second agent having access to a second data set in a second address space; and

an engine which communicates with the first agent and the second agent when activated, the engine being configured to;

send a request to the first agent to subdivide the first data set into elementary data blocks, to compute a signature for each elementary data block using a first one-way hash function, to store the signatures of the elementary data blocks in a first array, and to compute a signature for the first array using a second one-way hash function;

send a request to the second agent to subdivide the second data set into elementary data blocks, to compute the a signature for each elementary block using the first one-way hash function, to store the signatures of the elementary data blocks in a second array, and to compute a signature for the second array using the second one-way hash function;

transfer the signature for the first array from the first address space to the second address space and send a request to the second agent to determine whether the signature for the first array is identical to the signature for the second array; and

identify an area of difference between the first array and the second array in collaboration with the first and second agents if the signatures of the arrays are not identical and, upon identifying the area of difference between the arrays, transfer data corresponding to the area of difference between the arrays from the first address space to the second address space and copy the data into the second data set.

30. The data synchronization system of claim 29, wherein the first agent, the second agent, and the engine each comprise a set of computer-executable instructions.