System and method for cache replacement using bloom filter lookahead approach

Patent metadata

Field	Value
Publication number	US-9110792-B1
Application number	US-201213460722-A
Country	US
Kind code	B1
Filing date	Apr 30, 2012
Priority date	Mar 12, 2012
Publication date	Aug 18, 2015
Grant date	Aug 18, 2015

Abstract

Data objects of a file are cached in a cache memory of a storage system, where the data objects of the file are accessed sequentially via access windows in a chain. It is estimated whether a next access of a data object of the file likely occurs in which of the access windows using respective bloom filters associated with the access windows. In response to a request for cache space reclamation, a data object is evicted from the cache memory that will be likely accessed in a farthest access window in the chain from a current access window based on the estimation.

First claim

What is claimed is:

1. A computer-implemented method for cache management of a storage system, the method comprising:
caching a plurality of data objects of a file in a cache memory of a storage system, the plurality of the data objects of the file to be accessed sequentially via a plurality of access windows in a chain;
estimating whether a next access of a data object of the file likely occurs in which of the access windows using respective bloom filters associated with the access windows; and
in response to a request for cache space reclamation, evicting a data object from the cache memory that will likely be accessed in a farthest access window in the chain from a current access window based on the estimation, wherein evicting a data object from the cache memory based on the estimation comprises evicting any data object identified in a garbage list from the cache memory before evicting any data object identified from the access windows, wherein the garbage list stores one or more data objects that are not referenced within any of the access windows.

2. The method of claim 1 , further comprising:
for given one of the access windows in the chain, examining an access list associated with the access window to identify a second data object that is likely accessed within the access window; and
evicting the second data object from the cache memory if the second data object is listed in the access list of the access window.

3. The method of claim 2 , further comprising iteratively performing examining the access list for each of the access windows, starting from a farthest access window to a nearest access window in the chain, until a second access window is found in the chain whose access list contains at least one data object.

4. The method of claim 3 , further comprising identifying and evicting a data object from the current access window based on access ordering of data objects associated with the current access window, if the second access window cannot be found.

5. The method of claim 1 , wherein the plurality of data objects are deduplicated data objects that are stored in a storage device of the storage system.

6. The method of claim 1 , wherein estimating whether a next access of a data object of the file likely occurs in which of the access windows comprises:
for given one of the access windows in the chain, applying a corresponding bloom filter on metadata of the data object to generate an output; and
indicating in an access list associated with the access window based on the output to indicate whether the data object is likely accessed within the access window.

7. The method of claim 6 , further comprising iteratively performing applying the corresponding bloom filter and indicating in the associated access list for each of the access windows, starting from a nearest access window to a farthest access window in the chain, until a first access window is found in the chain whose output from its corresponding bloom filter indicates that the data object is likely accessed within the first access window.

8. The method of claim 7 , further comprising indicating in a garbage list that the data object is not referenced, if none of the access windows in the chain has been found that the data object is likely accessed.

9. A non-transitory computer-readable storage medium having instructions stored therein, which when executed by a processor, cause the processor to perform a method for cache management of a storage system, the method comprising:
caching a plurality of data objects of a file in a cache memory of a storage system, the plurality of the data objects of the file to be accessed sequentially via a plurality of access windows in a chain;
estimating whether a next access of a data object of the file likely occurs in which of the access windows using respective bloom filters associated with the access windows; and
in response to a request for cache space reclamation, evicting a data object from the cache memory that will likely be accessed in a farthest access window in the chain from a current access window based on the estimation, wherein evicting a data object from the cache memory based on the estimation comprises evicting any data object identified in a garbage list from the cache memory before evicting any data object identified from the access windows, wherein the garbage list stores one or more data objects that are not referenced within any of the access windows.

10. The non-transitory computer-readable storage medium of claim 9 , wherein the operations further comprise:
for given one of the access windows in the chain, examining an access list associated with the access window to identify a second data object that is likely accessed within the access window; and
evicting the second data object from the cache memory if the second data object is listed in the access list of the access window.

11. The non-transitory computer-readable storage medium of claim 10 , wherein the operations further comprise iteratively performing examining the access list for each of the access windows, starting from a farthest access window to a nearest access window in the chain, until a second access window is found in the chain whose access list contains at least one data object.

12. The non-transitory computer-readable storage medium of claim 11 , wherein the operations further comprise identifying and evicting a data object from the current access window based on access ordering of data objects associated with the current access window, if the second access window cannot be found.

13. The non-transitory computer-readable storage medium of claim 9 , wherein the plurality of data objects are deduplicated data objects that are stored in a storage device of the storage system.

14. The non-transitory computer-readable storage medium of claim 9 , wherein estimating whether a next access of a data object of the file likely occurs in which of the access windows comprises:
for given one of the access windows in the chain, applying a corresponding bloom filter on metadata of the data object to generate an output; and
indicating in an access list associated with the access window based on the output to indicate whether the data object is likely accessed within the access window.

15. The non-transitory computer-readable storage medium of claim 14 , wherein the operations further comprise iteratively performing applying the corresponding bloom filter and indicating in the associated access list for each of the access windows, starting from a nearest access window to a farthest access window in the chain, until a first access window is found in the chain whose output from its corresponding bloom filter indicates that the data object is likely accessed within the first access window.

16. The non-transitory computer-readable storage medium of claim 15 , wherein the operations further comprise indicating in a garbage list that the data object is not referenced, if none of the access windows in the chain has been found that the data object is likely accessed.

17. A storage system, comprising:
a cache memory to cache a plurality of data objects of a file in a cache memory of a storage system, the plurality of the data objects of the file to be accessed sequentially via a plurality of access windows in a chain;
an access predictor to estimate whether a next access of a data object of the file likely occurs in which of the access windows using respective bloom filters associated with the access windows; and
an access manager, in response to a request for cache space reclamation, to evict a data

Assignees

• Douglis Frederick
• Hsu Windsor W
• Qian Hangwei
• Emc Corp

Inventors

• Douglis Frederick
• Hsu Windsor W
• Qian Hangwei

Classifications

• G06F12/0276

  Generational garbage collection · CPC title

• G06F12/0269 Primary

  Incremental or concurrent garbage collection, e.g. in real-time systems (G06F12/0261 takes precedence) · CPC title

• G06F11/1453

  using de-duplication of the data · CPC title

• G06F3/0641 Primary

  De-duplication techniques · CPC title

• G06F12/0871

  Allocation or management of cache space · CPC title