IN-MEMORY DATABASE SYSTEM

• US 20020087500A1
• Filed: 08/18/1998
• Published: 07/04/2002
• Est. Priority Date: 08/18/1998
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: BERKOWITZ, BRIAN T., MEIN, GUNNAR, CHRISTOFFERSON, PETER A., SIMHADRI, SREENIVAS
• Granted Patent: US 6,457,021 B1
• Time in Patent Office: Days
• US Class Current: 707/1
• CPC Class Codes: G06F 16/2308 Concurrency control transaction processing G06F9/466
• CPC Class Codes: G06F 16/2329 using versioning
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users

Abstract

An in-memory database system uses a shared memory to cache records and keys read from a database and controls the updating of the records and keys through a database manager process. When a transaction performs an update, the original, unmodified data is preserved in the shared memory, the new data is written to the shared memory, and a look-aside table for the transaction records the changes. A transaction performs read-only access to the shared memory using its own context while a versioning scheme based on the look-aside tables ensures a read-committed isolation level view of the original, unmodified data until the modifying transaction commits the update. The database manager is responsible for writing the new data into the shared memory and for maintaining the look-aside tables for all transaction which have made modifications to the data in the shared memory. The database manager also writes committed changes to the database and performs rollback on uncommitted changes in the shared memory using the entries in the look-aside table for the committing/aborting transaction. The shared memory is divided into logical pages and short duration page latches are employed to maintain consistency on the page while a transaction or the database manager is reading or writing data on the page.

Claims

1. A computerized method for controlling access to database records stored in memory shared among multiple processes comprising:

creating a record entry in look-aside table for a process when the process updates a database;

preserving any original database record affected by the update; and

giving a process access to a new database record created by the update if a record entry corresponding to the new database record exists in the look-aside table for the process.

2. The computerized method of claim 1, further comprising:

setting a modified flag in the original database record; and

determining if a search of the look-aside table for a process is required when the process accesses a database record based on the state of the modified flag.

3. The computerized method of claim 1, further comprising:

deleting any original database record corresponding to a record entry for a new database record in a look-aside table when the process associated with the look-aside table commits its updates.

4. The computerized method of claim 1, further comprising:

deleting any new database record corresponding to a record entry in a look-aside table when the process associated with the look-aside table aborts its updates.

5. The computerized method of claim 1, further comprising:

creating an index entry in the look-aside table for a process when the process updates key data for a database record;

preserving any original key data affected by the update; and

giving a process access to any new key data created by the update if a key entry corresponding to the new key data exists in the look-aside table for the process.

6. The computerized method of claim 5, further comprising:

marking any new key data as inserted; and

marking any original key data as deleted.

7. The computerized method of claim 5, further comprising:

deleting any original key data corresponding to an index entry for new key data in a look-aside table when the process associated with the look-aside table commits its updates.

8. The computerized method of claim 5, further comprising:

deleting any new key data corresponding to an index entry in a look-aside table when the process associated with the look-aside table aborts its updates.

9. A computerized system comprising:

a plurality of client processes for manipulating data;

a shared memory for caching the data manipulated by the plurality of client processes; and

an in-memory database manager for creating a table in the shared memory for each one of the plurality of client process that requests changes to data in the shared memory, for making the changes, and for modifying the table to reflect changes made to the data requested by the associated client process,

wherein each client process uses its associated table to determine if it has access to changed data in shared memory.

10. The computerized system of claim 9, wherein the in-memory database manager further uses the table associated with a client process to make data changed in response to a request by the client process accessible to the plurality of client processes when the client process commits its changes.

11. The computerized system of claim 9, wherein the in-memory database manager further uses the table associated with a client process to void data changed in response to a request by the client process when the client process aborts its changes.

12. The computerized system of claim 9, further comprising a database located external to the shared memory from which the in-memory database manager reads data into the shared memory and writes data from the shared memory.

14. The computer-readable medium of claim 13, wherein the data in the old record field is null if the new record identified by the new record field is created from a blank record.

