Method and apparatus for detecting and recovering from data corruption of a database via read logging

• US 6,449,623 B1
• Filed: 12/09/1998
• Issued: 09/10/2002
• Est. Priority Date: 09/04/1998
• Status: Expired due to Term

• Current Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Rastogi, Rajeev, Bohannon, Philip L., Sudarshan, Sundararajarao, Silberschatz, Abraham, Seshadri, Srinivasan
• Primary Examiner(s): Trammell, James P.
• Assistant Examiner(s): CHEUNG, MARY DA ZHI WANG
• Application Number:
  US09/207,927
• Publication Number:
  US 20020091718A1
• Time in Patent Office: 1,371 Days
• Field of Search: 707/200, 707/202, 707/204
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1471 involving logging of persistent data for recovery
• CPC Class Codes: G06F 11/1474 in transactions G06F16/20 takes precedence
• CPC Class Codes: G06F 2201/80 Database-specific techniques
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

A method of detecting and recovering from data corruption of a database is characterized by the step of logging information about reads of a database in memory to detect errors in data of the database, wherein said errors in data of said database arise from one of bad writes of data to the database, of erroneous input of data to the database by users and of logical errors in code of a transaction. The read logging method may be implemented in a plurality of database recovery models including a cache-recovery model, a prior state model a redo-transaction model and a delete transaction model. In the delete transaction model, it is assumed that logical information is not available to allow a redo of transactions after a possible error and the effects of transactions that read corrupted data are deleted from history and any data written by a transaction reading Ararat data is treated as corrupted.

Claims

1. A method of detecting and recovering from data corruption of a database comprising the steps of logging information about reads of a database to automatically detect and recover from physical corruption of the data in the database using a codeword matching audit algorithm said information about reads comprises one of a start and an end point and length of data read for detection of said physical corruption arising from bad writes of data to the database or corruption arising indirectly therefrom, and maintaining a corrupt transaction table and a corrupt data table for a recovery algorithm.

2. A method of detecting and recovering from data corruption as recited in claim 1 further comprising the step of:

storing data of the database in main volatile memory of a data processor.

3. A method of detecting and recovering from data corruption as recited in claim 1 further comprising the steps of

maintaining a log of writes of the database and combining said log of reads and said log of writes into a combined log of reads and writes.

4. A method of detecting and recovering from data corruption as recited in claim 3 further comprising the step of storing a codeword corresponding to a value of a data item in a record of said combined log of reads and writes.

5. A method of detecting and recovering from data corruption as recited in claim 3, said recovery from data corruption comprising first and second phases, a first redo phase followed by an undo phase.

6. A method as recited in claim 5 wherein said redo phase comprises a forward scan of a log of read and write operations.

7. A method as recited in claim 6 wherein said forward scan adds an identity of data to a corrupt data table whenever said data is written by a corrupt transaction.

8. A method as recited in claim 6 wherein said forward scan adds an identity of data to a corrupt data table whenever said data has failed an audit.

9. A method as recited in claim 6 further comprising the step of maintaining a corrupt transaction table.

10. A method as recited in claim 9 wherein said forward scan adds transactions to said corrupt transaction table that are known corrupt transactions.

11. A method as recited in claim 9 wherein said forward scan adds transactions to said corrupt transaction table whenever data is read that is identified in the corrupt data table.

12. A method as recited in claim 11 wherein in a redo phase, actions such as writes are applied to a database image unless a transaction is listed in the corrupt transaction table.

13. A method as recited in claim 9 further comprising the step of storing a codeword corresponding to a value of a data item in a record of said combined log of reads and writes wherein said forward scan adds transactions to said corrupt transaction table whenever said codeword does not match the current value of said data item read from a database.

14. A method as recited in claim 6 wherein said undo phase comprises undoing portions of corrupt transactions.

15. A method as recited in claim 6 wherein said undo phase comprises undoing in progress corrupt transactions at the time of a data processor failure.

