Benefits from computing physical IDE disk geometry?

Benefits from computing physical IDE disk geometry?

[Timothy Miller]

I'm excited about the new I/O scheduler (proposed?) in the 2.5.x kernel, but
I have to admit to a considerable amount of ignorance of its actual
behavior.  Thus, if it already does what I'm talking about, please feel free
to ignore this post.  :)


Any good SCSI drive knows the physical geometry of the disk and can
therefore optimally schedule reads and writes.  Although necessary features,
like read queueing, are also available in the current SATA spec, I'm not
sure most drives will implement it, at least not very well.

So, what if one were to write a program which would perform a bunch of
seek-time tests to estimate an IDE disk's physical geometry?  It could then
make that information available to the kernel to use to reorder accesses
more optimally.  Additionally, discrepancies from expected seek times could
be logged in the kernel and used to further improve efficiency over time.
If it were good enough, many of the advantages of using SCSI disks would
become less significant.

Ideas?

AW: Benefits from computing physical IDE disk geometry?

[Oliver S.]

> Any good SCSI drive knows the physical geometry of the disk and can
> therefore optimally schedule reads and writes.

 If the scheduler inside the OS can rely on the drive to have a linear
mapping it is implemented as a cyclical-scan scheduler, there is only
a little difference in the effectivity of the scheduling.

> Although necessary features, like read queueing, are also available
> in the current SATA spec, I'm not sure most drives will implement it,
> at least not very well.

 AFAIK the Seagate Barracudas implement first-party-dma, which is a
very lightweight implementation of command-queuing; with first-party
-dma, the CPU includes the adresses of where the data for a certain
request is read or written into the request-command so that when the
disk responds to a command, it sends this information back to the
controller. So this chip doesn't have to hold a list of outstanding
requests and their scattered adresses where the data is read from or
written to. Doesn't look very elegant, but that's just in line with
the cheap ATA-concepts.
 And the only controller-chips I'm aware of supporting this features
are the chips fom Silicon Image. But I think that sooner or later,
all SATA-chips will support it.

Re: Benefits from computing physical IDE disk geometry?

[John Bradford]

> Any good SCSI drive knows the physical geometry of the disk and can
> therefore optimally schedule reads and writes.  Although necessary features,
> like read queueing, are also available in the current SATA spec, I'm not
> sure most drives will implement it, at least not very well.
> 
> So, what if one were to write a program which would perform a bunch of
> seek-time tests to estimate an IDE disk's physical geometry?  It could then
> make that information available to the kernel to use to reorder accesses
> more optimally.  Additionally, discrepancies from expected seek times could
> be logged in the kernel and used to further improve efficiency over time.

On a system that's been set up with one large root partition, and
nothing else, you might get a noticable gain, but I would guess that
you could get a simliar gain by partitioning the disk and manually
placing, E.G. /var near the outside of the disk, and things like /etc
near the centre.  I.E. placing more active partitions on faster areas
of the disk.

> If it were good enough, many of the advantages of using SCSI disks would
> become less significant.

Not really - there are still a lot of advantages of SCSI that it
wouldn't address.

John.

Re: Benefits from computing physical IDE disk geometry?

[Nick Piggin]

Timothy Miller wrote:

>I'm excited about the new I/O scheduler (proposed?) in the 2.5.x kernel, but
>I have to admit to a considerable amount of ignorance of its actual
>behavior.  Thus, if it already does what I'm talking about, please feel free
>to ignore this post.  :)
>
>
>Any good SCSI drive knows the physical geometry of the disk and can
>therefore optimally schedule reads and writes.  Although necessary features,
>like read queueing, are also available in the current SATA spec, I'm not
>sure most drives will implement it, at least not very well.
>
The "continuous" nature of drive addressing means that the kernel
can do a fine job seek-wise. Due to write caches and read track
buffers, rotational scheduling (which could be done if we knew
geometry) would provide too little gain for the complexity. I would
say that for most workloads you wouldn't see any difference. (IMO)

>
>
>So, what if one were to write a program which would perform a bunch of
>seek-time tests to estimate an IDE disk's physical geometry?
>
Yes, something like this has been done.

>It could then
>make that information available to the kernel to use to reorder accesses
>more optimally.  Additionally, discrepancies from expected seek times could
>be logged in the kernel and used to further improve efficiency over time.
>
The benefit I see is knowing the seek time itself (not geometry), which
can be used to tune the IO scheduler. This is something that I'll
probably need to do (in kernel) in order to get my IO scheduler in 2.6,
as it probably (not tested yet) has bad failure cases on high seek time
devices like CDROMs.

