Web Caching

Appendix E.  Cache Digests

We talked about Cache Digests and Bloom filters in Section 8.4. This appendix provides further information on the implementation. The discussion here is targeted towards developers and gets a little technical at times. Since interoperation is important, I include an example that developers can use to verify their implementations.

The Cache Digest Implementation

Since digests are designed to be shared between cooperating caches, all implementations must agree on (or have some way to determine) how many and which hash functions to use, the format of the digest key, and the size of the Bloom filter. This section describes Cache Digests Version 5, as implemented in Squid. Currently, there is no other formal documentation for Cache Digests, apart from some pages on the Squid web site.

Keys

Let’s start with the digest key. This is the chunk of data to which we apply the hash functions. The key is simply a unique identifier for each object in the cache. The URI alone is not a good cache key. Cached responses are identified by a request method, a URI, and possibly additional request fields. A Cache Digest key consists of the request method, encoded as an 8-bit value, followed by the URI string (see Figure E-1). The null byte that terminates the URI string is not included in the key. The values used to encode the request method are listed in Table E-1.

Table E-1. Cache Digest Request Method Encodings

Value	Method
0	NONE
1	GET
2	POST
3	PUT
4	HEAD
5	CONNECT
6	TRACE
7	PURGE
8	OPTIONS ...