Memory system having persistent garbage collection

Abstract

Non-volatile memory systems such as those using NAND FLASH technology have a property that a memory location can be written to only once prior to being erased, and a contiguous group of memory locations need to be erased simultaneously. The process of recovering space that is no longer being used for storage of current data, called garbage collection, may interfere with the rapid access to data in other memory locations of the memory system during the erase period. The effects of garbage collection on system performance may be mitigated by performing portions of the process contemporaneously with the user initiated reading and writing operations. The memory circuits and the data may also be configured such that the data is stored in stripes of a RAID array and the scheduling of the erase operations may be arranged so that the erase operations for garbage collection are hidden from the user operations.

1 . A non-volatile data storage system, comprising:
 a memory module having a plurality of non-volatile memory circuits (NVS) each NVS circuit configurable into a first memory area and a second memory area, each of the first and the second memory areas having a plurality storage locations for data,   wherein the a memory circuit of the plurality of memory circuits is further configurable such that a storage location of the plurality of storage locations of the memory circuit is characterized as having a status of one of live, dead, or free, and prior to all of the storage locations of the first memory area being characterized as being either live or dead, a processor of the memory module is configurable to move data from at least one active storage location in the first memory area of the memory circuit to a free storage location not in the first memory area.   
     
     
         2 . The data storage system of  claim 1 , wherein the first memory area and the second memory area comprise a memory block of the memory circuit and when none of the storage locations in the memory is free, the processor is configurable to move the data in the live storage locations to another memory block. 
     
     
         3 . The data storage system of  claim 1 , wherein when none storage areas of a memory block is live, the block is scheduled to be erased. 
     
     
         4 . The data storage system of  claim 3 , wherein a plurality of memory blocks are configured as a RAID stripe where an erase operation is scheduled such that the data stored in the RAID stripe is recoverable prior to the completion of an erase operation in progress at the time a read request is made. 
     
     
         5 . A data storage system comprising:
 a memory module having a plurality of non-volatile memory circuits (NVS) each NVS configurable into a first memory area and a second memory area, each of the first and the second memory areas having storage locations for data, and each of the storage locations once writable unless subsequently erased,   wherein the memory module is further configurable such that each storage location has a status of one of active, dead, or free, and when all of the storage locations of the first memory area of a NVS of the plurality of NVS are either active or dead, and data stored in an active storage location of the first memory area is modified, the memory module is configurable to move data from at least one other active storage location of the memory module to a free storage location not in the first memory area.   
     
     
         6 . The system of  claim 5 , wherein the storage locations the first memory area and the second memory area are logical memory locations. 
     
     
         7 . The system of  claim 5 , wherein when less than a predetermined percentage of the second memory area is one of active or dead storage locations, the data from the least one other active storage location of the first memory area is moved to a free storage location in the second memory area or to a free storage location of another NVS. 
     
     
         8 . The system of  claim 5 , wherein when greater than a predetermined percentage of the second memory area is one of active or dead storage locations, data from least two other active storage locations of the first memory area is moved to a free storage location of the second memory area or to a free storage location of another NVS. 
     
     
         9 . The system of  claim 5 , wherein when data in an active storage location of the second memory area is modified, the memory module is configured to move data from at least one other active storage location of the first memory area to a free storage location not in the first memory area. 
     
     
         10 . The system of  claim 5 , wherein the storage locations comprise a first storage location and a second storage location, and modification of data of the first storage location is performed by writing modified data to the second location, the second location being a free storage location. 
     
     
         11 . The system of  claim 10 , wherein, where each of the first storage location and the second storage location are a plurality of storage locations, and a storage location of the plurality of first storage locations having data that has been written to the second storage location has a status of dead, and a storage location of the plurality of first storage locations having data that has not been written to second storage locations has a status of active, and data of active storage locations is writable to a free first or second storage location on any of a plurality of NVS. 
     
     
         12 . The system of  claim 5 , wherein a number of storage locations of the second memory area is about 20 percent of sum of the number of storage locations of the first memory area and the second memory area. 
     
     
         13 . The system of  claim 5 , wherein the first memory area and the second memory area comprise a block of the NVS; the block is a minimum erasable area of memory, and each storage location of the block has a status of free after the block is erased. 
     
     
         14 . The system of  claim 13 , wherein the NVS comprises a plurality of blocks of memory. 
     
     
         15 . The system of  claim 5 , where the NVS comprises a flash memory circuit. 
     
     
         16 . The system of  claim 15 , wherein the flash memory circuit is one of a single level cell or a multiple level cell technology. 
     
     
         17 . The system of  claim 5 , wherein the number of storage locations in the first memory area and the second memory area is determined by a system policy. 
     
     
         18 . A method of managing data in a flash memory system, the method comprising:
 allocating a block of flash memory of a flash memory circuit to a first memory area and a second memory area, each memory area having a plurality of pages for storing data;   writing data to a page of the first memory area of a block;   modifying the data of the page by writing modified data to a free page of the block, or to another block having a free page; and   for the condition that the plurality of pages of the first memory area are all either active or dead:   moving data of at least one additional active page from the first memory area to a free page not in the first memory area.   
     
     
         19 . The method of  claim 18 , wherein each page has a status of free, active or dead, and data is writable to free pages. 
     
     
         20 . The method of  claim 19 , further comprising designating a page having data as an active page. 
     
     
         21 . The method of  claim 20 , further comprising designating an active page having data that has been read and modified, modified by writing modified data to another page, or moved, as a dead page. 
     
     
         22 . The method of  claim 18 , further comprising designating all valid pages as free pages after erasing a block of memory. 
     
     
         23 . The method of  claim 18 , wherein for the condition that a predetermined percentage the plurality of pages of the second memory area are either active or dead:
 moving data of at least two additional active pages from the first memory area to a free page not in the first memory area.   
     
     
         24 . The method of  claim 18 , further comprising:
 determining that no free pages remain in the second memory area and:   moving data of at least one of the active pages in the first or second data areas, to a free page not in the first or the second memory areas until the data of all of the pages of the block are dead, in accordance with a policy.   
     
     
         25 . The method of  claim 21 , further comprising marking the block having all dead pages as being available for an erase operation. 
     
     
         26 . The method of  claim 25 , further comprising erasing a marked block, in accordance with a policy. 
     
     
         27 . The method of  claim 26 , wherein the policy is that a marked block of a plurality of marked blocks having the lowest number of previous erases is the marked block selected to be erased. 
     
     
         28 . A computer program product, stored or distributed on or in a computer readable medium, the product comprising:
 instructions for configuring a processor in communication with a flash memory circuit to perform a method of:   allocating free pages of a block of the flash memory circuit to a first memory area and a second memory area;   writing data to a free page of the first memory area and designating the page as an active page;   moving the data of the active page to a free page not in the first memory area, and designating the active page as a dead page;   determining whether all pages of the first memory area are designated as either active or dead pages; and   for each additional page designated as a dead page:   moving data of at least one additional active page from the first memory area to a free page not in the first memory area.   
     
     
         29 . The computer program product of  claim 28 , further comprising: erasing the pages of the block and designating the erased pages as free pages. 
     
     
         30 . The computer program product of  claim 29 , wherein the free page not in the first memory area is a free page in the second memory area, or a free page in a second block of a plurality of blocks of the flash memory circuit. 
     
     
         31 . The computer program product of  claim 29 , wherein, when there are no free pages in the block, data of active pages in the first memory area and the second memory area are moved to the second block, in accordance with a policy. 
     
     
         32 . The computer program product of  claim 31 , wherein when none of the pages of the block are live or free pages, the block is marked for an erase operation. 
     
     
         33 . The computer program product of  claim 32 , wherein a block having a status of being available for an erase operation is erased in accordance with a policy. 
     
     
         34 . The computer program product of  claim 33 , wherein the policy is to erase the block having lowest number of previous erases. 
     
     
         35 . The computer program product of  claim 33 , wherein a pointer having a value equal to that of a free page of the block having the lowest page number is maintained, and performing the steps of writing or moving by writing data to the free page corresponding to the value of the pointer. 
     
     
         36 . A computer memory system, comprising:
 a plurality of non-volatile memory circuits (NVS), wherein a block of data is stored such that the block of data is allocated to a plurality of memory areas of the memory circuits, and a parity block of the block of data is allocated to another of the plurality of memory areas,   wherein erase operations of a garbage collection process for the memory areas are scheduled such that the block of data can be recovered from the memory system by either of: reading the block of parity data and less than all of the plurality of memory areas to which the block of data is stored; or reading the block of data from the plurality of memory areas.