Re: key length

From: Jon Kay <>
Date: Tue, 25 Dec 2001 00:59:21 -0600

Alex Rousskov wrote:
> Hi Jon,
> I have posted URL collision numbers for various key lengths to
> squid-dev a year or so ago. IIRC, based on Duane's hierarchy traces
> (one week long?), there are a few collisions with key length of 6 and
> no collisions with key length 8. If you need details, please find that
> post in the archives.
> If you change key length to 8, somebody needs to double check
> and test that the store code compares the key with the actual URL when
> loading an entry and detects collisions. I doubt there will be many
> collisions with 8 byte keys, but a check may be in order just to feel
> safe.
> Somebody will also need to rewrite Cache Digest hash functions
> to use 8-byte keys. AFAIK, this change will break Cache Digest
> compatibility with caches running versions with 16-byte keys.


As Bill Gates would say, NEVER EVER break compatibility.

Some luck turned up here. Turned out that the existing hint
code already takes the first 8 bytes of a 16-bytemd5 digest.

Whew! So that lets me dodge 2/3 of the nastiness.

I've coded in a separate hint_table, alas. But I am able to
reuse the existing key generation code and even the keys
themselves. There is a separate HintCacheKey (used to be
GenericKey), but it is now used as a pointer to a cache_key
that thinks the thing it points at is half as long as it is.

I was afraid that there would be some worse detail standing in
the way, but so far it looks good, modulo pre-tolower()ing questions.

Jon Kay                                         (512) 420-9025
Squid installation, maintenance, and coding       'push done right.'
Received on Tue Dec 25 2001 - 00:01:35 MST

This archive was generated by hypermail pre-2.1.9 : Tue Dec 09 2003 - 16:14:41 MST