Cache eviction

• US 7,590,803 B2
• Filed: 09/23/2004
• Issued: 09/15/2009
• Est. Priority Date: 09/23/2004
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP AG (SAP SE)
• Inventors: Wintergerst, Michael
• Primary Examiner(s): Bataille; Pierre-Michel
• Assistant Examiner(s): DUDEK JR, EDWARD J
• Application Number:
  US10/949,541
• Publication Number:
  US 20060064549A1
• Time in Patent Office: 1,818 Days
• Field of Search: 711/134, 710/57
• US Class Current: 711/134
• CPC Class Codes: G06F 12/121 using replacement algorithms
• CPC Class Codes: G06F 12/127 using additional replacement algorithms

Abstract

Described herein are methods and apparatus, including computer program products, that implement cache eviction for runtime systems. A computer program product can cause a data processing apparatus to compute a fill level of a cache memory; use a first eviction process to evict one or more of the entities in the cache memory if the fill level exceeds a first threshold but not a second threshold; use a second, distinct eviction process to evict one or more of the entities in the cache memory if the fill level exceeds the second threshold but not a third threshold; and decline subsequent requests to store additional entities in the cache memory if the fill level exceeds the third threshold.

Claims

1. A machine-readable storage medium comprising instructions which, when executed, cause a machine to:

evict cached entities of a centralized shared cache memory in accordance with an eviction policy being executed by a framework manager of the cache memory, wherein evicting the cached entities includes versioning the cached entities as they are being referred to by fill metrics, wherein versioning the cached entities includes duplicating the cached entities such that the duplicate cached entities are dynamically updated while the cached entities are being referred to by the fill metrics in compliance with the eviction policy, wherein the cached entities are referred to by the fill metrics that are associated with multiple thresholds that are further associated with multiple distinct processes, and depending on which of the multiple thresholds is exceeded, a corresponding process of the multiple processes is triggered, wherein the instructions which, when executed, further cause the machine to compute a fill level corresponding to a fill metric, the fill level at the cache memory having the cached entities, the computing of the fill level including computing a measurement of each of the fill metrics, wherein the fill level exceeds a threshold if each of the fill metrics exceeds an associated threshold level;

evict one or more of the cached entities in the cache memory in accordance with a first eviction technique if the fill level exceeds a first threshold but not a second threshold;

evict one or more of the cached entities in the cache memory in accordance with a second eviction technique if the fill level exceeds the second threshold but not a third threshold; and

decline subsequent requests to store additional entities in the cache memory if the fill level exceeds the third threshold.

2. The machine-readable storage medium of claim 1, wherein:

the first eviction technique comprises a background technique that operates independently of requests to store the cached entities in the cache memory; and

the second eviction technique comprises an active technique that operates in conjunction with the requests to store the cached entities in the cache memory.

3. The machine-readable storage medium of claim 1, wherein the cached entities comprise live cached entities in the cache memory, and marked cached entities in the cache memory that are marked for deletion but whose memory has not yet been reclaimed.

4. The machine-readable storage medium of claim 1, wherein a first fill metric comprises an amount of the cached entities, a second fill metric comprises a total amount of memory being used by the cached entities, and the instructions to compute the fill metrics when executed, cause the machine to:

count the amount of the cached entities in the cache memory to compute a measurement of the first fill metric; and

compute the total amount of memory being used by the cached entities in the cache memory to compute a measurement of the second fill metric.

5. The machine-readable storage medium of claim 1, wherein the instructions to evict one or more of the entities in the cache memory when executed, cause the machine to:

identify one or more cached entities to evict in accordance with the eviction policy.

6. The machine-readable storage medium of claim 5, wherein the eviction policy comprises a least-recently-used policy.

7. The machine-readable storage medium of claim 5, wherein the eviction policy is implemented by a user-specified plug-in module.

8. The machine-readable storage medium of claim 1, wherein the cache memory is shared and commonly accessible by a plurality of runtime systems in a server computer.

9. The machine-readable storage medium of claim 8, wherein the runtime systems comprise virtual machines.

10. The machine-readable storage medium of claim 1, wherein the cached entities in the cache memory are stored in shared closures.

11. The machine-readable storage medium of claim 1, wherein the cached entities in the cache memory comprise objects, and wherein requests to store additional cached entities in the cache memory are generated by user code executing in a virtual machine.

12. The machine-readable storage medium of claim 1, wherein the instructions to compute the fill level of the cache memory when executed, cause the machine to compute a fill level of a cache memory storing shared closures of the cached entities.

