Method and system for maintaining checkpoint values

• US 6,253,212 B1
• Filed: 06/23/1998
• Issued: 06/26/2001
• Est. Priority Date: 06/23/1998
• Status: Expired due to Term

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle Corporation
• Inventors: Loaiza, Juan R., Joshi, Ashok, Bridge, William H. Jr.
• Primary Examiner(s): Alam, Hosain T.
• Application Number:
  US09/103,627
• Time in Patent Office: 1,099 Days
• Field of Search: 707/8, 707/202, 707/200-201, 707/203-204
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1402 Saving, restoring, recovering or retrying
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

A method and system are provided for maintaining a checkpoint value that indicates which records of a plurality of records associated with updates made before a failure have to be processed after the failure. According to one aspect of the invention, an ordered list of buffers is maintained in volatile memory. The ordered list of buffers has a head and a tail. The ordered list of buffers is maintained by writing a record that indicates the update to nonvolatile memory and adding the buffer to the tail of the ordered list whenever an update is made to a data item within a buffer in volatile memory. When a data item contained in a buffer within the ordered list is stored in nonvolatile memory, the buffer can be removed from the ordered list. A checkpoint value that identifies a record associated with a buffer located at the head of the ordered list is written to nonvolatile memory. According to another aspect, after a failure, the record associated with the checkpoint value is identified. If a particular record was stored to nonvolatile memory before the record associated with the checkpoint value, the particular record is not processed. If the particular record was not stored to nonvolatile memory before the record associated with the checkpoint value, the particular record is processed.

Claims

1. A method for maintaining a checkpoint value that indicates which records of a plurality of records associated with updates made before a failure have to be processed after the failure, the method comprising the steps of:

maintaining an ordered list of buffers, wherein buffers within said ordered list of buffers reside in volatile memory, wherein the ordered list of buffers has a head and a tail, the step of maintaining the ordered list including the steps of

when an update is made to a data item within a buffer in volatile memory, performing the steps of

writing a record that indicates the update to nonvolatile memory; and

inserting the buffer into a particular position in said ordered list in a manner that preserves relative ordering of buffers already in said ordered list;

when a data item contained in a buffer within the ordered list is stored in nonvolatile memory, removing the buffer from the ordered list; and

writing to nonvolatile memory as said checkpoint value, a value that identifies a record of said plurality of records that is associated with a buffer that is currently located at the head of the ordered list.

2. The method of claim 1, further comprising performing the following steps after the failure:

identifying the record associated with the checkpoint value;

if a particular record was stored to nonvolatile memory before the record associated with the checkpoint value, then not processing the particular record; and

if the particular record was not stored to nonvolatile memory before the record associated with the checkpoint value, then processing the particular record.

3. The method of claim 1, wherein the step of inserting the buffer into a particular position in said ordered list further comprises the step of sorting the buffer into the ordered list based on when the record associated with the buffer is stored to nonvolatile memory relative to when the records associated with the buffers that are already in the ordered list were stored to nonvolatile memory.

4. The method of claim 1, wherein the step of inserting the buffer into a particular position in said ordered list further comprises the step of sorting the buffer into the ordered list based on where the record associated with the buffer is stored in nonvolatile memory relative to where the records associated with the buffers that are already in the ordered list were stored in nonvolatile memory.

5. The method of claim 1, wherein the step of inserting the buffer into a particular position in said ordered list further comprises the step of adding the buffer to the ordered list only if the buffer does not already reside in the ordered list.

6. The method of claim 1, wherein the step of maintaining an ordered list of buffers further comprises the step of storing an index value with each buffer in the ordered list of buffers, wherein the index value indicates a storage location in nonvolatile memory of the record associated with the buffer.

7. The method of claim 2, wherein the step of processing the particular record if the particular record was not stored to nonvolatile memory before the record associated with the checkpoint value further comprises the step of processing all records sequentially stored at locations that follow a location at which the record associated with the checkpoint value is stored.

8. The method of claim 7, further comprising the step of processing the record associated with the checkpoint value.

9. The method of claim 1, wherein the step of writing to nonvolatile memory the checkpoint value further comprises the step of writing to nonvolatile memory the checkpoint value at predetermined time intervals.

10. The method of claim 1, wherein the step of writing to nonvolatile memory the checkpoint value further comprises the steps of:

if said ordered list is empty, then

determining a location of the record last written to nonvolatile memory; and

storing the checkpoint value that is based on said location.

11. The method of claim 1, further comprising the step of causing a process that writes updated data items to nonvolatile memory to select which updated data items to write to nonvolatile memory based on which buffer is at the head of the ordered list.

