Distributed concurrency control using serialization ordering

• US 20040078379A1
• Filed: 09/02/2003
• Published: 04/22/2004
• Est. Priority Date: 09/13/2002
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: Netezza (International Business Machines Corporation)
• Inventors: Hinshaw, Foster D., Harris, Craig S., Sarin, Sunil K.
• Granted Patent: US 7,146,366 B2
• Time in Patent Office: Days
• US Class Current: 707/100
• CPC Class Codes: G06F 16/2308 Concurrency control transaction processing G06F9/466
• CPC Class Codes: G06F 16/2315 Optimistic concurrency control
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

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.

Claims

1. A method of concurrency control for database transactions in a distributed database system comprising two or more nodes on a computer network, said method comprising:

locally, with respect to a node, asserting a serialization ordering between a first transaction requesting to use a database resource locally and one or more other database transactions that have already used the database resource locally;

including the serialization ordering within a local serialization graph, wherein the local serialization graph comprises a subset of all serialization orderings throughout the distributed database; and

detecting cycles in a local serialization graph.

2. The method of concurrency control of claim 1, further comprising:

communicating the serialization ordering from a first node on which it was originally asserted to a second node in the distributed database system, wherein the second node is responsible for ensuring serializability of at least one of the database transactions participating in the serialization ordering.

3. The method of concurrency control of claim 2, wherein a node comprises one or more of a central processor unit, a memory, a storage interface, and a network interface.

4. The method of concurrency control of claim 3, wherein a first subset of nodes have a primary responsibility for managing individual database resources and a second subset of nodes have a primary responsibility for starting and ending database transactions.

5. The method of concurrency control of claim 2, wherein the second node is a master node and is responsible for ensuring serializability of all database transactions in the distributed database system.

6. The method of concurrency control of claim 2, wherein the second node is one of a plurality of nodes collectively responsible for ensuring serializability of all database transactions in the distributed database system.

7. The method of concurrency control of claim 2, wherein a global serialization ordering is maintained across a plurality of nodes.

8. The method of concurrency control of claim 2, wherein the at least one database transaction originated at the second node.

9. The method of concurrency control of claim 2, wherein the second node is selected according to a policy.

10. The method of concurrency control of claim 2, wherein the step of communicating the serialization ordering to the second node further comprises computing new serialization orderings on the second node, and wherein the new serialization orderings arise from logical transitivity between the communicated serialization ordering and serialization orderings present on the second node.

11. The method of concurrency control of claim 10, wherein a subset of the new serialization orderings derived from logical transitivity is communicated to one or more nodes responsible for ensuring serializability of database transactions involved in the new serialization orderings.

12. The method of concurrency control of claim 1, wherein the step of detecting cycles in the serialization graph is performed when a new serialization ordering is discovered.

13. The method of concurrency control of claim 1, wherein the step of detecting cycles in the serialization graph is deferred for a period of time.

14. The method of concurrency control of claim 1, wherein the step of detecting cycles in the serialization graph is performed on the node that establishes a new serialization ordering.

15. The method of concurrency control of claim 1, wherein the step of detecting cycles comprises detecting all cycles in the serialization graph.

16. The method of concurrency control of claim 1, wherein the step of detecting cycles comprises stopping after detecting a first cycle.

17. The method of concurrency control of claim 2, wherein the step of detecting cycles in the serialization graph is performed on the second node.

18. The method of concurrency control of claim 2, further comprising continuing, at the first node, to process requests of database transactions related by the serialization ordering on a cautiously optimistic basis, delegating further global cycle detection to the second node.

19. The method of concurrency control of claim 2, further comprising deferring, at the first node, processing of requests for one or more of the database transactions related by the serialization ordering until the second node warrants that no new cycles are caused by the communicated serialization ordering.

20. The method of concurrency control of claim 1, further comprising:

breaking a cycle in the local serialization graph by aborting a database transaction whose attempt to use a database resource caused formation of one or more serialization cycles.

21. The method of concurrency control of claim 1, further comprising:

breaking one or more cycles in the local serialization graph by aborting selected database transactions that are members of one or more serialization cycles, such that after aborting the selected database transactions no serialization cycles remain.

22. The method of concurrency control of claim 1, further comprising:

breaking one or more cycles in the local serialization graph by aborting selected database transactions based on at least one of the following;

age, priority, desired time of completion, and other database transaction properties.

23. The method of concurrency control of claim 1, further comprising:

ensuring global serializability by delaying use of the database resource until such time as the use does not result in a cycle of serialization ordering relationships through use of pessimistic 2-phase locking in conjunction with a Read Committed isolation level.

24. The method of concurrency control of claim 23, wherein the step of delaying the use of the database resource further comprises putting the database transaction requesting the database resource to sleep and awakening the database transaction when the database transaction can use the resource in a way that avoids a serialization cycle.

25. The method of concurrency control of claim 1, wherein the step of asserting a serialization ordering further comprises dynamically asserting the serialization ordering based on pattern of use of the resource by the first database transaction and the one or more database transactions.

26. A method of controlling concurrency of database transactions in a distributed database system comprising two or more nodes, said method comprising:

locally asserting a resolution of resource contention between a first database transaction attempting to use a database resource and one or more other database transactions that have already used the database resource;

communicating the resolution of resource contention from the local node to a second node in the distributed database system, wherein the second node is responsible for ensuring serializability of at least one of the database transactions participating in the resource contention; and

locally identifying a database transaction that is causing the resource contention.

27. The method of controlling concurrency of database transactions of claim 26, wherein the step of locally asserting a resolution of resource contention further comprises asserting a serialization ordering.

28. The method of controlling concurrency of database transactions of claim 27, wherein the step of communicating the resolution of resource contention further comprises communicating a subset of arcs from a local serialization graph.

29. The method of controlling concurrency of database transactions of claim 27, further comprising including the serialization ordering within a local serialization graph, wherein the local serialization graph comprises a subset of all serialization orderings in the distributed database.

30. The method of controlling concurrency of database transactions of claim 29, further comprising detecting cycles in the local serialization graph.

31. The method of controlling concurrency of database transactions of claim 26, wherein the second node is a master node.

32. The method of controlling concurrency of database transactions of claim 26, wherein the second node is one of a plurality of nodes collectively responsible for ensuring global serialization ordering.

33. The method of controlling concurrency of database transactions of claim 26, wherein the second node is selected based on a policy.

34. The method of controlling concurrency of database transactions of claim 26, wherein at least one of the first database transaction and the one or more database transactions originated at the second node.