Guaranteeing global serializability by applying commitment ordering selectively to global transactions
First Claim
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, andwherein 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 Assignments
0 Petitions
Accused Products
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.
-
Citations
38 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20)
-
-
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. - View Dependent Claims (22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 35)
-
-
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. - View Dependent Claims (33, 34, 36, 37, 38)
-
Specification