SYSTEM AND METHOD FOR TRACKING BLOCK LEVEL MAPPING OVERHEAD IN A NON-VOLATILE MEMORY

• US 20180024920A1
• Filed: 07/20/2016
• Published: 01/25/2018
• Est. Priority Date: 07/20/2016
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Inventors: Thomas, Nicholas James, Kragel, Oleg, Moser, Michael Anthony
• Granted Patent: US 9,921,956 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 2212/1041 Resource optimization
• CPC Class Codes: G06F 2212/1044 Space efficiency improvement
• CPC Class Codes: G06F 2212/2022 Flash memory
• CPC Class Codes: G06F 2212/7201 Logical to physical mapping or translation of blocks or pages
• CPC Class Codes: G06F 2212/7205 Cleaning, compaction, garbage collection, erase control

Abstract

A system and method is disclosed for tracking block mapping overhead in a non-volatile memory. The system may include a non-volatile memory having multiple memory blocks and a processor configured to track a block level mapping overhead for closed blocks of the multiple memory blocks. The processor may be configured to track predetermined logical address ranges within which data written to a block fall, and then store the sum of the number of different logical address ranges for each respective block as a block address entropy metric. The method may include the processor using the block address entropy metric to select source blocks for garbage collection with a lower block address entropy metric or to adjust other operational characteristics such as data routing within the non-volatile memory system based on average block address entropy for a group of blocks.

Claims

1. A non-volatile memory system comprising:

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

a processor in communication with the non-volatile memory, the processor configured to;

receive data from a host;

store the received data in an open block in the non-volatile memory;

update a logical block address (LBA) range data structure dedicated exclusively to the open block to identify one of a plurality of predetermined LBA ranges associated with the received data, wherein the processor is configured to update the LBA range data structure only when the LBA range of the received data contains data associated with a host LBA falling in one of the predetermined LBA ranges for a first time in the open block.

2. The non-volatile memory system of claim 1, wherein the processor is further configured to update a LBA data range counter each time data in a different LBA range of the predetermined plurality of LBA ranges is first received for the open block.

3. The non-volatile memory system of claim 1, wherein the processor is further configured to, upon completely filling the open block with received data, store the LBA data range counter in a block address entropy data structure, wherein the block address entropy data structure comprises respective LBA data range counters for closed blocks in the non-volatile memory.

4. The non-volatile memory system of claim 3, wherein each of the predetermined number of LBA ranges comprises a fixed number of LBAs.

5. The non-volatile memory system of claim 4, wherein each of the predetermined number of LBA ranges comprises a same number of LBAs.

6. The non-volatile memory system of claim 4, wherein the fixed number of LBAs corresponds to a logical address size of a piece of a mapping table for the non-volatile memory.

7. The non-volatile memory system of claim 3, wherein the processor is further configured to select a block for garbage collection based on both an amount of valid data and an LBA data range counter value of closed blocks in the non-volatile

8. The non-volatile memory system of claim 7, wherein the processor is further configured to select a block for garbage collection that has a lowest LBA data range counter value among blocks having a same amount of valid data.

9. A non-volatile memory system comprising:

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

a processor in communication with the non-volatile memory, the processor configured to;

receive data from a host;

store the received data in an open block in the non-volatile memory;

as the received data is stored in the open block, determine a block address entropy value for the open block, wherein the block address entropy value comprises a number of different of mapping address table pieces from a predetermined number of mapping address table pieces of a main mapping table that correspond to logical addresses of the received data in the open block; and

upon fully programming the open block, storing the block address entropy value in an entropy value data structure, the entropy value data structure configured to store a respective block address entropy value for each fully programmed block in the non-volatile memory.

10. The non-volatile memory system of claim 9, further comprising a volatile memory in communication with the processor, the non-volatile memory configured to store only a portion of the mapping address table at one time.

11. The non-volatile memory system of claim 9, wherein each of the predetermined number of mapping table pieces is a same size.

12. The non-volatile memory system of claim 11, wherein the same size comprises a same number of logical block addresses.

13. The non-volatile memory system of claim 10, wherein to determine the block address entropy value for the open block, the processor is configured to generate a logical block address (LBA) range data structure in the volatile memory for the open block, wherein the LBA range data structure comprises a plurality of entries, each of the plurality of entries associated with a respective predetermined portion of a complete logical address range of the non-volatile memory system.

14. The non-volatile memory system of claim 13, wherein each of the plurality of entries corresponds to a LBA range of a different one of the predetermined number of mapping pieces.

15. The non-volatile memory system of claim 10, wherein the processor is further configured to generate a bit map for each open block in the non-volatile memory, the bit map having a predetermined number of entries each representing a logical address range of a different one of the predetermined mapping address table pieces, and to mark each entry of the predetermined number of entries corresponding to data written to a respective open block.

16. The non-volatile memory system of claim 9, wherein the non-volatile memory comprises a substrate formed with a three-dimensional memory structure.

17. A method of tracking block address entropy in a non-volatile memory system comprising:

receiving data at a non-volatile memory having a plurality of blocks;

storing the received data in a block of the plurality of blocks;

marking logical ranges of the received data in predetermined logical range entries of a logical block address range data structure associated with the block, each predetermined logical range entry corresponding to a different piece of a mapping table for the non-volatile memory system;

determining a block address entropy value for the block, wherein the block address entropy value comprises a sum of different predetermined logical range entries marked for the block in the logical block address range data structure; and

in response to fully programming the block, storing the determined block address entropy value and deleting the logical block address range data structure associated with the block.

18. The method of claim 17, further comprising, in response to detecting a number of free blocks in the non-volatile memory falling below a predetermined threshold:

determining a source block for a garbage collection operation in the non-volatile memory based at least in part on block address entropy values for each fully programmed block of the non-volatile memory; and

copying only valid data from the determined source block to an open block in the volatile memory.

19. The method of claim 17, wherein the plurality of blocks of the non-volatile memory comprise a first portion of blocks having a first block type and a second portion of blocks having a second block type, further comprising:

determining an average block address entropy value for all fully programmed blocks of the first block type; and

when the average block address entropy value for all fully programmed blocks of the first block type is above a predetermined value, routing subsequently received data to blocks of the second block type in the non-volatile memory.

20. The method of claim 19, wherein the first block type is a single level cell (SLC) block type and the second block type is a multi-level cell (MLC) block type.

21. A non-volatile memory system comprising:

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

means for receiving data from a host and storing the received data in an open block of the non-volatile memory; and

means for storing logical block address (LBA) range data exclusively for the open block and for updating the LBA range data only when an LBA range of the received data contains data associated with a host LBA falling in one of a predetermined number of LBA ranges for a first time in the open block.