System and method for maintaining and recovering data consistency across multiple instances of a database

• US 6,751,636 B1
• Filed: 12/05/2000
• Issued: 06/15/2004
• Est. Priority Date: 12/05/2000
• Status: Expired due to Term

• Current Assignee: RPX Corporation
• Original Assignee: Silicon Graphics Incorporated (Graphics Properties Holdings, Inc.)
• Inventors: Mende, Jr., Robert G., Vasa, Mayank V.
• Primary Examiner(s): Amsbury, Wayne
• Assistant Examiner(s): AL HASHEMI, SANA A
• Application Number:
  US09/730,618
• Time in Patent Office: 1,288 Days
• Field of Search: 707/202, 707/203, 707/204, 707/103.R, 707/200, 709/223
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

The present invention is a system and method that facilitates consistency maintenance and recovery from a system or process crash with valid data. A data consistency maintenance and recovery system and method of the present invention utilizes a dual page configuration and locking process to store and track data associated with multiple indexes of a database. A primary page is utilized as the primary data storage location and a mirror page operates as copy of the primary page except during certain stages of data manipulation (e.g., a write operation). Read operations access information from unlocked primary pages. Write operations access, lock and update a mirror page, then access, lock and update a primary page. Page accesses are tracked (e.g., counted). Then a write process unlocks and syncs the primary page to disk as well as the mirror page. A page with consistent data is copied to a page with inconsistent data during a process system crash recovery. In one embodiment of the present invention, a primary page is considered consistent if a write operation has not accessed the primary page to begin a write process, otherwise data on a mirror page is considered consistent. In one embodiment of the present invention, a consistency maintenance locking method and an access tracking method are utilized to facilitate consistency maintenance across multiple instances of the MDBM database.

Claims

1. A computer implemented data consistency maintenance method for maintaining consistency through a plurality of multiple instances stored in a page based memory mapped, multiple anonymous reader, multiple writer database, comprising the steps of:

accessing a mirror pages including a copy instance of indexed data associated with a particular value during a write access request operation;

accessing a primary page associated with said mirror page;

acquiring a genlock on said mirror page;

updating said copy instance of indexed data included in said mirror page;

acquiring a genlock on a primary page associated with said mirror page;

performing an update on an instance of indexed data associated with said particular value on said primary page;

preventing read operations and write operations of other processes from accessing said mirror page and said primary page while locked; and

releasing said genlock on said primary page and said genlock on said mirror page.

2. A data consistency maintenance method of claim 1 further comprising the steps of keeping said mirror page and said primary page in lockstep except during a write operation.

3. A data consistency method of claim 1 further comprising the steps of:

retrieving said mirror page from a database; and

mapping said mirror page into a local memory if not already stored in said local memory.

4. A data consistency maintenance method of claim 1 further comprising the steps of:

utilizing a lowest order bit of an access counter value to function as said genlock; and

incrementing said access counter value each time a write access is performed.

5. A computer implemented consistency recovery method for recovering consistency across multiple instances of a page based memory mapped, multiple anonymous reader, multiple writer database after a process crash, comprising the steps of:

determining an appropriate primary page for comparison to a mirror page;

resolving the data to be utilized as valid data when recovering from a process or system crash;

evaluating access counter values of the primary page and the mirror page, wherein each access counter value includes a genlock; and

restoring consistency.

6. A computer implemented consistency recovery method of claim 5 further comprising the step of allowing a writer to either complete or abort a transaction that crashed.

7. A computer implemented consistency recovery method of claim 5 wherein both said appropriate primary page and said mirror page are consistent if the access counter values of both said appropriate primary page and said mirror page are equal and they are both unlocked.

8. A computer implemented consistency recovery method of claim 5 wherein said appropriate primary page is consistent if an access counter value of said appropriate primary page is less than an access counter value of said mirror page and said appropriate primary page is unlocked and said mirror page is locked.

9. A computer implemented consistency recovery method of claim 5 wherein said mirror page is consistent if an access counter value of said appropriate primary page is equal to an access counter value of said mirror page and said primary page and said mirror page are locked.

10. A computer implemented consistency recovery method of claim 5 wherein said mirror page is consistent if the access counter value of said appropriate primary page is greater than the access counter value of said mirror page and said appropriate primary page is unlocked and said mirror page is locked.

11. A computer implemented consistency recovery method of claim 5 wherein said appropriate primary page and said mirror page are considered to be in an invalid state if said appropriate primary page is locked and the mirror page is unlocked and data included in said mirror page is considered valid for purposes of consistency restoration.

12. A computer implemented consistency recovery method for recovering consistency across multiple instances of a page based memory mapped, multiple anonymous reader, multiple writer database after a process crash, comprising the steps of:

determining an appropriate primary page for comparison to a mirror page;

resolving the data to be utilized as valid data when recovering from a process or system crash;

examining an atomic consistency element, wherein a first primary page comprising a bucket of information that is not an initial bucket of information associated with a particular value is said appropriate primary page if said atomic consistency elements is zero and second primary page that is an initial bucket of information associated with a particular value is said appropriate primary page if said atomic consistency is not zero; and

restoring consistency.

13. A data consistency maintenance and recovery computer system comprising:

a bus for providing a communication path between components of computer system;

a central processing unit (CPU) coupled to said bus, said CPU for performing information control and data processing including a first process and a second process that perform a write operation and read operation except when prevented by a genlock; and

a database coupled to said bus, said database stores information in multiple indexes onto the same data including records comprising fields arranged on a plurality primary pages and maintains a plurality of mirror pages that are a copy of the data included in said plurality of primary pages except when a process performs a write operation, wherein said mirror page is written to before said primary page during said write operation, wherein each one of said plurality of primary pages and each one of said plurality of mirror pages include an access counter value, wherein each access counter value includes a genlock.

14. The data consistency and recovery computer system of claim 13 wherein said data consistency maintenance and recovery computer system compares the status of said lock included in one of said plurality of primary pages to the status of said lock included in said one plurality of said mirror pages comprising a copy of data in said one of said plurality of primary pages and compares an access counter value of said one of said plurality of primary pages to an access counter value of said one of said plurality of mirror pages to determine whether said one of said plurality of primary pages and said one of said plurality of said mirror pages are consistent after recovering from a process or system crash.

15. The data consistency maintenance and recovery computer system of claim 13 wherein said genlock is the lowest order bit of said access counter value.

16. The data consistency maintenance and recovery computer system of claim 13 wherein said genlock is locked and unlocked by incrementing said access counter value.

17. The data consistency maintenance and recovery computer system of claim 13 wherein said first process and said second process lock one of said plurality of mirror pages and one of said plurality of primary pages when beginning a write operation and unlock said one of said plurality of said mirror pages and said one of said plurality of primary pages when finishing a write operation.