[dm-devel] [PATCH] dm mpath selector: more evenly distribute ties

[Khazhismel Kumykov]

On Wed, Jan 24, 2018 at 2:57 AM, Martin Wilck <mwilck at suse.com> wrote:
> On Fri, 2018-01-19 at 15:07 -0800, Khazhismel Kumykov wrote:
>> Move the last used path to the end of the list (least preferred) so
>> that
>> ties are more evenly distributed.
>>
>> For example, in case with three paths with one that is slower than
>> others, the remaining two would be unevenly used if they tie. This is
>> due to the rotation not being a truely fair distribution.
>>
>> Illustrated: paths a, b, c, 'c' has 1 outstanding IO, a and b are
>> 'tied'
>> Three possible rotations:
>> (a, b, c) -> best path 'a'
>> (b, c, a) -> best path 'b'
>> (c, a, b) -> best path 'a'
>> (a, b, c) -> best path 'a'
>> (b, c, a) -> best path 'b'
>> (c, a, b) -> best path 'a'
>> ...
>
>
> This happens only if a and b actually have the same weight (e.g. queue
> length for the queue-length selector). If 'a' really receives more IO,
> its queue grows, and the selector will start preferring 'b', so the
> effect should level out automatically with the current code as soon as
> you have real IO going on. But maybe I haven't grasped what you're
> referring to as "tied".
Yes, for "tied" I'm referring to paths with the same weight. As queue
length grows it does tend to level out, but in the case where queue
length doesn't grow (in this example I'm imagining 2 concurrent
requests to the device) the bias does show and the selectors really do
send 'a' 2x more requests than 'b' (when 'c' is much slower and 'a'
and 'b' are ~same speed).

>
> OTOH, if the "best" path has much lower queue length than the other
> paths for whatever reason, your pushing it to the tail will require a
> full list walk with every new call of the selector. I see tjat as a
> small disadvantage of your approach.
I see, with best at the tail, we would not see as much benefit from
the check if a path has no IOs on it in queue-length. In service-time
no such short circuit exists, so I don't believe anything changes
there. Am I understanding this correctly?

>
> Regards
> Martin
>

Thanks for your comments,
Khazhy

>>
>> So 'a' is used 2x more than 'b', although they should be used evenly.
>>
>> With this change, the most recently used path is always the least
>> preferred, removing this bias resulting in even distribution.
>> (a, b, c) -> best path 'a'
>> (b, c, a) -> best path 'b'
>> (c, a, b) -> best path 'a'
>> (c, b, a) -> best path 'b'
>> ...
>>
>> Signed-off-by: Khazhismel Kumykov <khazhy at google.com>
>> ---
>>  drivers/md/dm-queue-length.c | 6 +++---
>>  drivers/md/dm-service-time.c | 6 +++---
>>  2 files changed, 6 insertions(+), 6 deletions(-)
>>
>> diff --git a/drivers/md/dm-queue-length.c b/drivers/md/dm-queue-
>> length.c
>> index 23f178641794..969c4f1a3633 100644
>> --- a/drivers/md/dm-queue-length.c
>> +++ b/drivers/md/dm-queue-length.c
>> @@ -195,9 +195,6 @@ static struct dm_path *ql_select_path(struct
>> path_selector *ps, size_t nr_bytes)
>>       if (list_empty(&s->valid_paths))
>>               goto out;
>>
>> -     /* Change preferred (first in list) path to evenly balance.
>> */
>> -     list_move_tail(s->valid_paths.next, &s->valid_paths);
>> -
>>       list_for_each_entry(pi, &s->valid_paths, list) {
>>               if (!best ||
>>                   (atomic_read(&pi->qlen) < atomic_read(&best-
>> >qlen)))
>> @@ -210,6 +207,9 @@ static struct dm_path *ql_select_path(struct
>> path_selector *ps, size_t nr_bytes)
>>       if (!best)
>>               goto out;
>>
>> +     /* Move most recently used to least preferred to evenly
>> balance. */
>> +     list_move_tail(&best->list, &s->valid_paths);
>> +
>>       ret = best->path;
>>  out:
>>       spin_unlock_irqrestore(&s->lock, flags);
>> diff --git a/drivers/md/dm-service-time.c b/drivers/md/dm-service-
>> time.c
>> index 7b8642045c55..f006a9005593 100644
>> --- a/drivers/md/dm-service-time.c
>> +++ b/drivers/md/dm-service-time.c
>> @@ -282,9 +282,6 @@ static struct dm_path *st_select_path(struct
>> path_selector *ps, size_t nr_bytes)
>>       if (list_empty(&s->valid_paths))
>>               goto out;
>>
>> -     /* Change preferred (first in list) path to evenly balance.
>> */
>> -     list_move_tail(s->valid_paths.next, &s->valid_paths);
>> -
>>       list_for_each_entry(pi, &s->valid_paths, list)
>>               if (!best || (st_compare_load(pi, best, nr_bytes) <
>> 0))
>>                       best = pi;
>> @@ -292,6 +289,9 @@ static struct dm_path *st_select_path(struct
>> path_selector *ps, size_t nr_bytes)
>>       if (!best)
>>               goto out;
>>
>> +     /* Move most recently used to least preferred to evenly
>> balance. */
>> +     list_move_tail(&best->list, &s->valid_paths);
>> +
>>       ret = best->path;
>>  out:
>>       spin_unlock_irqrestore(&s->lock, flags);
>> --
>> dm-devel mailing list
>> dm-devel at redhat.com
>> https://www.redhat.com/mailman/listinfo/dm-devel
>
> --
> Dr. Martin Wilck <mwilck at suse.com>, Tel. +49 (0)911 74053 2107
> SUSE Linux GmbH, GF: Felix Imendörffer, Jane Smithard, Graham Norton
> HRB 21284 (AG Nürnberg)
>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 4843 bytes
Desc: S/MIME Cryptographic Signature
URL: <http://listman.redhat.com/archives/dm-devel/attachments/20180124/cc58e8e1/attachment.p7s>