>
>If it were good enough, many of the advantages of using SCSI disks would
>become less significant.
>
I'm not sure that this is among SCSI's big advantages. I know some
SCSI disks have farness/starvation problems with big reorder windows.

>
>
>Ideas?
>
It is worth looking into I think. I will be testing something like it
for AS but in kernel not userspace. I don't think it would be very
useful to help basic head movement optimization, but I would like
someone else to prove me wrong.

Re: Benefits from computing physical IDE disk geometry?

[Timothy Miller]

From: "Nick Piggin" <piggin@cyberone.com.au>


> The benefit I see is knowing the seek time itself (not geometry), which
> can be used to tune the IO scheduler. This is something that I'll
> probably need to do (in kernel) in order to get my IO scheduler in 2.6,
> as it probably (not tested yet) has bad failure cases on high seek time
> devices like CDROMs.

Well, that IS the heart of the matter, really.  Detecting geometry was only
a means to the end of predicting seek time and rotational latency.  If you
could magically predict the seek time between any two accesses, then you
could sort your queue optimally.  What would be able to do that?  A neural
net?  :)  What would be able to do that without a lot of training time?

Personally, I've been excited about AS, and I would hate to see it not get
in.

Re: Benefits from computing physical IDE disk geometry?

[Nick Piggin]

Timothy Miller wrote:

>From: "Nick Piggin" <piggin@cyberone.com.au>
>
>
>>The benefit I see is knowing the seek time itself (not geometry), which
>>can be used to tune the IO scheduler. This is something that I'll
>>probably need to do (in kernel) in order to get my IO scheduler in 2.6,
>>as it probably (not tested yet) has bad failure cases on high seek time
>>devices like CDROMs.
>>
>
>Well, that IS the heart of the matter, really.  Detecting geometry was only
>a means to the end of predicting seek time and rotational latency.
>
OK yeah. I thought you had more exotic techniques in mind
like rotational latency optimisation which require actual geometry

>  If you
>could magically predict the seek time between any two accesses, then you
>could sort your queue optimally.
>
Well using the assumption that |head sector - target sector| gives
an ordering correstponding to seek time, we do sort the queue optimally.
I personally feel that being trickier than that is too much complexity.

>What would be able to do that?  A neural
>net?  :)  What would be able to do that without a lot of training time?
>
I think just some averages, maybe histograms. Not quite sure exactly
how I'll need to do it. I probably want each IO submitting process'
average seek time, and the average seek time when changing from one
process to another. Nothing too fancy.

>
>
>Personally, I've been excited about AS, and I would hate to see it not get
>in.
>
It is getting there. It definitely does some things much better than
deadline, although in other areas it is not so good.

Re: Benefits from computing physical IDE disk geometry?

[Mark Hahn]

> >>The benefit I see is knowing the seek time itself (not geometry), which
> >>can be used to tune the IO scheduler. This is something that I'll

but seek time is some combination of headswitch time, rotational 
latency, and actual head motion.  the first three are basically
not accessible in any practical way.  the latter is easy, and the 
current approximation (seek time is a linear function of block distance)
is very reasonable.

adjusting the cost function would be interesting: I'm guessing that 
handling short seeks (which are quite fast) would be more important
than adjusting for zones.  given that the current queueing code 
handles starvation, I wonder if we could actually permit backward
seeks of, say, 0-2 cylinders.

> Well using the assumption that |head sector - target sector| gives
> an ordering correstponding to seek time, we do sort the queue optimally.
> I personally feel that being trickier than that is too much complexity.

exactly.

Re: Benefits from computing physical IDE disk geometry?

[Nick Piggin]

Mark Hahn wrote:

