Skip to contentSkip to conversation

Historical Service Time Path Selector

PATCH Superseded Gabriel Krisman Bertazi 2 participants 5 messages Apr 16, 2020 – Apr 26, 2020

Subsystems (2)

v1 of 4 Superseded Latest is v4 →

lore
Share & tools
lore
#0 lore raw

cover Historical Service Time Path Selector

Hello,

This small series implements a new path selector that leverages historical path IO time in order to estimate future path performance. Implementation details can be found on Patch 2.

This selector yields better path distribution, considering the mean deviation from the calculated optimal utilization, for small IO depths when compared to the Service Time selector with fio benchmarks. For instance, on a multipath setup with 4 paths, where one path is 4 times slower than the rest, issuing 500MB of randwrites, we have the following path utilization rates:

      |    depth=1    |    depth=64   |       |
      |   ST  |   HST |   ST  |   HST |  Best |
|-----+-------+-------+-------+-------+-------|
| sda | 0.250 | 0.294 | 0.297 | 0.294 | 0.307 |
| sdb | 0.250 | 0.297 | 0.296 | 0.297 | 0.307 |
| sdc | 0.250 | 0.296 | 0.298 | 0.296 | 0.307 |
| sdd | 0.250 | 0.112 | 0.106 | 0.112 | 0.076 |

For small depths, HST is much quicker in detecting slow paths and has a better selection than ST. As the iodepth increases, ST gets close to HST, which still behaves steadily.

The raw performance data for different depths types of IO can be found at:

<https://people.collabora.com/~krisman/GOO0012/hst-vs-st-bench.html>

This was tested primarily on a Google cloud SAN with real data and usage patterns and with artificial benchmarks using fio.

Khazhismel Kumykov (2):
md: Expose struct request to path selector
md: 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           |   6 +
 5 files changed, 589 insertions(+), 2 deletions(-)
 create mode 100644 drivers/md/dm-historical-service-time.c
Signature · 1 line
2.26.0
#1 lore raw

PATCH 1/2 md: Expose struct request to path selector

From: Khazhismel Kumykov <[email protected]>

This allows a path selector to access metadata such as request start and end time. nr_bytes is retained for end_io, as blk_rq_bytes represents the number of bytes *left* in a request, and is 0 after a request is finished.

---
 drivers/md/dm-mpath.c         | 12 ++++++++++--
 drivers/md/dm-path-selector.h |  6 ++++++
 2 files changed, 16 insertions(+), 2 deletions(-)
