Multi-node fault-tolerant timestamp generation

• US 6,078,930 A
• Filed: 10/31/1997
• Issued: 06/20/2000
• Est. Priority Date: 02/28/1997
• Status: Expired due to Term

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle Corporation
• Inventors: Lee, J. William, Bridge, William H. Jr.
• Primary Examiner(s): Kulik, Paul V.
• Application Number:
  US08/961,798
• Time in Patent Office: 963 Days
• Field of Search: 707/200, 707/201, 707/202, 707/203, 714/12, 714/15, 714/16, 714/20
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1415 at system level
• CPC Class Codes: G06F 2201/835 Timestamp
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

Techniques for determining a safe recovery time value after a failure of a first node in a computer system are described. According to the techniques, every node in a multi-node parallel database system maintains a logical clock for generating timestamps. The logical clocks are synchronized by attaching a current timestamp to every message that is sent by a node. When a node receives an incoming timestamp that is greater than the value indicated by the associated logical clock, it sets the associated logical clock forward to at least the value of the timestamp. When a node fails, a recovery node calculates a "safe" logical clock value to use in recovering the crashed node. In calculating the "safe" logical clock value, the recovery node searches specific areas of the database to locate and recover a most recent timestamp value associated with the crashed node. The recovery node then compares its current logical clock time value with the most recent crash node timestamp value to determine which timestamp is most recent. If the most recent crash node timestamp value is more recent than the recovery node'"'"'s current logical clock time value, the recovery node'"'"'s logical clock is updated to be at least as recent as the most recent crash node timestamp value. The recovery node then recovers the crashed node as its logical clock is guaranteed to be at least as recent as any timestamp value that was previously written to the database by the crashed node prior to failure.

Claims

1. A method for determining a safe recovery time value after a failure of a first node in a computer system, wherein said first node is one of a plurality of nodes that has access to a database, wherein a plurality of logical clocks are associated with said plurality of nodes, the method comprising the steps of:

prior to said failure, said first node maintaining a first logical clock of said plurality of logical clocks to assign time values to changes made to said database by said first node;

after said failure, reading a most recent log timestamp value from a log file associated with said first node;

determining, based on said most recent log timestamp value, a recovery timestamp value that is at least as recent as any time value recorded in said database by said first node prior to said failure; and

recovering said first node using said recovery timestamp value.

2. The method of claim 1 wherein the step of determining said recovery timestamp value includes the steps of:

reading a crash delta value, wherein said crash delta value equals a predetermined value;

calculating a second timestamp value, wherein said second timestamp value equals the sum of said most recent log timestamp value and said crash delta value; and

determining said recovery timestamp value based on said second timestamp value.

3. The method of claim 1 further comprises performing the following steps prior to the failure of said first node:

detecting an attempt by the first node to perform an update to said database without storing data in said log file to reflect said update;

in response to said attempt, performing the steps of

determining whether the logical clock of said first node is less than the sum of the most recent log timestamp value that is recorded in said log file and a crash delta value;

if the logical clock of said first node is not less than the sum of the most recent log timestamp value that is recorded in said log file and said crash delta value, then prohibiting said update to said database by said first node.

4. The method of claim 3 wherein the step of prohibiting said update to said database includes the steps of:

waiting until the sum of the most recent log timestamp value that is recorded in said log file and said crash delta value is greater than said logical clock of said first node; and

after the sum of the most recent log timestamp value that is recorded in said log file and said crash delta value is greater than said logical clock of said first node, allowing the first node to perform said update to said database without storing data in said log file to reflect said update.

5. The method of claim 3 wherein the step of prohibiting said update to said database includes the steps of:

allowing said first node to perform said update to said database; and

causing said first node to store data in said log file to reflect said update.

6. The method of claim 1 further comprising the steps of:

applying to said database one or more updates that are recorded in said log file associated with said first node; and

assigning to said one or more updates timestamp values that reflect a time that is at least as recent as said recovery timestamp value.

7. The method of claim 1 wherein:

said database includes a body of data whose updates are not recorded in said log file; and

the method further comprising the step of, prior to failure of said first node,

causing each of said plurality of nodes to perform the following steps when updating said body of data;

reading a timestamp value from said body of data;

