md/raid5: improve IO pattern

Bump the flush stripe batch size to 2048. For my 12 disks raid array, the stripes takes:
12 * 4k * 2048 = 96MB

This is still quite small. A hardware raid card generally has 1GB size, which we suggest the raid5-cache has similar cache size.

The advantage of a big batch size is we can dispatch a lot of IO in the same time, then we can do some scheduling to make better IO pattern.

Last patch prioritizes stripes, so we don't worry about a big flush stripe batch will starve normal stripes.

Signed-off-by Shaohua Li <[email protected]>

---
 drivers/md/raid5-cache.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

drivers/md/raid5-cache.c +0 -0

index 3f307be..b25512c 100644

drivers/md/raid5-cache.c +0 -0

 /* reclaim stripes in groups */
 #define R5C_RECLAIM_STRIPE_GROUP (NR_STRIPE_HASH_LOCKS * 2)
 

Signature · 1 line

2.9.3

Quoted 18 lines · Shaohua Li

Bump the flush stripe batch size to 2048. For my 12 disks raid array, the stripes takes:
12 * 4k * 2048 = 96MB

This is still quite small. A hardware raid card generally has 1GB size, which we suggest the raid5-cache has similar cache size.

The advantage of a big batch size is we can dispatch a lot of IO in the same time, then we can do some scheduling to make better IO pattern.

Last patch prioritizes stripes, so we don't worry about a big flush stripe batch will starve normal stripes.

Signed-off-by Shaohua Li <[email protected]>

---
 drivers/md/raid5-cache.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

drivers/md/raid5-cache.c line 46

Quoted 10 lines

drivers/md/raid5-cache.c +1 -1

index 3f307be..b25512c 100644
@@ -43,7 +43,7 @@
 /* wake up reclaim thread periodically */
 #define R5C_RECLAIM_WAKEUP_INTERVAL (30 * HZ)
 /* start flush with these full stripes */
-#define R5C_FULL_STRIPE_FLUSH_BATCH 256
+#define R5C_FULL_STRIPE_FLUSH_BATCH 2048

Fixed numbers are warning signs... I wonder if there is something better
we could do? "conf->max_nr_stripes / 4" maybe? We use that sort of
number elsewhere.
Would that make sense?

Quoted 20 lines · Neil Brown

Quoted 18 lines · Shaohua Li

Bump the flush stripe batch size to 2048. For my 12 disks raid array, the stripes takes:
12 * 4k * 2048 = 96MB

This is still quite small. A hardware raid card generally has 1GB size, which we suggest the raid5-cache has similar cache size.

The advantage of a big batch size is we can dispatch a lot of IO in the same time, then we can do some scheduling to make better IO pattern.

Last patch prioritizes stripes, so we don't worry about a big flush stripe batch will starve normal stripes.

Signed-off-by Shaohua Li <[email protected]>

---
 drivers/md/raid5-cache.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

Quoted 15 lines

drivers/md/raid5-cache.c line 46

Quoted 10 lines

drivers/md/raid5-cache.c +1 -1

index 3f307be..b25512c 100644
@@ -43,7 +43,7 @@
 /* wake up reclaim thread periodically */
 #define R5C_RECLAIM_WAKEUP_INTERVAL (30 * HZ)
 /* start flush with these full stripes */
-#define R5C_FULL_STRIPE_FLUSH_BATCH 256
+#define R5C_FULL_STRIPE_FLUSH_BATCH 2048

Fixed numbers are warning signs... I wonder if there is something better
we could do? "conf->max_nr_stripes / 4" maybe? We use that sort of
number elsewhere.
Would that make sense?

The code where we check the batch size (in r5c_do_reclaim) already a check:
total_cached > conf->min_nr_stripes * 1 / 2
so I think that's ok, no?

Quoted 37 lines · Shaohua Li

Quoted 20 lines · Neil Brown

Quoted 18 lines · Shaohua Li

Bump the flush stripe batch size to 2048. For my 12 disks raid array, the stripes takes:
12 * 4k * 2048 = 96MB

This is still quite small. A hardware raid card generally has 1GB size, which we suggest the raid5-cache has similar cache size.

The advantage of a big batch size is we can dispatch a lot of IO in the same time, then we can do some scheduling to make better IO pattern.

Last patch prioritizes stripes, so we don't worry about a big flush stripe batch will starve normal stripes.

Signed-off-by Shaohua Li <[email protected]>

---
 drivers/md/raid5-cache.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

Quoted 15 lines

drivers/md/raid5-cache.c line 46

