System and method for supporting atomic writes in a flash translation layer

• US 9,772,781 B2
• Filed: 11/27/2013
• Issued: 09/26/2017
• Est. Priority Date: 11/27/2013
• Status: Active Grant

• Current Assignee: NGD Systems, Inc.
• Original Assignee: NGD Systems, Inc.
• Inventors: Salessi, Nader, Alcantara, Joao
• Primary Examiner(s): Savla, Arpan P.
• Application Number:
  US14/092,821
• Publication Number:
  US 20150149697A1
• Time in Patent Office: 1,399 Days
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 12/0292 using tables or multilevel address translation means G06F12/023 takes precedence; address translation in virtual memory systems G06F12/10
• CPC Class Codes: G06F 12/1009 using page tables, e.g. page table structures
• 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 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0644 Management of space entities, e.g. partitions, extents, pools
• CPC Class Codes: G06F 3/065 Replication mechanisms
• CPC Class Codes: G06F 3/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]

Abstract

A method of maintaining and updating a logical-to-physical (LtoP) table in a storage device including a processor, a volatile memory, and a non-volatile memory, the storage device being in communication with a host utilizing atomic writes, the method including receiving, by the processor, data for storing at a plurality of physical addresses in the non-volatile memory, the data being associated with a plurality of logical addresses of the host, storing, by the processor, the plurality of physical addresses in an atomic segment in the volatile memory, storing, by the processor, one or more of zones of the LtoP table in the non-volatile memory, the one or more zones of the LtoP table corresponding in size to the atomic segment, and updating the one or more zones of the LtoP table with the plurality of physical addresses in the atomic segment.

Claims

1. A method of maintaining and updating a logical-to-physical (LtoP) table in a storage device comprising a processor, a volatile memory, and a non-volatile memory, the storage device being in communication with a host utilizing atomic writes, the method comprising:

in response to receiving and storing first data at the non-volatile memory, updating, by the processor, a first subset of zones of the LtoP table corresponding to the stored first data, each zone of the first subset of zones mapping physical addresses of stored first data at the non-volatile memory with corresponding logical addresses of the host;

receiving, by the processor, second data for storing at a plurality of physical addresses in the non-volatile memory, the second data being associated with a plurality of logical addresses of the host;

storing, by the processor, the plurality of physical addresses in an atomic LtoP segment in the volatile memory;

after receiving the second data, storing, by the processor, the first subset of zones of the LtoP table in the non-volatile memory; and

in response to the storing of the first subset of zones, updating, by the processor, a second subset of zones of the LtoP table with the plurality of physical addresses in the atomic LtoP segment, the second subset of zones corresponding in size to the atomic LtoP segment, and the second subset of zones having a number of zones that is equal to or greater than that of the first subset of zones.

2. The method of claim 1, further comprising:

after the receiving of the second data, storing, by the processor, the second data at the plurality of physical addresses in the volatile memory.

3. The method of claim 1, wherein each physical address of the plurality of the physical addresses is associated with a different logical address of the plurality of logical addresses.

4. The method of claim 1, wherein each zone of the second subset of zones of the LtoP table comprises two or more physical addresses of the plurality of physical addresses and associated two or more logical addresses of the plurality of logical addresses.

5. The method of claim 1, wherein the first subset of zones of the LtoP table are least used dirty zones of the LtoP table.

6. The method of claim 1, wherein the LtoP table is stored in the volatile memory.

7. The method of claim 1, wherein the storing of the first subset of zones of the LtoP table in the non-volatile memory occurs before the storing of the plurality of physical addresses in the atomic LtoP segment.

8. The method of claim 1, wherein the storing of the first subset of zones of the LtoP table in the non-volatile memory comprises storing each of the one or more zones of the LtoP table in a data structure comprising a zone number and a zone information.

9. The method of claim 1, wherein the first subset of zones of the LtoP table comprise two or more zones of the LtoP table and are contiguous and sequential.

10. A storage device configured to maintain and update a logical-to-physical (LtoP) table in a storage device being in communication with a host utilizing atomic writes, the storage device comprising:

a processor; and

a memory comprising a volatile memory and a non-volatile memory, wherein the memory has stored thereon instructions that, when executed by the processor, cause the processor to perform;

in response to receiving and storing first data at the non-volatile memory, updating, by the processor, a first subset of zones of the LtoP table corresponding to the stored first data, each zone of the first subset of zones mapping physical addresses of stored first data at the non-volatile memory with corresponding logical addresses of the host;

receiving second data for storing at a plurality of physical addresses in the non-volatile memory, the second data being associated with a plurality of logical addresses of the host;

storing the plurality of physical addresses in an atomic LtoP segment in the volatile memory;

after receiving the second data, storing the first subset of zones of the LtoP table in the non-volatile memory; and

in response to the storing of the first subset of zones, updating a second subset of zones of the LtoP table with the plurality of physical addresses in the atomic LtoP segment, the second subset of zones corresponding in size to the atomic LtoP segment, and the second subset of zones having a number of zones that is equal to or greater than that of the first subset of zones.

11. The storage device of claim 10, wherein the executed instructions further cause the processor to perform:

after the receiving of the second data, storing, by the processor, the second data at the plurality of physical addresses in the volatile memory.

12. The storage device of claim 10, wherein each physical address of the plurality of the physical addresses is associated with a different logical address of the plurality of logical addresses.

13. The storage device of claim 10, wherein each zone of the second subset of zones of the LtoP table comprises two or more physical addresses of the plurality of physical addresses and associated two or more logical addresses of the plurality of logical addresses.

14. The storage device of claim 10, wherein the first subset of zones of the LtoP table are least used dirty zones of the LtoP table.

15. The storage device of claim 10, wherein the LtoP table is stored in the volatile memory.

16. The storage device of claim 10, wherein the storing of the first subset of zones of the LtoP table in the non-volatile memory occurs before the storing of the plurality of physical addresses in the atomic LtoP segment.

17. The storage device of claim 10, wherein the storing of the first subset of zones of the LtoP table in the non-volatile memory comprises storing each of the one or more zones of the LtoP table in a data structure comprising a zone number and a zone information.