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

[Alex Rousskov]

On 04/17/2017 10:53 AM, Loic Dachary wrote:
> On 04/17/2017 06:28 PM, Alex Rousskov wrote:
>> On 04/17/2017 09:08 AM, Loic Dachary wrote:
>>
>>>   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)
>>
>> How would the last three lines look for CARP and sourcehash?


> I'm not sure :-) But I could write a simulation to figure it out.
> Unless I missed a part of src/carp.cc that mitigates the problem, the
> situation should not be very different from what is described at
> https://docs.openstack.org/developer/swift/ring_background.html#part-2

It is totally up to you whether to do anything else. FWIW, AFAICT:

* only math (not simulation) is needed to show that any "peer =
request_hash % n" mapping algorithm (where "n" is the number of peers)
may result in a lot of "moved" request:peer assignments;

* many folks do not know whether CRUSH, CARP and sourcehash use a "peer
= request_hash % n" mapping algorithm (you should say that explicitly);

* it would be both interesting and useful to know how the amount of
"movement" changes with "n" in all compared algorithms (e.g., should I
bother with CRUSH if I have 10 peers?);

* do not assume that we know that a 1/3 movement shown by CRUSH (for
n=2) is a lot less than some X shown by CARP (for the same "n");

* disclose the price of the reduction of movement (e.g., "a few RAM
bytes per peer to store the more complex mapping and a few CPU cycles to
find the right peer for each request").

Perhaps your article already addresses all these concerns, but if you
want others to be enthusiastic about CRUSH, it may help to distill its
advantages and costs to something one can grasp by reading a
two-paragraph email with an easy-to-grok table.


HTH,

Alex.