Quoted 10 lines

drivers/md/raid5-cache.c +1 -1

index 3f307be..b25512c 100644
@@ -43,7 +43,7 @@
 /* wake up reclaim thread periodically */
 #define R5C_RECLAIM_WAKEUP_INTERVAL (30 * HZ)
 /* start flush with these full stripes */
-#define R5C_FULL_STRIPE_FLUSH_BATCH 256
+#define R5C_FULL_STRIPE_FLUSH_BATCH 2048

Fixed numbers are warning signs... I wonder if there is something better
we could do? "conf->max_nr_stripes / 4" maybe? We use that sort of
number elsewhere.
Would that make sense?

Quoted 3 lines

The code where we check the batch size (in r5c_do_reclaim) already a check:
total_cached > conf->min_nr_stripes * 1 / 2
so I think that's ok, no?

I'm not sure what you are saying.

I'm suggesting that we get rid of R5C_FULL_STRIPE_FLUSH_BATCH and use a number like "conf->max_nr_stripes / 4"
Are you agreeing, or are you saying that you don't think we need to get rid of R5C_FULL_STRIPE_FLUSH_BATCH??

Previous patch (raid5: only dispatch IO from raid5d for harddisk raid) defers IO dispatching. The goal is to create better IO pattern. At that time, we don't sort the deffered IO and hope the block layer can do IO merge and sort. Now the raid5-cache writeback could create large amount of bios. And if we enable muti-thread for stripe handling, we can't control when to dispatch IO to raid disks. In a lot of time, we are dispatching IO which block layer can't do merge effectively.

This patch moves further for the IO dispatching defer. We accumulate bios, but we don't dispatch all the bios after a threshold is met. This 'dispatch partial portion of bios' stragety allows bios coming in a large time window are sent to disks together. At the dispatching time, there is large chance the block layer can merge the bios. To make this more effective, we dispatch IO in ascending order. This increases request merge chance and reduces disk seek.

Signed-off-by Shaohua Li <[email protected]>

---
 drivers/md/raid5.c | 141 ++++++++++++++++++++++++++++++++++++++++++++---------
 drivers/md/raid5.h |  11 ++++-
 2 files changed, 127 insertions(+), 25 deletions(-)

drivers/md/raid5.c +117 -24

index d7c90da..fe6232f 100644
@@ -56,6 +56,7 @@
 #include <linux/nodemask.h>
 #include <linux/flex_array.h>
 #include <trace/events/block.h>
+#include <linux/sort.h>
 
 #include "md.h"
 #include "raid5.h"

@@ -876,41 +877,121 @@ static int use_new_offset(struct r5conf *conf, struct stripe_head *sh)
 	return 1;
 }
 
-static void flush_deferred_bios(struct r5conf *conf)
+static void dispatch_bio_list(struct bio_list *tmp)
 {
-	struct bio_list tmp;
 	struct bio *bio;
 
+	while ((bio = bio_list_pop(tmp)))
+		generic_make_request(bio);
+}
+
+static int cmp_sh(const void *a, const void *b)
+{
+	const struct r5pending_data *da = a;
+	const struct r5pending_data *db = b;
+
+	if (da->sector > db->sector)
+		return 1;
+	if (da->sector < db->sector)
+		return -1;
+	return 0;
+}
+
+static void dispatch_defer_bios(struct r5conf *conf, int target,
+				struct bio_list *list)
+{
+	int start = 0;
+	int end = conf->pending_data_cnt - 1;
+	int mid;
+	int cnt = 0;
+
+	if (conf->pending_data_cnt == 0)
+		return;
+	sort(conf->pending_data, conf->pending_data_cnt,
+		sizeof(struct r5pending_data), cmp_sh, NULL);
+
+	while (start <= end) {
+		mid = (start + end) / 2;
+		if (conf->pending_data[mid].sector > conf->last_bio_pos)
+			end = mid - 1;
+		else if (conf->pending_data[mid].sector < conf->last_bio_pos)
+			start = mid + 1;
+		else {
+			start = mid;
+			break;
+		}
+	}
+
+	end = conf->pending_data_cnt - 1;
+	for (mid = start; mid <= end; mid++) {
+		conf->last_bio_pos = conf->pending_data[mid].sector;
+		bio_list_merge(list, &conf->pending_data[mid].bios);
+
+		cnt++;
+		if (cnt >= target) {
+			mid++;
+			break;
+		}
+	}
+	conf->pending_data_cnt -= cnt;
+	BUG_ON(conf->pending_data_cnt < 0);
+	if (mid <= end) {
+		memmove(&conf->pending_data[start], &conf->pending_data[mid],
+			(end - mid + 1) * sizeof(struct r5pending_data));
+		return;
+	}
+
+	for (mid = 0; mid < start; mid++) {
+		conf->last_bio_pos = conf->pending_data[mid].sector;
+		bio_list_merge(list, &conf->pending_data[mid].bios);
+
+		cnt++;
+		if (cnt >= target) {
+			mid++;
+			break;
+		}
+	}
+
+	conf->pending_data_cnt -= mid;
+	BUG_ON(conf->pending_data_cnt < 0);
+	if (mid == start) {
+		BUG_ON(conf->pending_data_cnt);
+		return;
+	}
+	memmove(&conf->pending_data[0], &conf->pending_data[mid],
+			(start - mid) * sizeof(struct r5pending_data));
+}
+
+static void flush_deferred_bios(struct r5conf *conf)
+{
+	struct bio_list tmp = BIO_EMPTY_LIST;
+
 	if (!conf->batch_bio_dispatch || !conf->group_cnt)
 		return;
 
-	bio_list_init(&tmp);
 	spin_lock(&conf->pending_bios_lock);
-	bio_list_merge(&tmp, &conf->pending_bios);
-	bio_list_init(&conf->pending_bios);
+	dispatch_defer_bios(conf, conf->pending_data_cnt, &tmp);
 	spin_unlock(&conf->pending_bios_lock);
 
-	while ((bio = bio_list_pop(&tmp)))
-		generic_make_request(bio);
+	dispatch_bio_list(&tmp);
 }
 
