Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
2000-05-04
2004-05-25
Yoo, Do Hyun (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C711S134000, C711S135000, C711S136000, C711S171000
Reexamination Certificate
active
06742084
ABSTRACT:
TECHNICAL FIELD
The present invention relates generally to computer data storage and, more particularly, to data caching methods for managing the contents of a cache that holds data blocks of different sizes, such as the disk cache of a virtual tape subsystem.
BACKGROUND ART
A data-storage technology that offers more performance typically costs more as well. For example, semiconductor memory has better performance (faster response time) than magnetic disk, but also costs more; magnetic disk, in turn, has better performance than magnetic tape, but also costs more. Data caching is a technique for using two data-storage devices technologies in a way that provides performance approximating that of the higher-performing technology at a cost approximating that of the less expensive technology. This is accomplished by using a relatively small amount of the more expensive technology in combination with a large amount of the less expensive technology, but taking steps to ensure that the data that is accessed most frequently is stored in the higher-performing technology. The relatively small amount of storage provided by the more expensive, higher-performing technology is called the cache.
Two steps are taken to ensure that frequently accessed data can be found in the cache. First, every time a data block is requested, that block is moved to the cache if it is not already there, so that it will be available from the cache if it is requested again in the not too distant future. Second, the data blocks that are removed from the cache when it is necessary to make room for incoming blocks are chosen in accordance with a rule that is designed to maximize performance; this rule is known as a block-replacement algorithm and is referred to herein as a caching method.
The best known and most widely used caching method is the Least Recently Used (LRU) algorithm, which selects the least recently used data block (the block in the cache that has gone unused for the longest time) for removal from the cache. This ensures that a data block brought into the cache will stay there as long as can be justified by its frequency of use.
In most caches, the data blocks either all have the same size or have sizes that span a relatively narrow range. As an example of the latter case, the semiconductor cache of a disk storage subsystem is typically divided into slots of fixed size, and a given data block may occupy one to two or three of these cache slots. A very different situation holds in a virtual tape subsystem, where the data blocks (virtual tape volumes) may range in size from 0.1 megabyte, or even smaller, to hundreds of megabytes, or even larger.
A virtual tape subsystem looks just like a conventional tape subsystem to an application. However, when an application thinks it is writing a file to tape, the virtual tape subsystem is actually storing the data on magnetic disk in a logical entity known as a virtual tape volume. Apart from a nominal overhead, the size of the virtual volume is the same as the size of the user's file (either before or after data compression, depending on the implementation). As virtual volumes accumulate in the disk buffer, they are periodically migrated to physical tape in a way conducive to efficient use of tape drives and tape capacity.
The disk buffer of a virtual tape subsystem functions as a cache for virtual tape volumes. When an application requests a virtual volume that is in this cache (a “cache hit”), the requested volume can be accessed quickly because the volume is resident on a direct-access storage device. When an application requests a virtual volume that is no longer in the cache (a “cache miss”), that volume must be read into the cache from tape, which typically requires a mount of a tape, a search on the tape to the requested virtual volume, and then the transfer of that volume to the cache. The time required for the mount, the search, and the data transfer is the “miss penalty,” the amount by which the response time for a cache miss exceeds that for a cache hit.
In view of the substantial miss penalty, it is important that the cache be used effectively to keep the overall mean response time as low as possible. However, it is not obvious how to do this when, as in a virtual tape subsystem, the entities that vie for space in the cache extend over a wide range in size. A large data block (virtual volume in the case of virtual tape) takes up a lot of cache space that might be used to store hundreds of smaller blocks. To control the number of cache misses, therefore, a large block must be allowed to remain in the cache only as long as the high cost in cache space can be justified by the expected benefit of its presence in the cache. The standard LRU caching method will not suffice as it does not take block size into account.
Furthermore, keeping the mean response time as low as possible is not simply a matter of minimizing the number of cache misses. The miss penalty is larger for a large block than for a small block owing to the increased time required to read (“stage”) the larger block into the cache.
What is needed for a virtual tape subsystem, or any cached storage subsystem where the data blocks extend over a wide range in size, is a caching method that takes the size of the data blocks into account to achieve the best possible performance and is flexible enough that it can be used either to maximize the cache hit ratio (the fraction of block references that are cache hits) or to minimize the overall mean response time.
SUMMARY OF THE INVENTION
Accordingly, it is an object of the present invention to provide a caching method that boosts cache performance over the standard LRU caching method when data blocks that are candidates for storage in the cache extend over a significant size range.
It is another object of the present invention to provide a caching method in which a data block flushed from the cache will always be the least recently used of all the cached blocks within a given size range but not necessarily the least recently used of all the blocks in the cache.
It is a further object of the present invention to provide a caching method that selects cached blocks for removal based on their size and likelihood that they will soon be referenced.
In carrying out the above objects and other objects, features, and advantages, the present invention provides a caching method for selecting data blocks for removal from a cache. The caching method is for use in a virtual tape subsystem or any other cached system of computer data storage in which the data blocks are of variable size.
The caching method includes determining the size and the unreferenced time interval of each data block in the cache. The size of a data block is the amount of cache space taken up by the block. The unreferenced time interval of a data block is the time that has elapsed since the block was last accessed (including the case where the “access” was actually the creation of the block). The recall probability per unit time of each data block in the cache is then determined. The recall probability of a data block is a function of its unreferenced time interval and possibly size and other parameters as well. The caching method then determines a quality factor (q) for each data block. The quality factor (q) of a data block is a function of its recall probability and size. The caching method concludes with removing from the cache the data block with the lowest quality factor (q).
The advantages accruing to the present invention are numerous. The caching method can be used to enhance various performance metrics such as the cache hit ratio, the mean response time, and the bandwidth consumed by the staging activity. The optimal caching strategies for all three metrics can be implemented with the general caching method; selection of the metric to be optimized is accomplished simply by assigning values to a few constants. Further, the caching method can be customized to the data access patterns of a given site by using recall probabilities estimated from access statistics for that site.
These a
Defouw Richard J.
Korngiebel Ronald W.
Sutton Alan
Brooks & Kushman P.C.
Namazi Mehdi
Storage Technology Corporation
Yoo Do Hyun
LandOfFree
Caching method for selecting data blocks for removal from... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Caching method for selecting data blocks for removal from..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Caching method for selecting data blocks for removal from... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3208801