Resynchronization of multiple copies of a database after a divergence in transaction history

• US 7,457,829 B2
• Filed: 06/23/2003
• Issued: 11/25/2008
• Est. Priority Date: 06/23/2003
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: East, Jeffrey A., Marinescu, Andrei, Zwilling, Michael I.
• Primary Examiner(s): Pardo; Thuy N
• Application Number:
  US10/602,283
• Publication Number:
  US 20040267809A1
• Time in Patent Office: 1,982 Days
• Field of Search: 707/2, 707/10, 707/202, 707/101, 709/203, 709/213, 714/37
• 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

Abstract

The resynchronization of multiple copies of a database after a divergence in transaction history in provided. In an illustrative implementation, algorithms are provided for synchronizing multiple copies of a database upon the occurrence of a divergence in transaction history. A data environment is provided having a database and a copy. The database environment operating in a manner where the database records some transactions and the copy recording some later transactions, but neither having an up-to-date set of data or log of data changes. In operation, the database and its copy compare transaction log sequence numbers to discern the changes database and/or database copy pages. During resynchronization, the database and/or its copy sends page specific information about changes that have not been performed on each other respectively. In this manner, the data environment may be resynchronized with minimal data transmitted and without a requiring a complete restoration of the database.

Claims

1. A method for resynchronizing multiple copies of a database after a divergence in transaction history, the database, D1, and its copies, D1′

, having database pages, logs, and log records, comprising;

identifying a point when the divergence in transaction history occurred using the database and database copy logs, the point represented by a fail over log sequence number (FOLSN), wherein the divergence in transaction history comprises at least one of;

a condition in which D1 fails for a period of time during which D1′

remains

operational, and D1 is brought back online;

or

a condition in which D1 has provided data to the database and the data has not been

received by D1′

; and

processing the database log records created after the divergence in transaction history to populate from D1 to D1′

or from D1′

to D1 changes and identified content, the log records having log sequence numbers for use in processing.

2. The method as recited in claim 1, further comprising setting a maximum page log sequence number (MPLSN) to equal the FOLSN.

3. The method as recited in claim 2, further comprising performing a scan of the log of either of D1 or D1′

to obtain a first log record that occurs after the FOLSN until an end-of-log on either of D1 or D1′

is reached.

4. The method as recited in claim 3, further comprising checking to determine if there is a log record to analyze.

5. The method as recited in claim 4, further comprising replaying log records on D1 starting with log records occurring before an identified last checkpoint before the FOLSN and continuing to the FOLSN.

6. The method as recited in claim 5, further comprising removing the log records after the FOLSN from either of D1 or D1′

.

7. The method as recited in claim 6, further comprising copying log records from the FOLSN to the MPLSN from D1 to D1′

or from D1′

to D1.

8. The method as recited in claim 7, further comprising performing operations recorded from the FOLSN to the MPLSN on D1 or D1′

pages.

9. The method as recited in claim 8, further comprising preventing the use of D1 or D1′

until the operations of claim 8 are completed.

10. The method as recited in claim 9, further comprising clearing a MPLSN value.

11. The method as recited in claim 10, further comprising recovering D1 and/or D1′

.

12. The method as recited in claim 11, further comprising catching up D1 with D1′

or vice versa.

13. The method as recited in claim 4, further comprising determining if the log record occurring after the FOLSN is a page format log record.

14. The method as recited in claim 4, further comprising determining if the log record occurring after the FOLSN is a page update log record.

15. The method as recited in claim 14, further comprising comparing a previous page log sequence number (PPLSN) of the log record occurring after the FOLSN with the FOLSN.

16. The method as recited in claim 15, further comprising upon determining that the PPLSN is less than the FOLSN, retrieving current contents of the D1 pages or D1′

pages.

17. The method as recited in claim 16, further comprising determining if the D1 pages or D1′

pages are de-allocated.

18. The method as recited in claim 17, further comprising sending a dummy page from D1 to D1′

or from D1′

to D1 with a page LSN (PLSN) field of the log record set in a current end-of-log (EOL) log sequence number on D1 or D1′

.

19. The method as recited in claim 18, setting a value of the MPLSN to the value of the PLSN if the PLSN is larger than the MPLSN.

20. The method of claims 13, 14, or 19, further comprising obtaining a next log record.

21. A computer readable medium having computer readable instructions to instruct a computer to perform the method as recited in claim 1.

22. A system for resynchronization of a database having multiple copies after an occurrence of a divergence in transaction history comprising:

database log records, the database log records comprising log sequence numbers representative of database operations and transactions;

