Cache replacement for shared memory caches

Patent metadata

Field	Value
Publication number	US-9274963-B2
Application number	US-201213554562-A
Country	US
Kind code	B2
Filing date	Jul 20, 2012
Priority date	Jul 20, 2012
Publication date	Mar 1, 2016
Grant date	Mar 1, 2016

Abstract

A method for managing objects stored in a shared memory cache. The method includes accessing data from the shared memory cache using at least a plurality of cache readers. A system updates data in the shared memory cache using a cache writer. The system maintains a cache replacement process collocated with a cache writer. The cache replacement process makes a plurality of decisions on objects to store in the shared memory cache. Each of the plurality of cache readers maintains information on frequencies with which it accesses cached objects. Each of the plurality of cache readers communicates the maintained information to the cache replacement process. The cache replacement process uses the communicated information on frequencies to make at least one decision on replacing at least one object currently stored in the shared memory cache.

First claim

What is claimed is:

1. In an information processing system comprising cache memory communicatively coupled with at least one processor, and in which multiple processes at least read data from the cache memory, a method for managing objects stored in the cache memory, comprising:
reading, with at least one first process, data stored in the cache memory;
maintaining, with the at least one first process, information on cached data that has been requested by at least one client;
receiving, by at least one second process, communications from the at least one first process;
communicating, from the at least one first process, at least part of the maintained information to the at least one second process; and
using, by the at least one second process, at least part of the maintained information from the at least one first process to make at least one decision on replacing at least one object currently stored in the cache memory, wherein replacing an object comprises removing the object from the cache in order to store another object, and in which the at least one first process communicating at least part of the maintained information to the at least one second process is performed in response to a time period having elapsed since a previous time that the at least one first process communicated at least part of the maintained information to the at least one second process.

2. The method of claim 1 , in which the system is further comprised of multiple cache readers independently reading cached data residing in shared cache memory, and a single cache writer updating cached data in the shared cache memory, wherein the at least one first process comprises a cache reader and the at least one second process resides on the cache writer.

3. The method of claim 1 , in which the at least part of the maintained information includes information on how frequently at least one cached object is accessed.

4. The method of claim 1 , in which the at least one decision on what objects should be stored in the cache memory is made using at least one of:
LRU (Least Recently Used);
LRU−K (where K is a positive integer);
GreedyDual-Size; and
a quantitative utility metric assigned to cached objects.

5. The method of claim 1 , in which the at least one first process communicating at least part of the maintained information to the at least one second process is performed in response to a change in an access pattern of at least one cached object since a previous time that the at least one first process communicated at least part of the maintained information to the at least one second process.

6. The method of claim 5 , in which the change in an access pattern comprises an access frequency for a cached object falling below a threshold.

7. The method of claim 5 , in which the change in an access pattern comprises an access frequency for a cached object exceeding a threshold.

8. In an information processing system comprising cache memory communicatively coupled with at least one processor, and in which multiple processes at least read data from the cache memory, a method for managing objects stored in the cache memory, comprising:
reading, with at least one first process, data stored in the cache memory;
maintaining, with the at least one first process, information on cached data that has been requested by at least one client;
receiving, by at least one second process, communications from the at least one first process;
communicating, from the at least one first process, at least part of the maintained information to the at least one second process; and
using, by the at least one second process, at least part of the maintained information from the at least one first process to make at least one decision on replacing at least one object currently stored in the cache memory, wherein replacing an object comprises removing the object from the cache in order to store another object, and in which the at least one first process communicating at least part of the maintained information to the at least one second process is performed in response to a number of cache reads having occurred since a previous time that the at least one first process communicated at least part of said maintained information to the at least one second process.

9. The method of claim 8 , in which the system is further comprised of multiple cache readers independently reading cached data residing in shared cache memory, and a single cache writer updating cached data in the shared cache memory, wherein the at least one first process comprises a cache reader and the at least one second process resides on the cache writer.

10. The method of claim 8 , in which the at least part of the maintained information includes information on how frequently at least one cached object is accessed.

11. The method of claim 8 , in which the at least one decision on what objects should be stored in the cache memory is made using at least one of:
LRU (Least Recently Used);
LRU−K (where K is a positive integer);
GreedyDual-Size; and
a quantitative utility metric assigned to cached objects.

12. The method of claim 8 , in which the at least one first process communicating at least part of the maintained information to the at least one second process is performed in response to a change in an access pattern of at least one cached object since a previous time that the at least one first process communicated at least part of the maintained information to the at least one second process.

13. The method of claim 12 , in which the change in an access pattern comprises an access frequency for a cached object falling below a threshold.

14. The method of claim 12 , in which the change in an access pattern comprises an access frequency for a cached object exceeding a threshold.

15. The method of claim 1 ,
In an information processing system comprising cache memory communicatively coupled with at least one processor, and in which multiple processes at least read data from the cache memory, a method for managing objects stored in the cache memory, comprising:
reading, with at least one first process, data stored in the cache memory;
maintaining, with the at least one first process, information on cached data that has been requested by at least one client;
receiving, by at least one second process, communications from the at least one first process;
communicating, from the at least one first process, at least part of the maintained information to the at least one second process; and
using, by the at least one second process, at least part of the maintained information from the at least one first process to make at least one decision on replacing at least one object currently stored in the cache memory, wherein replacing an object comprises removing the object from the cache in order to store another object, and in which a frequency of the at least one first process communicating at least part of the maintained information to the at least one second process is at least one of

decreased in response to the cache frequently having space, and
increased in response to the cache frequently being full.

16. The method of claim 15 , in which the system is further comprised of multiple cache readers independently reading cached data residing in shared cache memory, and a single cache writer updating cached data in the shared cache memory, wherein the at least one first process comprises a cache reader and the at least one second process resides on the cache writer.

17. The method of claim 15 , in which the at least part of the maintained information includes informati

Assignees

• Iyengar Arun
• IBM

Inventors

• Iyengar Arun

Classifications

• G06F12/123

  with age lists, e.g. queue, most recently used [MRU] list or least recently used [LRU] list · CPC title

• G06F12/121

  using replacement algorithms · CPC title

• G06F12/084 Primary

  with a shared cache · CPC title

• G06F2212/69

  Physics · mapped topic