comparing said timestamp value with a logical clock value of said node that is updating said body of data;

if said timestamp value is more recent than said logical clock value of said node that is updating said body of data, then setting said logical clock of said node that is updating said body of data equal to said timestamp value; and

writing said logical clock value of said node that is updating said body of data into said body of data.

8. The method of claim 1 wherein the step of determining said recovery timestamp value further includes the steps of:

reading a third timestamp value from a body of data, wherein updates to said body of data are not recorded in said log file; and

determining said recovery timestamp value based on said third timestamp value.

9. The method of claim 8 wherein the step of reading said third timestamp value from said body of data further comprises the step of reading said third timestamp value from a catalog file, wherein said catalog file maintains data that reflects a physical structure of said database.

10. The method of claim 1 wherein the step of determining said recovery timestamp value includes the steps of:

reading a crash delta value, wherein said crash delta value equals a predetermined value;

calculating a second timestamp value, wherein said second timestamp value equals the sum of said most recent log timestamp value and said crash delta value;

reading a third timestamp value from a body of data, wherein updates to said body of data are not recorded in said log file;

comparing said second timestamp value with said third timestamp value;

if said second timestamp value is more recent than said third timestamp value, then setting said recovery timestamp value equal to said second timestamp value; and

if said third timestamp value is more recent than said second timestamp value, then setting said recovery timestamp value equal to said third timestamp value.

11. The method of claim 1 wherein the step of determining said recovery timestamp value further comprises the steps of:

reading a logical clock value from a second node, wherein said second node is one of said plurality of nodes and wherein said second node is responsible for recovering said first node;

comparing said recovery timestamp value with the logical clock value of said second node; and

if the logical clock value of said second node is more recent than said recovery timestamp value, then setting said recovery timestamp value equal to the logical clock value of said second node.

12. A computer-readable medium having stored thereon sequences of instructions for determining a safe recovery time value after a failure of a first node in a computer system, wherein said first node is one of a plurality of nodes that has access to a database, wherein a plurality of logical clocks are associated with said plurality of nodes, the sequences of instructions including instructions for performing the steps of:

prior to said failure, said first node maintaining a first logical clock of said plurality of logical clocks to assign time values to changes made to said database by said first node;

after said failure, reading a most recent log timestamp value from a log file associated with said first node;

determining, based on said most recent log timestamp value, a recovery timestamp value that is at least as recent as any time value recorded in said database by said first node prior to said failure; and

recovering said first node using said recovery timestamp value.

13. The computer-readable medium of claim 12 wherein the sequence of instructions for determining said recovery timestamp value includes instructions for:

reading a crash delta value, wherein said crash delta value equals a predetermined value;

calculating a second timestamp value, wherein said second timestamp value equals the sum of said most recent log timestamp value and said crash delta value; and

determining said recovery timestamp value based on said second timestamp value.

14. The computer-readable medium of claim 12 wherein the sequence of instructions further comprises instructions for performing the following steps prior to the failure of said first node:

detecting an attempt by the first node to perform an update to said database without storing data in said log file to reflect said update;

in response to said attempt, performing the steps of

determining whether the logical clock of said first node is less than the sum of the most recent log timestamp value that is recorded in said log file and a crash delta value;

if the logical clock of said first node is not less than the sum of the most recent log timestamp value that is recorded in said log file and said crash delta value, then prohibiting said update to said database by said first node.

15. The computer-readable medium of claim 12 further comprising sequence of instructions for performing the steps of:

applying to said database one or more updates that are recorded in said log file associated with said first node; and

assigning to said one or more updates timestamp values that reflect a time that is at least as recent as said recovery timestamp value.

16. The computer-readable medium of claim 12 wherein:

said database includes a body of data whose updates are not recorded in said log file; and

the sequences of instructions further comprise instructions for, prior to failure of said first node, causing each of said plurality of nodes to perform the following steps when updating said body of data;

reading a timestamp value from said body of data;

comparing said timestamp value with a logical clock value of said node that is updating said body of data;

if said timestamp value is more recent than said logical clock value of said node that is updating said body of data, then setting said logical clock of said node that is updating said body of data equal to said timestamp value; and

writing said logical clock value of said node that is updating said body of data into said body of data.

