FLASH STORAGE DEVICE WITH READ CACHE

• US 20120239854A1
• Filed: 05/12/2010
• Published: 09/20/2012
• Est. Priority Date: 05/12/2009
• Status: Active Grant

• Current Assignee: Sandisk Technologies Incorporated (Western Digital Corporation)
• Original Assignee: STEC Incorporated (Western Digital Corporation)
• Inventors: MOSHAYEDI, Mark, HSUEH, Po-Jen, MATAYA, Richard A.
• Granted Patent: US 8,806,144 B2
• Time in Patent Office: Days
• US Class Current: 711/103
• CPC Class Codes: G06F 11/076 by exceeding a count or rate limit, e.g. word- or bit count limit
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 12/0284 Multiple user address space allocation, e.g. using different base addresses interprocessor communication G06F15/163
• CPC Class Codes: G06F 12/0833 in combination with broadcast means (e.g. for invalidation or updating)
• CPC Class Codes: G06F 12/0866 for peripheral storage systems, e.g. disk cache
• 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/466 Metadata, control data
• CPC Class Codes: G06F 2212/62 Details of cache specific to multiprocessor cache arrangements
• CPC Class Codes: G06F 2212/7208 Multiple device management, e.g. distributing data over multiple flash devices
• CPC Class Codes: G06F 2212/7209 Validity control, e.g. using flags, time stamps or sequence numbers
• CPC Class Codes: G11C 16/3418 Disturbance prevention or evaluation; Refreshing of disturbed memory data
• CPC Class Codes: G11C 16/349 Arrangements for evaluating degradation, retention or wearout, e.g. by counting erase cycles

Abstract

A flash storage device includes a first memory, a flash memory comprising a plurality of physical blocks, each of the plurality of physical blocks comprising a plurality of physical pages, and a controller. The controller is configured to store, in the first memory, copies of data read from the flash memory, map a logical address in a read request received from a host system to a virtual unit address and a virtual page address, and check a virtual unit cache tag table stored in the first memory based on the virtual unit address. If a hit is found in the virtual unit cache tag table, a virtual page cache tag sub-table stored in the first memory is checked based on the virtual page address, wherein the virtual page cache tag sub-table is associated with the virtual unit address. If a hit is found in the virtual page cache tag sub-table, data stored in the first memory mapped to the hit in the virtual page cache tag sub-table is read in response to the read request received from the host system.

Claims

1. A method of managing a flash storage device, the method comprising:

storing, in a first memory, copies of data read from a flash memory in the flash storage device;

mapping a logical address in a read request received from a host system to a virtual unit address and a virtual page address;

checking a virtual unit cache tag table in the first memory based on the virtual unit address;

if a hit is found in the virtual unit cache tag table, checking a virtual page cache tag sub-table in the first memory based on the virtual page address, wherein the virtual page cache tag sub-table is associated with the virtual unit address;

if a hit is found in the virtual page cache tag sub-table, reading data stored in the first memory mapped to the hit in the virtual page cache tag sub-table in response to the read request received from the host system.

2. The method of claim 1, wherein if a hit is not found in the virtual page cache tag sub-table the method further comprises:

reading data stored in a physical block and a physical page in the flash memory mapped to the virtual unit address and the virtual page address, respectively, in response to the read request;

storing a copy of the read data in the first memory; and

updating the virtual page cache tag sub-table.

3. The method of claim 2, wherein updating the virtual page cache tag sub-table comprises mapping a tag in the virtual page cache tag sub-table corresponding to the virtual page address to the location of the read data in the first memory.

4. The method of claim 3, wherein a number of tags in the virtual page cache tag sub-table mapped to locations of data in the first memory is less than a total number of tags in the virtual page cache tag sub-table.

5. The method of claim 3, wherein if a number of tags in the virtual page cache tag sub-table mapped to locations of data in the first memory is equal to a first threshold value, updating the virtual page cache tag sub-table further comprises invalidating one of the tags in the virtual page cache tag sub-table.

6. The method of claim 5, wherein the invalidated tag is selected according to a first replacement policy.

