Non-volatile cache

• US 8,756,375 B2
• Filed: 06/29/2013
• Issued: 06/17/2014
• Est. Priority Date: 12/06/2006
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: Fusion-IO Incorporated (Western Digital Corporation)
• Inventors: Flynn, David
• Primary Examiner(s): Gu, Shawn X
• Application Number:
  US13/931,897
• Publication Number:
  US 20130297880A1
• Time in Patent Office: 353 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

Apparatuses, systems, and methods are disclosed for caching data. A method includes directly mapping a logical address of a backing store to a logical address of a non-volatile cache. A method includes mapping, in a logical-to-physical mapping structure, the logical address of the non-volatile cache to a physical location in the non-volatile cache. The physical location may store data associated with the logical address of the backing store. A method includes removing the mapping from the logical-to-physical mapping structure in response to evicting the data from the non-volatile cache so that membership in the logical-to-physical mapping structure denotes storage in the non-volatile cache.

Claims

1. A method comprising:

directly mapping a logical address of a backing store to a logical address of a non-volatile cache;

mapping, in a logical-to-physical mapping structure, the logical address of the non-volatile cache to a physical location in the non-volatile cache, the physical location storing data associated with the logical address of the backing store; and

removing the mapping to the physical location from the logical-to-physical mapping structure in response to evicting the data from the non-volatile cache such that membership in the logical-to-physical mapping structure denotes storage in the non-volatile cache.

2. The method of claim 1, wherein the logical-to-physical mapping structure comprises a fully associative relationship between logical addresses of the backing store and physical storage locations on non-volatile media of the cache.

3. The method of claim 1, further comprising satisfying a storage request for the backing store using the cache based on the logical-to-physical mapping structure.

4. The method of claim 3, wherein satisfying the storage request comprises storing data of the storage request to the cache sequentially on non-volatile media of the cache to preserve an ordered sequence of storage operations performed on the non-volatile media at one or more logical addresses of the cache.

5. The method of claim 4, wherein storing the data of the storage request to the cache sequentially comprises appending the data of the storage request to an append point of a sequential, log-based, cyclic writing structure of the non-volatile media and wherein the logical-to-physical mapping structure is configured such that the logical address of the backing store maps to a unique entry in the logical-to-physical mapping structure and the unique entry maps to a distinct physical location on the non-volatile media.

6. The method of claim 3, wherein satisfying the storage request comprises reading data of the storage request from the cache using a physical storage address for non-volatile media of the cache, the physical storage address associated with a logical address of the storage request.

7. The method of claim 1, further comprising storing the data associated with the logical address of the backing store at the physical location in the cache in a format that associates the data with the logical address of the non-volatile cache.

8. The method of claim 7, further comprising reconstructing the logical-to-physical mapping structure using logical addresses and sequence indicators associated with data on non-volatile media of the cache.

9. The method of claim 1, wherein the logical-to-physical mapping structure comprises a plurality of entries mapping variable length ranges of logical addresses of the cache to locations on non-volatile media of the cache.

10. 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 backing store.

11. The method of claim 10, wherein the one or more predefined commands comprise one or more of a flush command, a pin command, an unpin command, a freeze command, and a thaw command.

12. The method of claim 1, further comprising dynamically reducing a cache size for the cache in response to an age characteristic for non-volatile media of the cache.

13. The method of claim 1, wherein the logical-to-physical mapping structure maps logical addresses of the backing store directly to logical addresses of the cache by using the logical addresses of the backing store directly in entries in the logical-to-physical mapping structure for logical addresses of the cache and for logical addresses of the backing store.

14. The method of claim 1, wherein cache data blocks associated with logical block addresses of the cache are equal in size to storage device data blocks associated with logical addresses of the backing store.

15. An apparatus comprising:

a direct mapping module configured to associate logical addresses of a storage device directly with logical addresses of a non-volatile cache device and to map the logical addresses of the cache device to physical addresses of data on non-volatile media of the cache device; and

a cache fulfillment module configured to service input/output requests for the storage device using the cache device based on the mapping of logical addresses of the cache device to the physical addresses of the data, wherein the direct mapping module and the cache fulfillment module comprise one or more of logic hardware and a non-transitory computer readable storage medium storing executable code.

16. The apparatus of claim 15, further comprising an eviction module configured to evict data from the cache device, the direct mapping module configured to remove mappings for evicted data from a logical-to-physical mapping structure such that membership in the logical-to-physical mapping structure denotes storage in the cache device.

17. The apparatus of claim 15, wherein the direct mapping module is configured to maintain a fully associative relationship between logical addresses of the storage device and the physical addresses of the cache device.

18. An apparatus comprising:

means for directly mapping a logical address of a backing store to a logical address of a cache;

means for maintaining a fully associative relationship between the logical address of the backing store and physical addresses of the cache; and

means for satisfying a storage request for the backing store using the cache based on the logical address of the backing store, wherein the means for directly mapping, the means for maintaining, and the means for satisfying comprise one or more of logic hardware and a non-transitory computer readable storage medium storing executable code.

19. The apparatus of claim 18, further comprising means for removing an entry for the logical address of the cache from a mapping structure in response to evicting associated data from the cache such that membership in the mapping structure denotes storage in the cache.

20. The apparatus of claim 18, further comprising means for reconstructing a mapping structure for the cache based on logical addresses and sequence identifiers stored with data in a sequential log of the cache.