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

[Loic Dachary]

On 04/17/2017 08:34 PM, Alex Rousskov wrote:
> 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.

That's what I should have done to begin with. Explaining with maths would be complicated, I'll write some code and run a simulation, it will be easier to understand.

Cheers

-- 
Loïc Dachary, Artisan Logiciel Libre