-static void defer_bio_issue(struct r5conf *conf, struct bio *bio)
+static void defer_issue_bios(struct r5conf *conf, sector_t sector,
+				struct bio_list *bios)
 {
-	/*
-	 * change group_cnt will drain all bios, so this is safe
-	 *
-	 * A read generally means a read-modify-write, which usually means a
-	 * randwrite, so we don't delay it
-	 */
-	if (!conf->batch_bio_dispatch || !conf->group_cnt ||
-	    bio_op(bio) == REQ_OP_READ) {
-		generic_make_request(bio);
-		return;
-	}
+	struct bio_list tmp = BIO_EMPTY_LIST;
+
 	spin_lock(&conf->pending_bios_lock);
-	bio_list_add(&conf->pending_bios, bio);
+	conf->pending_data[conf->pending_data_cnt].sector = sector;
+	bio_list_init(&conf->pending_data[conf->pending_data_cnt].bios);
+	bio_list_merge(&conf->pending_data[conf->pending_data_cnt].bios,
+		bios);
+	conf->pending_data_cnt++;
+	if (conf->pending_data_cnt >= PENDING_IO_MAX)
+		dispatch_defer_bios(conf, PENDING_IO_ONE_FLUSH, &tmp);
 	spin_unlock(&conf->pending_bios_lock);
-	md_wakeup_thread(conf->mddev->thread);
+
+	dispatch_bio_list(&tmp);
 }
 
 static void

@@ -923,6 +1004,8 @@ static void ops_run_io(struct stripe_head *sh, struct stripe_head_state *s)
 	struct r5conf *conf = sh->raid_conf;
 	int i, disks = sh->disks;
 	struct stripe_head *head_sh = sh;
+	struct bio_list pending_bios = BIO_EMPTY_LIST;
+	bool should_defer;
 
 	might_sleep();
 

@@ -939,6 +1022,8 @@ static void ops_run_io(struct stripe_head *sh, struct stripe_head_state *s)
 		}
 	}
 
+	should_defer = conf->batch_bio_dispatch && conf->group_cnt;
+
 	for (i = disks; i--; ) {
 		int op, op_flags = 0;
 		int replace_only = 0;

@@ -1093,7 +1178,10 @@ static void ops_run_io(struct stripe_head *sh, struct stripe_head_state *s)
 				trace_block_bio_remap(bdev_get_queue(bi->bi_bdev),
 						      bi, disk_devt(conf->mddev->gendisk),
 						      sh->dev[i].sector);
-			defer_bio_issue(conf, bi);
+			if (should_defer && op_is_write(op))
+				bio_list_add(&pending_bios, bi);
+			else
+				generic_make_request(bi);
 		}
 		if (rrdev) {
 			if (s->syncing || s->expanding || s->expanded

@@ -1138,7 +1226,10 @@ static void ops_run_io(struct stripe_head *sh, struct stripe_head_state *s)
 				trace_block_bio_remap(bdev_get_queue(rbi->bi_bdev),
 						      rbi, disk_devt(conf->mddev->gendisk),
 						      sh->dev[i].sector);
-			defer_bio_issue(conf, rbi);
+			if (should_defer && op_is_write(op))
+				bio_list_add(&pending_bios, rbi);
+			else
+				generic_make_request(rbi);
 		}
 		if (!rdev && !rrdev) {
 			if (op_is_write(op))

@@ -1156,6 +1247,9 @@ static void ops_run_io(struct stripe_head *sh, struct stripe_head_state *s)
 		if (sh != head_sh)
 			goto again;
 	}
+
+	if (should_defer && !bio_list_empty(&pending_bios))
+		defer_issue_bios(conf, head_sh->sector, &pending_bios);
 }
 
 static struct dma_async_tx_descriptor *

