Data recovery in a distributed system

• US 7,231,408 B2
• Filed: 07/24/2002
• Issued: 06/12/2007
• Est. Priority Date: 01/28/2000
• Status: Expired due to Fees

• Current Assignee: Nokia Solutions and Networks US LLC (Nokia Corporation)
• Original Assignee: Nokia Corporation
• Inventors: Belcaid, Adel, Lahdensuo, Kari
• Primary Examiner(s): Wong; Don
• Assistant Examiner(s): Black; Linh
• Application Number:
  US10/201,627
• Publication Number:
  US 20030065685A1
• Time in Patent Office: 1,784 Days
• Field of Search: 707 1-202, 707/203
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1658 Data re-synchronization of a redundant component, or initial sync of replacement, additional or spare unit
• CPC Class Codes: G06F 11/2038 with a single idle spare processing component
• CPC Class Codes: G06F 11/2048 where the redundant components share neither address space nor persistent storage
• 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
• CPC Class Codes: G06F 2201/80 Database-specific techniques
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

In a distributed system, where data is maintained in at least two databases and the data includes at least one data element, the amount of data transmitted during data recovery is minimized by comparing a first total of the data elements of the data in a first database with a second total of a corresponding data elements of corresponding data in a second database. An updating procedure for the data element is initiated if the first total and the second total are not the same.

Claims

1. A method for recovering data in a distributed system where the data is maintained in at least two databases, one of the databases being a master database and at least one other database being a slave database, and the data comprises at least one data element, the method comprising:

initiating recovery of the data;

calculating during the recovery a first total from the data in a first database and a second total from a corresponding data in a second database;

comparing the first total with the second total;

if the first total and the second total are the same, ending the recovery of the data;

if the first total and the second total are not the same, the method further comprises during the recovery;

a) dividing the data and the corresponding data into at least two smaller data groups according to a predetermined rule;

b) calculating a third total for each data group in the first database and a fourth total for each corresponding data group in the second database;

c) comparing for each data group the third total with the fourth total; and

d) deducing on the basis of this comparison in which data group or data groups updating is needed.

2. A method as claimed in claim 1, wherein for each data element in a data group needing updating, the method further comprises:

e) comparing a fifth total of the data element in the first database with a sixth total of a corresponding data element in the second database; and

f) initiating an updating procedure for the data element if the fifth total and the sixth total are not the same.

3. A method as claimed in claim 1, the method further comprising:

e) dividing according to a predetermined rule each data group in the first database needing update and corresponding data group in the second database into at least two smaller data groups;

f) repeating steps b), c) and d) for the smaller data groups;

g) repeating step e) for further subdividing the smaller data groups into further smaller data groups and step f) on these further subdivided data groups until a predetermined condition have been met; and

after that the method further comprises for data elements in those further subdivided data groups found to need updating in the last repetition period;

h) comparing a fifth total of a data element of the data group needing updating in the first database with a sixth total of a corresponding data element in the second database; and

i) initiating an updating procedure for the data element if the fifth total and the sixth total are not the same.

4. A method as claimed in claim 3, wherein if the fifth and sixth totals are not the same, the method further comprises:

comparing a first age indication of the data element of the data group needing update in the first database with a second age indication of the corresponding data element in the second database;

deducing on the basis of this comparison whether the data element should be updated in the first database or in the second database.

5. A method as claimed in claim 3, wherein comparing the fifth total with the sixth total further comprises:

forming in the first database a summary comprising at least an identifier and the fifth total of the data element;

sending the summary to the second database; and

performing the comparison between the fifth and sixth totals in the second database.

6. A method as claimed in claim 5, wherein the summary further comprises a first age indication indicating the age of the data element in the first database;

and the method further comprises;

comparing the first age indication with a second age indication of the corresponding data element in the second database if the fifth total and the sixth total are not the same, the second age indication indicating the age of the corresponding data element in the second database; and

deducing in the second database on the basis of this comparison whether the data element should be updated in the first database or in the second database.

7. A method as claimed in claim 6, the method further comprising:

starting to update the data element from the second database to the first database if the data element should be updated in the first database;

or

sending from the second database to the first database an update indication indicating the data element which should be updated in the second database.

8. A method as claimed in claim 1, wherein the first database is a master database of the data and the second database is a slave database of the data.

