Out-of-order data transfer mechanisms for data storage systems

• US 10,095,433 B1
• Filed: 10/24/2012
• Issued: 10/09/2018
• Est. Priority Date: 10/24/2012
• Status: Active Grant

• Current Assignee: JP Morgan Chase Bank, N.A. (JP Morgan Chase & Co)
• Original Assignee: Western Digital Technologies Incorporated (Western Digital Corporation)
• Inventors: Gao, Jianxun
• Primary Examiner(s): Lo, Ann J
• Assistant Examiner(s): Warren, Tracy A
• Application Number:
  US13/659,865
• Time in Patent Office: 2,176 Days
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 2212/217 Hybrid disk, e.g. using both magnetic and solid state storage devices
• CPC Class Codes: G06F 2212/7202 Allocation control and policies
• CPC Class Codes: G06F 3/0601 Interfaces specially adapted for storage systems
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0628 making use of a particular technique
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0659 Command handling arrangements, e.g. command buffers, queues, command scheduling
• CPC Class Codes: G06F 3/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]
• CPC Class Codes: G06F 3/068 Hybrid storage device

Abstract

A data storage system implements out-of-order data transfer. In one embodiment, the data storage system can retrieve from a host system a scatter gather list (SGL) associated with a data read command and generate a memory access table based on the retrieved SGL. The data storage system can further retrieve data from memory, and at least some data may be retrieved out of order. Retrieved data can be provided to the host system using the memory access table, and at least some data may be provided out of order. Data retrieval performance can be increased.

Claims

1. A data storage system comprising:

a non-volatile memory array; and

a controller configured to;

receive a read data command from a host system;

retrieve from the host system a scatter gather list (SGL) associated with the read data command, the SGL comprising a plurality of entries associated with a plurality of logical addresses corresponding to logical data units stored in the non-volatile memory array;

generate a memory access table using the SGL, the memory access table comprising a plurality of entries, wherein the plurality of entries includes a respective plurality of physical addresses translated from the plurality of logical addresses of the logical data units, wherein one of the plurality of logical addresses corresponding to one of the logical data units is associated with more than one of the plurality of physical addresses in the memory access table, and wherein one of the plurality of entries in the memory access table comprises a pointer to one of the plurality of entries in the SGL;

generate, based at least in part on the memory access table, a plurality of requests to retrieve the logical data units stored in the non-volatile memory array and retrieve the logical data units, wherein at least some of logical data units are retrieved not in the same order as an order of the retrieval requests or an order of entries in the SGL; and

provide to the host system, based at least in part on the memory access table, at least some of the logical data units retrieved not in the same order as the order of the plurality of retrieval requests.

2. The data storage system of claim 1, wherein the plurality of entries of the memory access table are associated with a plurality of entries of the SGL and wherein the plurality of logical data units retrieved from the non-volatile memory array are associated with the plurality of entries of the memory access table.

3. The data storage system of claim 1, wherein the controller is further configured to:

determine that a retrieved logical data unit is associated with first and second entries of the memory access table, and

divide the retrieved logical data unit into a first portion associated with the first entry of the memory access table and a second portion associated with the second entry of the memory access table.

4. The data storage system of claim 1, wherein the plurality of requests comprises first and second requests, the first request associated with a first entry of the SGL and the second request associated with a second entry of the SGL that follows the first entry of the SGL, and wherein the controller is further configured to:

retrieve at least some logical data units for the second request prior to retrieving at least some logical data units for the first request; and

provide to the host system the at least some logical data units for the second request prior to providing to the host system the at least some logical data units for the first request.

5. The data storage system of claim 1, wherein the plurality of entries of the memory access table comprise a first group of consecutive entries none of which include a pointer to at least one of the entries of the SGL and a second group of consecutive entries wherein all of the entries in the second group include a pointer to at least one of the entries of the SGL.

6. The data storage system of claim 5, wherein at least one entry of the memory access table is associated with a third group of entries in the SGL, and wherein the controller is further configured to access the SGL to retrieve information associated with the entries in the third group of the SGL.

7. The data storage system of claim 6, wherein the entries in the third group of the SGL are not consecutive.

8. The data storage system of claim 6, wherein at least some of the entries in the third group of the SGL are not consecutive.

9. The data storage system of claim 5, wherein the number of the entries of the second group of the memory access table is less than that of the entries of the first group of the memory access table.

10. The data storage system of claim 5, wherein the at least one entry of the second group of the memory access table includes neither a physical address for a corresponding entry of the SGL, nor a size of data associated with the physical address.

11. In a data storage system comprising a non-volatile memory array and a controller, a method of executing data storage operations communicated by a host system, the method comprising:

receiving a read data command from the host system;

retrieving from the host system a scatter gather list (SGL) associated with the read data command, the SGL comprising a plurality of entries associated with a plurality of logical addresses corresponding to logical data units stored in the non-volatile memory array;

generating a memory access table using the SGL, the memory access table comprising a plurality of entries, wherein the plurality of entries includes a respective plurality of physical addresses translated from the plurality of logical addresses of the logical data units, wherein one of the plurality of logical addresses corresponding to one of the logical data units is associated with more than one of the plurality of physical addresses in the memory access table, and wherein one of the plurality of entries in the memory access table comprises a pointer to one of the plurality of entries in the SGL;

generating, based at least in part on the memory access table, a plurality of requests to retrieve a plurality of logical data units stored in the non-volatile memory array and retrieving the plurality of logical data units, wherein at least some of the logical data units are retrieved not in the same order as the order of the retrieval requests or the order of the entries in the SGL; and

based at least in part on the memory access table, providing to the host system at least some of the logical data units retrieved not in the same order as the order of the plurality of retrieval requests, wherein the method is executed under the control of the controller.

12. The method of claim 11, wherein the plurality of entries of the memory access table are associated with a plurality of entries of the SGL and wherein the plurality of logical data units retrieved from the non-volatile memory array are associated with the plurality of entries of the memory access table.

13. The method of claim 11, further comprising:

determining that a retrieved logical data unit is associated with first and second entries of the memory access table; and

dividing the retrieved logical data unit into a first portion associated with the first entry of the memory access table and a second portion associated with the second entry of the memory access table.

14. The method of claim 11, wherein the plurality of requests comprises first and second requests, the first request associated with a first entry of the SGL and the second request associated with a second entry of the SGL that follows the first entry of the SGL, and wherein the method further comprises:

retrieving at least some logical data units for the second request prior to retrieving at least some logical data units for the first request; and

providing to the host system the at least some logical data units for the second request prior to providing to the host system the at least some logical data units for the first request.

15. The method of claim 11, wherein the plurality of entries of the memory access table comprise a first group of consecutive entries none of which include a pointer to at least one of the entries of the SGL and a second group of consecutive entries wherein all of the entries in the second group include a pointer to at least one of the entries of the SGL.

16. The method of claim 15, wherein at least one entry of the memory access table is associated with a third group of entries in the SGL, and wherein the method further comprises accessing the SGL to retrieve information associated with the entries in the third group of the SGL.

17. The method of claim 16, wherein the entries in the third group of the SGL are consecutive.

18. The method of claim 16, wherein at least some of the entries in the third group of the SGL are not consecutive.