[chord] Spreading the Load using Consistent Hashing

[Garret Swart]

Greetings:

I presented a conference paper last week that contains a partial analysis of
the overload characteristics of Chord and proposes a couple of tweaks to the
Chord object placement algorithm to improve those characteristics.  I would
be interested in discussing this work with anyone on the Chord project to
see if it has any applicability to work you are doing.

One of the results of the analysis is a closed form for the standard
deviation of the number of objects assigned to a node in terms of the number
of nodes, the number of objects, the number of virtual nodes per node, and
the level of replication of each object.

The conclusion is that virtual nodes, while a good way of handling
heterogeneous nodes, are an expensive way of smoothing the load between
similar nodes.  A better approach is to use fewer virtual nodes per node but
place the object on the node offset by a secondary hash function from the
node given by the primary hash.

Furthermore, if you can stomach a small constant factor increase in the cost
of an object look up, the load can be spread even more evenly using a
dynamic load balancing technique with minimal overhead.  Interestingly this
technique works most efficaciously with two virtual nodes per real node.

The paper is available as
http://www.cs.ucc.ie/~gs1/SpreadLoad/SpreadLoadIEEE.pdf and was presented as
part of a small conference: the 3rd International Symposium on Parallel and
Distributed Computing (ISPDC 2004) held in Cork last week.

I would like to turn this into a journal article and I am interested in
feedback, discussion, or collaboration.

Garret Swart
University College Cork
Cork, Ireland

P. S. Rob, we met an eon or two ago at DEC SRC when you were an intern and I
was working on Taos.

P. P. S. I'm also working on automatic configuration of computing systems
that meet a variety of QoS requirements (security, network bandwidth,
processing throughput, availability) using constraint satisfaction
techniques and on web architectures for collaboration and undo using long
running transactions.  See http://www.cs.ucc.ie/~gs1 for more information.