Systems and methods for read caching in flash storage

• US 9,223,702 B2
• Filed: 08/11/2014
• Issued: 12/29/2015
• Est. Priority Date: 05/12/2009
• Status: Active Grant

• Current Assignee: Sandisk Technologies Incorporated (Western Digital Corporation)
• Original Assignee: HGST Technologies Santa Ana, Inc. (Western Digital Corporation)
• Inventors: Hsueh, Po-Jen, Mataya, Richard A., Moshayedi, Mark
• Primary Examiner(s): Rossiter, Sean D
• Application Number:
  US14/457,077
• Publication Number:
  US 20140351498A1
• Time in Patent Office: 505 Days
• Field of Search: None
• US Class Current: 1/1
• 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 controller receives a read request for reading a page of data from the flash memory from a host system, and identifies, in a cache tag table stored in the random access memory, a virtual unit address associated with the page of data. In response to identifying the virtual unit address in the cache tag table, controller determines whether a valid tag line for the page of data is associated with the virtual unit address in the cache tag table. In response to determining that the valid tag line is associated with the virtual unit address in the cache tag table, the controller reads the page of data from the random access memory in accordance with the read request and returns the read data to the host system.

Claims

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

receiving a read request for reading a page of data from a non-volatile memory;

identifying, in a cache tag table stored in a cache memory different from the non-volatile memory, a virtual unit address associated with the page of data;

in response to identifying the virtual unit address in the cache tag table, determining whether, in a sub-table of the cache tag table, a valid tag line for the page of data is associated with the virtual unit address, the valid tag line indicating that the page of data includes valid data; and

in response to determining that the valid tag line is associated with the virtual unit address in the cache tag table, reading the page of data from the cache memory in accordance with the read request.

2. The method of claim 1, wherein the cache tag table comprises a plurality of sub-tables for locating virtual pages stored in the cache memory based on respective virtual page addresses, each sub-table being associated with a respective virtual unit address.

3. The method of claim 1, wherein the valid tag line is indexed by a virtual page address for the page of data.

4. The method of claim 1, further comprising, in response to not determining that the valid tag line is associated with the virtual unit address in the cache tag table:

reading the page of data from the non-volatile memory;

storing the page of data in the cache memory; and

associating the valid to line with the virtual unit address in the cache tag table.

5. The method of claim 1, wherein a maximum number of valid tag lines associated with a respective virtual unit address in the cache tag table is less than a total number of virtual pages in a virtual unit corresponding to the virtual unit address.

6. The method of claim 5, further comprising:

when the maximum number of valid tag lines are associated with the respective virtual unit address, invalidating one or more of the valid tag lines before associating another valid tag line with the respective virtual unit address.

7. The method of claim 6, wherein invalidating one or more of the valid tag lines comprises invalidating a tag line associated with a least recently used virtual page address.

8. The method of claim 1, further comprising:

determining if a valid tag line for a virtual page address associated with a write command is in the cache tag table;

in response to determining the valid tag line for the virtual page address associated with the write command is in the cache tag table, invalidating the valid tag line for the virtual page address.

9. The method of claim 1, further comprising:

writing one or more new pages of data to the non-volatile memory;

writing the one or more new pages of data to the cache memory; and

associating valid tag lines for the one or more new pages of data with a corresponding virtual unit address in the cache tag table.

10. The method of claim 1, further comprising:

mapping a host logical address in the read request to the virtual it address and a virtual. page address for the page of data.

14. The system of claim 1, wherein a maximum number of valid tag lines associated with a respective virtual unit address in the cache tag table is less than a total number of virtual pages in a virtual unit corresponding to the virtual unit address.

15. The system of claim 14, wherein the controller is further configured to:

when the maximum number of valid tag lines are associated with the respective virtual unit address, invalidating one or more of the valid tag lines before associating another valid tag line with the respective virtual unit address.

16. The system of claim 15, wherein invalidating one or more of the valid tag lines comprises invalidating a tag line associated with a least recently used virtual page address.

11. A system, comprising:

a random access 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;

receive a read request for reading a page of data from the flash memory;

identify, in a cache tag table stored in the random access memory, a virtual unit address associated with the page of data;

in response to identifying the virtual unit address in the cache tag table, determine whether, in a sub-table of the cache tag table, a valid tag line for the page of data is associated with the virtual unit address, the valid tag line being indexed by a virtual page address for the page of data and indicating that the page of data includes valid data; and

in response to determining that the valid tag line is associated with the virtual unit address in the cache tag table, read the page of data from the random access memory in accordance with the read request.

13. The system of claim 11, wherein the controller is further configured to, in response to not determining that the valid tag line is associated with the virtual unit address in the cache tag table:

reading the page of data from the flash memory;

storing the page of data in the random access memory; and

associating the valid tag line with the virtual unit address in the cache tag table.

17. The system of claim 11, wherein the controller is further configured to:

determining if a valid tag line for a virtual page address associated with a write command is in the cache tag table;

in response to determining the valid tag line for the virtual page address associated with the write command is in the cache tag table, invalidating the valid tag line for the virtual page address.

18. The system of claim 11, wherein the controller is further configured to:

writing one or more new pages of data to the flash memory;

writing the one or more new pages of data to the random access memory; and

associating valid tag lines for the one or more new pages of data with a corresponding virtual unit address in the cache tag table.

12. The system of claim lit wherein the cache tag table comprises a plurality of sub-tables for locating virtual pages stored in the random access memory based on respective virtual page addresses, each sub-table being associated with a respective virtual unit address.

19. A flash controller, comprising non-transitory instructions stored therein that, when executed by the controller, perform the operations of:

receiving a read request for reading a page of data from a one or more flash memory devices;

identifying, in a cache tag table stored in a cache memory different from the flash memory, a virtual unit address associated with the page of data;

in response to identifying the virtual unit address in the cache tag table, determining whether, in a sub-table of the cache tag table, a valid tag line for the page of data is associated with the virtual unit address, the valid tag line being indexed by a virtual page address for the page of data and indicating that the page of data includes valid data; and

in response to determining that the valid tag line is associated with the virtual unit address in the cache tag table, reading the page of data from the cache memory in accordance with the read request.

20. The flash controller of claim 19, wherein the cache tag table comprises a plurality of sub-tables for locating virtual pages stored in the cache memory based on respective virtual page addresses, each sub-table being associated with a respective virtual unit address.