CONCURRENT CONTENT MANAGEMENT AND WEAR OPTIMIZATION FOR A NON-VOLATILE SOLID-STATE CACHE

• US 20140181377A1
• Filed: 11/22/2013
• Published: 06/26/2014
• Est. Priority Date: 01/29/2010
• Status: Active Grant

• Current Assignee: NetApp, Inc.
• Original Assignee: NetApp, Inc.
• Inventors: Kimmel, Jeffrey S., Pafford, Randy, Sundaram, Rajesh S.
• Granted Patent: US 9,043,542 B2
• Time in Patent Office: Days
• US Class Current: 711/103
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 12/12 Replacement control
• CPC Class Codes: G06F 2212/222 Non-volatile memory
• CPC Class Codes: G06F 2212/7211 Wear leveling

Abstract

Described is a technique for managing the content of a nonvolatile solid-state memory data cache to improve cache performance while at the same time, and in a complementary manner, providing for automatic wear leveling. A modified circular first-in first-out (FIFO) log/algorithm is generally used to determine cache content replacement. The algorithm is used as the default mechanism for determining cache content to be replaced when the cache is full but is subject to modification in some instances. In particular, data are categorized according to different data classes prior to being written to the cache, based on usage. Once cached, data belonging to certain classes are treated differently than the circular FIFO replacement algorithm would dictate. Further, data belonging to each class are localized to designated regions within the cache.

Claims

1. A method comprising:

making write allocation decisions for a cache implemented as non-volatile solid-state storage in a storage system, by executing a cache replacement algorithm that concurrently applies cache hit optimization and wear optimization for the cache; and

writing to locations in the cache according to the write allocation decisions.

2. A method as recited in claim 1, wherein the cache replacement algorithm comprises a circular FIFO replacement algorithm.

3. A method as recited in claim 1, wherein making write allocation decisions for the cache comprises:

classifying data into a plurality of data classes based on an expected usage of the data; and

selecting locations in the cache to store the data according to results of said classifying.

4. A method as recited in claim 3, wherein the cache comprises a plurality of erase blocks, and wherein selecting locations in the cache to store the data comprises selecting locations in the cache so that each of the plurality of erase blocks will store data from only one data class at a time, of the plurality of data classes.

5. A method as recited in claim 3, wherein the cache replacement algorithm comprises a circular FIFO replacement algorithm, and wherein making write allocation decisions for the cache comprises:

defining a first data class, of the plurality of data classes, to include data which are expected to remain valid in the cache for at least a complete cycle of a circular FIFO cache replacement log and that should be replaced in the cache upon expiration of a complete cycle of the cache replacement log if they are determined not to be recently used; and

defining a second data class, of the plurality of data classes, to include data which are expected to remain valid in the cache for less than a complete cycle of the cache replacement log.

6. A method as recited in claim 5, wherein selecting locations in the cache to store the data units comprises selecting locations in the cache so that, for each of the plurality of data classes, the data in said data class tend to be grouped together in the cache.

7. A method as recited in claim 6, wherein making write allocation decisions for the cache further comprises defining a third data class, of the plurality of data classes, to include data which are expected to remain valid in the cache for a plurality of complete cycles of the cache replacement log.

8. A method as recited in claim 6, wherein the non-volatile solid-state storage comprises a plurality of erase blocks, and wherein selecting locations in the cache to store the data units comprises selecting locations in the cache so that each of the plurality of erase blocks will store data from only one data class at a time, of the plurality of data classes.

9. A method as recited in claim 6, wherein the non-volatile solid-state storage comprises a plurality of erase blocks, and wherein selecting locations in the cache to store the data units comprises ensuring that at least some of the data in each of the data classes are confined to a specified set of one or more erase blocks.

10. A method as recited in claim 9, wherein the specified set of one or more erase blocks comprises an integer number of erase block stripes, each said erase block stripe including a set of erase blocks distributed across a plurality of physical memory devices.

11. A method as recited in claim 10, wherein each said erase block stripe is a RAID parity group.

12. A method as recited in claim 5, wherein making write allocation decisions for the cache further comprises:

detecting when a predetermined amount of data, stored in a region of the cache that contains data of the second data class, have been invalidated; and

responsive at least in part to said detecting, making the region available for reuse before a location in the region reaches FIFO-driven replacement.

13. A method as recited in claim 12, further comprising:

copying at least some data units in the region which have not been invalidated to new locations in the cache, prior to making the region available for reuse; and

assigning the copied data units to a tail end of the cache replacement log.

14. A method as recited in claim 12, wherein making the region available for reuse comprises making the region available for reuse only for data of a class other than the second data class.

15. A method as recited in claim 5, wherein making write allocation decisions for the cache further comprises:

identifying a plurality of data in the cache as being subject to imminent replacement in the cache and as having been recently used; and

copying the identified data to new locations in the cache and assigning the identified data to a tail end of the cache replacement log.

16. A method comprising:

receiving at a storage server a plurality of data access requests from a plurality of storage clients over a network, the storage server including a primary cache and a secondary cache, the secondary cache implemented as non-volatile solid-state storage including a plurality of erase blocks;

defining a first data class in the storage server to include data which are expected to remain valid in the secondary cache for at least a complete cycle of a circular cache replacement log and that should be replaced in the secondary cache if they are determined to be not recently used;

defining a second data class in the storage server to include data in the secondary cache which are expected to remain valid for less than a complete cycle of the cache replacement log;

defining a third data class in the storage server to include data in the secondary cache which are expected to remain valid for a plurality of complete cycles of the cache replacement log;

classifying each of a plurality of data units in the storage server into one of the first, second or third data class, based on a usage frequency of each said data unit; and