16. A method of detecting and recovering from data corruption as recited in claim 3 further comprising the step of responsive to the identity of a known corrupt data item, determining a probable source of the corruption from said combined log of writes and reads.

17. A method as recited in claim 16 wherein said determining step comprises the substep of processing said log of writes and reads backwards from an end of said combined log of writes and reads.

18. A method as recited in claim 17 further comprising the substeps of maintaining a table of suspect corrupt data items and, for each data item of said table, maintaining a set of known corrupt data items whose corruption would be explained if said data item were corrupt.

19. A method as recited in claim 18 further comprising the substep of maintaining a table of suspect corrupt transactions and, for each transaction of said table, maintaining said set of known corrupt data items whose corruption would be explained if said transaction were corrupt.

20. A method as recited in claim 19 further comprising the substeps of adding a transaction to the table of suspect corrupt transactions when a write of a data item in the suspect data table by said transaction is encountered in said combined log during said backwards processing step.

21. A method as recited in claim 20 further comprising the substep of adding the set of known corrupt data items associated with said data item in the suspect data table to the set of known corrupt data items associated with said transaction.

22. A method as recited in claim 19 further comprising the substep of adding a data item to the suspect data table when a read of said data item by a transaction in the suspect transaction table is encountered in said combined log during said backwards processing step.

23. A method as recited in claim 22 further comprising the substep of adding the set of known corrupt data items associated with said transaction to the set of known corrupt data items associated with said data item.

24. A method as recited in claim 23 further comprising the step of stopping said backwards processing whenever a suspect transaction exists in the suspect transaction table such that the set of data items associated with said transaction contains all known corrupt data items, said transaction being output to said user as a possible source of said corruption.

25. A method as recited in claim 24 further comprising the steps of performing forward recovery from said transaction determined by said user as a source of said corruption.

26. A method of detecting and recovering from data corruption as recited in claim 1 further comprising the step of logging one of an identity of information read from and an identity of information written to the database.

27. A method of detecting and recovering from data corruption as recited in claim 1 further comprising the step of:

storing a codeword in a record of said read-logging information.

28. A method of detecting and recovering from data corruption as recited in claim 1 further comprising the step of:

protecting data of the database with codewords, one codeword for each region of the database.

29. A method as recited in claim 1 wherein in a delete transaction model comprises deleting effects of selective transactions from a database image when the transaction was affected by an error.

30. A method as recited in claim 1 for further recovering from logical corruption, the method comprising the step of maintaining a logical redo log.

31. A method as recited in claim 30 further comprising the additional steps of maintaining a transaction code for redoing transactions and of storing user inputs for a transaction in said logical redo log.

32. A method as recited in claim 31 further comprising the step of maintaining a commit record at a transaction level.

33. A method as recited in claim 30 comprising the further step of returning a database to a transaction consistent state prior to a first detected instance of possible data corruption.

34. A method as recited in claim 33 comprising the further step of rerunning transactions affected by the first detected instance of a possible data corruption in the same order as an original set of transactions.

35. A method as recited in claim 33 comprising the further step of deleting effects of transactions when logical information is unavailable to permit redoing transactions.

36. A method as recited in claim 1, wherein direct physical corruption has occurred to data in memory used for database cache, further comprising the step of removing corruption from cache pages without reflecting any corrupt data values in log records.

37. A method as recited in claim 1 wherein said information about reads comprises one of a start and an end point and length of data read.

38. A method as recited in claim 1 further comprising the step of detecting logical corruption of data, said method comprises the step of logging a codeword of a logical state found.

39. A method as recited in claim 1, further comprising the step of logging lock information in a logical read log.

40. A method as recited in claim 39 wherein said lock information comprises a name of a data item and a type of lock.

41. A method as recited in claim 1 further comprising the step of ensuring a disc image of said database is free of corruption.

42. A method as recited in claim 1, wherein, in the event of logical corruption, said method comprises the step of logging the identity and codeword for a logical structure protected by a lock.