9. A method as claimed in claim 1, wherein said comparing and deducing are performed in a third network node to which the first and second database send the totals.

10. A method as claimed in claim 9, further comprising:

sending, from both databases, with the total a corresponding age indication indicating the age of the data the total corresponds to;

comparing a first age indication sent by the first database with a second age indication sent by the second database if the totals are not the same;

deducing on the basis of this comparison whether the data element should be updated in the first database or in the second database.

11. A method as claimed in claim 1, wherein the total is a checksum.

12. A system comprising at least two network nodes, each of which comprises a memory having at least first data, the first data comprising at least one data element, the network nodes being arranged to maintain the first data;

the system being arranged to initiate recovery of the first data;

to calculate, during the recovery of the first data, a first total from the data in a first memory of a first network node and a second total from the corresponding data in a second memory of a second network node;

to compare the first total with the second total; and

if the first total and second total are not the same;

to divide the first data and the corresponding data into at least two smaller data groups according to a predetermined rule;

to calculate a third total for each data group in the first memory and a fourth total for each corresponding data group in the second memory;

to compare for each data group the third total with the fourth total; and

to deduce on the basis of this comparison in which data group or data groups updating is needed.

13. A system as claimed in claim 12, the system being further arranged to compare a first age indication of a data element of the data group needing updating in the first memory with a second age indication of the corresponding data element in the second memory if the third total and fourth total are not the same;

and to deduce on the basis of this comparison whether the data element should be updated in the first memory or in the second memory.

14. A system as claimed in claim 12, the system being further arranged, in response to the third total being different than the fourth total, to divide according to a predetermined rule each data group needing update in the first memory and corresponding data groups in the second memory into at least two smaller data groups;

to calculate a third total from the smaller data group in the first memory and a fourth total from the corresponding smaller data group in the second memory;

to compare for each data group the third total with the fourth total;

to deduce on the basis of this comparison in which data group or data groups updating is needed;

to repeat said division, calculation and deduction for subdivided smaller data groups a until a predetermined condition is met; and

after that the system is further arranged, for data elements in those further subdivided data groups found to need updating in the last repetition period, to compare a fifth total of a data element of the data group needing updating in a first memory with a sixth total of a corresponding data element in the second memory; and

to initiate the updating procedure for the data element if the fifth total and the sixth total are not the same.

15. A system as claimed in claim 12, wherein

the first network node is arranged to form, in response to the recovery of the first data, a summary comprising for a data element of the data group in the first memory at least an identifier and a total;

and to send the summary to the second network node; and

the second network node is arranged to perform said calculation of the corresponding total and said comparison between the totals.

16. A system as claimed in claim 15, wherein

the summary further comprises a first age indication indicating the age of the data element;

and

the second network node is arranged to compare the first age indication with a second age indication of the corresponding data element in the second memory if the compared totals are not the same; and

to deduce on the basis of this comparison whether the data element should be updated in the first memory or in the second memory.

17. A system as claimed in claim 16, wherein

the second network node is arranged to start to update the data element from the second memory to the first memory if the data element should be updated in the first memory.

18. A system as claimed in claim 12, wherein the system further comprises a third network node for performing the comparison of totals and the deduction and the first and second network nodes are arranged to send the totals to the third network node.

19. A network node comprising a memory having at least first data, the first data comprising at least one data element;

the network node being arranged to maintain the first data and to be in connection with a second network node comprising second data corresponding to the first data;

wherein the network node is arranged, in response to receiving a second total of the second data during recovery of the first data, to calculate a first total from the first data;

to compare the second total with the first total; and

to request for third totals if the first total and the second total are not the same; and

, in response to receiving third totals, to divide the first data into at least two smaller data groups according to a predetermined rule;

to calculate a fourth total for each data group;

to compare each fourth total with a corresponding third total; and

to deduce on the basis of this comparison in which data group or data groups updating is needed.

20. A network node in a system where at least first data is maintained in two network nodes;

the network node comprising a memory having at least the first data, the first data comprising at least one data element;

wherein the network node is arranged to maintain the first data and to be in connection with a second network node;

to calculate during recovery of the first data a first total from the first data;

to send the first total to the second network node;

to receive a response from the second network node; and

if the response indicates that further total is required to divide the first data into at least two smaller data groups according to a predetermined rule;

to calculate for each data group a third total; and

send the third totals to the second network node.