Re: key length

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.

Alex.

On Sun, 23 Dec 2001, Jon Kay wrote:

> I would like to start a discussion about key length.
>
> Cache Digests and Hint Caches both use md5 keys in
> similarly central roles. However, Squid uses 16-byte digests and
> Hint Cache uses 8-byte digests. Hint Caches distribute keys as part
> of our updates, and so we are sensitive to key size, whereas Cache
> Digests do not. We figured that that 64 bits is sufficient guard
> against hash collisions, in a world that has less than 2^64 atoms.
>
> Thoughts on a merge?
>
> I could create two separate hash tables, with separate key-handling
> code, to handle this (and suspect that's what's going to happen), but
> it seems silly.
>
> If we raise our size from 8 to 16 bytes, the current Hint protocol
> structure rises from 20 to 28 bytes, raising per-update overhead 40%
> and making the protocol that much less attractive in banwdwidth-scarce
> spots.
>
>
> Mike, I hope you don't mind that I cc'ed you, since I think
> 8 bytes was your decision originally.
> --
> Jon Kay pushcache.com jkay@pushcache.com
> http://www.pushcache.com/ (512) 420-9025
> Squid consulting 'push done right.'
>
Received on Sun Dec 23 2001 - 10:35:35 MST