>>>>The benefit I see is knowing the seek time itself (not geometry), which
>>>>can be used to tune the IO scheduler. This is something that I'll
>>>>
>
>but seek time is some combination of headswitch time, rotational 
>latency, and actual head motion.  the first three are basically
>not accessible in any practical way.  the latter is easy, and the 
>
Yep which is one reason why I don't think being fancy will pay
off (the other reason being that even if you did know the parameters
I don't think they would help a lot).

I just want to know the average seek time.

>
>current approximation (seek time is a linear function of block distance)
>is very reasonable.
>
Well, strictly, not linear. But yes it does provide a good ordering.
That is besides the point though: I can decide if one request will
have a shorter seek time than another just fine. I would still like
to know the aproximate seek _time_ for higher level tuning stuff
eg. will anticipation be worth it, and how soon should requests
expire.

>
>
>adjusting the cost function would be interesting: I'm guessing that 
>handling short seeks (which are quite fast) would be more important
>than adjusting for zones.  given that the current queueing code 
>handles starvation, I wonder if we could actually permit backward
>seeks of, say, 0-2 cylinders.
>
There is (in AS) no cost function further than comparing distance
from the head. Closest forward seek wins.

If by the queueing code you mean the actual IO schedulers? Then
yes, they do handle starvation, however they (AS, deadline)
handle _fairness_ by not seeking backward. Well actually
AS does allow a process to seek upto IIRC 256MB backward
which is a couple of ext2 blockgroups while maintaining quite
good fairness.

>
>
>>Well using the assumption that |head sector - target sector| gives
>>an ordering correstponding to seek time, we do sort the queue optimally.
>>I personally feel that being trickier than that is too much complexity.
>>
>
>exactly.
>  
>

Re: Benefits from computing physical IDE disk geometry?

[Alan Cox]

On Sad, 2003-04-12 at 23:46, Timothy Miller wrote:
> Any good SCSI drive knows the physical geometry of the disk and can
> therefore optimally schedule reads and writes.  Although necessary features,
> like read queueing, are also available in the current SATA spec, I'm not
> sure most drives will implement it, at least not very well.

Some of them are in recent PATA and Jens Axboe implemented the TCQ for
IDE, but its all a bit limited right now

> So, what if one were to write a program which would perform a bunch of
> seek-time tests to estimate an IDE disk's physical geometry?  It could then
> make that information available to the kernel to use to reorder accesses
> more optimally.

Its a common misconception that a disk looks something like it did 15
years ago. Your ATA disk is basically an entire standalone computer 
running a small OS. The physical disk layout does not divide neatly 
into equal sized cylinders and some blocks may even be in suprising
places due to bad block sparing or anything else the drive manufacturer
felt appropriate.

The drive firmware will look after a lot of the optimising for you,
and once it gets TCQ it will probably get you all you want from SCSI
with SATA. Until then playing games with it isnt likely to help - feed
IDE disks large, sequential I/O as much as possible and they'll deliver
you very nice numbers. 

Alan

Re: Benefits from computing physical IDE disk geometry?

[John Bradford]

> > So, what if one were to write a program which would perform a bunch of
> > seek-time tests to estimate an IDE disk's physical geometry?  It could then
> > make that information available to the kernel to use to reorder accesses
> > more optimally.
> 
> Its a common misconception that a disk looks something like it did 15
> years ago. Your ATA disk is basically an entire standalone computer 
> running a small OS. The physical disk layout does not divide neatly 
> into equal sized cylinders and some blocks may even be in suprising
> places due to bad block sparing or anything else the drive manufacturer
> felt appropriate.

Is the basic assumption that lower block numbers are generally located
in zones nearer the outside of the disk still true, though?  I.E. do
you know of any disks that 'start from the middle'?  I usually
recommend that people place their swap and /var partitions near the
beginning of the disk, (for a _slight_ improvement), but maybe there
is a good reason not to do this for some disks?

John.

Re: Benefits from computing physical IDE disk geometry?

[Helge Hafting]

On Sun, Apr 13, 2003 at 05:15:51PM +0100, John Bradford wrote:
> Is the basic assumption that lower block numbers are generally located
> in zones nearer the outside of the disk still true, though?  I.E. do
> you know of any disks that 'start from the middle'?  I usually
> recommend that people place their swap and /var partitions near the
> beginning of the disk, (for a _slight_ improvement), but maybe there
> is a good reason not to do this for some disks?

I generally put swap in the middle of the disk, not on the
"fastest" end.  The "fast" end is faster for large transfers,
but that isn't what swap is about.

Swap tends to have lots of small transfers now and then, in between
other io.  So you want a short seek from wherever the
access arm is to keep latency down, and the middle of the
disk has short way both from inner and outer tracks.

Helge Hafting

Re: Benefits from computing physical IDE disk geometry?

[John Bradford]

> > Is the basic assumption that lower block numbers are generally located
> > in zones nearer the outside of the disk still true, though?  I.E. do
> > you know of any disks that 'start from the middle'?  I usually
> > recommend that people place their swap and /var partitions near the
> > beginning of the disk, (for a _slight_ improvement), but maybe there
> > is a good reason not to do this for some disks?
> 
> I generally put swap in the middle of the disk, not on the
> "fastest" end.  The "fast" end is faster for large transfers,
> but that isn't what swap is about.

Well, I was thinking of machines that are really starved of physical
RAM, 32 MB or less, even down to 4 MB.  I generally run swapless on
'real' machines :-).

Also, the higher capcity tracks mean less seeks, so the chance of not
having to seek at all increases slightly.