13. The machine-readable storage medium of claim 1, wherein the threshold comprises an Nth threshold, wherein the associated threshold level comprises an Nth threshold level associated with the Nth threshold.

14. A method comprising:

evicting cached entities of a centralized shared cache memory in accordance with an eviction policy being executed by a framework manager of the cache memory, wherein evicting the cached entities includes versioning the cached entities as they are being referred to by fill metrics, wherein versioning the cached entities includes duplicating the cached entities such that the duplicate cached entities are dynamically updated while the cached entities are being referred to by the fill metrics in compliance with the eviction policy, wherein the cached entities are referred to by the fill metrics that are associated with multiple thresholds that are further associated with multiple distinct processes, and depending on which of the multiple thresholds is exceeded, a corresponding process of the multiple processes is triggered, wherein the evicting of the cached entities includes computing a fill level corresponding to a fill metric, the fill level at the cache memory having the cached entities, the computing of the fill level including computing a measurement of each of the fill metrics, wherein the fill level exceeds a threshold if each of the fill metrics exceeds the associated threshold level;

evicting one or more of the entities in the cache memory in accordance with a first eviction technique if the fill level exceeds a first threshold but not a second threshold;

evicting one or more of the entities in the cache memory in accordance with a second eviction technique if the fill level exceeds the second threshold but not a third threshold; and

declining subsequent requests to store additional entities in the cache memory if the fill level exceeds the third threshold.

15. The method of claim 14, wherein:

the first eviction technique comprises a background technique that operates independently of requests to store the cached entities in the cache memory; and

the second eviction technique comprises an active technique that operates in conjunction with the requests to store the cached entities in the cache memory.

16. The method of claim 14, wherein the cached entities comprise live cached entities in the cache memory, and marked cached entities in the cache memory that are marked for deletion but whose memory has not yet been reclaimed.

17. The method of claim 14, wherein a first fill metric comprises an amount of the cached entities, a second fill metric comprises a total amount of memory being used by the cached entities, the method further comprising:

counting the amount of the cached entities in the cache memory to compute a measurement of the first fill metric; and

computing the total amount of memory being used by the cached entities in the cache memory to compute a measurement of the second fill metric.

18. The method of claim 14, wherein the threshold comprises an Nth threshold, wherein the associated threshold level comprises an Nth threshold level associated with the Nth threshold.

19. A system comprising:

means for evicting cached entities of a centralized shared cache memory in accordance with an eviction policy being executed by a framework manager of the cache memory, wherein evicting the cached entities includes versioning the cached entities as they are being referred to by fill metrics, wherein versioning the cached entities includes duplicating the cached entities such that the duplicate cached entities are dynamically updated while the cached entities are being referred to by the fill metrics in compliance with the eviction policy, wherein the cached entities are referred to by the fill metrics that are associated with multiple thresholds that are further associated with multiple distinct processes, and depending on which of the multiple thresholds is exceeded, a corresponding process of the multiple processes is triggered, wherein the server computer system is further to compute a fill level corresponding to a fill metric, the fill level at the cache memory having the cached entities, the computing of the fill level including computing a measurement of each of the fill metrics, wherein the fill level exceeds a threshold if each of the fill metrics exceeds the associated threshold level;

means for evicting one or more of the entities in the cache memory in accordance with a first eviction technique if the fill level exceeds a first threshold but not a second threshold;

means for evicting one or more of the entities in the cache memory in accordance with a second eviction technique if the fill level exceeds the second threshold but not a third threshold; and

means for declining subsequent requests to store additional entities in the cache memory if the fill level exceeds the third threshold.

20. The system of claim 19, wherein:

the first eviction technique comprises a background technique that operates independently of requests to store the cached entities in the cache memory; and

the second eviction technique comprises an active technique that operates in conjunction with the requests to store the cached entities in the cache memory.

21. The system of claim 19, wherein the cached entities comprise live cached entities in the cache memory, and marked cached entities in the cache memory that are marked for deletion but whose memory has not yet been reclaimed.

22. The system of claim 19, wherein a first fill metric comprises an amount of the cached entities, a second fill metric comprises a total amount of memory being used by the cached entities, the system further comprising:

means for counting the amount of the cached entities in the cache memory to compute a measurement of the first fill metric; and

means for computing the total amount of memory being used by the cached entities in the cache memory to compute a measurement of the second fill metric.

23. The system of claim 19, wherein the threshold comprises an Nth threshold, wherein the associated threshold level comprises an Nth threshold level associated with the Nth threshold.

24. The system of claim 19, wherein the virtual machine comprises a Java virtual machine or a Common Language Runtime virtual machine.