Re: Questions about hash functions of CRUSH

[Sage Weil <sage@xxxxxxxxxxxx>]

On Fri, 13 Apr 2012,  wrote:
> Hi everyone.
> 
> I'm still reading CRUSH source code.
> 
> When reading src/crush/hash.c, I've got some questions about the hash function.
> 
> 1. There are several magic numbers there, like 1315423911, 231232,
> 1232. Are they arbitrary or do they really mean something in theory?

You'll notice there are lots of 1's, 2's, and 3's... that was me mashing 
the keyboard.  :)

> 2. crush_hashmix macro is a part of Jenkins hash function. In the
> series of crush_hash_rjenkins1_* functions, why input parameters are
> mixed this way instead of something else? Are they arbitrary or do
> they really mean something in theory?
> 
> > For example
> >  crush_hashmix(a, b, hash);
> >  crush_hashmix(c, d, hash);
> >  crush_hashmix(e, x, hash);
> >  crush_hashmix(y, a, hash);
> >  crush_hashmix(b, x, hash);
> >  crush_hashmix(y, c, hash);
> >  crush_hashmix(d, x, hash);
> >  crush_hashmix(y, e, hash);
> > Do the order and combinations matter something?

I did some experimentation and that seemed to get all of the bits mixed in 
well.  It was not particularly methodical, so it is something we'll want 
to revisit and properly measure for the next CRUSH revision to see if a 
change is warranted.

sage