Out-of-order execution of strictly-ordered transactional workloads
First Claim
1. A non-transitory computer readable storage medium embodying instructions executed by a processor to perform a method of transaction processing, comprising:
- receiving a plurality of transactions from an execution queue, wherein the plurality of transactions have a specified order within the execution queue;
acquiring a plurality of locks corresponding to data items needed for execution of the plurality of transactions, wherein the plurality of locks are sequentially acquired based on the specified order of the plurality of transactions within the execution queue;
executing each transaction of the plurality of transactions upon acquiring all locks needed for execution of each transaction, wherein an order of execution of the plurality of transactions is different from the specified order of the plurality of transactions within the execution queue;
releasing the locks needed for execution of each transaction of the plurality of transactions upon committing each transaction;
maintaining a single first-in, first-out (FIFO) data lock queue containing a first plurality of pending locks that has not yet been acquired, wherein each pending lock in the data lock queue corresponds to one of the data items that is currently locked by a first one of the plurality of transactions and that is needed for execution of a second one the plurality of transactions, and wherein the first plurality of pending locks comprises pending locks for all locked data items needed for execution of all of the plurality of transactions; and
maintaining a transaction lock queue comprising a second plurality of pending locks that has not yet been acquired, wherein each pending lock in the transaction lock queue corresponds to one of the data items that is needed for execution of one of the plurality of transactions and includes a reference to the corresponding one of the plurality of transactions.
1 Assignment
0 Petitions
Accused Products
Abstract
A method of transaction processing includes receiving a plurality of transactions from an execution queue, acquiring a plurality of locks corresponding to data items needed for execution of the plurality of transactions, executing each transaction of the plurality of transactions upon acquiring all locks needed for execution of each transaction, and releasing the locks needed for execution of each transaction of the plurality of transactions upon committing each transaction. The plurality of transactions have a specified order within the execution queue, the plurality of locks are sequentially acquired based on the specified order of the plurality of transactions within the execution queue, and an order of execution of the plurality of transactions is different from the specified order of the plurality of transactions within the execution queue.
-
Citations
20 Claims
-
1. A non-transitory computer readable storage medium embodying instructions executed by a processor to perform a method of transaction processing, comprising:
-
receiving a plurality of transactions from an execution queue, wherein the plurality of transactions have a specified order within the execution queue; acquiring a plurality of locks corresponding to data items needed for execution of the plurality of transactions, wherein the plurality of locks are sequentially acquired based on the specified order of the plurality of transactions within the execution queue; executing each transaction of the plurality of transactions upon acquiring all locks needed for execution of each transaction, wherein an order of execution of the plurality of transactions is different from the specified order of the plurality of transactions within the execution queue; releasing the locks needed for execution of each transaction of the plurality of transactions upon committing each transaction; maintaining a single first-in, first-out (FIFO) data lock queue containing a first plurality of pending locks that has not yet been acquired, wherein each pending lock in the data lock queue corresponds to one of the data items that is currently locked by a first one of the plurality of transactions and that is needed for execution of a second one the plurality of transactions, and wherein the first plurality of pending locks comprises pending locks for all locked data items needed for execution of all of the plurality of transactions; and maintaining a transaction lock queue comprising a second plurality of pending locks that has not yet been acquired, wherein each pending lock in the transaction lock queue corresponds to one of the data items that is needed for execution of one of the plurality of transactions and includes a reference to the corresponding one of the plurality of transactions. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
-
-
12. A non-transitory computer readable storage medium embodying instructions executed by a processor to perform a method of transaction processing, comprising:
-
receiving a plurality of transactions from an execution queue, wherein the plurality of transactions have a specified order within the execution queue; acquiring a plurality of locks corresponding to data items needed for execution of the plurality of transactions, wherein the plurality of locks are sequentially acquired based on the specified order of the plurality of transactions within the execution queue; maintaining a first-in, first-out (FIFO) data lock queue containing a first plurality of pending locks that has not yet been acquired, wherein each pending lock in the data lock queue corresponds to one of the data items that is currently locked by a first one of the plurality of transactions and that is needed for execution of a second one the plurality of transactions, and wherein the first plurality of pending locks comprises pending locks for all locked data items needed for execution of all of the plurality of transactions; maintaining a transaction lock queue comprising a second plurality of pending locks that has not yet been acquired, wherein each pending lock in the transaction lock queue corresponds to one of the data items that is needed for execution of one of the plurality of transactions and includes a reference to the corresponding one of the plurality of transactions; upon determining that a transaction to be executed is not referenced in the transaction lock queue, executing each transaction of the plurality of transactions upon acquiring all locks needed for execution of each transaction, wherein an order of execution of the plurality of transactions is different from the specified order of the plurality of transactions within the execution queue; and releasing the locks needed for execution of each transaction of the plurality of transactions upon committing each transaction. - View Dependent Claims (13, 14, 15, 16, 17, 18, 19, 20)
-
Specification