System and method for implementing an adaptive replacement cache policy

• US 6,996,676 B2
• Filed: 11/14/2002
• Issued: 02/07/2006
• Est. Priority Date: 11/14/2002
• Status: Active Grant

• Current Assignee: Tahoe Research Limited (f/k/a Learndale Limited) (Vector Capital Corporation)
• Original Assignee: International Business Machines Corporation
• Inventors: Modha, Dharmendra Shantilal, Megiddo, Nimrod
• Primary Examiner(s): LANE, JOHN A
• Application Number:
  US10/295,507
• Publication Number:
  US 20040098541A1
• Time in Patent Office: 1,181 Days
• Field of Search: 711/129, 711/133, 711/170
• US Class Current: 711/129
• CPC Class Codes: G06F 12/122 of the least frequently used [LFU] type, e.g. with individual count value
• 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/127 using additional replacement algorithms
• CPC Class Codes: G06F 2212/502 using adaptive policy

Abstract

An adaptive replacement cache policy dynamically maintains two lists of pages, a recency list and a frequency list, in addition to a cache directory. The policy keeps these two lists to roughly the same size, the cache size c. Together, the two lists remember twice the number of pages that would fit in the cache. At any time, the policy selects a variable number of the most recent pages to exclude from the two lists. The policy adaptively decides in response to an evolving workload how many top pages from each list to maintain in the cache at any given time. It achieves such online, on-the-fly adaptation by using a learning rule that allows the policy to track a workload quickly and effectively. This allows the policy to balance between recency and frequency in an online and self-tuning fashion, in response to evolving and possibly changing access patterns. The policy is also scan-resistant. It allows one-time-only sequential read requests to pass through the cache without flushing pages that have temporal locality. The policy is extremely simple to implement and requires only constant-time overhead per request. The policy has negligible space overhead.

Claims

1. A method for adaptively managing pages in a cache memory with a variable workload, comprising:

maintaining the cache memory into a first list L1 and a second list L2;

wherein the cache memory has a capacity to store c pages;

adaptively distributing the workload between the first list L1 and the second list L2, to a total capacity of c pages; and

wherein maintaining the cache memory comprises dividing the first list L1 into two list portions T1 and B1.

2. The method of claim 1, wherein adaptively distributing the workload comprises adaptively varying the sizes of the two list portions T1 and B1.

3. The method of claim 2, wherein maintaining the cache memory further comprises dividing the second list L2 into two list portions T2 and B2.

4. The method of claim 3, wherein adaptively distributing the workload further comprises adaptively varying the sizes of the two list portions T2 and B2.

5. The method of claim 4, wherein the first list L1 maintains a first directory of approximately c page names.

6. The method of claim 5, wherein the second list L2 maintains a second directory of approximately c page names.

7. The method of claim 6, wherein adaptively distributing the workload comprises adaptively varying the sizes of list portions T1 and T2, wherein the sum of the sizes of the two list portions T1 and T2 is c.

8. The method of claim 7, wherein adaptively distributing the workload further comprises adaptively varying the sizes of list portions B1 and B2, wherein the sum of the sizes of the two list portions B1 and B2 is approximately c.

9. The method of claim 8, wherein the list L1 contains pages that have been requested exactly once since the last time it was removed from the first directory.

10. The method of claim 9, wherein the list L2 contains pages that have been requested more than once since the last time it was removed from the second directory.

11. The method of claim 10, wherein maintaining the cache memory comprises maintaining the first and second lists L1, L2, as least recently used, LRU, lists, each with a least recently used, LRU, position and a most recently used, MRU, position.

12. The method of claim 11, wherein maintaining the cache memory further comprises maintaining the list portions T1, B1, T2, B2, as least recently used, LRU, lists.

13. The method of claim 12, wherein if a requested page is found in the first list L1, moving the requested page from the first list L1 to the MRU position in the second list L2.

14. The method of claim 12, wherein if a requested page is found in the second list L2, moving the requested page from the second list L2 to the MRU position in the second list L2.

15. The method of claim 14, wherein a page in the LRU position in the list portion T1 is more recent than a page in the MRU position in the list portion B1.

16. The method of claim 15, wherein a page in the LRU position in the list portion T2 is more recent than a page in the MRU position in the list portion B2.

17. The method of claim 12, wherein if the requested page is not found in either the first list L1 or the second list L2, and if the first list L1 does not contain exactly half the number of pages currently in the cache memory, replacing a page in the LRU position in the second list L2 with the requested page.

18. The method of claim 8, wherein the pages contained in the cache memory are a subset of pages listed in the directories of the first and second lists L1, L2.

19. The method of claim 18, wherein the list portion T1 of the first list L1 contains pages that are listed in the first directory and that are physically present in the cache memory;

and

wherein the list portion B1 of the list L1 contains pages that are listed in the first directory of the first list L1 but are not physically present in the cache memory.

20. The method of claim 19, wherein the list portion T2 of the second list L2 contains pages that are listed in the second directory and that are physically present in the cache memory;

and

wherein the list portion B2 of the second list L2 contains pages that are listed in the second directory of the second list L2 but are not physically present in the cache memory.

21. The method of claim 12, wherein maintaining the cache memory into the first list L1 comprises maintaining a target size for the list portion T1.

22. The method of claim 21, wherein maintaining the cache memory into the second list L2 further comprises maintaining a target size for the list portion T2.

23. The method of claim 22, wherein the sum of the target size for the list portion T1 and the target size for the list portion T2 is equal to c.