> Swap tends to have lots of small transfers now and then, in between
> other io.  So you want a short seek from wherever the
> access arm is to keep latency down, and the middle of the
> disk has short way both from inner and outer tracks.

Yeah, that would probably be a better idea for machines which are only
really hitting swap on occasions, instead of all the time :-).

John.

Re: Benefits from computing physical IDE disk geometry?

[Wes Felter]

On Sat, 2003-04-12 at 17:46, Timothy Miller wrote:

> So, what if one were to write a program which would perform a bunch of
> seek-time tests to estimate an IDE disk's physical geometry?  It could then
> make that information available to the kernel to use to reorder accesses
> more optimally.

Greg Ganger et al. have done some recent work in this area:

http://www.pdl.cmu.edu/PDL-FTP/stray/freeblocks_abs.html
http://www.pdl.cmu.edu/PDL-FTP/stray/traxtent_abs.html

-- 
Wes Felter - wesley@felter.org - http://felter.org/wesley/

Re: Benefits from computing physical IDE disk geometry?

[Chuck Ebbert]

Nick Piggin wrote:


>>
>> Any good SCSI drive knows the physical geometry of the disk and can
>> therefore optimally schedule reads and writes.  Although necessary features,
>> like read queueing, are also available in the current SATA spec, I'm not
>> sure most drives will implement it, at least not very well.
>>
> The "continuous" nature of drive addressing means that the kernel
> can do a fine job seek-wise. Due to write caches and read track
> buffers, rotational scheduling (which could be done if we knew
> geometry) would provide too little gain for the complexity. I would
> say that for most workloads you wouldn't see any difference. (IMO)


  OTOH you can come up with scenarios like, say, a DBMS doing 16K page
aligned IO to raw devices where you might see big gains from making sure
those 16K chunks didn't cross a physical cylinder boundary.


--
 Chuck

Re: Benefits from computing physical IDE disk geometry?

[Dr. David Alan Gilbert]

* Chuck Ebbert (76306.1226@compuserve.com) wrote:

>   OTOH you can come up with scenarios like, say, a DBMS doing 16K page
> aligned IO to raw devices where you might see big gains from making sure
> those 16K chunks didn't cross a physical cylinder boundary.

Maybe true; but figuring out where the drive really puts your sectors
these days ain't that easy; what with remapping and multiple different
densities on the platter.

Now given these discs have processors on board isn't it about time
someone improved the disc interface standards to push some of the
intelligence drivewards?  I guess with enough intelligence the drive
could do free block allocation and could do things like copying blocks
around for you.

Dave
 ---------------- Have a happy GNU millennium! ----------------------   
/ Dr. David Alan Gilbert    | Running GNU/Linux on Alpha,68K| Happy  \ 
\ gro.gilbert @ treblig.org | MIPS,x86,ARM,SPARC,PPC & HPPA | In Hex /
 \ _________________________|_____ http://www.treblig.org   |_______/

Re: Benefits from computing physical IDE disk geometry?

[Lars Marowsky-Bree]

On 2003-04-13T19:24:05,
   "Dr. David Alan Gilbert" <gilbertd@treblig.org> said:

> Now given these discs have processors on board isn't it about time
> someone improved the disc interface standards to push some of the
> intelligence drivewards?  I guess with enough intelligence the drive
> could do free block allocation and could do things like copying blocks
> around for you.

Ah, you have reinvented SCSI (which can copy without involving the host...),
or reinvented the Object Based Storage (see Lustre).


Sincerely,
    Lars Marowsky-Brée <lmb@suse.de>

-- 
SuSE Labs - Research & Development, SuSE Linux AG
  
"If anything can go wrong, it will." "Chance favors the prepared (mind)."
  -- Capt. Edward A. Murphy            -- Louis Pasteur

Re: Benefits from computing physical IDE disk geometry?

[Dr. David Alan Gilbert]

* Lars Marowsky-Bree (lmb@suse.de) wrote:
> 
> Ah, you have reinvented SCSI (which can copy without involving the host...),
> or reinvented the Object Based Storage (see Lustre).

Gee and I just thought I was being mad.....

Dave
 ---------------- Have a happy GNU millennium! ----------------------   
/ Dr. David Alan Gilbert    | Running GNU/Linux on Alpha,68K| Happy  \ 
\ gro.gilbert @ treblig.org | MIPS,x86,ARM,SPARC,PPC & HPPA | In Hex /
 \ _________________________|_____ http://www.treblig.org   |_______/

Re: Benefits from computing physical IDE disk geometry?

[Alan Cox]

