Using history of I/O sequences to trigger cached read ahead in a non-volatile storage device

• US 10,146,448 B2
• Filed: 07/03/2014
• Issued: 12/04/2018
• Est. Priority Date: 05/30/2014
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Inventors: Kotte, Dharani, Mathur, Akshay, Kannan, Baskaran, Patro, Sumant K.
• Primary Examiner(s): Sain, Gautam
• Application Number:
  US14/323,927
• Publication Number:
  US 20150347041A1
• Time in Patent Office: 1,615 Days
• Field of Search: 711103
• CPC Class Codes: G06F 12/08 in hierarchically structured memory systems, e.g. virtual memory systems
• CPC Class Codes: G06F 3/0616 in relation to life time, e.g. increasing Mean Time Between Failures [MTBF]
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0656 Data buffering arrangements
• CPC Class Codes: G06F 3/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]

Abstract

Systems, methods and/or devices are used to enable using history of I/O sequences to trigger cached read ahead in a non-volatile storage device. In one aspect, the method includes (1) receiving, at a storage device, a plurality of input/output (I/O) requests from a host, the plurality of I/O requests including read requests and write requests to be performed in a plurality of regions in a logical address space of the host, and (2) performing one or more operations for each region of the plurality of regions in the logical address space of the host, including (a) determining whether the region has a history of sequential read requests during a predetermined time period, and (b) in accordance with a determination that the region has a history of sequential read requests during the predetermined time period, enabling read ahead logic for the region.

Claims

1. A method performed by a storage device, comprising:

receiving, at the storage device, a plurality of input/output (I/O) requests from a host, the plurality of I/O requests including read requests and write requests to be performed in a plurality of regions in a logical address space of the host, wherein each region in the logical address space of the host includes a plurality of logical addresses;

for each read request of the read requests received from the host, mapping an address specified by the read request to a physical address in a non-volatile storage medium of the storage device in accordance with a logical to physical address map maintained by a storage controller of the storage device for mapping logical addresses in the logical address space of the host to physical addresses in the storage device; and

the storage device performing one or more operations for each respective region of the plurality of regions in the logical address space of the host, including;

determining, and storing in a data structure in the storage device, a total number of sequential read requests from the respective region in the logical address space of the host during a predetermined time period, wherein sequential read requests are read requests for sequential logical addresses in the logical address space of the host;

in accordance with the determined total number of sequential read requests from the respective region in the logical address space of the host, determining that the respective region has a history of sequential read requests from the respective region in the logical address space of the host during the predetermined time period, by determining that the determined total number of sequential read requests from the respective region is greater than a count threshold; and

in accordance with determining that the respective region in the logical address space of the host has a history of sequential read requests from the respective region during the predetermined time period, enabling read ahead logic for the respective region in the logical address space of the host, including performing a read ahead operation for a predefined amount of data from the non-volatile storage medium, comprising an entire sub-region of the respective region in the logical address space of the host.

2. The method of claim 1, wherein enabling read ahead logic for the respective region includes:

in response to a respective read operation;

performing the read ahead operation, to read data from the storage medium of the storage device; and

storing read data obtained by the read ahead operation to a cache; and

in response to one or more subsequent read requests, reading from the cache.

3. The method of claim 1, wherein, for each respective region of the plurality of regions, determining whether the respective region has a history of sequential read requests from the respective region in the logical address space of the host during the predetermined time period includes:

tracking whether a total number of sequential I/O requests to the respective region has exceeded a sequential request threshold; and

determining whether the total number of sequential I/O requests to the respective region has exceeded the sequential request threshold.

4. The method of claim 3, further comprising, for each respective region of the plurality of regions in the logical address space, setting a flag to denote the determination of whether the total number of sequential I/O requests to the respective region has exceeded the sequential request threshold.

5. The method of claim 1, further comprising, for each respective region of the plurality of regions in the logical address space, setting a flag to denote the determination of whether the respective region has a history of sequential read requests from the region in the logical address space of the host during the predetermined time period.

6. The method of claim 1, further comprising, for each respective region of the plurality of regions in the logical address space, storing information in the data structure to maintain a history of I/O request patterns in the respective region for the predetermined time period.

7. The method of claim 1, wherein the predetermined time period is configurable.

8. The method of claim 1, wherein the storage device comprises one or more flash memory devices.

9. The method of claim 1, wherein the storage device comprises one or more three-dimensional (3D) memory devices and circuitry associated with operation of memory elements in the one or more 3D memory devices.

10. The method of claim 9, wherein the circuitry and one or more memory elements in a respective 3D memory device, of the one or more 3D memory devices, are on the same substrate.

11. A storage device, comprising:

one or more processors; and

memory storing one or more programs, which when executed by the one or more processors cause the storage device to;

receive, at the storage device, a plurality of input/output (I/O) requests from a host, the plurality of I/O requests including read requests and write requests to be performed in a plurality of regions in a logical address space of the host, wherein each region in the logical address space of the host includes a plurality of logical addresses;

for each read request of the read requests received from the host, mapping an address specified by the read request to a physical address in a non-volatile storage medium of the storage device in accordance with a logical to physical address map maintained by a storage controller of the storage device for mapping logical addresses in the logical address space of the host to physical addresses in the storage device; and

perform one or more operations for each respective region of the plurality of regions in the logical address space of the host, including;

determining, and storing in a data structure in the storage device, a total number of sequential read requests from the respective region in the logical address space of the host during a predetermined time period, wherein sequential read requests are read requests for sequential logical addresses in the logical address space of the host;

in accordance with the determined total number of sequential read requests from the respective region in the logical address space of the host, determining whether the respective region has a history of sequential read requests from the respective region in the logical address space of the host during the predetermined time period, by determining that the determined total number of sequential read requests from the respective region is greater than a count threshold; and