43. A method of detecting and recovering from data corruption of a database comprising the steps of logging information about reads of a database to automatically detect and recover from logical corruption of the data in the database using a codeword matching audit algorithm for detection of said logical corruption, maintaining a logical redo log and storing user inputs for a transaction in said logical redo log, and maintaining a corrupt transaction table and a corrupt data table for a recovery algorithm.

44. A data corruption recovery method as recited in claim 43 further comprising the step of performing forward recovery in said logical redo log from a determined point of initial corruption.

45. A corruption recovery method as recited in claim 44 further comprising the steps of saving log records until a commit or an abort for a transaction is seen and, if a commit is seen, then scanning the read log records to determine if a transaction has read corrupted data and marking the transaction as corrupt.

46. A corruption recovery method as recited in claim 45 further comprising the steps of, if a commit is seen and the transaction is marked corrupt, reexecuting the transaction logically and, responsive thereto, replacing logical redo records with redo records generated by the logical reexecution of the transaction and adding data written by the transaction to a corrupt data table.

47. A corruption recovery method as recited in claim 45 further comprising the steps of, if a commit is seen and the transaction is:

not marked corrupt, executing its logical redo records.

48. A corruption recovery method as recited in claim 44 further comprising the steps of saving log records until a commit or an abort for a transaction is seen and, if an abort is seen, discarding the log records.

49. A method of detecting and recovering from data corruption of a database comprising the steps of logging information about reads of a database to automatically detect and recover from logical corruption of the data in the database using a codeword matching audit algorithm for detection of said logical corruption, maintaining a corrupt transaction table and a corrupt data table for a recovery algorithm and deleting the effects of transactions from an image of the database.

50. The method of detecting and recovering from data corruption as recited in claim 49 further comprising the step of logging lock information in said logical redo log.

51. A method of detecting and recovering from data corruption as recited in claim 49, said recovery from data corruption comprising first and second phases, a first redo phase followed by an undo phase.

52. A method as recited in claim 51 wherein said redo phase comprises a forward scan of a log of read and write operations.

53. A method as recited in claim 52 wherein said forward scan adds an identity of data to a corrupt data table whenever said data is written by a corrupt transaction.

54. A method as recited in claim 52 wherein said forward scan adds-transactions to a corrupt transaction table whenever data is read that is identified in the corrupt data table.

55. A method as recited in claim 54 wherein in a redo phase, actions such as writes are applied to a database image unless a transaction is listed in the corrupt transaction table.

56. A method as recited in claim 51 wherein said undo phase comprises undoing portions of corrupt transactions.

57. A method as recited in claim 51 wherein said undo phase comprises undoing in progress transactions at the time of a data processor failure.

58. A method of detecting and recovering from data corruption of a database comprising the steps of logging information about reads of a database to automatically detect and recover from logical corruption of the data in the database using a codeword matching audit algorithm for detection of said logical corruption and logging the codeword of a logical state found.

59. A method of detecting and recovering from data corruption of a database comprising the steps of:

(a) logging information about reads of a database to automatically detect and recover from physical corruption of the data in the database using a codeword matching audit algorithm for detection of said physical corruption, said physical corruption arising from bad writes of data to the database or corruption arising indirectly therefrom;

(b) storing a codeword corresponding to a value of a data item in a record of said combined log of reads and writes; and

(c) performing a forward scan of a log of read and write operations wherein said forward scan adds an identity of data to a corrupt data table whenever said data has failed an audit.

60. A method of detecting and recovering from data corruption of a database comprising the steps of:

(a) logging information about reads of a database to automatically detect and recover from logical corruption of the data in the database using a codeword matching audit algorithm for detection of said logical corruption and deleting the effects of transactions from an image of the database;

(b) logging lock information in a logical redo log;

(c) recovering from data corruption using first and second phases, a first redo phase followed by an undo phase;

(d) said redo phase comprising a forward scan of a log of read and write operations; and

(e) said forward scan adding an identity of data to a corrupt data table whenever said data is written by a corrupt transaction wherein said forward scan adds transactions to a corrupt transaction table whenever data is read that is identified in the corrupt data table.