Historical Service Time Path Selector
Subsystems (2)
v4 cover Historical Service Time Path Selector
Hi,
This fourth version of HST applies the suggestion from Mikulas Patocka to do the ktime_get_ns inside the mpath map_bio instead of generic device-mapper code. This means that struct dm_mpath_io gained another 64bit field. For the request-based case, we continue to use the block layer start time information.
With this modification, I was able obtain similar performance on BIO to request-based multipath with HST on the benchmarks shared in v1.
v3: https://www.redhat.com/archives/dm-devel/2020-April/msg00308.html
v2: https://www.redhat.com/archives/dm-devel/2020-April/msg00270.html
v1: https://www.redhat.com/archives/dm-devel/2020-April/msg00176.html
Gabriel Krisman Bertazi (1):
md: mpath: Pass IO start time to path selector
Khazhismel Kumykov (1):
md: mpath: Add Historical Service Time Path Selector
drivers/md/Kconfig | 11 + drivers/md/Makefile | 1 + drivers/md/dm-historical-service-time.c | 561 ++++++++++++++++++++++++ drivers/md/dm-mpath.c | 12 +- drivers/md/dm-path-selector.h | 2 +- drivers/md/dm-queue-length.c | 2 +- drivers/md/dm-service-time.c | 2 +- 7 files changed, 585 insertions(+), 6 deletions(-) create mode 100644 drivers/md/dm-historical-service-time.c
Signature · 1 line
2.26.2
PATCH v4 1/2 md: mpath: Pass IO start time to path selector
HST is going to need this information to perform path prediction. For request-based mpath, we use the struct request io_start_time, while for bio based, use the DM layer start_time.
--- drivers/md/dm-mpath.c | 12 +++++++++--- drivers/md/dm-path-selector.h | 2 +- drivers/md/dm-queue-length.c | 2 +- drivers/md/dm-service-time.c | 2 +- 4 files changed, 12 insertions(+), 6 deletions(-)
drivers/md/dm-mpath.c +9 -3
@@ -105,6 +105,7 @@ struct multipath {struct dm_mpath_io {struct pgpath *pgpath;size_t nr_bytes; +u64 start_time_ns; };typedef int (*action_fn ) (struct pgpath *pgpath);
@@ -519,6 +520,7 @@ static int multipath_clone_and_map(struct dm_target *ti, struct request *rq, mpio->pgpath = pgpath; mpio->nr_bytes = nr_bytes; + mpio->start_time_ns = rq->io_start_time_ns; bdev = pgpath->path.dev->bdev; q =bdev_get_queue (bdev);
@@ -567,7 +569,8 @@ static void multipath_release_clone(struct request *clone,if (pgpath && pgpath->pg->ps.type->end_io) pgpath->pg->ps.type->end_io (&pgpath->pg->ps, &pgpath->path, - mpio->nr_bytes); + mpio->nr_bytes, + mpio->start_time_ns); }blk_put_request (clone);
@@ -629,6 +632,7 @@ static int __multipath_map_bio(struct multipath *m, struct bio *bio, } mpio->pgpath = pgpath; + mpio->start_time_ns =ktime_get_ns (); bio->bi_status =0 ;bio_set_dev (bio, pgpath->path.dev->bdev);
@@ -1620,7 +1624,8 @@ static int multipath_end_io(struct dm_target *ti, struct request *clone,struct path_selector *ps = &pgpath->pg->ps;if (ps->type->end_io) - ps->type->end_io (ps, &pgpath->path, mpio->nr_bytes); + ps->type->end_io (ps, &pgpath->path, mpio->nr_bytes, + mpio->start_time_ns); }return r;
@@ -1664,7 +1669,8 @@ static int multipath_end_io_bio(struct dm_target *ti, struct bio *clone,struct path_selector *ps = &pgpath->pg->ps;if (ps->type->end_io) - ps->type->end_io (ps, &pgpath->path, mpio->nr_bytes); + ps->type->end_io (ps, &pgpath->path, mpio->nr_bytes, + mpio->start_time_ns); }return r;
drivers/md/dm-path-selector.h +1 -1
@@ -74,7 +74,7 @@ struct path_selector_type {int (*start_io) (struct path_selector *ps,struct dm_path *path,size_t nr_bytes);int (*end_io) (struct path_selector *ps,struct dm_path *path, -size_t nr_bytes); +size_t nr_bytes,u64 start_time); };/* Register a path selector */
drivers/md/dm-queue-length.c +1 -1
@@ -227,7 +227,7 @@ static int ql_start_io(struct path_selector *ps, struct dm_path *path, }static int ql_end_io (struct path_selector *ps,struct dm_path *path, -size_t nr_bytes) +size_t nr_bytes,u64 start_time) {struct path_info *pi = path->pscontext;
drivers/md/dm-service-time.c +1 -1
@@ -309,7 +309,7 @@ static int st_start_io(struct path_selector *ps, struct dm_path *path, }static int st_end_io (struct path_selector *ps,struct dm_path *path, -size_t nr_bytes) +size_t nr_bytes,u64 start_time) {struct path_info *pi = path->pscontext;
Signature · 1 line
2.26.2
PATCH v4 2/2 md: mpath: Add Historical Service Time Path Selector
In reply to Gabriel Krisman BertaziFrom: Khazhismel Kumykov <[email protected]>
This new selector keeps an exponential moving average of the service time for each path (losely defined as delta between start_io and end_io), and uses this along with the number of inflight requests to estimate future service time for a path. Since we don't have a prober to account for temporally slow paths, re-try "slow" paths every once in a while (num_paths * historical_service_time). To account for fast paths transitioning to slow, if a path has not completed any request within (num_paths * historical_service_time), limit the number of outstanding requests. To account for low volume situations where number of inflights would be zero, the last finish time of each path is factored in.
--- drivers/md/Kconfig | 11 + drivers/md/Makefile | 1 + drivers/md/dm-historical-service-time.c | 561 ++++++++++++++++++++++++ 3 files changed, 573 insertions(+) create mode 100644 drivers/md/dm-historical-service-time.c
drivers/md/Kconfig +11 -0
@@ -452,6 +452,17 @@ config DM_MULTIPATH_ST If unsure, say N. +config DM_MULTIPATH_HST + tristate "I/O Path Selector based on historical service time" + depends on DM_MULTIPATH + help + This path selector is a dynamic load balancer which selects + the path expected to complete the incoming I/O in the shortest + time by comparing estimated service time (based on historical + service time). + + If unsure, say N. + config DM_DELAY tristate "I/O delaying target" depends on BLK_DEV_DM
drivers/md/Makefile +1 -0
@@ -55,6 +55,7 @@ obj-$(CONFIG_DM_FLAKEY) += dm-flakey.o obj-$(CONFIG_DM_MULTIPATH) += dm-multipath.o dm-round-robin.o obj-$(CONFIG_DM_MULTIPATH_QL) += dm-queue-length.o obj-$(CONFIG_DM_MULTIPATH_ST) += dm-service-time.o +obj-$(CONFIG_DM_MULTIPATH_HST) += dm-historical-service-time.o obj-$(CONFIG_DM_SWITCH) += dm-switch.o obj-$(CONFIG_DM_SNAPSHOT) += dm-snapshot.o obj-$(CONFIG_DM_PERSISTENT_DATA) += persistent-data/
drivers/md/dm-historical-service-time.c new file +561 -0
561 lines not on this page · raw message
Signature · 1 line
2.26.2
Quoted 8 lines · Gabriel Krisman Bertazi
Hi,
This fourth version of HST applies the suggestion from Mikulas Patocka to do the
ktime_get_nsinside the mpathmap_bioinstead of generic device-mapper code. This means that structdm_mpath_iogained another 64bit field. For the request-based case, we continue to use the block layer start time information.
Quoted 6 lines
With this modification, I was able obtain similar performance on BIO to request-based multipath with HST on the benchmarks shared in v1.
v3: https://www.redhat.com/archives/dm-devel/2020-April/msg00308.html
v2: https://www.redhat.com/archives/dm-devel/2020-April/msg00270.html
v1: https://www.redhat.com/archives/dm-devel/2020-April/msg00176.html
I already staged your v3 in linux-next. Please provide an incremental patch that layers on this git branch:
https://git.kernel.org/pub/scm/linux/kernel/git/device-mapper/linux-dm.git/log/?h=dm-5.8
I was hopeful for a flag to be set (e.g. in 'struct path_selector') to reflect whether the path selector expects highres start_time. Makes little sense to incur that extra cost of providing the time if the path selector doesn't even use it.
Alternatively, could split out the setting of the time needed by .end_io to a new path_selector_type method (e.g. .set_start_time). And then only use ktime_get_ns() for bio-based if .set_start_time is defined. Would get a little fiddly needing to make sure a stale start_time isn't used... also, makes more sense to conditionally call this .set_start_time just after .start_io is.
Mike
Quoted 28 lines · Mike Snitzer
Quoted 8 lines · Gabriel Krisman Bertazi
Hi,
This fourth version of HST applies the suggestion from Mikulas Patocka to do the
ktime_get_nsinside the mpathmap_bioinstead of generic device-mapper code. This means that structdm_mpath_iogained another 64bit field. For the request-based case, we continue to use the block layer start time information.Quoted 6 lines
With this modification, I was able obtain similar performance on BIO to request-based multipath with HST on the benchmarks shared in v1.
v3: https://www.redhat.com/archives/dm-devel/2020-April/msg00308.html
v2: https://www.redhat.com/archives/dm-devel/2020-April/msg00270.html
v1: https://www.redhat.com/archives/dm-devel/2020-April/msg00176.htmlI already staged your v3 in linux-next. Please provide an incremental patch that layers on this git branch:
https://git.kernel.org/pub/scm/linux/kernel/git/device-mapper/linux-dm.git/log/?h=dm-5.8
I was hopeful for a flag to be set (e.g. in 'struct
path_selector') to reflect whether the path selector expects highresstart_time. Makes little sense to incur that extra cost of providing the time if the path selector doesn't even use it.
Quoted 6 lines
Alternatively, could split out the setting of the time needed by .end_io to a new
path_selector_typemethod (e.g. .set_start_time). And then only usektime_get_ns()for bio-based if .set_start_time is defined. Would get a little fiddly needing to make sure a stalestart_timeisn't used... also, makes more sense to conditionally call this .set_start_time just after .start_io is.
Oh, my apologies, I hadn't noticed it was merged. I will make the time fetch conditional and submit a new patch based on that branch.
Thanks,
Signature · 1 line
Gabriel Krisman Bertazi
Quoted 37 lines · Gabriel Krisman Bertazi
Quoted 28 lines · Mike Snitzer
Quoted 8 lines · Gabriel Krisman Bertazi
Hi,
This fourth version of HST applies the suggestion from Mikulas Patocka to do the
ktime_get_nsinside the mpathmap_bioinstead of generic device-mapper code. This means that structdm_mpath_iogained another 64bit field. For the request-based case, we continue to use the block layer start time information.Quoted 6 lines
With this modification, I was able obtain similar performance on BIO to request-based multipath with HST on the benchmarks shared in v1.
v3: https://www.redhat.com/archives/dm-devel/2020-April/msg00308.html
v2: https://www.redhat.com/archives/dm-devel/2020-April/msg00270.html
v1: https://www.redhat.com/archives/dm-devel/2020-April/msg00176.htmlI already staged your v3 in linux-next. Please provide an incremental patch that layers on this git branch:
https://git.kernel.org/pub/scm/linux/kernel/git/device-mapper/linux-dm.git/log/?h=dm-5.8
I was hopeful for a flag to be set (e.g. in 'struct
path_selector') to reflect whether the path selector expects highresstart_time. Makes little sense to incur that extra cost of providing the time if the path selector doesn't even use it.Quoted 6 lines
Alternatively, could split out the setting of the time needed by .end_io to a new
path_selector_typemethod (e.g. .set_start_time). And then only usektime_get_ns()for bio-based if .set_start_time is defined. Would get a little fiddly needing to make sure a stalestart_timeisn't used... also, makes more sense to conditionally call this .set_start_time just after .start_io is.
Quoted 2 lines
Oh, my apologies, I hadn't noticed it was merged. I will make the time fetch conditional and submit a new patch based on that branch.
I don't want to waste your time so please don't run with that idea just yet.
There is a possibility we really _do_ need higher resolution time.
I'm about to have a concall to discuss some disk IO stat issues with DM disk stats vs NVMe disk stats (provided by block core).
I'll let you know the outcome and we can discuss further.
Thanks,
Mike
Quoted 43 lines · Mike Snitzer
Quoted 37 lines · Gabriel Krisman Bertazi
Quoted 28 lines · Mike Snitzer
Quoted 8 lines · Gabriel Krisman Bertazi
Hi,
This fourth version of HST applies the suggestion from Mikulas Patocka to do the
ktime_get_nsinside the mpathmap_bioinstead of generic device-mapper code. This means that structdm_mpath_iogained another 64bit field. For the request-based case, we continue to use the block layer start time information.Quoted 6 lines
With this modification, I was able obtain similar performance on BIO to request-based multipath with HST on the benchmarks shared in v1.
v3: https://www.redhat.com/archives/dm-devel/2020-April/msg00308.html
v2: https://www.redhat.com/archives/dm-devel/2020-April/msg00270.html
v1: https://www.redhat.com/archives/dm-devel/2020-April/msg00176.htmlI already staged your v3 in linux-next. Please provide an incremental patch that layers on this git branch:
https://git.kernel.org/pub/scm/linux/kernel/git/device-mapper/linux-dm.git/log/?h=dm-5.8
I was hopeful for a flag to be set (e.g. in 'struct
path_selector') to reflect whether the path selector expects highresstart_time. Makes little sense to incur that extra cost of providing the time if the path selector doesn't even use it.Quoted 6 lines
Alternatively, could split out the setting of the time needed by .end_io to a new
path_selector_typemethod (e.g. .set_start_time). And then only usektime_get_ns()for bio-based if .set_start_time is defined. Would get a little fiddly needing to make sure a stalestart_timeisn't used... also, makes more sense to conditionally call this .set_start_time just after .start_io is.Quoted 2 lines
Oh, my apologies, I hadn't noticed it was merged. I will make the time fetch conditional and submit a new patch based on that branch.
Quoted 8 lines
I don't want to waste your time so please don't run with that idea just yet.
There is a possibility we really _do_ need higher resolution time.
I'm about to have a concall to discuss some disk IO stat issues with DM disk stats vs NVMe disk stats (provided by block core).
I'll let you know the outcome and we can discuss further.
OK, that concall's issue had nothing to do with needing higher resolution time (was about IOPs realized with requested-based vs bio-based).
Reality is, DM won't need anything higher resolution than jiffies until block core's interfaces require something other than jiffies (e.g. generic_end_io_acct).
So feel free to proceed with the conditional time fetch solution you were going to run with (prior to my previous mail asking you to hold off).
Sorry for the noise. Thanks,
Mike
Quoted 8 lines · Mike Snitzer
OK, that concall's issue had nothing to do with needing higher resolution time (was about IOPs realized with requested-based vs bio-based).
Reality is, DM won't need anything higher resolution than jiffies until block core's interfaces require something other than jiffies (e.g.
generic_end_io_acct).
Quoted 6 lines
So feel free to proceed with the conditional time fetch solution you were going to run with (prior to my previous mail asking you to hold off).
Sorry for the noise. Thanks,
Mike
No problem, thanks for the information. I get started on it.
Signature · 1 line
Gabriel Krisman Bertazi
Quoted 5 lines · Gabriel Krisman Bertazi
This fourth version of HST applies the suggestion from Mikulas Patocka to do the
ktime_get_nsinside the mpathmap_bioinstead of generic device-mapper code. This means that structdm_mpath_iogained another 64bit field. For the request-based case, we continue to use the block layer start time information.
You should add some info to the multipath.conf.5 man page ( https://git.opensvc.com/gitweb.cgi?p=multipath-tools/.git;a=blob;f=multipath/multipath.conf.5;h=05a5e8ffeb110d969f3b2381eb3b88d7f28380f6;hb=HEAD#l189 ), or none one is going to use it.
Thanks.
Quoted 8 lines · Xose Vazquez Perez
Quoted 5 lines · Gabriel Krisman Bertazi
This fourth version of HST applies the suggestion from Mikulas Patocka to do the
ktime_get_nsinside the mpathmap_bioinstead of generic device-mapper code. This means that structdm_mpath_iogained another 64bit field. For the request-based case, we continue to use the block layer start time information.
Quoted 4 lines
You should add some info to the multipath.conf.5 man page (
https://git.opensvc.com/gitweb.cgi?p=multipath-tools/.git;a=blob;f=multipath/multipath.conf.5;h=05a5e8ffeb110d969f3b2381eb3b88d7f28380f6;hb=HEAD#l189
),
or none one is going to use it.
Sure, will do.
Signature · 1 line
Gabriel Krisman Bertazi