Algorithm for cache replacement

• US 6,266,742 B1
• Filed: 10/27/1997
• Issued: 07/24/2001
• Est. Priority Date: 10/27/1997
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Iyengar, Arun Kwangil, Challenger, James Robert Harold
• Primary Examiner(s): Nguyen, Hiep T.
• Application Number:
  US08/958,506
• Time in Patent Office: 1,366 Days
• Field of Search: 711/137, 711/136, 711/145, 711/143, 711/119, 711/133
• US Class Current: 711/133
• CPC Class Codes: G06F 12/0888 using selective caching, e.g. bypass
• CPC Class Codes: G06F 12/123 with age lists, e.g. queue, most recently used [MRU] list or least recently used [LRU] list

Abstract

In a computer system in which caching is utilized for improving performance, a method for determining whether an uncached object should be cached, and, if so, which objects, if any, should be removed from a cache to make room for the new uncached object. The method assigns a metric correlated with the desirability of caching an object, considering parameters such as access frequencies, object sizes, object lifetimes and times to calculate and/or to fetch the object. The metric weights more recent accesses more heavily than less recent accesses. The method can be used for improving the performance of an algorithm which utilizes priority queues and can additionally be applied when attempting to predict the expected frequency of an occurrence based upon past occurrences.

Claims

1. In a system containing a set of objects and wherein each object has an object value associated with it, said system adapted to provide a priority queue and at least one data structure, a method for identifying an object with a low object value comprising the steps of:

determining a thresho1d value;

comparing the object value to said threshold value for at least one object;

placing one or more objects for which the object value is greater than said threshold value on a data structure; and

placing one or more objects for which the object value is not greater than said threshold value on said priority queue;

identifying one or more objects in the system having low object values by examining at least one of said priority queue and said data structure; and

ordering said objects on said priority queue based on said object value.

2. The method of claim 1 further comprising associating a second value, correlated to said object value, to each of said objects and at least partially ordering said objects on said data structure based on said second values.

3. The method of claim 1 wherein said priority queue is adapted to allow objects to be identified in ascending order of object values starting from the object with the lowest object value.

4. The method of claim 3 wherein said priority queue is implemented using one or more B-+ trees.

5. The method of claim 1 wherein the number of objects in the system may be changed.

6. The method of claim 1 further comprising varying said threshold value.

7. The method of claim 1 wherein said system comprises a cache and the object value associated with an object correlates to the desirability of caching the object.

8. The method of claim 2 wherein said system comprises a cache and the object value and said second value associated with an object correlate to the desirability of caching the object.

9. The method of claim 2 wherein said second value associated with an object is correlated with the frequency with which said object is accessed.

10. The method of claim 9 wherein said data structure comprises a list ordered by how recently said objects have been accessed.

11. The method of claim 10 wherein said second value associated with an object is determined by the position of said object on said list.

12. The method of claim 1 further comprising the step of deleting an object from at least one of said priority queue and said data structure.

13. The method of claim 2 in which said identifying step further comprises examining all objects on said priority queue and examining at least one of said objects on said data structure with a low second value.

79. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine, to perform method steps for any of claims 1-2, 3-23, 24-47 and 15-78.

14. In a system having at least one cache manager managing one or more caches including a priority cache for ordering objects by caching value, in which at least one cache contains at least one cached object having an object caching value, a method for determining priority of objects in at least one of said one or more caches which contain an object comprising the steps of:

periodically calculating one or more caching values; and

comparing one or more caching values to at least one object caching value of the at least one cached object.

15. The method of claim 14 in which said caching value is calculated using at least one parameter selected from the group consisting of the frequency with which the object is accessed, the size of the object, the lifetime of the object, and the expected time to fetch or create the object.

16. The method of claim 15 wherein said comparing comprises comparing the caching value of one or more cached objects to the caching value of at least one uncached object.

17. The method of claim 15 wherein said calculating is done upon occurrence of a trigger event.

18. The method of claim 17 wherein said trigger event is when an object is requested.

19. The method of claim 17 wherein said trigger event is when an object is updated.

20. The method of claim 17 wherein said trigger event is when an object is accessed by the cache manager.

21. The method of claim 15 wherein overhead for calculating said caching value for an object is controlled by varying the frequency with which said caching value for said object is determined.

22. The method of claim 15 in which said caching value is based on the estimated savings in system time by caching said object.

23. The method of claim 15 in which said caching value is calculated using at least one parameter selected from the group consisting of the frequency with which the object is accessed, the size of the object, the lifetime of the object, and the expected time to fetch or create the object if the object is not cached.

