Prioritizing garbage collection and block allocation based on I/O history for logical address regions

• US 10,162,748 B2
• Filed: 07/03/2014
• Issued: 12/25/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., Kannan, Baskaran
• Primary Examiner(s): Sain, Gautam
• Application Number:
  US14/323,946
• Publication Number:
  US 20150347296A1
• Time in Patent Office: 1,636 Days
• Field of Search: 711103
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 12/0269 Incremental or concurrent garbage collection, e.g. in real-time systems G06F12/0261 takes precedence
• CPC Class Codes: G06F 12/0871 Allocation or management of cache space
• CPC Class Codes: G06F 2212/1044 Space efficiency improvement
• CPC Class Codes: G06F 2212/152 Virtualized environment, e.g. logically partitioned system
• CPC Class Codes: G06F 2212/2022 Flash memory
• CPC Class Codes: G06F 2212/214 Solid state disk
• CPC Class Codes: G06F 2212/222 Non-volatile memory
• CPC Class Codes: G06F 2212/312 In storage controller
• 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/0608 Saving storage space on storage 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/0652 Erasing, e.g. deleting, data cleaning, moving of data to a wastebasket
• 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 prioritizing garbage collection and block allocation based on I/O history for logical address regions. 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, (2) in accordance with the plurality of I/O requests over a predetermined time period, identifying an idle region of the plurality of regions in the logical address space of the host, and (3) in accordance with the identification of the idle region, enabling garbage collection of data storage blocks, in the storage device, that store data in the idle region.

Claims

1. A method performed by a storage device having a storage medium and a storage controller, the method comprising:

receiving, at the storage device, over a predetermined time period, 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 predefined regions in a logical address space of the host;

in accordance with the plurality of I/O requests received over the predetermined time period, performing at the storage controller of the storage device a set of operations, including;

identifying an idle logical address space region of the plurality of predefined regions in the logical address space of the host, wherein;

identifying the idle logical address space region comprises identifying a region, of the plurality of predefined regions in the logical address space of the host, that has not been accessed at least once by the plurality of I/O requests during the predetermined time period,

the logical address space of the host includes logical block addresses organized in numerical order, and

each region in the logical address space of the host, including the identified idle logical address space region, includes a plurality of the logical block addresses; and

in accordance with the identification of the idle logical address space region, which is a respective predefined region of the plurality of predefined regions in the logical address space of the host;

identifying one or more data storage blocks, in the storage medium, that store data in the identified idle logical address space region, wherein identifying the one or more data storage blocks comprises mapping one or more logical addresses in the idle logical address space region to physical addresses in a physical address space of the storage device, and

enabling garbage collection of the identified data storage blocks, in the storage medium of the storage device.

2. The method of claim 1, further comprising:

identifying a subset of the identified one or more data storage blocks, in the storage medium, that satisfy predefined garbage collection criteria, and initiating garbage collection of the identified subset of the identified one or more data storage blocks.

3. The method of claim 2, further comprising:

determining whether a respective bank of a plurality of banks in the storage medium is participating in garbage collection; and

in accordance with a determination that the respective bank is not participating in garbage collection, allocating blocks from the respective bank for subsequent write requests.

4. The method of claim 3, wherein each bank of the plurality of banks comprises a plurality of data storage blocks, and the respective bank is not participating in garbage collection of any of the identified one or more data storage blocks.

5. The method of claim 1, further comprising, for each region of the plurality of predefined regions in the logical address space of the host, setting a flag to denote a determination of whether the region is an idle logical address space region during the predetermined time period.

6. The method of claim 1, further comprising, for each region of the plurality of predefined regions in the logical address space of the host, storing information in a data structure to maintain a history of I/O request patterns in the 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:

a storage medium;

a storage controller that includes 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, over a predetermined time period, 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 predefined regions in a logical address space of the host;

at the storage controller, in accordance with the plurality of I/O requests received over the predetermined time period;

identify an idle logical address space region of the plurality of predefined regions in the logical address space of the host, wherein;