On Sul, 2003-04-13 at 19:24, Dr. David Alan Gilbert wrote:
> Now given these discs have processors on board isn't it about time
> someone improved the disc interface standards to push some of the
> intelligence drivewards?  I guess with enough intelligence the drive
> could do free block allocation and could do things like copying blocks
> around for you.

I wish it would. Most of the research and stuff so far has either put
the file system into the disk firmware (upgrade hell). Having a disk
which talked entirely about

	read(handle,offset, length)
	write(handle, offset, length)
	alloc(handle, near_handle, length, otherhints...)

might well work out rather better. It also allows the disk to do fairly
major relayout of data as it learns usage.

Re: Benefits from computing physical IDE disk geometry?

[Andreas Dilger]

On Apr 13, 2003  23:14 +0100, Alan Cox wrote:
> On Sul, 2003-04-13 at 19:24, Dr. David Alan Gilbert wrote:
> > Now given these discs have processors on board isn't it about time
> > someone improved the disc interface standards to push some of the
> > intelligence drivewards?  I guess with enough intelligence the drive
> > could do free block allocation and could do things like copying blocks
> > around for you.
> 
> I wish it would. Most of the research and stuff so far has either put
> the file system into the disk firmware (upgrade hell). Having a disk
> which talked entirely about
> 
> 	read(handle,offset, length)
> 	write(handle, offset, length)
> 	alloc(handle, near_handle, length, otherhints...)
> 
> might well work out rather better.

This is essentially what the Lustre Object Storage Target (OST) protocol
looks like.  The client talks to the OST with "object IDs" and does simple
create/destroy/getattr/setattr operations on the objid.

The data I/O protocol (bulk read/write) can do scatter/gather vector I/O
on one or more objects at a time using objid/offset/range triplets, and
the internal data representation is totally opaque to the client (i.e. no
block numbers are passed around in the API).

One thing that is totally missing from the Linux client-side is the ability
to use a "copy" syscall to copy objects directly between OSTs instead of
having to go through the client.

> It also allows the disk to do fairly major relayout of data as it learns
> usage.

Yes, among other things.  We can do stacking of drivers (e.g. RAID, snapshot,
migration, read caching, etc) without having to change the protocol.

Cheers, Andreas
--
Andreas Dilger
http://sourceforge.net/projects/ext2resize/
http://www-mddsp.enel.ucalgary.ca/People/adilger/

Re: Benefits from computing physical IDE disk geometry?

[Alan Cox]

On Sul, 2003-04-13 at 19:03, Chuck Ebbert wrote:
>   OTOH you can come up with scenarios like, say, a DBMS doing 16K page
> aligned IO to raw devices where you might see big gains from making sure
> those 16K chunks didn't cross a physical cylinder boundary.

You couldn't even tell where such boundaries exist, or what the real
block size of the underlying media is. Cyliners are all different sizes.

Re: Benefits from computing physical IDE disk geometry?

[Nick Piggin]

Alan Cox wrote:

>On Sul, 2003-04-13 at 19:03, Chuck Ebbert wrote:
>
>>  OTOH you can come up with scenarios like, say, a DBMS doing 16K page
>>aligned IO to raw devices where you might see big gains from making sure
>>those 16K chunks didn't cross a physical cylinder boundary.
>>
>
>You couldn't even tell where such boundaries exist, or what the real
>block size of the underlying media is. Cyliners are all different sizes.
>
Yes this is getting very difficult as Alan said. Its also something
that we can't do in kernel - the block io scheduler can only choose
from what it is given. I wouldn't be surprised if big databases did
try using some sorts of disk mapping systems to help optimise
their IO however.

Re: Benefits from computing physical IDE disk geometry?

[Chuck Ebbert]

Lars Marowsky-Bree wrote:


> Object Based Storage (see Lustre).


  Thanks, I was trying to remember where I'd seen that.

  Is anyone actually making such things for sale?

--
 Chuck

Re: Benefits from computing physical IDE disk geometry?

[Andreas Dilger]

On Apr 13, 2003  18:13 -0400, Chuck Ebbert wrote:
> Lars Marowsky-Bree wrote:
> > Object Based Storage (see Lustre).
> 
>   Thanks, I was trying to remember where I'd seen that.
> 
>   Is anyone actually making such things for sale?

Yes, there is a 3rd party vendor which has already sold a bunch of
Object Storage Targets (OSTs) to LLNL for the MCR cluster, see:

	http://www.top500.org/top5/2002/11/five/
	http://www.llnl.gov/linux/mcr/
	http://www.bluearc.com/news/press_releases/pr_mcr_121102.shtml