12. The method of claim 1, wherein the step of removing the buffer from the ordered list further comprises the step of removing a particular number of the buffers, wherein the particular number of buffers that are removed dynamically adjusts according to how many of the buffers currently reside in the ordered list.

13. The method of claim 1, wherein the step of removing the buffer from the ordered list further comprises the step of removing a particular number of the buffers, wherein the step of removing the particular number of the buffers is performed at a frequency that dynamically adjusts according to how many buffers currently reside in the ordered list.

14. The method of claim 1, wherein the step of removing the buffer from the ordered list further comprises the step of removing the buffer from a position in said ordered list other than the head of the ordered list.

15. The method of claim 1, wherein the step of removing the buffer from the ordered list further comprises the steps of:

determining if the buffer was updated while being removed from the ordered list;

if the buffer was updated while being removed from the ordered list, then inserting the buffer back into the ordered list.

16. The method of claim 1, wherein the step of inserting the buffer into a particular position in said ordered list further comprises the steps of:

obtaining an index value, wherein the index value corresponds to a storage location in nonvolatile memory;

storing the index value as the index value for the buffer; and

inserting the buffer into the ordered list based on the index value for the buffer.

17. The method of claim 1, wherein:

each buffer is associated with an index value, wherein said index value identifies where the record associated with each buffer is written to nonvolatile memory;

said step of inserting the buffer into a particular position in said ordered list includes the step of inserting the buffer into a particular position of one of a plurality of ordered lists;

said step of writing to nonvolatile memory as said checkpoint value the value that identifies the record associated with the buffer located at the head of the ordered list includes the step of writing to nonvolatile memory the checkpoint value that identifies the record associated with a particular buffer located at the head of one of the plurality of ordered lists, wherein said particular buffer is associated with a smallest index value of all buffers located at the head of the one of the plurality of ordered lists; and

said step of removing the buffer from the ordered list includes the step of removing the buffer from one of the plurality of ordered lists.

18. The method of claim 1, wherein the step of inserting the buffer into a particular position in said ordered list further comprises the step of adding the buffer to the tail of the ordered list.

19. The method of claim 1, wherein the step of inserting the buffer into a particular position in said ordered list further comprises the step of adding the buffer in a position other than the tail of the ordered list.

20. The method of claim 1, wherein the step of removing the buffer from the ordered list further comprises the step of removing the buffer from a position in said ordered list without removing the buffer currently at the head of the ordered list.

21. A computer-readable medium carrying one or more sequences of instructions for for maintaining a checkpoint value that indicates which records of a plurality of records associated with updates made before a failure have to be processed after the failure, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of:

maintaining an ordered list of buffers, wherein buffers within said ordered list of buffers reside in volatile memory, wherein the ordered list of buffers has a head and a tail, the step of maintaining the ordered list including the steps of

when an update is made to a data item within a buffer in volatile memory, performing the steps of

writing a record that indicates the update to nonvolatile memory; and

inserting the buffer into a particular position in said ordered list in a manner that preserves relative ordering of buffers already in said ordered list;

when a data item contained in a buffer within the ordered list is stored in nonvolatile memory, removing the buffer from the ordered list; and

writing to nonvolatile memory as said checkpoint value, a value that identifies a record of said plurality of records that is associated with a buffer that is currently located at the head of the ordered list.

22. The computer-readable medium of claim 21, wherein the computer-readable medium further comprises instructions for performing the following steps after the failure:

identifying the record associated with the checkpoint value;

if a particular record was stored to nonvolatile memory before the record associated with the checkpoint value, then not processing the particular record; and

if the particular record was not stored to nonvolatile memory before the record associated with the checkpoint value, then processing the particular record.

23. The computer-readable medium of claim 21, wherein the step of inserting the buffer into a particular position in said ordered list further comprises the step of sorting the buffer into the ordered list based on when the record associated with the buffer is stored to nonvolatile memory relative to when the records associated with the buffers that are already in the ordered list were stored to nonvolatile memory.

24. The computer-readable medium of claim 21, wherein the step of inserting the buffer into a particular position in said ordered list further comprises the step of sorting the buffer into the ordered list based on where the record associated with the buffer is stored in nonvolatile memory relative to where the records associated with the buffers that are already in the ordered list were stored in nonvolatile memory.

25. The computer-readable medium of claim 21, wherein the step of inserting the buffer into a particular position in said ordered list further comprises the step of adding the buffer to the ordered list only if the buffer does not already reside in the ordered list.

