Re: reversible fingerprint comment in membuffer code

Philip Martin <philip.martin_at_wandisco.com> writes:

> Is this comment in cache-membuffer.c:combine_key correct?
>
> /* scramble key DATA. All of this must be reversible to prevent key
> * collisions. So, we limit ourselves to xor and permutations. */
> data[1] = (data[1] << 27) | (data[1] >> 37);
> data[1] ^= data[0] & 0xffff;
> data[0] ^= data[1] & APR_UINT64_C(0xffffffffffff0000);
>
> I don't see why this needs to be reversible, and it's not clear it is
> reversible.

I talked to Stefan and I believe I can explain. Reversibility is not a
hard requirement on trunk or 1.9 at present, since we store the full
key, but may be a requirement in future. This code is for keys that fit
in the fingerprint and when generating the fingerprint from such keys we
want to avoid introducing collisions, i.e. distinct keys should generate
distinct fingerprints. The cache would cope with collisions but is
better without. A reversible scramble is one way to ensure no
collisions are introduced.

The other reason for the scramble is that it spreads the variation for
small keys across more bytes of the fingerprint and thus across the
cache.

-- 
Philip Martin | Subversion Committer
WANdisco // *Non-Stop Data*