HK1160526B - System and method for managing garbage collection in solid-state memory - Google Patents

Description

System and method for managing garbage collection in solid state memory

Background

The solid state memory subsystem executes a plurality of commands in its normal operation. For example, garbage collection is frequently performed on memory blocks that may contain valid and invalid data. When such a memory block is selected for garbage collection, a garbage collection operation copies valid data within the memory block to a new location in memory and then erases the entire memory block, making the entire block available for future data writes. Thus, the amount of memory freed by the garbage collection process depends on the amount of invalid pages within the memory block selected for garbage collection.

Disclosure of Invention

Embodiments of the present invention relate to optimizing the selection of memory blocks for garbage collection to maximize the amount of memory freed by the garbage collection operation. The systems and methods disclosed herein provide for efficient selection of optimal or near optimal garbage collection candidate blocks, with the optimal selection defined as the block with the most invalid pages.

Certain embodiments disclosed herein provide a storage subsystem comprising: a non-volatile solid-state memory array; and a controller including a garbage collection module and configured to receive and execute memory commands from a host system and the garbage collection module. The controller is further configured to: maintaining, 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 allocated to a first pool by the number of invalid pages, wherein the garbage collection module is configured to select a memory block from a plurality of pools based on the number of invalid pages. The controller is further configured to update the invalid page counter associated with the first memory block after executing a memory command from the host system that causes a change in validity of a page within the first memory block; and reassigning the first memory block to a second pool when the updated invalid page counter exceeds a threshold.

Certain embodiments disclosed herein provide a method of managing memory operations in a non-volatile solid-state memory. The method comprises the following steps: 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 being sorted into a first pool of a plurality of pools by the number of invalid pages. The method also includes updating the invalid page counter for the first memory block after receiving a write command from a host system that causes a change in validity of a page within the first memory block; and when the invalid page counter of the first memory block indicates that the number of invalid pages within the first memory block exceeds a threshold, reclassifying the first memory block to a second pool of the plurality of pools.

Certain embodiments disclosed herein provide a method of selecting a block of memory in a non-volatile memory array of a storage subsystem for a garbage collection memory command. The method may include maintaining data relating to a number of invalid pages within the memory block; allocating the memory blocks into a plurality of pools, each pool configured to have a different invalid page minimum threshold in the respective memory blocks allocated to that pool; and updating the data when a memory command received from a host system causes a change in the validity of a page within the memory block. The method also includes reallocating memory blocks containing the page to a new pool having a higher invalid page minimum threshold based on the updated data and selecting memory blocks allocated to the pool having the largest minimum threshold for garbage collection.

Certain embodiments disclosed herein provide a method of selecting a block of memory in a non-volatile memory array of a storage subsystem for a garbage collection memory command. The method may include maintaining statistics regarding the number of invalid pages within the memory block; maintaining a plurality of pools of memory blocks using the statistical data based on a number of invalid pages; and updating the statistics when a memory command received from a host system causes a change in validity of a page within the memory block. The method further includes reallocating a memory block containing the page to a new pool of the plurality of pools based on the updated statistics, the new pool having a higher minimum threshold of invalid pages than a current pool associated with the memory block; and selecting a first memory block from a first pool of the plurality of pools for garbage collection.

The use of a pool as described herein facilitates optimal or near optimal selection of garbage collection candidate blocks in an efficient manner. Furthermore, the data structure of the pool can be implemented with a bit mask, which occupies a minimum space in memory.

Drawings

Systems and methods embodying various features of the invention will now be described with reference to the accompanying drawings, in which:

FIG. 1 is a block diagram illustrating a solid-state storage subsystem according to one embodiment.

FIG. 2 is a flow diagram illustrating a method of maintaining invalid page information on a block of memory within a solid-state storage subsystem, according to one embodiment.

FIG. 3 is a flow diagram illustrating a method of selecting a block of memory for garbage collection according to one embodiment.

FIG. 4 illustrates an example of using invalid blocks and free block pools to track memory blocks for garbage collection according to one embodiment.

