Web cache performance by applying different replacement policies to the web cache

• US 6,272,598 B1
• Filed: 03/22/1999
• Issued: 08/07/2001
• Est. Priority Date: 03/22/1999
• Status: Expired due to Term

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Arlitt, Martin F., Friedrich, Richard J., Jin, Tai Y.
• Primary Examiner(s): Nguyen, Hiep T.
• Application Number:
  US09/273,849
• Time in Patent Office: 869 Days
• Field of Search: 711/122, 711/133, 711/134, 711/135, 711/136, 711/129, 711/173, 709/203, 709/219
• US Class Current: 711/133
• CPC Class Codes: G06F 12/0897 with two or more cache hierarchy levels with multilevel cache hierarchies G06F12/0811
• CPC Class Codes: G06F 12/121 using replacement algorithms
• CPC Class Codes: G06F 16/9574 of access to content, e.g. by caching

Abstract

A cache system is described that includes a storage that is partitioned into a plurality of storage areas, each for storing one kind of objects received from remote sites and to be directed to target devices. The cache system further includes a cache manager coupled to the storage to cause objects to be stored in the corresponding storage areas of the storage. The cache manager causes cached objects in each of the storage areas to be replaced in accordance with one of a plurality of replacement policies, each being optimized for one kind of objects.

Claims

1. A cache system comprising:

a storage that is partitioned into a plurality of storage areas, each for storing one kind of objects of different sizes received from remote sites and to be directed to target devices;

a cache manager coupled to the storage to cause objects to be stored in the corresponding areas of the storage, wherein the cache manager causes cached objects in each of the storage areas to be replaced in accordance with one of a plurality of replacement policies, each policy being optimized for one kind of objects and being different from one another such that the storage can store objects of different kinds while offering optimized performance across different performance metrics at the same time, wherein the cache manager may cause more than one cached object in a storage area to be evicted in order for a single new object to be stored in the same storage area.

2. The cache system of claim 1, wherein when the cache manager receives an object from remote sites, the cache manager determines to which one of the storage areas the received object is to be cached based on which kind the object belongs to.

3. The cache system of claim 1, wherein the cache manager dynamically changes the size of each of the storage areas of the storage.

4. The cache system of claim 1, wherein the cache manager statically partitions the storage areas such that the size of each of the storage areas remains unchanged after partitioning.

5. The cache system of claim 1, wherein the cache manager further comprises:

a partition lookup table that indicates which kind of objects are stored in which of the storage areas;

a replacement policy database that stores the plurality of replacement policies;

a replacement controller that applies one of the replacement policies to a corresponding one of the storage areas.

6. The cache system of claim 1, wherein the plurality of replacement policies are selected from a group comprising a Least-Recently-Used (LRU) replacement policy, a Least-Frequently-Used (LFU) replacement policy, a Greedy-Dual-Size (GDS) replacement policy, a LFU-Aging replacement policy, a LRU-Log (size) replacement policy, a Size replacement policy, a Lowest-Latency-First replacement policy, a Lowest-Relative-Value (LRV) replacement policy, a GDS-Frequency replacement policy, and a LFU-Dynamic Aging replacement policy.

7. A cache system, comprising:

(A) a storage that includes a first and a second storage device coupled together, wherein each of the first and second storage devices stores objects of different sizes received from remote sites and to be directed to target devices;

(B) a cache manager coupled to the first storage device to send received objects to the first storage device, wherein the cache manager causes cached objects in the first storage device to be replaced in accordance with a first replacement policy, wherein the replaced objects are sent to the second storage device, wherein the cache manager causes cached objects in the second storage device to be replaced in accordance with a second replacement policy different from the first replacement policy such that the storage can store objects of different kinds while offering optimized performance across different performance metrics at the same time, wherein the cache manager may cause more than one cached object in one of the first and second storage devices to be evicted in order for a single new object to be stored in the same storage device.

8. The cache system of claim 7, further comprising a third storage device coupled to the second storage device to store objects replaced from the second storage device, wherein the cache manager replaces the objects stored in the third storage device in accordance with a third replacement policy different from the first and second replacement policies.