making write allocation decisions for the plurality of data units with respect to the secondary cache, by selecting locations in the secondary cache so that data from each of the first, second or third data class are confined at any given time to a separate set of one or more erase block stripes, each said erase block stripe including a set of erase blocks distributed across a plurality of physical memory devices.

18. A method as recited in claim 16, wherein the non-volatile solid-state storage comprises a plurality of erase blocks, and wherein selecting locations in the secondary cache comprises selecting locations in the secondary cache so that each of the plurality of erase blocks will store data from only one of the first, second or third data class at a time.

19. A method as recited in claim 18, wherein making write allocation decisions comprises:

detecting that a predetermined amount of data, stored in a region of the cache that contains data of the second data class, have been invalidated; and

responsive at least in part to said detecting, immediately making locations in the region that have been invalidated available for reuse.

20. A method as recited in claim 18, wherein making write allocation decisions further comprises:

identifying a plurality of data in the secondary cache as being subject to imminent replacement in the secondary cache and as having been recently used; and

copying the identified data to new locations in the cache and assigning the identified data to a tail end of the cache replacement log.

17. A method as recited in claim 165, wherein each said erase block stripe is a RAID parity group.

21. A storage system comprising:

a random access memory facility;

a cache formed from non-volatile solid-state storage and designated to cache data evicted from the random access memory facility;

a processor; and

a memory storing instructions for execution by the processor to cause the storage server to execute operations including

monitoring usage of data in the storage system;

based on results of said monitoring, classifying data in the storage system into a plurality of data classes according to usage characteristics of the data, each of the data classes being associated with a different one of a plurality of cache replacement policies applied to the cache; and

selecting storage locations in the cache for the data, based on results of said classifying, including localizing within the cache at least some of the data in each of the data classes.

22. A storage system as recited in claim 21, wherein the data comprises a plurality of data units, and wherein each said data unit is assigned to one of the data classes prior to being stored in the cache.

23. A storage system as recited in claim 21, wherein the cache comprises a plurality of erase blocks, and wherein localizing within the cache at least some of the data in each of the data classes comprises storing data so that each said erase block stores data subject to the same cache placement policy.

24. A storage system as recited in claim 21, wherein the cache comprises a plurality of erase blocks, and wherein localizing within the cache at least some of the data in each of the data classes comprises ensuring that at least some of the data in each of the data classes are confined to a specified set of one or more erase blocks.

25. A storage system as recited in claim 24, wherein the specified set of one or more erase blocks comprises an integer number of erase block stripes, each said erase block stripe including a set of erase blocks distributed across a plurality of physical memory devices.

26. A storage system as recited in claim 25, wherein each said erase block stripe is a RAID parity group.

27. A storage system as recited in claim 21, wherein the plurality of cache replacement policies apply a cache utilization optimization scheme.

28. A storage system as recited in claim 27, wherein the plurality of cache replacement policies further apply a wear optimization scheme for the cache.

29. A storage server comprising:

a network interface through which to receive a plurality of data access requests from a plurality of storage clients over a network;

a primary storage facility;

a cache implemented as non-volatile solid-state storage, the non-volatile solid-state storage including a plurality of erase blocks; and

a processor configured to apply a plurality of cache replacement policies associated with the cache, to data managed by the storage server, each of the cache replacement policies corresponding to a different one of a plurality of classes of data usage, and to implement the cache replacement policies by confining write activity for data in at least one of the classes to designated erase blocks or sets of erase blocks of the non-volatile solid-state storage.

30. A storage server as recited in claim 29, wherein the plurality of cache replacement policies collectively apply a cache replacement optimization scheme and a wear optimization scheme for the cache.

31. A storage server as recited in claim 29, wherein the processor is configured to confine data in each of the classes to a separate set of one or more erase block stripes, each said erase block stripe including a set of erase blocks distributed across a plurality of physical memory devices.

32. A storage server as recited in claim 31, wherein each said erase block stripe is a RAID parity group.

33. A storage server as recited in claim 29, wherein the processor is configured to select locations in the cache so that each of the plurality of erase blocks will store data from only one data class at a time, of the plurality of data classes.

34. A storage server as recited in claim 29, wherein the plurality of classes of data usage comprise:

a first class for data which are expected to remain valid in the cache for at least a complete cycle of a circular cache replacement log and that should be replaced in the cache if they are not recently used; and

a second class for data which are expected to remain valid in the cache for less than a complete cycle of the cache replacement log.

35. A storage server as recited in claim 34, wherein the plurality of classes of data usage comprise a third class for data which are expected to remain valid in the cache for a plurality of complete cycles of the cache replacement log.

36. A storage server as recited in claim 34, wherein the processor is configured to:

detect that a predetermined amount of data, stored in a region of the cache that contains data of the second class, have been invalidated, and

immediately make locations in the region that have been invalidated available for reuse.

37. A storage server as recited in claim 36, wherein immediately making locations in the cache that have been invalidated available for reuse comprises making the locations in the cache that have been invalidated available for reuse only for data units of a class other than the second class.

38. A storage server as recited in claim 34, wherein the processor is configured to:

identify a plurality of data in the cache as being subject to imminent replacement in the cache and as having been recently used; and

copy the identified data to new locations in the cache and assign the identified data to a tail end of the cache replacement log.

39. A storage system comprising:

a cache implemented as non-volatile solid-state storage;

means for making write allocation decisions for a data set in relation to the cache, based on expected usage of data in the data set, to implement concurrently a wear optimization scheme and a cache replacement scheme for the cache; and

means for writing to locations in the cache according to the write allocation decisions.