Detailed Description

While particular embodiments of the present invention have been described, these embodiments have been presented by way of example only, and are not intended to limit the scope of the invention. Indeed, the novel methods and systems described herein may be embodied in a variety of other forms. Furthermore, various omissions, substitutions and changes in the form of the methods and systems described herein may be made without departing from the spirit of the inventions. The accompanying claims and their equivalents are intended to cover such forms or modifications as would fall within the spirit and scope of the inventions.

Summary of the invention

Embodiments of the present invention relate to optimizing the selection of memory blocks for garbage collection to maximize the amount of memory freed by the garbage collection operation. The systems and methods disclosed herein provide for efficient selection of optimal or near optimal garbage collection candidate blocks, with the optimal selection defined as the block with the most invalid pages. In one embodiment, the controller sorts the memory blocks into respective invalid block pools by the amount of invalid pages each block contains. When performing garbage collection, the controller selects blocks from the non-empty pool of blocks having the largest minimum number of invalid pages. These pools facilitate 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 that occupy minimal space in memory. Although this disclosure describes various embodiments that are applicable to blocks, embodiments are not limited and may be applied to other units of memory, such as super blocks.

System overview

FIG. 1 is a block diagram illustrating an embodiment of a storage subsystem. As shown, the storage subsystem 140 includes a controller 150, which in turn includes a host command queue 142, a garbage collection command queue 144, and a garbage collection module 148. In one embodiment, the host command queue 142 receives memory commands from a driver 132 residing in the host system 130, and the garbage collection command queue 144 receives commands from a garbage collection module 148 that manages garbage collection. In other embodiments, commands from the driver 132 and the garbage collection module 148 are received into a single queue for execution. The memory commands from the drive 132 may include write and read commands issued by the host system 130, while the memory commands from the garbage collection module 148 may include commands for garbage collection. As further shown in FIG. 1, in one embodiment, the controller 150 executes commands in the host command queue 142 and the garbage collection command queue 144 on one or more non-volatile solid state memory arrays 160.

The controller 150 also maintains a number of data structures, which in one embodiment include an invalid page table 152 and a mapping table 154. In one embodiment, the invalid page table 152 keeps track of the validity of data located at physical page addresses throughout the non-volatile solid-state memory array 160, while the mapping table 154 keeps track of the correspondence between Logical Block Addresses (LBAs) and physical page addresses in the non-volatile memory array 160. In one embodiment, other data structures include invalid page counter 156, invalid block pool 162, and free pool 164. In one embodiment, the invalid page counters 156 are maintained for at least some memory blocks in the memory array 160. In one embodiment, an invalid page counter 156 is maintained for each block and tracks the number of invalid pages within the associated block. In one embodiment, the invalid page counter 156 and/or the invalid page table 152 are stored in Dynamic Random Access Memory (DRAM). In one embodiment, blocks are assigned to respective invalid block pools 162. For example, the blocks in use may be classified into a pool of blocks having at least 25% invalid pages, a pool of blocks having at least 50% invalid pages, a pool of blocks having at least 75% invalid pages, or a pool of blocks having 100% invalid pages. Blocks available for new writes are sorted into the free pool 164. In one embodiment, the data structure relating to pool allocation is stored in a Static Random Access Memory (SRAM). The use and maintenance of these data structures for garbage collection will be described further below.

Maintaining invalid page data for a memory block