9. The cache system of claim 8, wherein when the first storage device receives an object for caching and the first storage device is full, the first storage device passes a replaced object to the second storage device in accordance with the first replacement policy.

10. The cache system of claim 9, wherein when the second storage device receives the replaced object for caching and the second storage device is full, the second storage device passes a second replaced object to the third storage device in accordance with the second replacement policy.

11. The cache system of claim 10, wherein when the third storage device receives the replaced second object for caching from the second storage device and the third storage device is full, the third storage device evicts a third replaced object in accordance with the third replacement policy.

12. The cache system of claim 11, wherein when a cached object in the third storage device is requested by an access request in a cache hit operation, the object is moved back to the first storage device.

13. The cache system of claim 8, wherein each of the first, second, and third replacement policies is selected from a group comprising a Least-Recently-Used (LRU) replacement policy, a Least-Frequently-Used (LFU) replacement policy, a Greedy-Dual-Size (GDS) replacement policy, a LFU-Aging replacement policy, a LRU-Log (size) replacement policy, a Size replacement policy, a Lowest-Latency-First replacement policy, a Lowest-Relative-Value (LRV) replacement policy, a GDS-Frequency replacement policy, and a LFU-Dynamic Aging replacement policy.

14. A cache system, comprising:

(A) a storage that is partitioned into a first and a second storage area, each including a first and a second storage device coupled together;

(B) a cache manager coupled to the first storage device of each of the storage areas to cause objects to be stored in the corresponding areas of the storage, wherein the cache manager causes cached objects in the first storage device of the first storage area to be replaced in accordance with a first replacement policy, wherein the replaced objects are then sent to the second storage device of the first storage area and the cache manager causes the cached objects stored in the second storage device of the first storage area to be replaced in accordance with a second replacement policy different from the first replacement policy, wherein the cache manager causes cached objects in the first storage device of the second storage area to be replaced in accordance with a third replacement policy different from the first replacement policy, wherein the replaced objects are then sent to the second storage device of the second storage area and the cache manager causes the cached objects stored in the second storage device of the second storage area to be replaced in accordance with a fourth replacement policy different from the third replacement policy.

15. The cache system of claim 14, wherein the cache manager further comprises:

a partition lookup table that indicates which object is stored in which of the storage areas;

a replacement policy database that stores the replacement policies;

a replacement controller that applies the corresponding one of the replacement policies to a corresponding one of the storage devices of the corresponding storage area.

16. The cache system of claim 14, wherein each of the first and second storage areas further comprises a third storage device coupled to the second storage device to store objects replaced from the second storage device, wherein the cache manager replaces objects stored in the third storage device in accordance with a fifth replacement policy.

17. The cache system of claim 14, wherein the storage further comprises a third storage area including a plurality of storage devices coupled together.

18. The cache system of claim 14, wherein the replacement policies are selected from a group comprising a Least-Recently-Used (LRU) replacement policy, a Least-Frequently-Used (LFU) replacement policy, a Greedy-Dual-Size (GDS) replacement policy, a LFU-Aging replacement policy, a LRU-Log (size) replacement policy, a Size replacement policy, a Lowest-Latency-First replacement policy, a Lowest-Relative-Value (LRV) replacement policy, a GDS-Frequency replacement policy, and a LFU-Dynamic Aging replacement policy.

19. The cache system of claim 14, wherein when the first storage device of one of the first and second storage areas receives an object for caching and the first storage device is full, the first storage device passes a replaced object to the second storage device in accordance with one of the first and the third replacement policies.

20. The cache system of claim 19, wherein when the second storage device of one of the first and second storage areas receives the replaced object for caching and the second storage device is full, the second storage device determines a second replaced object in accordance with one of the second and fourth replacement policies.

21. The cache system of claim 20, wherein when a cached object in the second storage device of one of the first and second storage areas is requested by an access request in a cache hit operation, the object is moved back to the corresponding first storage device.