Memory admission control based on object size or request frequency

• US 7,051,161 B2
• Filed: 09/17/2002
• Issued: 05/23/2006
• Est. Priority Date: 09/17/2002
• Status: Active Grant

• Current Assignee: III Holdings 3, LLC
• Original Assignee: Nokia Corporation
• Inventors: Dixit, Sudhir, Wu, Tau
• Primary Examiner(s): Moazzami, Nasser
• Application Number:
  US10/244,449
• Publication Number:
  US 20040054860A1
• Time in Patent Office: 1,344 Days
• Field of Search: 711/122, 711/130, 711133-134, 711160-171, 711/216, 709217-218, 709/223, 709/226
• US Class Current: 711/134
• CPC Class Codes: G06F 12/0888 using selective caching, e.g. bypass
• CPC Class Codes: G06F 12/123 with age lists, e.g. queue, most recently used [MRU] list or least recently used [LRU] list
• CPC Class Codes: G06F 16/9574 of access to content, e.g. by caching

Abstract

Admission of new objects into a memory such as a web cache is selectively controlled. If an object is not in the cache, but has been requested a specified number of prior occasions (e.g., if the object has been requested at least once before), it is admitted into the cache regardless of size. If the object has not previously been requested the specified number of times, the object is admitted into the cache if the object satisfies a specified size criterion (e.g., if it is smaller than the average size of objects currently stored in the cache). To make room for new objects, other objects are evicted from the cache on, e.g., a Least Recently Used (LRU) basis. The invention could be implemented on existing web caches, on distributed web caches, in client-side web caching, and in contexts unrelated to web object caching.

Claims

1. A method of managing a computer memory by selectively admitting new objects into the memory, comprising:

receiving requests for objects not stored in the memory;

determining, as to each of the requested objects, whether the requested object has previously been requested a designated number of times, wherein the designated number is fixed;

as to each of the requested objects determined to have previously been requested the designated number of times, storing the requested object in the memory based upon that determination;

receiving requests for additional objects not stored in the memory, wherein at least some of the additional requested objects have not previously been requested the designated number of times;

determining, as to each of the additional requested objects, whether the additional requested object satisfies a size criterion;

as to each of the additional requested objects satisfying the size criterion, storing the additional requested object in the memory based upon the additional requested object satisfying the size criterion and without regard to whether the additional requested object has previously been requested the designated number of times; and

evicting one or more previously-stored objects in connection with storing one of the additional requested objects that satisfies the size criterion and that has not previously been requested.

2. The method of claim 1, further comprising:

determining, as to each of the additional requested objects, and prior to determining whether the additional requested object satisfies the size criterion, that the additional requested object has not previously been requested designated number of times.

3. The method of claim 1, further comprising:

updating data records of a first type to indicate that the requested objects and additional requested objects have been requested.

4. The method of claim 3, further comprising:

updating a second type of data record upon storage in the memory of one of the requested objects or one of the additional requested objects and recalculating the size criterion based upon said storage.

5. The method of claim 1, wherein the evicted one or more previously-stored objects are evicted on a Least Recently Used (LRU) basis.

6. The method of claim 1, wherein receiving requests for objects and receiving requests for additional objects comprise receiving requests for objects having Universal Resource Locators (URLs).

7. The method of claim 6, wherein receiving requests for objects having URLs comprises receiving requests for web content available from an origin web server.

8. The method of claim 6, further comprising:

determining, as to each of the additional requested objects, and prior to determining whether the additional requested object satisfies the size criterion, that the additional requested object has not previously been requested the designated number of times.

9. The method of claim 6, further comprising:

updating data records of a first type to indicate that the requested objects and the additional requested objects have been requested;

updating a second type of data record upon storage in the memory of one of the requested objects or one of the additional requested objects and recalculating the size criterion based upon said storage.

10. The method of claim 6, wherein the evicted one or more previously-stored objects are evicted on a Least Recently Used (LRU) basis.

11. A method of managing a computer memory by selectively admitting new objects into the memory, comprising:

receiving a request for an object not stored in the memory;

storing the objcct in the memory if it has previously been requested a designated number of times;

storing the object in the memory if its size satisfies a size criterion; and

evicting, as may be necessary in connection with storing a not-previously-requested object having a size satisfying the size criterion, one or more currently stored objects, wherein;

storing the object in the memory if it has previously been requested comprises storing the object in memory if the object has been requested one prior time, and

storing the object in memory if its size satisfies the size criterion comprises storing the object in memory if it is smaller than the average size of objects currently stored.

12. The method of claim 11, wherein the step of storing the object in the memory if it has previously been requested comprises storing the object in the memory based on the object having been requested the designated number of times.

13. A method of managing a computer memory by selectively admitting new objects into the memory, comprising:

receiving a request for an object not stored in the memory;

storing the object in the memory if it has previously been requested a designated number of times;

storing the object in the memory if its size satisfies a size criterion; and

