Using sub-region I/O history to cache repeatedly accessed sub-regions in a non-volatile storage device

• US 10,372,613 B2
• Filed: 07/03/2014
• Issued: 08/06/2019
• Est. Priority Date: 05/30/2014
• Status: Expired due to Fees

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Inventors: Mathur, Akshay, Kotte, Dharani, Biswas, Chayan, Kannan, Baskaran, Patro, Sumant K.
• Primary Examiner(s): Sain, Gautam
• Application Number:
  US14/323,955
• Publication Number:
  US 20150347013A1
• Time in Patent Office: 1,860 Days
• Field of Search: 711103
• CPC Class Codes: G06F 12/0253 Garbage collection, i.e. reclamation of unreferenced memory
• CPC Class Codes: G06F 12/0862 with prefetch
• CPC Class Codes: G06F 12/0871 Allocation or management of cache space
• CPC Class Codes: G06F 12/0873 Mapping of cache memory to specific storage devices or parts thereof
• CPC Class Codes: G06F 2212/1044 Space efficiency improvement
• CPC Class Codes: G06F 2212/222 Non-volatile memory
• CPC Class Codes: G06F 2212/312 In storage controller
• CPC Class Codes: G06F 2212/6024 History based prefetching

Abstract

Systems, methods and/or devices are used to enable using sub-region I/O history to cache repeatedly accessed sub-regions in a non-volatile storage device. In one aspect, the method includes (1) receiving a plurality of input/output (I/O) requests including read requests and write requests to be performed in a plurality of regions in a logical address space of a 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, for each sub-region of a plurality of sub-regions of the region: (a) determining whether the sub-region is accessed more than a predetermined threshold number of times during a predetermined time period, and (b) if so, caching, from a storage medium of the storage device to a cache of the storage device, data from the sub-region.

Claims

1. A method, comprising:

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

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

for each sub-region of a plurality of sub-regions of the region in the logical address space of the host, wherein each sub-region includes two or more pages and two or more logical block addresses (LBAs);

determining, and storing in a data structure in the storage device, a total number of times the sub-region in the logical address space of the host is accessed during a predetermined time period;

in accordance with the determined total number of times the sub-region is accessed, determining whether the sub-region in the logical address space of the host is accessed more than a predetermined threshold number of times during the predetermined time period; and

in accordance with a determination that the sub-region in the logical address space of the host is accessed more than the predetermined threshold number of times in the predetermined time period, caching, from a storage medium of the storage device to a cache of the storage device, data from the sub-region.

2. The method of claim 1, wherein, with respect to a sub-region of the plurality of sub-regions, caching data from the sub-region includes:

in response to a subsequent write request to the sub-region, caching the sub-region, wherein the subsequent write request to the sub-region is received subsequent to the determination that the sub-region in the logical address space of the host is accessed more than the predetermined threshold number of times in the predetermined time period.

3. The method of claim 1, further comprising, with respect to a sub-region of the plurality of sub-regions, subsequent to caching data from the sub-region:

writing subsequent write requests to the sub-region to the cache;

reading subsequent read requests from the sub-region from the cache; and

writing contents of the cache to the storage medium of the storage device in a merged operation.

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

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

6. The method of claim 1, wherein the predetermined threshold number is configurable.

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

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

9. The method of claim 1, wherein the plurality of regions in the logical address space of the host are fixed-size, predefined regions in the logical address space of the host, and the plurality of sub-regions of each region of the plurality of regions in the logical address space of the host are fixed-size, predefined sub-regions in the logical address space of the host, and the fixed-size of the sub-regions is smaller than the fixed-size of the regions in the logical address space of the host.

10. The method of claim 1, including translating a respective logical address, in the logical address space of the host, to a corresponding physical address in a physical address space of the storage device.

11. The method of claim 1, wherein performing one or more operations for each region of the plurality of regions in the logical address space of the host includes:

for each sub-region of the plurality of sub-regions of the region in the logical address space of the host,

maintaining an access count for the sub-region in the logical address space of the host.

12. The method of claim 11, wherein determining whether the sub-region in the logical address space of the host is accessed more than the predetermined threshold number of times during the predetermined time period includes determining, in accordance with the access count, whether the sub-region in the logical address space of the host is accessed more than the predetermined threshold number of times during the predetermined time period.

13. 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; and

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

