Guaranteeing global serializability by applying commitment ordering selectively to global transactions

• US 5,504,899 A
• Filed: 12/02/1994
• Issued: 04/02/1996
• Est. Priority Date: 10/17/1991
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Digital Equipment Corporation (HP Inc.)
• Inventors: Raz, Yoav
• Primary Examiner(s): Kriess, Kevin A.
• Assistant Examiner(s): Chaki, Kakali
• Application Number:
  US08/348,753
• Time in Patent Office: 487 Days
• Field of Search: 395/600, 395/650, 395/700
• US Class Current: 1/1
• CPC Class Codes: G06F 9/466 Transaction processing

Abstract

Global serializability in a distributed computing system having a plurality of resource managers is guaranteed by selectively committing global transactions, and aborting or delaying commitment of transactions to enforce an order of commitment of global transactions that is the same as an order of conflicts among the global transactions, including indirect conflicts caused by local transactions. These conflicts are detected, for example, by maintaining a serializability graph in each resource manager recording the effects of local as well as global transactions, including the effects of committed local transactions. The serializability graph includes nodes representing transactions, directed edges representing direct conflicts, and paths including more than one edge representing indirect conflicts. By referencing the serializability graph, global serializability is achieved in a most efficient manner. An atomic commitment coordinator, for example, communicates with a plurality of resource managers by way of "prepare," "commit" and "abort" commands, and the serializability graph in each resource manager is referenced to delay acknowledging that a global transaction has been "prepared" until an optimum "abort set" is obtained for compliance with the global transaction commitment order.

Claims

1. A computer-implemented method of processing global transactions that are distributed across a computing system and local transactions that are not distributed across the computing system, said method comprising the steps of:

a) preparing results of said local and global transactions under the control of a resource manager that insures serializability of a local schedule of said local transactions;

b) checking for memory access conflicts among said local and global transactions, not all of said local and global transactions having memory access conflicts, and when said checking for memory access conflicts finds that one of said local and global transactions has a first operation that conflicts with a second operation in another one of said local and global transactions, recording in memory of said computing system an order of performance for the transactions having the first conflicting operation and the second conflicting operation;

c) after a plurality of said global transactions which conflict with each other have prepared results that are ready to be committed, selecting an abort set of transactions for a selected one of said plurality of said global transactions which conflict with each other and have prepared results that are ready to be committed, said abort set being selected based on said order of performance having been recorded in said memory and being selected so that

(1) each uncommitted global transaction excluded from said abort set other than the selected global transaction would not conflict directly or indirectly with the selected global transaction after aborting all transactions in said abort set, and

(2) each transaction for which preparation of results has begun that is not yet ready to be committed and that is excluded from said abort set would not conflict directly or indirectly with the selected global transaction after aborting all transactions in said abort set,

whereby said order of performance having been recorded in said memory is consistent with the committing of the selected global transaction and commitment at a later time of global transactions that are excluded from the abort set, and

wherein said abort set includes at least one global transaction which conflicts indirectly with the selected global transaction via at least one local transaction conflicting with each of said selected global transaction and said at least one global transaction such that commitment of said at least one global transaction after commitment of the selected global transaction would be inconsistent with said order of performance having been recorded in said memory; and

d) committing to memory state of said computing system prepared results of said selected global transaction, and aborting prepared results of said transactions in said abort set.

2. The method as claimed in claim 1, wherein said committing of said selected global transaction occurs in response to an atomic commitment protocol with said resource manager.

3. The method as claimed in claim 2, wherein said atomic commitment protocol includes the steps of:

e) the resource manager signaling that said selected global transaction has been prepared and is ready to be committed; and

then

f) the atomic commitment protocol requesting the resource manager to commit to memory state of said computing system prepared results of said selected global transaction.

4. The method as claimed in claim 3, wherein said atomic commitment protocol further comprises the step of requesting said resource manager to signal whether said selected global transaction has been prepared and is ready to be committed.

