Solid state drive using two-level indirection architecture

• US 10,496,334 B2
• Filed: 05/04/2018
• Issued: 12/03/2019
• Est. Priority Date: 05/04/2018
• Status: Active Grant

• Current Assignee: JP Morgan Chase Bank, N.A. (JP Morgan Chase & Co)
• Original Assignee: Western Digital Technologies Incorporated (Western Digital Corporation)
• Inventors: Myran, Mark David, Mishra, Chandan, Gholamipour, Amir Hossein, Cometti, Aldo Giovanni, Yoo, Namhoon
• Primary Examiner(s): Patel, Kaushikkumar M
• Application Number:
  US15/971,869
• Publication Number:
  US 20190339904A1
• Time in Patent Office: 578 Days
• Field of Search: None
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 12/1009 using page tables, e.g. page table structures
• CPC Class Codes: G06F 2212/1008 Correctness of operation, e.g. memory ordering
• CPC Class Codes: G06F 2212/1024 Latency reduction
• CPC Class Codes: G06F 2212/214 Solid state disk
• CPC Class Codes: G06F 2212/222 Non-volatile memory
• CPC Class Codes: G06F 2212/466 Metadata, control data
• CPC Class Codes: G06F 2212/657 Virtual address space management
• CPC Class Codes: G06F 2212/7201 Logical to physical mapping or translation of blocks or pages
• CPC Class Codes: G06F 2212/7203 Temporary buffering, e.g. using volatile buffer or dedicated buffer blocks
• CPC Class Codes: G06F 3/0604 Improving or facilitating administration, e.g. storage management
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0659 Command handling arrangements, e.g. command buffers, queues, command scheduling
• CPC Class Codes: G06F 3/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]
• CPC Class Codes: G06F 3/0688 Non-volatile semiconductor memory arrays

Abstract

Aspects of the present disclosure provide systems and methods for operating a solid state drive (SSD) using two-level indirection architecture. The SSD receives a command to perform a data operation in a NAND array and a logical address for the data operation. The SSD then converts the logical address to a physical address using a two-stage logical-to-physical (L2P) mapping table that includes a first stage stored in a byte-rewritable memory and a second stage stored in a block-erasable non-volatile memory (NVM). The SSD performs the data operation in the NAND array based on the physical address. The byte-rewritable memory may any byte-rewritable persistent memory. The block-erasable low latency NVM may be a flash memory that has lower latency than NAND array.

Claims

1. A method of operating a solid state drive (SSD), comprising:

receiving a command to perform a data operation in a NAND array and a logical address for the data operation;

converting the logical address to a physical address using a two-stage logical-to-physical (L2P) mapping table comprising a partition table stored in a byte-rewritable non-volatile memory and a plurality of L2P table partitions stored in a block-erasable non-volatile memory (NVM) that has faster access than the NAND array; and

performing the data operation in the NAND array based on the physical address.

2. The method of claim 1,

wherein the converting comprises:

determining, using the partition table, a location in the block-erasable NVM storing the L2P table partition corresponding to the logical address for the data operation; and

determining, using the L2P table partition, the physical address for performing the data operation in the NAND array.

3. The method of claim 2, wherein the performing the data operation comprises:

programming second data, received as part of the command, to the NAND array to replace first data stored in the NAND array; and

updating the partition table and the L2P table partition to map the logical address to a physical address of the second data.

4. The method of claim 3, wherein the updating comprises:

updating an L2P entry in the L2P table partition to store the physical address of the second data; and

updating an entry in the partition table to store a new location of the updated L2P table partition.

5. The method of claim 1, wherein the command comprises, at least one of:

a program command for writing data to a page of the NAND array;

or

a read command for reading data from a page of the NAND array.

6. The method of claim 1, wherein:

the partition table comprises a plurality of partition indexes,

wherein each partition index indicates a location of a corresponding one of the L2P table partitions in the block-erasable NVM.

7. A solid state device (SSD) comprising:

a communication interface configured to communicate with a host;

a NAND array;

a byte-rewritable non-volatile memory;

a block-erasable non-volatile memory (NVM) that has faster access than the NAND array; and

