Managing cache elements

• US 8,086,803 B2
• Filed: 05/13/2009
• Issued: 12/27/2011
• Est. Priority Date: 05/13/2009
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Muthiah, Muthu Annamalai, Rane, Jayesh V, Sangwikar, Sanket S
• Primary Examiner(s): Lam, David
• Application Number:
  US12/464,951
• Publication Number:
  US 20100293335A1
• Time in Patent Office: 958 Days
• Field of Search: 711/133, 711/125, 711/141, 711/146, 711/135, 709213-216
• US Class Current: 711/133
• CPC Class Codes: G06F 12/0813 with a network or matrix configuration
• CPC Class Codes: Y02D 10/00 Energy efficient computing, e.g. low power processors, power management or thermal management

Abstract

A method for managing cache elements in an environment based on Common Information Model is described. Cache elements in the cache are associated with a time attribute and historical data. Cache elements having a time attribute lying in a certain range are polled for from the server and updated at predetermined time points. A new time attribute is calculated for each cache element based on its historical data and this new time attribute assists in adapting the polling frequency for the cache element to its importance and change characteristics. Asynchronous notifications from the server preempt the polling based on the time attribute for a cache element and instead, polling for the cache element is based on the asynchronous notification. A system for cache management includes a client and a server, the client having a cache that is managed based on each cache element'"'"'s importance and change characteristics.

Claims

1. A method for managing cache elements in a data processing system having at least one processor and at least one cache, each cache element having associated therewith data, Time to Live (TTL), frequency of change (n_change), and frequency of access (n_access), the method comprising:

setting a polling interval and a refining interval;

storing each cache element in the cache and assigning a base value to the TTL for each cache element fetched for a first time;

managing each cache element according to the following steps;

(a) setting n_change and n_access to zero for the cache element;

(b) tracking historical data, comprising n_change and n_access, for the cache element by incrementing n_change each time the cache element is changed and incrementing const_access each time the cache element is accessed;

(c) in response to expiration of the TTL for the cache element, marking the cache element invalid;

(d) in response to expiration of the polling interval and to the cache element being marked invalid, polling for the cache element to obtain new data for the cache element and updating the cache element with the new data;

(e) in response to expiration of the refining interval, computing a new TTL for the cache element based on the historical data and current TTL for the cache element and returning to step a; and

(f) returning to step b.

2. The method of claim 1, wherein the cache elements have further associated therewith a maximum tolerance value, maximum allowable accesses (N_accessMax), maximum allowable changes (N_changeMax), and first and second constants (const_change and const_access, respectively) having values selectable between a predetermined range, wherein the new TTL (TTL_new) in step e is computed according to the following formula:

TTL_new=TTL_current−

(const_change*(n_change−

N_changeMax/2))−

(const_access*(n_access−

N_accessMax/2)).

3. The method of claim 2, wherein the predetermined range is between 0 and 1.

4. The method of claim 1, further comprising

immediately after step b and before step c, in response to receiving an asynchronous notification for the cache element, marking the cache element invalid and jumping to step d.

5. The method of claim 1, wherein step d further comprises:

polling for the cache element in a server to obtain the new data for the cache element from the server.

6. The method of claim 1, wherein the setting step and steps a through f are performed by the processor.

7. The method of claim 1, wherein the historical data relating to the cache element is stored in the cache element.

8. The method of claim 2, further comprising:

in step c, marking the cache element invalid if the TTL equals or is greater than the maximum tolerance value for the cache element.

9. The method of claim 1, wherein in step b, n_change and n_access are incremented by one each time the cache element is changed or accessed, respectively.

10. The method of claim 1, wherein the refining interval is greater than the polling interval.

11. A system for managing cache elements, having associated with each cache element data, Time to Live (TTL), frequency of change (n_change), and frequency of access (n_access), the system comprising:

a server having data elements stored in a memory;

a client;

a cache in the client configured to store at least one cache element; and

a processor in the client configured to perform the following steps for managing each cache element;

(a) setting a polling interval and a refining interval;

(b) assigning a base value to the TTL for the cache element fetched for a first time;

(c) setting n_change and n_access to zero for the cache element;

(d) tracking historical data, comprising n_change and n_access, relating to the cache element by incrementing n_change by one each time the cache element is changed and incrementing const_access by one each time the cache element is accessed;

(e) in response to expiration of the TTL for the cache element, marking the cache element invalid;

(f) in response to expiration of the polling interval and to the cache element being marked invalid, polling the memory in the server to obtain new data for the cache element and updating the cache element with the new data;

(g) in response to expiration of the refining interval, computing a new TTL for the cache element based on the historical data and a current TTL for the cache element and returning to step c; and

(h) returning to step d.

12. The system of claim 11, wherein the cache elements have further associated therewith a maximum tolerance value, maximum allowable accesses (N_accessMax), maximum allowable changes (N_changeMax), and first and second constants (const_change and const_access, respectively) having values selectable between a predetermined range, wherein the new TTL (TTL_new) in step g is computed according to the following formula:

TTL_new=TTL_current−

(const_change*(n_change−

N_changeMax/2))−

(const_access*(n_access−

N_accessMax/2)).

13. The system of claim 12, wherein the predetermined range is between 0 and 1.

14. The system of claim 11, wherein the historical data relating to the cache element is stored in the cache element.

15. The system of claim 12, further comprising:

in step e, marking the cache element invalid if the TTL equals or is greater than the maximum tolerance value for the cache element, thereby indicating that the TTL has expired.

16. The system of claim 11, wherein the refining interval is greater than the polling interval.