Method and system for dynamic compression of address tables in a memory

Patent metadata

Field	Value
Publication number	US-9229876-B2
Application number	US-201414274310-A
Country	US
Kind code	B2
Filing date	May 9, 2014
Priority date	Dec 17, 2013
Publication date	Jan 5, 2016
Grant date	Jan 5, 2016

Abstract

A method and system are disclosed for handling logical-to-physical mapping and increasing the amount of mapping table information that may be stored in a cache in volatile memory. The method includes the storage device storing in fast access memory, such as RAM, a copy of only a portion of the complete mapping information for non-volatile memory of the storage device using a compressed format by compressing the mapping data when a skip pattern of interleaved sequential writes to non-volatile memory are found in the mapping information. The system includes a storage device having volatile memory, non-volatile memory and a controller in communication with the volatile and non-volatile memory that is configured to carry out the method noted above.

First claim

What is claimed is:

1. A method of managing a memory device comprising:
in a memory device having a non-volatile memory, a volatile memory and a controller in communication with the non-volatile memory and the volatile memory, the controller:
receiving a host command identifying a logical block address for data stored in non-volatile memory of the memory device;
determining if mapping information regarding a physical address in the non-volatile memory associated with the logical block address resides in the volatile memory;
when no mapping information associated with the logical block address resides in the volatile memory:
retrieving a segment of mapping information from a logical-to-physical mapping structure in the non-volatile memory, the segment associated with the logical block address in the host command;
compressing the segment of mapping information into a compressed logical group address entry based on a logical address skip pattern in physical address entries associated in the segment; and
storing the compressed segment of mapping information in the volatile memory.

2. The method of claim 1 , wherein the logical address skip pattern comprises a plurality of groups of sequential runs of logical addresses associated with sequential physical addresses in a first row of the segment that is contiguous with a second plurality of groups of sequential runs of logical addresses associated with sequential physical addresses in a second row of the segment.

3. The method of claim 1 , wherein the segment comprises a portion having the logical address skip pattern and a portion without the logical address skip pattern, and wherein storing the compressed segment of mapping information comprises storing mapping information for the portion having the logical address skip pattern in a compressed format and storing the portion without the logical address skip pattern in an uncompressed format.

4. The method of claim 1 , wherein the segment comprises a portion having the logical address skip pattern and a portion without the logical address skip pattern, and wherein storing the compressed segment of mapping information comprises:
storing mapping information for the portion having the logical address skip pattern in a compressed format;
determining if the portion without the logical address skip pattern is compressible using a different compression method;
storing any of the portion without the logical address skip pattern that is compressible using the different compression method; and
storing in an uncompressed format any remainder of the portion without the skip pattern that is not compressible using the different compression format.

5. The method of claim 1 , wherein retrieving the segment of mapping information from the logical-to-physical mapping structure in the non-volatile memory comprises first determining if room is available in the volatile memory for the segment of mapping information and, if insufficient room is available, ejecting a previously retrieved segment of mapping information from the volatile memory prior to retrieving the segment of mapping information associated with the logical block address in the host command.

6. The method of claim 5 , wherein ejecting the previously retrieved segment comprises selecting the least recently used segment of mapping data in the volatile memory for ejection and erasing the least recently used segment from the volatile memory.

7. A memory device comprising:
a non-volatile memory;
a volatile memory; and
a controller in communication with the non-volatile memory and the volatile memory, wherein the controller is configured to:
receive a host command identifying a logical block address for data stored in non-volatile memory of the memory device;
determine if mapping information regarding a physical address in the non-volatile memory associated with the logical block address resides in the volatile memory;
when no mapping information associated with the logical block address resides in the volatile memory:
retrieve a segment of mapping information from a logical-to-physical mapping structure in the non-volatile memory, the segment associated with the logical block address in the host command;
compress the segment of mapping information into a compressed logical group address entry based on a logical address skip pattern in physical address entries associated in the segment; and
store the compressed segment of mapping information in the volatile memory.

8. The memory device of claim 7 , wherein the volatile memory comprises random access memory (RAM) and the non-volatile memory comprises flash memory.

9. The memory device of claim 8 , wherein the logical address skip pattern comprises a plurality of groups of sequential runs of logical addresses associated with sequential physical addresses in a first row of the segment that is contiguous with a second plurality of groups of sequential runs of logical addresses associated with sequential physical addresses in a second row of the segment.

10. The memory device of claim 9 , wherein the segment comprises a portion having the logical address skip pattern and a portion without the logical address skip pattern, and wherein to store the compressed segment of mapping information the controller is configured to store mapping information for the portion having the logical address skip pattern in a compressed format and store the portion without the logical address skip pattern in an uncompressed format.

11. The memory device of claim 7 , wherein the segment comprises a portion having the logical address skip pattern and a portion without the logical address skip pattern, and wherein to store the compressed segment of mapping information the controller is further configured to:
store mapping information for the portion having the logical address skip pattern in a compressed format;
determine if the portion without the logical address skip pattern is compressible using a different compression method;
store any of the portion without the logical address skip pattern that is compressible using the different compression method; and
store in an uncompressed format any remainder of the portion without the skip pattern that is not compressible using the different compression format.

12. The memory device of claim 11 , wherein the different compression method comprises a run-length compression method.

13. The memory device of claim 7 , wherein to retrieve the segment of mapping information from the logical-to-physical mapping structure in the non-volatile memory, the controller is configured to first determine if room is available in the volatile memory for the segment of mapping information and, if insufficient room is available, to eject a previously retrieved segment of mapping information from the volatile memory prior to retrieving the segment of mapping information associated with the logical block address in the host command.

14. The memory device of claim 7 , wherein the controller is configured to, in order to eject the previously retrieved segment, select the least recently used segment of mapping data in the volatile memory for ejection and erase the least recently used segment from the volatile memory.

Assignees

• Sandisk Technologies Inc

Inventors

• Slepon Raphael

Classifications

• G06F2212/7201

  Logical to physical mapping or translation of blocks or pages · CPC title

• G06F12/0246 Primary

  in block erasable memory, e.g. flash memory · CPC title

• G06F2212/657

  Virtual address space management · CPC title

• G06F3/061

  Improving I/O performance · CPC title

• G06F3/0679

  Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP] · CPC title