dm mpath selector: more evenly distribute ties
PATCH 1/1 dm mpath selector: more evenly distribute ties
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'
...
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'
...
--- drivers/md/dm-queue-length.c | 6 +++--- drivers/md/dm-service-time.c | 6 +++--- 2 files changed, 6 insertions(+), 6 deletions(-)
drivers/md/dm-queue-length.c +3 -3
@@ -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);
drivers/md/dm-service-time.c +3 -3
@@ -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);
Signature · 1 line
2.16.0.rc1.238.g530d649a79-goog
Quoted 8 lines · Khazhismel Kumykov
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.
Quoted 10 lines
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".
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.
Regards
Martin
Quoted 81 lines
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 <[email protected]>--- drivers/md/dm-queue-length.c | 6 +++--- drivers/md/dm-service-time.c | 6 +++--- 2 files changed, 6 insertions(+), 6 deletions(-)drivers/md/dm-queue- renamed from drivers/md/dm-queue-length.c +0
-0
length.c
index23f178641794..969c4f1a3633100644drivers/md/dm-queue-length.c +0
-3@@ -195,9 +195,6 @@ static struct dm_path *ql_select_path(structpath_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) {drivers/md/dm-queue-length.c +0
-0if (!best || (atomic_read(&pi->qlen) < atomic_read(&best-Quoted 1 line
qlen)))
drivers/md/dm-queue-length.c +1
-0@@ -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. */
drivers/md/dm-queue-length.c +2
-0+list_move_tail (&best->list, &s->valid_paths); + ret = best->path; out:spin_unlock_irqrestore (&s->lock, flags);drivers/md/dm-service- renamed from drivers/md/dm-service-time.c +0
-0
time.c
index7b8642045c55..f006a9005593100644drivers/md/dm-service-time.c +0
-3@@ -282,9 +282,6 @@ static struct dm_path *st_select_path(structpath_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))drivers/md/dm-service-time.c +1
-0best = 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. */
drivers/md/dm-service-time.c +2
-1+list_move_tail (&best->list, &s->valid_paths); + ret = best->path; out:spin_unlock_irqrestore (&s->lock, flags); --dm-devel mailing list
[email protected]
https://www.redhat.com/mailman/listinfo/dm-devel
Signature · 3 lines
Dr. Martin Wilck <[email protected]>, Tel. +49 (0)911 74053 2107 SUSE Linux GmbH, GF: Felix Imendörffer, Jane Smithard, Graham Norton HRB 21284 (AG Nürnberg)
Quoted 21 lines · Martin Wilck
Quoted 8 lines · Khazhismel Kumykov
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.
Quoted 10 lines
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'
...
Quoted 6 lines
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).
Quoted 5 lines
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?
Quoted 4 lines
Regards
Martin
Thanks for your comments,
Khazhy
Quoted 87 lines
Quoted 78 lines
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 <[email protected]>--- drivers/md/dm-queue-length.c | 6 +++--- drivers/md/dm-service-time.c | 6 +++--- 2 files changed, 6 insertions(+), 6 deletions(-)drivers/md/dm-queue- renamed from drivers/md/dm-queue-length.c +0
-0
length.c
index23f178641794..969c4f1a3633100644drivers/md/dm-queue-length.c +0
-3@@ -195,9 +195,6 @@ static struct dm_path *ql_select_path(structpath_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-Quoted 1 line
qlen)))
drivers/md/dm-queue-length.c +1
-0@@ -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. */
drivers/md/dm-queue-length.c +2
-0+list_move_tail (&best->list, &s->valid_paths); + ret = best->path; out:spin_unlock_irqrestore (&s->lock, flags);drivers/md/dm-service- renamed from drivers/md/dm-service-time.c +0
-0
time.c
index7b8642045c55..f006a9005593100644drivers/md/dm-service-time.c +0
-3@@ -282,9 +282,6 @@ static struct dm_path *st_select_path(structpath_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;drivers/md/dm-service-time.c +1
-0@@ -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. */
drivers/md/dm-service-time.c +2
-1+list_move_tail (&best->list, &s->valid_paths); + ret = best->path; out:spin_unlock_irqrestore (&s->lock, flags); --Quoted 3 lines
dm-devel mailing list
[email protected]
https://www.redhat.com/mailman/listinfo/dm-devel--
Dr. Martin Wilck <[email protected]>, Tel. +49 (0)911 74053 2107 SUSE Linux GmbH, GF: Felix Imendörffer, Jane Smithard, Graham Norton HRB 21284 (AG Nürnberg)
Quoted 36 lines · Khazhismel Kumykov
Quoted 24 lines · Martin Wilck
Quoted 11 lines · Khazhismel Kumykov
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.Quoted 10 lines
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'
...Quoted 9 lines
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".
Quoted 7 lines
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).
Have you actually observed this? I find the idea pretty academical that two paths would be walking "tied" this way. In practice, under IO load, I'd expect queue lengths (and service-times, for that matter) to fluctuate enough to prevent this effect to be measurable. But of course, I may be wrong. If you really did observe this, the next question would be: does hurt performance to an extent that can be noticed/measured? I reckon that if 'a' got saturated under the load, hurting performance, its queue length would grow quickly and 'b' would automatically get preferred.
Quoted 10 lines
Quoted 5 lines
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?
Forget that. I was confused. We're walking the entire list every time anyway, except for the . I find it strange to put the best candidate to the tail every time, but I can't prove that it really hurts.
Martin
Signature · 3 lines
Dr. Martin Wilck <[email protected]>, Tel. +49 (0)911 74053 2107 SUSE Linux GmbH, GF: Felix Imendörffer, Jane Smithard, Graham Norton HRB 21284 (AG Nürnberg)
Quoted 45 lines · Martin Wilck
Quoted 36 lines · Khazhismel Kumykov
Quoted 24 lines · Martin Wilck
Quoted 11 lines · Khazhismel Kumykov
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.Quoted 10 lines
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'
...Quoted 9 lines
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".Quoted 7 lines
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).
Quoted 9 lines
Have you actually observed this? I find the idea pretty academical that two paths would be walking "tied" this way. In practice, under IO load, I'd expect queue lengths (and service-times, for that matter) to fluctuate enough to prevent this effect to be measurable. But of course, I may be wrong. If you really did observe this, the next question would be: does hurt performance to an extent that can be noticed/measured? I reckon that if 'a' got saturated under the load, hurting performance, its queue length would grow quickly and 'b' would automatically get preferred.
This is fairly simple to observe - start two sync reader threads against a device with 3 backing paths, with one path taking longer on average to complete requests than the other two. One of the 'faster' paths will be used ~2x more than the other. Perhaps not that common a situation, but is a real one. The bias seemed simple to remove, so that the two (or N) paths would be used equally.
I don't see a downside to more evenly distributing in this case, although I can't say I've directly observed performance downsides for a biased distribution (aside from the distribution being biased itself being a downside).
The bias of note is inherent to the order paths are added to the selector (and which path is 'always bad'), so if 'a' is saturated due to this, then slows, once it recovers it will continue to be preferred, versus in an even distribution.
Khazhy
Martin Wilck
Reviewed-byQuoted 79 lines · Khazhismel Kumykov
Quoted 56 lines · Martin Wilck
Quoted 43 lines · Khazhismel Kumykov
Quoted 26 lines · Martin Wilck
Quoted 12 lines · Khazhismel Kumykov
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.Quoted 11 lines
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'
...Quoted 14 lines
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".Quoted 11 lines
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).Quoted 13 lines
Have you actually observed this? I find the idea pretty academical that
two paths would be walking "tied" this way. In practice, under IO load,
I'd expect queue lengths (and service-times, for that matter) to fluctuate enough to prevent this effect to be measurable. But of course, I may be wrong. If you really did observe this, the next question would be: does hurt performance to an extent that can be noticed/measured? I reckon that if 'a' got saturated under the load,
hurting performance, its queue length would grow quickly and 'b' would
automatically get preferred.This is fairly simple to observe - start two sync reader threads against a device with 3 backing paths, with one path taking longer on average to complete requests than the other two. One of the 'faster' paths will be used ~2x more than the other. Perhaps not that common a situation, but is a real one. The bias seemed simple to remove, so that the two (or N) paths would be used equally.
Quoted 9 lines
I don't see a downside to more evenly distributing in this case, although I can't say I've directly observed performance downsides for a biased distribution (aside from the distribution being biased itself
being a downside).
The bias of note is inherent to the order paths are added to the selector (and which path is 'always bad'), so if 'a' is saturated due to this, then slows, once it recovers it will continue to be preferred, versus in an even distribution.
Well, the expectation is indeed that load is spread equally, and I can also see no downside. So:
Signature · 3 lines
Dr. Martin Wilck <[email protected]>, Tel. +49 (0)911 74053 2107 SUSE Linux GmbH, GF: Felix Imendörffer, Jane Smithard, Graham Norton HRB 21284 (AG Nürnberg)