Identification of hot regions to enhance performance and endurance of a non-volatile storage device

• US 10,114,557 B2
• Filed: 07/03/2014
• Issued: 10/30/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, Biswas, Chayan, Patro, Sumant K.
• Primary Examiner(s): Sain, Gautam
• Application Number:
  US14/323,913
• Publication Number:
  US 20150347029A1
• Time in Patent Office: 1,580 Days
• Field of Search: 711103
• CPC Class Codes: G06F 11/00 Error detection; Error correction; Monitoring error detection, correction or monitoring in information storage based on relative movement between record carrier and transducer G11B20/18; monitoring, i.e. supervising the progress of recording or reproducing G11B27/36; in static stores G11C29/00
• CPC Class Codes: G06F 11/3034 where the computing system component is a storage system, e.g. DASD based or network based digital input from or digital output to record carriers G06F3/06; digital recording or reproducing G11B20/18; for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS], H04L67/1097
• CPC Class Codes: G06F 11/3485 for I/O devices
• CPC Class Codes: G06F 12/00 Accessing, addressing or allocating within memory systems or architectures digital input from, or digital output to record carriers, e.g. to disk storage units, G06F3/06
• CPC Class Codes: G06F 2201/81 Threshold
• CPC Class Codes: G06F 2201/88 Monitoring involving counting
• CPC Class Codes: G06F 2212/1036 Life time enhancement
• CPC Class Codes: G06F 2212/7201 Logical to physical mapping or translation of blocks or pages
• CPC Class Codes: G06F 2212/7204 Capacity control, e.g. partitioning, end-of-life degradation
• CPC Class Codes: G06F 2212/7205 Cleaning, compaction, garbage collection, erase control
• CPC Class Codes: G06F 2212/7208 Multiple device management, e.g. distributing data over multiple flash devices
• CPC Class Codes: G06F 3/0611 in relation to response time
• CPC Class Codes: G06F 3/0616 in relation to life time, e.g. increasing Mean Time Between Failures [MTBF]
• CPC Class Codes: G06F 3/0653 Monitoring storage devices or systems
• CPC Class Codes: G06F 3/0655 Vertical data movement, i.e. input-output transfer; data movement between one or more hosts and one or more storage devices
• 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/0688 Non-volatile semiconductor memory arrays

Abstract

Systems, methods and/or devices are used to enable identification of hot regions to enhance performance and endurance of a non-volatile storage device. In one aspect, the method includes (1) receiving a plurality of input/output (I/O) 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 (a) determining whether the region is accessed by the plurality of I/O requests more than a predetermined threshold number of times during a predetermined time period, (b) if so, marking the region with a hot region indicator, and (c) while the region is marked with the hot region indicator, identifying open blocks associated with the region, and marking each of the identified open blocks with a hot block indicator.

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, wherein each region includes two or more logical block addresses (LBAs), including;

determining whether the region in the logical address space of the host is accessed by the plurality of I/O requests more than a predetermined threshold number of times during a predetermined time period;

in accordance with a determination that the region in the logical address space of the host is accessed more than the predetermined threshold number of times during the predetermined time period, marking the region in the logical address space of the host with a hot region indicator; and

while the region in the logical address space of the host is marked with the hot region indicator,

identifying open physical blocks, comprising physical blocks, to which logical addresses in the region are mapped using a logical address to physical address mapping, that are not full and that are available for storing additional data while retaining data already stored therein; and

based on the identifying of open physical blocks to which logical addresses in the region are mapped, marking each of the identified open physical blocks with a hot block indicator, wherein the hot block indicator for a respective open physical block is distinct from the hot region indicator for the region in the logical address space of the host, and each block of the identified open physical blocks includes a plurality of pages and corresponds to a predefined range of physical addresses in a physical address space of the storage device;

wherein at least one region marked with the hot region indicator includes one or more logical addresses mapped to a physical block that is not open, and one or more logical addresses mapped to a physical block that is open.

2. The method of claim 1, wherein, with respect to a region of the plurality of regions, determining whether the region is accessed more than the predetermined threshold number of times includes tracking whether a total number of write requests to the region has exceeded a write threshold.

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

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

5. The method of claim 1, further comprising:

receiving, at the storage device, a subsequent write request from the host, the subsequent write request received subsequent to the plurality of I/O requests;

determining whether the subsequent write request from the host is to a region marked with the hot region indicator;

in accordance with a determination that the subsequent write request is to a region marked with the hot region indicator, storing data specified by the subsequent write request to an open physical block marked with the hot block indicator; and

in accordance with a determination that the subsequent write request is to a region not marked with the hot region indicator, storing data specified by the subsequent write request to an open physical block not marked with the hot block indicator.

6. The method of claim 1, wherein pages of a block storing data for one or more regions marked with the hot region indicator are invalidated faster than pages of a block storing data only for regions other than regions marked with the hot region indicator.

7. The method of claim 1, wherein blocks storing data for one or more regions marked with the hot region indicator are selected for garbage collection with higher probability than blocks storing data only for regions other than regions marked with the hot region indicator.

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

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

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

11. The method of claim 10, 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.

12. 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, wherein each region includes two or more logical block addresses (LBAs), including;

determining whether the region in the logical address space of the host is accessed by the plurality of I/O requests more than a predetermined threshold number of times during a predetermined time period;

