Better server selection client code?

Andrew Harbick aharbick at
Fri Oct 20 14:00:14 UTC 2006

>> Agreed.  But I don't think it has to be that fancy.  I just position the
>> servers around the unit circle at even intervals.
> But when I add a new server, I dont want to move all the servers to
> maintain the intervals same. That is same as doing a modulo function.
> (to elaborate: The first server moves 1/n, second moves 2/n...and so
> on to make space for the new server )
> So to have a practical midway, I pick the biggest arc. or a random one
> if they are all the same - resulting in a non-uniform distribution of
> load

Ah...  I think I get it.  You're saying that the new server is position 
at the mid-point of the longest arc.  The result would be that only 
total_keys * (1/arclength * 2) keys would move.

Interesting.  However this the keys aren't evenly distributed when you 
add a new server.  Go from one server to two and you have servers at 0.0 
and 0.5.  Then go from 2 to three and you have servers at 0.0, 0.5, and 
either 0.25 or 0.75.  Right?

>> So assuming your keys
>> hash with an even distribution around the unit circle, traffic to your
>> servers is going to be even.  This way of positioning the servers only
>> ends up moving 1/totalServer keys on the addition of a new server which

This was actually an error it should be total_keys/total_servers.  I 
meant to say "1/totalServer *percent*".  Even still, that's not entirely 
right either.

Here's a picture of my method:

Where the blue pie pieces are keys that will end up on a new server and 
represents 35% of the keys.  I haven't worked out the math to figure out 
what percentage of the keys move for an arbitrary bump from N-servers to 
M-servers.  Either way, it is less than all of them.


More information about the memcached mailing list