Distributed multi-version commitment ordering protocols for guaranteeing serializability during transaction processing

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.

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.

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.

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).