Method and apparatus for using undo/redo logging to perform asynchronous updates of parity and data pages in a redundant array data storage environment

• US 6,041,423 A
• Filed: 11/08/1996
• Issued: 03/21/2000
• Est. Priority Date: 11/08/1996
• Status: Expired due to Term

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle Corporation
• Inventors: Tsukerman, Alex
• Primary Examiner(s): Beausoliel, Jr., Robert W.
• Assistant Examiner(s): Iqbal, Nadeem
• Application Number:
  US08/747,064
• Time in Patent Office: 1,229 Days
• Field of Search: 395/181, 395/182.03, 395/182.04, 395/182.06, 395/182.13, 395/182.14, 395/182.17, 395/182.18, 395/182.19, 395/427, 395/441, 395/428 , 395/182.05, 395/182.1, 395/183.18, 371/40.15, 371/10.3, 371/51.1, 711/114, 714/19, 714/1, 714/5, 714/20, 714/42
• US Class Current: 714/19
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems

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.

Claims

1. 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.

2. 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.

3. 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.

8. 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.

9. 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.

4. 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.

5. 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.

6. 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.

7. 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.

10. 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.

11. 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.

13. 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.

14. 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.

15. 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.

12. 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.

16. 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.

17. 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.

18. 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.

19. 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.

20. 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.

21. 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.

22. 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.

23. 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.

24. 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.