Techniques to achieve ordering among storage device transactions

• US 10,417,218 B2
• Filed: 12/23/2015
• Issued: 09/17/2019
• Est. Priority Date: 12/23/2015
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Doshi, Kshitij A., Trika, Sanjeev N., Sakthivelu, Sridharan
• Primary Examiner(s): Morrison, Jay A
• Assistant Examiner(s): Caiado, Antonio J
• Application Number:
  US14/757,602
• Publication Number:
  US 20170185643A1
• Time in Patent Office: 1,364 Days
• Field of Search: 707703
• CPC Class Codes: G06F 16/2379 Updates performed during online database operations; commit processing
• CPC Class Codes: G06F 9/466 Transaction processing

Abstract

Various embodiments are generally directed to an apparatus, method and other techniques to receiving a sequence of transactions, each transaction including a request to write data to a memory device, processing the sequence of transactions, and communicating a response to a host after the sequence of transaction have been completed.

Claims

1. An apparatus, comprising:

a memory capable of storing a sequence of transactions, each transaction including a request to write data to a memory device of the memory; and

a controller comprising circuitry operatively coupled with the memory, the controller to receive a command for a dependent transaction in the sequence of transactions, the command to indicate dependencies and a number of requests to write data for the dependent transaction, the command comprising a first parameter having one or more tokens to identify pre-requisite transactions for the dependent transaction and a second parameter having a number value to indicate the number of requests for the dependent transaction, the controller to create, in response to receipt of the sequence of transactions from a host computing platform, a directed-acyclic-graph (DAG) structure for each of the transactions of the sequence of transactions, a DAG structure for a dependent transaction of the sequence of transactions that is dependent on another transaction of the sequence of transactions, to comprise an edge for the other transaction;

the controller to determine, based on the DAG for the dependent transaction, whether a dependency on the other transaction is committed;

the controller to complete the sequence of transactions and to send a response to the host computing platform after the dependency on the other transaction is committed and completion of the sequence of transactions.

2. The apparatus of claim 1, the controller to process the dependent transaction and the other transaction from the sequence of transactions in parallel by writing data for the dependent transaction and the other transaction to the memory device, and commit the other transaction prior to committing the dependent transaction, the sequence of transactions completed when all transactions in the sequence of transactions have been committed.

3. The apparatus of claim 2, the dependent transaction having a plurality of dependencies from additional transactions from the sequence of transactions, each of the additional transactions corresponding with a different node of the DAG structure for the dependent transaction and each of the dependencies corresponding with a different edge of the DAG structure for the dependent transaction.

4. The apparatus of claim 3, the controller to process the dependent transaction and at least one of the additional transactions in parallel by writing data to the memory device, and to commit the dependent transaction after each of the additional transactions has been committed.

5. The apparatus of claim 1, the controller to determine whether the DAG structure for the dependent transaction indicates any dependencies exist for a transaction in the sequence of transactions that have not been committed, committing the transaction if the DAG structure indicates no dependencies exist, and withhold committing the transaction if the DAG structure indicates dependencies exist.

6. The apparatus of claim 1, the controller to process the sequence of transactions based on priorities and use a traversal technique comprising one of a breadth-first traversal and a depth-first traversal.

7. The apparatus of claim 1, comprising:

a storage device comprising the memory, the controller, one or more memory devices, and an interface capable of communicating commands and transactions with the host computing platform.

8. A computer-implemented method, comprising:

receiving, at an interface of an apparatus from a host computing platform, a sequence of transactions, each transaction including a request to write data to a memory device;

receiving, by a controller, a command for a dependent transaction in the sequence of transactions, the command to indicate dependencies and a number of requests to write data for the dependent transaction, the command comprising a first parameter having one or more tokens to identify pre-requisite transactions for the dependent transaction and a second parameter having a number value to indicate the number of requests for the dependent transaction;

creating, by the controller, based on receipt of the sequence of transactions, a directed-acyclic-graph (DAG) structure for each of the transactions of the sequence of transactions, a DAG structure for the dependent transaction of the sequence of transactions that is dependent on another transaction of the sequence of transactions, to comprise an edge for the other transaction,

