md: add dm-raid1 read balancing

RFC PATCH In review Konstantin Sharlaimov 5 participants 10 messages Nov 3, 2007 – Nov 11, 2007

Subsystems (2)

MD RAID Device mapper

lore

Share & tools

lore

Konstantin Sharlaimov

author

2007-11-03 10:08 UTC #0 lore raw

RFC PATCH 1/1 md: add dm-raid1 read balancing

This patch adds RAID1 read balancing to device mapper. A read operation that is close (in terms of sectors) to a previous read or write goes to the same mirror.

Signed-off-by Konstantin Sharlaimov <[email protected]>

---
Please give it a try, it works for me, yet my results might be system-specific. Any feedback (bug-reports, suggestions) will be greatly appreciated.

drivers/md/dm-raid1.c renamed from drivers/md/dm-raid1.c.old +63 -2

@@ -19,6 +19,7 @@
 #include <linux/time.h>
 #include <linux/vmalloc.h>
 #include <linux/workqueue.h>
+#include <linux/random.h>
 
 #define DM_MSG_PREFIX "raid1"
 #define DM_IO_PAGES 64

@@ -26,6 +27,9 @@
 #define DM_RAID1_HANDLE_ERRORS 0x01
 #define errors_handled(p)	((p)->features & DM_RAID1_HANDLE_ERRORS)
 
+/* Read balancing max hdd head distance */
+#define DM_RAID1_BALANCE_MAX_IO_DISTANCE	(256)
+
 static DECLARE_WAIT_QUEUE_HEAD(_kmirrord_recovery_stopped);
 
 /*-----------------------------------------------------------------

@@ -116,6 +120,7 @@ struct mirror {
 	atomic_t error_count;
 	struct dm_dev *dev;
 	sector_t offset;
+	sector_t last_io_sector;
 };
 
 struct mirror_set {

@@ -741,13 +746,51 @@ static void do_recovery(struct mirror_se
 	}
 }
 
+static void set_mirror_last_io_sector(struct mirror *m, sector_t sector)
+{
+	/* FIXME: Probably some more work is needed here, however this is unlikely */
+	m->last_io_sector = sector;
+}
+
 /*-----------------------------------------------------------------
  * Reads
  *---------------------------------------------------------------*/
+/*
+ * There is a per-array 'last IO operation' sector number maintained by
+ * read and write handlers for the region. When balancing reads we pick 
+ * the disk whose IO operation (HDD head position) is closest.
+ */
 static struct mirror *choose_mirror(struct mirror_set *ms, sector_t sector)
 {
-	/* FIXME: add read balancing */
-	return ms->default_mirror;
+	/* If we got here, then the array is in sync and we can pick any mirror */
+	
+	unsigned int i;
+	struct mirror *use_mirror;
+	sector_t use_distance, new_distance;
+	
+	use_mirror = &ms->mirror[0];
+	use_distance = abs(sector - ms->mirror[0].last_io_sector);
+		
+	for (i = 1; i < ms->nr_mirrors; i++) {
+		new_distance = abs(sector - ms->mirror[i].last_io_sector);
+		if (new_distance < use_distance) {
+			use_distance = new_distance;
+			use_mirror = &ms->mirror[i];
+		}
+	}
+	
+	/* 
+	 * If the HDD head is too far from the needed sector then we do stochastic 
+	 * balancing - chose the mirror randomly. This appers to have a better 
+	 * chance of chosing an idle disk in case of two or more regions residing 
+	 * on the same physical disk.
+	 *
+	 * TODO: Gather more statistical data and verify that the above is correct
+	 */
+	if (use_distance > DM_RAID1_BALANCE_MAX_IO_DISTANCE)
+		return &ms->mirror[random32() % ms->nr_mirrors];
+	else
+		return use_mirror;
 }
 
 /*

@@ -776,6 +819,9 @@ static void do_reads(struct mirror_set *
 		else
 			m = ms->default_mirror;
 
+		/* Set last IO position for chosen mirror */
+		set_mirror_last_io_sector(m, bio->bi_sector);
+			
 		map_bio(ms, m, bio);
 		generic_make_request(bio);
 	}

