hash algorithm for nginx cache

Johan Bergström johan at bergstroem.nu
Tue Apr 21 20:23:25 MSD 2009


On Apr 21, 2009, at 17:46 , Joe Bofh wrote:

> Igor,
> If you look at the docs, it is supposed to have excellent collision
> resistance.
> See http://tanjent.livejournal.com/756623.html
> Given that cache objects are supposed to have a limited shelf life
> (days, months), I would think that collision resistance is vs. hashing
> performance is a decent tradeoff.
> 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.

> --J
> Igor Sysoev wrote:
>> On Sat, Apr 18, 2009 at 08:27:11PM +0200, Joe Bofh wrote:
>>> See
>>> http://search.cpan.org/~tmaesaka/Digest-MurmurHash-0.10/lib/Digest/MurmurHash.pm#BENCHMARK
>>> http://murmurhash.googlepages.com/
>>> for sample implementations.
>> Thank you for information, but as I understand this hash produce  
>> 32- or
>> 64-bit hash. I believe it should have more collisions as compared to
>> md5,
>> which is 128-bit hash.
> -- 
> Posted via http://www.ruby-forum.com/.

More information about the nginx mailing list