evicting, as may be necessary in connection with storing a not-previously-requested object having a size satisfying the size criterion, one or more currently stored objects, wherein;

receiving a request for an object comprises receiving a request for an object having a Universal Resource Locator (URL),

storing the object in the memory if it has previously been requested comprises storing the object in memory if the object has been requested one prior time, and

storing the object in memory if its size satisfies the size criterion comprises storing the object in memory if it is smaller than the average size of objects currently stored.

14. The method of claim 13, wherein the step of storing the object in the memory if it has previously been requested comprises storing the object in the memory based on the object having been requested the designated number of times.

15. A server, comprising:

at least one network connection permitting communication with client devices and with origin servers providing objects;

a memory; and

a processor configured to control admission of objects into the memory by

receiving requests for objects not stored in the memory and retrieving the requested objects from one or more of the origin servers,

determining, as to each of the requested objects, whether the requested object has previously been requested a designated number of times, wherein the designated number is fixed,

as to each of the requested objects determined to have previously been requested the designated number of times, storing the requested object in the memory based upon that determination,

receiving requests for additional objects not stored in the memory, wherein at least some of the additional requested objects have not previously been requested the designated number of times, and retrieving the additional requested objects from one or more of the origin servers,

determining, as to each of the additional requested objects, whether the additional requested object satisfies a size criterion,

as to each of the additional requested objects satisfying the size criterion, storing the additional requested object in the memory based upon the additional requested object satisfying the size criterion and without regard to whether the additional requested object has previously been requested the designated number of times, and

evicting one or more previously-stored objects, in connection with storing one of the additional requested objects that satisfies the size criterion and that has not previously been requested.

16. The server of claim 15, wherein the processor is configured to

determine, as to each of the additional requested objects, and prior to determining whether the additional requested object satisfies the size criterion, that the additional requested object has not previously been requested the designated number of times.

17. The server of claim 15, wherein the processor is further configured to update data records of a first type to indicate that the requested objects and additional requested objects have been requested.

18. The server of claim 17, wherein the processor is further configured to update a second type of data record upon storage in the memory of one of the requested objects or one of the additional requested objects and to recalculate the size criterion based upon said storage.

19. The server of claim 15, wherein the processor is configured to evict one or more previously-stored objects on a Least Recently Used (LRU) basis.

20. The server of claim 15, wherein the server is a web server, wherein receiving requests for objects and receiving requests for additional objects comprise receiving requests for objects having Universal Resource Locators (URLs), and wherein the processor is configured retrieve the requested objects and additional requested objects from one or more of the origin servers based on their URLs.

21. The server of claim 20, wherein the requested objects and additional requested objects comprise web content.

22. The server of claim 20, wherein the processor is configured to

determine, as to each of the additional requested objects, and prior to determining whether the additional requested object satisfies the size criterion, that the additional requested object has not previously been requested the designated number of times.

23. The server of claim 20, wherein the processor is further configured to:

update data records of a first type to indicate that the requested objects and the additional requested objects have been requested, and

update a second type of data record upon storage in the memory of one of the requested objects or one of the additional requested objects and to recalculate the size criterion based upon said storage.

24. The server of claim 20, wherein the processor is configured to evict one or more previously-stored objects on a Least Recently Used (LRU) basis.

25. A server, comprising:

at least one network connection permitting communication with client devices and with one or more origin servers providing objects;

a memory; and

a processor configured to control admission of objects into the memory by

receiving a request for an object not stored in the memory and retrieving the object from an origin server,

storing the object in the memory if it has previously been requested one prior time,

storing the object in the memory if its size is smaller than the average size of objects currently stored, and

evicting, as may be necessary in connection with storing a not-previously-requested object having a size that satisfies the size criterion, one or more currently stored objects.

26. The server of claim 25, wherein the server is a web server, wherein the requested object has a Universal Resource Locator (URL), and wherein the processor is configured to retrieve the object from an origin server based on the URL.

27. The server of claim 25, wherein the step of storing the object in the memory if it has previously been requested comprises storing the object in the memory based on the object having been requested the designated number of times.

28. The server of claim 26, wherein the step of storing the object in the memory if it has previously been requested comprises storing the object in the memory based on the object having been requested the designated number of times.

29. A machine-readable medium having machine-executable instructions for performing steps comprising:

receiving requests for objects not stored in a memory;

determining, as to each of the requested objects, whether the requested object has previously been requested a designated number of times, wherein the designated number is fixed;

as to each of the requested objects determined to have previously been requested the designated number of times, storing the requested object in the memory based upon that determination;

receiving requests for additional objects not stored in the memory, wherein at least some of the additional requested objects have not previously been requested the designated number of times;

determining, as to each of the additional requested objects, whether the additional requested object satisfies a size criterion;

as to each of the additional requested objects satisfying the size criterion, storing the additional requested object in the memory based upon the additional requested object satisfying the size criterion and without regard to whether the additional requested object has previously been requested the designated number of times; and