in accordance with determining that the respective region in the logical address space of the host has a history of sequential read requests from the respective region during the predetermined time period, enabling read ahead logic for the respective region in the logical address space of the host, including performing a read ahead operation for a predefined amount of data from the non-volatile storage medium, comprising an entire sub-region of the respective region in the logical address space of the host.

12. The storage device of claim 11, wherein enabling read ahead logic for the region includes:

in response to a respective read operation;

performing the read ahead operation, to read data from the storage medium of the storage device; and

storing read data obtained by the read ahead operation to a cache; and

in response to one or more subsequent read requests, reading from the cache.

13. The storage device of claim 11, wherein, for a respective region of the plurality of regions, determining whether the respective region has a history of sequential read requests from the respective region in the logical address space of the host during the predetermined time period includes:

tracking whether a total number of sequential I/O requests to the region has exceeded a sequential request threshold; and

determining whether the total number of sequential I/O requests to the respective region has exceeded the sequential request threshold.

14. The storage device of claim 13, wherein the one or more programs, which when executed by the one or more processors, further cause the storage device to:

for each respective region of the plurality of regions in the logical address space, set a flag to denote the determination of whether the total number of sequential I/O requests to the respective region has exceeded the sequential request threshold.

15. The storage device of claim 11, wherein the one or more programs, which when executed by the one or more processors, further cause the storage device to:

for each respective region of the plurality of regions in the logical address space, store information in the data structure to maintain a history of I/O request patterns in the respective region for the predetermined time period.

16. A storage system, comprising:

a storage medium;

one or more processors; and

memory storing one or more programs, which when executed by the one or more processors cause the storage system to;

receive, at a storage device, a plurality of input/output (I/O) requests from a host, the plurality of I/O requests including read requests and write requests to be performed in a plurality of regions in a logical address space of the host, wherein each region in the logical address space of the host includes a plurality of logical addresses;

for each read request of the read requests received from the host, mapping an address specified by the read request to a physical address in a non-volatile storage medium of the storage device in accordance with a logical to physical address map maintained by a storage controller of the storage device for mapping logical addresses in the logical address space of the host to physical addresses in the storage device; and

perform one or more operations for each respective region of the plurality of regions in the logical address space of the host, including;

determining, and storing in a data structure in the storage device, a total number of sequential read requests from the respective region in the logical address space of the host during a predetermined time period, wherein sequential read requests are read requests for sequential logical addresses in the logical address space of the host;

in accordance with the determined total number of sequential read requests from the respective region in the logical address space of the host, determining whether the respective region has a history of sequential read requests from the respective region in the logical address space of the host during the predetermined time period, by determining that the determined total number of sequential read requests from the respective region is greater than a count threshold; and

in accordance with determining that the respective region in the logical address space of the host has a history of sequential read requests from the respective during the predetermined time period, enabling read ahead logic for the respective region in the logical address space of the host, including performing a read ahead operation for a predefined amount of data from the non-volatile storage medium, comprising an entire sub-region of the respective region in the logical address space of the host.

17. A non-transitory computer readable storage medium, storing one or more programs configured for execution by one or more processors of a storage device, the one or more programs including instructions for:

receiving, at a storage device, a plurality of input/output (I/O) requests from a host, the plurality of I/O requests including read requests and write requests to be performed in a plurality of respective regions in a logical address space of the host, wherein each region in the logical address space of the host includes a plurality of logical addresses;

for each read request of the read requests received from the host, mapping an address specified by the read request to a physical address in a non-volatile storage medium of the storage device in accordance with a logical to physical address map maintained by a storage controller of the storage device for mapping logical addresses in the logical address space of the host to physical addresses in the storage device; and

the storage device performing one or more operations for each respective region of the plurality of regions in the logical address space of the host, including;

determining, and storing in a data structure in the storage device, a total number of sequential read requests from the respective region in the logical address space of the host during a predetermined time period, wherein sequential read requests are read requests for sequential logical addresses in the logical address space of the host;

in accordance with the determined total number of sequential read requests from the respective region in the logical address space of the host, determining whether the respective region has a history of sequential read requests from the respective region in the logical address space of the host during the predetermined time period, by determining that the determined total number of sequential read requests from the respective region is greater than a count threshold; and

in accordance with determining that the respective region in the logical address space of the host has a history of sequential read requests from the respective region during the predetermined time period, enabling read ahead logic for the respective region in the logical address space of the host, including performing a read ahead operation for a predefined amount of data from the non-volatile storage medium, comprising an entire sub-region of the respective region in the logical address space of the host.

18. The non-transitory computer readable storage medium of claim 17, wherein enabling read ahead logic for the respective region includes:

in response to a respective read operation;

performing the read ahead operation, to read data from the storage medium of the storage device; and

storing read data obtained by the read ahead operation to a cache; and

in response to one or more subsequent read requests, reading from the cache.

19. The non-transitory computer readable storage medium of claim 17, wherein, for each respective region of the plurality of regions, determining whether the respective region has a history of sequential read requests from the respective region in the logical address space of the host during the predetermined time period includes:

tracking whether a total number of sequential I/O requests to the respective region has exceeded a sequential request threshold; and

determining whether the total number of sequential I/O requests to the respective region has exceeded the sequential request threshold.

20. The non-transitory computer readable storage medium of claim 19, wherein the one or more programs further include instructions for:

for each respective region of the plurality of regions in the logical address space, setting a flag to denote the determination of whether the total number of sequential I/O requests to the region has exceeded the sequential request threshold.

21. The non-transitory computer readable storage medium of claim 17, wherein the one or more programs further include instructions for:

for each respective region of the plurality of regions in the logical address space, storing information in the data structure to maintain a history of I/O request patterns in the respective region for the predetermined time period.