5. The method as claimed in claim 3, further comprising the step of said resource manager receiving a request to prepare another one of said global transactions, and said resource manager delaying acknowledgement of completion of preparation of results of said another one of said global transactions when an abort set for said another one of said global transactions must include said selected global transaction after said resource manager has signaled that said selected global transaction has been prepared and is ready to be committed.

6. The method as claimed in claim 2, wherein after said step d), said method further comprises the steps of said resource manager:

e) selecting another abort set of said transactions for another one of said global transactions for which results have been prepared,

f) placing a lock on said another abort set to prevent results of transactions in said another abort set from being committed,

g) transmitting a signal in an atomic commitment protocol indicating that results of said another one of said global transactions are ready to be committed, and then

h) in response to an abort signal in said atomic commitment protocol, releasing said lock on said another abort set and aborting said results of said another one of said global transactions.

7. The method as claimed in claim 1, wherein there exist more than one non-empty abort set such that said order of performance recorded in said memory of said computing system is consistent with the committing of said selected global transaction and commitment at a later time of global transactions that are excluded from each non-empty abort set, and wherein said step of selecting an abort set determines which of the non-empty abort sets has a minimum performance loss due to the aborting of results of transactions in each non-empty abort set, and selects the non-empty abort set having said minimum performance loss.

8. The method as claimed in claim 1, further comprising the step of delaying the committing of the prepared results of said selected global transaction until said abort set becomes empty in order to minimize the number of transactions having results that are aborted in said step d).

9. The method as claimed in claim 1, further comprising the step of delaying acknowledgement of completion of preparation of a specified one of said global transactions until committing of said specified one of said global transactions before committing all other of said global transactions not yet committed nor aborted is consistent with said order of conflicts.

10. The method as claimed in claim 9, further comprising the step of terminating said delaying when said delaying persists for a predetermined duration of time.

11. The method as claimed in claim 9, further comprising the step of terminating said delaying upon receipt of a termination signal from an atomic commitment protocol coordinating commitment of said specified one of said global transactions.

12. The method as claimed in claim 1, wherein said checking for memory access conflicts includes detecting when a data access operation for one transaction addresses data accessed by data access operations for other transactions.

13. The method as claimed in claim 1, wherein said method includes a step of committing prepared results of said at least one local transaction, said step of committing prepared results of said at least one local transaction being performed prior to performing said step of selecting an abort set.

14. The method as claimed in claim 1, wherein a read operation of a second one of said transactions reads write data written by a write operation of a first one of said transactions before said first one of said transactions is committed, and wherein said method further comprises the step of aborting results of all of said transactions that have read data written by aborted transactions.

15. The method as claimed in claim 1, wherein said method includes a step of committing prepared results of a first local transaction and a step of committing prepared results of a second local transaction, and wherein said local schedule has a commit order of said first and second local transactions that is contrary to an order of conflicts between said first and second local transactions.

16. The method as claimed in claim 1, wherein said step of recording in memory of said computing system includes recording in said memory a graph of conflict orders between said local and global transactions, and wherein said step of selecting an abort set includes searching said graph for determining said abort set, said abort set including a transaction on each path in said graph to said selected global transaction from a global transaction not yet having results aborted or committed to memory state of said computing system, and said abort set further including a transaction on each path in said graph to said selected global transaction from a local transaction that has not completed preparation of results.

17. The method as claimed in claim 16, wherein said searching said graph for determining said abort set includes, for each of said paths, searching for and including in said abort set a transaction not yet having results aborted or committed that is closest to said selected global transaction.

18. The method as claimed in claim 16, further comprising the steps of removing from said graph committed local transactions when said committed local transactions do not have any paths in said graph from transactions that are not yet committed nor aborted.

19. The method as claimed in claim 1, wherein said step of preparing results of said local and global transactions includes said resource manager managing memory locks to insure seralizability of said local schedule of said local transactions.