7. The method of claim 1, wherein if a hit is not found in the virtual unit cache tag table the method further comprises:

reading data stored in a physical block and a physical page in the flash memory mapped to the virtual unit address and the virtual page address, respectively, in response to the read request;

storing a copy of the read data in the first memory; and

updating the virtual unit cache tag table and the virtual page cache tag sub-table associated with the virtual unit address.

8. The method of claim 7, wherein updating the virtual unit cache tag table comprises creating a tag corresponding to the virtual unit address in the virtual unit cache tag table and a virtual page cache tag sub-table associated with the virtual unit address.

9. The method of claim 8, wherein the number of tags in the virtual unit cache tag table is less than a total number of virtual unit addresses mapped to physical blocks in the flash memory.

10. The method of claim 8, wherein if a number of tags in the virtual unit cache tag table is equal to a second threshold value, updating the virtual unit cache tag table further comprises removing one of the tags from the virtual unit cache tag table.

11. The method of claim 10, wherein the tag removed from the virtual unit cache tag table is selected according to a second replacement policy.

12. A flash storage device comprising:

a first memory;

a flash memory comprising a plurality of physical blocks, each of the plurality of physical blocks comprising a plurality of physical pages;

a controller, wherein the controller is configured to;

store, in the first memory, copies of data read from the flash memory;

map a logical address in a read request received from a host system to a virtual unit address and a virtual page address;

check a virtual unit cache tag table stored in the first memory based on the virtual unit address;

if a hit is found in the virtual unit cache tag table, check a virtual page cache tag sub-table stored in the first memory based on the virtual page address, wherein the virtual page cache tag sub-table is associated with the virtual unit address;

if a hit is found in the virtual page cache tag sub-table, read data stored in the first memory mapped to the hit in the virtual page cache tag sub-table in response to the read request received from the host system.

13. The flash storage device of claim 12, wherein if a hit is not found in the virtual page cache tag sub-table the controller is further configured to:

read data stored in one of the plurality of physical blocks and one of the plurality of physical pages in the flash memory mapped to the virtual unit address and the virtual page address, respectively, in response to the read request;

store a copy of the read data in the first memory; and

update the virtual page cache tag sub-table.

14. The flash storage device of claim 13, wherein the controller is configured to update the virtual page cache tag sub-table by mapping a tag in the virtual page cache tag sub-table to the location of the read data in the first memory.

15. The flash storage device of claim 14, wherein a number of tags in the virtual page cache tag sub-table mapped to locations of data in the first memory is less than a total number of tags in the virtual page cache tag sub-table.

16. The flash storage device of claim 14, wherein if a number of tags in the virtual page cache tag sub-table mapped to locations of data in the first memory is equal to a first threshold value, the controller is configured to invalidate one of the tags in the virtual page cache tag sub-table.

17. The flash storage device of claim 16, wherein the controller is configured to select the invalidated tag in the virtual page cache tag sub-table according to a first replacement policy.

18. The flash storage device of claim 12, wherein if a hit is not found in the virtual unit cache tag table the controller is further configured to:

read data stored in one of the plurality of physical blocks and one of the plurality of physical pages in the flash memory mapped to the virtual unit address and the virtual page address, respectively, in response to the read request;

store a copy of the read data in the first memory; and

update the virtual unit cache tag table and the virtual page cache tag sub-table associated with the virtual unit address.

19. The flash storage device of claim 18, wherein the controller is configured to update the virtual unit cache tag table by creating a tag corresponding to the virtual unit address in the virtual unit cache tag table and a virtual page cache tag sub-table associated with the virtual unit address.

20. The flash storage device of claim 19, wherein the number of tags in the virtual unit cache tag table is less than a total number of virtual unit addresses mapped to physical blocks in the flash memory.

21. The flash storage device of claim 19, wherein if a number of tags in the virtual unit cache tag table is equal to a second threshold value, the controller is configured to remove one of the tags from the virtual unit cache tag table.

22. The flash storage device of claim 21, wherein the controller is configured to select the tag removed from the virtual unit cache tag table according to a second replacement policy.

23. The flash storage device of claim 12, wherein the first memory comprises a dynamic random access memory.