Algorithm for cache replacement

Details Algorithm for cache replacement Algorithm for cache replacement

1997-10-27

2001-07-24

Nguyen, Hiep T. (Department: 2187)

Electrical computers and digital processing systems: memory

Storage accessing and control

Hierarchical memories

C711S136000, C711S137000, C711S143000, C711S145000

Reexamination Certificate

active

06266742

ABSTRACT:

BACKGROUND OF THE INVENTION
Caching is commonly used for improving computer performance when the system is frequently accessing objects which require significant time to fetch or create. By caching an object, the cost for fetching or creating the object is only incurred once. Subsequent requests for a cached object can then be satisfied from the cache, a process which incurs significantly less overhead than recalculating the object or fetching it from a remote location.
In many cases, caches are of finite size. Selectivity must be applied in determining which objects should be cached when the cache is full or almost full. The subject invention provides a method for determining which objects should be placed in a cache. It is particularly (but not exclusively) useful when multiple parameters affecting the desirability of caching objects vary for different objects. Such parameters include the frequency with which an object is accessed, object size, the time to calculate an object, or the time to fetch the object from a remote location, and the lifetime (i.e. time between updates) of an object.
Caching is particularly useful for improving performance in the World Wide Web. Several types of caching are currently being utilized to cache Web-retrieved objects which could make use of the present invention, including server caching, proxy caching and browser caching. Web server performance is often poor when the percentage of dynamic pages generated by the server is high (see “An Analysis of Web Server Performance” by A. Iyengar et. al., “Proceedings of GLOBECOM '97”, November 1997). In order to improve performance, server caching of local dynamic data is utilized. In server caching, the server generating dynamic pages can cache dynamic pages so that they only have to be generated once (see “Improving Web Server Performance by Caching Dynamic Data”, A. Iyengar and J. Challenger, “Proceedings of the Usenix Symposium on Internet Technologies and Systems”, December 1997).
Another caching scheme is to have a proxy server cache documents from remote servers. Using proxy caching, the proxy server will be able to satisfy requests for documents without having to remotely fetch a document for each request (see “Caching Proxies: Limitations and Potentials” by M. Abrams et. al., “Fourth International World Wide Web Conference Proceedings”, December 1996, pp. 119-133; and “World Wide Web Proxies” by A. Luotonen and K. Altis in “Computer Networks and ISDN Systems”, vol. 27 (1994), pp. 147-154). Finally, browser caching is often used wherein web browsers cache recently requested documents and images both in main memory and on disk.
A number of cache replacement algorithms have been proposed in the literature (see “A Case for Delay-Conscious Caching of Web Documents”, P. Scheuermann et. al., Sixth International World Wide Web Conference Proceedings, 1997; “Performance Engineering of the World Wide Web: Application to Dimensioning and Cache Design”, J. Bolot and P. Hoschka, “World Wide Web Journal”, Summer 1996, pp. 185-195; “Proxy Caching That Estimates Page Load Delays”,R. P. Wooster and M. Abrams, “Sixth International World Wide Web Conference Proceedings”, 1997; “Removal Policies in Network Caches for World-Wide Web Documents”, S. Williams et. al., “Proceedings of SIGCOMM '96”, pp. 293-305; “Intelligent Caching and Indexing Techniques for Relational Database Systems”, T. Sellis, “Information Systems”, vol. 13 no. 2, pp. 175-185, 1988.) Those set forth in the Bolot and Sellis references, utilize as parameters the time since an object was last referenced, the time to retrieve the item, the expected lifetime of the object, and the object size.
Commonly used methods for predicting the frequency with which an object is accessed include the time since the object was last accessed, in which the Least Recently Used (LRU) object is the candidate for replacement, and the LRU-K algorithm, discussed below. The time since the object was last accessed is one of the most common methods. It is of limited accuracy because it doesn't consider accesses before the most recent one. LRU-K, on the other hand, (see “The LRU-K Page Replacement Algorithm for Database Disk Buffering” by O'Neil et. al, in Proceedings of SIGMOD '93, pp. 297-306), estimates the time before the next access based on the time since the kth most recent access. LRU-K is equivalent to LRU when k=1. One drawback to LRU-K is that it weights the times between each of the last k references equally. A better strategy would be to assign more weight to more recent references. Another drawback to LRU-K is that the times of the last K references must be maintained for each object. The space overhead thus grows with K.
Some caching algorithms use a metric for the desirability of caching an object which is preferably proportional to the processing time which is saved by caching the object. Maintaining current values of the metric at all times as proposed in the prior art is, however, prohibitively expensive.
It is an objective of the present invention to provide a method for making caching decisions which balances the expense of caching with the benefits.
SUMMARY OF THE INVENTION
Under the present invention, the value of a metric a which is maintained for an object is allowed to be slightly out of date; and, in calculating a, more weight is assigned to more recent references. The m value for an object is typically updated whenever the object is requested, updated, or under certain other circumstances when the program handling cache replacement (which is known as the cache manager) accesses the object. A priority queue is used to order objects by estimated m values. The priority queue makes it easy to locate the object having the lowest estimated m value (i.e., by definition, the least desirable to cache). Since priority queues have a slight performance disadvantage in that access times grow logarithmically with the size of the priority queue, it is desirable to keep the priority queue as small as possible. To keep the priority queue small, the present method uses a supplemental data structure and a threshold value for a which determines the data structure on which an object should be placed. The result is that the time to locate objects to be replaced doesn't grow with the number of cached objects.
In accordance with the present invention, the method for bounding the size of priority queues can be applied to other situations where priority queues are needed, and not just to cache replacement. Furthermore, the present invention provides a new method for predicting the expected frequency with which objects are accessed. The invention estimates access frequencies based on several accesses in the past, with recent times between accesses being assigned more weight than more distant ones. Space requirements are small and do not grow with the number of past accesses considered.
In addition, the present invention provides a method for estimating the lifetimes of objects. The method can be applied to other situations outside the realm of caching where it is necessary to predict the likelihood of an event occurring based upon past behavior.


REFERENCES:
patent: 5043885 (1991-08-01), Robinson
patent: 5293609 (1994-03-01), Shih et al.
patent: 5546559 (1996-08-01), Kyushima et al.
patent: 5555393 (1996-09-01), Tanaka et al.
patent: 5594885 (1997-01-01), Lautzenheiser
patent: 5619676 (1997-04-01), Fukuda et al.
patent: 5706467 (1998-01-01), Vishlitzky et al.
patent: 5751993 (1998-05-01), Ofek et al.
patent: 5778442 (1998-07-01), Ezzat et al.
patent: 5822759 (1998-10-01), Treynor
patent: 5829023 (1998-10-01), Bishop
patent: 5893139 (1999-04-01), Kamiyama
patent: 5943687 (1999-08-01), Liedberg
patent: 6012126 (2000-01-01), Aggarwal et al.
patent: 6021470 (2000-02-01), Frank et al.

Affiliated with

Also associated with

Rating

Algorithm for cache replacement does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Algorithm for cache replacement, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Algorithm for cache replacement will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2536694