Re: Cache keys

Jeffrey Mogul:
>
>This was one of the few remaining sections of the draft that I had
>not been able to write.  After the discussions of the past few days
>(online and on the telephone), and a lot of puzzling, I think I've
>been able to write a fairly concise set of rules for constructing
>and using cache keys.  Comments are welcome, but due to various
>schedule constraints, something very close to this is going to be
>in Monday's draft from Jim.
>
>-Jeff
>
>13.12 SLUSHY: Cache keys
>   A ``cache key'' is a value used to identify a cache entry.  HTTP
>   caches construct keys in three different ways:

Change this to:

    HTTP caches construct three different kinds of cache keys:

>      - Some subset of the fields stored with a cache entry
>        constitute the ``entry key'' for that entry.  These may
>        include the Request-URI, some request-header fields, and
>        some response-header fields.
>
>      - Some subset of the fields of a response, together with
>        perhaps the Request-URI, constitute the ``replacement key''
>        of a response.
>
>      - Some subset of the fields of a request, together with the
>        Request-URI, constitute the ``lookup key'' of a request.
>
>   When a cache receives a request, it builds a lookup key from that
>   request, then tries to find (lookup) a cache entry with a matching
>   entry key.

I think it is better to talk about `find (lookup) a matching cache
entry', and to forget about the entry key concept.

>   If such a match exists, then the cache can decide (based
>   on the other caching rules) whether to return that entry in reply to
>   the request.
>
>   When a cache receives a response, it builds a replacement key from
>   that response, and from the request that elicited it.  It uses this
>   key to find any previously stored entry with a matching entry key.
                                                   ^^^^^^^^^^^^^^^^^^      
why not `equal replacement key'?

>   If such an entry exists, the cache replaces the old entry with the
>   new one.
>
>      The term ``replacement'' means to remove the old entry from the
>      cache, and then to insert the new entry.  It does not imply a
>      modification of an existing entry.
>
>   This section describes specifically how the three kinds of keys are
>   constructed, and how a cache determines if keys match.
>
>13.12.1 SLUSHY: Key-matching procedure
>   We express replacement keys as a tuple (URI, variant-ID), in which
>   the variant-ID may be null.

Sigh.  I put text in the spec two weeks ago in which replacement keys
also containing the Content-Location header.  I am willing to change
that text if you are willing to make variant-IDs quoted stings instead
of tokens.

>   We express lookup keys as a tuple (URI,
>   variant-ID, all-request-headers), in which the variant-ID may be
>   null.  The all-request-headers element of the tuple is not always
>   used, but is included here as a notational convenience.  We express
>   entry keys as the tuple (URI, variant-ID, sel-hdr-values), in which
>   the variant-ID may be null, and the sel-hdr-values may either be
>   null, or may be a set of request headers.

The variant-ID cannot be part of the lookup key.  You write:

      - Some subset of the fields of a request, together with the
        Request-URI, constitute the ``lookup key'' of a request.

and there is no variant-ID in the request.

>   A replacement key matches an entry key if both their URI elements
>   match and their variant-ID elements match.  (A null variant-ID does
>   not match a non-null variant-ID.)
>
>   A lookup key matches an entry key if both their URI elements match
>   and their variant-ID elements match, and either
>
>      - the sel-hdr-values element of the entry key is null
>
>   or
>
>      - the sel-hdr-values element of the entry key matches the
>        appropriate headers in the all-request-headers element of
>        the request key, according to the matching rules in section
>        10.v.

There needs to be added detail here about Vary: {other}, and probably
also about freshness.

>   This description matching algorithm is clearly not the most efficient
>   implementation of an equivalent algorithm.  A cache may use any
>   algorithm that yields equivalent results.  For example, it may use a
>   hierarchical approach where cache entries are grouped into sets by
>   the URI and variant-ID, and only if a set includes non-null
>   sel-hdr-values elements does the cache need to consider the other
>   request headers.
>
>   If on a cache lookup there are two or more entries that appear to
>   match the request, then the one with the most recent Date value MUST
>   be used.

(Note: I did not have time to read the other sections in the original
message yet).

Koen.

Received on Friday, 19 April 1996 15:57:45 UTC