Least recently used eviction implementation

• US 7,971,001 B2
• Filed: 12/28/2004
• Issued: 06/28/2011
• Est. Priority Date: 12/28/2004
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP AG (SAP SE)
• Inventors: Petev, Petio G., Wintergerst, Michael
• Primary Examiner(s): Ellis; Kevin L
• Assistant Examiner(s): Parikh; Kalpit
• Application Number:
  US11/024,524
• Publication Number:
  US 20060143399A1
• Time in Patent Office: 2,373 Days
• Field of Search: 711/118, 711/133, 711/143, 711/159, 711/136
• US Class Current: 711/136
• CPC Class Codes: G06F 12/123 with age lists, e.g. queue, most recently used [MRU] list or least recently used [LRU] list
• CPC Class Codes: G06F 12/126 with special data handling, e.g. priority of data or instructions, handling errors or pinning

Abstract

Methods for a treatment of cached objects are described. In one embodiment, management of a region of a cache is configured with an eviction policy plug-in. The eviction policy plug-in includes an eviction timing component and a sorting component, with the eviction timing component including code to implement an eviction timing method, and the eviction timing method to trigger eviction of an object from the region of cache. The sorting component includes code to implement a sorting method to identify an object that is eligible for eviction from said region of cache. The sorting method includes identifying an object for eviction that is cached in the region of cache and that has been used least recently compared to other objects that are cached in the region of cache.

Claims

1. A method, comprising:

using one or more processors to process program code, the program code to perform the following;

configuring management of a region of a cache by selecting one of a plurality of sorting policies for an eviction policy plug-in, said eviction policy plug-in comprising an eviction timing method to create free space within said region of cache by triggering eviction of an object from said region of cache without increasing an allocation of storage space given to said region of cache, said eviction policy plug-in also comprising a sorting method to identify said object on the basis that said object has been used least recently compared to other objects that are cached in said region of cache;

managing said region of cache by executing said eviction timing method and said sorting method, said executing of said eviction timing method including;

triggering eviction of objects from said region of cache when a total count of objects in said region of cache is above a first threshold, wherein eviction of objects occurs until the total count of objects falls below the first threshold;

triggering eviction of an object from said region of cache in response to another object being newly entered into said region of cache when the total count of objects in said region of cache is above a second threshold said second threshold corresponding to less usage of said region of cache than said first threshold;

triggering eviction of objects from said region of cache on a timed basis when the total count of objects in said region of cache is above a third threshold, said third threshold corresponding to less usage of said region of cache than said first threshold; and

triggering eviction of an object from said region of cache when said object resides in said region of cache for more than an amount of time specified by a time-to-live attribute for said object.

2. The method of claim 1 wherein said object is a member of a first shared closure and said newly entered object is a member of a second shared closure.

3. The method of claim 2 wherein said object is cached in a shared memory in a computing system, said shared memory being shared between a plurality of virtual machines.

4. The method of claim 1 wherein said first threshold corresponds to a maximum allocation for the cache region.

5. The method of claim 1 wherein said eviction timing method further comprises, after said second threshold is surpassed, triggering eviction of one or more objects from said region of cache, each of the one or more objects having an object size, wherein cached objects are evicted according to object size.

6. The method of claim 1 wherein said eviction timing method further comprises:

after said third threshold is surpassed, triggering eviction of objects from said region of cache on a periodic basis.

7. A computing system comprising a machine, said computing system also comprising program code disposed on a computer readable storage medium, said program capable of being executed by said machine to perform a method, said method comprising:

configuring management of a region of a cache by selecting one of a plurality of sorting policies for an eviction policy plug-in, said eviction policy plug-in comprising an eviction timing method to create free space within said region of cache by triggering eviction of an object from said region of cache without increasing an allocation of storage space given to said region of cache, said eviction policy plug-in also comprising a sorting method to identify said object on the basis that said object has been used least recently compared to other objects that are cached in said region of the cache;

managing said region of cache by executing said eviction timing method and said sorting method, said executing of said eviction timing method including;

triggering eviction of objects from said region of cache when a total count of objects in said region of cache is above a first threshold, wherein eviction of objects occurs until the total count of objects falls below the first threshold;

triggering eviction of an object from said region of cache in response to another object being newly entered into said region of cache when the total count of objects in said region of cache is above a second threshold said second threshold corresponding to less usage of said region of cache than said first threshold; and

triggering eviction of objects from said region of cache on a timed basis when the total count of objects in said region of cache is above a third threshold, said third threshold corresponding to less usage of said region of cache than said first threshold; and

triggering eviction of an object from said region of cache when said object resides in said region of cache for more than an amount of time specified by a time-to-live attribute for said object.

8. The method of claim 7 wherein said object is a member of a first shared closure and said newly entered object is a member of a second shared closure.

9. The method of claim 8 wherein said object is cached in a shared memory in a computing system, said shared memory being shared between a plurality of virtual machines.

10. The method of claim 7 wherein said first threshold corresponds to a maximum allocation for the cache region.

11. The method of claim 7 wherein said eviction timing method further comprises, after said second threshold is surpassed, each of the one or more objects having an object size, wherein cached objects are evicted according to object size.

12. The method of claim 7 wherein said eviction timing method further comprises:

after said third threshold is surpassed, triggering eviction of objects from said region of cache on a periodic basis.

13. An article of manufacture including executable or interpretable program code recorded on a computer readable storage medium which, when executed or interpreted by a machine, causes the machine to perform a method, the method comprising:

configuring management of a region of a cache by selecting one of a plurality of sorting policies for an eviction policy plug-in, said eviction policy plug-in comprising an eviction timing method to create free space within said region of cache by triggering eviction of an object from said region of cache without increasing an allocation of storage space given to said region of cache, said eviction policy plug-in also comprising a sorting method to identify said object on the basis that said object has been used least recently compared to other objects that are cached in said region of cache;

managing said region of cache by executing said eviction timing method and said sorting method, said executing of said eviction timing method including;

triggering eviction of objects from said region of cache when a total count of objects in said region of cache is above a first threshold, wherein eviction of objects occurs until the total count of objects falls below the first threshold;

triggering eviction of an object from said region of cache in response to another object being newly entered into said region of cache when the total count of objects in said region of cache is above a second threshold said second threshold corresponding to less usage of said region of cache than said first threshold; and

triggering eviction of objects from said region of cache on a timed basis when the total count of objects in said region of cache is above a third threshold, said third threshold corresponding to less usage of said region of cache than said first threshold; and

triggering eviction of an object from said region of cache when said object resides in said region of cache for more than an amount of time specified by a time-to-live attribute for said object.

14. The method of claim 13 wherein said object is a member of a first shared closure and said newly entered object is a member of a second shared closure.

15. The method of claim 14 wherein said object is cached in a shared memory in a computing system, said shared memory being shared between a plurality of virtual machines.

16. The method of claim 13 wherein said first threshold corresponds to a maximum allocation for the cache region.

17. The method of claim 13 wherein said eviction timing method further-comprises, after said second threshold is surpassed, each of the one or more objects having an object size, wherein cached objects are evicted according to object size.

18. The method of claim 13 wherein said eviction timing method further comprises:

after said third threshold is surpassed, triggering eviction of objects from said region of cache on a periodic basis.