Apparatus, system, and method for caching data on a solid-state storage device

• US 8,719,501 B2
• Filed: 09/08/2010
• Issued: 05/06/2014
• Est. Priority Date: 09/08/2009
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: Fusion-IO Incorporated (Western Digital Corporation)
• Inventors: Flynn, David, Strasser, John, Thatcher, Jonathan, Atkisson, David, Zappe, Michael, Aune, Joshua, Vigor, Kevin B.
• Primary Examiner(s): Farrokh, Hashem
• Application Number:
  US12/877,971
• Publication Number:
  US 20110066808A1
• Time in Patent Office: 1,336 Days
• Field of Search: 711/118, 711/103
• US Class Current: 711/118
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 12/0866 for peripheral storage systems, e.g. disk cache
• CPC Class Codes: G06F 2212/214 Solid state disk
• CPC Class Codes: G06F 2212/7201 Logical to physical mapping or translation of blocks or pages
• CPC Class Codes: G06F 2212/7205 Cleaning, compaction, garbage collection, erase control
• CPC Class Codes: G06F 2212/7207 management of metadata or control data

Abstract

An apparatus, system, and method are disclosed for caching data on a solid-state storage device. The solid-state storage device maintains metadata pertaining to cache operations performed on the solid-state storage device, as well as storage operations of the solid-state storage device. The metadata indicates what data in the cache is valid, as well as information about what data in the nonvolatile cache has been stored in a backing store. A backup engine works through units in the nonvolatile cache device and backs up the valid data to the backing store. During grooming operations, the groomer determines whether the data is valid and whether the data is discardable. Data that is both valid and discardable may be removed during the grooming operation. The groomer may also determine whether the data is cold in determining whether to remove the data from the cache device. The cache device may present to clients a logical space that is the same size as the backing store. The cache device may be transparent to the clients.

Claims

1. A method, comprising:

maintaining, by a storage controller configured to manage a solid-state storage device, a logical address space by use of an index configured to a) map data stored on the solid-state storage device to respective storage locations of the solid-state storage device, and b) to map identifiers corresponding to data of a primary storage system cached on the solid-state storage device to respective storage locations of the solid-state storage device, wherein the logical address space is larger than a physical address space of the solid-state storage device; and

accessing metadata pertaining to storage operations performed on the solid-state storage device and maintained by the storage controller to manage data of the primary storage system cached on the solid-state storage device.

2. The method of claim 1, further comprising accessing metadata pertaining to cache operations performed on the solid-state storage device and maintained by the storage controller to manage grooming operations on storage divisions of the solid-state storage device, wherein the metadata pertaining to cache operations and the metadata pertaining to storage operations are stored in a shared datastructure.

3. The method of claim 1, wherein the metadata comprises a discardability indicator identifying storage units of the solid-state storage device that have been stored on a backing store, the method further comprising:

using the discardability indicators to select a storage division for recovery.

4. The method of claim 3, the method further comprising:

identifying a nondiscardable storage unit in the selected storage division using the metadata; and

causing data of the nondiscardable storage unit to be stored on a different storage division of the solid-state storage media.

5. The method of claim 2, further comprising selecting a storage division for recovery using the metadata pertaining to cache operations.

6. The method of claim 2, further comprising:

identifying a discardable storage unit of a cache entry that the metadata pertaining to the cache operations indicates should be retained on the solid-state storage device; and

causing the identified, discardable storage unit to be stored on a different storage division of the solid-state storage media in a recovery operation.

7. The method of claim 1, the method further comprising:

accessing cache attributes in the metadata pertaining to cache operations, and

using the cache attributes to select a storage division of the solid-state storage device for recovery.

8. The method of claim 1, further comprising:

receiving a storage request comprising a logical address associated with a first cache entry referencing storage units in a first storage division of the solid-state storage device;

storing data of the storage request in storage units of a second storage division of the solid-state storage device; and

