Better server selection client code?
aharbick at aharbick.com
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
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
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