26. The computer-readable medium of claim 21, wherein the step of maintaining an ordered list of buffers further comprises the step of storing an index value with each buffer in the ordered list of buffers, wherein the index value indicates a storage location in nonvolatile memory of the record associated with the buffer.

27. The computer-readable medium of claim 22, wherein the step of processing the particular record if the particular record was not stored to nonvolatile memory before the record associated with the checkpoint value further comprises the step of processing all records sequentially stored at locations that follow a location at which the record associated with the checkpoint value is stored.

28. The computer-readable medium of claim 27, wherein the computer-readable medium further comprises instructions for performing the step of processing the record associated with the checkpoint value.

29. The computer-readable medium of claim 21, wherein the step of writing to nonvolatile memory the checkpoint value further comprises the step of writing to nonvolatile memory the checkpoint value at predetermined time intervals.

30. The computer-readable medium of claim 21, wherein the step of writing to nonvolatile memory the checkpoint value further comprises the steps of:

if said ordered list is empty, then

determining a location of the record last written to nonvolatile memory; and

storing the checkpoint value that is based on said location.

31. The computer-readable medium of claim 21, wherein the computer-readable medium further comprises instructions for performing the step of causing a process that writes updated data items to nonvolatile memory to select which updated data items to write to nonvolatile memory based on which buffer is at the head of the ordered list.

32. The computer-readable medium of claim 21, wherein the step of removing the buffer from the ordered list further comprises the step of removing a particular number of the buffers, wherein the particular number of buffers that are removed dynamically adjusts according to how many of the buffers currently reside in the ordered list.

33. The computer-readable medium of claim 21, wherein the step of removing the buffer from the ordered list further comprises the step of removing a particular number of the buffers, wherein the step of removing the particular number of the buffers is performed at a frequency that dynamically adjusts according to how many buffers currently reside in the ordered list.

34. The computer-readable medium of claim 21, wherein the step of removing the buffer from the ordered list further comprises the step of removing the buffer from a position in said ordered list other than the head of the ordered list.

35. The computer-readable medium of claim 21, wherein the step of removing the buffer from the ordered list further comprises the steps of:

determining if the buffer was updated while being removed from the ordered list;

if the buffer was updated while being removed from the ordered list, then inserting the buffer back into the ordered list.

36. The computer-readable medium of claim 21, wherein the step of inserting the buffer into a particular position in said ordered list further comprises the steps of:

obtaining an index value, wherein the index value corresponds to a storage location in nonvolatile memory;

storing the index value as the index value for the buffer; and

inserting the buffer into the ordered list based on the index value for the buffer.

37. The computer-readable medium of claim 21, wherein:

each buffer is associated with an index value, wherein said index value identifies where the record associated with each buffer is written to nonvolatile memory;

said step of inserting the buffer into a particular position in said ordered list includes the step of inserting the buffer into a particular position of one of a plurality of ordered lists;

said step of writing to nonvolatile memory as said checkpoint value the value that identifies the record associated with the buffer located at the head of the ordered list includes the step of writing to nonvolatile memory the checkpoint value that identifies the record associated with a particular buffer located at the head of one of the plurality of ordered lists, wherein said particular buffer is associated with a smallest index value of all buffers located at the head of the one of the plurality of ordered lists; and

said step of removing the buffer from the ordered list includes the step of removing the buffer from one of the plurality of ordered lists.

38. The computer-readable medium of claim 21, wherein the step of inserting the buffer into a particular position in said ordered list further comprises the step of adding the buffer to the tail of the ordered list.

39. The computer-readable medium of claim 21, wherein the step of inserting the buffer into a particular position in said ordered list further comprises the step of adding the buffer in a position other than the tail of the ordered list.

40. The computer-readable medium of claim 21, wherein the step of removing the buffer from the ordered list further comprises the step of removing the buffer from a position in said ordered list without removing the buffer currently at the head of the ordered list.

47. The computer system of claim 35, wherein the step of inserting the buffer into a particular position in said ordered list further comprises the step of adding the buffer to the tail of the ordered list.

48. The computer system of claim 35, wherein the step of inserting the buffer into a particular position in said ordered list further comprises the step of adding the buffer in a position other than the tail of the ordered list.

49. The computer system of claim 35, wherein the step of removing the buffer from the ordered list further comprises the step of removing the buffer from a position in said ordered list without removing the buffer currently at the head of the ordered list.

41. A computer system for maintaining a checkpoint value that indicates which records of a plurality of records associated with updates made before a failure have to be processed after the failure, 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;

