Methods and apparatus for implementing a chche replacement scheme

• US 6,883,068 B2
• Filed: 12/17/2001
• Issued: 04/19/2005
• Est. Priority Date: 12/17/2001
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Chawla, Rajeev, Tsirigotis, Panagiotis, Radia, Sanjay R.
• Primary Examiner(s): LANE, JOHN A
• Application Number:
  US10/016,123
• Publication Number:
  US 20030115420A1
• Time in Patent Office: 1,219 Days
• Field of Search: 711/133, 711/134, 709/213, 709/216
• US Class Current: 711/133
• 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

Methods and systems are provided for processing a cache. A candidate object is identified for updating. A fresh object corresponding to the candidate object is obtained if it is determined that a newer version of the candidate object is available. A destination buffer is selected from a group of primary and non-primary buffers based on an amount of available space in a primary buffer. The fresh object is stored in the destination buffer.

Claims

1. A method of refreshing a cache, the cache comprising at least one cached object, the cache including at least one candidate object to be updated, the method comprising:

obtaining a fresh object corresponding to the candidate object when it is determined that a newer version of the candidate object is available;

identifying a destination buffer, chosen from at least one primary buffer and at least one non-primary buffer, in which to store the fresh object based on an amount of available space in the primary buffer; and

storing the fresh object in the destination buffer.

2. A method according to claim 1 further comprising:

receiving a request for a requested object;

identifying a source buffer corresponding to the requested object; and

moving the requested object from the source buffer to the primary buffer when the source buffer is the non-primary buffer.

3. A method according to claim 1 further comprising:

receiving a request for a requested object, the request originating from a requester;

accessing an entry in a table corresponding to the at least one cached object using a table index, the accessing based on identifying information associated with the requested object;

identifying a source buffer based on buffer identification information from the table;

obtaining the requested object from the source buffer;

updating the primary buffer with the requested object if the source buffer is an overflow type buffer; and

transmitting the requested object to the requester.

4. A method according to claim 1, wherein obtaining the fresh object is performed by retrieving the fresh object from an origin server.

5. A method according to claim 4 further comprising:

requesting information from the origin server to determine that the newer version of the candidate object is available.

6. A method according to claim 1 further comprising:

identifying the candidate object based on expiration information associated with the cached object.

7. A method according to claim 6, wherein the primary buffer comprises at least one primary cyclic buffer, wherein the primary cyclic buffer is stored on at least one disk drive;

and

wherein the non-primary buffer comprises a cyclic overflow buffer stored on at least one disk drive, wherein the cyclic overflow buffer is configured to receive the fresh object.

8. A method according to claim 1 further comprising:

identifying the candidate object based on a position within the primary buffer.

9. A method for managing a cache, the method comprising:

obtaining current information corresponding to a set of information units by identifying target information units for which updated information is available;

identifying an information destination, chosen from at least one primary destination and at least one non-primary destination, in which to store the updated information based on an amount of available space in the primary destination;

storing the updated information in the information destination;

receiving a request;

identifying a source having requested information corresponding to the request, the source being from a group consisting of a primary storage location and an overflow storage location;

moving the requested information from the source to the primary storage location if the source is the overflow storage location.

10. A method according to claim 9 further comprising transmitting the requested object to a requester after the requested information is moved.

11. A method according to claim 9, wherein obtaining the current information is accomplished by connecting to a server over a data network and requesting the current information from the server.

12. A method of maintaining files in a cache, the method comprising:

obtaining at least one updated file corresponding to at least one of a plurality of expired files within the cache by identifying those of the expired files that have changed on a corresponding origin server;

identifying a file storage means, chosen from at least one primary file storage means and at least one non-primary file storage means, in which to store the updated file based on availability in the primary storage means; and

moving the updated file from the non-primary storage means to the primary storage means upon receiving a request to provide access to the updated file.

13. An apparatus for updating a cache, the apparatus comprising:

a network interface controller operative to receive a fresh object corresponding to a stale object when it is determined that a fresh object is available; and

a memory management controller operative to select a memory segment, chosen from at least one primary segment and at least one overflow segment, in which to store the fresh object based on an amount of available space in the primary segment, wherein the memory management controller is operative to store the fresh object in the selected memory segment.

14. An apparatus according to claim 13, wherein the network interface controller is further operative to request information from an origin server to determine that the fresh object is available.

15. An apparatus according to claim 13 further comprising a processor operative to identify the stale object based on expiration information.

16. An apparatus according to claim 13 further comprising:

a network listener operative to receive a request for an object, wherein the listener is configured to move the requested object into the primary segment, in the case where the requested object was previously stored in the overflow segment.

17. Apparatus according to claim 13 further comprising:

a network service operative to transmit a fresh object over a network, wherein the network service is operative to move the fresh object from the overflow segment to the primary segment.

18. An apparatus for implementing a cache replacement scheme, the apparatus comprising:

means for obtaining a fresh object corresponding to a stale object when it is determined that a fresh object is available;

means for identifying a first storage means from a group comprising a primary storage means and an overflow storage means based on an amount of free space in the primary storage means; and

means for storing the fresh object in the first storage means.

19. An apparatus for updating cache, the apparatus comprising:

means for receiving newer information corresponding to information-containing means by identifying target information-containing means for which the newer information is available;

information-storage means, chosen from at least one of primary-storage means and overflow-storage means for storing the newer information based on an amount of available space in the primary-storage means;

means for storing the updated information in the information-storage means;

means for receiving a request;

means for identifying a source having requested information corresponding to the request; and

means for moving the requested information from the source to the primary-storage means when the source corresponds to the overflow-storage means.

20. A computer-readable medium containing instructions operative to cause a processor to refresh a cache, the computer-readable medium comprising:

program code configured to obtain a fresh object corresponding to a candidate object when it is determined that the candidate object is expired and a newer version of the candidate object is available;

identification program code configured to identify a destination buffer, the destination buffer chosen from at least one primary buffer and at least one overflow buffer, wherein the fresh object is stored in the destination buffer and wherein the identification program code causes the processor to identify the destination buffer based on an amount of available space in the primary buffer.

21. A computer-readable medium according to claim 20 further comprising:

program code configured to receive a request;

program code configured to identify a source buffer corresponding to the request; and

program code configured to move the requested object from the source buffer to the primary buffer when the source buffer is the overflow buffer.

22. A computer-readable medium according to claim 20, wherein the program code for obtaining the fresh object includes instructions capable of retrieving the fresh object from an origin server.

23. A computer-readable medium according to claim 20, further comprising:

program code configured to identify the candidate object based on expiration information associated with the object, wherein a table of expiration information is maintained by the processor.

24. A computer-readable medium according to claim 20, further comprising:

program code configured to identify the candidate object based on a location in persistent memory associated with the processor.

25. A computer-readable medium containing instructions operative to implement a cache replacement scheme, the computer-readable medium comprising:

program code for obtaining current information corresponding to a set of information units by identifying target information units for which updated information is available;

program code for identifying an information destination, chosen from at least one primary destination and at least one non-primary destination, in which to store the updated information based on an amount of available space in the primary destination;

program code for storing the updated information in the information destination;

program code for receiving a request; and

program code for identifying a source having requested information corresponding to the request, the source chosen from a primary storage location and an overflow storage location.

26. A computer-readable medium containing software associated with a method of maintaining a web cache, the software comprising:

instructions capable of causing a web server to obtain from an origin server at least one updated web page corresponding to at least one stale web page;

instructions capable of causing the web server to store the updated web page in an overflow cyclic buffer associated with a primary cyclic buffer; and

instructions capable of causing the web server to move the updated web page from the overflow cyclic buffer to the primary cyclic buffer upon receiving a request to download a requested web page having a URL associated with the updated web page.