FIG. 2 is a flow diagram illustrating a method 200 for maintaining invalid page information on a memory block, according to one embodiment. At block 202, the controller 150 begins receiving a write command (operation) for execution. The write operation may be issued by the host system 130. At block 204, the controller updates the mapping table 154 as part of performing the write operation. In one embodiment, the controller updates the mapping table by first locating an entry for the LBA in the write command in the mapping table to determine the physical page address corresponding to the LBA, and then updating the located entry with the new physical page address to which the new data was written. For example, a write may point to LBA10, which was mapped to Block 5, Page 2, prior to the write operation. Before actually writing to memory, the controller updates the mapping table so that the entry for LBA10 corresponds to the new location (e.g., block 12, page 4) to which the data will be written. Alternatively, the controller may update the mapping table after actually writing to the memory. In block 206, the controller determines whether an update to an invalid page table is required. This is required in most cases unless the particular LBA entry associated with the write operation has not previously been assigned any physical address. In the above example, page 2 is now invalid due to block 5, and the portion of invalid page table 154 that covers block 5 needs to be updated. If an update is required, the method proceeds to block 208, where the controller increments the invalid page counter 156 for the changed block. Next, in block 210, the invalid page table 152 is updated.

At block 212, the controller makes another check to determine if the page counter for the changed block crosses the invalid page threshold. If the threshold has been crossed, the block is reassigned to a new pool at block 214. Following the above example, if the invalid page counter indicates that the number of invalid pages in block 5 has increased to 1024 in total 2048, block 5 is reassigned from the 25% invalid pool to the 50% invalid pool. In one embodiment, the controller process handling write operations from the host obtains locks (locks) of invalid page counter, invalid page table and invalid block pool data structures, or a subset of these data structures, while doing the above update tasks. Since the garbage collection process references some of the same data structures in operation, locking these data structures prevents the garbage collection process and other internal system processes from reading out stale data and executing commands, which would cause data consistency problems. For example, in one embodiment, when an invalid page table is used to prevent an impending garbage collection command from executing at a physical page address indicated as containing invalid information, the table lock is ensured at the time of the update to correctly prevent a garbage collection command attempting to write invalid data from executing in accordance with the update information. In other embodiments, the various update steps may be performed in a different order than shown in FIG. 2.

Selecting memory blocks for garbage collection using invalid page data

FIG. 3 is a flow diagram illustrating a method of selecting a memory block for garbage collection according to one embodiment. In one embodiment, the method 300 is performed by the controller 150 to select an optimal or near optimal candidate block for garbage collection. As discussed above, the optimal selection includes selecting the block with the largest number of invalid pages to maximize the amount of memory freed by the garbage collection operation.

In FIG. 3, the threshold percentages associated with the various pools are provided as examples only and other percentages may be used. Additionally, in one embodiment, the minimum threshold percentage is set according to over-provisioning (extra storage beyond the declared capacity) provided in the non-volatile memory array. For example, the lowest threshold percentage may be equal to or greater than the over-supply amount, as the over-supply amount is related to the minimum amount of invalid pages in the block when the free block is exhausted. In the illustrated example, the lowest threshold of 25% invalid pages corresponds to a 25% over-provisioning provided in the example storage subsystem. In other embodiments, the number of pools may be set to other numbers, and the lowest threshold percentage may be higher or lower than the oversupply percentage. In one embodiment, the threshold for at least one pool is set to 100% or close to 100% invalid to capture the block that will produce the greatest amount of space after garbage collection.

The method 300 begins at block 302 where the controller determines whether there are enough blocks remaining in the free pool to accommodate the pending write operation. If it is determined that there are not enough blocks in the free pool, garbage collection is triggered and the method proceeds to block 304 where the controller determines if there are any blocks in the 100% invalid pool. If so, a block of memory from the pool is selected in block 312. If not, the controller determines whether there are any blocks in the 75% invalid pool in block 306. If so, a block of memory from the pool is selected in block 312. If not found in the 75% pool, the same process is repeated for the 50% invalid pool in block 308. Finally, if there are no chunks in the 100%, 75%, or 50% pools, a chunk is selected from the 25% pool in block 310. The 25% pool is the default pool in this example and is expected to contain at least one block because block 310 is only reached if the free pool is determined to be exhausted in block 302. This is because a 25% over-provisioning ensures that at least one block has at least 25% invalid pages when there are no more free blocks. The candidate block selected in block 310 or 312 is then used in a garbage collection operation in block 314. Finally, while FIG. 3 illustrates selecting a single block, other embodiments may select multiple blocks from one or more pools together for garbage collection. For example, if the controller determines that 45 blocks are needed for garbage collection, and there are only 10 blocks in the 100% pool and 41 blocks in the 75% pool, the controller may select 10 from the 100% pool and the remaining 35 it needs from the 75% pool.

