US6598121B2
Expired / Lapsed
US
⏱️ 0.0 years remaining
System and method for coordinated hierarchical caching and cache replacement
Assignee: International Business Machines Corp
•
Filing: 2001-11-06
•
Granted: 2003-07-22
•
Expires: 2021-11-06
Abstract
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.
Inventors
- 👤 James R. H. Challenger
- 👤 Paul Michael Dantzig
- 👤 Daniel Manuel Dias
- 👤 Arun Kwangil Iyengar
- 👤 Eric M. Levy-Abegnoli
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-24 14:37
CPC Classifications
G; G06; G06F; G06F12/00; G06F12/02; G06F12/08; G06F12/0802; G06F12/0806; G06F12/0811; G06F12/12; G06F12/121
Claims Analysis
Total Claims: 42
Claim 1
Independent Claim
98 words
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.
Claim 2
Independent Claim
98 words
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.
Claim 3
Dependent Claim
73 words
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.
Claim 4
Dependent Claim
21 words
The system of claim 1 , wherein the one or more level 1 nodes comprise one or more Web server accelerators.
Claim 5
Dependent Claim
19 words
The system of claim 1 , wherein the one or more level 1 nodes comprise one or more routers.
Claim 6
Dependent Claim
20 words
The system of claim 1 , wherein the one or more level 2 nodes comprise one or more Web servers.
Claim 7
Dependent Claim
15 words
The system of claim 1 , wherein the nodes are disposed within an encapsulated cluster.
Claim 8
Dependent Claim
68 words
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.
Claim 9
Independent Claim
100 words
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.
Claim 10
Independent Claim
100 words
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.
Claim 11
Dependent Claim
73 words
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.
Claim 12
Dependent Claim
101 words
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.
Claim 13
Dependent Claim
82 words
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.
Claim 14
Dependent Claim
40 words
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.
Claim 15
Dependent Claim
24 words
The method of claim 8 , wherein, at any specific time, an object is stored in, at most, one of the level 2 caches.
Claim 16
Dependent Claim
57 words
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.
Claim 17
Dependent Claim
38 words
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.
Claim 18
Dependent Claim
28 words
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.
Claim 19
Dependent Claim
22 words
The method of claim 8 , further comprising the step of preventing an object from being cached in a level 1 cache.
Claim 20
Dependent Claim
24 words
The method of claim 17 , further comprising the step of allowing the object to be cached in at least one level 2 cache.
Claim 21
Dependent Claim
29 words
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.
Claim 22
Dependent Claim
27 words
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.
Claim 23
Dependent Claim
23 words
The method of claim 8 , wherein the storing step comprises the step of determining the object to be a general cache candidate.
Claim 24
Dependent Claim
25 words
The method of claim 21 , wherein the determining step comprises the step of checking a text string or header information associated with the object.
Claim 25
Dependent Claim
20 words
The method of claim 21 , wherein the determining step comprises the step of applying a function to the object.
Claim 26
Dependent Claim
20 words
The method of claim 23 , wherein the applying step comprises the step of determining the size of the object.
Claim 27
Dependent Claim
21 words
The method of claim 23 , wherein the applying step comprises the step of determining the expected lifetime of the object.
Claim 28
Dependent Claim
24 words
The method of claim 8 , wherein the storing step comprises the step of identifying the object to be a level 1 cache candidate.
Claim 29
Dependent Claim
20 words
The method of claim 26 , wherein the identifying step comprises the step of determining the size of the object.
Claim 30
Dependent Claim
26 words
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.
Claim 31
Dependent Claim
22 words
The method of claim 26 , wherein the identifying step comprised the step of determining sufficient space in the level 1 cache.
Claim 32
Dependent Claim
24 words
The method of claim 8 , wherein the storing step comprises the step of identifying the object to be a level 2 cache candidate.
Claim 33
Dependent Claim
25 words
The method of claim 30 , wherein the identifying step comprises the step of determining the object not to be a level 1 cache candidate.
Claim 34
Dependent Claim
20 words
The method of claim 30 , wherein the identifying step comprises the step of determining the size of the object.
Claim 35
Dependent Claim
22 words
The method of claim 30 , wherein the identifying step comprises the step of determining sufficient space in the level 2 cache.
Claim 36
Dependent Claim
19 words
The method of claim 8 , wherein the storing step comprises the step of applying a cache replacement policy.
Claim 37
Dependent Claim
81 words
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.
Claim 38
Independent Claim
87 words
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.
Claim 39
Independent Claim
87 words
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.
Claim 40
Dependent Claim
73 words
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.
Claim 41
Independent Claim
104 words
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.
Claim 42
Independent Claim
104 words
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.
References Cited (Backward Citations)
US4755930A
Cited
US4928239A
Cited
US5584013A
Cited
US5802563A
Cited
US5946690A
Cited
US5924116A
Cited
US6338117B1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2006-07-21 | 2007-01-20 | 2007-07-22 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2010-07-21 | 2011-01-20 | 2011-07-22 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2014-07-21 | 2015-01-20 | 2015-07-22 | $7700.00 | Window Closed / Lapsed |