Method for cache replacement of web documents

• US 20020184448A1
• Filed: 05/29/2001
• Published: 12/05/2002
• Est. Priority Date: 05/29/2001
• Status: Active Grant

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Ciardo, Gianfranco, Cherkasova, Ludmila
• Granted Patent: US 6,546,473 B2
• Time in Patent Office: Days
• US Class Current: 711/133
• CPC Class Codes: G06F 12/122 of the least frequently used [LFU] type, e.g. with individual count value

Abstract

A method for determining the priority of documents in a web cache. The present invention incorporates the document size and the frequency of file access in determining which documents to keep in the cache and which documents to replace. The priority of a document is determined using a ratio of the frequency of access of the document raised to a first value to the size of the document raised to a second value, wherein the first value and the second value are rational numbers other than one. In one embodiment, the first value is greater than one and the second value is less than one. In another embodiment, the age of the document is also considered in determining the priority of a document. In the present embodiment, the ratio is added to a clock value, wherein the clock value is a running counter associated with the document starting at the time the document was first stored in the web cache.

Claims

1. A method for determining the priority of a file in a web cache comprising the computer-implemented steps of:

a) determining a frequency based on how many times said file has been accessed since it was stored in said web cache;

b) determining a size based on how many bytes comprise said file; and

c) determining said priority using a ratio of said frequency raised to a first value to said size raised to a second value, wherein said first value and said second value are rational numbers other than one.

2. The method as recited in claim 1 wherein said priority is determined by adding said ratio to a clock value, wherein said clock value is a running counter associated with said file, said clock value starting at the time said file was stored in said web cache.

3. The method as recited in claim 2 wherein said priority is determined by adding said ratio, said clock value, and said frequency.

4. The method as recited in claim 3 wherein said frequency raised to said first value equals one such that said ratio is one to size raised to a second value.

5. The method as recited in claim 2 wherein said clock value can be set to any monotonically increasing function to accommodate different aging mechanisms.

6. The method as recited in claim 1 wherein said first value is greater than one.

7. The method as recited in claim 1 wherein said second value is less than one.

8. A computer-usable medium having computer-readable program code embodied therein for causing a computer system to perform the steps of:

a) determining a frequency based on how many times said file has been accessed since it was stored in said web cache;

b) determining a size based on how many bytes comprise said file; and

c) determining said priority using a ratio of said frequency raised to a first value to said size raised to a second value, wherein said first value and said second value are rational numbers other than one.

9. The computer-usable medium as recited in claim 8 wherein said priority is determined by adding said ratio to a clock value, wherein said clock value is a running counter associated with said file, said clock value starting at the time said file was stored in said web cache.

10. The computer-usable medium as recited in claim 9 wherein said priority is determined by adding said ratio, said clock value, and said frequency.

11. The computer-usable medium as recited in claim 10 wherein said frequency raised to said first value equals one such that said ratio is one to size raised to a second value.

12. The computer-usable medium as recited in claim 9 wherein said clock value can be set to any monotonically increasing function to accommodate different aging mechanisms.

13. The method as recited in claim 8 wherein said first value is greater than one.

14. The method as recited in claim 8 wherein said second value is less than one.

16. The method as recited in claim 15 wherein said priority is determined by adding said ratio to a clock value, wherein said clock value is a running counter associated with said file, said clock value starting at the time said file was stored in said web cache.

17. The method as recited in claim 16 wherein said priority is determined by adding said ratio, said clock value, and said frequency.

18. The method as recited in claim 17 wherein said frequency raised to said first value equals one such that said ratio is one to size raised to a second value.

19. The method as recited in claim 16 wherein said clock value can be set to any monotonically increasing function to accommodate different aging mechanisms.

20. The method as recited in claim 15 wherein said first value is greater than one.

21. The method as recited in claim 15 wherein said second value is less than one.

15. A method for replacement of files in a web cache comprising the computer-implemented steps of:

a) requesting a file from said web cache, said web cache comprising at least one file, said web cache having a total size and a used size, wherein said total size is the number of bytes said web cache can store, wherein a used size is the number of bytes currently being stored by said web cache, each file having a priority, said priority determined by the steps of;

a1) determining a frequency based on how many times said cached file has been accessed since it was stored in said web cache;

a2) determining a size based on how many bytes comprise said cached file; and

a

     3) determining said priority using a ratio of said frequency raised to a first value to said size raised to a second value, wherein said first value and said second value are rational numbers other than one;

b) provided said file is located in said web cache, serving said file out of said web cache and updating said priority;

c) provided said file is not located in said web cache, determining whether to store said file in said web cache by performing the steps of;

c1) adding said file size of said file to said used size, resulting in a first value;

c2) provided said first value is less than said total size, adding said file to said web cache;

c3) provided said first value is greater than said total size, removing at least one of said files according to said priority until said used size is less than said total size; and

d) storing said file into said web cache.

22. A computer-usable medium having computer-readable program code embodied therein for causing a computer system to perform the steps of:

a) requesting a file from said web cache, said web cache comprising at least one file, said web cache having a total size and a used size, wherein said total size is the number of bytes said web cache can store, wherein a used size is the number of bytes currently being stored by said web cache, each file having a priority, said priority determined by the steps of;

a1) determining a frequency based on how many times said cached file has been accessed since it was stored in said web cache;

a2) determining a size based on how many bytes comprise said cached file; and

a3) determining said priority using a ratio of said frequency raised to a first value to said size raised to a second value, wherein said first value and said second value are rational numbers other than one;

b) provided said file is located in said web cache, serving said file out of said web cache and updating said priority;

c) provided said file is not located in said web cache, determining whether to store said file in said web cache by performing the steps of;

c1) adding said file size of said file to said used size, resulting in a first value;

c2) provided said first value is less than said total size, adding said file to said web cache;

c3) provided said first value is greater than said total size, removing at least one of said files according to said priority until said used size is less than said total size; and

d) storing said file into said web cache.

23. The computer-usable medium as recited in claim 22 wherein said priority is determined by adding said ratio to a clock value, wherein said clock value is a running counter associated with said file, said clock value starting at the time said file was stored in said web cache.

24. The computer-usable medium as recited in claim 23 wherein said priority is determined by adding said ratio, said clock value, and said frequency.

25. The computer-usable medium as recited in claim 24 wherein said frequency raised to said first value equals one.

26. The computer-usable medium as recited in claim 23 wherein said clock value can be set to any monotonically increasing function to accommodate different aging mechanisms.

27. The computer-usable medium as recited in claim 22 wherein said first value is greater than one.

28. The computer-usable medium as recited in claim 22 wherein said second value is less than one.

30. The method as recited in claim 29 wherein said priority is calculated according to

31. The method as recited in claim 30 wherein said Clock can be set to any monotonically increasing function to accommodate different aging mechanisms.

32. The method as recited in claim 29 wherein said α

is greater than one.

33. The method as recited in claim 29 wherein said β

is less than one.

29. A method for determining the priority of a file in a web cache, wherein said priority is calculated according to