# US 2015/0106570 A1 · Cache method and cache apparatus

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

- Number: US 2015/0106570 A1
- Document ID: US20150106570A1
- Status: Published application
- Kind: A1
- Application number: 14/494,217
- Filed: 2014-09-23
- Published: 2015-04-16
- Earliest claimed: 2013-10-10
- Assignees: Fujitsu Limited
- Applicants: Fujitsu Limited
- Inventors: Toshihiro Shimizu
- Web page: https://patentgrep.com/patent/US20150106570A1

## CPC

- G06F 12/121: using replacement algorithms
- G06F 12/0891: using clearing, invalidating or resetting means
- G06F 12/12: Replacement control
- G06F 12/0866: for peripheral storage systems, e.g. disk cache
- G06F 12/122: of the least frequently used [LFU] type, e.g. with individual count value
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A cache apparatus stores part of a plurality of accessible data blocks into a cache area. A calculation part calculates, for each pair of data blocks of the plurality of data blocks, an expected value of the number of accesses made after one of the data blocks is accessed until the other of the data blocks is accessed, on the basis of a probability that when each of the plurality of data blocks is accessed, each data block that is likely to be accessed next is accessed next. When a data block is read from outside the cache area, a determination part determines a data block to be discarded from the cache area, on the basis of the expected value of the number of accesses made after the read data block is accessed until each of the plurality of data blocks is accessed.

## Claims

### Claim 1

A non-transitory computer-readable storage medium storing a caching program that causes a computer to execute a process comprising:
storing part of a plurality of accessible data blocks into a cache area of a storage device;
calculating, for each pair of data blocks of the plurality of data blocks, an expected value of a number of accesses made after one of the data blocks is accessed until the other one of the data blocks is accessed, based on a probability that when each of the plurality of data blocks is accessed, each data block that is likely to be accessed next is accessed next; and
determining, in response to a data block being read from outside the cache area according to an access request to the data block, a data block to be discarded from the cache area, based on the expected value of the number of accesses made after the read data block is accessed until each of the plurality of data blocks is accessed.

### Claim 2 (depends on 1)

The non-transitory computer-readable storage medium according to claim 1, wherein the calculating includes calculating the expected value by generating a transition matrix based on the probability that when each of the plurality of data blocks is accessed, each data block that is likely to be accessed next is accessed next, and by performing a matrix calculation using the generated transition matrix.

### Claim 3 (depends on 1)

The non-transitory computer-readable storage medium according to claim 1, wherein the determining a data block to be discarded includes determining a data block having a highest expected value as the data block to be discarded.

### Claim 4 (depends on 1)

The non-transitory computer-readable storage medium according to claim 1, the procedure further comprising:
determining, for each of the plurality of data blocks, a priority order for discard of the other data blocks upon reading the data block from outside the cache area, based on the expected value of the number of accesses made until each of the plurality of data blocks is accessed after each of the other data blocks is accessed; and
storing the determined priority order into the storage device;
wherein the determining a data block to be discarded includes determining, in response to the data block being read from outside the cache area, a data block to be discarded, based on the priority order for discard upon reading the data block.

### Claim 5 (depends on 4)

The non-transitory computer-readable storage medium according to claim 4, wherein:
the storing includes arranging pieces of identification information of a predetermined number of data blocks having lowest expected values, in the priority order for discard, and storing the arranged pieces of identification information; and
the determining a data block to be discarded includes determining, in response to the data block being read from outside the cache, when a data block that is not listed in the priority order for discard upon reading the data block is present in the cache area, the data block that is not listed in the priority order for discard as a data block to be discarded, and determining, when a data block that is not listed in the priority order for discard upon reading the data block is not present in the cache area, a data block having a highest priority among the data blocks stored in the cache area as a data block to be discarded.

### Claim 6 (depends on 1)

The non-transitory computer-readable storage medium according to claim 1, wherein the calculating includes calculating the expected value based on transition probabilities in a Markov chain in which an access to a data block is defined as a state transition.

### Claim 7 (depends on 6)

The non-transitory computer-readable storage medium according to claim 6, wherein the calculating includes calculating the expected value based on transition probabilities in a higher-order Markov chain in which a plurality of accesses to a predetermined number of data blocks are defined as a state transition.

### Claim 8 (depends on 1)

The non-transitory computer-readable storage medium according to claim 1, wherein the calculating includes approximating the expected value.

### Claim 9

A cache method executed by a computer, the cache method comprising:
storing, by a processor, part of a plurality of accessible data blocks into a cache area of a storage device;
calculating, by the processor, for each pair of data blocks of the plurality of data blocks, an expected value of a number of accesses made after one of the data blocks is accessed until the other one of the data blocks is accessed, based on a probability that when each of the plurality of data blocks is accessed, each data block that is likely to be accessed next is accessed next; and
determining, by the processor, in response to a data block being read from outside the cache area according to an access request to the data block, a data block to be discarded from the cache area, based on the expected value of the number of accesses made after the read data block is accessed until each of the plurality of data blocks is accessed.

### Claim 10

A cache apparatus comprising:
a processor configured to execute a process including:
storing part of a plurality of accessible data blocks into a cache area of a storage device;
calculating, for each pair of data blocks of the plurality of data blocks, an expected value of a number of accesses made after one of the data blocks is accessed until the other one of the data blocks is accessed, based on a probability that when each of the plurality of data blocks is accessed, each data block that is likely to be accessed next is accessed next, and
determining, in response to a data block being read from outside the cache area according to an access request to the data block, a data block to be discarded from the cache area, based on the expected value of the number of accesses made after the read data block is accessed until each of the plurality of data blocks is accessed.