identifying the idle logical address space region comprises identifying a region, of the plurality of predefined regions in the logical address space of the host, that has not been accessed at least once by the plurality of I/O requests during the predetermined time period,

the logical address space of the host includes logical block addresses organized in numerical order, and

each region in the logical address space of the host, including the identified idle logical address space region, includes a plurality of the logical block addresses; and

in accordance with the identification of the idle logical address space region, which is a respective predefined region of the plurality of predefined regions in the logical address space of the host;

identify one or more data storage blocks, in the storage medium, that store data having logical addresses in the identified idle logical address space region, wherein identifying the one or more data storage blocks comprises mapping one or more logical addresses in the idle logical address space region to physical addresses in a physical address space of the storage system, and

enable garbage collection of the identified data storage blocks, in the storage medium of the storage device.

12. 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:

identify a subset of the identified one or more data storage blocks, in the storage medium, that satisfy predefined garbage collection criteria, and initiate garbage collection of the identified subset of the identified one or more data storage blocks.

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:

determine whether a respective bank of a plurality of banks in the storage medium is participating in garbage collection; and

in accordance with a determination that the respective bank is not participating in garbage collection, allocate blocks from the respective bank for subsequent write requests.

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

15. A storage system, comprising:

a storage medium;

a storage controller that includes 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 system, over a predetermined time period, 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 predefined regions in a logical address space of the host;

at the storage controller, in accordance with the plurality of I/O requests received over the predetermined time period;

identify an idle logical address space region of the plurality of predefined regions in the logical address space of the host, wherein;

identifying the idle logical address space region comprises identifying a region, of the plurality of predefined regions in the logical address space of the host, that has not been accessed at least once by the plurality of I/O requests during the predetermined time period,

the logical address space of the host includes logical block addresses organized in numerical order, and

each region in the logical address space of the host, including the identified idle logical address space region, includes a plurality of the logical block addresses; and

in accordance with the identification of the idle logical address space region, which is a respective predefined region of the plurality of predefined regions in the logical address space of the host;

identify one or more data storage blocks, in the storage medium, that store data having logical addresses in the identified idle logical address space region, wherein identifying the one or more data storage blocks comprises mapping one or more logical addresses in the idle logical address space region to physical addresses in a physical address space of the storage system, and

enable garbage collection of the identified data storage blocks, in the storage medium of the storage system.

16. A non-transitory computer readable storage medium, storing one or more programs configured for execution by one or more processors of a storage controller 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 predefined regions in a logical address space of the host;

at the storage controller, in accordance with the plurality of I/O requests received over the predetermined time period;

identifying an idle logical address space region of the plurality of predefined regions in the logical address space of the host, wherein;

identifying the idle logical address space region comprises identifying a region, of the plurality of predefined regions in the logical address space of the host, that has not been accessed at least once by the plurality of I/O requests during the predetermined time period,

the logical address space of the host includes logical block addresses organized in numerical order, and

each region in the logical address space of the host, including the identified idle logical address space region, includes a plurality of the logical block addresses; and

in accordance with the identification of the idle logical address space region, which is a respective predefined region of the plurality of predefined regions in the logical address space of the host;

identifying one or more data storage blocks, in a storage medium of the storage device, that store data having logical addresses in the identified idle logical address space region, wherein identifying the one or more data storage blocks comprises mapping one or more logical addresses in the idle logical address space region to physical addresses in a physical address space of the storage device, and

enabling garbage collection of the identified data storage blocks, in the storage medium of the storage device.

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

identifying a subset of the identified one or more data storage blocks, in the storage medium, that satisfy predefined garbage collection criteria, and initiating garbage collection of the identified subset of the identified one or more data storage blocks.

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

determining whether a respective bank of a plurality of banks in the storage medium of the storage device is participating in garbage collection; and

in accordance with a determination that the respective bank is not participating in garbage collection, allocating blocks from the respective bank for subsequent write requests.

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

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