maintaining an ordered list of buffers, wherein buffers within said ordered list of buffers reside in volatile memory, wherein the ordered list of buffers has a head and a tail, the step of maintaining the ordered list including the steps of

when an update is made to a data item within a buffer in volatile memory, performing the steps of

writing a record that indicates the update to nonvolatile memory; and

inserting the buffer into a particular position in said ordered list in a manner that preserves relative ordering of buffers already in said ordered list;

when a data item contained in a buffer within the ordered list is stored in nonvolatile memory, removing the buffer from the ordered list; and

writing to nonvolatile memory as said checkpoint value, a value that identifies a record of said plurality of records that is associated with a buffer that is currently located at the head of the ordered list.

42. The computer system of claim 41, wherein the set of computer instructions further comprises computer instructions for performing the following steps after the failure:

identifying the record associated with the checkpoint value;

if a particular record was stored to nonvolatile memory before the record associated with the checkpoint value, then not processing the particular record; and

if the particular record was not stored to nonvolatile memory before the record associated with the checkpoint value, then processing the particular record.

43. The computer system of claim 41, wherein the step of inserting the buffer into a particular position in said ordered list further comprises the step of sorting the buffer into the ordered list based on when the record associated with the buffer is stored to nonvolatile memory relative to when the records associated with the buffers that are already in the ordered list were stored to nonvolatile memory.

44. The computer system of claim 41, wherein the step of removing the buffer from the ordered list further comprises the step of removing a particular number of the buffers, wherein the particular number of buffers that are removed dynamically adjusts according to how many of the buffers currently reside in the ordered list.

45. The computer system of claim 41, wherein the step of inserting the buffer into a particular position in said ordered list further comprises the steps of:

obtaining an index value, wherein the index value corresponds to a storage location in nonvolatile memory;

storing the index value as the index value for the buffer; and

inserting the buffer into the ordered list based on the index value for the buffer.

46. The computer system of claim 41, wherein:

each buffer is associated with an index value, wherein said index value identifies where the record associated with each buffer is written to nonvolatile memory;

said step of inserting the buffer into a particular position in said ordered list includes the step of inserting the buffer into a particular position of one of a plurality of ordered lists;

said step of writing to nonvolatile memory as said checkpoint value the value that identifies the record associated with the buffer located at the head of the ordered list includes the step of writing to nonvolatile memory the checkpoint value that identifies the record associated with a particular buffer located at the head of one of the plurality of ordered lists, wherein said particular buffer is associated with a smallest index value of all buffers located at the head of the one of the plurality of ordered lists; and

said step of removing the buffer from the ordered list includes the step of removing the buffer from one of the plurality of ordered lists.

50. A method for maintaining a checkpoint value that indicates which records of a plurality of records associated with updates made before a failure have to be processed after the failure, the method comprising the steps of:

maintaining a sorted buffer queue that includes a head and a tail, wherein the sorted buffer queue includes queue entries that are inserted into said sorted buffer queue based on an index value that is associated with each queue entry;

removing queue entries from said sorted buffer queue only after information associated with said queue entries is stored in nonvolatile memory; and

repeatedly updating the checkpoint value to equal the index value that is currently associated with the queue entry at the head of the sorted buffer queue.

52. The method of claim 50, further comprising performing the following steps after the failure:

identifying a record that is associated with the checkpoint value;

if a particular record was stored to nonvolatile memory before the record associated with the checkpoint value, then not processing the particular record; and

if a particular record was not stored to nonvolatile memory before the record associated with the checkpoint value, then processing the particular record.

53. The method of claim 50, wherein the step of inserting the queue entries into said sorted buffer queue further comprises the step of adding the queue entries to the sorted buffer queue only if the queue entries do not already reside in the sorted buffer queue.

54. The method of claim 52, wherein the step of processing the particular record if the particular record was not stored to nonvolatile memory before the record associated with the checkpoint value further comprises the step of processing all records sequentially stored at locations that follow a location at which the record associated with the checkpoint value is stored.

55. The method of claim 54, further comprising the step of processing the record associated with the checkpoint value.

56. The method of claim 50, wherein the step of repeatedly updating the checkpoint value further comprises the step of writing to nonvolatile memory the checkpoint value at predetermined time intervals.

57. The method of claim 50, wherein the step of removing the queue entries from the sorted buffer queue further comprises the step of removing a particular number of queue entries, wherein the particular number of queue entries that are removed dynamically adjusts according to how many of the queue entries currently reside in the sorted buffer queue.

