Method and Apparatus for Providing Improved Garbage Collection Process In Solid State Drive

Abstract

An improved garbage collection (“GC”) process configured to recover new blocks from used storage space is disclosed. After initiating the GC process for a flash memory in accordance with at least one of predefined triggering events, a first valid page within a first block marked as an erasable block is identified. Upon determining a first signature representing the content of the first valid page according to a predefined signature generator, the process identifies a second valid page within a second block as a duplicated page of the first valid page in response to the first signature. The process subsequently associates the logical block address (“LBA”) of the first valid page to the second valid page. In an alternative embodiment, page compression and sequential order of page arrangement can also be implemented to further enhance efficiency of garbage collection.

What is claimed is: 
     
         1 . A method for recycling memory space containing stale data in a non-volatile memory (“NVM”) storage system, comprising:
 identifying a first valid page within a first block marked as an erasable block; 
 generating, by a signature generator, a first signature in accordance with content of the first valid page; 
 comparing the first signature with a plurality of signatures stored in a signature table for identifying a second valid page within a second block as a duplicated page of the first valid page; and 
 associating a logical block address (“LBA”) of the first valid page to the second valid page when the first signature matches with a second signature of the plurality of signatures indicating the second valid page containing substantially same data as the first valid page. 
 
     
     
         2 . The method of  claim 1 , further comprising issuing a signal to initiate a process of garbage collection (“GC”) in a NVM in accordance with at least one of predefined triggering events. 
     
     
         3 . The method of  claim 1 , further comprising compressing content of the first valid page to reduce number of bytes representing the content of the first valid page; and
 writing compressed first valid page to a new valid block.   
     
     
         4 . The method of  claim 3 , further comprising:
 arranging a plurality of compressed valid pages including compressed first valid page in a sequential order; and   writing the plurality of compressed valid pages to a new block in the sequential order.   
     
     
         5 . The method of  claim 1 , further comprising:
 arranging a plurality of valid pages including the first valid page in a sequential order when the first signature does not match with anyone of signatures stored in the signature table; and   writing a plurality of compressed valid pages to a new block in the sequential order.   
     
     
         6 . The method of  claim 2 , wherein issuing a signal to initiate a process of GC in a non-volatile memory includes activating the process of GC to remove stale data from a flash memory in response to one of detecting expired blocks, high error rate during page read, exceed total read times, and high invalid pages. 
     
     
         7 . The method of  claim 1 , wherein generating, by a signature generator, a first signature includes hashing the content of the first valid page to generate a unique value representing the first valid page. 
     
     
         8 . The method of  claim 1 , wherein comparing the first signature with a plurality of signatures stored in a signature table includes comparing content of the first signature with every signature stored in the signature table in a solid state drive (“SSD”) controller. 
     
     
         9 . The method of  claim 1 , wherein associating a logical block address (“LBA”) of the first valid page to the second valid page includes updating flash translation layer (“FTL”) to point the LBA of the first valid page to the second valid page. 
     
     
         10 . A memory device comprising:
 a plurality of non-volatile memory (“NVM”) blocks wherein each of the plurality of non-volatile memory blocks includes a set of non-volatile memory pages configured to store information persistently; and   a memory controller coupled to the plurality of NVM blocks and configured to manage the plurality of NVM blocks, wherein the memory controller includes:
 a garbage collection (“GC”) manager configured to recover storage space based on a predefined GC triggering events; 
 a signature table coupled to the GC manager and configured to store a plurality of signatures representing content of valid pages in the plurality of NVM blocks; and 
 a de-dupe module coupled to the GC manager and capable of identifying a duplicated page for a valid page within an erasable block based on the plurality of signatures in the signature table. 
   
     
     
         11 . The device of  claim 10 , wherein the memory controller further includes a compressor configured to generate a compressed valid page in accordance with content of the valid page before rewriting the compressed valid page to a new block. 
     
     
         12 . The device of  claim 10 , wherein the memory controller further includes a sequencer configured to arrange a plurality of valid pages in a sequential order before the valid pages are moved into one or more blocks. 
     
     
         13 . The device of  claim 10 ,
 wherein the plurality of NVM blocks is a group of flash memory blocks wherein each block includes  256  pages of flash memory; and   wherein a garbage collection manager includes a garbage collection scan and garbage block identifier capable of identifying one or more valid pages in a garbage block.   
     
     
         14 . The device of  claim 10 , wherein the de-dupe module includes a hasher configured to generate a signature in accordance with hashing content of a page. 
     
     
         15 . The device of  claim 11 , wherein the de-dupe module includes a signature generator configured to generate a unique signature based on content of a page. 
     
     
         16 . A method for recycling memory space containing stale data in a non-volatile memory (“NVM”) storage system, comprising:
 generating, by a signature generator, a first signature in accordance with content of the first valid page within a first block marked as an erasable block; 
 comparing the first signature with a plurality of signatures stored in a signature table for identifying a second valid page within a second block as a duplicated page of the first valid page; 
 associating a logical block address (“LBA”) of the first valid page to the second valid page when the first signature matches with a second signature of the plurality of signatures; and 
 updating a flash translation layer (“FTL”) to point the LBA of the first valid page to the second valid page. 
 
     
     
         17 . The method of  claim 16 , further comprising:
 arranging a plurality of compressed valid pages including compressed first valid page in a sequential order; and   writing the plurality of compressed valid pages to a new block in the sequential order.   
     
     
         18 . The method of  claim 16 , further comprising initiating a process of GC in a non-volatile memory for activating the process of garbage collection to remove stale data from a flash memory in response to one of detecting expired blocks, high error rate during page read, exceed total read times, and high invalid pages. 
     
     
         19 . The method of  claim 16 , further comprising determining a first signature representing content of the first valid page in accordance with a predefined signature generator. 
     
     
         20 . The method of  claim 19 , further comprising identifying a second valid page within a second block as a duplicated page of the first valid page when the first signature matches with a signature associated with the second valid page.