# US 10,503,423 B1 · System and method for cache replacement using access-ordering lookahead approach > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,503,423 B1 - Document ID: US10503423B1 - Status: Granted - Kind: B1 - Application number: 15/598,229 - Filed: 2017-05-17 - Granted: 2019-12-10 - Earliest claimed: 2012-03-12 - Assignees: EMC IP Holding Company LLC - Applicants: EMC IP Holding Company LLC - Inventors: Frederick Douglis; Windsor W. Hsu; Hangwei Qian - Web page: https://patentgrep.com/patent/US10503423B1 ## CPC - G06F 3/0641: {De-duplication techniques} - G06F 11/1453: {using de-duplication of the data} - G06F 12/0269: {Incremental or concurrent garbage collection, e.g. in real-time systems (G06F12/0261 takes precedence)} - G06F 12/0276: {Generational garbage collection} - G06F 12/121: using replacement algorithms - G06F 12/123: with age lists, e.g. queue, most recently used [MRU] list or least recently used [LRU] list - G06F 12/0866: for peripheral storage systems, e.g. disk cache - G06F 12/0871: Allocation or management of cache space - G06F 2212/466: Metadata, control data - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract In response to a request for accessing a file stored in a storage system, data objects associated with the file are retrieved from a storage device of the storage system. The data objects of the file are cached in a cache memory. An access sequence of the cached data objects within the file is determined based on metadata of the file, where the access sequence represents a sequential order in time of accessing the cached data objects within the file. In response to a request for cache space reclamation, one or more cached data objects are identified whose next access is a farthest in time from a data object currently being accessed amongst the cached data objects based on the access sequence of the data objects. The identified data objects are evicted from the cache memory whose next access is a farthest amongst the cached data objects. ## Claims ### Claim 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. ### Claim 2 (depends on 1) 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. ### Claim 3 (depends on 1) 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. ### Claim 4 (depends on 1) 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. ### Claim 5 (depends on 1) 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. ### Claim 6 (depends on 5) 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. ### Claim 7 (depends on 6) 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. ### Claim 8 (depends on 6) 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. ### Claim 9 (depends on 6) 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. ### Claim 10 (depends on 1) 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. ### Claim 11 (depends on 10) 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. ### Claim 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. ### Claim 13 (depends on 12) 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. ### Claim 14 (depends on 12) 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. ### Claim 15 (depends on 12) 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. ### Claim 16 (depends on 12) 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. ### Claim 17 (depends on 16) The non-transitory computer-readable storage medium of claim 16, wherein the operations further comprise: 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. ### Claim 18 (depends on 17) The non-transitory computer-readable storage medium of claim 17, wherein the eviction candidate data structure includes one or more entries, each entry corresponding to one of the data objects. ### Claim 19 (depends on 17) The non-transitory computer-readable storage medium of claim 17 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. ### Claim 20 (depends on 17) The non-transitory computer-readable storage medium of claim 17, 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. ### Claim 21 (depends on 12) 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 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. ### Claim 22 (depends on 21) The non-transitory computer-readable storage medium of claim 21, wherein the operations further comprise storing the access information with the metadata for the file, such that the access information is available when the file is accessed for reading. ### Claim 23 A data processing system, comprising: a storage device to store a plurality of files; a cache memory to cache a plurality of data objects of a file stored in the storage device, wherein the data objects constitute at least a portion of the file, and wherein at least one of the data objects occurs more than once within the file; an access predictor to determine 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; and an access manager, in response to a request for cache space reclamation, to identify a cached data object 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 to evict the identified data object from the cache memory whose next access is a farthest amongst the cached data objects within the file. ### Claim 24 (depends on 23) The system of claim 23, wherein determining the access sequence of the cached data objects is performed based on a sequential access pattern of the file. ### Claim 25 (depends on 23) The system of claim 23, wherein the access predictor is further configured to predict 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.