System and method for cache replacement using access-ordering lookahead approach

Patent metadata

Field	Value
Publication number	US-9684469-B1
Application number	US-201213460711-A
Country	US
Kind code	B1
Filing date	Apr 30, 2012
Priority date	Mar 12, 2012
Publication date	Jun 20, 2017
Grant date	Jun 20, 2017

Abstract

Data objects of a file are cached in a cache memory of a storage system. An access sequence of the cached data objects is determined based on metadata of the file. In response to a request for cache space reclamation, a data object is evicted from the cache memory whose next access is a farthest amongst the cached data objects based on the access sequence of the data objects.

First claim

What is claimed is:

1. A computer-implemented method for cache management of a storage system, the method comprising:
in response to a request for accessing a file stored in a storage system, identifying and retrieving a plurality of data objects associated with the file from a storage device of the storage system, wherein the data objects constitute at least a portion of the file;
caching the plurality of data objects of the file in a cache memory of the storage system;
determining an access sequence of the cached data objects within the file based on metadata of the file, wherein the access sequence represents a sequential order in time of accessing the cached data objects within the file, wherein the data objects are deduplicated data objects within the file, and wherein at least one of the data objects appears more than once within the file;
in response to a request for cache space reclamation, identifying one or more of the cached data objects whose next access is a farthest in time from a data object currently being accessed amongst the cached data objects within the file based on the access sequence of the data objects; and
evicting the identified one or more data objects from the cache memory whose next access is a farthest amongst the cached data objects within the file, including accessing an eviction candidate data structure to identify an eviction candidate, wherein the eviction candidate data structure comprises a Max Heap data structure, and wherein a next data object to be evicted from the cache memory is identified by popping an entry having a highest sequence number from the Max Heap data structure.

2. The method of claim 1 , wherein determining the access sequence of the cached data objects is performed based on a sequential access pattern of the file.

3. The method of claim 1 , further comprising predicting an access pattern of the file, wherein determining the access sequence of the cached data objects is performed based on the predicted access pattern of the file.

4. 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.

5. The method of claim 1 , further comprising:
generating access information for each data object based on the metadata of the file, the access information including sequential access order of the data object within the file; and
storing the access information in an access list associated with the data object, the access list including a list of sequence numbers, each sequence number representing a logical access time of the data object within the file.

6. The method of claim 5 , further comprising:
in response to an access of a first data object, identifying a next sequence number from a first access list associated with the first data object, the next sequence number representing a next logical time at which the first data object is accessed again within the file; and
storing the next sequence number in an entry associated with the first data object of the eviction candidate data structure.

7. The method of claim 6 , wherein the eviction candidate data structure includes one or more entries, each entry corresponding to one of the data objects.

8. The method of claim 6 , wherein evicting a data object from the cache memory comprises evicting a data object associated with an entry of the eviction candidate data structure that has a highest sequence number.

9. The method of claim 6 , wherein storing the next sequence number in an entry associated with the first data object of an eviction candidate data structure comprises:
obtaining an index of the entry associated with the first data object by hashing a fingerprint of the first data object using a predetermined hash function; and
storing the next sequence number in an entry of the eviction candidate data structure identified by the index.

10. The method of claim 1 , further comprising:
generating access information for each data object based on the metadata of the file, the access information including sequential access order of the data object within the file; and
storing the access information as an access list in an access information file, the access list including a list of object references and sequence numbers, each sequence number representing a logical access time of the data object subsequently occurring within the file.

11. The method of claim 10 , further comprising storing the access information with the metadata for the file, such that the access information is available when the file is accessed for reading.

12. A non-transitory computer-readable storage medium having instructions stored therein, which when executed by a processor, cause the processor to perform operations for cache management of a storage system, the operations comprising:
in response to a request for accessing a file stored in a storage system, identifying and retrieving a plurality of data objects associated with the file from a storage device of the storage system, wherein the data objects constitute at least a portion of the file;
caching the plurality of data objects of the file in a cache memory of the storage system;
determining an access sequence of the cached data objects within the file based on metadata of the file, wherein the access sequence represents a sequential order in time of accessing the cached data objects within the file, wherein the data objects are deduplicated data objects within the file, and wherein at least one of the data objects appears more than once within the file;
in response to a request for cache space reclamation, identifying one or more of the cached data objects whose next access is a farthest in time from a data object currently being accessed amongst the cached data objects within the file based on the access sequence of the data objects; and
evicting the identified one or more data objects from the cache memory whose next access is a farthest amongst the cached data objects within the file, including accessing an eviction candidate data structure to identify an eviction candidate, wherein the eviction candidate data structure comprises a Max Heap data structure, and wherein a next data object to be evicted from the cache memory is identified by popping an entry having a highest sequence number from the Max Heap data structure.

13. The non-transitory computer-readable storage medium of claim 12 , wherein determining the access sequence of the cached data objects is performed based on a sequential access pattern of the file.

14. The non-transitory computer-readable storage medium of claim 12 , wherein the operations further comprise predicting an access pattern of the file, and wherein determining the access sequence of the cached data objects is performed based on the predicted access pattern of the file.

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

16. The non-transitory computer-readable storage medium of claim 12 , wherein the operations further comprise:
generating access information for each data object based on the metadata of the file, the access information including sequential access order of the data object within the file; and
storing the access information in an access list associated with the data object, the access list including a list of sequence numbers, each sequence number representing a logical access time of the data object within the file.

17. The non-transitory computer-readable stora

Assignees

• Douglis Frederick
• Hsu Windsor W
• Qian Hangwei
• Emc Ip Holding Co Llc

Inventors

• Douglis Frederick
• Hsu Windsor W
• Qian Hangwei

Classifications

• G06F12/0276

  Generational garbage collection · CPC title

• G06F12/0866

  for peripheral storage systems, e.g. disk cache · CPC title

• G06F3/0641 Primary

  De-duplication techniques · CPC title

• G06F12/0871

  Allocation or management of cache space · CPC title

• G06F11/1453

  using de-duplication of the data · CPC title