Mirroring seek optimization

Mirroring seek optimization

[Robert Long]

Hi,

I don’t know who to talk to, so I thought I would start here. A while back I developed a further optimization for speeding up read access in mirrored disk arrays. Testing reveals that it achieves about a 7% advantage over the current implementation. I had considered patenting it, but I found that there is an existing US patent (7,330,930) that is broad enough to cover the existing Linux mirror implementation as well as my improvement.

Any ideas regarding who to contact regarding further discussion of applying the improvement would be appreciated.

Bob Long


--
To unsubscribe from this list: send the line "unsubscribe linux-raid" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: Mirroring seek optimization

[NeilBrown]

[-- Attachment #1: Type: text/plain, Size: 796 bytes --]

On Sat, 23 Aug 2014 17:51:09 -0700 Robert Long <boblong@k9heritage.com> wrote:

> Hi,
> 
> I don’t know who to talk to, so I thought I would start here. A while back I developed a further optimization for speeding up read access in mirrored disk arrays. Testing reveals that it achieves about a 7% advantage over the current implementation. I had considered patenting it, but I found that there is an existing US patent (7,330,930) that is broad enough to cover the existing Linux mirror implementation as well as my improvement.
> 
> Any ideas regarding who to contact regarding further discussion of applying the improvement would be appreciated.
> 
> Bob Long

Post your patch, test results, documentation, anything to this list.
That would be the best way forward.

NeilBrown

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 828 bytes --]

Mirroring seek optimization

[Robert Long]

Hi Again,

First, the code base that I was working from is now 2 years old. While I doubt that the raid1.c code has changed significantly I could be very wrong. At that time the load balancing algorithm was simply to attempt to split the actively seeked area of the disk into two parts, and have one disk take the low half and one take the high half. The effect of that, in read intensive applications, is to cut in half the overall seek length for each disk in the mirror, resulting in considerable seek time savings and overall higher throughput. A moving average of sector addresses needs to be maintained to make this work, but this is quite easily done. The more writing happens, the more this advantage is lost. The problem with this approach, though not a large one, is that is that a numerical average is not actually representative of the middle of the work area due to outliers, clusters of reads, etc.

A solution to this is to maintain a running median of the sector address. When this is done you get a measurable increase in throughput, at the cost of greater computational overhead. The method that I used to maintain a moving median involves the creation of an equal sized min heap and max heap connected together at the head of each. This connection point represents the current median sector of access requests to the mirror.

Today I fired up the machine that I used to develop and test this modification. It took some time just to locate the modified raid1.c file :) The machine, in addition to the boot drive, is equipped with a couple of 1 TB Hitachi disk drives that were used for test purposes. To be honest I don’t remember the name of the test software that I used, but it seems that it was a pretty performance standard utility, not something I put together myself. Perhaps you could jog my memory. As I mentioned previously the improvement was around 7% with read only testing of random seeks.

If this is of interest I will gladly post the NOT PRODUCTION READY code. (I took some shortcuts in the code for testing purposes, primarily in the assignment of drives to the array so that I didn’t have to figure out how the existing code does such a nice job of drive allocation.)

On the other hand, if the improvement is deemed to be insufficient then I will chuck the code into the dust bin of history. Given the continued rise in the use of SSDs, seek optimization becomes less relevant every day.

Bob Long

PS
This is all the “documentation” that exists other than a few comments sprinkled throughout the code.--
To unsubscribe from this list: send the line "unsubscribe linux-raid" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html