Using frequency domain to prioritize storage of metadata in a cache

• US 9,804,973 B1
• Filed: 11/12/2015
• Issued: 10/31/2017
• Est. Priority Date: 01/09/2014
• Status: Expired due to Fees

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Pure Storage, Inc.
• Inventors: Shalev, Ori
• Primary Examiner(s): Nguyen, Than
• Application Number:
  US14/939,693
• Time in Patent Office: 719 Days
• Field of Search: 711118, 711129, 711136
• CPC Class Codes: G06F 12/0253 Garbage collection, i.e. reclamation of unreferenced memory
• CPC Class Codes: G06F 12/0866 for peripheral storage systems, e.g. disk cache
• 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 12/12 Replacement control
• CPC Class Codes: G06F 12/122 of the least frequently used [LFU] type, e.g. with individual count value
• CPC Class Codes: G06F 12/123 with age lists, e.g. queue, most recently used [MRU] list or least recently used [LRU] list
• CPC Class Codes: G06F 12/126 with special data handling, e.g. priority of data or instructions, handling errors or pinning
• CPC Class Codes: G06F 12/127 using additional replacement algorithms
• CPC Class Codes: G06F 2212/1021 Hit rate improvement
• CPC Class Codes: G06F 2212/313 In storage device
• CPC Class Codes: G06F 2212/466 Metadata, control data
• CPC Class Codes: G06F 2212/70 Details relating to dynamic memory management

Abstract

A system and method for efficiently caching metadata in a storage system. Addresses from a plurality of I/O accesses to the storage system are captured and then a frequency domain representation of the addresses is generated. The frequency domain representation is used to measure the randomness of the various applications which are accessing the storage system. Scores are generated based on the measure of randomness, and scores are assigned to the various regions of the logical address space. Scores are then assigned to the metadata pages which are stored in the cache based on the region of the logical address space to which the metadata pages correspond. The scores are used when determining which metadata pages to evict from the cache. The cache will attempt to evict those metadata pages which correspond to regions of the logical address space that are servicing random I/O accesses.

Claims

1. A method comprising:

measuring an amount of randomness within a plurality of addresses that are referenced in a plurality of accesses to one or more storage devices including adding together frequency component values above a first cutoff frequency in a first frequency distribution of a first frequency domain representation of the plurality of addresses of the plurality of accesses; and

caching, in dependence upon the amount of randomness for each of the plurality of addresses, metadata associated with one or more of the plurality of addresses.

2. The method as recited in claim 1, wherein measuring the amount of randomness comprises generating the first frequency domain representation of the plurality of addresses of the plurality of accesses.

3. The method as recited in claim 1, wherein the plurality of accesses target a logical address space.

4. The method as recited in claim 3, wherein measuring the amount of randomness comprises:

capturing the plurality of addresses from the plurality of accesses;

generating the first frequency domain representation of a first plurality of addresses from the captured plurality of addresses, wherein the first plurality of addresses correspond to a first region of the logical address space, and wherein the first frequency domain representation has the first frequency distribution;

identifying the first region as a relatively low random region responsive to determining the frequency component values above the first cutoff frequency are less than a first threshold; and

identifying the first region as a relatively high random region responsive to determining the frequency component values above the first cutoff frequency are greater than a first threshold.

5. The method as recited in claim 4, further comprising:

generating a first score corresponding to the first region, wherein the first score is based on the amount of randomness in the first frequency distribution;

identifying one or more pages of first metadata corresponding to the first region which are stored in the cache;

assigning the first score to each of the one or more pages of first metadata which are stored in the cache; and

utilizing the first score when determining whether to evict the one or more pages of first metadata from the cache.

6. The method as recited in claim 4, further comprising partitioning the logical address space into a plurality of regions.

7. The method as recited in claim 6, further comprising generating a second frequency domain representation of a second plurality of addresses from the captured plurality of addresses, wherein the second plurality of addresses correspond to a second region of the logical address space, and wherein the second frequency domain representation has a second frequency distribution.

8. A system comprising:

one or more storage devices;