drivers/md/dm-mpath.c +10 -2
index 2bc18c9c3abc..0cdd3a939d41 100644
@@ -546,7 +546,12 @@ static int multipath_clone_and_map(struct dm_target *ti, struct request *rq,
 	clone->cmd_flags |= REQ_FAILFAST_TRANSPORT;
 	*__clone = clone;
 
-	if (pgpath->pg->ps.type->start_io)
+	if (pgpath->pg->ps.type->start_io_rq)
+		pgpath->pg->ps.type->start_io_rq(&pgpath->pg->ps,
+					      &pgpath->path,
+					      clone ?: rq,
+					      nr_bytes);
+	else if (pgpath->pg->ps.type->start_io)
 		pgpath->pg->ps.type->start_io(&pgpath->pg->ps,
 					      &pgpath->path,
 					      nr_bytes);
@@ -1614,7 +1619,10 @@ static int multipath_end_io(struct dm_target *ti, struct request *clone,
 	if (pgpath) {
 		struct path_selector *ps = &pgpath->pg->ps;
 
-		if (ps->type->end_io)
+		if (ps->type->end_io_rq)
+			ps->type->end_io_rq(ps, &pgpath->path,
+					 clone, mpio->nr_bytes);
+		else if (ps->type->end_io)
 			ps->type->end_io(ps, &pgpath->path, mpio->nr_bytes);
 	}
 
drivers/md/dm-path-selector.h +6 -0
index b6eb5365b1a4..98b6c9d4e21f 100644
@@ -12,6 +12,7 @@
 #ifndef	DM_PATH_SELECTOR_H
 #define	DM_PATH_SELECTOR_H
 
+#include <linux/blkdev.h>
 #include <linux/device-mapper.h>
 
 #include "dm-mpath.h"
@@ -75,6 +76,11 @@ struct path_selector_type {
 			 size_t nr_bytes);
 	int (*end_io) (struct path_selector *ps, struct dm_path *path,
 		       size_t nr_bytes);
+
+	int (*start_io_rq)(struct path_selector *ps, struct dm_path *path,
+			   const struct request *rq, size_t nr_bytes);
+	int (*end_io_rq)(struct path_selector *ps, struct dm_path *path,
+			 const struct request *rq, size_t nr_bytes);
 };
 
 /* Register a path selector */
Signature · 1 line
2.26.0
#2 lore raw

PATCH 2/2 md: 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 d6d5ab23c088..6f348a66450c 100644
@@ -443,6 +443,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 d91a7edcd2ab..d148eeade973 100644
@@ -54,6 +54,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.0
#3 lore raw
In reply to Gabriel Krisman Bertazi
Quoted 28 lines · Gabriel Krisman Bertazi

Hello,

This small series implements a new path selector that leverages historical path IO time in order to estimate future path performance. Implementation details can be found on Patch 2.

This selector yields better path distribution, considering the mean deviation from the calculated optimal utilization, for small IO depths when compared to the Service Time selector with fio benchmarks. For instance, on a multipath setup with 4 paths, where one path is 4 times slower than the rest, issuing 500MB of randwrites, we have the following path utilization rates:

      |    depth=1    |    depth=64   |       |
      |   ST  |   HST |   ST  |   HST |  Best |
|-----+-------+-------+-------+-------+-------|
| sda | 0.250 | 0.294 | 0.297 | 0.294 | 0.307 |
| sdb | 0.250 | 0.297 | 0.296 | 0.297 | 0.307 |
| sdc | 0.250 | 0.296 | 0.298 | 0.296 | 0.307 |
| sdd | 0.250 | 0.112 | 0.106 | 0.112 | 0.076 |

For small depths, HST is much quicker in detecting slow paths and has a better selection than ST. As the iodepth increases, ST gets close to HST, which still behaves steadily.

The raw performance data for different depths types of IO can be found at:

Quoted 8 lines

<https://people.collabora.com/~krisman/GOO0012/hst-vs-st-bench.html>

This was tested primarily on a Google cloud SAN with real data and usage patterns and with artificial benchmarks using fio.

Khazhismel Kumykov (2):
md: Expose struct request to path selector
md: Add Historical Service Time Path Selector

Looks like you've put a lot of time to this and I'd be happy to help you get this to land upstream.

But... (you knew there'd be at least one "but" right? ;) I'm not liking making this path selector request-based specific. All other selectors up to this point are request-based vs bio-based agnostic.

Would you be open to dropping patch 1/2 and replacing it with something like the following patch?

Then you'd pass 'u64 start_time_ns' into the path_selector_type's .end_io (and possibly .start_io).

drivers/md/dm.c +10 -0
index df13fdebe21f..50121513227b 100644
@@ -674,6 +674,16 @@ static bool md_in_flight(struct mapped_device *md)
 		return md_in_flight_bios(md);
 }
 
+u64 dm_start_time_ns_from_clone(struct bio *bio)
+{
+	struct dm_target_io *tio = container_of(bio, struct dm_target_io, clone);
+	struct dm_io *io = tio->io;
+
+	/* FIXME: convert io->start_time from jiffies to nanoseconds */
+	return (u64)jiffies_to_msec(io->start_time) * NSEC_PER_MSEC;
+}
+EXPORT_SYMBOL_GPL(dm_start_time_ns_from_clone);
+
 static void start_io_acct(struct dm_io *io)
 {
 	struct mapped_device *md = io->md;
include/linux/device-mapper.h +2 -0
index 475668c69dbc..e2d506dd805e 100644
@@ -329,6 +329,8 @@ void *dm_per_bio_data(struct bio *bio, size_t data_size);
 struct bio *dm_bio_from_per_bio_data(void *data, size_t data_size);
 unsigned dm_bio_get_target_bio_nr(const struct bio *bio);
 
+u64 dm_start_time_ns_from_clone(struct bio *bio);
+
 int dm_register_target(struct target_type *t);
 void dm_unregister_target(struct target_type *t);
 
#4 lore raw
Quoted 8 lines · Mike Snitzer

Looks like you've put a lot of time to this and I'd be happy to help you get this to land upstream.

But... (you knew there'd be at least one "but" right? ;) I'm not liking making this path selector request-based specific. All other selectors up to this point are request-based vs bio-based agnostic.

Quoted 5 lines

Would you be open to dropping patch 1/2 and replacing it with something like the following patch?

Then you'd pass 'u64 start_time_ns' into the path_selector_type's .end_io (and possibly .start_io).

I think it is fine.

Kind of a MD newbie question, but if I understand correctly, dm_start_time_ns_from_clone is only for bio based multipath, and we just pass req->io_start_time directly on request based multipath, right? If I understand the code correctly, start_io_acct is only called for the bio level DM.

I will update the patches, do a quick round of tests with BIO based and send a v2.

Thanks a lot,

Signature · 1 line
Gabriel Krisman Bertazi