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.
Claims19
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 observations of data accesses are represented as a tree data structure that includes a plurality of nodes with each node representing a cumulative distinct key count,
- wherein the partial pattern match predicts one or more suffixes representing the predicted future access patterns;
- monitoring the plurality of nodes for a current key count of zero, wherein recording the observations of data accesses includes identifying a data access pattern associated with a key associated with the current key count of zero;
- upon determining that the data accesses are associated with insertion of data into the cache within a time interval of recording the observations of the data accesses, exempting eviction of the inserted data;
- and
- evicting data from the cache based on the predicted future access patterns.
A system, comprising:
- a processor;
- and
- a cache having data stored thereon, wherein the processor has instructions stored thereon configured to:
- record data access observations regarding how the data is accessed within the cache,
- wherein the observations of data accesses are represented as a tree data structure that includes a plurality of nodes with each node representing a cumulative distinct key count;
- 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;
- monitor the plurality of nodes for a current key count of zero, wherein recording the observations of data accesses includes identifying a data access pattern associated with a key associated with the current key count of zero;
- upon determining that the data accesses are associated with insertion of data into the cache within a time interval of recording the observations of the data accesses, exempt eviction of the inserted data;
- and
- 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 computing device 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 observations of data accesses are represented as a tree data structure that includes a plurality of nodes with each node representing a cumulative distinct key count,
- wherein the partial pattern match predicts a suffix to the prefix using the dictionary of pattern prefixes,
- wherein the suffix represents the predicted future access patterns;
- monitor the plurality of nodes for a current key count of zero, wherein recording the observations of data accesses includes identifying a data access pattern associated with a key associated with the current key count of zero;
- and
- upon determining that the data accesses are associated with insertion of data into the cache within a time interval of recording the observations of the data accesses, exempting eviction of the inserted data;
- and evict data from the cache based on the predicted future access patterns identified by the suffix.
Dependencies are inferred from the claim text.