for each sub-region of a plurality of sub-regions of the region in the logical address space of the host, wherein each sub-region includes two or more pages and two or more logical block addresses (LBAs);

determining, and storing in a data structure in the storage device, a total number of times the sub-region in the logical address space of the host is accessed during a predetermined time period;

in accordance with the determined total number of times the sub-region is accessed, determining whether the sub-region in the logical address space of the host is accessed more than a predetermined threshold number of times during the predetermined time period; and

in accordance with the determination that the sub-region in the logical address space of the host is accessed more than the predetermined threshold number of times in the predetermined time period, caching, from a storage medium of the storage device to a cache of the storage device, data from the sub-region.

14. The storage device of claim 13, wherein, with respect to a sub-region of the plurality of sub-regions, caching data from the sub-region includes:

in response to a subsequent write request to the sub-region, caching the sub-region, wherein the subsequent write request to the sub-region is received subsequent to the determination that the sub-region in the logical address space of the host is accessed more than the predetermined threshold number of times in the predetermined time period.

15. 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, with respect to a sub-region of the plurality of sub-regions, subsequent to caching data from the sub-region:

write subsequent write requests to the sub-region to the cache;

read subsequent read requests from the sub-region from the cache; and

write contents of the cache to the storage medium of the storage device in a merged operation.

16. 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 region of the plurality of regions in the logical address space, store information in a data structure to maintain a history of I/O request patterns in the region for the predetermined time period.

17. The storage device of claim 13, wherein the plurality of regions in the logical address space of the host are fixed-size, predefined regions in the logical address space of the host, and the plurality of sub-regions of each region of the plurality of regions in the logical address space of the host are fixed-size, predefined sub-regions in the logical address space of the host, and the fixed-size of the sub-regions is smaller than the fixed-size of the regions in the logical address space of the host.

18. 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; and

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

for each sub-region of a plurality of sub-regions of the region in the logical address space of the host, wherein each sub-region includes two or more pages and two or more logical block addresses (LBAs);

determining, and storing in a data structure in the storage device, a total number of times the sub-region in the logical address space of the host is accessed during a predetermined time period;

in accordance with the determined total number of times the sub-region is accessed, determining whether the sub-region in the logical address space of the host is accessed more than a predetermined threshold number of times during the predetermined time period; and

in accordance with the determination that the sub-region in the logical address space of the host is accessed more than the predetermined threshold number of times in the predetermined time period, caching, from a storage medium of the storage device to a cache of the storage device, data from the sub-region.

19. 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 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; and

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

for each sub-region of a plurality of sub-regions of the region in the logical address space of the host, wherein each sub-region includes two or more pages and two or more logical block addresses (LBAs);

determining, and storing in a data structure in the storage device, a total number of times the sub-region in the logical address space of the host is accessed during a predetermined time period;

in accordance with the determined total number of times the sub-region is accessed, determining whether the sub-region in the logical address space of the host is accessed more than a predetermined threshold number of times during the predetermined time period; and

in accordance with a determination that the sub-region in the logical address space of the host is accessed more than the predetermined threshold number of times in the predetermined time period, caching, from a storage medium of the storage device to a cache of the storage device, data from the sub-region.

20. The non-transitory computer readable storage medium of claim 19, wherein, with respect to a sub-region of the plurality of sub-regions, caching data from the sub-region includes:

in response to a subsequent write request to the sub-region, caching the sub-region, wherein the subsequent write request to the sub-region is received subsequent to the determination that the sub-region in the logical address space of the host is accessed more than the predetermined threshold number of times in the predetermined time period.

21. The non-transitory computer readable storage medium of claim 19, wherein the one or more programs further include instructions for, with respect to a sub-region of the plurality of sub-regions, subsequent to caching data from the sub-region:

writing subsequent write requests to the sub-region to the cache;

reading subsequent read requests from the sub-region from the cache; and

writing contents of the cache to the storage medium of the storage device in a merged operation.

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

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

23. The non-transitory computer readable storage medium of claim 19, wherein the plurality of regions in the logical address space of the host are fixed-size, predefined regions in the logical address space of the host, and the plurality of sub-regions of each region of the plurality of regions in the logical address space of the host are fixed-size, predefined sub-regions in the logical address space of the host, and the fixed-size of the sub-regions is smaller than the fixed-size of the regions in the logical address space of the host.