20. The method as claimed in claim 1, wherein said step of preparing results of said local and global transactions includes said resource manager comparing time stamps of said local transactions to time stamps of memory resources to insure serializability of said local schedule of said local transactions.

21. A computer-implemented method of processing global transactions that are distributed across a computing system and local transactions that are not distributed across the computing system, said computing system including local processors for processing local transactions and at least one global coordinator, said method comprising the steps of:

a) a local processor receiving from said global coordinator requests to perform global transactions;

b) said local processor servicing a transaction queue for scheduling and performing operations of said local and global transactions such that operations of some of said local and global transactions are performed in accordance with availability of resources of said digital computer before commitment of other of said local and global transactions, and said local processor employing memory locks to insure that the operations of local transactions provide consistent results;

c) said local processor checking for memory access conflicts among said local and global transactions, not all of said local and global transactions having memory access conflicts, and when said checking for memory access conflicts finds that one of said local and global transactions has a first operation that conflicts with a second operation in another one of said local and global transactions, recording in memory of said computing system an order of performance for the transactions having the first conflicting operation and the second conflicting operation; and

d) after a plurality of said global transactions which conflict with each other have results that are ready to be committed by said local processor, said local processor selecting an abort set of transactions for a selected one of said plurality of said global transactions which conflict with each other and have results that are ready to be committed by said local processor, said abort set being selected based on said order of performance being recorded in said memory and being selected so that

(1) each uncommitted global transaction excluded from said abort set other than the selected global transaction would not conflict directly or indirectly with the selected global transaction after aborting all transactions in said abort set, and

(2) each transaction for which preparation of results has begun that is not yet ready to be committed and that is excluded from said abort set would not conflict directly or indirectly with the selected global transaction after aborting all transactions in said abort set,

whereby said order of performance recorded in said memory is consistent with the committing of the selected global transaction and commitment at a later time of global transactions that are excluded from the abort set, and

wherein said abort set includes at least one global transaction which conflicts indirectly with the selected global transaction via at least one local transaction conflicting with each of said selected global transaction and said at least one global transaction such that commitment of said at least one global transaction after commitment of said selected global transaction would be inconsistent with said order of performance having been recorded in said memory; and

e) said local processor committing to memory state of said computing system prepared results of said selected global transaction, and aborting prepared results of said transactions in said abort set.

22. The method as claimed in claim 21, further including the step of said local processor delaying commitment of global transactions for which preparation of results by said local processor has been completed but for which commitment before commitment of other of said global transactions is contrary to said order of performance.

23. The method as claimed in claim 21, further including the step of said local processor delaying acknowledgement of completion of preparation of results of a requested one of said global transactions until commitment of said requested one of said global transactions before committing all other of said global transactions not yet committed nor aborted is consistent with said order of performance.

24. The method as claimed in claim 23, further comprising the step of said local processor terminating said delaying acknowledgement upon receipt of a signal.

25. The method as claimed in claim 21, wherein said checking for memory access conflicts is performed during the preparation of results for transactions having conflicting operations.

26. The method as claimed in claim 21, wherein a read operation of a second one of said transactions reads write data written by a write operation of a first one of said transactions before said first one of said transactions is committed, and wherein said method further comprises the step of said local processor aborting all results prepared by said local processor of said transactions that have read data written by aborted transactions.

27. The method as claimed in claim 21, wherein said step of scheduling ensures consistent results of local transactions by ensuring serializability of a local schedule and includes said local processor committing prepared results of a first local transaction and committing prepared results of a second local transaction, wherein said local schedule has a commitment order of said first and second local transactions that is contrary to an order of conflicts between said local transactions.

28. The method as claimed in claim 21, wherein after said step d), said method further comprises said local processor:

f) selecting an abort set of said transactions for one of said global transactions for which results have been prepared,

g) placing a lock on said abort set to prevent results of transactions in said abort set from being committed,

h) transmitting a signal in an atomic commitment protocol indicating that results of said one of said global transactions is ready to be committed, and then