17. The computer-readable medium of claim 12 wherein the sequence of instructions for determining said recovery timestamp value further includes instructions for:

reading a third timestamp value from a body of data, wherein updates to said body of data are not recorded in said log file; and

determining said recovery timestamp value based on said third timestamp value.

18. The computer-readable medium of claim 12 wherein the sequence of instructions for determining said recovery timestamp value includes instructions for:

reading a crash delta value, wherein said crash delta value equals a predetermined value;

calculating a second timestamp value, wherein said second timestamp value equals the sum of said most recent log timestamp value and said crash delta value;

reading a third timestamp value from a body of data, wherein updates to said body of data are not recorded in said log file;

comparing said second timestamp value with said third timestamp value;

if said second timestamp value is more recent than said third timestamp value, then setting said recovery timestamp value equal to said second timestamp value; and

if said third timestamp value is more recent than said second timestamp value, then setting said recovery timestamp value equal to said third timestamp value.

19. The computer-readable medium of claim 12 wherein the sequence of instructions for determining said recovery timestamp value further comprises instructions for:

reading a logical clock value from a second node, wherein said second node is one of said plurality of nodes and wherein said second node is responsible for recovering said first node;

comparing said recovery timestamp value with the logical clock value of said second node; and

if the logical clock value of said second node is more recent than said recovery timestamp value, then setting said recovery timestamp value equal to the logical clock value of said second node.

20. A computer system for determining a safe recovery time value after a failure of a first node in a computer system, wherein said first node is one of a plurality of nodes that has access to a database, wherein a plurality of logical clocks are associated with said plurality of nodes, the computer system comprising:

a memory;

one or more processors coupled to the memory; and

a set of computer instructions contained in the memory, the set of computer instructions including computer instructions which when executed by the one or more processors, cause the one or more processors to perform the steps of;

prior to said failure, said first node maintaining a first logical clock of said plurality of logical clocks to assign time values to changes made to said database by said first node;

after said failure, reading a most recent log timestamp value from a log file associated with said first node;

determining, based on said most recent log timestamp value, a recovery timestamp value that is at least as recent as any time value recorded in said database by said first node prior to said failure; and

recovering said first node using said recovery timestamp value.

21. The computer system of claim 20 wherein the step of determining said recovery timestamp value includes the steps of:

reading a crash delta value, wherein said crash delta value equals a predetermined value;

calculating a second timestamp value, wherein said second timestamp value equals the sum of said most recent log timestamp value and said crash delta value; and

determining said recovery timestamp value based on said second timestamp value.

22. The computer system of claim 20 further comprises computer instructions for performing the following steps prior to the failure of said first node:

detecting an attempt by the first node to perform an update to said database without storing data in said log file to reflect said update;

in response to said attempt, performing the steps of

determining whether the logical clock of said first node is less than the sum of the most recent log timestamp value that is recorded in said log file and a crash delta value;

if the logical clock of said first node is not less than the sum of the most recent log timestamp value that is recorded in said log file and said crash delta value, then prohibiting said update to said database by said first node.

23. The computer system of claim 22 wherein the step of prohibiting said update to said database includes the steps of:

waiting until the sum of the most recent log timestamp value that is recorded in said log file and said crash delta value is greater than said logical clock of said first node; and

after the sum of the most recent log timestamp value that is recorded in said log file and said crash delta value is greater than said logical clock of said first node, allowing the first node to perform said update to said database without storing data in said log file to reflect said update.

24. The computer system of claim 22 wherein the step of prohibiting said update to said database includes the steps of:

allowing said first node to perform said update to said database; and

causing said first node to store data in said log file to reflect said update.

25. The computer system of claim 20 further comprising computer instructions for performing the steps of:

applying to said database one or more updates that are recorded in said log file associated with said first node; and

assigning to said one or more updates timestamp values that reflect a time that is at least as recent as said recovery timestamp value.

26. The computer system of claim 20 wherein:

said database includes a body of data whose updates are not recorded in said log file; and

the computer system further comprising computer instructions for performing the step of, prior to failure of said first node, causing each of said plurality of nodes to perform the following steps when updating said body of data;

reading a timestamp value from said body of data;

comparing said timestamp value with a logical clock value of said node that is updating said body of data;

