Method and apparatus for cache management

There exists a continuous need in the data processing field to increase the efficiency of short-term storage space. That is, with cache management, there is a need to increase the amount of data that can be stored within a storage unit without incurring additional costs in providing larger storage units.

When improving the efficiency of a cache device, one property to consider is that more frequently accessed data should be given a higher priority than less frequently accessed data.

What is needed is a cache management technique that increases the efficiency of a cache storage device and gives priority to the more frequently accessed data.

FIG. 1 is a flow diagram describing the operations of cache management according to one embodiment.

FIG. 2 is a diagram describing the operations of generating a recall value according to one embodiment.

FIG. 3 is diagram of a system capable of implementing the operations of cache management according to one embodiment.

The present application describes a cache management operation. In one embodiment, data is stored within a storage device in an order according to the frequency the data is accessed. In one embodiment, the storage device is a cache storage device, providing storage of data for faster access relative to a larger secondary storage device.

FIG. 1 provides a flow diagram describing the operation of managing data in storage device according to one embodiment. Initially, a recall value for a first unit of data is generated ( 102 ). In one embodiment, the recall value is a representation of the frequency the unit of data is accessed. A recall value for a second unit of data is also generated ( 104 ). The recall value for the first unit of data is compared with the recall value for the second unit of data ( 106 ).

The unit of data with the higher recall value is selected to be stored in a first section of the storage unit ( 108 ). The unit of data with the lower recall value is selected to be stored in a second subsequent section of the storage unit ( 110 ). The unit of data selected to be stored in the second section of the storage will be compressed, by an amount greater than the data selected to be stored in the first section of the storage unit ( 112 ).

In one embodiment, the data selected to be stored in the first section of the storage device is not compressed, but the data to be stored in the second section of the storage device is compressed. In an alternative embodiment, the data selected to be stored in the first section undergoes a first rate of compression, and data selected to be stored in the second section of the storage device undergoes a second rate of compression, greater than the first rate of compression.

In one embodiment, the operations described above are repeated following the elapse of a predetermined period of time. Moreover, the operations discussed above may be performed in parallel. For example, the generating the recall value of the first data unit and generating the recall value of the second data unit may be done in parallel.

Furthermore, the operations described above are applicable to a group of data units larger than 2. Moreover, in one embodiment, more than one unit of data may be stored in the same section of the storage device. As a result, in one embodiment, when more than one unit of data are stored in the same section of the storage device, the multiple units of data stored in the same section undergo the same rate of compression.

FIG. 2 provides a diagram describing the operations of generating a recall value according to one embodiment. In one embodiment, a predetermined recall value is assigned to a unit of data when the unit of data is initially accessed, before the unit of data has been stored in the storage unit ( 202 ). For example, a recall value of 1 may be assigned to a unit of data when the unit of data is initially accessed.

In one embodiment, each time a unit of data is accessed, the recall value for the respective unit of data is incremented by a predetermined amount ( 204 ). For example, each time a unit of data is accessed, the recall value for the respective unit of data may be incremented by 1.

In one embodiment, the recall value of each unit of data stored in the storage device is decremented by predetermined amount following the elapse of a predetermined period of time, regardless of how many times it may have been accessed during the predetermined period of time ( 206 ). For example, each unit of data stored in the storage unit may be decremented by 10% every 1 second. Therefore, in one embodiment, data that is not accessed will eventually have a recall value below a predetermined threshold and be removed from the storage device.

In one embodiment, the recall value could be stored along with the respective units of data in the storage device. Alternatively, the recall values could be stored separately as a table in a separate storage device.

The operations described above can be stored in the memory of a computer system as a set of instructions to be executed, as illustrated in FIG. 3 . In addition, the instructions to perform the operations described above could alternatively be stored on other forms of machine-readable media, including magnetic and optical disks. For example, the operations of one embodiment could be stored on machine-readable media, such as magnetic disks or optical disks, which are accessible via a disk drive (or computer-readable medium drive). Further, the instructions can be downloaded into a computing device over a data network in a form of compiled and linked version.

Alternatively, the logic to perform the operations as discussed above, could be implemented in additional computer and/or machine readable media, such as discrete hardware components as large-scale integrated circuits (LSI's), application-specific integrated circuits (ASIC's), firmware such as electrically erasable programmable read-only memory (EEPROM's); and electrical, optical, acoustical and other forms of propagated signals (e.g., carrier waves, infrared signals, digital signals, etc.); etc.

Although the present invention has been described with reference to specific exemplary embodiments, it will be evident that various modifications and changes may be made to these embodiments without departing from the broader spirit and scope of the invention. Accordingly, the specification and drawings are to be regarded in an illustrative rather than a restrictive sense.