Predictive cache replacement
AssigneeFacebook, Inc.
InventorEitan Frachtenberg
Life of this patent
Estimating the term…
Abstract
Systems and methods for predictive cache replacement policies are provided. In particular, some embodiments dynamically capture and predict access patterns of data to determine which data should be evicted from the cache. A novel tree data structure can be dynamically built that allows for immediate use in the identification of developing patterns and the eviction determination. In some cases, the data can be dynamically organized into histograms, strings, and other representations allowing traditional analysis techniques to be applied. Data organized into histogram-like structures can also be converted into strings allowing for well-known string pattern recognition analysis. The pattern recognition and prediction techniques disclosed also have applications outside of caching.
Claims20
A method, comprising:
- recording observations of data accesses from a cache;
- dynamically building a prediction model to predict future access patterns based on the recorded observations of data accesses,
- wherein the prediction model dynamically builds a dictionary of pattern prefixes based on the recorded observations of data accesses;
- analyzing observations of current data accesses from the cache to predict future access patterns by performing a partial pattern match using the dictionary of pattern prefixes,
- wherein the partial pattern match predicts one or more suffixes representing the predicted future access patterns;
- and
- evicting data from the cache based on the predicted future access patterns.
A system, comprising:
- a processor;
- a cache having data stored thereon;
- an observation engine, under control of the processor, to record data access observations regarding how the data is accessed within the cache;
- a prediction module, under control of the processor, to dynamically build a prediction model to predict future access patterns based on the recorded data access observations,
- wherein the prediction module builds the prediction model with a dictionary of pattern prefixes based on the recorded data access observations;
- and
- an eviction module, under control of the processor, to evict data from the cache which has the lowest value as scored by the prediction model.
A non-transitory computer-readable medium having instructions stored thereon that, when executed by one or more processors, cause a machine to:
- build a prediction model, using observations of data accesses from a cache, to predict future access patterns,
- wherein the prediction model includes a dictionary of pattern prefixes built from the observations of data accesses;
- analyze the observations of data accesses from the cache to predict future access patterns by performing a partial pattern match using the dictionary of pattern prefixes,
- wherein the partial pattern match predicts a suffix to the prefix using the dictionary of pattern prefixes;
- and
- wherein the suffix represents the predicted future access patterns;
- and
- evict data from the cache based on the predicted future access patterns identified by the suffix.
Dependencies are inferred from the claim text.