if said timestamp value is more recent than said logical clock value of said node that is updating said body of data, then setting said logical clock of said node that is updating said body of data equal to said timestamp value; and

writing said logical clock value of said node that is updating said body of data into said body of data.

27. The computer system of claim 20 wherein the step of determining said recovery timestamp value further comprises computer instructions for performing the steps of:

reading a third timestamp value from a body of data, wherein updates to said body of data are not recorded in said log file; and

determining said recovery timestamp value based on said third timestamp value.

28. The computer system of claim 27 wherein the step of reading said third timestamp value from said body of data further comprises computer instructions for performing the step of reading said third timestamp value from a catalog file, wherein said catalog file maintains data that reflects a physical structure of said database.

29. The computer system of claim 20 wherein the step of determining said recovery timestamp value includes the steps of:

reading a crash delta value, wherein said crash delta value equals a predetermined value;

calculating a second timestamp value, wherein said second timestamp value equals the sum of said most recent log timestamp value and said crash delta value;

reading a third timestamp value from a body of data, wherein updates to said body of data are not recorded in said log file;

comparing said second timestamp value with said third timestamp value;

if said second timestamp value is more recent than said third timestamp value, then setting said recovery timestamp value equal to said second timestamp value; and

if said third timestamp value is more recent than said second timestamp value, then setting said recovery timestamp value equal to said third timestamp value.

30. The computer system of claim 20 wherein the step of determining said recovery timestamp value further comprises computer instructions for performing the steps of:

reading a logical clock value from a second node, wherein said second node is one of said plurality of nodes and wherein said second node is responsible for recovering said first node;

comparing said recovery timestamp value with the logical clock value of said second node; and

if the logical clock value of said second node is more recent than said recovery timestamp value, then setting said recovery timestamp value equal to the logical clock value of said second node.

31. A method for determining a safe recovery time value after a failure of a first node in a computer system, wherein said first node is one of a plurality of nodes that has access to a database, wherein a plurality of logical clocks are associated with said plurality of nodes, the method comprising the steps of:

prior to said failure, said first node maintaining a first logical clock of said plurality of logical clocks to assign time values to changes made to said database by said first node;

after said failure,

reading a first possibly most recent timestamp value associated with said first node;

reading a second possibly most recent timestamp value associated with said first node;

determining, based on said first possibly most recent timestamp value and said second possibly most recent timestamp value, a recovery timestamp value that is at least as recent as any time value recorded in said database by said first node prior to said failure; and

recovering said first node using said recovery timestamp value.

33. The method of claim 31 wherein:

the step of reading a first possibly most recent timestamp value comprises the steps of reading a most recent log timestamp value from a log file associated with said first node; and

the step of determining a recovery timestamp value comprises the steps of determining, based on said most recent log timestamp value and said second possibly most recent timestamp value, a recovery timestamp value that is at least as recent as any time value recorded in said database by said first node prior to said failure.

34. The method of claim 33 further comprising the steps of:

reading a crash delta value, wherein said crash delta value equals a predetermined value;

calculating a timestamp value, wherein said crash delta timestamp value equals the sum of said most recent log timestamp value and said crash delta value; and

determining, based on said crash delta timestamp value and said second possibly most recent timestamp value, said recovery timestamp value that is at least as recent as any time value recorded in said database by said first node prior to said failure.

35. The method of claim 33 further comprises performing the following steps prior to the failure of said first node:

detecting an attempt by the first node to perform an update to said database without storing data in said log file to reflect said update;

in response to said attempt, performing the steps of determining whether the logical clock of said node is less than the sum of the most recent log timestamp value that is recorded in said log file and a crash delta value;

if the logical clock of said first node is not less than the sum of t he most recent log timestamp value that is recorded in said log file and said crash delta value, them prohibiting said update to said database by said first node.

36. The method of claim 35 wherein the step of prohibiting said update to said database includes the steps of:

waiting until the sum of the most recent log timestamp value that is recorded in said log file and said crash delta value is greater than said logical clock of said first node; and

after the sum of the most recent log timestamp value that is recorded in said and said crash delta value is greater than said logical clock of said first node;

allowing the first node to perform said update to said data base without storing data in said log file to reflect said update.

