Method and system for compacting data in non-volatile memory

1. A method for managing garbage collection in a non-volatile memory system comprising a non-volatile memory having a plurality of blocks, the method comprising:

selecting a fully programmed block in the non-volatile memory as a source block for compaction;

copying only valid data from the source block into a destination block in the non-volatile memory;

writing new data to the destination block;

wherein the valid data from the source block is copied into the destination block such that an offset location of the valid data in the destination block is identical to an offset location of the valid data in the source block and the new data is written into offset locations in the destination block corresponding to offset locations associated with obsolete data in the source block; and

wherein the non-volatile memory system further comprises a first mapping table containing a mapping of logical block addresses to virtual block addresses, and a second mapping table containing a mapping of virtual block addresses to physical block addresses, and wherein the method further comprises:

updating both the first and second mapping tables when writing the new data to the destination block; and

only updating the second mapping table when copying the valid data from the source block to the destination block.

2. The method of claim 1 , wherein selecting the fully programmed block comprises selecting a least recently used block in the non-volatile memory.

3. The method of claim 1 , wherein selecting the fully programmed block comprises selecting a block in the non-volatile memory having a least amount of valid data.

4. The method of claim 1 , wherein the valid data from the source block only comprises mapping data for the non-volatile memory.

5. The method of claim 4 , wherein writing new data comprises writing updated mapping data to the destination block.

6. The method of claim 1 , wherein copying only valid data from the source block and writing new data comprises:

sequentially reviewing data at each data offset in the source block, wherein at each particular data offset:

when data at the particular data offset is valid data, copying the valid data from the particular data offset to an identical data offset in the destination block; and

when data at the particular data offset is obsolete data, writing new data to the identical data offset in the destination block.

7. A non-volatile memory system comprising:

a non-volatile memory having a plurality of memory blocks;

a first mapping table containing a mapping of logical block addresses to virtual block addresses in the non-volatile memory system;

a second mapping table containing a mapping of virtual block addresses to physical block addresses in the non-volatile memory system; and

a controller in communication with the non-volatile memory, the controller configured to:

select a fully programmed block from the plurality of memory blocks as a source block;

copy valid data from a particular offset location in the source block to a same particular offset location in a destination block in the plurality of memory blocks;

write new data to the destination block only at offset locations corresponding to offset locations of obsolete data in the source block, wherein the destination block contains all valid data from the source block in offset locations identical to original offset locations of the valid data in the source block upon completion of copying all valid data from the source block;

update both the first and second mapping tables when writing the new data to the destination block; and

only update the second mapping table when copying the valid data from the source block to the destination block.

8. The non-volatile memory system of claim 7 , wherein the controller is configured to select a least recently used block in the non-volatile memory as the source block.

9. The non-volatile memory system of claim 7 , wherein the controller is configured to select a block in the non-volatile memory having a least amount of valid data as the source block.

10. The non-volatile memory system of claim 7 , wherein the source block only comprises mapping data for the non-volatile memory.

11. The non-volatile memory system of claim 10 , wherein the new data comprises only updated mapping data.

12. The non-volatile memory system of claim 7 , wherein the non-volatile memory comprises a silicon substrate and a plurality of memory cells forming a monolithic three-dimensional structure, wherein at least one portion of the memory cells is vertically disposed with respect to the silicon substrate.

13. The non-volatile memory system of claim 7 , wherein to copy valid data and write new data to the destination block, the controller is further configured to:

sequentially review data at each data offset in the source block, and at each particular data offset:

when data at the particular data offset is valid data, copy the valid data from the particular data offset to an identical data offset in the destination block; and

when data at the particular data offset is obsolete data, write new data to the identical data offset in the destination block.

14. A non-volatile memory system comprising:

a non-volatile memory having a plurality of memory blocks;

a fine granularity mapping table containing mapping entries of logical addresses to virtual addresses;

a coarse granularity mapping table containing mapping entries of the virtual addresses to physical addresses associated with the plurality of memory blocks; and

a controller in communication with the non-volatile memory, the controller configured to:

relocate valid data from a source block selected from the plurality of memory blocks to a relocation block in the plurality of memory blocks;

write new data to the relocation block;

update both the fine granularity mapping table and the coarse granularity mapping table to map the new data written to the relocation block; and

update only the coarse granularity mapping table, without updating any fine granularity mapping table mapping entries, in response to relocating valid data from the source block to the relocation block.

15. The non-volatile memory system of claim 14 , wherein the non-volatile memory comprises a silicon substrate and a plurality of memory cells forming a monolithic three-dimensional structure, wherein at least one portion of the memory cells is vertically disposed with respect to the silicon substrate.

16. The non-volatile memory system of claim 14 , wherein to relocate the valid data and write the new data to the relocation block, the controller is configured to:

sequentially review data at each data offset in the source block, wherein at each particular data offset the controller is further configured to:

when data at the particular data offset is valid data, copy the valid data from the particular data offset to an identical data offset in the relocation block; and

when data at the particular data offset is obsolete data, write new data to the identical data offset in the relocation block.

17. The non-volatile memory system of claim 14 , wherein the source block only comprises mapping data for the non-volatile memory system.

18. The non-volatile memory system of claim 17 , wherein the new data comprises only updated mapping data for the non-volatile memory system.