Cache control method and cache apparatus

• US 20030014603A1
• Filed: 07/09/2002
• Published: 01/16/2003
• Est. Priority Date: 07/10/2001
• Status: Active Grant

• Current Assignee: NEC Corporation
• Original Assignee: NEC Corporation
• Inventors: Sasaki, Shigero, Tanaka, Atsuhiro, Tatsukawa, Kosuke
• Granted Patent: US 6,834,329 B2
• Time in Patent Office: Days
• US Class Current: 711/158
• 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 each having a different access pattern;

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

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

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

determining the lowest priority group by comparing the lowest priority data items in the respective groups according to LRU.

4. The cache control method claimed in claim 1, dealing with a plurality of data having widely different access frequency counts, further comprising the steps of

determining the lowest priority group by comparing the lowest priority data items in the respective groups according to LRU;

and wherein;

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

5. The cache control method claimed in claim 1, further comprising the steps of:

estimating cache hit rates of the respective groups; and

determining the lowest priority group based on the estimated cache hit rates of the respective groups.

6. The cache control method claimed in claim 1, further comprising the steps of:

estimating cache hit rates of the respective groups; and

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

wherein;

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

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

2. A cache control method comprising the steps of:

dividing requested data 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 data items with respect to each of the groups according to an individual caching algorithm for the group; and

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

8. A cache apparatus carrying out the process of:

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

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

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

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

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

9. A cache apparatus carrying out the process of dividing requested data 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 data items with respect to each of the group according to an individual caching algorithm for the group; and

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

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

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

10. 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 each having a different access pattern;

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

a lowest priority determining means for determining the lowest priority group 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 for purging the lowest priority data item in the lowest priority group determined by the lowest priority determining means.

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

the data grouping means divides the data items stored in the cache memory section into plural groups of data having widely 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; and

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

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

the data grouping means divides the data items stored in the cache memory section into plural groups of data having widely 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;

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

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

13. The cache apparatus claimed in claim 10, further comprising:

a hit rate estimating means for estimating hit rates for the respective groups;

wherein

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

14. The cache apparatus claimed in claim 10, further comprising:

a hit rate estimating means for estimating hit rates for the respective groups;

wherein

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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