# US 10,896,132 B1 · Systems and methods for prioritizing cache objects for deletion

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 10,896,132 B1
- Document ID: US10896132B1
- Status: Granted
- Kind: B1
- Application number: 15/980,770
- Filed: 2018-05-16
- Granted: 2021-01-19
- Earliest claimed: 2018-05-16
- Assignees: Veritas Technologies LLC
- Applicants: Veritas Technologies LLC
- Inventors: Jitendra Patidar; Anindya Banerjee
- Web page: https://patentgrep.com/patent/US10896132B1

## CPC

- G06F 12/0868: Data transfer between cache memory and other subsystems, e.g. storage devices or host systems
- G06F 12/0891: using clearing, invalidating or resetting means
- G06F 12/0895: of parts of caches, e.g. directory or tag array
- G06F 12/0897: with two or more cache hierarchy levels (with multilevel cache hierarchies G06F12/0811)
- G06F 12/128: adapted to multidimensional cache systems, e.g. set-associative, multicache, multiset or multilevel
- G06F 2212/1016: Performance improvement
- G06F 2212/1044: Space efficiency improvement
- G06F 2212/152: Virtualized environment, e.g. logically partitioned system
- G06F 2212/154: Networked environment
- G06F 2212/283: Plural cache memories
- G06F 2212/313: In storage device
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Provided computer-implemented methods for prioritizing cache objects for deletion may include (1) tracking, at a computing device, a respective time an externally-accessed object spends in an external cache, (2) queuing, when the externally-accessed object is purged from the external cache, the externally-accessed object in a first queue, (3) queuing, when an internally-accessed object is released, the internally-accessed object in a second queue, (4) prioritizing objects within the first queue, based on a cache-defined internal age factor and on respective times the objects spend in the external cache and respective times the objects spend in an internal cache, (5) prioritizing objects within the second queue based on respective times the objects spend in the internal cache, (6) selecting an oldest object having a longest time in any of the first queue and the second queue, and (7) deleting the oldest object. Various other methods, systems, and computer-readable media are disclosed.

## Claims

### Claim 1

A computer-implemented method for prioritizing cache objects for deletion, at least a portion of the method being performed by a computing device comprising at least one processor, the method comprising:
tracking, at the computing device, a respective time an externally-accessed object spends in an external cache;
queuing, when the externally-accessed object is purged from the external cache, the externally-accessed object in a first queue;
setting, when the externally-accessed object is purged, a respective unhold flag;
queuing, when an internally-accessed object is released, the internally-accessed object in a second queue;
setting, when the externally-accessed object in the first queue re-accessed internally, a respective hold flag;
transferring, when the externally-accessed object in the first queue having both a respective hold flag and a respective unhold flag set is released, the externally-accessed object to a third queue;
prioritizing objects within the first queue, based on a cache-defined internal age factor and on respective times the objects in the first queue spend in the external cache and respective times the objects in the first queue spend in an internal cache;
prioritizing objects within the second queue based on respective times the objects in the second queue spend in the internal cache;
prioritizing objects within the third queue based on respective times the objects in the third queue spend in the internal cache;
selecting an oldest object having a longest time in any of the first queue, the second queue, and the third queue; and
deleting the oldest object.

### Claim 2 (depends on 1)

The computer-implemented method of claim 1, further comprising:
setting the respective hold flag when the externally-accessed object is initially accessed externally; and
clearing, when the externally-accessed object is purged, the respective hold flag.

### Claim 3 (depends on 1)

The computer-implemented method of claim 1, wherein at least one of the externally-accessed object and the internally-accessed object is an inode data structure.

### Claim 4 (depends on 1)

The computer-implemented method of claim 1, wherein at least one of the internal cache and the external cache is an inode cache.

### Claim 5 (depends on 4)

The computer-implemented method of claim 4, wherein the inode cache is in a file system layer, an operating system layer, or a network file system layer.

### Claim 6 (depends on 1)

The computer-implemented method of claim 1, wherein the deleting is initiated by at least one of a system memory reaching maximum capacity and an in-core cache reaching maximum capacity.

### Claim 7

