Better server selection client code?

Jeetendra Mirchandani jeetum at
Fri Oct 20 07:57:08 UTC 2006

On 10/19/06, Andrew Harbick <aharbick at> wrote:
> > But here you can have a problem of load distribution. According to the
> > algorithm, if 2 servers map to points very close on the unit circle, the
> > load distribution will be screwed badly.
> >
> > possible solution - dont use hashing for mapping servers to the unit
> > circle, instead maintain a map, and pick the longest arc to place the
> > new server.
> 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

> 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
> is perfect since you just added a new machine which you want to have
> that many keys anyhow.  Unless I'm missing something, I don't see what
> you need something more complex.
> >
> > The paper also mentions in section 2.2:
> > <snip>
> > For technical reasons detailed in [6], it is quite important to make a
> > small number of copies of each cache point--that is, to map several
> > copies of each cache to different ``random'' points on the unit circle.
> > This produces a more uniform distribution of URLs to caches.
> > </snip>
> >
> > This will also provide a good failover, as discussed here:
> >
> Andy


"Reality is merely an illusion, albeit a very persistent one."

More information about the memcached mailing list