[squid-dev] [RFC] CRUSH peer selection method

[Loic Dachary]

Hi,

Adding CRUSH[1] as an alternative peer selection method[2] would reduce the cache miss when a new peer is added. With the current hashing methods (carp, userhash or sourcehash) a large number of requests targeting a given peer before the addition will target another peer after the addition. And something similar happens when a peer is removed. The interesting property of CRUSH is that it tries hard to minimize that undesirable side effect. In other words, if we have:

  peer 1 targeted by a set of requests (X1)
  peer 2 targeted by a set of requests (X2)

and we add a new peer, CRUSH makes it so 1/3 of the requests from peer 1 and 2 move to peer 3

  peer 1 targeted by a set of requests (2/3 of X1)
  peer 2 targeted by a set of requests (2/3 of X2)
  peer 3 targeted by a set of requests (1/3 of X1 + 1/3 of X2)

A implementation[3] depending on libcrush[4] (it does not compile even, just a rough draft) was written to verify there is no obvious blocker.

What do you think ?

[1] CRUSH http://www.crss.ucsc.edu/media/papers/weil-sc06.pdf
[2] http://www.squid-cache.org/Versions/v4/cfgman/cache_peer.html
[3] draft implementation http://bugs.squid-cache.org/attachment.cgi?id=3541
[4] libcrush http://libcrush.org/main/libcrush
-- 
Loïc Dachary, Artisan Logiciel Libre