58. The method of claim 50, wherein the step of removing the queue entries from the sorted buffer queue further comprises the step of removing a particular number of queue entries, wherein the step of removing the particular number of queue entries is performed at a frequency that dynamically adjusts according to how many queue entries currently reside in the sorted buffer queue.

59. The method of claim 50, wherein the step of removing the queue entries from the sorted buffer queue further comprises the step of removing the queue entries from a position in said sorted buffer queue other than the head of the sorted buffer queue.

60. The method of claim 50, wherein the step of removing the queue entries from the sorted buffer queue further comprises the steps of:

determining if the queue entries were updated while being removed from the sorted buffer queue;

if the queue entries were updated while being removed from the sorted buffer queue, then inserting the updated queue entries back into the sorted buffer queue.

61. The method of claim 50, wherein the step of inserting the queue entries into said sorted buffer queue further comprises the step of adding the queue entries to the tail of the sorted buffer queue.

62. The method of claim 50, wherein the step of inserting the queue entries into said sorted buffer queue further comprises the step of adding the queue entries in a position other than the tail of the sorted buffer queue.

63. The method of claim 50, wherein the step of removing queue entries from the sorted buffer queue further comprises the step of removing queue entries from a position in said sorted buffer queue without removing the queue entries currently at the head of the sorted buffer queue.

51. A computer-readable medium carrying one or more sequences of instructions for maintaining a checkpoint value that indicates which records of a plurality of records associated with updates made before a failure have to be processed after the failure, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of:

maintaining a sorted buffer queue that includes a head and a tail, wherein the sorted buffer queue includes queue entries that are inserted into said sorted buffer queue based on an index value that is associated with each queue entry;

removing queue entries from said sorted buffer queue only after information associated with said queue entries is stored in nonvolatile memory; and

repeatedly updating the checkpoint value to equal the index value that is currently associated with the queue entry at the head of the sorted buffer queue.

64. The computer-readable medium of claim 51, further comprising instructions for performing the following steps after the failure:

identifying a record that is associated with the checkpoint value;

if a particular record was stored to nonvolatile memory before the record associated with the checkpoint value, then not processing the particular record; and

if the particular record was not stored to nonvolatile memory before the record associated with the checkpoint value, then processing the particular record.

65. The computer-readable medium of claim 51, wherein the step of inserting the queue entries into said sorted buffer queue further comprises the step of adding the queue entries to the sorted buffer queue only if the queue entries do not already reside in the sorted buffer queue.

66. The computer-readable medium of claim 64, wherein the step of processing the particular record if the particular record was not stored to nonvolatile memory before the record associated with the checkpoint value further comprises the step of processing all records sequentially stored at locations that follow a location at which the record associated with the checkpoint value is stored.

67. The computer-readable medium of claim 66, further comprising instruction for performing the step of processing the record associated with the checkpoint value.

68. The computer-readable medium of claim 51, wherein the step of repeatedly updating the checkpoint value further comprises the step of writing to nonvolatile memory the checkpoint value at predetermined time intervals.

69. The computer-readable medium of claim 51, wherein the step of removing the queue entries from the sorted buffer queue further comprises the step of removing a particular number of queue entries, wherein the particular number of queue entries that are removed dynamically adjusts according to how many of the queue entries currently reside in the sorted buffer queue.

70. The computer-readable medium of claim 51, wherein the step of removing the queue entries from the sorted buffer queue further comprises the step of removing a particular number of queue entries, wherein the step of removing the particular number of queue entries is performed at a frequency that dynamically adjusts according to how many queue entries currently reside in the sorted buffer queue.

71. The computer-readable medium of claim 51, wherein the step of removing the queue entries from the sorted buffer queue further comprises the step of removing the queue entries from a position in said sorted buffer queue other than the head of the sorted buffer queue.

72. The computer-readable medium of claim 51, wherein the step of removing the queue entries from the sorted buffer queue further comprises the steps of:

determining if the queue entries were updated while being removed from the sorted buffer queue;

if the queue entries were updated while being removed from the sorted buffer queue, then inserting the updated queue entries back into the sorted buffer queue.

73. The computer-readable medium of claim 51, wherein the step of inserting the queue entries into said sorted buffer queue further comprises the step of adding the queue entries to the tail of the sorted buffer queue.

74. The computer-readable medium of claim 51, wherein the step of inserting the queue entries into said sorted buffer queue further comprises the step of adding the queue entries in a position other than the tail of the sorted buffer queue.

75. The computer-readable medium of claim 51, wherein the step of removing queue entries from the sorted buffer queue further comprises the step of removing queue entries from a position in said sorted buffer queue without removing the queue entries currently at the head of the sorted buffer queue.