Cache control method and cache apparatus

• US 6,834,329 B2
• Filed: 07/09/2002
• Issued: 12/21/2004
• Est. Priority Date: 07/10/2001
• Status: Active Grant

• Current Assignee: NEC Corporation
• Original Assignee: NEC Corporation
• Inventors: Tatsukawa, Kosuke, Sasaki, Shigero, Tanaka, Atsuhiro
• Primary Examiner(s): Kim, Matthew
• Assistant Examiner(s): Thomas, Shane M.
• Application Number:
  US10/190,815
• Publication Number:
  US 20030014603A1
• Time in Patent Office: 896 Days
• Field of Search: 711/133, 711/134, 711/136, 711/159, 711/160, 711/118, 711/158, 711/130, 711/149, 711/170, 711/171, 711/172
• US Class Current: 711/134
• CPC Class Codes: G06F 12/126 with special data handling, e.g. priority of data or instructions, handling errors or pinning
• CPC Class Codes: G06F 16/9574 of access to content, e.g. by caching

Abstract

A data grouping means divides data items stored in a cache memory section into groups of data having different access patterns. The priority assigning means assigns an order of priorities to data items in each group that the priority assigning means manages according to an individual caching algorithm. The lowest priority determining means determines the lowest priority group when there is not enough unused memory space in the cache memory section and it is necessary to purge a data item. The data operating means purges the lowest priority data in the lowest priority group. Thus the groups of data having different access patterns can be cached effectively.

Claims

1. A cache control method comprising the steps of:

classifying a plurality of data items stored in a cache memory section into groups of data items each having a different access pattern;

assigning an order of priorities to the data items with respect to each of the groups of data items according to an individual caching algorithm for the group of data items; and

purging a data item, which is given the lowest priority based on the individual caching algorithm for the respective group of data items, in the lowest priority group of data items determined by prescribed evaluation standards when it is necessary to purge a data item from the cache memory section;

estimating cache hit rates of the respective groups of data items;

determining the lowest priority group of data items based on the estimated cache hit rates of the respective groups of data items;

wherein the cache hit rate of each group of data items is estimated based on the size of memory space occupied by the group of data items and the number of data items which have been accessed once or more times in the group of data items.

2. The cache control method claimed in claim 1, dealing with a plurality of data items having different access frequency counts, further comprising the step of:

determining the lowest priority group by comparing the lowest priority data items in the respective groups of data items according to LRU (Least Recently Used).

3. The cache control method claimed in claim 1, dealing with a plurality of data items having different access frequency counts, further comprising the step of:

determining the lowest priority group of data items by comparing the lowest priority data items in the respective groups of data items according to LRU (Least Recently Used); and

wherein

the plurality of data items include a directory data and a file data.

4. The cache control method claim in claim 1, wherein data items are divided into groups of data items based on a hyperlink structure of the data items.

5. A cache control method comprising the steps of:

dividing requested data items into divided data items, which are units of cache control;

grouping the divided data items into a group of data items whose access times are predictable and a group of data items whose access times are unpredictable;

assigning an order of priorities to the divided data items with respect to each of the groups of data items according to an individual caching algorithm for the group of data items; and

purging a data item, which is given the lowest priority based on the individual caching algorithm for the group of data items, in the lowest priority group of data items determined by prescribed evaluation standards when it is necessary to purge a data item from the cache memory section;

estimating cache hit rates of the respective groups of data items;

determining the lowest priority group of data items based on the estimated cache hit rates of the respective groups of data items;

wherein the cache hit rate of each group of data items is estimated base on the size of memory space occupied by the group of data items and the number of data items which have been accessed once or more times in the group of data items.

6. A cache apparatus comprising:

a data grouping means for classifying a plurality of data items stored in a cache memory section into groups of data items each having a different access pattern;

a priority assigning means provided for each of the groups of data items for assigning an order of priorities to the data items belonging to the corresponding group of data items according to an individual caching algorithm for the group of data items;

a lowest priority determining means for determining the lowest priority group of data items by prescribed evaluation standards when it is necessary to purge a data item from the cache memory section; and

a data operating means provided for each of the groups of data items for purging the lowest priority data item in the lowest priority group of data items determined by the lowest priority determining means;

a hit rate estimating means for estimating hit rates for the respective groups of data items;

wherein

the lowest priority determining means determines the lowest priority group of data items based on the estimated cache hit rates of the respective groups of data items calculated by the hit rate estimating means; and

the hit rate estimating means estimates a cache hit rate of each group of data items based on the size of memory space occupied by the group of data items and the number of data items which have been accessed once or more times in the group of data items.

7. The cache apparatus claimed in claim 6, wherein:

the data grouping means divides the data items stored in the cache memory section into a plurality of groups of data items having different access frequency counts;

each of the priority assigning means assigns an order of priorities to the data items that the priority assigning means manages according to LRU (Least Recently Used); and

the lowest priority determining means determines the lowest priority group of data items by comparing the lowest priority data items in the respective groups of data items.

8. The cache apparatus claimed in claim 7, which serves as a proxy cache for storing Web data.

9. The cache apparatus claimed in claim 7, which serves as a disk cache for storing disk data.

10. The cache apparatus claimed in claim 6, wherein:

the data grouping means divides the data items stored in the cache memory section into a plurality of groups of data items having different access frequency counts;

each of the priority assigning means assigns an order of priorities to the data items that the priority assigning means manages according to LRU (Least Recently Used);

the lowest priority determining means determines the lowest priority group of data items by comparing the lowest priority data items in the respective groups of data items; and

the data grouping means divides the data items stored in the cache memory section into a group of directory data items and a group of file data items.

11. The cache apparatus claimed in claim 10, which serves as a proxy cache for storing Web data.

12. The cache apparatus claimed in claim 10, which serves as a disk cache for storing disk data.

13. The cache apparatus claimed in claim 6, wherein the data grouping means divides the data items into groups of data items based on a hyperlink structure of the data items.

14. The cache apparatus claimed in claim 13, which serves as a proxy cache for storing Web data.

15. The cache apparatus claimed in claim 13, which serves as a disk cache for storing disk data.

16. The cache apparatus claimed in claim 6, which serves as a proxy cache for storing Web data.

17. The cache apparatus claimed in claim 6, which serves as a disk cache for storing disk data.