System and method for coordinated hierarchical caching and cache replacement

• US 6,598,121 B2
• Filed: 11/06/2001
• Issued: 07/22/2003
• Est. Priority Date: 08/28/1998
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Levy-Abegnoli, Eric M., Iyengar, Arun Kwangil, Challenger, James R. H., Dias, Daniel Manuel, Dantzig, Paul Michael
• Primary Examiner(s): Kim, Matthew
• Assistant Examiner(s): Anderson, Matthew D.
• Application Number:
  US09/993,837
• Publication Number:
  US 20020035672A1
• Time in Patent Office: 623 Days
• Field of Search: 711/122, 711/134, 711/138, 711/156, 711/119, 711/124, 711/133, 711/152, 711/159
• US Class Current: 711/122
• CPC Class Codes: G06F 12/0811 with multilevel cache hierarchies
• CPC Class Codes: G06F 12/121 using replacement algorithms

Abstract

A system and method for hierarchically caching objects includes one or more level 1 nodes, each including at least one level 1 cache; one or more level 2 nodes within which the objects are permanently stored or generated upon request, each level 2 node coupled to at least one of the one or more level 1 nodes and including one or more level 2 caches; and means for storing, in a coordinated manner, one or more objects in at least one level 1 cache and/or at least one level 2 cache, based on a set of one or more criteria. Furthermore, in a system adapted to receive requests for objects from one or more clients, the system having a set of one or more level 1 nodes, each containing at least one level 1 cache, a method for managing a level 1 cache includes the steps of applying, for part of the at least one level 1 cache, a cache replacement policy designed to minimize utilization of a set of one or more resources in the system; and using, for other parts of the at least one level 1 cache, one or more other cache replacement policies designed to minimize utilization of one or more other sets of one or more resources in the system.

Claims

1. A system for hierarchically caching objects, comprising:

one or more level 1 nodes, each including at least one level 1 cache;

one or more level 2 nodes within which the objects are permanently stored, each level 2 node coupled to at least one of the one or more level 1 nodes and including one or more level 2 caches; and

means for storing, in a coordinated manner, one or more objects in at least one of at least one level 1 cache and at least one level 2 cache, based on a set of one or more criteria.

2. The system of claim 1, wherein the set of one or more criteria comprises at least one of:

a size of one or more of the objects, a storage space available in one or more of the caches, a pattern of data accesses to one or more of the objects, a frequency of update of one or more of the objects, and a time to fetch one or more of the objects.

3. The system of claim 1, wherein the one or more level 1 nodes comprise one or more Web server accelerators.

4. The system of claim 1, wherein the one or more level 1 nodes comprise one or more routers.

5. The system of claim 1, wherein the one or more level 2 nodes comprise one or more Web servers.

6. The system of claim 1, wherein the nodes are disposed within an encapsulated cluster.

7. The system of claim 1, further comprising one or more level 3 nodes coupled to at least one of the one or more level 2 nodes and wherein the means for storing comprises a means for storing one or more objects in one or more of the at least one level 1 cache, the at least one level 2 cache and at least one level 3 cache.

8. A method for caching objects, comprising the steps of:

creating one or more level 1 nodes, each including at least one level 1 cache;

creating one or more level 2 nodes within which the objects are permanently stored, each level 2 node coupled to at least one of the one or more level 1 nodes and including one or more level 2 caches; and

storing one or more objects in at least one of at least one level 1 cache and at least one level 2 cache, in a coordinated manner based on a set of one or more criteria.

9. The method of claim 8, wherein the set of one or more criteria comprises at least one of;

a size of one or more of the objects, a storage space available in one or more of the caches, a pattern of data accesses to one or more of the objects, a frequency of update of one or more of the objects, and a time to fetch one or more of the objects.

10. The method of claim 8, further comprising the steps of:

receiving, at the one or more level 1 nodes, a request for an object from a client;

determining whether the requested object is in the at least one level 1 cache;

transmitting, in response to the object being found in the at least one level 1 cache, the object from the at least one level 1 cache to the client; and

attempting, in response to the object not being found in the at least one level 1 cache, to satisfy the request from the at least one level 2 cache.

11. The method of claim 10, wherein the attempting step comprises the steps of:

forwarding the object to at least one of the one or more level 2 nodes;

determining whether the object is in at least one level 2 cache corresponding to the at least one of the one or more level 2 nodes; and

sending, in response to the object being found in the at least one level 2 cache, the object from the level 2 cache to the client.

12. The method of claim 11, further comprising the steps of:

identifying the object as being cacheable at the at least one level 1 cache; and

moving the object or a copy of the object to a level 1 cache.

13. The method of claim 8, wherein, at any specific time, an object is stored in, at most, one of the level 2 caches.

14. The method of claim 8, further comprising the step of preventing the caching of an object in a level 2 cache where a cost of obtaining the object from the level 2 cache is high relative to a cost of fetching of generating the object from a level 2 node corresponding to the level 2 cache.

15. The method of claim 14, wherein the cost of creating the object from the level 2 cache includes a cost of at least one invalidation and update of the object in the cache after its value changes.

16. The method of claim 8, further comprising the step of caching, in response to a level 1 cache being full, an object in a level 2 cache.

17. The method of claim 8, further comprising the step of preventing an object from being cached in a level 1 cache.

18. The method of claim 17, further comprising the step of allowing the object to be cached in at least one level 2 cache.

19. The method of claim 17 wherein the preventing step is made necessary due to a difficulty of maintaining sufficiently current values of the object in the level 1 cache.

20. The method of claim 17 wherein the preventing step is made necessary because the request for the object causes a side effect on a level 2 node.

21. The method of claim 8, wherein the storing step comprises the step of determining the object to be a general cache candidate.

22. The method of claim 21, wherein the determining step comprises the step of checking a text string or header information associated with the object.

23. The method of claim 21, wherein the determining step comprises the step of applying a function to the object.

24. The method of claim 23, wherein the applying step comprises the step of determining the size of the object.

25. The method of claim 23, wherein the applying step comprises the step of determining the expected lifetime of the object.

26. The method of claim 8, wherein the storing step comprises the step of identifying the object to be a level 1 cache candidate.

27. The method of claim 26, wherein the identifying step comprises the step of determining the size of the object.

28. The method of claim 26, wherein the identifying step comprises the step of determining any limits in logging facilities of the associated level 1 node.

29. The method of claim 26, wherein the identifying step comprised the step of determining sufficient space in the level 1 cache.

30. The method of claim 8, wherein the storing step comprises the step of identifying the object to be a level 2 cache candidate.

31. The method of claim 30, wherein the identifying step comprises the step of determining the object not to be a level 1 cache candidate.

32. The method of claim 30, wherein the identifying step comprises the step of determining the size of the object.

33. The method of claim 30, wherein the identifying step comprises the step of determining sufficient space in the level 2 cache.

34. The method of claim 8, wherein the storing step comprises the step of applying a cache replacement policy.

35. The method of claim 34 wherein the applying step comprises the steps of:

applying, for part of the at least one level 1 cache, a cache replacement policy designed to minimize utilization of a set of one or more resources in the system; and

using, for other parts of the at least one level 1 cache, one or more other cache replacement policies designed to minimize utilization of one or more other sets of one or more resources in the system.

36. A method for caching objects, comprising the steps of:

creating one or more level I nodes, each including at least one level I cache, for all integers I such;

that L>

=I>

0, where L>

=3, wherein the objects are permanently stored or generated on at least one of the nodes; and

storing, in a coordinated manner, one or more objects in at least one of at least one level j cache and at least one level k cache where L>

=k>

j>

0, based on a set of one or more criteria.

37. The method of claim 36, wherein the set of one or more criteria comprises at least one of:

a size of one or more of the objects, a storage space available in one or more of the caches, a pattern of data accesses to one or more of the objects, a frequency of update of one or more of the objects, and a time to fetch one or more of the objects.

38. A system for hierarchically caching objects comprising:

one or more level 1 nodes, each including at least one level 1 cache;

one or more level 2 nodes within which the objects are permanently stored or are dynamically originated upon request, each level 2 node coupled to at least one of the one or more level 1 nodes and including one or more level 2 caches; and

means for storing, in a coordinated manner, one or more objects in at least one of at least one level 1 cache and at least one level 2 cache, based on a set of one or more criteria.