updating the metadata to associate the cache entry with the storage units in the second storage division, to indicate the storage units in the first storage division are invalid, and to indicate the storage units in the second storage division are nondiscardable.

9. The method of claim 1, further comprising:

storing data on a first storage unit of the solid-state storage device, the data corresponding to a first logical address proximate to a logical address of a second cache entry in the metadata; and

modifying the second cache entry to include the first logical address and to reference the first storage unit.

10. The method of claim 1, wherein the solid-state storage device is communicatively coupled to the backing store, the method further comprising:

presenting a logical address space that comprises a capacity of the backing store;

determining a current occupancy of the solid-state storage device using the metadata pertaining to the storage operations; and

increasing a priority of a backup engine configured to cause nondiscardable storage units to be stored on the backing store when the current occupancy exceeds the target occupancy threshold.

11. The method of claim 1, further comprising:

presenting a logical address space that exceeds a logical address space of the backing store;

identifying a storage request associated with a logical address that falls outside of the logical address space of the backing store; and

maintaining a nondiscardable indicator of a storage unit of a cache entry associated with the logical address.

12. The method of claim 1, the method further comprising:

receiving a storage request referencing a first logical address associated with a first cache entry in the metadata, and a second logical address not associated with a cache entry in the metadata; and

servicing the request by combining data stored on the solid-state storage device and corresponding to the first cache entry with data read from the backing store.

13. The method of claim 12, further comprising adding a cache entry to the metadata associated with storage units of the solid-state storage device comprising the data read from the backing store.

14. The method of claim 12, further comprising modifying the metadata to include a cache entry that includes the second logical address and reference storage units comprising the data read from the backing store.

15. The method of claim 12, wherein data of the storage request is non-contiguous.

16. An apparatus, comprising:

a storage controller configured to store data corresponding to a primary storage system on respective storage divisions of a solid-state storage device; and

a cache controller configured to maintain cache metadata pertaining to the data corresponding to the primary storage system stored on the respective storage divisions of the solid-state storage device, wherein the cache metadata includes discardability indicators configured to identify data stored on the solid-state storage device that has been backed-up to the primary storage system;

wherein the storage controller is configured to select a storage division of the solid-state storage device for a storage recovery operation by use of the discardability indicators, wherein the selected storage division comprises data that has not been backed-up to the primary storage system.

17. The apparatus of claim 16, wherein the storage controller is further configured to access the cache metadata to identify storage units of the storage division selected for the storage recovery operation that comprise data corresponding to the primary storage system that can be evicted.

18. The apparatus of claim 16, wherein the storage division is selected based on discardability indicators corresponding to data stored within respective storage units of the storage division.

19. The apparatus of claim 16, wherein the cache metadata comprises cache metadata identifying a cache entry to retain on the solid-state storage device, and wherein the storage controller is further configured to access the cache metadata to identify in a storage division selected for recovery, a discardable storage unit associated with a cache entry to retain on the solid-state storage device, and to store the identified, discardable storage unit on a different storage division of the solid-state storage media.

20. A method, comprising:

storing data on a solid-state storage device in one or more storage operations performed on the solid-state storage device by a storage controller;

maintaining, by the storage controller, storage metadata pertaining to one or more of wear-levels of storage units of the solid-state storage device and reliability of the storage units of the solid-state storage device; and

accessing the storage metadata to manage entries of a cache comprising data of a backing store cached on the storage units of the solid-state storage device based on one or more of the wear-levels of the storage units and the reliability of the storage units as indicated by the storage metadata.

21. The method of claim 20, wherein managing the cache comprises selecting a cache entry for eviction based on the storage metadata indicating one of a storage unit comprising data of the cache entry having a high amount of wear, the storage unit having a low amount of wear, and the storage unit being unreliable.

