hash algorithm for nginx cache

Joe Bofh lists at ruby-forum.com
Wed Apr 22 03:22:52 MSD 2009

FWIW, I got a follow up reply from Austin (the chap that created 
murmurhash). He sez:

"MurmurHash2, MD5, Lookup3, and any cryptographic hash all have 
statistically-correct collision behaviour - the average number of 
collisions they create on a given keyset is the same as if the hash 
function returned a totally random number. For comparison, FNV mixes 
very poorly and tends to produce massively more collisions than expected 
on "sparse" keys with only a few bits set, and SuperFastHash will tend 
to produce a higher than expected number of collisions on keysets where 
keys differ in only 2-3 bits - see 
http://murmurhash.googlepages.com/statistics and the associated pages 
for more info."

So it looks like collision-wise, it's comparable.


Johan Bergström wrote:
> Hey,
> On Apr 21, 2009, at 17:46 , Joe Bofh wrote:
>> I guess if you put in an option to specify the hash, that would work
>> too. FNV and Murmur have been adopted on various open source  
>> projects as
>> optional hashs because of the hashing performance.
> For reference; libmemcached - another high performing project -
> nowadays include most current hashing algorithms. Fnv1a and murmur are
> two of them. See: 
> http://hg.tangent.org/libmemcached/file/048b32d9d1ae/docs/memcached_behavior.pod
>   (sorry for bad linkage, the site docs/manpage hasn't been updated
> for a while)
> Two my knowledge, murmur/murmur2 is the best pick for a high
> performance/low (but not zero) collision tradeoff.

Posted via http://www.ruby-forum.com/.

More information about the nginx mailing list