Apparatus, system, and method for caching data

• US 8,489,817 B2
• Filed: 08/12/2011
• Issued: 07/16/2013
• Est. Priority Date: 12/06/2007
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: Fusion-IO Incorporated (Western Digital Corporation)
• Inventors: Flynn, David, Atkisson, David, Aune, Joshua
• Primary Examiner(s): Gu, Shawn X
• Application Number:
  US13/209,007
• Publication Number:
  US 20120210041A1
• Time in Patent Office: 704 Days
• Field of Search: None
• US Class Current: 711/128
• CPC Class Codes: G06F 1/183 Internal mounting support structures, e.g. for printed circuit boards, internal connecting means for buses G06F13/409
• CPC Class Codes: G06F 11/108 Parity data distribution in semiconductor storages, e.g. in SSD
• CPC Class Codes: G06F 12/0804 with main memory updating G06F12/0806 takes precedence
• CPC Class Codes: G06F 12/0868 Data transfer between cache memory and other subsystems, e.g. storage devices or host systems
• CPC Class Codes: G06F 12/0871 Allocation or management of cache space
• CPC Class Codes: G06F 12/0891 using clearing, invalidating or resetting means
• CPC Class Codes: G06F 2211/103 Hybrid, i.e. RAID systems with parity comprising a mix of RAID types
• CPC Class Codes: G06F 2212/222 Non-volatile memory
• CPC Class Codes: G06F 2212/7201 Logical to physical mapping or translation of blocks or pages
• CPC Class Codes: G06F 3/0613 in relation to throughput
• CPC Class Codes: G06F 3/0656 Data buffering arrangements
• CPC Class Codes: G06F 3/0685 Hybrid storage combining heterogeneous device types, e.g. hierarchical storage, hybrid arrays
• CPC Class Codes: G06F 3/0688 Non-volatile semiconductor memory arrays
• CPC Class Codes: H04L 12/403 with centralised control, e.g. polling
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]
• CPC Class Codes: H05K 7/1444 Complex or three-dimensional-arrangements; Stepped or dual mother boards
• CPC Class Codes: H05K 7/1487 Blade assemblies, e.g. blade cases or inner arrangements within a blade

Abstract

An apparatus, system, and method are disclosed for caching data. A storage request module detects an input/output (“I/O”) request for a storage device cached by solid-state storage media of a cache. A direct mapping module references a single mapping structure to determine that the cache comprises data of the I/O request. The single mapping structure maps each logical block address of the storage device directly to a logical block address of the cache. The single mapping structure maintains a fully associative relationship between logical block addresses of the storage device and physical storage addresses on the solid-state storage media. A cache fulfillment module satisfies the I/O request using the cache in response to the direct mapping module determining that the cache comprises at least one data block of the I/O request.

Claims

1. A method for caching data, the method comprising:

detecting an input/output (“

I/O”

) request for a storage device being cached by solid-state storage media of a cache;

referencing a single mapping structure to determine that the cache comprises data of the I/O request, the single mapping structure mapping each logical block address of the storage device directly to a logical block address of the cache, the single mapping structure comprising a fully associative relationship between logical block addresses of the storage device and physical storage addresses on the solid-state storage media; and

satisfying the I/O request using the cache in response to determining that the cache comprises at least one data block of the I/O request.

2. The method of claim 1, wherein satisfying the I/O request comprises storing the data of the I/O request to the cache sequentially on the solid-state storage media to preserve an ordered sequence of storage operations performed on the solid-state storage media at one or more logical block addresses of the cache.

3. The method of claim 2, wherein storing the data of the I/O request to the cache sequentially comprises appending the data of the I/O request to an append point of a sequential, log-based, cyclic writing structure of the solid-state storage media, and wherein the single mapping structure is configured such that each logical block address of the storage device maps to a distinct unique entry in the single mapping structure and the unique entry maps to a distinct physical storage address on the solid-state storage media.

4. The method of claim 1, wherein satisfying the I/O request comprises reading the data of the I/O request from the cache using a physical storage address of the solid-state storage media associated with a logical block address of the I/O request.

5. The method of claim 1, further comprising storing the data of the I/O request on the solid-state storage media in a format that associates the data of the I/O request with respective logical block addresses of the data of the I/O request.