22. The method of claim 20, wherein managing the cache comprises causing data of a cache entry stored on a first storage unit of the solid-state storage device to be stored on a second storage unit of the solid-state storage device based on the storage metadata indicating one of the storage division having a high amount of wear, the storage division having a low amount of wear, and the storage division being unreliable.

23. The method of claim 20, wherein the cache manager causes a storage unit stored on a solid-state storage device to be stored on a backing store based on the storage metadata indicating one of the storage division having a high amount of wear, the storage division having a low amount of wear, and the storage division being unreliable.

24. A method, comprising:

appending data of a primary storage system to a storage log on a non-volatile storage medium;

providing a single translation layer configured to bind identifiers of data stored on the non-volatile storage medium to physical addresses on the non-volatile storage medium, and to translate identifiers corresponding to the data of a primary storage system in the storage log on the non-volatile storage medium to respective physical addresses on the non-volatile storage medium; and

writing data of the primary storage system in the storage log back to the primary storage system in accordance with an order of the data of the primary storage system within the storage log.

25. The method of claim 24, further comprising determining whether data pertaining to the client storage request is cached on the solid-state storage device and identifying a physical address of the cached data by comparing a set of client logical addresses to a variable size cache entry selected using one or more of the set of client logical addresses.

26. The method of claim 24, wherein in response to data pertaining to a client storage request not being stored on the solid-state storage device, the method further comprising:

storing data corresponding to the client storage request in a one or more storage units of the solid-state storage device; and

creating a new cache entry indexed to the client logical address to represent the variable size cache entry.

27. The method of claim 24, wherein in response to data pertaining to a client storage request not being stored on the solid-state storage device, the method further comprising:

storing data corresponding to the client storage request on storage units of the solid-state storage device; and

modifying a cache entry to reference the logical address of the client storage request and the storage units.

28. The method of claim 27, wherein modifying the cache entry further comprises:

merging the cache entry with a second cache entry in the metadata, the second cache entry associated with a logical address proximate within a logical address space to the logical address of the client storage request by associating the cache entry with the logical address of the second cache entry and storage units of the second cache entry.

29. The method of claim 24, further comprising receiving a client storage request to remove data stored on the solid-state storage device, the method further comprising deleting a cache entry associated with the data referenced in the client storage request and marking a storage unit associated with the cache entry as invalid.

30. The method of claim 29, the method further comprising:

splitting a cache entry into one or more cache entries, the one or more cache entries omitting references to storage units comprising data referenced in the client storage request.

31. The method of claim 24, wherein the storage request references data at a first logical address, and a second, non-contiguous logical address, the method further comprising:

identifying a first cache entry referencing storage units comprising data corresponding to the first logical address;

identifying a second cache entry referencing storage units comprising data corresponding to the second logical address; and

providing data of the storage units referenced by the first and the second cache entries in response to the client storage request.

32. The method of claim 24, further comprising:

accessing a reverse index comprising associations between storage divisions of the solid-state storage device and client logical addresses; and

providing an indication of an available storage capacity of the solid-state storage device using the reverse index.

33. A computer program product comprising instructions stored on a non-transitory machine-readable medium, the instructions configured to cause a machine to perform a method for caching data on a solid-state storage device, the method comprising:

maintaining shared metadata pertaining to cache operations performed on a solid-state storage device and to storage operations of the solid-state storage device, the metadata comprising an index configured to map data stored on the solid-state storage device to respective storage locations of the solid-state storage device, and to map identifiers corresponding to data of a primary storage system cached on the solid-state storage device to respective storage locations of the solid-state storage device;

accessing the metadata to manage storage operations of the solid-state storage device, wherein the storage operations comprise selecting a storage division of the solid-state storage device for recovery using the metadata pertaining to the cache operations; and

accessing the metadata to manage a cache stored on the solid-state storage device, wherein managing the cache comprises selecting a storage unit of the solid-state storage device to backup to a backing store using the metadata pertaining to one or more of wear levels of the storage divisions and reliability of the storage divisions.