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

[Loic Dachary]

On 04/19/2017 04:31 PM, Alex Rousskov wrote:
> On 04/19/2017 08:06 AM, Loic Dachary wrote:
>> On 04/19/2017 03:53 PM, Alex Rousskov wrote:
> 
>>> On 04/18/2017 01:00 AM, Loic Dachary wrote:
>>>
>>>> It turns out [CARP] performs as well as CRUSH
> 
> 
>>> On 04/19/2017 06:51 AM, Loic Dachary wrote:
>>>
>>>> I found one use case where CRUSH behaves significantly better than CARP.
> 
> 
>>> FYI, here is how the above statements can be interpreted: "It is all a
>>> mystery to us. Sometimes CRUSH and CARP are about the same, sometimes
>>> one of the algorithms wins, but we cannot tell you when to use CARP or
>>> CRUSH because we cannot generalize their differences. Our experimental
>>> data does not suggest any clear trends."
>>>
>>> That unpredictability may be the nature of the beast, of course, but I
>>> currently see no reasoning or experimental data to confirm or deny that
>>> sad hypothesis.
> 
>> CRUSH is no mystery [...] CARP is somewhat mysterious
> 
> You may know exactly how each algorithm works, but that does not really
> matter in this context. What matters here is the _relative_ strengths
> and weaknesses of an algorithm. That part is still a mystery (to me).
> When is CRUSH better than CARP? When is CARP better than CRUSH?
> 
> 
>> Please let me know if that is of interest to Squid
> 
> As of 04/18/2017, my personal answer to that question is "why bother?".
> 
> As of 04/19/2017, my personal answer to that question is "maybe": One
> out of 2+ random(?) tests shows about the same CARP and CRUSH  results.

The first test was to demonstrate excessive data movement when peers are added / removed. I did this because I (incorrectly) read CARP to be the equivalent of hash(request) % count(peers). The test proved me wrong and I went back to study CARP more thoroughly.

> Another test shows better CRUSH performance. It is not clear to me
> whether some other tests will show better CARP performance.

The test program I wrote[1] displays the properties of CARP that help comparing it with CRUSH, that is:

- requests are evenly distributed among peers, in accordance to the weights
- when a peer is added or removed, the amount of requests moving to or from the new or old peer is in proportion of its weight
- when the weight of a peer is changed, the amount of requests moving to or from the changed peer is in proportion of the weight change

I wrote this test program in C++ with a copy/paste of the code from carp.cc instead of python based approximation to avoid errors due to a misunderstanding on my part.

While conducting these tests I discovered that CARP does not perform as well as CRUSH when changing weights. If there are other tests that you think relevant to compare the two algorithms, I'd be happy to work on that.

I hope this shows you the work done is better than a random exploration of meaningless tests.

> I hope the above clarifies my position. Others may have a completely
> different opinion, of course, and my current position does not block
> CRUSH acceptance.

Your feedback is much appreciated and helpful.

Cheers

[1] CARP test http://libcrush.org/dachary/python-crush/blob/e7579b28f4288525750e94fe9bdc4bf985cb5d1f/carp.cc

-- 
Loïc Dachary, Artisan Logiciel Libre