i) in response to an abort signal in said atomic commitment protocol, releasing said lock on said abort set and aborting said results of said one of said global transactions.

29. The method as claimed in claim 21, wherein said step of recording in memory of said computing system includes said local processor recording in said memory a graph of conflict orders between said local and global transactions, and wherein said step of selecting an abort set includes said local processor searching said graph for an abort set of transactions, said abort set including a transaction on each path in said graph to said selected global transaction from a global transaction not yet having results aborted or committed to memory state of said computing system.

30. The method as claimed in claim 29, wherein said searching said graph for determining said abort set includes, for each of said paths, searching for and including in said abort set a transaction that is not yet committed nor aborted and is closest to said selected global transaction.

31. The method as claimed in claim 29, further comprising the steps of removing from said graph committed local transactions when said committed local transactions do not have any paths in said graph from transactions that are not yet committed nor aborted.

35. The digital computer system as claimed in claim in claim 31, wherein said means for aborting includes means for aborting all of said transactions that have read data written by aborted transactions.

32. In a distributed processing system, a digital computer system for processing global transactions that are distributed across said distributed processing system and local transactions that are not distributed across said distributed processing system, said digital computer system comprising, in combination:

a) means for servicing a transaction queue for performing operations of said local and global transactions such that operations of some transactions are performed in accordance with availability of resources of said digital computer system before commitment of other transactions, and means for managing memory locks such that the operations of local transactions provide consistent results;

b) means for checking for memory access conflicts among said local and global transactions, not all of said local and global transactions having memory access conflicts, and when said checking for memory access conflicts finds that one of said local and global transactions has a first operation that conflicts with a second operation in another one of said local and global transactions, recording in memory of said computing system an order of performance for the transactions having the first conflicting operation and the second conflicting operation; and

c) means, operative after a plurality of said global transactions which conflict with each other have results that are ready to be committed, for selecting an abort set of transactions for a selected one of said plurality of said global transactions which conflict with each other and have results that are ready to be committed, said abort set being selected based on said order of performance having been recorded in said memory and being selected so that

(1) each uncommitted global transaction excluded from said abort set other than the selected global transaction would not conflict directly or indirectly with the selected global transaction after aborting all transactions in said abort set, and

(2) each transaction for which preparation of results has begun that is not yet ready to be committed and that is excluded from said abort set would not conflict directly or indirectly with the selected global transaction after aborting all transactions in said abort set,

whereby said order of performance having been recorded in said memory is consistent with the committing of the selected global transaction and commitment at a later time of uncommitted global transactions that are excluded from the abort set, and

wherein said abort set includes at least one global transaction which conflicts indirectly with the selected global transaction via at least one local transaction conflicting with each of said selected global transaction and said at least one global transaction such that commitment of said at least one global transaction after commitment of said selected global transaction would be inconsistent with said order of performance having been recorded in said memory; and

d) means for committing to memory state of said computing system prepared results of said selected global transaction, and aborting prepared results of said transactions in said abort set.

33. The digital computer system as claimed in claim 32, further including means responsive to said abort set being non-empty for delaying the commitment of said selected global transaction and the aborting of transactions in said abort set.

34. The digital computer system as claimed in claim 33, further comprising means for terminating said delaying in response to a signal in an atomic commitment protocol.

36. The digital computer system as claimed in claim 32, further comprising means for exchanging information about global transactions in accordance with an atomic commitment protocol.

37. The digital computer system as claimed in claim 32, wherein said means for recording includes means for recording in memory of said digital computer system a graph of conflict orders between said transactions, and wherein said means for selecting an abort set includes means for searching said graph for determining said abort set of transactions, said abort set including a transaction on each path in said graph to said selected global transaction from a global transaction not yet having results aborted or committed to memory state of said digital computer system.

38. The digital computer as claimed in claim 37, further comprising means for removing from said graph committed local transactions when said committed local transactions do not have any path in said graph from transactions that are not yet committed nor aborted.