SYSTEM AND METHOD FOR MANAGING GARBAGE COLLECTION IN SOLID-STATE MEMORY

• US 20110283049A1
• Filed: 05/12/2010
• Published: 11/17/2011
• Est. Priority Date: 05/12/2010
• Status: Active Grant

• Current Assignee: Western Digital Technologies Incorporated (Western Digital Corporation)
• Original Assignee: Western Digital Technologies Incorporated (Western Digital Corporation)
• Inventors: KANG, HO-FAN, KAN, ALAN CHINGTAO
• Granted Patent: US 9,026,716 B2
• Time in Patent Office: Days
• US Class Current: 711/103
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 2212/7205 Cleaning, compaction, garbage collection, erase control
• CPC Class Codes: G11C 16/16 for erasing blocks, e.g. arrays, words, groups

Abstract

Embodiments of the invention are directed to optimizing the selection of memory blocks for garbage collection to maximize the amount of memory freed by garbage collection operations. The systems and methods disclosed herein provide for the efficient selection of optimal or near-optimal garbage collection candidate blocks, with the most optimal selection defined as block(s) with the most invalid pages. In one embodiment, a controller classifies memory blocks into various invalid block pools by the amount of invalid pages each block contains. When garbage collection is performed, the controller selects a block from a non-empty pool of blocks with the highest minimum amount of invalid pages. The pools facilitate the optimal or near-optimal selection of garbage collection candidate blocks in an efficient manner and the data structure of the pools can be implemented with bitmasks, which take minimal space in memory.

Claims

1. A storage subsystem, comprising:

a non-volatile solid-state memory array; and

a controller comprising a garbage collection module and configured to receive and execute memory commands from a host system and the garbage collection module, the controller further configured to;

maintain, for a first memory block in the memory array, an invalid page counter for storing data related to a number of invalid pages within the first memory block, the first memory block assigned by the number of invalid pages into a first pool, wherein the garbage collection module is configured to select memory blocks from a plurality of pools based on the number of invalid pages;

upon executing a memory command from the host system that causes a change in a validity of a page within the first memory block,

update an invalid page counter associated with the first memory block; and

reassign the first memory block to a second pool when the updated invalid page counter exceeds a threshold.

2. The storage subsystem of claim 1, wherein the controller is further configured to assign the first memory block to a pool for free memory blocks after the first memory block undergoes garbage collection.

3. The storage subsystem of claim 1, wherein each of the plurality of pools is assigned with blocks having a different minimum number of invalid pages and the garbage collection module is configured to select, for garbage collection, a second memory block assigned to a third pool with a highest minimum number of invalid pages.

4. The storage subsystem of claim 3, wherein the plurality of pools comprise the first pool initially configured for memory blocks with at least 25% invalid pages, the second pool initially configured for memory blocks with at least 50% invalid pages, the third pool initially configured for memory blocks with at least 75% invalid pages, and a fourth pool initially configured for memory blocks with 100% invalid pages.

5. The storage subsystem of claim 1, wherein a data structure is used to store data related to pool assignments of the memory blocks.

6. The storage subsystem of claim 5, wherein the data structure is stored in static random access memory (SRAM).

7. The storage subsystem of claim 5, wherein the data structure is a tree structure.

8. The storage subsystem of claim 5, wherein the controller is further configured to obtain a lock on the data structure prior to reassigning the first memory block into a different pool.

9. The storage subsystem of claim 1, wherein the controller is further configured to obtain a lock on the invalid page counter prior to updating the page counter.

10. The storage subsystem of claim 1, wherein the invalid page counter is stored in dynamic random access memory (DRAM).

11. A method of managing memory operations in non-volatile solid-state memory, the method comprising:

maintaining, for a first memory block in the non-volatile solid-state memory, an invalid page counter for storing data related to a number of invalid pages within the first memory block, the first memory block classified by the number of invalid pages into a first pool;

upon receipt of a write command from a host system that causes a change in a validity of a page within the first memory block,

updating an invalid page counter for the first memory block; and

reclassifying the first memory block to a second pool when the invalid page counter of the first memory block indicates that a number of invalid pages within the first memory block exceeds a threshold.

12. The method of claim 11, further comprising:

selecting, for garbage collection, a second memory block classified in a third pool with a highest minimum threshold of invalid pages.

13. The method of claim 11, wherein the plurality of pools comprise the first pool initially configured for memory blocks with at least 25% invalid pages, the second pool initially configured for memory blocks with at least 50% invalid pages, the third pool initially configured for memory blocks with at least 75% invalid pages, and a fourth pool initially configured for memory blocks with 100% invalid pages.

14. The method of claim 11, further comprising:

locating, in a mapping table, an entry for a logical address in the write command to determine a physical page address that corresponds to the logical address;

updating an invalid page table with information that blocks pending garbage collection commands from being executed at the physical page address;

executing the write command; and

updating the located entry in the mapping table with a new physical address at which the data is written by the execution of the write command.

15. The method of claim 14, wherein the updating the invalid page table further comprises updating an entry in the invalid page table to indicate that data at the physical page address is invalid.

16. The method of claim 14, wherein the invalid page table is implemented as a bitmask wherein a bit is used to represent a validity of data at a page address.

17. The method of claim 14, wherein the invalid page table is stored in DRAM.

18. The method of claim 11, wherein a data structure is used to store data related to pool classifications of the memory blocks.

19. The method of claim 18, wherein the data structure is stored in SRAM.

20. The method of claim 18, wherein the data structure is a tree structure.

21. The method of claim 11, wherein the invalid page counter is stored in DRAM.

22. A method for selecting memory blocks in a non-volatile memory array of a storage subsystem for garbage collection memory commands, the method comprising:

maintaining data related to a number of invalid pages within the memory blocks;

assigning the memory blocks to a plurality of pools, each of the pools configured to have a different minimum threshold of invalid pages in the individual memory blocks assigned to the pool; and

selecting a memory block assigned to a pool with the highest minimum threshold for garbage collection.

23. The method of claim 22 wherein the selecting further comprises:

identifying a pool with the highest minimum threshold with at least one memory block entry.

24. The method of claim 22 further comprising:

updating the data when a memory command received from a host system causes a validity of a page within the memory blocks to be changed; and

re-assigning a memory block containing the page to a new pool with a higher minimum threshold of invalid pages based on the updated data.

25. A method for selecting memory blocks in a non-volatile memory array of a storage subsystem for garbage collection memory commands, the method comprising:

maintaining statistical data regarding how many pages within the memory blocks are invalid;

using the statistical data to maintain a plurality of pools of memory blocks based on the number of invalid pages; and

selecting a first memory block for garbage collection from a first pool.