a cache; and

a storage controller;

wherein the storage controller is configured to;

measure an amount of randomness within a plurality of addresses that are referenced in a plurality of accesses to one or more storage devices including adding together frequency component values above a first cutoff frequency in a first frequency distribution of a first frequency domain representation of the plurality of addresses of the plurality of accesses; and

cache, in dependence upon the amount of randomness for each of the plurality of addresses, metadata associated with one or more of the plurality of addresses.

9. The system as recited in claim 8, wherein measuring the amount of randomness comprises generating the first frequency domain representation of the plurality of addresses of the plurality of accesses.

10. The system as recited in claim 8, wherein the plurality of accesses target a logical address space.

11. The system as recited in claim 10, wherein measuring the amount of randomness comprises:

capturing the plurality of addresses from the plurality of accesses;

generating the first frequency domain representation of a first plurality of addresses from the captured plurality of addresses, wherein the first plurality of addresses correspond to a first region of the logical address space, and wherein the first frequency domain representation has the first frequency distribution;

identifying the first region as a relatively low random region responsive to determining the frequency component values above the first cutoff frequency are less than a first threshold; and

identifying the first region as a relatively high random region responsive to determining the frequency component values above the first cutoff frequency are greater than a first threshold.

12. The system as recited in claim 11, wherein the storage controller is further configured to generate a first score corresponding to the first region, wherein the first score is based on the amount of randomness in the first frequency distribution, and wherein the cache is further configured to:

identify one or more pages of first metadata corresponding to the first region which are stored in the cache;

assign the first score to each of the one or more pages of first metadata which are stored in the cache; and

utilize the first score when determining whether to evict the one or more pages of first metadata from the cache.

13. The system as recited in claim 11, wherein the storage controller is further configured to partition the logical address space into a plurality of regions.

14. The system as recited in claim 13, wherein the storage controller is further configured to generate a second frequency domain representation of a second plurality of addresses from the captured plurality of addresses, wherein the second plurality of addresses correspond to a second region of the logical address space, and wherein the second frequency domain representation has a second frequency distribution.

15. A non-transitory computer readable storage medium storing program instructions, wherein the program instructions are executable by a processor to:

measure an amount of randomness within a plurality of addresses that are referenced in a plurality of accesses to one or more storage devices including adding together frequency component values above a first cutoff frequency in a first frequency distribution of a first frequency domain representation of the plurality of addresses of the plurality of accesses; and

cache, in dependence upon the amount of randomness for each of the plurality of addresses, metadata associated with one or more of the plurality of addresses.

16. The non-transitory computer readable storage medium as recited in claim 15, wherein measuring the amount of randomness comprises generating a frequency domain representation of the plurality of addresses of the plurality of accesses.

17. The non-transitory computer readable storage medium as recited in claim 15, wherein the plurality of accesses target a logical address space.

18. The non-transitory computer readable storage medium as recited in claim 17, wherein measuring the amount of randomness comprises:

capturing the plurality of addresses from the plurality of accesses;

generating a first frequency domain representation of a first plurality of addresses from the captured plurality of addresses, wherein the first plurality of addresses correspond to a first region of the logical address space, and wherein the first frequency domain representation has the first frequency distribution;

identifying the first region as a relatively low random region responsive to determining the frequency component values above the first cutoff frequency are less than a first threshold; and

identifying the first region as a relatively high random region responsive to determining the frequency component values above the first cutoff frequency are greater than a first threshold.

19. The non-transitory computer readable storage medium as recited in claim 18, wherein the program instructions are further executable by a processor to:

generate a first score corresponding to the first region, wherein the first score is based on the amount of randomness in the first frequency distribution;

identify one or more pages of first metadata corresponding to the first region which are stored in the cache;

assign the first score to each of the one or more pages of first metadata which are stored in the cache; and

utilize the first score when determining whether to evict the one or more pages of first metadata from the cache.

20. The non-transitory computer readable storage medium as recited in claim 18, wherein the program instructions are further executable by a processor to partition the logical address space into a plurality of regions.