System and method for managing large filesystem-based caches

• US 8,041,893 B1
• Filed: 09/09/2008
• Issued: 10/18/2011
• Est. Priority Date: 09/09/2008
• Status: Active Grant

• Current Assignee: Ip Ot Sub Ulc
• Original Assignee: Vignette Software LLC (Open Text Corporation)
• Inventors: Fung, Kin-Chung, Scheevel, Mark R.
• Primary Examiner(s): Doan; Duc
• Application Number:
  US12/206,909
• Time in Patent Office: 1,134 Days
• Field of Search: None
• US Class Current: 711/118
• CPC Class Codes: G06F 11/3466 Performance evaluation by tracing or monitoring
• CPC Class Codes: G06F 12/0866 for peripheral storage systems, e.g. disk cache
• CPC Class Codes: G06F 12/124 being minimized, e.g. non MRU
• CPC Class Codes: G06F 2201/885 Monitoring specific for caches
• CPC Class Codes: G06F 2212/463 File

Abstract

Embodiments disclosed herein utilize statistical approximations to manage large filesystem-based caches based on imperfect information. When removing entries from a large cache, which may have a million or more entries, the cache manager does not need to find the absolutely oldest entry that has been accessed the least recently. Instead, it suffices to find an entry that is older than most. In embodiments disclosed herein, statistical sampling of the cache is performed to produce models of different properties of the cache, including the number of entries, distribution of access times, distribution of entry sizes, etc. The models are then used to guide decisions that involve those properties. The size of the samples can be adjusted to balance the cost of acquiring the samples against the confidence level of the models produced by the samples. To achieve randomness, entries are stored using prefixes of addresses generated via a message-digest function.

Claims

1. A method of managing a cache, comprising:

at a computer, obtaining a statistical sampling of said cache;

generating a last access histogram based on said statistical sampling of said cache, wherein said last access histogram represents a distribution of access times of entries in said cache;

generating a size histogram based on said statistical sampling of said cache, wherein said size histogram represents a distribution of entry sizes in said cache;

determining a mean size of cache entries using said size histogram;

determining a percentage of entries to be removed from said cache;

determining a cutoff time based on said last access histogram and said percentage of said entries to be removed from said cache; and

removing, from said cache, entries whose last access time is older than said cutoff time.

2. The method of claim 1, further comprising:

based on said last access histogram, estimating a percentage of cache entries whose last access time is earlier than a reference point in time.

3. The method of claim 1, further comprising:

based on said size histogram, estimating a cumulative size of all cache entries.

4. The method of claim 1, wherein obtaining a statistical sampling of said cache comprises:

randomly selecting a directory of said cache;

reading entries of said randomly selected directory of said cache; and

comparing a number of said entries of said randomly selected directory of said cache to a predefined sample size.

5. The method of claim 4, wherein said number of said entries of said randomly selected directory of said cache is smaller than said predefined sample size, further comprising:

repeating said randomly selecting step and said reading step until said number of said entries matches or exceeds said predefined sample size.

6. The method of claim 1, further comprising:

receiving a cache entry; and

generating a cache address for said cache entry using a message-digest function.

7. The method of claim 6, further comprising:

storing said cache entry in said directory of said cache based on prefixes of said cache address.

8. The method of claim 1, wherein said cache contains a million or more entries.

9. A system, comprising:

a processor;

at least one non-transitory computer-readable storage medium accessible by said processor and carrying computer instructions executable by said processor, wherein when executed by said processor said computer instructions are operable to perform;

obtaining a statistical sampling of a filesystem-based cache;

generating a last access histogram based on said statistical sampling of said cache, wherein said last access histogram represents a distribution of access times of entries in said cache;

generating a size histogram based on said statistical sampling of said cache, wherein said size histogram represents a distribution of entry sizes in said cache;

determining a mean size of cache entries using said size histogram;

determining a percentage of entries to be removed from said cache;

determining a cutoff time based on said last access histogram and said percentage of said entries to be removed from said cache; and

removing from said cache entries whose last access time is older than said cutoff time.

10. The system of claim 9, wherein said computer instructions are further operable to perform:

based on said last access histogram, estimating a percentage of cache entries whose last access time is earlier than a reference point in time.

11. The system of claim 9, wherein said computer instructions are further operable to perform:

based on said size histogram, estimating a cumulative size of all cache entries.

12. The system of claim 9, wherein said computer instructions are further operable to perform:

randomly selecting a directory of said cache;

reading entries of said randomly selected directory of said cache;

comparing a number of said entries of said randomly selected directory of said cache to a predefined sample size; and

repeating said randomly selecting step and said reading step until said number of said entries matches said predefined sample size.

13. The system of claim 9, wherein said computer instructions are further operable to perform:

receiving a cache entry;

generating a cache address for said cache entry using a message-digest function; and

storing said cache entry in said directory of said cache based on prefixes of said cache address.

14. A computer program product comprising at least one computer-readable storage medium accessible by a processor and carrying computer instructions executable by said processor, wherein when executed by said processor said computer instructions are operable to perform:

obtaining a statistical sampling of a filesystem-based cache;

generating a last access histogram based on said statistical sampling of said cache, wherein said last access histogram represents a distribution of access times of entries in said cache;

generating a size histogram based on said statistical sampling of said cache, wherein said size histogram represents a distribution of entry sizes in said cache;

determining a mean size of cache entries using said size histogram;

determining a percentage of entries to be removed from said cache;

determining a cutoff time based on said last access histogram and said percentage of said entries to be removed from said cache; and

removing from said cache entries whose last access time is older than said cutoff time.

15. The computer program product of claim 14, wherein said computer instructions are further operable to perform:

based on said last access histogram, estimating a percentage of cache entries whose last access time is earlier than a reference point in time.

16. The computer program product of claim 14, wherein said computer instructions are further operable to perform:

based on said size histogram, estimating a cumulative size of all cache entries.

17. The computer program product of claim 14, wherein said computer instructions are further operable to perform:

randomly selecting a directory of said cache;

reading entries of said randomly selected directory of said cache;

comparing a number of said entries of said randomly selected directory of said cache to a predefined sample size; and

repeating said randomly selecting step and said reading step until said number of said entries matches or exceeds said predefined sample size.

18. The computer program product of claim 14, wherein said computer instructions are further operable to perform:

receiving a cache entry;

generating a cache address for said cache entry using a message-digest function; and

storing said cache entry in said directory of said cache based on prefixes of said cache address.