These are not the "OST-on-a-disk" paradigm that we first worked on with
Seagate, but rather large NAS/NFS storage servers that also implement
the Lustre network protocol.  We are also working with other vendors to
implement Linux-based OST targets (I'm not sure whether I can reveal names
or not) for even larger clusters.

Maybe if Lustre becomes popular enough, we will see Lustre implemented on
single disks.  There is an object-based storage group with the SCSI T10
committee, but so far their protocol is mostly unusable for Lustre.

Cheers, Andreas
--
Andreas Dilger
http://sourceforge.net/projects/ext2resize/
http://www-mddsp.enel.ucalgary.ca/People/adilger/

Re: Benefits from computing physical IDE disk geometry?

[Chuck Ebbert]

> You couldn't even tell where such boundaries exist, or what the real
> block size of the underlying media is. Cyliners are all different sizes.


 Not even if you do timing tests?  I know people have done tests that
pinpoint where the xfer rate changes, for example.  I'm sure it
wouldn't be easy, but I bet you could get some useful information.
And at the very least, remapped sectors should be easy to spot...


--

Re: Benefits from computing physical IDE disk geometry?

[Chuck Ebbert]

Alan Cox wrote:


> You couldn't even tell where such boundaries exist, or what the real
> block size of the underlying media is. Cyliners are all different sizes.


  Found this by accident while skimming a new book; haven't visited yet
but it may be of interest:

    A technical report describing Skippy and two other disk drive
microbenchmarks (run in seconds or minutes rather than hours or days)
is at

      http://sunsite.berkeley.edu/
             Dienst/UI/2.0/Describe/ncstrl.ucb/CSD-99-1063

(Hennessey & Patterson 3rd ed., Ch.7, exercise 5.)


--
 "Let's fight till six, and then have dinner," said Tweedledum.
  --Lewis Carroll, _Through the Looking Glass_

Re: Benefits from computing physical IDE disk geometry?

[Chuck Ebbert]

Nick Piggin wrote:


>>
>>but seek time is some combination of headswitch time, rotational 
>>latency, and actual head motion.  the first three are basically
>>not accessible in any practical way.  the latter is easy, and the 
>>
> Yep which is one reason why I don't think being fancy will pay
> off (the other reason being that even if you did know the parameters
> I don't think they would help a lot).


 The graphs in the "skippy" disk benchmark paper are
interesting -- some disks show bizarre peaks and dips in their
times across increasing sector distances. (The lesson here might
be to test your disks and avoid the bad actors rather than try
to compensate for their behavior, though.)


> There is (in AS) no cost function further than comparing distance
> from the head. Closest forward seek wins.


 The RAID1 code has its own scheduler that does similar things.  Why
aren't they being integrated? (See raid1.c:read_balance())

--
 Chuck

Re: Benefits from computing physical IDE disk geometry?

[Nick Piggin]

Chuck Ebbert wrote:

>Nick Piggin wrote:
>
>
>>There is (in AS) no cost function further than comparing distance
>>from the head. Closest forward seek wins.
>>
>
>
> The RAID1 code has its own scheduler that does similar things.  Why
>aren't they being integrated? (See raid1.c:read_balance())
>
If RAID1 can use the generic elevator then it should. I
guess it can't though.

Re: Benefits from computing physical IDE disk geometry?

[Chuck Ebbert]

> If RAID1 can use the generic elevator then it should. I
> guess it can't though.


  No, but it is feeding IO requests into the elevators of the 
block devices below it.  For a given read, all it wants to do
is pick one device to handle the work.  If it could look into
the queues maybe it could make better decisions.

--
 Chuck

Re: Benefits from computing physical IDE disk geometry?

[Nick Piggin]

Chuck Ebbert wrote:

>>If RAID1 can use the generic elevator then it should. I
>>guess it can't though.
>>
>
>
>  No, but it is feeding IO requests into the elevators of the 
>block devices below it.  For a given read, all it wants to do
>is pick one device to handle the work.  If it could look into
>the queues maybe it could make better decisions.
>
OK right. As far as I can see, the algorithm in the RAID1 code
is used to select the best drive to read from? If that is the
case then I don't think it could make better decisions given
more knowledge. It really wants to know if the disk head is
close to request x however it is impossible to tell where the
disk head will be by the time request x is the next in line
for that disk, regardless if it can look at the low level
queues or not.

It seems to me that a better way to layer it would be to have
the complex (ie deadline/AS/CFQ/etc) scheduler handling all
requests into the raid block device, then having a raid
scheduler distributing to the disks, and having the disks
run no scheduler (fifo).

In practice the current scheme probably works OK, though I
wouldn't know due to lack of resources here :P

Re: Benefits from computing physical IDE disk geometry?

[Chuck Ebbert]

Nick Piggin wrote:


> OK right. As far as I can see, the algorithm in the RAID1 code
> is used to select the best drive to read from? If that is the
> case then I don't think it could make better decisions given
> more knowledge.


  How about if it just asks the elevator whether or not a given read
is a good fit with its current workload?  I saw in 2.5 where the balance
code is looking at the number of pending requests and if it's zero then
it sends it to that device.  Somehow I think something better than
that could be done, anyway.


> It seems to me that a better way to layer it would be to have
> the complex (ie deadline/AS/CFQ/etc) scheduler handling all
> requests into the raid block device, then having a raid
> scheduler distributing to the disks, and having the disks
> run no scheduler (fifo).


 That only works if RAID1 is working at the physical disk level (which
it should be AFAIC but people want flexibility to mirror partitions.)


> In practice the current scheme probably works OK, though I
> wouldn't know due to lack of resources here :P


 I've been playing with the 2.4 read balance code and have some
improvements, but real gains need a new approach.

(cc'd to linux-raid)

--
 Chuck

Re: Benefits from computing physical IDE disk geometry?

[Nick Piggin]

Chuck Ebbert wrote:

>Nick Piggin wrote:
>
>
>
>>OK right. As far as I can see, the algorithm in the RAID1 code
>>is used to select the best drive to read from? If that is the
>>case then I don't think it could make better decisions given
>>more knowledge.
>>
>
>
>  How about if it just asks the elevator whether or not a given read
>is a good fit with its current workload?  I saw in 2.5 where the balance
>code is looking at the number of pending requests and if it's zero then
>it sends it to that device.  Somehow I think something better than
>that could be done, anyway.
>
That balance code is probably the IDE or SCSI channel balancing?
In that case, the driver simply wants to know which device it
should service next, which is an appropriate fit (is that what
you were talking about? I don't have source here sorry)


We could ask the elevator if a given read is a good fit. It
would probably help.

>
>
>
>>It seems to me that a better way to layer it would be to have
>>the complex (ie deadline/AS/CFQ/etc) scheduler handling all
>>requests into the raid block device, then having a raid
>>scheduler distributing to the disks, and having the disks
>>run no scheduler (fifo).
>>
>
>
> That only works if RAID1 is working at the physical disk level (which
>it should be AFAIC but people want flexibility to mirror partitions.)
>
How so? Basically you want your high level scheduler to run first.
You want it to act on the stream of requests from the system, not
on the stream of requests to the device. If you know what I mean.

I might be wrong here. I haven't done any testing, and only a
little bit of thinking.

>
>
>
>>In practice the current scheme probably works OK, though I
>>wouldn't know due to lack of resources here :P
>>
>
>
> I've been playing with the 2.4 read balance code and have some
>improvements, but real gains need a new approach.
>
The problem I see, is the higher level schedulers (deadline for
example, as opposed to the RAID scheduler) will find it difficult
to tell if a request will be "good" for them or not. For example
we have 2 devices, 100 requests in each scheduler queue.

Device A's head is at sector x and next request is at x+100,
Device B's head is at sector x+10 and next request is at x+200.

RAID wants to know which queue should take a request at sector
x+1000. What do you do?

The way you would do a good "goodness" function, I guess,
would be to search through all requests on the device, and return
the minimum distance from the request you are running the query
on. Do this for both queues, and insert the request into the
queue with the smallest delta. I don't see much else doing any
good.

On the other hand, if you simply have a fifo after the RAID
scheduler, the RAID scheduler itself knows where each disk's
head will end up simply by tracking the value of the last
sector it has submitted to the device. It also has the advantage
that it doesn't have "high level" scheduling stuff below it
ie. request deadline handling, elevator scheme, etc.

This gives the RAID scheduler more information, without
taking any away from the high level scheduler AFAIKS.

Re: Benefits from computing physical IDE disk geometry?

[Nick Piggin]

Nick Piggin wrote:

> Chuck Ebbert wrote:
>
>> Nick Piggin wrote:
>>
>>
>>
>>> OK right. As far as I can see, the algorithm in the RAID1 code
>>> is used to select the best drive to read from? If that is the
>>> case then I don't think it could make better decisions given
>>> more knowledge.
>>>
>>
>>
>>  How about if it just asks the elevator whether or not a given read
>> is a good fit with its current workload?  I saw in 2.5 where the balance
>> code is looking at the number of pending requests and if it's zero then
>> it sends it to that device.  Somehow I think something better than
>> that could be done, anyway.
>>
> That balance code is probably the IDE or SCSI channel balancing?
> In that case, the driver simply wants to know which device it
> should service next, which is an appropriate fit (is that what
> you were talking about? I don't have source here sorry)
>
>
> We could ask the elevator if a given read is a good fit. It
> would probably help.
>
>>
>>
>>
>>> It seems to me that a better way to layer it would be to have
>>> the complex (ie deadline/AS/CFQ/etc) scheduler handling all
>>> requests into the raid block device, then having a raid
>>> scheduler distributing to the disks, and having the disks
>>> run no scheduler (fifo).
>>>
>>
>>
>> That only works if RAID1 is working at the physical disk level (which
>> it should be AFAIC but people want flexibility to mirror partitions.)
>>
> How so? Basically you want your high level scheduler to run first.
> You want it to act on the stream of requests from the system, not
> on the stream of requests to the device. If you know what I mean.
>
> I might be wrong here. I haven't done any testing, and only a
> little bit of thinking.
>
>>
>>
>>
>>> In practice the current scheme probably works OK, though I
>>> wouldn't know due to lack of resources here :P
>>>
>>
>>
>> I've been playing with the 2.4 read balance code and have some
>> improvements, but real gains need a new approach.
>>
> The problem I see, is the higher level schedulers (deadline for
> example, as opposed to the RAID scheduler) will find it difficult
> to tell if a request will be "good" for them or not. For example
> we have 2 devices, 100 requests in each scheduler queue.
>
> Device A's head is at sector x and next request is at x+100,
> Device B's head is at sector x+10 and next request is at x+200.
>
> RAID wants to know which queue should take a request at sector
> x+1000. What do you do?
>
> The way you would do a good "goodness" function, I guess,
> would be to search through all requests on the device, and return
> the minimum distance from the request you are running the query
> on. Do this for both queues, and insert the request into the
> queue with the smallest delta. I don't see much else doing any
> good. 

Well no I'm an idiot. You obviously don't have to "search
through all requests" as they are (for AS, DL, CFQ) in an
rbtree. So that might not be too bad an idea to investigate.
But...
It still means you get the high level scheduling below where
you want it. This means the read/write batches for each queue
will not stay in sync (not sure if this is a bad thing), request
deadlines will mean even the good "goodness" calculation
does not always be good, process fairness could be badly
impacted for some loads, and AS has other problems
(hopefully not too bad).

Re: Benefits from computing physical IDE disk geometry?

[Chuck Ebbert]

> The way you would do a good "goodness" function, I guess,
> would be to search through all requests on the device, and return
> the minimum distance from the request you are running the query
> on. Do this for both queues, and insert the request into the
> queue with the smallest delta. I don't see much else doing any
> good.


  That would be perfect.  And like you say in a later message, they're
in a tree so it might actually work.  Then the read balance code
wouldn't need to do that calculation at all.

  How hard would this be to add?



> On the other hand, if you simply have a fifo after the RAID
> scheduler, the RAID scheduler itself knows where each disk's
> head will end up simply by tracking the value of the last
> sector it has submitted to the device. It also has the advantage
> that it doesn't have "high level" scheduling stuff below it
> ie. request deadline handling, elevator scheme, etc.
> 
> This gives the RAID scheduler more information, without
> taking any away from the high level scheduler AFAIKS.


 But then wouldn't you have to put all that into the RAID
scheduler?

--
 Chuck

Re: Benefits from computing physical IDE disk geometry?

[Nick Piggin]

Chuck Ebbert wrote:

>>The way you would do a good "goodness" function, I guess,
>>would be to search through all requests on the device, and return
>>the minimum distance from the request you are running the query
>>on. Do this for both queues, and insert the request into the
>>queue with the smallest delta. I don't see much else doing any
>>good.
>>
>
>
>  That would be perfect.  And like you say in a later message, they're
>in a tree so it might actually work.  Then the read balance code
>wouldn't need to do that calculation at all.
>
>  How hard would this be to add?
>
It would be easy to add. Though of course it would have to
be shown to give an improvement somewhere to be included.

>
>
>
>
>>On the other hand, if you simply have a fifo after the RAID
>>scheduler, the RAID scheduler itself knows where each disk's
>>head will end up simply by tracking the value of the last
>>sector it has submitted to the device. It also has the advantage
>>that it doesn't have "high level" scheduling stuff below it
>>ie. request deadline handling, elevator scheme, etc.
>>
>>This gives the RAID scheduler more information, without
>>taking any away from the high level scheduler AFAIKS.
>>
>
>
> But then wouldn't you have to put all that into the RAID
>scheduler?
>
No - as far as I can see, the RAID scheduler already does
this. Having FIFOs between it and the disks would simply
make its assumptions valid.