Skip to contentSkip to conversation

Historical Service Time Path Selector

PATCH In review Gabriel Krisman Bertazi 3 participants 10 messages May 11, 2020 – May 21, 2020

Subsystems (2)
lore
Share & tools
lore
#0 lore raw

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
#1 lore raw

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
index f5e7f8e88767..deb6ae5ad35b 100644
@@ -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
index b6eb5365b1a4..c47bc0e20275 100644
@@ -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
index 969c4f1a3633..5fd018d18418 100644
@@ -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
index f006a9005593..9cfda665e9eb 100644
@@ -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
#2 lore raw

PATCH v4 2/2 md: mpath: Add Historical Service Time Path Selector

In reply to Gabriel Krisman Bertazi

From: 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
index 37f05707c59d..5669eeb5cf6f 100644
@@ -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
index 9a2d673f94bc..31840f95cd40 100644
@@ -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
#3 lore raw
In reply to Gabriel Krisman Bertazi
Quoted 8 lines · Gabriel Krisman Bertazi

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.

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

#4 lore raw
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_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.

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.

Quoted 6 lines

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.

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
#5 lore raw
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_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.

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.

Quoted 6 lines

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.

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

#6 lore raw
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_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.

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.

Quoted 6 lines

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.

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

#7 lore raw
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
#8 lore raw
In reply to 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_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.

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.

#9 lore raw
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_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.

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