Computer method and system for concurrency control using dynamic serialization ordering
View Patent ↗A mechanism controls concurrency among database transactions through the use of serial ordering relations. The ordering relations are computed dynamically in response to patterns of use. An embodiment of the present invention serializes a transaction that accesses a resource before a transaction that modifies the resource, even if the accessor starts after the modifier starts or commits after the modifier commits. A method of concurrency control for a database transaction in a distributed database system stores an intended use of a database system resource by the database transaction in a serialization graph. A serialization ordering is asserted between the database transaction and other database transactions based on the intended use of the database system resource by the database transaction. The serialization ordering is then communicated to a node in the distributed database system that needs to know the serialization ordering to perform concurrency control. Cycles in the serialization graph are detected based on the asserted serialization order and in order to break such cycles and ensure transaction serializability a database transaction is identified that is a member of a cycle in the serialization graph.
1. A computer implemented method of establishing serialization ordering among database transactions in a database system, comprising:
given a database transaction, storing a representation of an intended use of a database resource by the database transaction, wherein intended use of the database resource includes any of reads and writes based on history of the database transaction, wherein the intended use of the database resource includes at least one of: accessing state of the database resource and modifying the state of the database resource, and wherein storing the representation of the intended use of database resource comprises:
creating a resource usage record; and
associating the resource usage record with the database transaction, wherein the resource usage record is maintained for a period of time after the database transaction commits, and is not released until no serialization orderings is created that would involve the committed database transaction in a cycle of serialization orderings; and
dynamically asserting serialization ordering between the database transaction and other database transactions based upon the intended use of the database resource by the database transaction and the other database transactions.
2. The method of establishing serialization ordering of claim 1 , wherein the serialization ordering between a first transaction accessing the state of the database resource and a second transaction modifying the state of the database resource is in the first transaction preceding the second transaction.
3. The method of establishing serialization ordering of claim 2 , wherein the serialization ordering imposed applies whether the first transaction accessed the state of the database resource temporally before or temporally after the second transaction modifies the state of the database resource.
4. The method of establishing serialization ordering of claim 1 , wherein the serialization ordering imposed when a first database transaction accesses or modifies the database resource and a second database transaction modifies or accesses the database resource is that the second database transaction waits for the first database transaction to complete.
5. The method of establishing serialization ordering of claim 1 , wherein the resource usage record is released when the database transaction is aborted or rolled back.
6. The method of establishing serialization ordering of claim 1 , wherein the database resource includes at least one of the following: a record, a subset of records in a table identified by a qualifier on contents of records, and a table of records in a relational database system.
7. The method of establishing serialization ordering of claim 1 , wherein the database system operates in conjunction with serial ordering of database transactions, such that a first database transaction having a serialization ordering before a second database transaction can access versions of the database resource, which existed before any modifications made by the second database transaction.
8. The method of establishing serialization ordering of claim 1 , wherein the use of the database resource comprises modifying the state of the database resource with a commutative operation.
9. The method of establishing serialization ordering of claim 8 , wherein the commutative operation is at least one of: addition, subtraction, multiplication and division.
10. The method of establishing serialization ordering of claim 8 , wherein no serialization ordering is imposed when a plurality of database transactions operate to modify the database resource using arithmetically commutative operations.
11. The method of establishing serialization ordering of claim 1 , wherein the serialization ordering imposed when a first database transaction commits before a second database transaction starts.
12. The method of establishing serialization ordering of claim 1 , wherein the step of storing a representation of the use does not assert the serialization ordering when at least one or any combination of the following occurs: (a) the database transaction intends only to create or insert new resources, (b) the database transaction modifying the database resource acquired the database resource in reverse mode, (c) the use of the database resource does not require concurrency control, and (d) the database resource is unable be shared by another database transaction.
13. A computer system for establishing serialization orderings among database transactions in a database system, comprising:
at least two transactions;
a representation of intended use of a database resource by the at least two transactions, wherein intended use of the database resource includes any of reads and mites based on history of the database transaction, wherein the intended use of the database resource includes at least one of: accessing state of the database resource and modifying the state of the database resource, and wherein storing the representation of the intended use of database resource comprises:
creating a resource usage record; and
associating the resource usage record with the database transaction, wherein the resource usage record is maintained for a period of time after the database transaction commits, and is not released until no serialization orderings can be created that would involve the committed database transaction in a cycle of serialization orderings; and
a serialization graph storing an ordering between the at least two database transactions based upon the intended use of the database resource by the at least two database transactions.
14. A system as claimed in claim 13 , wherein the database system is a multi-versioning database system.