Out-of-order execution of strictly-ordered transactional workloads

• US 9,652,491 B2
• Filed: 04/15/2013
• Issued: 05/16/2017
• Est. Priority Date: 04/15/2013
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Meng, Shicong, Zhang, Li
• Primary Examiner(s): Waldron, Scott A
• Assistant Examiner(s): Wang, Dongming
• Application Number:
  US13/863,022
• Publication Number:
  US 20140310236A1
• Time in Patent Office: 1,492 Days
• Field of Search: 707607
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: G06F 16/2379 Updates performed during online database operations; commit processing
• CPC Class Codes: G06F 9/466 Transaction processing

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.

Claims

1. 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 of 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.

2. The method of claim 1, wherein at least two transactions of the plurality of transactions are executed at a same time.

3. The method of claim 1, wherein an order in which the plurality of locks are acquired is different from an order in which the plurality of locks are released.

4. The method of claim 1, further comprising:

adding a new pending lock to the data lock queue and the transaction lock queue when the new lock is unable to be acquired for a target data item; and

removing the new pending lock from the data lock queue and the transaction lock queue upon acquiring the new lock.

5. The method of claim 1, wherein executing each transaction comprises an initial execution operation that identifies a read-write set of the transaction and ignores all write operations corresponding to the transaction, and an actual execution operation,

wherein the initial execution operation is performed prior to acquiring the plurality of locks and the read-write set is used to acquire the plurality of locks, and the actual execution operation is performed subsequent to acquiring the plurality of locks.

6. The method of claim 1, further comprising:

prefetching read results from a datastore corresponding to each of the plurality of transactions upon receiving each of the plurality of transactions; and

storing the prefetched read results in a local memory cache.

7. The method of claim 1, wherein each transaction of the plurality of transactions is executed upon determining that the transaction to be executed is not referenced in the transaction lock queue.

8. 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 of 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.

9. The method of claim 8, wherein at least two transactions of the plurality of transactions are executed at a same time.

10. The method of claim 8, wherein an order in which the plurality of locks are acquired is different from an order in which the plurality of locks are released.

11. The method of claim 8, further comprising:

adding a new pending lock to the data lock queue and the transaction lock queue when the new lock is unable to be acquired for a target data item; and

removing the new pending lock from the data lock queue and the transaction lock queue upon acquiring the new lock.

12. The method of claim 8, wherein executing each transaction comprises an initial execution operation that identifies a read-write set of the transaction and ignores all write operations corresponding to the transaction, and an actual execution operation,

wherein the initial execution operation is performed prior to acquiring the plurality of locks and the read-write set is used to acquire the plurality of locks, and the actual execution operation is performed subsequent to acquiring the plurality of locks.

13. The method of claim 8, further comprising:

prefetching read results from a datastore corresponding to each of the plurality of transactions upon receiving each of the plurality of transactions; and

storing the prefetched read results in a local memory cache.

14. The method of claim 8, wherein the FIFO data lock queue is a single queue, and the first plurality of pending locks comprises pending locks for all locked data items.