Multiple version database concurrency control system

• US 5,280,612 A
• Filed: 11/26/1991
• Issued: 01/18/1994
• Est. Priority Date: 11/26/1991
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Lorie, Raymond A., Mohan, Chandrasekaran, Pirahesh, Mir H.
• Primary Examiner(s): Kulik, Paul V.
• Application Number:
  US07/801,769
• Time in Patent Office: 784 Days
• Field of Search: 395/600, 395/650, 395/425
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2329 using versioning
• CPC Class Codes: G06F 16/2343 Locking methods, e.g. distributed locking or locking implementation details
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database
• CPC Class Codes: Y10S 707/99939 Privileged access
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

An improved concurrency control system for application to a distributed concurrent transaction and query processing system using multi-version database records to overcome delays arising from lock conflicts. Read-only queries are afforded a consistent "stable state" of the database during the life of the query. Updating transactions requiring locks can proceed without waiting for the termination of long queries. At least two database versions are necessary, although availability of more versions permits long read-only queries to phase-out over time without forcing new queries to use aged "stable-state" data and without roll-back. Read-only queries can be terminated and converted to locking transactions to permit an update of the "stable state" database version before the queries would normally terminate. A novel record key structure having a plurality of substructures corresponding to the several database versions is used to access database records. Rapid selection of proper record version and efficient version tracking and updating is effected using several bit-mapped transaction index tables.

Claims

1. In a computer-implemented concurrent transaction and readonly query processing system in which a plurality N of versions of a database are maintained during a present version period (v), said database including a plurality of data records that are updated by said transactions and read by said queries, a plurality of versions of each of said plurality of data records being distributed among said database versions, each said database version (i) consisting essentially of said data records existing at the beginning of the corresponding said version period (i), each said version period (i) being the time interval between one said database version (i) and the next subsequent said database version (i+1), said database versions including a present database version (v), a present stable database version (v-1) and an oldest database version (v-N+1), wherein N is a positive integer greater than 2, a method for concurrency control comprising the unordered steps of:

(a) maintaining a dynamic Uncommitted List (UL) of all said transactions that are uncommitted;

(b) maintaining for said present database version (v) a present version (v) of a Non-Stable and Uncommitted List (NSUL) of all said transactions that are either uncommitted or were committed no earlier than during said present version period(v);

directing all said read-only queries that arrive during said present version period (v) to said data records in said present stable database version (v-1); and

(d) refreshing said present database version (v) by performing the steps of

(d.1) setting a refresh time t after all said read-only queries that arrived during said oldest version period (v-N+2) are terminated,

(d.2) creating a new version (v+1) of said database containing said data records existing at said refresh time t,

(d.3) creating a new version (v+1) of said NSUL containing said transactions listed at said refresh time t in said dynamic UL, and

(d.4) initiating a new version period (v+1) at said refresh time t by assigning said present database version (v) to be the new present stable database version (v), whereby database atomicity is maintained buy using said present stable database version (v) for subsequent read-only query processing without lock conflict or transaction rollback.

2. The method of claim 1 wherein said refreshing step (d) is performed before the updating of a data record written by a previous committed transaction listed in said NSUL.

3. The method of claim 1 wherein said setting step (d.1) further comprises the step of:

(d.1.1) aborting all said read-only queries that had arrived during said oldest version period (v-N+2).

4. The method of claim 2 wherein said processing system includes record accession means for accessing said database records, said record accession means having at least one record key structure corresponding to each said record, said structure having a plurality of substructures each corresponding to one of said N+1 record versions, further comprising the unordered step of:

(e) updating said record key structure corresponding to said updated record.

5. The method of claim 2 wherein:

said UL and NSULs comprise bit maps having at least one bit position corresponding to each said transaction that is still, active or was terminated after the start of said version period (v-N+2).

6. The method of claim 1 wherein said processing system includes record accession means for accessing said database records, said record accession means having at least ne record key structure corresponding to each said record, said structure having a plurality of substructures each corresponding to one of said N+1 record versions, further comprising the step of:

(e) updating said record key structure corresponding to said updated record.

7. The method of claim 1 wherein:

said UL and said NSULs comprise bit maps having at least one bit position corresponding to each said transaction that is still active or was terminated after the start of said oldest version period (v-N+2).

8. In a computer-implemented concurrent transaction and read-only query processing system in which at least two versions of a database are maintained during a present version period, said database including a plurality of data records that are updated by said transactions and read by said queries, at least two versions of each data record of said plurality of data records being distributed among said database versions, each said database version(i) consisting essentially of said data records existing at the beginning of a corresponding said version period (i), each said version period (i) being the time interval between one said database version (i) and the next subsequent said database version (i+1), said versions including a present version and a stable version, a method for concurrency control comprising the underordered steps of:

(a) maintaining a dynamic Uncommitted List (UL) of all said transactions that are uncommitted;

(b) maintaining a Non-Stable and Uncommitted List (NSUL) of all said transactions that are either uncommitted or were committed during said present version period;

(c) directing all said read-only queries that arrive during said present version period to said data records in said stable database version; and

(d) refreshing said present database version by performing the steps of

(d.1) setting a refresh time t after all said read-only queries are terminated,

(d.2) creating a new version of said database containing said data records existing at said refresh time t.

(d.3) resetting said NSUL to equal said UL, and

(d.4) initiating a new version period at said refresh time t by assigning said present database version to be the new stable database version, whereby database atomicity is maintained by using said stable database version for read-only query processing without lock conflict or transaction rollback.

9. The method of claim 8 wherein said refreshing step (d) is performed before updating a record written by a committed transaction listed in said NSUL.

