US6041423A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for using undo/redo logging to perform asynchronous updates of parity and data pages in a redundant array data storage environment
Assignee: Oracle International Corp
•
Filing: 1996-11-08
•
Granted: 2000-03-21
•
Expires: 2016-11-08
Abstract
Abstract A method and apparatus for using undo/redo logging to perform asynchronous updates of parity and data pages in a redundant array data storage system is disclosed. The computer-implemented apparatus includes, 1) a redundant array data storage system having a plurality of data pages and a corresponding parity page residing therein, each page of the plurality of data pages and the parity page containing version information indicating a version of content in the page, 2) a memory-resident plurality of data pages corresponding to the plurality of data pages residing in the redundant array data storage system, 3) a data log retaining modification information defining any differences between content of the memory-resident plurality of data pages and content of the plurality of data pages residing in the redundant array data storage system, and 4) control logic for deferring modification of the parity page following modification of one of the plurality of data pages. The control logic further includes control logic for re-creating content of one of the plurality of data pages or the parity page by applying the modification information in the data log to the memory-resident plurality of data pages.
Inventors
- 👤 Alex Tsukerman
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-03 21:35
CPC Classifications
G; G06; G06F; G06F11/00; G06F11/07; G06F11/08; G06F11/10; G06F11/1076
Claims Analysis
Total Claims: 32
Claim 1
Independent Claim
210 words
A method of updating data in a redundant array storage system that includes a plurality of data pages and a corresponding parity page, the method comprising: performing multiple modifications to the plurality of data pages; deferring update of the parity page until after the multiple modifications have been performed; updating the parity page in a single parity page update operation to bring the parity page up to date with the multiple modifications performed on the plurality of data pages, wherein updating the parity page in a single parity page update operation comprises updating the parity page based on most recent versions of each of the plurality of data pages; retaining information in a data log for undoing the multiple modifications and for re-doing the multiple modifications; detecting loss of one of the most recent versions of the plurality of data pages due to a system failure, the system failure occurring after one or more of the plurality of data pages in the redundant array storage system is updated to reflect the multiple modifications and before updating the parity page; and regenerating the one of the most recent versions of the plurality of data pages based on the information in the data log and a stale version of the parity page.
Claim 2
Independent Claim
210 words
A method of updating data in a redundant array storage system that includes a plurality of data pages and a corresponding parity page, the method comprising: performing multiple modifications to the plurality of data pages; deferring update of the parity page until after the multiple modifications have been performed; updating the parity page in a single parity page update operation to bring the parity page up to date with the multiple modifications performed on the plurality of data pages, wherein updating the parity page in a single parity page update operation comprises updating the parity page based on most recent versions of each of the plurality of data pages; retaining information in a data log for undoing the multiple modifications and for re-doing the multiple modifications; detecting loss of one of the most recent versions of the plurality of data pages due to a system failure, the system failure occurring after one or more of the plurality of data pages in the redundant array storage system is updated to reflect the multiple modifications and before updating the parity page; and regenerating the one of the most recent versions of the plurality of data pages based on the information in the data log and a stale version of the parity page.
Claim 3
Dependent Claim
69 words
The method of claim 1 wherein updating the parity page base on most recent versions of each of the plurality of data pages comprises exclusive ORing the parity page with stale versions of each of the plurality of data pages modified in the multiple modifications and exclusive ORing the parity page with the most recent versions of each of the plurality of data pages modified in the multiple modifications.
Claim 4
Dependent Claim
123 words
The method of claim 1 wherein regenerating the one of the most recent versions of the plurality of data pages based on the information in the data log and the stale version of the parity page comprises: undoing one or more modifications according to the information in the data log to generate one or more stale versions of the plurality of data pages; combining the one or more stale versions of the plurality of data pages with the stale version of the parity page to generate a stale version of the lost data page; and re-doing one or more modifications according to the information in the data log to regenerate the lost data page from the stale version of the lost data page.
Claim 5
Independent Claim
194 words
A method of updating data in a redundant array storage system that includes a plurality of data pages and a corresponding parity page, the method comprising: performing multiple modifications to the plurality of data pages; deferring update of the parity page until after the multiple modifications have been performed; updating the parity page in a single parity page update operation to bring the parity page up to date with the multiple modifications performed on the plurality of data pages; retaining information in a data log for undoing the multiple modifications and for re-doing the multiple modifications; detecting loss of a most recent version of one of the plurality of data pages and loss of a stale version of the one of the plurality of data pages due to a system failure; regenerating the stale version of the one of the plurality of data pages based on a stale version of the parity page; and regenerating the most recent version of the one of the plurality of data pages from the stale version of the one of the plurality of data pages and from the information in the data log for re-doing the multiple modifications.
Claim 6
Independent Claim
194 words
A method of updating data in a redundant array storage system that includes a plurality of data pages and a corresponding parity page, the method comprising: performing multiple modifications to the plurality of data pages; deferring update of the parity page until after the multiple modifications have been performed; updating the parity page in a single parity page update operation to bring the parity page up to date with the multiple modifications performed on the plurality of data pages; retaining information in a data log for undoing the multiple modifications and for re-doing the multiple modifications; detecting loss of a most recent version of one of the plurality of data pages and loss of a stale version of the one of the plurality of data pages due to a system failure; regenerating the stale version of the one of the plurality of data pages based on a stale version of the parity page; and regenerating the most recent version of the one of the plurality of data pages from the stale version of the one of the plurality of data pages and from the information in the data log for re-doing the multiple modifications.
Claim 7
Dependent Claim
55 words
The method of claim 4 wherein regenerating the stale version of the one of the plurality of data pages based on a stale version of the parity page comprises combining the stale version of the parity page with one or more stale versions of the plurality of data pages other than the lost stale version.
Claim 8
Dependent Claim
64 words
The method of claim 5 wherein combining the stale version of the parity page with one or more stale versions of the plurality of data pages other than the lost stale version comprises regenerating the one or more stale versions of the plurality of data pages other than the lost stale version from the information in the data log for undoing the multiple modifications.
Claim 9
Independent Claim
227 words
A method of updating data in a redundant array storage system that includes a plurality of data pages and a corresponding parity page, the method comprising: performing multiple modifications to the plurality of data pages; deferring update of the parity page until after the multiple modifications have been performed; updating the parity page in a single parity page update operation to bring the parity page up to date with the multiple modifications performed on the plurality of data pages; retaining information in a data log for re-doing the multiple modifications; detecting loss of most recent versions of the plurality of data pages generated by the multiple modifications and loss of at least one stale version of a first data page of the plurality of data pages due to a system failure, the system failure occurring after updating the parity page to an up-to-date parity page that is up to date with the multiple modifications; regenerating each of the most recent versions of the plurality of data pages except a most recent version of the first data page based on the information in the data log for re-doing the multiple modifications; and regenerating the most recent version of the first data page by combining the up-to-date parity page with the most recent versions of the plurality of data pages regenerated based on the information in the data log.
Claim 10
Independent Claim
227 words
A method of updating data in a redundant array storage system that includes a plurality of data pages and a corresponding parity page, the method comprising: performing multiple modifications to the plurality of data pages; deferring update of the parity page until after the multiple modifications have been performed; updating the parity page in a single parity page update operation to bring the parity page up to date with the multiple modifications performed on the plurality of data pages; retaining information in a data log for re-doing the multiple modifications; detecting loss of most recent versions of the plurality of data pages generated by the multiple modifications and loss of at least one stale version of a first data page of the plurality of data pages due to a system failure, the system failure occurring after updating the parity page to an up-to-date parity page that is up to date with the multiple modifications; regenerating each of the most recent versions of the plurality of data pages except a most recent version of the first data page based on the information in the data log for re-doing the multiple modifications; and regenerating the most recent version of the first data page by combining the up-to-date parity page with the most recent versions of the plurality of data pages regenerated based on the information in the data log.
Claim 11
Dependent Claim
32 words
The method of claim 1 wherein performing multiple modifications to the plurality of data pages comprises performing a first modification and a second modification to one of the plurality of data pages.
Claim 12
Dependent Claim
47 words
The method of claim 1 wherein performing multiple modifications to the plurality of data pages comprises performing a first modification to a first data page of the plurality of data pages and performing a second modification to a second data page of the plurality of data pages.
Claim 13
Dependent Claim
215 words
An article of manufacture including one or more computer-readable media that embody a program of instructions to update data in a redundant array storage system that includes a plurality of data pages and a corresponding parity page, wherein the program of instructions, when executed by one or more processors in a processing system, causes the one or more processors to: perform multiple modifications to the plurality of data pages; defer update of the parity page until after the multiple modifications have been performed; and update the parity page in a single parity page update operation to bring the parity page up to date with the multiple modifications performed on the plurality of data pages; retain information in a data log for undoing the multiple modifications and for re-doing the multiple modifications; detect loss of one of the most recent versions of the plurality of data pages due to a system failure, the system failure occurring after one or more of the plurality of data pages in the redundant array storage system is updated to reflect the multiple modifications and before updating the parity page; and regenerate the one of the most recent versions of the plurality of data pages based on the information in the data log and a stale version of the parity page.
Claim 14
Dependent Claim
215 words
An article of manufacture including one or more computer-readable media that embody a program of instructions to update data in a redundant array storage system that includes a plurality of data pages and a corresponding parity page, wherein the program of instructions, when executed by one or more processors in a processing system, causes the one or more processors to: perform multiple modifications to the plurality of data pages; defer update of the parity page until after the multiple modifications have been performed; and update the parity page in a single parity page update operation to bring the parity page up to date with the multiple modifications performed on the plurality of data pages; retain information in a data log for undoing the multiple modifications and for re-doing the multiple modifications; detect loss of one of the most recent versions of the plurality of data pages due to a system failure, the system failure occurring after one or more of the plurality of data pages in the redundant array storage system is updated to reflect the multiple modifications and before updating the parity page; and regenerate the one of the most recent versions of the plurality of data pages based on the information in the data log and a stale version of the parity page.
Claim 15
Dependent Claim
56 words
The article of claim 10 wherein the program of instructions that causes the one or more processors to update the parity page in a single parity page update operation comprises instructions to cause the one or more processors to update the parity page based on most recent versions of each of the plurality of data pages.
Claim 16
Dependent Claim
236 words
A data processing system comprising: a redundant array storage system that includes a plurality of data pages and a corresponding parity page; and a computer coupled to the redundant array storage system, the computer including a processing unit and a memory, the memory having stored therein a program of instructions to configure the computer to update data in the redundant array storage system, wherein the program of instructions, when executed by the processing unit of the computer, causes the computer to: perform multiple modifications to the plurality of data pages; defer update of the parity page until after the multiple modifications have been performed; and update the parity page in a single parity page update operation to bring the parity page up to date with the multiple modifications performed on the plurality of data pages; retain information in a data log for undoing the multiple modifications and for re-doing the multiple modifications; detect loss of one of the most recent versions of the plurality of data pages due to a system failure, the system failure occurring after one or more of the plurality of data pages in the redundant array storage system is updated to reflect the multiple modifications and before updating the parity page; and regenerate the one of the most recent versions of the plurality of data pages based on the information in the data log and a stale version of the parity page.
Claim 17
Dependent Claim
236 words
A data processing system comprising: a redundant array storage system that includes a plurality of data pages and a corresponding parity page; and a computer coupled to the redundant array storage system, the computer including a processing unit and a memory, the memory having stored therein a program of instructions to configure the computer to update data in the redundant array storage system, wherein the program of instructions, when executed by the processing unit of the computer, causes the computer to: perform multiple modifications to the plurality of data pages; defer update of the parity page until after the multiple modifications have been performed; and update the parity page in a single parity page update operation to bring the parity page up to date with the multiple modifications performed on the plurality of data pages; retain information in a data log for undoing the multiple modifications and for re-doing the multiple modifications; detect loss of one of the most recent versions of the plurality of data pages due to a system failure, the system failure occurring after one or more of the plurality of data pages in the redundant array storage system is updated to reflect the multiple modifications and before updating the parity page; and regenerate the one of the most recent versions of the plurality of data pages based on the information in the data log and a stale version of the parity page.
Claim 18
Dependent Claim
123 words
The article of claim 10 wherein regenerating the one of the most recent versions of the plurality of data pages based on the information in the data log and the stale version of the parity page comprises: undoing one or more modifications according to the information in the data log to generate one or more stale versions of the plurality of data pages; combining the one or more stale versions of the plurality of data pages with the stale version of the parity page to generate a stale version of the lost data page; and re-doing one or more modifications according to the information in the data log to regenerate the lost data page from the stale version of the lost data page.
Claim 19
Dependent Claim
32 words
The article of claim 10 wherein performing multiple modifications to the plurality of data pages comprises performing a first modification and a second modification to one of the plurality of data pages.
Claim 20
Dependent Claim
47 words
The article of claim 10 wherein performing multiple modifications to the plurality of data pages comprises performing a first modification to a first data page of the plurality of data pages and performing a second modification to a second data page of the plurality of data pages.
Claim 21
Dependent Claim
228 words
An article of manufacture including one or more computer-readable media that embody a program of instructions to update data in a redundant array storage system that includes a plurality of data pages and a corresponding parity page, wherein the program of instructions, when executed by one or more processors in a processing system, causes the one or more processors to: perform multiple modifications to the plurality of data pages; defer update of the parity page until after the multiple modifications have been performed; update the parity page in a single parity page update operation to bring the parity page up to date with the multiple modifications performed on the plurality of data pages; retain information in a data log for undoing the multiple modifications and for re-doing the multiple modifications; detect loss of a most recent version of one of the plurality of data pages and loss of a stale version of the one of the plurality of data pages due to a system failure; regenerate the stale version of the one of the plurality of data pages based on a stale version of the parity page; and regenerate the most recent version of the one of the plurality of data pages from the stale version of the one of the plurality of data pages and from the information in the data log for re-doing the multiple modifications.
Claim 22
Dependent Claim
228 words
An article of manufacture including one or more computer-readable media that embody a program of instructions to update data in a redundant array storage system that includes a plurality of data pages and a corresponding parity page, wherein the program of instructions, when executed by one or more processors in a processing system, causes the one or more processors to: perform multiple modifications to the plurality of data pages; defer update of the parity page until after the multiple modifications have been performed; update the parity page in a single parity page update operation to bring the parity page up to date with the multiple modifications performed on the plurality of data pages; retain information in a data log for undoing the multiple modifications and for re-doing the multiple modifications; detect loss of a most recent version of one of the plurality of data pages and loss of a stale version of the one of the plurality of data pages due to a system failure; regenerate the stale version of the one of the plurality of data pages based on a stale version of the parity page; and regenerate the most recent version of the one of the plurality of data pages from the stale version of the one of the plurality of data pages and from the information in the data log for re-doing the multiple modifications.
Claim 23
Dependent Claim
55 words
The article of claim 16 wherein regenerating the stale version of the one of the plurality of data pages based on a stale version of the parity page comprises combining the stale version of the parity page with one or more stale versions of the plurality of data pages other than the lost stale version.
Claim 24
Dependent Claim
64 words
The article of claim 17 wherein combining the stale version of the parity page with one or more stale versions of the plurality of data pages other than the lost stale version comprises regenerating the one or more stale versions of the plurality of data pages other than the lost stale version from the information in the data log for undoing the multiple modifications.
Claim 25
Independent Claim
110 words
A method of recovering data in a redundant array storage system that includes a plurality of data pages and a parity page, the method comprising: detecting loss of a first data page of the plurality of data pages after modification of a second data page of the plurality of data pages and before the parity page is modified to reflect the modification of the second data page; undoing the modification to the second data page to generate a previous version of the second data page that corresponds to the parity page; and recovering the first data page using the previous version of the second data page and the parity page.
Claim 26
Independent Claim
110 words
A method of recovering data in a redundant array storage system that includes a plurality of data pages and a parity page, the method comprising: detecting loss of a first data page of the plurality of data pages after modification of a second data page of the plurality of data pages and before the parity page is modified to reflect the modification of the second data page; undoing the modification to the second data page to generate a previous version of the second data page that corresponds to the parity page; and recovering the first data page using the previous version of the second data page and the parity page.
Claim 27
Dependent Claim
71 words
The method of claim 19 wherein recovering the first data page using the previous version of the second data page and the parity page comprises: generating a previous version of the first data page using the previous version of the second data page and the parity page; and redoing a modification to the previous version of the first data page to generate a more recent version of the first data page.
Claim 28
Dependent Claim
42 words
The method of claim 20 wherein redoing a modification to the previous version of the first data page to generate a more recent version of the first data page comprises redoing the modification based on modification information stored in an redo log.
Claim 29
Dependent Claim
37 words
The method of claim 19 wherein undoing the modification to the second data page to generate a previous version of the second data page comprises undoing the modification based on modification information stored in an undo log.
Claim 30
Dependent Claim
39 words
The method of claim 19 wherein recovering the first data page using the previous version of the second data page and the parity page comprises exclusive ORing the previous version of the second data page and the parity page.
Claim 31
Dependent Claim
145 words
An article of manufacture including one or more computer-readable media that embody a program of instructions to recover data in a redundant array storage system that includes a plurality of data pages and a corresponding parity page, wherein the program of instructions, when executed by one or more processors in a processing system, causes the one or more processors to: detect loss of a first data page of the plurality of data pages after modification of a second data page of the plurality of data pages and before the parity page is modified to reflect the modification of the second data page; undo the modification to the second data page to generate a previous version of the second data page that corresponds to the parity page; and recover the first data page using the previous version of the second data page and the parity page.
Claim 32
Dependent Claim
145 words
An article of manufacture including one or more computer-readable media that embody a program of instructions to recover data in a redundant array storage system that includes a plurality of data pages and a corresponding parity page, wherein the program of instructions, when executed by one or more processors in a processing system, causes the one or more processors to: detect loss of a first data page of the plurality of data pages after modification of a second data page of the plurality of data pages and before the parity page is modified to reflect the modification of the second data page; undo the modification to the second data page to generate a previous version of the second data page that corresponds to the parity page; and recover the first data page using the previous version of the second data page and the parity page.
References Cited (Backward Citations)
US4761785B1
Cited
US4761785A
Cited
US5469453A
Cited
US5524205A
Cited
US5208813A
Cited
US5341831A
Cited
US5448578A
Cited
US5488731A
Cited
US5490248A
Cited
US5390327A
Cited
US5537567A
Cited
US5546558A
Cited
US5497457A
Cited
US5574882A
Cited
US5720025A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-03-21 | 2003-09-20 | 2004-03-21 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-03-21 | 2007-09-20 | 2008-03-21 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-03-21 | 2011-09-20 | 2012-03-21 | $7700.00 | Window Closed / Lapsed |