Apparatus, System, and Method for Caching Data on a Solid-State Storage Device

• US 20110066808A1
• Filed: 09/08/2010
• Published: 03/17/2011
• 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: Atkisson, David, Vigor, Kevin B., Aune, Joshua, Flynn, David, Thatcher, Jonathan, Zappe, Michael, Strasser, John
• Granted Patent: US 8,719,501 B2
• Time in Patent Office: Days
• 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 for caching data on a solid-state storage device, the method comprising:

maintaining metadata pertaining to cache operations performed on a solid-state storage device and to storage operations of the solid-state storage device;

accessing the metadata to manage storage operations of the solid-state storage device; and

accessing the metadata to manage a cache stored on the solid-state storage device.

2. The method of claim 1, 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 1, wherein the metadata comprises cache metadata, the method further comprising selecting a storage division for recovery using the cache metadata.

6. The method of claim 1, wherein the metadata comprises cache metadata, the method further comprising:

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

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

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

accessing cache attributes in the metadata, and

using the cache attributes to select a storage division 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 a 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; 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 a 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 a 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. A method for caching data on a solid-state storage device comprising a plurality of storage divisions, the method comprising:

storing cache data sequentially on a solid-state storage device;

maintaining cache metadata pertaining to the cache data sequentially stored on the solid-state storage device; and

accessing the cache metadata to manage sequential storage operations of the solid-state storage device.

17. The method of claim 16, wherein the cache metadata is associated with a logical address and is indexed independent of an address of storage units on the solid-state storage device comprising data of a logical address.

18. The method of claim 16, wherein the sequential storage operations comprise selecting a storage division for recovery based on whether the storage division comprises storage units that have been stored on a backing store as indicated by the cache metadata.

19. The method of claim 16, wherein the cache metadata comprises cache metadata identifying a cache entry to retain on the solid-state storage device, the method further comprising:

using the 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

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

20. A method for caching data on a solid-state storage device, comprising:

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

maintaining storage metadata pertaining to the sequential storage operations, the storage metadata comprising a reverse index associating storage metadata with storage units of the solid-state storage device; and

accessing the storage metadata to manage a cache stored on the storage units of the solid-state storage device.

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 for caching data on a solid-state storage device, comprising:

maintaining metadata comprising a plurality of cache entries, each associated with a logical address and referencing a variable number of storage units on a solid-state storage device, the storage units comprising data of the cache entry, wherein the cache entries are indexed in the metadata by logical address;

receiving a client storage request, the client storage request comprising a logical address; and

determining whether data pertaining to the client storage request is stored on the solid-state storage device using the cache entries and the logical address.

25. The method of claim 24, wherein determining comprises 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 the 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 the 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, wherein the client storage request comprises removing 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, wherein the client storage request comprises removing data stored on the solid-state storage device, 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 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;

accessing the metadata to manage storage operations of the solid-state storage device, 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 sequential storage operations of the solid-state storage device.