Adaptive garbage collection including flash memory using age and staleness parameters
Data being stored in a block of flash memory system may be characterized as being frequently modified or infrequently modified (hot/cold) based on a heuristic. When performing garbage collection, if the data from hot blocks is consolidated and data from cold blocks is separately consolidated by writing the data to different free blocks, the number of write operations to perform the garbage collection may be reduced. The lower “write amplification” contributes to increasing the lifetime of the memory circuit. When the number of blocks in a pool of previously erased blocks is reduced to a threshold value, a block having data previously stored therein may be selected for garbage collection based on a second heuristic.
1. A method of using a processor to manage a flash memory, comprising:
allocating a first number of blocks of the flash memory to store user data and a second number of blocks of the flash memory as an erased block pool, each block of flash memory comprised of a plurality of pages for storing data;
maintaining a garbage collection parameter for a block, comprising at least an age parameter and a staleness parameter for the block, where the age parameter is representative of a number of times data in any block of the first number of blocks of memory has been erased since a last time data in the block has been erased, and a staleness parameter represents a number of stale (invalid) pages of the block; and,
when an erased block is needed to replenish the erased block pool, selecting, for garbage collection, a block from the blocks storing data having a highest garbage collection parameter valuefor garbage connection;
determining a hot or cold status of the block being garbage collected by computing a heuristic value, and when the block is garbage collected, all valid data of the block is designated to be either hot data or cold data based on the heuristic value of the block, wherein hot data is data that is frequently modified and cold data is data that is not frequently modified;
maintaining a first write stream, a second write stream and a third write stream, such that data from the each of the first write stream, the second write stream and the third write stream is written to separate blocks of the flash memoryby a flash translation layer;
inserting user written data in the first write stream, hot data in the second write stream and cold data in the third write stream;
determining if a free page location is available for writing data of each of the first write stream, the second write stream or the third stream;
if no free page location is available for a selected stream of the first write stream, the second write stream or the third write stream, selecting a block of memory from the erased block pool and associating the erased block of memory from the erased block pool with one of the streams requiring page locations for writing the data;
if a page is available for writing the data, continue writing data from the stream until no page location is available;
determining if a number of erased blocks in the erased block pool has been reduced to a predetermined number, and if this predetermined number is reached, selecting the block of memory from the blocks of memory storing data having a highest garbage collection parameter for the garbage collection;
moving each valid page of data from the block being garbage collected to either the second write stream or the third write stream, depending on whether the block was determined to be hot or cold respectively, until all valid data has been moved from the block;
erasing the block; and
allocating the erased block to the erased block pool.
2. The method of claim 1 , wherein the age parameter is an index for each block whose value is initialized for each block when the block of the plurality of blocks of the free block pool is allocated to receive data from one of the first write stream; the second write stream or the third write stream, and an index is incremented each time any block of the first number of blocks of the flash memory is erased.
3. The method of claim 1 , wherein the staleness parameter is an index whose value is set to a predetermined value when the block of the plurality of blocks of the free block pool is allocated to receive data from one of the first write stream, the second write stream, or the third write stream; and the index is incremented each time a status of a page of the block is changed from valid to invalid (stale).
4. The method of claim 1 , wherein the garbage collection parameter heuristic value is a product of based on at least the age parameter and the staleness parameter.
5. A system comprising:
a processor; and
a flash memory comprising blocks of memory, wherein each of the blocks or memory comprises a plurality of pages for storing data;
the processor is configured to allocate a first number of blocks of the flash memory to store user data and a second number of blocks of the flash memory as an erased block pool;
the processor is configured to maintain a garbage collection parameter for a block, comprising at least an age parameter and a staleness parameter for the block, where the age parameter is representative of a number of times any block of the first number of blocks of memory has been erased since a last time the block has been erased, and a staleness parameter represents a number of stale (invalid) pages of the block; and,
the processor is configured to select for garbage collection, when an erased block is needed to replenish the erased block pool, a block from the blocks storing data having a highest garbage collection parameter value;
the processor is configured to determine a hot or cold status of the block being garbage collected by computing a heuristic value, and when the block is garbage collected, the processor is configured to designate all valid data of the block to be either hot data or cold data based on the heuristic value of the block, wherein hot data is data that is frequently modified and cold data is data that is not frequently modified;
the processor is configured to maintain a first write stream, a second write stream and a third write stream, such that data from the each of the first write stream, the second write stream and the third write stream is written to separate blocks of the flash memory;
the processor is configured to insert user written data in the first write stream, hot data in the second write stream and cold data in the third write stream;
the processor is configured to determine if a free page location is available for writing data of each of the first write stream, the second write stream or the third stream;
if no free page location is available for a selected stream of the first write stream, the second write stream or the third write stream, the processor is configured to select a block of memory from the erased block pool and associating the block of memory from the erased block pool with one of the streams requiring page locations for writing the data;
if a page is available for writing the data, the processor is configured to continue writing data from the stream until no page location is available;
the processor is configured to determine if a number of erased blocks in the erased block pool has been reduced to a predetermined number, and if this predetermined number is reached, the processor is configured to select the block of memory from the blocks of memory storing data having a highest garbage collection parameter for the garbage collection;
the processor is configured to move each valid page of data from the block being garbage collected to either the second write stream or the third write stream, depending on whether the block was determined to be hot or cold respectively, until all valid data has been moved from the block;
the processor is configured to erase the block; and
the processor is configured to allocate the erased block to the erased block pool.
6. The system of claim 5 , wherein the age parameter is an index whose value is initialized when the block of the plurality of blocks of the free block pool is allocated to receive data from one of the first write stream; the second write stream or the third write stream, and an index is incremented each time any block of the first number of blocks of the flash memory is erased.
7. The system of claim 5 , wherein the staleness parameter is an index whose value is set to a predetermined value when the block of the plurality of blocks of the free block pool is allocated to receive data from one of the first write stream, the second write stream, or the third write stream; and the index is incremented each time a status of a page of the block is changed from valid to invalid (stale).
8. The system of claim 5 , wherein the heuristic value is based on at least the age parameter and the staleness parameter.