A system for prioritizing cache objects for deletion, the system comprising:
a tracking module, stored in memory, that tracks a respective time an externally-accessed object spends in an external cache;
a first queuing module, stored in the memory, that queues, when the externally-accessed object is purged from the external cache, the externally-accessed object in a first queue;
a first setting module, stored in the memory, that sets, when the externally-accessed object is purged, a respective unhold flag;
a second queuing module, stored in the memory, that queues, when an internally-accessed object is released, the internally-accessed object in a second queue;
a second setting module, stored in the memory, that sets, when the externally-accessed object in the first queue re-accessed internally, a respective hold flag;
a transferring module, stored in the memory, that transfers, when the externally-accessed object in the first queue having both a respective hold flag and a respective unhold flag set is released, the externally-accessed object to a third queue;
a first prioritizing module, stored in the memory, that prioritizes objects within the first queue, based on a cache-defined internal age factor and on respective times the objects in the first queue spend in the external cache and respective times the objects in the first queue spend in an internal cache;
a second prioritizing module, stored in the memory, that prioritizes objects within the second queue based on respective times the objects in the second queue spend in the internal cache;
a third prioritizing module, stored in the memory, that prioritizes objects within the third queue based on respective times the objects in the third queue spend in the internal cache;
a selecting module, stored in the memory, that selects an oldest object having a longest time in any of the first queue, the second queue, and the third queue;
a deleting module, stored in the memory, that deletes the oldest object; and
at least one physical processor that executes the tracking module, the first queuing module, the first setting module, the second queuing module, the second setting module, the transferring module, the first prioritizing module, the second prioritizing module, the third prioritizing module, the selecting module, and the deleting module.

### Claim 8 (depends on 7)

The system of claim 7, further comprising:
a third setting module, stored in the memory, that sets the respective hold flag when the externally-accessed object is initially accessed externally; and
a clearing module, stored in the memory, that clears, when the externally-accessed object is purged, the respective hold flag.

### Claim 9 (depends on 7)

The system of claim 7, wherein at least one of the externally-accessed object and the internally-accessed object is an inode data structure.

### Claim 10 (depends on 7)

The system of claim 7, wherein at least one of the internal cache and the external cache is an inode cache.

### Claim 11 (depends on 10)

The system of claim 10, wherein the inode cache is in a file system layer, an operating system layer, or a network file system layer.

### Claim 12 (depends on 7)

The system of claim 7, wherein the deleting is initiated by at least one of a system memory reaching maximum capacity and an in-core cache reaching maximum capacity.

### Claim 13

A non-transitory computer-readable medium comprising one or more computer-executable instructions that, when executed by at least one processor of a computing device, cause the computing device to:
track, at the computing device, a respective time an externally-accessed object spends in an external cache;
queue, when the externally-accessed object is purged from the external cache, the externally-accessed object in a first queue;
set, when the externally-accessed object is purged, a respective unhold flag;
queue, when an internally-accessed object is released, the internally-accessed object in a second queue;
set, when the externally-accessed object in the first queue re-accessed internally, a respective hold flag;
transfer, when the externally-accessed object in the first queue having both a respective hold flag and a respective unhold flag set is released, the externally-accessed object to a third queue;
prioritize objects within the first queue based on a cache-defined internal age factor and on respective times the objects in the first queue spend in the external cache and respective times the objects in the first queue spend in an internal cache;
prioritize objects within the second queue based on respective times the objects in the second queue spend in the internal cache;
prioritize objects within the third queue based on respective times the objects in the third queue spend in the internal cache;
select an oldest object having a longest time in any of the first queue, the second queue, and the third queue; and
delete the oldest object.

### Claim 14 (depends on 13)

The non-transitory computer-readable medium of claim 13, wherein the computer-executable instructions further comprise computer-executable instructions that cause the computing device to:
set the respective hold flag when the externally-accessed object is initially accessed externally; and
clear, when the externally-accessed object is purged, the respective hold flag.

### Claim 15 (depends on 13)

The non-transitory computer-readable medium of claim 13, wherein at least one of the externally-accessed object and the internally-accessed object is an inode data structure.

### Claim 16 (depends on 13)

The non-transitory computer-readable medium of claim 13, wherein at least one of the internal cache and the external cache is an inode cache.

### Claim 17 (depends on 16)

The non-transitory computer-readable medium of claim 16, wherein the inode cache is in a file system layer, an operating system layer, or a network file system layer.
