What is a good function to map an id to memcache in a pool of servers?

Question

Something like:

host = getHost(id)
>>> 172.16.25.52

Ideally, the algorithm should minimize the number of cache misses when the pool of servers is expanded / contracted.

Are there any known algorithms out there that do this? Or libraries, potentially (I'm using Python).

Thank you.

Answer 1

The memcached library does this by default. So you can just read the code from the repository: http://bazaar.launchpad.net/~python-memcached-team/python-memcached/trunk/annotate/head%3A/memcache.py#L274

As for minimizing the cache misses with an expanding/contracting pool... a difficult thing to do. Either you're not dividing the servers correctly at first or it will be less optimal when expanding/contracting. If you would have a maximum of N servers than it might be easier though, since you can make a couple of assumptions.