6. The method of claim 1, further comprising associating sequence indicators with the data of the I/O request on the solid-state storage media, wherein the sequence indicators record an ordered sequence of storage operations performed on the solid-state storage media.

7. The method of claim 6, further comprising:

storing the data of the I/O request in a format that associates the data of the I/O request with respective logical block addresses on the solid-state storage media;

maintaining an entry in the single mapping structure, the entry comprising an association between logical block addresses of the data of the I/O request and physical storage locations comprising the data of the I/O request on the solid-state storage media; and

reconstructing the entry in the single mapping structure using the logical block addresses of the data of the I/O request and the sequence indicators associated with the data of the I/O request on the solid-state storage media.

8. The method of claim 1, wherein the I/O request comprises one or more sets of non-contiguous logical block address ranges for the storage device.

9. The method of claim 1, wherein the solid-state storage media is managed by a solid-state storage controller configured to mask differences in latency for storage operations performed on the solid-state storage media.

10. The method of claim 1, wherein the single mapping structure comprises a plurality of entries, each entry mapping a variable length range of logical block addresses of the cache to a location on the solid-state storage media of the cache.

11. The method of claim 1, wherein the presence of an entry for a logical block address of the cache in the single mapping structure indicates that the cache stores data associated with a corresponding logical block address of the storage device at a physical storage address on the solid-state storage media indicated by the entry.

12. The method of claim 1, further comprising performing one or more actions on the cache in response to detecting one or more predefined commands for the storage device, wherein the one or more predefined commands are selected from a group consisting of a flush command, a pin command, an unpin command, a freeze command, and a thaw command.

13. The method of claim 1, further comprising dynamically reducing a cache size for the cache in response to an age characteristic for storage media of the cache.

14. The method of claim 1, wherein the single mapping structure maps each logical block address of the storage device directly to a logical block address of the cache by using an address of the I/O request directly to identify both an entry in the single mapping structure for a logical block address of the cache and to identify a logical block address of the storage device.

15. The method of claim 1, wherein a cache data block associated with a logical block address of the cache is equal in size to a storage device data block associated with a logical block address of the storage device.

16. An apparatus for caching data, the apparatus comprising:

a storage request module that detects an input/output (“

I/O”

) request for a storage device cached by solid-state storage media of a cache;

a direct mapping module that references a single mapping structure using an address of the I/O request to determine that the cache comprises data of the I/O request, the address of the I/O request directly identifying both an entry in the single mapping structure and a logical block address of the storage device, the single mapping structure maintaining a fully associative relationship between logical block addresses of the storage device and physical storage addresses on the solid-state storage media; and

a cache fulfillment module that satisfies the I/O request using the cache in response to determining that the cache comprises at least one data block of the I/O request;

wherein the storage request module, the direct mapping module, and the cache fulfillment module comprise one or more of logic hardware and executable code, the executable code stored on a non-transitory computer storage medium of the apparatus.

17. The apparatus of claim 16, wherein the cache fulfillment module satisfies the I/O request by storing the data of the I/O request to the cache sequentially on the solid-state storage media to preserve an ordered sequence of storage operations performed on the solid-state storage media at one or more logical block addresses of the cache.

18. The apparatus of claim 16, wherein the cache fulfillment module satisfies the I/O request by reading the data of the I/O request from the cache using a physical storage address of the solid-state storage media associated with a logical block address of the I/O request.

19. A system for caching data, the system comprising:

a processor;

a storage controller for a nonvolatile solid-state storage cache, the cache in communication with the processor over one or more communications buses;

a cache controller in communication with the storage controller, the cache controller comprising,

a storage request module that detects an input/output (“

I/O”

) request for a storage device cached by solid-state storage media of a cache;

a direct mapping module that references a single mapping structure using an address of the I/O request to determine that the cache comprises data of the I/O request, the address of the I/O request directly identifying both an entry in the single mapping structure and a logical block address of the storage device, the single mapping structure maintaining a fully associative relationship between logical block addresses of the storage device and physical storage addresses on the solid-state storage media; and

a cache fulfillment module that satisfies the I/O request using the cache in response to determining that the cache comprises at least one data block of the I/O request.

20. The system of claim 19, further comprising a host computer system, the host computer system comprising the processor, wherein the storage controller and the cache controller each comprise a device driver executing on the processor of the host computer system.