Distributed multi-version commitment ordering protocols for guaranteeing serializability during transaction processing
First Claim
1. A method of operating a digital computer to process read-write transactions and read-only transactions in a computer system, said method comprising the steps of:
- a) beginning preparation of results of said transactions;
b) determining an order of conflicts among said read-write transactions;
c) committing to memory state of said computer system prepared results of a selected one of said read-write transactions;
d) aborting an abort set of said read-write transactions for which commitment is contrary to said order of conflicts and said committing to memory state of said computer system said prepared results of said selected one of said read-write transactions;
e) retaining a prior version of memory state of said computer system existing prior to being updated by said prepared results of said selected one of said read-write transactions; and
f) permitting selected ones of said read-only transactions to read said prior version of memory state after said prepared results of said selected one of said read-write transactions are committed to memory state of said computer system, while preventing said read-write transactions from reading said prior version of memory state after said prepared results'"'"' of said selected one of said read-write transactions are committed to memory state of said computer system.
3 Assignments
0 Petitions
Accused Products
Abstract
In a multi-version database, copies of prior committed versions (snapshots) are kept for access by the read-only transactions. The read-write transactions are selectively aborted to enforce an order of commitment of read-write transactions that is the same as an order of conflicts among the read-write transactions. In a preferred embodiment, the read-write transactions are serialized by maintaining and referencing a graph of conflicts among read-write transactions, and the read-only transactions are serialized by a timestamp mechanism for selection of the snapshots to be read. Each time that a read-write transaction is committed, the read-write transaction is assigned a unique timestamp that is used to timestamp all resources committed by the read-write transaction. Upon starting, each read-only transaction is also assigned a timestamp. Each read-only transaction reads only the latest committed versions of all resources, that are timestamped earlier than the timestamp of the read-only transaction. In a multiprocessing system, the timestamps are issued to global coordinators and distributed locally with atomic commit messages and global queries. Moreover, read-write transactions may selectively access a hierarchy of uncommitted versions to prepare for various possible commitment orders. The hierarchy defines a path for record access and for cascading aborts. A plurality of mutually-conflicting uncommitted versions may be prepared for each transaction to prepare for all possible commitment orders.
-
Citations
34 Claims
-
1. A method of operating a digital computer to process read-write transactions and read-only transactions in a computer system, said method comprising the steps of:
-
a) beginning preparation of results of said transactions; b) determining an order of conflicts among said read-write transactions; c) committing to memory state of said computer system prepared results of a selected one of said read-write transactions; d) aborting an abort set of said read-write transactions for which commitment is contrary to said order of conflicts and said committing to memory state of said computer system said prepared results of said selected one of said read-write transactions; e) retaining a prior version of memory state of said computer system existing prior to being updated by said prepared results of said selected one of said read-write transactions; and f) permitting selected ones of said read-only transactions to read said prior version of memory state after said prepared results of said selected one of said read-write transactions are committed to memory state of said computer system, while preventing said read-write transactions from reading said prior version of memory state after said prepared results'"'"' of said selected one of said read-write transactions are committed to memory state of said computer system. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14)
-
-
15. A method of operating a digital computer to process read-write transactions and read-only transactions in a computer system, said method comprising the steps of:
-
a) beginning preparation of results of said transactions; b) determining an order of conflicts among said read-write transactions by detecting when a data access operation for one of said read-write transactions addresses data accessed by data access operations for other ones of said read-write transactions; c) committing to memory state of said computer system prepared results of a selected one of said read-write transactions; d) aborting an abort set of said read-write transactions for which commitment is contrary to said order of conflicts and said committing to memory state of said computer system said prepared results of said selected one of said read-write transactions; e) retaining a prior version of memory state of said computer system existing prior to being updated by said prepared results of said selected one of said read-write transactions; and f) maintaining a sufficient number of prior committed versions of memory state of said computer system to process said read-only transactions by permitting each read-only transaction to read a version of memory state last committed prior to the time that processing of said each read-only transaction is begun and without delaying commitment of read-write transactions that update memory state to be read by said each read-only transaction, while preventing said read-write transactions from reading any of said prior versions of memory state having been updated by committed ones of said read-write transactions, and preventing said read-only transactions from reading any results of said read-write transactions before said results of said read-write transactions are committed to said memory state of said computer system, so that said read-only transactions do not conflict with said read-write transactions. - View Dependent Claims (16, 17, 18)
-
-
19. A digital computer system for processing read-write transactions and read-only transactions, said digital computer system comprising, in combination:
-
a) means for performing operations of said read-write transactions such that operations of some read-write transactions are performed in accordance with availability of resources of said digital computer system before commitment of other read-write transactions; b) means for determining an order of conflicts among said read-write transactions; and c) means for enforcing an order of commitment of selected ones of said read-write transactions in accordance with said order of conflicts, said means for enforcing including means for delaying commitment of selected read-write transactions and means for aborting an abort set of said read-write transactions selected so that committing of a selected one of said read-write transactions before commitment of other of said read-write transactions excluded from said abort set is consistent with said order of conflicts; and d) means for maintaining a sufficient number of prior committed versions of memory state of said computer system to process said read-only transactions by permitting each read-only transaction to read a version of memory state last committed prior to the time that processing of said each read-only transaction is begun and without delaying commitment of read-write transactions that update memory state to be read by said each read-only transaction, while preventing said read-write transactions from reading any prior versions of memory state having been updated by committed ones of said read-write transactions, and preventing said read-only transactions from reading any results of said read-write transactions before said results of said read-write transactions are committed to said memory state, so that said read-only transactions do not conflict with said read-write transactions. - View Dependent Claims (20, 21, 22, 23, 24, 25, 26, 27, 28)
-
-
29. A method of operating a digital computer to process read-write transactions in a computer system, said method comprising the steps of:
-
a) beginning preparation of results of said read-write transactions, said results including uncommitted versions of memory state associated with said read-write transactions, and (i) preparing a first transaction by modifying a last committed version of memory state to create a first uncommitted version of memory state associated with said first transaction, and (ii) before committing said first uncommitted version to memory state of said computer system, preparing a second transaction by modifying said first uncommitted version of memory state to create a second uncommitted version of memory state associated with said second transaction; b) determining an order of conflicts among said versions of memory state associated with said read-write transactions, wherein said order of conflicts includes said second uncommitted version of memory state following said first uncommitted version of memory state; c) committing to memory state of said computer system prepared results of a selected one of said read-write transactions; and d) aborting an abort set of said uncommitted versions of memory state for which commitment is contrary to said order of conflicts and said committing to memory state of said computer system said prepared results of said selected one of said read-write transactions, and when said first uncommitted version of memory state is aborted, aborting said second uncommitted version. - View Dependent Claims (30, 31)
-
-
32. A method of operating a digital computer to process read-write transactions in a computer system, said method comprising the steps of:
-
a) beginning preparation of results of said read-write transactions, said results including uncommitted versions of memory state associated with said transactions, including; (i) preparing a first transaction by modifying a last committed version of memory state to create a first uncommitted version of memory state associated with said first transaction, and (ii) preparing a second transaction by modifying said last committed version of memory state to create a second uncommitted version of memory state associated with said second transaction; b) during preparation of said uncommitted versions, detecting conflicts between said uncommitted versions, said conflicts occurring when one uncommitted version includes a modified version of a resource of a prior version and another uncommitted version is based upon said resource of said prior version, wherein said first uncommitted version includes a modified version of a resource in said last committed version upon which said second uncommitted version is based, and said second uncommitted version includes a modified version of a resource in said last committed version upon which said first uncommitted version is based, so that said first uncommitted version and said second uncommitted version are mutually conflicting; c) committing to memory state of said computer system an uncommitted version of memory state associated with a selected one of said read-write transactions; and d) aborting an abort set of said uncommitted versions of memory state which are based upon any resources of any prior version having been modified in said version of said memory state committed in step (c), wherein one of said first and second uncommitted versions is aborted when the other of said first and second uncommitted versions is committed in step (c). - View Dependent Claims (33, 34)
-
Specification