System and method for managing large filesystem-based caches
US8041893B1 · kind B1 · utility
Assignee
Inventors
Key dates
| Filing date | Sep 9, 2008 |
| Grant date | Oct 18, 2011 |
| Priority date | — |
| Expiry date | May 29, 2030 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F2212/463
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
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.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.