15. The computer-readable medium of claim 13, wherein the data in the new record field is null if the old record identified by the old record field is deleted.

16. The computer-readable medium of claim 13, further comprising:

a key record identifier field containing data representing an address for a record containing a key value;

a key length field containing data representing the length of the key in the record identified by the key record identifier field;

a primary key length field containing data representing the length of a primary key associated with the key in the record identified by the key record identifier field;

an index identifier field containing data representing an index structure for the key in the record identified by the key record identifier field; and

a data record identifier field containing data representing an address for a data record associated with the key value identified by the key record identifier field.

19. The computer-readable medium of claim 18, wherein the look-aside table is expanded when the size of the table is not equal to a pre-determined maximum size and the number of entries in with the table is greater than a pre-determined maximum number of entries for the size of the table.

20. The computer-readable medium of claim 19, wherein the look-aside table is contracted when the number of entries in the table is less than one half of the number of entries in a predetermined next smaller size.

21. The computer-readable medium of claim 19, wherein the look-aside table can span multiple pages.

22. The computer-readable medium of claim 19, further comprising determining the look-aside table for a transaction based on a transaction number stored in a transaction table.

23. The computer-readable medium of claim 19, wherein the look-aside table containing record entries and the method further comprises locating a record entry for a record using a table address calculated as

(dw^ bh^ (slot <

<

23))% table size

wherein dw is the low order four bytes of a shared memory page number on which the record is stored, bh is the high byte of the shared memory page number, slot is the slot on the page associated with the entry, ^ is a bit vise exclusive OR operation, <

<

is a left shift operation, and % is a modulo operation.

24. The computer-readable medium of claim 23, wherein the look-aside table further contains index entries associated with key for a record and the method further comprises locating an index entry for a key using a table address calculated as

(OBJID^ (DBID <

<

16)^ indexid <

<

12^ keyhash)% table size

wherein OBJID and DBID identify a database table for the record, indexid identifies the index for the key, keyhash is the result of a rotating exclusive OR'"'"'ing of the bytes of the key, ^ is a bitwise exclusive OR operation, <

<

is a left shift operation, and % is a modulo operation.

26. The method of claim 25, further comprising:

clearing all shared page latches associated with the page when the core process has not obtained the exclusive page latch after a pre-determined period of time has elapsed since the core process requested the exclusive page latch.

13. A computer-readable medium having stored thereon a look-aside table data structure comprising:

an old record field containing data representing a record identifier for an original record;

a new record field containing data representing a record identifier for a new record associated with the original record identified by the old record field; and

a column bitmap field containing data representing columns of data that are different between the original record identified by the old record field and the new record identified by the new record field.

17. A computer-readable medium having stored thereon an transaction table data structure comprising:

a transaction identifier field containing data representing a unique identifier for a transaction; and

a table address field containing data representing a table structure holding update information for the transaction identified by the transaction identifier field.

18. A computer-readable medium having computer-executable instructions to cause a computer to perform a method comprising:

dividing a shared memory into pages and associating an exclusive page latch with each page, and further associating a plurality of shared page latches with each page, wherein the exclusive page latch is acquired by a core process when writing data to a page, and one of the shared page latches is acquired by a client transaction when reading data from a page;

writing unmodified database data in the pages;

creating a look-aside table on a page in response to a client transaction requesting an update to the database data, wherein the look-aside table contains entries for tracking the updates;

writing the updated database data in the pages; and

deleting unmodified database data from the pages when the corresponding updated database data is committed by the transaction that requested the update.

25. A method for maintaining data consistency on a shared memory page comprising:

synchronizing read-only access to the page using a plurality of shared page latches associated with the page, wherein each transaction accessing the page to read data holds one of the plurality of shared page latches for only as long as necessary to read the data; and

synchronizing update access to the page with the read-only accesses to the page using a single exclusive page latch associated with the page, wherein only a core process can request the exclusive page latch, latches the page for update when all shared page latches are released, and holds the exclusive page latch for only as long as necessary to update the data.