@@ -800,6 +846,21 @@ static void write_callback(unsigned long
 
 	ms = bio_get_ms(bio);
 	bio_set_ms(bio, NULL);
+	
+	/*
+	 * Things might be different for various region states:
+	 * SYNC:	writing is done to all mirrors, reading is balanced
+	 * RECOVERING:	writing is delayed, reading is done from the default
+	 * NOSYNC:	writing to default only, reading from the default
+	 *
+	 * In any case, if we update last IO sector at all mirrors, we will use 
+	 * the up-to-date data when doing read balancing
+	 *
+	 * FIXME: update write position only on the region being written
+	 */
+
+	for (i = 0; i < ms->nr_mirrors; i++)
+		set_mirror_last_io_sector(&ms->mirror[i], bio->bi_sector);
 
 	/*
 	 * NOTE: We don't decrement the pending count here,

Rik van Riel

2007-11-03 14:29 UTC #1 lore raw

Quoted 9 lines · On Sat, 03 Nov 2007 20:08:42 +1000 Konstantin Sharlaimov…

This patch adds RAID1 read balancing to device mapper. A read operation that is close (in terms of sectors) to a previous read or write goes to the same mirror.
Signed-off-by Konstantin Sharlaimov <[email protected]>
---
Please give it a try, it works for me, yet my results might be system-specific. Any feedback (bug-reports, suggestions) will be greatly appreciated.

I like your approach. I have no dm-raid1 array here to test with, but I am curious what your results are :)

The code looks nice.

Signature · 3 lines

"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are,
by definition, not smart enough to debug it." - Brian W. Kernighan

Goswin von Brederlow

2007-11-07 09:15 UTC #2 lore raw

Was: [RFC PATCH 2.6.23.1] md: add dm-raid1 read balancing

In reply to Konstantin Sharlaimov

Quoted 3 lines · Konstantin Sharlaimov

This patch adds RAID1 read balancing to device mapper. A read operation that is close (in terms of sectors) to a previous read or write goes to the same mirror.

I wonder if there shouldn't be a way to turn this off (or if there already is one).

Or more generaly an option to say what is "near". Specifically I would like to teach the raid1 layer that I have 2 external raid boxes with a 16k chunk size. So read/write within a 16k chunk will be the same disk but the next 16k are a different disk and "near" doesn't apply anymore.

MfG
Goswin

Konstantin Sharlaimov

author

2007-11-08 11:06 UTC #3 lore raw

Re: Was: [RFC PATCH 2.6.23.1] md: add dm-raid1 read balancing

Quoted 8 lines · Goswin von Brederlow

I wonder if there shouldn't be a way to turn this off (or if there already is one).
Or more generaly an option to say what is "near". Specifically I would like to teach the raid1 layer that I have 2 external raid boxes with a 16k chunk size. So read/write within a 16k chunk will be the same disk but the next 16k are a different disk and "near" doesn't apply anymore.

Currently there is no way to turn this feature off (this is only a "request for comments" patch), but I'm planning to make it configurable via sysfs and module parameters.

Thanks for suggestion for the "near" definition. What do you think about adding the "chunk_size" parameter (with the default value of 1 chunk = 1 sector). Setting it to 32 will make all reads within 16k chunk to be considered "near" (with zero distance) so they will go to the same disk.

Max distance will also be configurable (after this distance the "read" operation is considered "far" and will go to randomly chosen disk)

Regards,
Konstantin

Goswin von Brederlow

2007-11-08 16:28 UTC #4 lore raw

Re: Was: [RFC PATCH 2.6.23.1] md: add dm-raid1 read balancing

Quoted 19 lines · Konstantin Sharlaimov

Quoted 8 lines · Goswin von Brederlow
I wonder if there shouldn't be a way to turn this off (or if there already is one).
Or more generaly an option to say what is "near". Specifically I would like to teach the raid1 layer that I have 2 external raid boxes with a 16k chunk size. So read/write within a 16k chunk will be the same disk but the next 16k are a different disk and "near" doesn't apply anymore.
Currently there is no way to turn this feature off (this is only a "request for comments" patch), but I'm planning to make it configurable via sysfs and module parameters.
Thanks for suggestion for the "near" definition. What do you think about adding the "chunk_size" parameter (with the default value of 1 chunk = 1 sector). Setting it to 32 will make all reads within 16k chunk to be considered "near" (with zero distance) so they will go to the same disk.

Quoted 5 lines

Max distance will also be configurable (after this distance the "read" operation is considered "far" and will go to randomly chosen disk)
Regards,
Konstantin

Maybe you need more parameter:

chunk_size - size of a continious chunk on the (multi disk) device
stripe_size - size of a stripe of chunks spanning all disks
rotation_size - size of multiple stripes before parity rotates to a
new disk (sign gives direction of rotation)
near_size - size that is considered to be near on a disk

I would give all sizes in blocks of 512 bytes or bytes.

Default would be:

chunk_size = 1 (block)
stripe_size = 1 (block)
rotation_size = 0 (no rotation)
near_size = 256

That would reflect that you have all chunks continious on a normal disk and read/writes are done in 128K chunks.

For raid 1 on raid 0:

chunk_size = raid chunk size
stripe_size = num disks * chunk_size
rotation_size = 0
near_size = 256

For raid 1 on raid 5:

chunk_size = raid chunk size
stripe_size = (num disks - 1) * chunk_size
rotation_size = (num disks - 1) * chunk_size (?)
near_size = 256

and so on.

MfG
Goswin

Rik van Riel

2007-11-08 17:06 UTC #5 lore raw

Re: Was: [RFC PATCH 2.6.23.1] md: add dm-raid1 read balancing

Quoted 1 line · On Thu, 08 Nov 2007 17:28:37 +0100 Goswin von Brederlow…

Maybe you need more parameter:

Generally a bad idea, unless you can come up with sane defaults (which do not need tuning 99% of the time) or you can derive these parameters automatically from the RAID configuration (unlikely with RAID 1?).

Before turning Konstantin's nice and simple code into something complex, it would be good to see benchmark results show that the complexity is actually needed.

Signature · 3 lines

"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are,
by definition, not smart enough to debug it." - Brian W. Kernighan

Bill Davidsen

2007-11-08 17:24 UTC #6 lore raw

Re: Was: [RFC PATCH 2.6.23.1] md: add dm-raid1 read balancing

Quoted 7 lines · Rik van Riel

Quoted 2 lines · On Thu, 08 Nov 2007 17:28:37 +0100 Goswin von Brederlow…
Maybe you need more parameter:

Quoted 9 lines

Generally a bad idea, unless you can come up with sane defaults (which do not need tuning 99% of the time) or you can derive these parameters automatically from the RAID configuration (unlikely with RAID 1?).
Before turning Konstantin's nice and simple code into something complex, it would be good to see benchmark results show that the complexity is actually needed.

I was about to post a question about the benefit of all this logic, I'll trim before posting...

Signature · 3 lines

bill davidsen <[email protected]>
 CTO TMR Associates, Inc
 Doing interesting things with small computers since 1979

Goswin von Brederlow

2007-11-08 19:43 UTC #7 lore raw

Re: Was: [RFC PATCH 2.6.23.1] md: add dm-raid1 read balancing

In reply to Rik van Riel

Quoted 5 lines · Rik van Riel

Quoted 1 line · On Thu, 08 Nov 2007 17:28:37 +0100 Goswin von Brederlow…
Maybe you need more parameter:

Quoted 7 lines

Generally a bad idea, unless you can come up with sane defaults (which do not need tuning 99% of the time) or you can derive these parameters automatically from the RAID configuration (unlikely with RAID 1?).
Before turning Konstantin's nice and simple code into something complex, it would be good to see benchmark results show that the complexity is actually needed.

A default of chunk=1, stripe=1, rotate=0 is what you have now. SO there is no regression. It is also the right choice for any device that isn't a (hardware) raid. I don't think 99% of all users have hardware raid.

For stacked software raids the raid1 modul should detect the underlying raid and default to values reflecting the raid disk below (assuming the mirrors have reasonable equal layouts). That would truely only leave hardware raids to be manually tuned.

MfG
Goswin

Bill Davidsen

2007-11-08 17:35 UTC #8 lore raw

Re: Was: [RFC PATCH 2.6.23.1] md: add dm-raid1 read balancing

In reply to Goswin von Brederlow

Quoted 32 lines · Goswin von Brederlow

Quoted 20 lines · Konstantin Sharlaimov
Quoted 9 lines · Goswin von Brederlow
I wonder if there shouldn't be a way to turn this off (or if there already is one).
Or more generaly an option to say what is "near". Specifically I would like to teach the raid1 layer that I have 2 external raid boxes with a 16k chunk size. So read/write within a 16k chunk will be the same disk but the next 16k are a different disk and "near" doesn't apply anymore.
Currently there is no way to turn this feature off (this is only a "request for comments" patch), but I'm planning to make it configurable via sysfs and module parameters.
Thanks for suggestion for the "near" definition. What do you think about adding the "chunk_size" parameter (with the default value of 1 chunk = 1 sector). Setting it to 32 will make all reads within 16k chunk to be considered "near" (with zero distance) so they will go to the same disk.
Quoted 6 lines
Max distance will also be configurable (after this distance the "read" operation is considered "far" and will go to randomly chosen disk)
Regards,
Konstantin
Maybe you need more parameter:

Quoted 8 lines

chunk_size - size of a continious chunk on the (multi disk) device
stripe_size - size of a stripe of chunks spanning all disks
rotation_size - size of multiple stripes before parity rotates to a
new disk (sign gives direction of rotation)
near_size - size that is considered to be near on a disk
I would give all sizes in blocks of 512 bytes or bytes.

Why? Would there ever be a time when there would be a significant (or any) benefit from a size other than a multiple of chunk size? If you give the rest of the sizes in multiples of chunk size it invites less human math.

Quoted 2 lines

Default would be:

Default would be "zero" to indicate that the raid system should figure out what to use, allowing the value of "one" to actually mean what it says. It also invites use of zero for the rest of the calculated sizes, indicating the raid subsystem should select values. With coming SSD hardware you may actually want one to mean one.

Quoted 32 lines

chunk_size = 1 (block)
stripe_size = 1 (block)
rotation_size = 0 (no rotation)
near_size = 256
That would reflect that you have all chunks continious on a normal disk and read/writes are done in 128K chunks.
For raid 1 on raid 0:
chunk_size = raid chunk size
stripe_size = num disks * chunk_size
rotation_size = 0
near_size = 256
For raid 1 on raid 5:
chunk_size = raid chunk size
stripe_size = (num disks - 1) * chunk_size
rotation_size = (num disks - 1) * chunk_size (?)
near_size = 256
and so on.
MfG
Goswin
-
To unsubscribe from this list: send the line "unsubscribe linux-raid" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

Signature · 3 lines

bill davidsen <[email protected]>
 CTO TMR Associates, Inc
 Doing interesting things with small computers since 1979

Samuel Tardieu

2007-11-11 23:36 UTC #9 lore raw

In reply to Konstantin Sharlaimov

Quoted 2 lines

Quoted 2 lines
Quoted 2 lines
Quoted 2 lines
Quoted 2 lines
"Konstantin" == Konstantin Sharlaimov
<[email protected]> writes:

Konstantin> This patch adds RAID1 read balancing to device mapper. A Konstantin> read operation that is close (in terms of sectors) to a Konstantin> previous read or write goes to the same mirror.

I am currently running it on top of a 2.6.24-rc2 kernel and it works fine so far.

Sam

Signature · 1 line

Samuel Tardieu -- [email protected] -- http://www.rfc1149.net/