24. The method of claim 23, wherein maintaining the list portions T1, B1, T2, B2, as least recently used, LRU, lists comprises maintaining each of the list portions T1, B1, T2, B2 with a least recently used, LRU, position and a most recently used, MRU, position.

25. The method of claim 24, wherein maintaining the cache memory further comprises, if a requested page is found in the list portion T1, moving the requested page to the MRU position in the list portion T2.

26. The method of claim 25, wherein maintaining the cache memory further comprises, if a requested page is found in the list portion B1, considering that a cache miss has occurred, increasing the target size for the list portion T1 by a predetermined amount, and decreasing the target size for the list portion T2 by the same predetermined amount.

27. The method of claim 26, wherein if the target size for the list portion T1 is less than or equal to the actual size of the list portion T1, moving a page in the LRU position in the list portion T1 to an MRU position in the list portion B1, and moving the requested page to an MRU position in the list portion T2.

28. The method of claim 26, wherein if the target size for the list portion T1 is greater than the actual size of the list portion T1, moving a page in the LRU position in the list portion T2 to an MRU position in the list portion B2, and moving the requested page to an MRU position in the list portion T2.

29. The method of claim 24, wherein maintaining the cache memory further comprises, if a requested page is found in the list portion B2, considering that a cache miss has occurred and that a cache directory hit has occurred, increasing the target size for the list portion T2 by a predetermined amount, and decreasing the target size for the list portion T1 by the same predetermined amount.

30. The method of claim 29, wherein if the target size for the list portion T1 is less than or equal to the actual size of the list portion T1, moving a page in the LRU position in the list portion T1 to an MRU position in the list portion B1, and moving the requested page to an MRU position in the list portion T2.

31. The method of claim 29, wherein if the target size for the list portion T1 is greater than the actual size of the list portion T1, moving a page in the LRU position in the list portion T2 to an MRU position in the list portion B2, and moving the requested page to an MRU position in the list portion T2.

32. The method of claim 24, wherein if a requested page is not in the first and second directories of the first and second lists L1, L2, if the first list L1 contains exactly c pages, if the actual size of the list portion T1 is less than c, and if the target size for the list portion T1 is less than or equal to the actual size of the list portion T1, moving a page in the LRU position in the list portion T1 to an MRU position in the list portion T1;

and

moving the requested page to an MRU position in the list portion T1, and deleting the LRU page in the list portion B1 from the cache memory.

33. The method of claim 32, wherein if a requested page is not in the directories of the first and second lists L1, L2, if the first list L1 contains exactly c pages, if the actual size of the list portion T1 is less than c, and if the target size for the list portion T1 is greater than the actual size of the list portion T1, moving a page in the LRU position in the list portion T2 to an MRU position in the list portion B2;

and

moving the requested page to an MRU position in the list portion T1, and deleting the LRU page in the list portion B1 from the cache memory.

34. The method of claim 33, wherein if a requested page is not in the first and second directories of the first and second lists L1, L2, if the first list L1 contains exactly c pages, and if the actual size of the list portion T1 is exactly c, deleting the LRU page in list portion T1 from the cache memory and moving the requested page to the MRU position in the list portion T1.

35. The method of claim 34, wherein if a requested page is not in the first and second directories of the first and second lists L1, L2, and the first list L1 contains less than c pages, and if together, the first and second lists L1 and L2 contain exactly 2c pages, deleting the LRU page in the list portion B1 from the cache memory.

36. The method of claim 35, wherein if a requested page is not in the first and second directories of the first and second lists L1, L2, and the first list L1 contains less than c pages, if together, the first and second lists L1 and L2 contain at least c pages, and if the target size for the list portion T1 is greater than the actual size of the list portion T1, moving a page in the LRU position in the list portion T2 to an MRU position in the list portion B2;

and

moving the requested page to the MRU position in the list portion T1.

37. The method of claim 36, wherein if a requested page is not in the first and second directories of the first and second lists L1, L2, if the first list L1 contains less than c pages, if together, the first and second lists L1 and L2 contain at least c pages, and if the target size for the list portion T1 is less than or equal to the actual size of the list portion T1, moving a page in the LRU position in the list portion T1 to an MRU position in the list portion B1;

and

moving the requested page to an MRU position in the list portion T1.

38. The method of claim 12, wherein if a requested page is not found in either the first list L1 or the second list L2, then, if the first list L1 contains exactly half the number of pages currently in the cache memory, replacing a page in the LRU position in the first list L1 with the requested page.

39. An apparatus for adaptively managing pages in a cache memory with a variable workload, comprising:

the cache memory maintaining a first list L1 and a second list L2;

wherein the cache memory has a capacity to store c pages;

means for adaptively distributing the workload between the first list L1 and the second list L2, to a total capacity of c pages;

wherein the first list L1 is comprised of two list portions T1 and B1; and

wherein the second list L2 is comprised of two list portions T2 and B2.

40. The apparatus of claim 39, wherein the means for distributing the workload adaptively varies the sizes of the two list portions T1 and B1;

and

wherein the means for adaptively distributing the workload further adaptively varies the sizes of the two list portions T2 and B2.

41. A computer program product that adaptively manages pages in a cache memory with a variable workload, comprising:

the cache memory maintaining a first list L1 and a second list L2;

wherein the cache memory has a capacity to store c pages;

a set of instruction codes that adaptively distributes the workload between the first list L1 and the second list L2, to a total capacity of c pages;

wherein the first list L1 is comprised of two list portions T1 and B1; and

wherein the second list L2 is comprised of two list portions T2 and B2.

42. The computer program product of claim 41, wherein the set of instruction codes adaptively varies the sizes of the two list portions T1 and B1, and the sizes of the two list portions T2 and B2.