37. The method of claim 35 wherein the step of prohibiting said update to said database includes the steps of:

allowing said first node to perform said update to said database; and

causing said first node to store data in said log file to reflect said update.

38. The method of claim 33 further comprising the steps of:

applying to said database one or more updates that are recorded in said log file associated with said first node; and

assigning to said one or more updates timestamp values that reflect a time that is at least as recent as said recovery timestamp value.

39. The method of claim 33 wherein:

said database includes a body of data whose updates are not recorded in said log file; and

the method further comprising the step of, prior to failure of said first node, causing each of said plurality of nodes to perform the following steps when updating said body of data;

comparing said timestamp value with a logical clock value of said node that is updating said body of data;

if said timestamp value is more recent than said logical clock value of said node that updating said body of data, then setting said logical clock of said node that is updating said body of data equal to said timestamp value; and

writing said logical clock value of said node that is updating said body of data into said body of data.

40. The method of claim 33 wherein:

the step of reading a second possibly most recent timestamp value comprises the steps of reading a non-log file timestamp value from a body of data, wherein updates to said body of data are not recorded in said log file; and

the step of determining a recovery timestamp value comprises the steps of determining, based on said most recent log timestamp value and said non-log file timestamp value, a recovery timestamp value that is at least as recent as any time value recorded in said database by said first node prior to said failure.

41. The method of claim 31 further comprising the steps of:

reading a third possibly most recent timestamp value associated with said first node; and

determining, based on said first possibly most recent timestamp value, said second possibly most recent timestamp value and said third possibly most recent timestamp value, said recovery timestamp value that is at least as recent as any time value recorded in said database by said first node prior to said failure.

42. The method of claim 31 wherein:

the step of reading a first possibly most recent timestamp value comprises the steps of reading a most recent log timestamp value from a log file associated with said first node;

the step of reading a second possibly most recent timestamp value comprises the steps of reading a non-log file timestamp value from a body of data, wherein updates to said body of data are not recorded in said log file;

the method further comprising the steps of

calculating a crash delta timestamp value, wherein said crash delta timestamp value equals the sum of said most recent log timestamp value and said crash delta value;

comparing said crash delta timestamp value with said non-log file timestamp value;

if said non-log file timestamp value is more recent than said crash delta timestamp value, then setting said recovery timestamp value equal to said non-log file timestamp value; and

if said non-log file timestamp value is more recent then said crash delta timestamp value, then setting said recovery timestamp value equal to said non-log file timestamp value.

43. The method of claim 31 wherein the step of determining said recovery timestamp value further comprises the steps of:

reading a logical clock value from a second node, wherein said second node is one of said plurality of nodes and wherein said second node is responsible for recovering said first node;

comparing said recovery timestamp value with the logical clock value of said second node; and

if the logical clock value of said second node is more recent than said recovery timestamp value, then setting said recovery timestamp value equal to the logical clock value of said second node.

32. A computer-readable medium having stored thereon sequences of instructions for determining a safe recovery time value after a failure of a first node in a computer system, wherein said first node is one of a plurality of nodes that has access to a database, wherein a plurality of logical clocks are associated with said plurality of nodes, the sequences of instructions including instructions for performing the steps of:

prior to said failure, said first node maintaining a first logical clock of said plurality of logical clocks to assign time values to changes made to said database by said first node;

after said failure,

reading a first possibly most recent timestamp value associated with said first node;

reading a second possibly most recent timestamp value associated with said first node;

determining, based on said first possibly most recent timestamp value and said second possibly most recent timestamp value, a recovery timestamp value that is at least as recent as any time value recorded in said database by said first node prior to said failure; and

recovering said first node using said recovery timestamp value.

44. The computer-readable medium of claim 32 wherein:

the step of reading a first possibly most recent timestamp value comprises the steps of

reading a most recent log timestamp value from a log file associated with said first node; and

the step of determining a recovery timestamp value comprises the steps of determining, based on said most recent log timestamp value and said second possibly most recent timestamp value, a recovery timestamp value that is at least as recent as any time value recorded in said database by said first node prior to said failure.

45. The computer-readable medium of claim 44 further comprising instructions for performing the steps of:

reading a crash delta value, wherein said crash delta value equals a predetermined value;

