Garbage collection based on queued and/or selected write commands

Patent metadata

Field	Value
Publication number	US-10102119-B2
Application number	US-201514929020-A
Country	US
Kind code	B2
Filing date	Oct 30, 2015
Priority date	Oct 30, 2015
Publication date	Oct 16, 2018
Grant date	Oct 16, 2018

Abstract

A non-volatile memory system may include a write task queue that queues write commands and a garbage collection module that analyzes information about pending write commands in the write task queue in order to perform garbage collection. Based on its analysis of the write task queue, the garbage collection module performs discouraging actions to discourage itself from selecting certain blocks in a candidate list to be source blocks for garbage collection. In addition or alternatively, the garbage collection module performs encouraging actions to encourage itself to select blocks storing current valid data associated with a write command as source blocks for garbage collection. Write amplification may be reduced as a result of the discouraging and encouraging actions.

First claim

We claim:

1. A non-volatile memory system comprising:
non-volatile memory; and
a controller configured to:
associate a first block with a write command queued in a write task queue;
in response to the association, determine that the first block is in a candidate list;
in response to the determination that the first block is in the candidate list, identify the first block for performance of a discouraging action that discourages the controller from selecting the first block for transfer of first data in the first block to a different storage area;
perform the discouraging action associated with the first block;
after performance of the discouraging action, select a second block in the candidate list for transfer of second data in the second block to the different storage area, wherein the second block has a lower ranking than a ranking of the first block in the candidate list; and
communicate with the non-volatile memory to transfer the second data in the second block to the different storage area.

2. The non-volatile memory system of claim 1 , wherein the determination that the first block is in the candidate list comprises a determination of whether the first block is in an active pool of the candidate list.

3. The non-volatile memory system of claim 1 , wherein the controller is further configured to:
analyze the write task queue;
identify physical address information associated with the write command in response to the analysis; and
determine that a current version of data requested to be written by the write command comprises the first data in the first block based on the identification of the physical address information,
wherein the controller is configured to associate the first block with the write command based on the determination that the current version of the data requested to be written comprises the first data in the first block.

4. The non-volatile memory system of claim 3 , wherein the controller is configured to analyze the write task queue in response to a triggering event, wherein the triggering event comprises an expiration of a time period, an update event indicative of a possible update to the candidate list, or a queuing of a new write command in the write task queue.

5. The non-volatile memory system of claim 1 , wherein the controller is configured to perform the discouraging action by lowering the ranking of the first block to an artificially low ranking.

6. The non-volatile memory system of claim 1 , wherein the controller is configured to perform the discouraging action by removing the first block from the candidate list.

7. The non-volatile memory system of claim 1 , wherein the controller is configured to perform the discouraging action by appending a tag to an entry of the first block in the candidate list that indicates to the controller not to select the first block for the transfer of the first data to the different storage area, or adding the first block to a do not select list.

8. The non-volatile memory system of claim 1 , wherein the transfer of the second data to the different storage area is part of a garbage collection process, and wherein the controller is further configured to erase the second block after the transfer of the second data as part of the garbage collection process.

9. The non-volatile memory system of claim 8 , wherein the controller is further configured to write data associated with the write command into the second block after the second block is erased.

10. A method comprising:
identifying, with a controller of a non-volatile memory system, a write command in a write task queue, the write command requesting first data to be written to non-volatile memory;
associating, with the controller, a first block of the non-volatile memory with the write command by identifying, with the controller, that the first block of the non-volatile memory is storing a current version of the first data;
determining, with the controller, that the first block is in a garbage collection candidate list in response to the associating;
in response to determining that the first block is in the garbage collection candidate list, sorting, with the controller, the garbage collection candidate list to discourage the controller from selecting the first block as a source block for a garbage collection process;
selecting, with the controller, a second block in the garbage collection candidate list as a source block instead of the first block for the garbage collection process, wherein the second block has a lower ranking than a ranking of the first block in the candidate list; and
transferring, with the controller, second data stored in the second block to a destination block to perform the garbage collection process.

11. A non-volatile memory system comprising:
non-volatile memory; and
means for associating the first block with the write command queued in the write task queue;
means for determining that the first block is in the candidate list in response to the association;
means for identifying the first block for performance of a discouraging action that discourages selecting the first block for transfer of first data in the first block to a different storage area in response to the determination that the first block is in the candidate list;
means for performing the discouraging action associated with the first block;
means for selecting a second block in the candidate list for transfer of second data in the second block to the different storage area after performance of the discouraging action, wherein the second block has a lower ranking than a ranking of the first block in the candidate list; and
means for communicating with the non-volatile memory to transfer the second data in the second block to the different storage area.

12. The non-volatile memory system of claim 11 , wherein the means for determining that the first block is in the candidate list comprise means for determining whether the first block is in an active pool of the candidate list.

13. The non-volatile memory system of claim 11 , further comprising:
means for analyzing the write task queue;
means for identifying physical address information associated with the write command in response to the analysis; and
means for determining that a current version of data requested to be written by the write command comprises the first data in the first block based on the identification of the physical address information,
wherein the means for associating comprises means for associating the first block with the write command based on the determination that the current version of the data requested to be written comprises the first data in the first block.

14. The non-volatile memory system of claim 11 , wherein the means for performing the discouraging action comprises means for lowering the ranking of the first block to an artificially low ranking.

15. The non-volatile memory system of claim 11 , wherein the means for performing the discouraging action comprises means for removing the first block from the candidate list.

16. The non-volatile memory system of claim 11 , wherein the means for performing the discouraging action comprises means for appending a tag to an entry of the first block in the candidate list that indicates not to select the first block for the transfer of the first data to the different storage area, or adding the first block to a do not select list.

Assignees

• Sandisk Technologies Inc
• Sandisk Technologies Llc

Inventors

• Gopinath Raja Alwar
• Tuers Daniel Edward
• Thomas Nicholas
• Manohar Abhijeet

Classifications

• G06F2212/7205

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

• G06F3/0659

  Command handling arrangements, e.g. command buffers, queues, command scheduling · CPC title

• G06F12/0253 Primary

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

• G06F2212/7201

  Logical to physical mapping or translation of blocks or pages · CPC title

• G06F3/0619

  in relation to data integrity, e.g. data losses, bit errors · CPC title