System and method for managing large filesystem-based caches
US8438336B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Sep 20, 2011 |
| Grant date | May 7, 2013 |
| Priority date | — |
| Expiry date | Nov 1, 2031 |
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.