Self-adapting cache management method and system

• US 6,601,143 B1
• Filed: 07/20/2000
• Issued: 07/29/2003
• Est. Priority Date: 09/25/1999
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Lamparter, Bernd
• Primary Examiner(s): PEIKARI, BEHZAD
• Application Number:
  US09/619,981
• Time in Patent Office: 1,104 Days
• Field of Search: 709/217, 709/219, 709/216, 711/2, 711/118, 711/133, 711/134, 711/135, 711/136, 711/159, 711/160
• US Class Current: 711/134
• CPC Class Codes: G06F 12/127 using additional replacement algorithms

Abstract

A self-adapting method and apparatus for determining an efficient cache line replacement algorithm for selecting which objects (or lines) are to be evicted from the cache. Objects are prioritized based upon weights which are determined dynamically for each object. The object weights depend on a first attribute L1 for each cache object and a first control parameter P1 which determines the influence of the first attribute L1 on the weights. The hit rate of the cache memory is observed during a first interval of time while the control parameter is set to a first value. The control parameter is adjusted and the hit rate is observed during a second interval of time. The control parameter is then adjusted an incremental amount having a magnitude and direction determined based on whether the hit rate improved or was reduced. The control parameter may be continuously and automatically adjusted based on observed hit rates and the algorithm may include additional control parameters associated with other object attributes, which are adjusted in a similar manner.

Claims

1. A self-adapting method for managing a cache, comprising the steps of:

providing a cache adapted to store a plurality of objects and which has an observable hit rate;

identifying a first attribute which is determinable for each of said plurality of objects;

associating a first control parameter with said first attribute;

determining a weight for each of said plurality of objects, wherein said weights are used to select one or more of said plurality of objects to be evicted from said cache, and wherein said first control parameter determines the significance of said first attribute in determining each said weight for each of said plurality of objects;

assigning an initial value for said first control parameter;

observing the hit rate during a first time interval;

adjusting said first control parameter in a first direction by a first incremental amount;

observing the hit rate during a second time interval; and

adjusting said first control parameter by a second incremental amount, wherein said second incremental amount has a magnitude and a direction determined, at least in part, by said hit rate for said first time interval and said hit rate for said second time interval.

2. A self-adapting method according to claim 1, further comprising the step of:

evaluating whether said hit rate in said second time interval is improved over said hit rate in said first time interval; and

wherein said step of adjusting said first control parameter by a second incremental amount includes the step of determining said second incremental amount as follows;

(1) if said hit rate in said second time interval is improved over said hit rate in said first time interval, then said direction of said second incremental amount is the same as said first direction, and

(2) if said hit rate during said second time interval is reduced from said hit rate during said first time interval, then said direction of second incremental amount is the opposite of said first direction.

3. A self-adapting method according to claim 2, wherein said step of adjusting said first control parameter by a second incremental amount includes the step of determining said second incremental amount as follows:

(1) if said hit rate in said second time interval is improved over said hit rate in said first time interval, said magnitude of said second incremental amount is a first value, and

(2) if said hit rate during said second time interval is reduced from said hit rate during said first time interval, said magnitude of said second incremental amount is a second value which is larger than said second value.

4. A self-adapting method according to claim 2, wherein said step of adjusting said first control parameter by a second incremental amount, includes the step of determining said second incremental amount as follows:

(1) if said hit rate in said second time interval is improved over said hit rate in said first time interval, the magnitude of said second incremental amount is greater then the magnitude of said first incremental amount, and

(2) if said hit rate during said second time interval is reduced from said hit rate during said first time interval, said magnitude of said second incremental amount is less then said magnitude of said first incremental amount.

5. A self-adapting method according to claim 1, further comprising the steps of:

identifying a second attribute which is determinable for each of said plurality of objects;

associating a second control parameter with each said second attribute, said second control parameter for determining the significance of each said second attribute in determining each said weight for each of said plurality of objects;

assigning an initial value for said second control parameter;

observing the hit rate during a third time interval;

adjusting said second control parameter in a second direction by a third incremental amount;

observing the hit rate during a forth time interval; and

adjusting said second control parameter by a forth incremental amount, wherein said forth incremental amount has a magnitude and a direction determined, at least in part, on said hit rate for said third time interval and said hit rate for said forth time interval.

6. A self-adapting method according to claim 5, wherein said step of identifying said first attribute includes the step of identifying said first attribute of each said object as the size of said object;

and

wherein said step of identifying said second attribute further includes the step of identifying said second attribute as the time since said object has been last accessed.

7. A self-adapting method according to claim 5, wherein said step of determining a weight for each of said plurality of objects further comprises the step of:

evaluating for each of said plurality of objects, a weight, wherein each said weight is determined according to the equation

8. A self-adapting method according to claim 7, wherein for each of said steps of observing said hit rate during said first, said second, and said third time intervals, each said first, said second, and said third time intervals are each within the range of two or more hours up to several days.

9. A self-adapting method according to claim 1, wherein, only if said hit rate during any said second time interval is improved from said hit rate during the preceding time interval, said method further comprises the steps of:

observing the hit rate during the next time interval; and

adjusting said first control parameter in said first direction by a calculated incremental amount; and

repeating said steps of observing the hit rate during the next time interval and adjusting said second control parameter, until said next hit rate is no longer improved over the preceding hit rate.

10. A self-adapting method according to claim 9, further comprising the steps of:

identifying a second attribute which is determinable for each of said plurality of objects;

associating a second control parameter with said second attribute, wherein said second control parameter determines the significance of said second attribute in determining each said weight for each of said plurality of objects;

selecting an initial value for said second control parameter;

observing the hit rate during a third time interval; and

adjusting said second control parameter by a third incremental amount, wherein said third incremental amounts has a magnitude and a direction determined in part on said hit rate for the preceding time interval and said hit rate for said third time interval.

11. A computer system comprising:

a cache adapted to store a plurality of objects, and which has an observable hit rate;

a plurality of weights, one of said plurality of weights being determined for each of said plurality of objects, using in selecting one or more said objects to be evicted from said cache;

a first attribute and an associated first control parameter, wherein said first control parameter determines the significance of said first attribute in determining each said weight; and

a cache control means, withing said cache, adapted to adjust said first control parameter an incremental amount having a magnitude and direction determined, at least in part, on the hit rate for a first time interval while said first control parameter has a first value and the hit rate for a second time interval while said first control parameter has a second value, said first value being different from said second value.

12. The computer system of claim 11, wherein said system is used as a web-proxy.