a controller operatively coupled with the communication interface and the NAND array, wherein the controller is configured to;

receive, from the host, a command to perform a data operation in the NAND array and a logical address for the data operation;

convert the logical address to a physical address using a two-stage logical-to-physical (L2P) mapping table comprising a partition table stored in the byte-rewritable non-volatile memory and a plurality of L2P table partitions stored in the block-erasable NVM; and

perform the data operation in the NAND array based on the physical address.

8. The SSD of claim 7,

wherein the controller is further configured to:

determine, using the partition table, a location in the block-erasable NVM storing the L2P table partition corresponding to the logical address for the data operation; and

determine, using the L2P table partition, the physical address for performing the data operation in the NAND array.

9. The SSD of claim 8, wherein the controller is further configured to:

program second data, received as part of the command, to the NAND array to replace first data stored in the NAND array; and

update the partition table and the L2P table partition to map the logical address to a physical address of the second data.

10. The SSD of claim 9, wherein the controller is further configured to:

update an L2P entry in the L2P table partition to store the physical address of the second data; and

update an entry in the partition table to store a new location of the updated L2P table partition.

11. The SSD of claim 7, wherein the command comprises, at least one of:

a program command for writing data to a page of the NAND array;

or

a read command for reading data from a page of the NAND array.

12. The SSD of claim 7, wherein:

the partition table comprises a plurality of partition indexes,

and wherein each partition index indicates a location of a corresponding one of the L2P table partitions in the block-erasable NVM.

13. A solid state drive (SSD), comprising:

means for receiving a command to perform a data operation in a NAND array and a logical address for the data operation;

means for converting the logical address to a physical address using a two-stage logical-to-physical (L2P) mapping table comprising a partition table stored in a byte-rewritable non-volatile memory and a plurality of L2P table partitions stored in a block-erasable non-volatile memory (NVM) that has faster access than the NAND array; and

means for performing the data operation in the NAND array based on the physical address.

14. The SSD of claim 13,

wherein the means for converting is configured to:

determine, using the partition table a location in the block-erasable NVM storing the L2P table partition corresponding to the logical address for the data operation; and

determine, using the L2P table partition, the physical address for performing the data operation in the NAND array.

15. The SSD of claim 14, wherein the means for performing the data operation is configured to:

program second data to the NAND array to replace first data stored in the NAND array; and

update the partition table and the L2P table partition to map the logical address to a physical address of the second data.

16. The SSD of claim 15, wherein the means for performing the data operation is further configured to:

update an L2P entry in the L2P table partition to store the physical address of the second data; and

update an entry in the partition table to store a new location of the updated L2P table partition.

17. The SSD of claim 13, wherein the command comprises, at least one of:

a program command for writing data to a page of the NAND array;

or

a read command for reading data from a page of the NAND array.

18. The SSD of claim 13, wherein:

the partition table comprises a plurality of partition indexes,

wherein each partition index indicates a location of a corresponding one of the L2P table partitions in the block-erasable NVM.

19. A solid state drive (SSD) comprising:

a NAND array;

a byte-rewritable non-volatile memory;

a block-erasable non-volatile memory (NVM) that has faster access than the NAND array; and

a controller operatively coupled with the NAND array, the byte-rewritable non-volatile memory, and the block-erasable NVM,

wherein the controller is configured to;

store first data in the NAND array using a two-stage logical-to-physical (L2P) mapping table comprising a partition table and a plurality of table partitions;

store the partition table in the byte-rewritable non-volatile memory, the partition table comprising a plurality of indexes corresponding to the plurality of table partitions; and

store the plurality of table partitions in the block-erasable NVM, each table partition comprising a plurality of physical addresses of the NAND array mapped to logical addresses of the first data.

20. The SSD of claim 19, wherein the controller is further configured to:

store second data in the NAND array;

update one or more of the plurality of table partitions to store one or more physical addresses of the NAND array for storing the second data; and

update one or more indexes of the partition table corresponding to the updated one or more table partitions.

21. The SSD of claim 19, wherein the controller is further configured to:

cache one or more of the table partitions in the byte-rewritable non-volatile memory.