24. The method of claim 14 further comprising establishing a threshold caching value based upon said plurality of caching values.

25. The method of claim 24, in which an auxiliary value correlated with said caching value is associated with each object, further comprising:

maintaining an auxiliary data structure at least partially ordered by said auxiliary value; and

placing one or more objects for which said caching values exceeds said threshold value on said auxiliary data structure.

26. The method of claim 24 further comprising determining if an object is to be placed on a priority queue comprising calculating a new object caching value for said object and comparing said calculated caching value to said threshold caching value.

27. The method of claim 26 further comprising placing said object on said priority queue if said new object caching value is not greater than said threshold caching value.

28. The method of claim 24 further comprising changing said threshold caching value.

29. The method of claim 14 further comprising determining if an uncached object is to be cached comprising calculating a new object caching value for said uncached object and identifying at least one cached object for removal from said cache.

30. The method of claim 29 wherein said identifying comprises identifying a set of cached objects having low caching values whose removal from said cache would make room for said new object.

31. The method of claim 30 further comprising obtaining an average caching value for said set and comparing said average caching value to said new object caching value.

32. The method of claim 31 in which said average caching value is weighted by the sizes of objects in said set.

33. The method of claim 30 further comprising maintaining information regarding accesses to said objects and including in said set those objects which are least recently accessed.

34. The method of claim 31 further comprising caching said new object only if said new object caching value exceeds said average caching value.

35. The method of claim 23 wherein said calculating of said caching value for at least one object comprises applying the formula:

(t/a−

t*p/u)/s, where a is the expected time between successive requests for the object, t is the expected time to fetch or create the object, u is the expected time between successive updates of the object, p is the probability that the object will be accessed between successive updates to the object, and s is the expected object size.

36. The method of claim 35 wherein p is determined using a quantity correlated with 1−

((a−

1)/a)^u.

37. The method of claim 35 wherein a is calculated based upon object accesses.

38. The method of claim 35 wherein u is calculated based upon object updates.

39. The method of claim 37 wherein a is calculated by a method comprising the steps of:

maintaining a variable event_latency representing an estimate of the expected time between successive accesses;

maintaining a variable last_event_time representing the time of a previous access;

after occurrence of a new access, at time new_event_time, updating event_latency using the formula;

new event_latency=((new_event_time−

last_event_time)+(k−

1)*old event_latency)/k for a weighting factor k.

40. The method of claim 38 wherein u is calculated by a method comprising the steps of:

maintaining a variable event_latency representing an estimate of the expected time between successive updates;

maintaining a variable last_event_time representing the time of a previous update;

after occurrence of a new update, at time new_event_time, updating event_latency using the formula;

new event_latency=((new_event_time_last_event_time)+(k−

1)*old event_latency)/k for a weighting factor k.

41. A method for estimating how frequently events occur comprising the steps of:

maintaining a variable event_latency representing an estimate of the expected time between successive events;

maintaining a variable last_event_time representing the time of a previous event;

after occurrence of a new event, at time new_event_time, updating event_latency using the formula;

new event_latency=((new_event_time−

last_event_time)+(k−

1)*old event_latency)/k for a weighting factor k.

42. The method of claim 41 in which the system further comprises one or more computers and said events correspond to object accesses.

43. The method of claim 41 in which the system further comprises one or more computers and said events correspond to object updates.

44. A method for calculating a caching value for an object comprising the steps of:

determining the expected time, a, between successive requests for the object;

determining the expected time, t, to fetch or create the object;

determining the expected time, u, between successive updates of the object;

determining the probability, p, that the object will be accessed between successive updates to the object;

determining the expected object size, s; and

applying the formula (t/a−

t*p/u)/s.

45. The method of claim 44 wherein p is determined using a quantity correlated with 1−

((a−

1)/a)^u.

46. The method of claim 44 wherein a is calculated based upon object accesses.

47. The method of claim 44 wherein u is calculated based upon object updates.

48. A system containing a set of objects comprising:

storage means;

at least one priority queue;

at least one data structure;

means for calculating a caching value for each object by applying the formula;

(t/a−

t*p/u)/s, where a is the expected time between successive requests for the object, t is the expected time to fetch or create the object, u is the expected time between successive updates of the object, p is the probability that the object will be accessed between successive updates to the object, and s is the expected object size; and

means for determining treatment of said object based on said caching value.

49. A system containing a set of objects comprising:

storage means;

at least one priority queue adapted to allow objects to be identified in ascending order of object caching values starting from the object with the lowest object caching value;

at least one data structure;

means for calculating an object caching value for each object; and

means for determining treatment of said object based on said object caching value.

50. The system of claim 49 wherein said means for determining treatment of said object based on said object caching value comprises:

threshold means for determining a threshold value;

a comparison component for comparing the object caching value to said threshold value for at least one object; and

wherein said system places one or more objects for which the object caching value is greater than said threshold value on the data structure and places one or more objects for which the object caching value is not greater than said threshold value on the priority queue.

51. The system of claim 50 further comprising means for identifying one or more objects in the system having low object caching values by examining at least one of said priority queue and said data structure.

52. The system of claim 49 wherein said priority queue is implemented using one or more B-+ trees.

53. The system of claim 49 wherein said data structure comprises a list ordered by how recently said objects have been accessed.

54. A system for estimating how frequently events occur comprising:

a variable event_latency representing an estimate of the expected time between successive events;

a variable last_event_time representing the time of a previous event;

processing component for, after occurrence of a new event, at time new_event_time, updating event_latency using the formula;

new event_latency=((new_event_time−

last_event_time)+(k−

1)*old event_latency)/k for a weighting factor k.

55. In a system having at least one cache managers managing one or more caches in which at least one cache contains at least one cached object having an object caching value, a method for determining priority of objects in at least one of said one or more caches which contain an object comprising the steps of:

periodically calculating one or more caching values; and

comparing one or more caching values to at least one object caching value of the at least one cached object.

56. The method of claim 55 wherein said comparing comprises comparing the caching value of one or more cached objects to the caching value of at least one uncached object.

57. The method of claim 55 wherein said calculating is done upon occurrence of a trigger event.

58. The method of claim 57 wherein said trigger event is when an object is requested.

59. The method of claim 57 wherein said trigger event is when an object is updated.

60. The method of claim 57 wherein said trigger event is when an object is accessed by a cache manager.

61. The method of claim 55 wherein overhead for calculating said caching value for an object is controlled by varying the frequency with which said caching value for said object is determined.

62. The method of claim 55 in which said caching value is based on the estimated savings in system time by caching said object.

63. The method of claim 55 in which said caching value is calculated using at least one parameter selected from the group consisting of the frequency with which the object is accessed, the size of the object, the lifetime of the object, and the expected time to calculate the object anew.

64. The method of claim 55 further comprising establishing a threshold caching value based upon said plurality of caching values.

65. The method of claim 64, in which an auxiliary value correlated with said caching value is associated with each object, further comprising:

maintaining an auxiliary data structure at least partially ordered by said auxiliary value; and

placing one or more objects for which said caching values exceeds said threshold value on said auxiliary data structure.

66. The method of claim 64 further comprising changing said threshold caching value.

67. The method of claim 64 further comprising determining if an uncached object is to be cached comprising calculating a new object caching value for said uncached object and identifying at least one cached object for removal from said cache.

68. The method of claim 67 wherein said identifying comprises identifying a set of cached objects having low caching values whose removal from said cache would make room for said new object.

69. The method of claim 68 further comprising obtaining an average caching value for said set and comparing said average caching value to said new object caching value.

70. The method of claim 69 in which said average caching value is weighted by the sizes of objects in said set.

71. The method of claim 68 further comprising maintaining information regarding accesses to said objects and including in said set those objects which are least recently accessed.

72. The method of claim 69 further comprising caching said new object only if said new object caching value exceeds said average caching value.

73. The method of claim 63 wherein said calculating of said caching value for at least one object comprises applying the formula:

(t/a−

t*p/u)/s, where a is the expected time between successive requests for the objects t is the expected time to fetch or create the object, u is the expected time between successive updates of the object, p is the probability that the object will be accessed between successive updates to the object, and s is the expected object size.

74. The method of claim 73 wherein p is determined using a quantity correlated with 1−

((a−

1)/a)^u.

75. The method of claim 73 wherein a is calculated based upon object accesses.

76. The method of claim 73 wherein u is calculated based upon object updates.

77. The method of claim 75 wherein a is calculated by a method comprising the steps of:

maintaining a variable event_latency representing an estimate of the expected time between successive accesses;

maintaining a variable last_event_time representing the time of a previous access;

after occurrence of a new access, at time new_event_time, updating event_latency using the formula;

new event_latency=((new_event_time−

last_event_time)+(k−

1)*old event_latency)/k for a weighting factor k.

78. The method of claim 76 wherein u is calculated by a method comprising the steps of:

maintaining a variable event_latency representing an estimate of the expected time between successive updates;

maintaining a variable last_event_time representing the time of a previous update;

after occurrence of a new update, at time new_event_time, updating event_latency using the formula;

new event_latency=((new_event_time−

last_event_time)+(k−

1)*old event_latency)/k for a weighting factor k.