10. The method of claim 8, wherein said setting step (d.1) comprises the step of:

(d.1.1) aborting all said read-only queries that had arrived during the oldest said version period for which a corresponding database version is maintained.

11. The method of claim 8 wherein:

said UL and said NSUL comprise bit maps having at least one bit position corresponding to each said transaction that is still active or was terminated after said start of the stable version period.

12. The method of claim 8 wherein said processing system includes record accession means for accessing said database records, said record accession means having at least one record key structure corresponding to each said record, said structure having a plurality of substructures each corresponding to one of said record versions, further comprising the unordered step of:

(e) updating said record key structure corresponding to said updated record.

13. In a distributed computer-implemented concurrent transaction and query processing system having a plurality of nodes in each of which are maintained portions of up to N versions of a distributed database, said distributed database including a plurality of data records distributed among said nodes, each data record of said plurality of data records being updated by said transactions and read by said queries, a plurality of versions of each said data record being distributed among said database versions, each said database version (i) at each node consisting essentially of the version (i) of said data records existing at said each node at the beginning of a corresponding said version period (i) for each said node, each said version period (i) for said each node being the time interval between one said database version (i) and the next subsequent said database version (i+1) for said each node, said database versions including a present database version (v), a present stable database version (v-1) and an oldest database version (v-N+2), said nodes having both original and received transactions and queries, wherein N is a positive integer greater than 2, a method for concurrency control comprising the unordered steps of:

(a) maintaining within each said node a dynamic Uncommitted List (UL) of all said transactions that are uncommitted within said each node;

(b) maintaining for said present version period (v) within each said node a present version (v) of a Non-Stable and Uncommitted List (NSUL) of all said transactions that are either uncommitted or were committed within said each node no earlier than during said present version period (v) for said each node;

(c) maintaining within each node a dynamic Precommit List (PL) of all precommitted transactions involving said each node;

(d) directing within each node all said queries that originate during said present version period (v) of the query originating node to said data records of said present stable database version (v-1) within said each node;

(e) refreshing said present database version (v) by performing within each node the steps of

(e.1) setting a refresh time t after all said read-only queries that arrived at said each node during said oldest version period (v-N+2 are terminated,

(e.2) creating a new version (v+1) of said NSUL containing said transactions listed at said refresh time t in said dynamic UL within said each node, and

(e.3) initiating a new version period (v+1) within said each node at said refresh time t by assigning said present database version (v) to be the new present stable database version (v) and creating a new present database version v+1);

(f) aborting, within said each node, every said transaction having an originating node version period earlier than said present version period (v) in said each; and

(g) aborting within said each node all said read-only queries directed to a database version represented in said dynamic PL for said each node.

14. The method of claim 13 wherein said refreshing step (e) is performed before the updating within said each node of a data record written by a committed transaction listed in said NSUL for said each node.

15. The method of claim 14 wherein said setting step (e.1) comprises the step of:

(e.1.1) aborting within said each node all said read-only queries that had arrived during said oldest version period (v-N+2) within said each node.

16. The method of claim 13 wherein:

said UL, said PL and said NSULs are implemented as bit maps having a single bit position corresponding to each said transaction that is still active or was terminated after the start of said oldest version period (v-N+2).

17. The method of claim 13 wherein said processing system includes record accession means in each said node for accessing said database records, said record accession means having at least one record key structure corresponding to each said record in said each node, said structure having a plurality of substructures each corresponding to one of said N+1 record versions, further comprising the unordered step of:

(g) updating said key structure corresponding to said each updated record within said each node.

18. A computer-implemented concurrent transaction and query processing system comprising:

multi-version database means for storing up to N versions of a database during a present version period (v), said database including a plurality of data records that are updated by said transactions and read by said queries, a plurality of versions of each data record of said plurality of data records being distributed among said database versions, each said database version (i) consisting essentially of said data records existing at the beginning of a corresponding said version period (i), each said version period (i) being the time interval between one said database version (i) and the next subsequent said database version (i+1), said database versions including a present database version (v) and a present stable database version (v-1);

Uncommitted List (UL) means coupled to said multi-version database means for identifying all uncommitted transactions;

Non-Stable and Uncommitted List (NSUL) means coupled to said multi-version database means for identifying all said transactions that are either uncommitted or were committed no earlier than during said present version period (v);

record accession means coupled to said multi-version database means for locating each said data record version and for identifying the transaction that created said each data record version;

version initiation means coupled to said multi-version database means for starting a new version period by assigning said present database version (v) to be the new present stable database version (v); and

garbage collection means for eliminating superfluous database records in response to an update by a transaction to a data record written by a previous committed transaction listed in said NSUL.

19. A computer-implemented concurrent transaction and query processing system comprising:

multi-version database means for storing two versions of a database, said database including a plurality of data records that are updated by said transactions and ready by said queries, up to two versions of each data record of said plurality of data records being distributed among said two database versions, each said database version (i) consisting essentially of said data records existing at the beginning of a corresponding said version period (i), each said version period (i) being the time interval between one said database version (i) and the next subsequent said database version (i+1), said data record versions including a present data record version and a present stable data record version;

Uncommitted List (UL) means coupled to said multi-version database means for identifying all uncommitted transactions;

Non-Stable and Uncommitted List (NSUL) means coupled to said multi-version database means for identifying all said transactions that are either uncommitted or were committed during said present version period;

record accession means coupled to said multi-version database means for locating each said record version and for identifying the transaction that created said each record version;

version initiation means coupled to said multi-version database means for starting a new version period by assigning said present data record version to be the new present stable data record version; and

garbage collection means for eliminating superfluous database records in response to an update by a transaction to a data record written by a previous committed transaction listed in said NSUL.