in accordance with a determination that the region in the logical address space of the host is accessed more than the predetermined threshold number of times during the predetermined time period, marking the region in the logical address space of the host with a hot region indicator; and

while the region in the logical address space of the host is marked with the hot region indicator,

identifying open physical blocks, comprising physical blocks, to which logical addresses in the region are mapped using a logical address to physical address mapping, that are not full and that are available for storing additional data while retaining data already stored therein; and

based on the identifying of open physical blocks to which logical addresses in the region are mapped, marking each of the identified open physical blocks with a hot block indicator, wherein the hot block indicator for a respective open physical block is distinct from the hot region indicator for the region in the logical address space of the host, and each block of the identified open physical blocks includes a plurality of pages and corresponds to a predefined range of physical addresses in a physical address space of the storage device;

wherein at least one region marked with the hot region indicator includes one or more logical addresses mapped to a physical block that is not open, and one or more logical addresses mapped to a physical block that is open.

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

receive, at the storage device, a subsequent write request from the host, the subsequent write request received subsequent to the plurality of I/O requests;

determine whether the subsequent write request from the host is to a region marked with the hot region indicator;

in accordance with a determination that the subsequent write request is to a region marked with the hot region indicator, store data specified by the subsequent write request to an open physical block marked with the hot block indicator; and

in accordance with a determination that the subsequent write request is to a region not marked with the hot region indicator, store data specified by the subsequent write request to an open physical block not marked with the hot block indicator.

14. The storage device of claim 12, wherein pages of a block storing data for one or more regions marked with the hot region indicator are invalidated faster than pages of a block storing data only for regions other than regions marked with the hot region indicator.

15. The storage device of claim 12, wherein blocks storing data for one or more regions marked with the hot region indicator are selected for garbage collection with higher probability than blocks storing data only for regions other than regions marked with the hot region indicator.

16. The storage device of claim 12, 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. 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 the plurality of regions in the 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, wherein each region includes two or more logical block addresses (LBAs), including;

determining whether the region in the logical address space of the host is accessed by the plurality of I/O requests more than a predetermined threshold number of times during a predetermined time period;

in accordance with a determination that the region in the logical address space of the host is accessed more than the predetermined threshold number of times during the predetermined time period, marking the region in the logical address space of the host with a hot region indicator; and

while the region in the logical address space of the host is marked with the hot region indicator,

identifying open physical blocks, comprising physical blocks, to which logical addresses in the region are mapped using a logical address to physical address mapping, that are not full and that are available for storing additional data while retaining data already stored therein; and

based on the identifying of open physical blocks to which logical addresses in the region are mapped, marking each of the identified open physical blocks with a hot block indicator, wherein the hot block indicator for a respective open physical block is distinct from the hot region indicator for the region in the logical address space of the host, and each block of the identified open physical blocks includes a plurality of pages and corresponds to a predefined range of physical addresses in a physical address space of the storage device;

wherein at least one region marked with the hot region indicator includes one or more logical addresses mapped to a physical block that is not open, and one or more logical addresses mapped to a physical block that is open.

18. 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 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, wherein each region includes two or more logical block addresses (LBAs), including;

determining whether the region in the logical address space of the host is accessed by the plurality of I/O requests more than a predetermined threshold number of times during a predetermined time period;

in accordance with a determination that the region in the logical address space of the host is accessed more than the predetermined threshold number of times during the predetermined time period, marking the region in the logical address space of the host with a hot region indicator; and

while the region in the logical address space of the host is marked with the hot region indicator,

identifying open physical blocks, comprising physical blocks, to which logical addresses in the region are mapped using a logical address to physical address mapping, that are not full and that are available for storing additional data while retaining data already stored therein; and

based on the identifying of open physical blocks to which logical addresses in the region are mapped, marking each of the identified open physical blocks with a hot block indicator, wherein the hot block indicator for a respective open physical block is distinct from the hot region indicator for the region in the logical address space of the host, and each block of the identified open physical blocks includes a plurality of pages and corresponds to a predefined range of physical addresses in a physical address space of the storage device;

wherein at least one region marked with the hot region indicator includes one or more logical addresses mapped to a physical block that is not open, and one or more logical addresses mapped to a physical block that is open.

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

receiving, at the storage device, a subsequent write request from the host, the subsequent write request received subsequent to the plurality of I/O requests;

determining whether the subsequent write request from the host is to a region marked with the hot region indicator;

in accordance with a determination that the subsequent write request is to a region marked with the hot region indicator, storing data specified by the subsequent write request to an open physical block marked with the hot block indicator; and

in accordance with a determination that the subsequent write request is to a region not marked with the hot region indicator, storing data specified by the subsequent write request to an open physical block not marked with the hot block indicator.

20. The non-transitory computer readable storage medium of claim 18, wherein pages of a block storing data for one or more regions marked with the hot region indicator are invalidated faster than pages of a block storing data only for regions other than regions marked with the hot region indicator.

21. The non-transitory computer readable storage medium of claim 18, wherein blocks storing data for one or more regions marked with the hot region indicator are selected for garbage collection with higher probability than blocks storing data only for regions other than regions marked with the hot region indicator.

22. The non-transitory computer readable storage medium of claim 18, 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.