# US 2017/0286291 A1 · Method and system for compacting data in non-volatile memory > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2017/0286291 A1 - Document ID: US20170286291A1 - Status: Published application - Kind: A1 - Application number: 15/083,723 - Filed: 2016-03-29 - Published: 2017-10-05 - Earliest claimed: 2016-03-29 - Assignees: SanDisk Technologies LLC - Applicants: SanDisk Technologies Inc. - Inventors: Nicholas James Thomas - Web page: https://patentgrep.com/patent/US20170286291A1 ## CPC - G06F 12/0253: {Garbage collection, i.e. reclamation of unreferenced memory} - G06F 2212/1044: Space efficiency improvement - G06F 2212/2022: Flash memory - G06F 2212/7205: Cleaning, compaction, garbage collection, erase control - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract A system and method for compacting data in a non-volatile memory system that may reduce the need for control data updates is described. The method may include copying valid data from a source block to a destination block, and also writing new host data to the destination block, such that the offset position in the destination block of the copied data is the same as in the source block and fewer mapping table updates are needed for the copied data. The system may include a non-volatile memory system with a coarse granularity mapping table and a fine granularity mapping table where a controller in the non-volatile memory system is configured to only update the coarse granularity mapping table for compacted data written to a new block, but is configured to update both the fine and coarse granularity mapping tables for new host data written to the new block. ## Claims ### Claim 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; and 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. ### Claim 2 (depends on 1) The method of claim 1, wherein selecting the fully programmed block comprises selecting a least recently used block in the non-volatile memory. ### Claim 3 (depends on 1) 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. ### Claim 4 (depends on 1) The method of claim 1, wherein the valid data from the source block only comprises mapping data for the non-volatile memory. ### Claim 5 (depends on 4) The method of claim 4, wherein writing new data comprises writing updated mapping data to the destination block. ### Claim 6 (depends on 1) 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. ### Claim 7 (depends on 1) The method of claim 1, 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 new data to the destination block; and only updating the second mapping table when copying valid data from the source block to the destination block. ### Claim 8 A non-volatile memory system comprising: a non-volatile memory having a plurality of memory blocks; and a controller in communication with the non-volatile memory, the controller configured to: select a fully programed 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 blocks; and 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. ### Claim 9 (depends on 8) The non-volatile memory system of claim 8, wherein the controller is configured to select a least recently used block in the non-volatile memory as the source block. ### Claim 10 (depends on 8) The non-volatile memory system of claim 8, 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. ### Claim 11 (depends on 8) The non-volatile memory system of claim 8, wherein the source block only comprises mapping data for the non-volatile memory. ### Claim 12 (depends on 11) The non-volatile memory system of claim 11, wherein the new data comprises only updated mapping data. ### Claim 13 (depends on 8) The non-volatile memory system of claim 8, 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. ### Claim 14 (depends on 8) The non-volatile memory system of claim 8, 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. ### Claim 15 (depends on 8) The non-volatile memory system of claim 8, wherein the non-volatile memory system further comprises: 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 wherein the controller is further configured to: update both the first and second mapping tables when writing new data to the destination block; and only update the second mapping table when copying valid data from the source block to the destination block. ### Claim 16 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. ### Claim 17 (depends on 16) The non-volatile memory system of claim 16, 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. ### Claim 18 (depends on 16) The non-volatile memory system of claim 16, 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. ### Claim 19 (depends on 16) The non-volatile memory system of claim 16, wherein the source block only comprises mapping data for the non-volatile memory system. ### Claim 20 (depends on 19) The non-volatile memory system of claim 19, wherein the new data comprises only updated mapping data for the non-volatile memory system.