calculating a crash delta timestamp value, wherein said crash delta timestamp value equals the sum of said most recent log timestamp value and said crash delta value; and

determining, based on said crash delta timestamp value and said second possibly most recent timestamp value, said recovery timestamp value that is at least as recent as any time value recorded in said database by said first node prior to said failure.

46. The computer readable medium of claim 44 the sequence of instructions further comprises instructions for performing the following steps prior to the failure of said node:

detecting an attempt by the first node to perform an update to said database without storing data in said log file to reflect said update;

in response to said attempt, performing the steps of

determining whether the logic clock of said first node is less than the sum of the most recent log timestamp value that is recorded in said log file and a crash delta value;

if the logical clock of said first node is not less than the sum of the most recent log timestamp value that is recorded in said log file and said crash delta value;

then prohibiting said update to said database by said first node.

47. The computer-readable medium of claim 46 wherein the step of prohibiting said update to said database includes the steps of:

waiting until the sum of the most recent log timestamp value that is recorded in said log file and said crash delta value is greater than said logical clock of said first node; and

after the sum of the most recent log timestamp value that is recorded in said log file and said crash delta value is greater than said logical clock of said first node, allowing the first node to perform said update to said database without storing data in said log file to reflect said update.

48. The computer-readable medium of claim 46 wherein the step of prohibiting said update to said database includes the steps of:

allowing said first node to perform said update to said database; and

causing said first node to store data in said log file to reflect said update.

49. The computer-readable medium of claim 44 further comprising instructions for performing the steps of:

applying to said database one or more updates that are recorded in said log file associated with said first node; and

assigning to said one or more updates timestamp values that reflect a time that is at least as recent as said recovery timestamp value.

50. The computer-readable medium of claim 44 wherein:

said database includes a body of data whose updates are not recorded in said log file; and

the computer-readable medium further comprising the instructions for performing the steps of, prior to failure of said first node, causing each of said plurality of nodes to perform the following steps when updating said body of data;

reading a timestamp value from said body of data;

comparing said timestamp value with a logical clock value of said node that is updating said body of data;

if said timestamp value is more recent than said logical clock value of said node that is updating said body of data, then setting said logical clock of said node that is updating said body of data equal to said timestamp value; and

writing said logical clock value of said node that is updating said body of data into said body of data.

51. The computer-readable medium of claim 44 wherein:

the step of reading a second possible most recent timestamp value comprises the steps of reading a non-log file timestamp value from a body of data, wherein updates to said body of data are not recorded in said log filed; and

the step of determining a recovery timestamp value comprises the steps of determining, based on said most recent log timestamp value and said non-log file timestamp value, a recovery timestamp value that is at least as recent as any time value recorded in said database by said first node prior to said failure.

52. The computer-readable medium of claim 32 further comprises instructions for performing the steps of:

reading a third possibly most recent timestamp value associated with said first node; and

determining, based on said first possibly most recent timestamp value, said second possibly most recent timestamp value and said third possibly most recent timestamp value, said recovery timestamp value that is at least as recent as any time value recorded in said database by said first node prior to said failure.

53. The computer-readable medium of claim 32 wherein:

the step of reading a first possibly most recent timestamp value comprises the steps of reading a most recent log timestamp value from a log file associated with said first node;

the step of reading a second possibly most recent timestamp value comprises the steps of reading a non-log file timestamp value from a body of data, wherein updates to said body of data are not recorded in said log file;

the computer-readable medium further comprising instructions for performing the steps of

calculating a crash delta timestamp value, wherein said crash delta timestamp value equals the sum of said most recent log timestamp value and said crash delta value;

comparing said crash delta timestamp value with said non-log value;

if said crash delta timestamp value is more recent than said non-log file timestamp value, then setting said recovery timestamp value equal to said non-log file timestamp value.

54. The computer-readable medium of claim 32 wherein the sequence of instructions further comprises instructions for performing the steps of:

reading a logical clock value from a second, node wherein said second node is one of said plurality of nodes and wherein said second node is responsible for recovering said first node;

comparing said recovery timestamp value with the logical clock value of said second node; and

if the logical clock value of said second node is more recent than said recovery timestamp value, then setting recovery timestamp value equal to the logical clock value of said second node.