Multi-pool data structure

FIG. 4 illustrates an example setting of the invalid chunk pool 402, according to one embodiment. As shown, example blocks 0-7 are distributed among 4 pools 402A-D according to the number of invalid pages each block contains. As previously shown in fig. 3, if it is determined that there are not enough blocks in the free pool 404, the controller triggers garbage collection. If and when this occurs, block 7 will be selected first for garbage collection since it belongs to a 100% invalid pool. If more blocks are still needed for garbage collection, the controller will select any block from pool 402B (Block 0, Block 2, or Block 5) in the next cycle because pool 402A is now empty and pool 402B is now a non-empty pool with the largest minimum invalid page threshold (at least 75%).

In one embodiment, to achieve speed optimization, the selection of a block assigned to a pool of multiple blocks does not depend on the actual percentage of invalid pages of the block and candidate blocks in the pool may be selected based on the current location of the selection process or blocks may be selected randomly. The selection process may traverse the blocks in a continuous manner to locate the next available block assigned to the largest non-empty pool. For example, if the selection process finally ended the search for a candidate block at block 1, block 2 would be selected because there were no more blocks in the 100% pool (block 7 has already been taken) and block 2 is the first block in the 75% pool encountered in the selection process. Thus, even if it has a lower percentage than either block 0 or block 5, block 2 is selected from pool 402B. In the next cycle, as the selection process extracts from block 3, moves to block 4, and finds block 5, block 5 will be selected, which is the next block belonging to the 75% pool. In other embodiments, additional checks and/or comparisons may be made so that a greater or maximum percentage of blocks in the same pool may be selected. In various embodiments, several blocks are selected at a time and may span different pools (e.g., block 7 may be selected along with blocks 0, 2, and 5). However, in some embodiments, the selection process keeps going from the pool of blocks with the largest minimum amount of invalid pages to the pool of blocks with the smallest minimum amount of invalid pages.

While the selection process removes blocks from the pool, other memory operations may cause blocks to be reallocated to a pool having a greater minimum amount of invalid pages or blocks may be newly allocated to a pool if the blocks have not previously reached any threshold.

In one embodiment, the pool structure is implemented with a bitmask, and a block may be associated with one or more bits indicating its allocation to the pool. For example, a 4-pool structure may include 4 corresponding bitmasks for chunks, each bitmask indicating whether a respective chunk belongs to a particular pool. In one embodiment, additional check bits may be allocated to a group of blocks to speed up the selection process. For example, a check bit may be used to indicate the status of 32 blocks, so that when the check bit is set to "0", the selection process is able to skip 32 blocks, knowing that none of these blocks has a "1" bit indicating allocation to the particular pool under consideration. If the check bit is set to "1," the selection process will check the individual bits of the 32 blocks, since a "1" indicates that at least one block is assigned to a particular pool. In another embodiment, additional check bits may be assigned to check bit groups in a hierarchical order. For example, the additional check bits may be assigned to a set of check bits such that if any of the check bits is set to "1," the additional check bits will also be set to "1. The check bit method reduces the time required to locate the block that is assigned to the pool with the largest minimum number of invalid pages. In another embodiment, the pool assignments are maintained in a table.

