Hi, check out this page http://bretm.home.comcast.net/hash/8.html for
CRC-32
It seems that FNV hash or the modified version at http://
bretm.home.comcast.net/hash/6.html is much better for the
requirements. (This is what I use in my client too.)
.
On Aug 9, 2007, at 12:20 PM, Richard Jones wrote:
Multiple hash functions are required or you lose the benefit of
multiple
points per server in the first place, for the reasons brad and russ
mentioned.
I'm going to give crc32 a go (for lookups and initial hashing) and
see how the
distribution looks, it's probably cheaper, and makes sense as it is
more
widely available. There was no particular reason why I used md5
over any
other hash.
160 was chosen as the number of points per server because it showed
a decent
distribution.. it's "big enough". Once the hashing and collision
handling are
well defined, this could potentially be tuned per-install, and
still maintain
compatability between clients. However, i think we can agree on a sane
default with a bit more testing.
I recently spotted a consistent hashing implementation in a branch
of php/pecl
memcache cvs - http://pecl.php.net/package/memcache which iirc uses
crc32
instead of md5. Need to investigate this some more.
RJ
On Wednesday 08 August 2007 13:03:37 Alex Stapleton wrote:
Brad Fitzpatrick wrote:
-- which digest algorithm(s) for the points and/or array lookup?
There are a seemingly infinite array of hash functions out there
but we
already have code for CRC32 on a vast number of platforms, is
there any
particular reason – be it speed or quality – that we shouldn't
continue
to use that?
-- how many points are put on the continuum for each target?
+
-- what is the input to the digest algorithm for points 1-n?
e.g.:
"127.0.0.1:11211-1"
"127.0.0.1:11211-2"
"127.0.0.1:11211-3"
....
"127.0.0.1:11211-<n>"
It seems like running multiple hashes over the string seems like a
bit
of a waste of cycles. Modifying the hash value for each point
would be
much more efficient and simpler to implement. Something like point
value
= <hash value> + (<point number> * 2654435761)
As Steve says in his follow-up we also need to handle collisions
while
creating the continuum. Simply incrementing the point value by 1
until
we find an empty place is going to give us a rather biased
continuum. I
think that incrementing the point number 1 and recalculating the
point
value from that should give a better distribution while being fairly
easy to actually implement.
--
Richard Jones
Last.fm Ltd. | http://www.last.fm/
Office: +44 (0) 207 780 7080