a means for identifying a point of the divergence in transaction history, operating on the database log records and log sequence numbers to identify the divergence in transaction history, wherein the divergence in transaction history comprises at least one of;

a condition in which D1 fails for a period of time during which D1′

remains

operational, and D1 is brought back online;

or

a condition in which D1 has provided data to the database and the data has not been

received by D1′

; and

a means for comparing information about the log records, the means for comparing using page sequence numbers and fail over sequence numbers to determine if changes have been made to the log records after the divergence in transaction history.

23. The system as recited in claim 22, wherein the means for identifying comprises a computing application.

24. The system as recited in claim 22, wherein the means for comparing information comprises a computing application.

25. A method for resynchronizing multiple copies of a database after a divergence in transaction history, the database, D1 operating on server computer S1, and its copies, D1′

operating on server computers S2, having database pages, logs, and log records, comprising;

identifying the divergence in transaction history, the divergence represented by a log sequence number (LSN), wherein the divergence in transaction history comprises at least one of;

a condition in which D1 fails for a period of time during which D1′

remains

operational, and D1 is brought back online;

or

a condition in which D1 has provided data to the database and the data has not been

received by D1′

;

on the server computer being recovered, scanning a log file to identify a set of pages to be replaced;

replacing those pages on the server computer being recovered with their images from a non-recovering server computer;

rolling forward a transaction log from a last checkpoint through a failover LSN on any of those pages being replaced on the server computer being recovered;

copying the log and log records from the non-recovering server computer from the failover LSN to a maximum LSN; and

replaying the copied log records.

26. A method for resynchronizing multiple copies of a database after a divergence in transaction history, the database, D1, and its copies, D1′

, having database pages, logs, and log records, comprising;

identifying a point when the divergence in transaction history occurred using the database and database copy logs, the divergence represented by a fail over log sequence number (FOLSN), wherein the divergence in transaction history comprises at least one of;

a condition in which D1 fails for a period of time during which D1′

remains

operational, and D1 is brought back online;

or

a condition in which D1 has provided data to the database and the data has not been

received by D1′

;

creating a list of pages having been changed; and

processing the database log records created after the divergence in transaction history to populate from D1 to D1′

or from D1′

to D1 changes and identified content, the log records having log sequence numbers for use in processing.

27. The method as recited in claim 26, further comprising setting the MPLSN to equal the FOLSN.

28. The method as recited in claim 27, further comprising creating an in-memory hash table, the in-memory hash table having data identifying database pages which have changed.

29. The method as recited in claim 28, further comprising scanning the log of D1 or D1′

to obtain a first log record occurring after the FOLSN, wherein the scan is performed until an end-of-log (EOL) log sequence number is encountered.

30. The method as recited in claim 29, further comprising performing a check to determine if there is a log record to process.

31. The method as recited in claim 30, further comprising upon determining there are no log records to process, looping over the pages found in the Changed Page Table (CPT) and copying them to D1 or D1′

.

32. The method as recited in claim 31, further comprising sending a dummy page and dummy ID by D1 to D1′

or from D1′

to D1, the dummy page having a page LSN (PLSN) being set to the EOL LSN on D1 or D1′

.

33. The method as recited in claim 32, further comprising determining the MPLSN returned on pages from D1 or D1′

and store it in the MPLSN.

34. The method as recited in claim 33, further comprising replaying the log records on D1 or D1′

starting with a last checkpoint before the FOLSN and continuing to the FOLSN.

35. The method as recited in claim 34, further comprising removing log records occurring after the FOLSN from D1 or D1′

.

36. The method as recited in claim 35, further comprising copying the log records from the FOLSN to the MPLSN from D1 to D1′

or D1′

to D1.

37. The method as recited in claim 36, further comprising re-performing operations recorded from the FOLSN to the MPLSN on D1 or D1′

pages.

38. The method as recited in claim 37, further comprising preventing the use of D1 or D1′

until the operations of claim 37 are completed.

39. The method as recited in claim 38, further comprising clearing a MPLSN value.

40. The method as recited in claim 39, further comprising recovering D1 and/or D1′

.

41. The method as recited in claim 40, further comprising performing log shipping between D1 and D1′

.

42. The method as recited in claim 30, further comprising determining if the log record is a page format record.

43. The method as recited in claim 42, further comprising determining if the log record is a page update log record.

44. The method as recited in claim 43, further comprising determining if the page is in the Changed Page Table (CPT).

45. The method as recited in claim 44, further comprising placing a page ID in the Changed Page Table (CPT).

46. The method as recited in claim 30, 43, or 44, further comprising obtaining a next log record.