determining, by a controller, based on the DAG for the dependent transaction, whether a dependency on the other transaction is committed,

completing the sequence of transactions; and

communicating a response to the host computing platform after the dependency on the other transaction is committed and completion of the sequence of transactions.

9. The computer-implemented method of claim 8, comprising:

processing the dependent transaction and the other transaction from the sequence of transactions in parallel by writing data for the dependent transaction and the other transaction to the memory device; and

committing the other transaction prior to committing the dependent transaction, the sequence of transactions completed when all transactions in the sequence of transactions have been committed.

10. The computer-implemented method of claim 9, the dependent transaction having a plurality of dependencies from additional transactions from the sequence of transactions, each of the other transactions corresponding with a different node of the DAG structure for the dependent transaction and each of the dependencies corresponding with a different edge in the DAG structure for the dependent transaction.

11. The computer-implemented method of claim 10, comprising:

processing the dependent transaction and at least one of the additional transactions in parallel by copying data to the memory device; and

committing the dependent transaction after each of the additional transactions have been committed.

12. The computer-implemented method of claim 8, comprising:

determining whether the DAG structure for the dependent transaction indicates any dependencies exist that have not been committed for a transaction;

committing the transaction if the DAG structure for the dependent transaction indicates no dependencies exist; and

withholding committing the transaction if the DAG structure for the dependent transaction indicates dependencies exist.

13. The computer-implemented method of claim 8, comprising:

processing the sequence of transactions based on priorities and using a traversal technique comprising one of a breadth-first traversal and a depth-first traversal.

14. A system, comprising:

a host computing platform; and

a storage device coupled with the host computing platform, the storage device comprising a memory, a controller, one or more memory devices, and an interface capable of communicating with the host computing platform,

the memory capable of storing a sequence of transactions, each transaction including a request to write data to a memory device; and

the controller operatively coupled with the memory, the controller to receive a command for a dependent transaction in the sequence of transactions, the command to indicate dependencies and a number of requests to write data for the dependent transaction, the command comprising a first parameter having one or more tokens to identify pre-requisite transactions for the dependent transaction and a second parameter having a number value to indicate the number of requests for the dependent transaction, the controller to create, in response to receipt of the sequence of transaction from a host computing platform, a directed-acyclic-graph (DAG) structure for each of the transactions of the sequence of transactions, a DAG structure for a dependent transaction of the sequence of transactions that is dependent on another transaction of the sequence of transactions, to comprise an edge for the other transaction, the controller to check the DAG for the dependent transaction to determine whether a dependency on the other transaction is committed, the controller to complete the sequence of transactions and to send a response to the host computing platform after the dependency on the other transaction is committed and completion of the sequence of transactions.

15. The system of claim 14, the controller to process the dependent transaction and the other transaction from the sequence of transactions in parallel by writing data for the dependent transaction and the other transaction to the memory device, and commit the other transaction prior to committing the dependent transaction, the sequence of transactions completed when all transactions in the sequence of transactions have been committed.

16. The system of claim 14, the dependent transaction having a plurality of dependencies from other transactions from the sequence of transaction, each of the other transactions corresponding with a different node of the DAG structure for the dependent transaction and each of the dependencies corresponding with a different edge of the DAG structure for the dependent transaction.

17. The system of claim 16, the controller to process the dependent transaction and at least one other transaction in parallel by writing data to the memory device, and commit the dependent transaction after each of the other transactions has been committed.

18. The system of claim 14, the controller to determine whether the DAG structure for the dependent transaction indicates any dependencies exist for a transaction in the sequence of transactions that have not been committed, committing the transaction if the DAG structure for the dependent transaction indicates no dependencies exist, and withhold committing the transaction if the DAG structure for the dependent transaction indicates dependencies exist.

19. The system of claim 14, the controller to process the sequence of transactions based on priorities and use a traversal technique comprising one of a breadth-first traversal and a depth-first traversal.