The multi-pool data structure provides an efficient way to select the optimal or near optimal candidate blocks for garbage collection. In one embodiment, the sorted linked list structure is used to organize the blocks that qualify for garbage collection. In one embodiment, the blocks are sorted in the linked list by the amount of invalid pages in the block, so that the optimal candidate for garbage collection can be located by selecting the block from either the front or back of the linked list (depending on the direction of the sorting). In one embodiment, the pools described above are implemented in a sorted linked list structure with pointers to entries corresponding to the minimum invalid page threshold for each pool, enabling quick location of the blocks allocated to each pool. In another embodiment, one or more linked lists are used for each pool, and blocks are assigned to a pool and inserted into the one or more linked lists of the corresponding pool as described above. In some embodiments, a pool data structure implemented with bitmasks requires significantly less overhead memory than a linked-list implementation. This difference is significant in storage subsystems where there are potentially millions of blocks or tens of thousands of super blocks, which may be candidates for garbage collection at any given time.

Conclusion

The features and attributes of the specific embodiments disclosed above may be combined in different ways to form additional embodiments, all of which are intended to fall within the scope of the present disclosure. While the present disclosure provides certain preferred embodiments and applications, other embodiments that are apparent to those of ordinary skill in the art, including embodiments that do not provide all of the features and advantages set forth herein, are also within the scope of the present disclosure. Accordingly, the scope of the disclosure is intended to be defined only by reference to the appended claims.

Claims (24)

1. A storage subsystem, comprising:

a non-volatile solid-state memory array; and

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

maintaining, 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 allocated to a first pool by the number of invalid pages, wherein the garbage collection module is configured to select a memory block from a plurality of pools based on the number of invalid pages;

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

updating the invalid page counter associated with the first memory block; and

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

2. The storage sub-system of claim 1, wherein the controller is further configured to allocate the first memory block to a pool for free memory blocks after garbage collecting the first memory block.

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

4. The storage sub-system of claim 1, wherein the plurality of pools includes the first pool initially configured for memory blocks having at least 25% invalid pages, the second pool initially configured for memory blocks having at least 50% invalid pages, the third pool initially configured for memory blocks having at least 75% invalid pages, and a fourth pool initially configured for memory blocks having 100% invalid pages.

5. The storage sub-system of claim 1, wherein the data structure is used to store data related to pool allocation of memory blocks.

6. The storage sub-system of claim 5, wherein the data structure is stored in static random access memory.

7. The storage sub-system of claim 5, wherein the data structure is a tree structure.

8. The storage sub-system of claim 5, wherein the controller is further configured to obtain a lock on the data structure prior to reallocating 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 a dynamic random access memory.

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 being sorted into a first pool of a plurality of pools by the number of invalid pages;

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

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

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

12. The method of claim 11, further comprising:

selecting a second memory block for garbage collection that is classified into a third pool having a maximum invalid page minimum threshold.

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

14. The method of claim 11, further comprising:

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

updating an invalid page table with information that prevents an impending garbage collection command from executing at the physical page address;

executing the write command; and

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

15. The method of claim 14, wherein 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 bit mask in which bits are used to represent the validity of data at a page address.

17. The method of claim 14, wherein the invalid page table is stored in a dynamic random access memory.

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

19. The method of claim 18, wherein the data structure is stored in static random access memory.

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 a dynamic random access memory.

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

maintaining data relating to a number of invalid pages within the memory block;

allocating the memory blocks into a plurality of pools, each pool configured to have a different invalid page minimum threshold in the respective memory blocks allocated to that pool;

updating the data when a memory command received from a host system causes a change in the validity of a page within the memory block;

reassigning the memory block containing the page to a new pool having a higher invalid page minimum threshold based on the updated data; and

the memory blocks allocated to the pool with the largest minimum threshold are selected for garbage collection.

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

the pool having the largest minimum threshold is identified with at least one memory block entry.

24. A method of selecting a memory block in a non-volatile memory array of a storage subsystem for a garbage collection memory command, the method comprising:

maintaining statistics regarding the number of invalid pages within the memory block;

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

updating the statistics when a memory command received from a host system causes a change in validity of a page within the memory block;

reassigning the memory block containing the page to a new pool of the plurality of pools based on the updated statistics, the new pool having a minimum threshold of invalid pages higher than a current pool associated with the memory block; and

a first memory block is selected from a first pool of the plurality of pools for garbage collection.