Caching Algorithm of CERN httpd

Which Documents Are Subject to Being Cached?

• The request method must be GET; for other methods caching does not make sense or is not particularly worth the effort (caching PUT or POST would be pathological behaviour).

• The request is not a query, i.e. there is no ?keywords part in the request URL. This is because queries produce usually dynamic results, e.g. database queries, and currently these results rarely contain expiry information although they should. Futhermore, the same keyword is often very unlikely to be requested in the near future; imagine an ISMAP query as an example.

• Document is not protected, i.e. no Authorization header field is in the request.

• The document doesn't expire immediately or have a very short lifetime.

• The requested resource is served by an HTTP, FTP or Gopher server;
  • Caching News would be rarely desirable since the NNTP server is usually somewhere very close.

  • WAIS consists mainly of database queries so it is not cached for the same reasons that query URL's are not. Additionally, WAIS URL's are so exotic that caching them would cause problems in httpd's current cache design.

Caching Only Certain Documents/Sites

Preventing Caching of Certain URL's

Expires HTTP Response Header

Especially, if the document expires immediately or within a very short time (a couple of minutes) it is never even written to the cache file. This saves resources because the same file is very unlikely to be requested again within a minute. Actually, sometimes what appears to be a lifetime of one minute could well be an inaccurate machine clock that is off by one minute, and expiry should be immediate.

Documents with an invalid Expires header line are never cached.

Use of Expires header field is the only correct way to determine if a document should be cached; strictly speaking documents without this field should never be cached. However, since in practise Expires header is extremely rarely given by the current HTTP servers, it is necessary to use approximative algorithms to calculate some kind of expiry date for documents that otherwise don't have it.

Furthermore, Expires field is part of only the HTTP protocol, not other WWW protocols.

Last-Modified HTTP Response Header

CERN httpd handles this via a last-modified factor, or LM factor for short. This factor specifies the fraction of time since last modification that the file is approximated to remain valid.

For example, with LM factor 0.1 a file that was changed ten hours ago it be considered to be up-to-date for one hour, and a file that was modified a month ago will expire after three days.

LM factor can be specified differently for URL's matching different URL patterns.

Default Expiry Time

However, since documents without a last-modified field are very often produced by CGI scripts on the fly it is safest to keep this value in zero, or very small. Afterall, most of the script responses should never be cached, but reproduced by the script every time, because the content usually changes.

If a CGI script produces output that is valid for a certain time it should express this by returning an Expires header field. As an example consider a result of a database lookup and the database is updated every night at 2:30; clearly the same query will return the same results at least until 2:30, so that time should be specified as the expiry time.

Guaranteed Cache Refresh Interval

As a special case, specifying the refresh interval to be zero every cache access will cause a check to be made from remote server. This is ideal for users who need to have always the absolutely most up-to-date version, but still want faster response times and saves in network costs. This is still cheaper as all the checks are performed using the conditional GET request, which sends the document only if it has changed, and otherwise tells the proxy to use the cache.

Conditional GET Request

If the document hasn't changed httpd will recalculate a new expiry date for it, using the old last-modification date with the LM factor approximation; that is of course only if no expiry date was explicitly given in the "Not modified" response.

CERN httpd's Physical Cache Design

As CERN httpd was probably the first WWW proxy ever to provide caching we picked this particular design to make it easy to debug the caching system, and sometimes go and fix the cache by hand. This will eventually be replaced by something more efficient. The current one clearly has some flaws in it, like DNS aliases for host names cause multiple caching of same documents. This can be solved by using the IP number string instead of the host name.

Using the Maximum Cache Capacity

If disk space is a critical factor, that is, if it's desirable that httpd keeps its cache in the minimum, it always removes all the expired files during the garbage collection. This is the default behaviour.

However, this is wasteful. Often files that have expired have not in fact changed, and a simple conditional GET request could be made to verify this and make them up-to-date again ("Not modified" HTTP response contains a new expiry date, or one can be calculated from the data in the cache database).

CERN httpd has a mode when it lets its cache fill up and removes only files that haven't been used in a long time (as usual, this time can be configured according to URL patterns). All expired files are kept until it is absolutely necessary to sacrifice some of them to get space for new ones. If there is sufficient amount of disk space available this situation is never reached, and httpd is able to get optimal performance for conditional GET request.

Standalone Cache Mode