Cache replacement for shared memory caches

Patent metadata

Field	Value
Publication number	US-9280470-B2
Application number	US-201213617477-A
Country	US
Kind code	B2
Filing date	Sep 14, 2012
Priority date	Jul 20, 2012
Publication date	Mar 8, 2016
Grant date	Mar 8, 2016

Abstract

An information processing system and computer program storage product for managing objects stored in a shared memory cache. The system includes at least a plurality of cache readers accessing data from the shared memory cache. The 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. A computer program storage product for managing objects stored in cache memory that is communicatively coupled with at least one processor, and in which multiple processes at least read data from the cache memory, the computer program storage product comprising a non-transitory computer readable storage medium comprising instructions configured to perform a method 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
wherein 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 computer program storage product of claim 1 , the cache memory communicatively coupled with the at least one processor being 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 computer program storage product of claim 1 , wherein the at least part of the maintained information includes information on how frequently at least one cached object is accessed.

4. The computer program storage product of claim 1 , wherein 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 computer program storage product of claim 1 , wherein 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 computer program storage product of claim 5 , wherein the change in an access pattern comprises an access frequency for a cached object falling below a threshold.

7. The computer program storage product of claim 5 , wherein the change in an access pattern comprises an access frequency for a cached object exceeding a threshold.

8. A computer program storage product for managing objects stored in cache memory that is communicatively coupled with at least one processor, and in which multiple processes at least read data from the cache memory, the computer program storage product comprising a non-transitory computer readable storage medium comprising instructions configured to perform a method 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
wherein 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.

9. The computer program storage product of claim 8 , wherein the cache memory communicatively coupled with the at least one processor being 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 computer program storage product of claim 8 , wherein the at least part of the maintained information includes information on how frequently at least one cached object is accessed.

11. The computer program storage product of claim 8 , wherein 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 computer program storage product of claim 8 , wherein 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 computer program storage product of claim 12 , wherein the change in an access pattern comprises an access frequency for a cached object falling below a threshold.

14. The computer program storage product of claim 12 , wherein the change in an access pattern comprises an access frequency for a cached object exceeding a threshold.

15. A computer program storage product for managing objects stored in cache memory that is communicatively coupled with at least one processor, and in which multiple processes at least read data from the cache memory, the computer program storage product comprising a non-transitory computer readable storage medium comprising instructions configured to perform a method 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 wherein
the method further comprising the at least one second process periodically replicating informatio

Assignees

• Iyengar Arun
• IBM

Inventors

• Iyengar Arun

Classifications

• G06F12/084 Primary

  with a shared cache · CPC title

• 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

• G06F2212/69

  Physics · mapped topic