@@ -6808,7 +6902,6 @@ static struct r5conf *setup_conf(struct mddev *mddev)
 	atomic_set(&conf->active_stripes, 0);
 	atomic_set(&conf->preread_active_stripes, 0);
 	atomic_set(&conf->active_aligned_reads, 0);
-	bio_list_init(&conf->pending_bios);
 	spin_lock_init(&conf->pending_bios_lock);
 	conf->batch_bio_dispatch = true;
 	rdev_for_each(rdev, mddev) {

drivers/md/raid5.h +10 -1

index 6b9d2e8..eb6d5d5 100644
@@ -572,6 +572,13 @@ enum r5_cache_state {
 				 */
 };
 
+#define PENDING_IO_MAX 512
+#define PENDING_IO_ONE_FLUSH 128
+struct r5pending_data {
+	sector_t sector; /* stripe sector */
+	struct bio_list bios;
+};
+
 struct r5conf {
 	struct hlist_head	*stripe_hashtbl;
 	/* only protect corresponding hash list and inactive_list */

@@ -689,9 +696,11 @@ struct r5conf {
 	int			worker_cnt_per_group;
 	struct r5l_log		*log;
 
-	struct bio_list		pending_bios;
 	spinlock_t		pending_bios_lock;
 	bool			batch_bio_dispatch;
+	struct r5pending_data	pending_data[PENDING_IO_MAX];
+	int			pending_data_cnt;
+	sector_t		last_bio_pos;
 };
 
 

Signature · 1 line

2.9.3

Quoted 8 lines · Shaohua Li

Previous patch (raid5: only dispatch IO from raid5d for harddisk raid) defers IO dispatching. The goal is to create better IO pattern. At that time, we don't sort the deffered IO and hope the block layer can do IO merge and sort. Now the raid5-cache writeback could create large amount of bios. And if we enable muti-thread for stripe handling, we can't control when to dispatch IO to raid disks. In a lot of time, we are dispatching IO which block layer can't do merge effectively.

Quoted 7 lines

This patch moves further for the IO dispatching defer. We accumulate bios, but we don't dispatch all the bios after a threshold is met. This 'dispatch partial portion of bios' stragety allows bios coming in a large time window are sent to disks together. At the dispatching time, there is large chance the block layer can merge the bios. To make this more effective, we dispatch IO in ascending order. This increases request merge chance and reduces disk seek.

I can see the benefit of batching and sorting requests.

I wonder if the extra complexity of grouping together 512 requests, then submitting the "first" 128 is really worth it. Have you measured the value of that?

If you just submitted every time you got 512 requests, you could use list_sort() on the bio list and wouldn't need an array.

If an array really is best, it would be really nice if "sort" could pass a 'void*' down to the cmp function,
and it could sort all bios that are
*after* last_bio_pos first, and then the others. That would make the code much simpler. I guess sort() could be changed (list_sort() already has a 'priv' argument like this).

If we cannot change sort(), then maybe use lib/bsearch.c for the binary search. Performing two comparisons in the loop of a binary search should get a *fail* in any algorithms class!!
The "pending_data" array that you have added to the r5conf structure adds 4096 bytes. This means it is larger than a page, which is best avoided (though it is unlikely to cause problems). I would allocate it separately.

So there is a lot that I don't really like, but it seems like a good idea in principle.

Quoted 20 lines · Neil Brown

Quoted 8 lines · Shaohua Li

Previous patch (raid5: only dispatch IO from raid5d for harddisk raid) defers IO dispatching. The goal is to create better IO pattern. At that time, we don't sort the deffered IO and hope the block layer can do IO merge and sort. Now the raid5-cache writeback could create large amount of bios. And if we enable muti-thread for stripe handling, we can't control when to dispatch IO to raid disks. In a lot of time, we are dispatching IO which block layer can't do merge effectively.

Quoted 7 lines

This patch moves further for the IO dispatching defer. We accumulate bios, but we don't dispatch all the bios after a threshold is met. This 'dispatch partial portion of bios' stragety allows bios coming in a large time window are sent to disks together. At the dispatching time, there is large chance the block layer can merge the bios. To make this more effective, we dispatch IO in ascending order. This increases request merge chance and reduces disk seek.

I can see the benefit of batching and sorting requests.

Quoted 3 lines

I wonder if the extra complexity of grouping together 512 requests, then submitting the "first" 128 is really worth it. Have you measured the value of that?

I'm pretty sure I tried. The whole point of dispatching the first 128 is we don't have a better pipeline. Grouping 512 and then dispatching them together definitely improve the IO patter, but the request accumulation takes time, we will have no IO running in the window.

Quoted 10 lines

If you just submitted every time you got 512 requests, you could use list_sort() on the bio list and wouldn't need an array.

If an array really is best, it would be really nice if "sort" could pass a 'void*' down to the cmp function,
and it could sort all bios that are
*after* last_bio_pos first, and then the others. That would make the code much simpler. I guess sort() could be changed (list_sort() already has a 'priv' argument like this).

Ok, I'll change this to a list. And add extra pointer to record the last sorted entry. I didn't see the sort uses much time in my profile, but the merge sort looks better. Will do the change.

Quoted 8 lines

If we cannot change sort(), then maybe use lib/bsearch.c for the binary search. Performing two comparisons in the loop of a binary search should get a *fail* in any algorithms class!!
The "pending_data" array that you have added to the r5conf structure adds 4096 bytes. This means it is larger than a page, which is best avoided (though it is unlikely to cause problems). I would allocate it separately.

Yep, already fixed internally.

Quoted 3 lines

So there is a lot that I don't really like, but it seems like a good idea in principle.

ok, thanks for your time!

Thanks,
Shaohua

Quoted 25 lines · Shaohua Li

Quoted 23 lines · Neil Brown

Quoted 8 lines · Shaohua Li

Previous patch (raid5: only dispatch IO from raid5d for harddisk raid) defers IO dispatching. The goal is to create better IO pattern. At that time, we don't sort the deffered IO and hope the block layer can do IO merge and sort. Now the raid5-cache writeback could create large amount of bios. And if we enable muti-thread for stripe handling, we can't control when to dispatch IO to raid disks. In a lot of time, we are dispatching IO which block layer can't do merge effectively.

Quoted 7 lines

This patch moves further for the IO dispatching defer. We accumulate bios, but we don't dispatch all the bios after a threshold is met. This 'dispatch partial portion of bios' stragety allows bios coming in a large time window are sent to disks together. At the dispatching time, there is large chance the block layer can merge the bios. To make this more effective, we dispatch IO in ascending order. This increases request merge chance and reduces disk seek.

I can see the benefit of batching and sorting requests.

I wonder if the extra complexity of grouping together 512 requests, then submitting the "first" 128 is really worth it. Have you measured the value of that?

Quoted 4 lines

I'm pretty sure I tried. The whole point of dispatching the first 128 is we don't have a better pipeline. Grouping 512 and then dispatching them together definitely improve the IO patter, but the request accumulation takes time, we will have no IO running in the window.

But we don't wait for the first batch before we start collecting the next batch - do we? Why would there be a window with no IO running?

Quoted 11 lines

Quoted 10 lines

If you just submitted every time you got 512 requests, you could use list_sort() on the bio list and wouldn't need an array.

If an array really is best, it would be really nice if "sort" could pass a 'void*' down to the cmp function,
and it could sort all bios that are
*after* last_bio_pos first, and then the others. That would make the code much simpler. I guess sort() could be changed (list_sort() already has a 'priv' argument like this).

Quoted 3 lines

Ok, I'll change this to a list. And add extra pointer to record the last sorted entry. I didn't see the sort uses much time in my profile, but the merge sort looks better. Will do the change.

I think both sorts are O(log(N)).
I had thought that list_sort() would work on a bio_list, but it requires a list_head (even though it doesn't use the prev pointer). If it worked on a bio_list and if you could just submit the whole batch, then using list_sort would have meant that you don't need to allocate a table of r5pending_data.
Now with the struct list_head in there, the data is twice the size.

I guess that doesn't matter too much.

It just feels like there should be a cleaner solution, but I cannot find it without writing a new sort function (not that it would be so hard do to that).