Solid-state storage device with multi-level addressing

• US 8,566,511 B2
• Filed: 07/23/2010
• Issued: 10/22/2013
• Est. Priority Date: 07/23/2009
• Status: Active Grant

• Current Assignee: Sandisk Technologies Incorporated (Western Digital Corporation)
• Original Assignee: STEC Incorporated (Western Digital Corporation)
• Inventors: Moshayedi, Mark, Tootoonchian, Mohammadali
• Primary Examiner(s): Rojas, Midys
• Application Number:
  US12/842,950
• Publication Number:
  US 20120239855A1
• Time in Patent Office: 1,187 Days
• Field of Search: 711/103, 711/203, 711/205, 711/206, 711/207, 711/E12.014, 711/E12.058, 711/E12.059
• US Class Current: 711/103
• 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

Abstract

A solid-state storage device with multi-level addressing is provided. The solid-state storage device includes a plurality of flash memory devices, a volatile memory, and a controller. The controller is configured to store data received from a host in the plurality of flash memory devices in response to a write command and to read the data stored in the plurality of flash memory devices in response to a read command. The controller is further configured to maintain a multi-level address table that maps logical addresses received from the host identifying the data stored in the plurality of flash memory devices to physical addresses in the plurality of flash memory devices containing the data. A first level of the multi-level address table is maintained by the controller in the volatile memory and second and third levels of the multi-level address table are maintained by the controller in the plurality of flash memory devices.

Claims

1. A solid-state storage device comprising:

a plurality of flash memory devices;

a volatile memory; and

a controller configured to store data received from a host in the plurality of flash memory devices in response to a write command and to read the data stored in the plurality of flash memory devices in response to a read command,

wherein the controller is further configured to maintain a multi-level address table that maps logical addresses received from the host identifying the data stored in the plurality of flash memory devices to physical addresses in the plurality of flash memory devices containing the data, and

wherein a first level of the multi-level address table is maintained by the controller in the volatile memory and second and third levels of the multi-level address table are maintained by the controller in the plurality of flash memory devices.

2. The solid-state storage device according to claim 1, wherein the first level of the multi-level address table maps to the second level of the multi-level address table based on a first parameter of the logical addresses, the second level of the multi-level address table maps to the third level of the multi-level address table based on a second parameter of the logical addresses, and the third level of the multi-level address table maps to the physical addresses in the plurality of flash memory devices containing the data based on a third parameter of the logical addresses.

3. The solid-state storage device according to claim 2, wherein the first level of the multi-level address table comprises a first table, the second level of the multi-level address table comprises a plurality of second tables, and the third level of the multi-level address table comprises a plurality of third tables, and

wherein each entry in the first table maps to a respective one of the plurality of second tables, and each entry in each of the plurality of second tables maps to a respective subset of the plurality of third tables.

4. The solid-state storage device according to claim 3, wherein the controller is further configured to determine the first, second, and third parameters of the logical addresses.

5. The solid-state storage device according to claim 1, wherein the volatile memory is embedded in the controller.

6. The solid-state storage device according to claim 1, wherein the volatile memory is dynamic random access memory.

7. A method for mapping a plurality of logical addresses received from a host to a plurality of physical addresses in a flash memory device, the method comprising:

determining in a controller a first parameter, a second parameter, and a third parameter from a logical address;

mapping the first parameter of the logical address to a first address in a first table stored in a volatile memory;

reading a second table from a flash memory device based on the first address;

mapping the second parameter of the logical address to a second address in the second table;

reading a third table from the flash memory device based on the second address; and

mapping the third parameter of the logical address to a third address in the third table, wherein the third address is a physical address in the flash memory device containing data associated with the logical address.

8. The method according to claim 7, further comprising extracting in the controller a first plurality of values from the first address,

wherein the second table is read from the flash memory based on the first plurality of values extracted from the first address.

9. The method according to claim 8, wherein the first plurality of values comprises a first block value, a first page value, and a first sector value.

10. The method according to claim 8, further comprising extracting in the controller a second plurality of values from the second address,

wherein the third table is read from the flash memory based on the second plurality of values extracted from the second address.

11. The method according to claim 10, wherein the second plurality of values comprises a second block value, a second page value, and a second sector value.

12. The method according to claim 7, wherein the first table comprises a plurality of first addresses, each of the plurality of first addresses corresponding to a respective one of a plurality of second tables in the flash memory device,

wherein each of the plurality of second tables comprises a plurality of second addresses, each of the plurality of second addresses corresponding to a respective one of a plurality of third tables in the flash storage device, and

wherein each of the plurality of third tables comprises a plurality of third addresses, each of the third addresses corresponding to a respective one of a plurality of physical addresses in the flash memory device containing data associated with respective logical addresses.

13. The method according to claim 12, wherein each of the plurality of second tables comprises sixty-four second addresses.

14. The method according to claim 13, wherein each of the plurality of third tables comprises eight third addresses.

15. The method according to claim 12, wherein determining the first parameter comprises the controller performing integer division on the logical address with the product of the number of second addresses in each of the plurality of second tables and the number of third addresses in each of the plurality of third tables.

16. The method according to claim 15, wherein determining the second parameter comprises the controller performing a modulo operation on the logical address with the number of second addresses in each of the plurality of second tables.

17. The method according to claim 16, wherein determining the third parameter comprises the controller performing a modulo operation on the logical address with the number of third addresses in each of the plurality of third tables.

18. A non-transitory processor-readable medium containing executable instructions for mapping a plurality of logical addresses received from a host to a plurality of physical addresses in a flash memory device, the executable instructions comprising code for:

determining a first parameter, a second parameter, and a third parameter from a logical address;

mapping the first parameter of the logical address to a first address in a first table stored in a volatile memory;

reading a second table from a flash memory device based on the first address;

mapping the second parameter of the logical address to a second address in the second table;

reading a third table from the flash memory device based on the second address; and

mapping the third parameter of the logical address to a third address in the third table, wherein the third address is a physical address in the flash memory device containing data associated with the logical address.

19. The non-transitory processor-readable medium according to claim 18, further comprising code for extracting a first plurality of values from the first address,

wherein the second table is read from the flash memory based on the first plurality of values extracted from the first address.

20. The non-transitory processor-readable medium according to claim 19, further comprising code for extracting a second plurality of values from the second address,

wherein the third table is read from the flash memory based on the second plurality of values extracted from the second address.