evicting one or more previously-stored objects, in connection with storing one of the additional requested objects that satisfies the size criterion and that has not previously been requested.

30. The machine-readable medium of claim 29, comprising further machine-executable instructions for performing the steps of:

determining, as to each of the additional requested objects, and prior to determining whether the additional requested object satisfies the size criterion, that the additional requested object has not previously been requested the designated number of times.

31. The machine-readable medium of claim 29, comprising further machine-executable instructions for performing the step of:

updating data records of a first type to indicate that the requested objects and additional requested objects have been requested.

32. The machine-readable medium of claim 31, comprising further machine-executable instructions for performing the steps of:

updating a second type of data record upon storage in the memory of one of the requested objects or one of the additional requested objects and recalculating the size criterion based upon said storage.

33. The machine-readable medium of claim 29, wherein the evicted one or more previously-stored objects are evicted on a Least Recently Used (LRU) basis.

34. The machine-readable medium of claim 29, wherein receiving requests for objects and receiving requests for additional objects comprise receiving requests for objects having Universal Resource Locators (URLs).

35. The machine-readable medium of claim 34, wherein receiving requests for objects having URLs comprises receiving requests for web content available from an origin web server.

36. The machine-readable medium of claim 34, comprising further machine-executable instructions for performing the steps of:

determining, as to each of the additional requested objects, and prior to determining whether the additional requested object satisfies the size criterion, that the additional requested object has not previously been requested the designated number of times.

37. The machine-readable medium of claim 34, comprising further machine-executable instructions for performing the steps of:

updating data records of a first type to indicate that the requested objects and the additional requested objects have been requested;

updating a second type of data record upon storage in the memory of one of the requested objects or one of the additional requested objects and recalculating the size criterion based upon said storage.

38. The machine-readable medium of claim 34, wherein the evicted one or more previously-stored objects are evicted on a Least Recently Used (LRU) basis.

39. A machine-readable medium having machine-executable instructions for performing steps comprising:

receiving a request for an object not stored in a memory;

storing the object in the memory if it has previously been requested a designated number of times;

storing the object in the memory if its size satisfies a size criterion; and

evicting, as may be necessary in connection with storing a not-previously-requested object having a size satisfying the size criterion, one or more currently stored objects, wherein

storing the object in the memory if it has previously been requested comprises storing the object in memory if the object has been requested one prior time, and

storing the object in memory if its size satisfies the size criterion comprises storing the object in memory if it is smaller than the average size of objects currently stored.

40. The machine-readable medium of claim 39, wherein the step of storing the object in the memory if it has previously been requested comprises storing the object in the memory based on the object having been requested the designated number of times.

41. A machine-readable medium having machine-executable instructions for performing steps comprising:

receiving a request for an object not stored in a memory;

storing the object in the memory if it has previously been requested a designated number of times;

storing the object in the memory if its size satisfies a size criterion; and

evicting, as may be necessary in connection with storing a not-previously-requested object having a size satisfying the size criterion, one or more currently stored objects, wherein

receiving a request for an object comprises receiving a request for an object having a Universal Resource Locator (URL),

storing the object in the memory if it has previously been requested comprises storing the object in memory if the object has been requested one prior time, and

storing the object in memory if its size satisfies the size criterion comprises storing the object in memory if it is smaller than the average size of objects currently stored.

42. The machine-readable medium of claim 41, wherein the step of storing the object in the memory if it has previously been requested comprises storing the object in the memory based on the object having been requested the designated number of times.

43. A method of controlling admission of objects into a web cache, comprising:

receiving a request for an object not in the cache, the object being identifiable by a Universal Resource Locator (URL);

determining if the object has previously been requested;

caching the object if it has previously been requested;

updating, if the object has not been previously requested, a first data record to indicate that the object has been requested;

comparing the size of the object to the average size of objects currently cached;

caching the object if its size is less than the average size of objects currently cached;

evicting, in connection with caching the object, one or more currently cached objects on a Least Recently Used (LRU) basis;

updating, upon admission of the object into the cache a second data record to indicate presence of the object in the cache; and

recalculating the average size of currently cached objects based upon the presence of the object in the cache.

44. A method of managing a computer memory by selectively admitting new objects into the memory, comprising:

(a) receiving requests for objects not stored in the memory;

(b) evaluating each of the objects according to a first criterion, wherein the first criterion is based solely on the number of previous requests for the object;

(c) as to each of the objects satisfying the first criterion in step (b), storing the object in the memory based on satisfaction of the first criterion;

(d) as to each of the objects not satisfying the first criterion in step (b), evaluating the object according to a second criterion, wherein the second criterion is based solely on size of the object in comparison to another size value;

(e) as to each of the objects satisfying the second criterion in step (d), storing the object in the memory based on satisfaction of the second criterion;

(f) as to each of the objects not satisfying the second criterion in step (d), not storing the object in the memory until a subsequent request for the object; and

(g) evicting one or more previously stored objects in connection with storing one of the objects that satisfies the second criterion and does not satisfy the first criterion.