System and method for managing data in non-volatile memory systems having multiple mapping layers

Patent metadata

Field	Value
Publication number	US-10459636-B2
Application number	US-201715468801-A
Country	US
Kind code	B2
Filing date	Mar 24, 2017
Priority date	Mar 24, 2017
Publication date	Oct 29, 2019
Grant date	Oct 29, 2019

Abstract

A system and method is described for managing mapping data in a non-volatile memory system having a volatile memory cache smaller than the update table for the mapping data. The system includes multiple mapping layers, for example two mapping layers, including a master mapping table of logical-to-physical mapping entries and an update table of mapping updates, for a non-volatile memory. A processor swaps predetermined size portions of the update mapping table and master mapping table into and out of the volatile memory cache based on host workload. The update mapping table portions may have a fixed or an adaptive logical range. Additional mapping layers, such as an expanded mapping layer having portions with a logical range greater than the logical range of the update mapping portions, may also be included and may be swapped into and out of the volatile memory with the master and update mapping table portions.

First claim

We claim:

1. A non-volatile memory system comprising:
a non-volatile memory;
a volatile memory having a fixed-size mapping table cache; and
a controller in communication with the volatile memory and the non-volatile memory, the controller configured to:
store a master mapping table of logical to physical address mapping data for data in the non-volatile memory, the master mapping table having a predetermined size and divided into a plurality of master mapping table sets;
store, in the non-volatile memory, an update mapping table of logical to physical address mapping data, the update mapping table having updated logical to physical mapping data not yet written into the master mapping table, the update mapping table divided into a plurality of update mapping table sets each having a same physical size as a master mapping table set, wherein a size of the fixed-size mapping table cache of the volatile memory is less than a size of the update mapping table; and
swap a portion of the update mapping table sets between the non-volatile memory and the volatile memory based on a workload of the non-volatile memory system.

2. The non-volatile memory system of claim 1 , wherein in response to receiving a host command relating to a logical block address (LBA), the controller is configured to:
determine if the LBA associated with the host command is in any master mapping table set or update mapping table set currently in the volatile memory; and
when the LBA is not found in any master mapping table set or update mapping table set currently in the volatile memory:
retrieve a master mapping table set corresponding to the LBA and an update mapping table set corresponding to the LBA from the non-volatile memory; and
store the master mapping table set and the update mapping table set corresponding to the LBA in the volatile memory.

3. The non-volatile memory system of claim 2 , wherein the controller is further configured to, when there is insufficient free space available in the mapping table cache of the volatile memory to store a master mapping table set or update mapping table set corresponding to the LBA associated with the host command, select one or more master mapping table sets or update mapping table sets to remove from the volatile memory prior to loading the master mapping table set or updated mapping table set associated with the LBA.

4. The non-volatile memory system of claim 3 , wherein to select one or more master mapping table sets or update mapping table sets to remove from the volatile memory the controller is configured to: select a master mapping table set having a greatest number of updates since last being retrieved from the non-volatile memory; and update the master mapping table in the non-volatile memory with all updates in the selected master mapping table set.

5. The non-volatile memory system of claim 1 , wherein in response to receiving a write request relating to a logical block address (LBA), the controller is further configured to:
when a master mapping table set associated with the LBA is already stored in the volatile memory, update in the volatile memory the master mapping table set associated with the LBA.

6. The non-volatile memory system of claim 5 , wherein when the master mapping table set associated with the LBA is not already stored in the volatile memory, the controller is further configured to:
when an update mapping table set associated with the LBA is already stored in the volatile memory, update in the volatile memory the update mapping table set associated with the LBA.

7. The non-volatile memory system of claim 5 , wherein when neither a master mapping table set associated with the LBA nor an update mapping table set associated with the LBA is already stored in the volatile memory, the controller is configured to:
load a master mapping table set and an update mapping table set corresponding to the LBA into the volatile memory from the non-volatile memory; and
update the master mapping table set and update mapping table set for associated with the LBA in the volatile memory.

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

9. A non-volatile memory system comprising:
a non-volatile memory;
a volatile memory having a fixed-size mapping table cache; and
a controller in communication with volatile memory and the non-volatile memory, the controller configured to:
store a master mapping table of logical to physical address mapping data for data in the non-volatile memory, the master mapping table having a predetermined size and divided into a plurality of master mapping table sets;
store, in the non-volatile memory, an update mapping table of logical to physical address mapping data, the update mapping table having updated logical to physical mapping data not yet written into the master mapping table, the update mapping table divided into a plurality of update mapping table sets each having a same physical size as a master mapping table set, wherein a size of the fixed-size mapping table cache of the volatile memory is less than a size of the update mapping table; and
swap a portion of the update mapping table sets between the non-volatile memory and the volatile memory based on a workload of the non-volatile memory system,
wherein each of the plurality of master mapping table sets has a same physical size and a same range length of logical block addresses (LBAs); and
wherein each of the plurality of update mapping table sets has a same physical size as each of the plurality of master mapping table sets, but has a greater range length of LBAs than each of the master mapping table sets.

10. The non-volatile memory system of claim 9 , wherein each master mapping layer set comprises a direct access mapping of sequentially numbered logical block addresses to any physical block addresses associated with each of the sequentially numbered LBAs.

11. The non-volatile memory system of claim 10 , wherein each update mapping table set comprises a plurality of regions, where each region is exclusively associated with a sequential LBA range of a different master mapping table set, and where each of the plurality of regions of each update mapping table set is configured to store only a limited number of mapping update entries.

12. The non-volatile memory system of claim 11 , wherein each update entry is configured to receive a LBA start address, a physical block address (PBA) start address and a data length for a contiguous run of data associated with the LBA start address.

13. The non-volatile memory system of claim 9 , wherein each of the plurality of update mapping sets comprises a first fixed range length of LBAs that is an integer multiple of the range length of LBAs in each of the master mapping table sets.

14. The non-volatile memory system of claim 9 , wherein the controller is further configured to, in response to detecting a merger criteria:
merge a first update mapping set in the mapping table cache associated with a first LBA range and a second update mapping set in the mapping table cache associated with a second LBA range into an adaptive update mapping set;
wherein the merger criteria comprise the first LBA range being sequential to the second LBA range and the first and second update mapping sets each having less than a threshold fullness.

15. A method of managing mapping data in a non-volatile memory system, the non-volatile memory system having a non-volatile memory and a controller in communication with the non-volatile memory, the method comprising the controller:

Assignees

• Sandisk Technologies Llc

Inventors

• Frid Marina
• Genshaft Igor

Classifications

• G06F3/0688

  Non-volatile semiconductor memory arrays · CPC title

• G06F3/061 Primary

  Improving I/O performance · CPC title

• G06F2212/7201

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

• G06F12/0246

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

• G06F3/0655

  Vertical data movement, i.e. input-output transfer; data movement between one or more hosts and one or more storage devices · CPC title