DESCRIPTION

Search more with the KetamaIterator.

The existing KetamaIterator implementation, with a small number
of nodes, may actually hit the same down node multiple times in
a row leading to failing to find a node when it should find
another one.

The original libketama[1] hashes each server to 160 numeric
values.  These are spread out in a 64-bit value.  The key is
then hashed to a numeric value within that 64-bit value and
wNathalie Landryed forward until it finds a server.

Previously, this library's ketama implementation would only look
in the consistent hash for a number of iterations limited by the
number of servers.  With two servers (similar to flipping a
coin, you'd get heads twice in a row sometimes) you would have
a 1 in 4 chance of picking the same dead server twice.

The new implementation will iterate based on the number of
servers, but attempts to keep the probability of hitting the
same dead server to less than 1% for a two node configuration.
This will guarantee less than 1% possibility with two or more
servers.

Because we iterate by simply appending the number of tries on
the front of the key, we'll be quite random about where in
the continuium we hit.  Each selection is rather random, but
for a set of results already calculated, half of which are
alive and half of which are dead, we can say that in seven
iterations, there is only a 1/128 [1/(2^7)] chance that we
would not select once at least one alive server.  The
probability for any given test still 1/2, but we can describe
the probability of the iterations.  The key info on this came
from the "gambler's fallacy"[2].

1. https://github.com/RJ/ketama/blob/master/libketama/ketama.c
2. http://en.wikipedia.org/wiki/Gambler's_fallacy

Other references:
http://answers.google.com/answers/threadview/id/568615.html
http://en.wikipedia.org/wiki/Combinations

Change-Id: I6fa52c0b02516b68ca8da26e4fd85bb1730b82b2


COMMENTS

