Optimized garbage collection algorithm to improve solid state drive reliability

Patent metadata

Field	Value
Publication number	US-9977736-B2
Application number	US-201514798400-A
Country	US
Kind code	B2
Filing date	Jul 13, 2015
Priority date	Nov 18, 2011
Publication date	May 22, 2018
Grant date	May 22, 2018

Abstract

A method for managing memory operations in a storage device having a plurality of data blocks, the method including steps for determining a number of page reads for each of the plurality of data blocks and determining a dwell time for each of the plurality of data blocks. In certain aspects, the method further includes steps for associating the plurality of data blocks with a plurality of rank groups based on the number of page reads and the dwell time associated with each of the plurality of data blocks and selecting a data block, from among the plurality of data blocks, for memory reclamation based on the associated rank group and the selected data block. A storage system and computer-readable media are also provided.

First claim

What is claimed is:

1. A method for managing memory operations in a storage device having a plurality of data blocks, the method comprising:
determining a number of page reads for each of the plurality of data blocks;
determining a dwell time for each of the plurality of data blocks;
associating the plurality of data blocks with a plurality of rank groups based on the number of page reads and the dwell time associated with each of the plurality of data blocks,
wherein, for each of the plurality of data blocks associated with a first rank group of the plurality of rank groups, the respective number of page reads is less than or equal to a threshold value for the number of page reads and the respective dwell time is less than or equal to a threshold value for the dwell time,
wherein, for each of the plurality of data blocks associated with a second rank group of the plurality of rank groups, the respective number of page reads exceeds the threshold value for the number of page reads and the respective dwell time is less than or equal to the threshold value for dwell time,
wherein, for each of the plurality of data blocks associated with a third rank group of the plurality of rank groups, the respective number of page reads is less than or equal to the threshold value for the number of page reads and the respective dwell time exceeds the threshold value for dwell time, and
wherein for each of the plurality of data blocks associated with a fourth rank group of the plurality of rank groups, the respective number of page reads exceeds the threshold value for the number of page reads and the respective dwell time exceeds the threshold value for dwell time; and
selecting a data block, from among the plurality of data blocks, for memory reclamation based on the associated rank group of the selected data block, wherein the data block is selected from a highest rank group of the plurality of rank groups having an associated data block.

2. The method of claim 1 , further comprising:
determining a number of invalid pages in each of the plurality of data blocks; and
ranking each of the plurality of data blocks within the associated plurality of rank groups based on one or more of the number of page reads, dwell time, or number of invalid pages,
wherein selecting the data block is further based on the ranking within the associated rank group of the selected data block.

3. The method of claim 1 , further comprising:
ranking each of the plurality of data blocks within the associated plurality of rank groups, wherein ranking each rank group of the plurality of rank groups is based on a set of criteria different from respective sets of criteria used for ranking within the other rank groups of the plurality of rank groups,
wherein selecting the data block is further based on the ranking within the associated rank group of the selected data block.

4. The method of claim 3 , wherein ranking each of the plurality of data blocks comprises:
ranking each data block of the plurality of data blocks that is associated with the second rank group based on the number of page reads of the data block; and
ranking each data block of the plurality of data blocks that is associated with the third rank group based on the dwell time of the data block.

5. The method of claim 3 , further comprising:
determining a number of invalid pages in each of the plurality of data blocks,
wherein ranking each data block of the plurality of data blocks comprises:
ranking each data block of the plurality of data blocks that is associated with the first rank group of the plurality of rank groups based on the number of invalid pages of the data block.

6. The method of claim 3 , wherein ranking each data block of the plurality of data blocks comprises ranking each data block of the plurality of data blocks that is associated with the fourth rank group based on a sum of at least the number of page reads and the dwell time of the data block.

7. A storage system, comprising:
a memory;
a memory array comprising a plurality of data blocks; and
a controller coupled to the memory and the memory array, wherein the controller is configured to perform operations for:
storing, to the memory, a number of page reads associated with each of the plurality of data blocks;
storing, to the memory, a dwell time associated with each of the plurality of data blocks;
associating the plurality of data blocks with a plurality of rank groups based on the number of page reads and the dwell time associated with each of the plurality of data blocks,
wherein, for each of the plurality of data blocks associated with a first rank group of the plurality of rank groups, the respective number of page reads is less than or equal to a threshold value for the number of page reads and the respective dwell time is less than or equal to a threshold value for the dwell time,
wherein, for each of the plurality of data blocks associated with a second rank group of the plurality of rank groups, the respective number of page reads exceeds the threshold value for the number of page reads and the respective dwell time is less than or equal to the threshold value for dwell time,
wherein, for each of the plurality of data blocks associated with a third rank group of the plurality of rank groups, the respective number of page reads is less than or equal to the threshold value for the number of page reads and the respective dwell time exceeds the threshold value for dwell time, and
wherein for each of the plurality of data blocks associated with a fourth rank group of the plurality of rank groups, the respective number of page reads exceeds the threshold value for the number of page reads and the respective dwell time exceeds the threshold value for dwell time; and
selecting a data block, from among the plurality of data blocks, for memory reclamation based on the associated rank group of the selected data block, wherein the data block is selected from a highest rank group of the plurality of rank groups having an associated data block.

8. The storage system of claim 7 , wherein the controller is further configured to perform operations comprising:
storing, to the memory, a number of invalid pages associated with each of the plurality of data blocks; and
ranking each of the plurality of data blocks within the associated plurality of rank groups based on one or more of the number of page reads, dwell time, or number of invalid pages,
wherein selecting the data block is further based on the ranking within the associated rank group of the selected data block.

9. The storage system of claim 7 , wherein the controller is further configured to perform operations comprising:
ranking each of the plurality of data blocks within the associated plurality of rank groups, wherein ranking within each rank group of the plurality of rank groups is based on a set of criteria different from respective sets of criteria used for ranking within the other rank groups of the plurality of rank groups,
wherein selecting the data block is further based on the ranking within the associated rank group of the selected data block.

10. The storage system of claim 9 , wherein ranking each of the plurality of data blocks comprises:
ranking each data block of the plurality of data blocks that is associated with the second rank group based on the number of page reads associated with the data block; and
ranking each data block of the plurality of data blocks that is associated with the third rank group based on the dwell time associated with the data block.

11. The storage system of claim 9 , wherein the controller is further configured to perform operations comprising:
determining a numbe

Assignees

• Hgst Tech Santa Ana Inc
• Western Digital Tech Inc

Inventors

• Melik-Martirosian Ashot

Classifications

• G06F2212/7211

  Wear leveling · CPC title

• G06F3/0626

  Reducing size or complexity of storage systems · CPC title

• G06F12/0246 Primary

  in block erasable memory, e.g. flash memory · CPC title

• G06F2212/7205

  Cleaning, compaction, garbage collection, erase control · CPC title

• G06F12/0253 Primary

  Garbage collection, i.e. reclamation of unreferenced memory · CPC title