Ordering of I/O requests

OSR_Community_User · November 2, 2004, 5:29am

I’m trying to decide if there is actually an “ordering” to I/O requests. Say
I have two threads on two processors and they both issue a disk write in
some known order on a single file handle. It seems like both those requests
will pass down the storage stack in parallel, and not get serialized until
they reach either the disk bus or possibly the SCSI port driver target
queue. As either thread can be interrupted by DPC or ISR processing, it’s
not know which request will actually happen first. If I’m running
multipathing hardware, they might even take different routes to the drive,
and get serialized there.

I care about this because I would like to be able to pipeline a bunch of
disk writes with overlapping headers and trailers, and assure they get
applied in the pipeline order. I don’t really want to wait for one to
complete before issuing the next one, which seems like the only way to
ASSURE an ordering. The end data on the disk will not be correct unless the
header of the second write is applied after the trailer of the first write,
and the header of the third write is applied after the trailer of the second
write.

I put on my user mode hat and think “of course the order the writes get
initially issued in will be preserved on the physical disk”, but I put on my
driver writer hat and say “what specifically will keep the writes in the
same order as they started in?”.

Anybody know the real answer?

Jan

OSR_Community_User · November 2, 2004, 7:27am

The wonderful thing about this topic is it all depends upon processing
at each layer. Since you specified they are on the same handle, let’s
note that the first thing will depend upon how the user opened the file.
If they used the Win32 API and did not specify overlapped I/O, then the
I/O Manager will serialize the operations on behalf of the original
user. If they used the Win32 API and specified overlapped I/O, but
themselves serialize the I/O internally, then the I/O would be
serialized. If they don’t serialize the I/O internally between two
threads then the application itself really has no idea in which order
the two operations were issued.

At the file system level, if the file was opened for cached I/O, the
operations are satisfied by copying data into the cache. Upon return,
the I/O is “done” in memory but not on disk. There is no guarantee as
to the order the data will be written. If the file was opened for
non-cached I/O but the file is compressed, NTFS will treat it as cached
I/O anyway (this is one reason why you will notice that database files
can’t be compressed - they can’t guarantee order of operations as is
required for transactional semantics).

So, let’s assume that the USER did everything write - file is opened for
overlapped I/O, non-cached, not compressed. I/O operations are directly
issued to the disk subsystem. Of course, a single user-level I/O might
be split into multiple I/O operations (if the allocation on disk is
fragmented). These I/O operation(s) are then send to the volume
manager. Again, the volume manager may split a single I/O operation up
into multiple I/O operations (mirroring, striping, or striping with
parity).

By the time this seemingly simple set of I/O operations reaches the SCSI
port layer there’s potentially little relationship between the original
(user) I/O and the actual (disk) I/O. Further, high-performance port
drivers often implement additional queuing algorithms (think of
simplistic algorithms like elevator scans, or more complex tag queuing
scans, or priority based real-time algorithms). Some port drivers
implement RAID features as well.

Both controllers and disks also add hardware (memory) caching. This can
(and typically does) again change the actual order in which things
occur.

Application programmers that believe the ordering of two arbitrary I/O
operations is in some way constrained are fooling themselves. Database
people (that is, the folks that implement SQL or Jet) understand that
nothing is certain until such time as the I/O is acknowledged from the
drive. They go to great lengths to disable features like disk (or
controller) caching because they need to know (for transactional
correctness) that I/O has in fact been committed to disk. The fastest
way to screw up a transactional system is to lie to it and claim blocks
are committed to disk when they in fact are not.

Regards,

Tony

Tony Mason

Consulting Partner

OSR Open Systems Resources, Inc.

http://www.osr.com

Looking forward to seeing you at the Next OSR File Systems Class October
18, 2004 in Silicon Valley!

From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com] On Behalf Of Jan Bottorff
Sent: Tuesday, November 02, 2004 2:45 AM
To: ntdev redirect
Subject: [ntdev] Ordering of I/O requests

I’m trying to decide if there is actually an “ordering” to I/O requests.
Say I have two threads on two processors and they both issue a disk
write in some known order on a single file handle. It seems like both
those requests will pass down the storage stack in parallel, and not get
serialized until they reach either the disk bus or possibly the SCSI
port driver target queue. As either thread can be interrupted by DPC or
ISR processing, it’s not know which request will actually happen first.
If I’m running multipathing hardware, they might even take different
routes to the drive, and get serialized there.

I care about this because I would like to be able to pipeline a bunch of
disk writes with overlapping headers and trailers, and assure they get
applied in the pipeline order. I don’t really want to wait for one to
complete before issuing the next one, which seems like the only way to
ASSURE an ordering. The end data on the disk will not be correct unless
the header of the second write is applied after the trailer of the first
write, and the header of the third write is applied after the trailer of
the second write.

I put on my user mode hat and think “of course the order the writes get
initially issued in will be preserved on the physical disk”, but I put
on my driver writer hat and say “what specifically will keep the writes
in the same order as they started in?”.

Anybody know the real answer?

Jan

Questions? First check the Kernel Driver FAQ at
http://www.osronline.com/article.cfm?id=256

You are currently subscribed to ntdev as: unknown lmsubst tag argument:
‘’
To unsubscribe send a blank email to xxxxx@lists.osr.com

OSR_Community_User · November 2, 2004, 10:08am

the only way to assure ordering is to wait for one request to complete
before starting the next one.

-p

From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com] On Behalf Of Jan Bottorff
Sent: Monday, November 01, 2004 11:45 PM
To: Windows System Software Devs Interest List
Subject: [ntdev] Ordering of I/O requests

I’m trying to decide if there is actually an “ordering” to I/O
requests. Say I have two threads on two processors and they both issue a
disk write in some known order on a single file handle. It seems like
both those requests will pass down the storage stack in parallel, and
not get serialized until they reach either the disk bus or possibly the
SCSI port driver target queue. As either thread can be interrupted by
DPC or ISR processing, it’s not know which request will actually happen
first. If I’m running multipathing hardware, they might even take
different routes to the drive, and get serialized there.

I care about this because I would like to be able to pipeline a
bunch of disk writes with overlapping headers and trailers, and assure
they get applied in the pipeline order. I don’t really want to wait for
one to complete before issuing the next one, which seems like the only
way to ASSURE an ordering. The end data on the disk will not be correct
unless the header of the second write is applied after the trailer of
the first write, and the header of the third write is applied after the
trailer of the second write.

I put on my user mode hat and think “of course the order the
writes get initially issued in will be preserved on the physical disk”,
but I put on my driver writer hat and say “what specifically will keep
the writes in the same order as they started in?”.

Anybody know the real answer?

Jan

Questions? First check the Kernel Driver FAQ at
http://www.osronline.com/article.cfm?id=256

You are currently subscribed to ntdev as: unknown lmsubst tag
argument: ‘’
To unsubscribe send a blank email to
xxxxx@lists.osr.com

OSR_Community_User · November 2, 2004, 10:18am

Watching order of completion isn’t even sufficient at the disk interface
level, let alone at user application level. Disks and controllers both
implement caching logic that might reorder the writes (and return
premature results) prior to actually being committed to disk. If an
application must know the order, it must be cognizant of these
distinctions and disable them or provide additional logic to ensure data
has been written through (ultimately, this becomes hardware dependent as
well.)

Regards,

Tony

Tony Mason

Consulting Partner

OSR Open Systems Resources, Inc.

http://www.osr.com

From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com] On Behalf Of Peter Wieland
Sent: Tuesday, November 02, 2004 10:06 AM
To: ntdev redirect
Subject: RE: [ntdev] Ordering of I/O requests

the only way to assure ordering is to wait for one request to complete
before starting the next one.

-p

From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com] On Behalf Of Jan Bottorff
Sent: Monday, November 01, 2004 11:45 PM
To: Windows System Software Devs Interest List
Subject: [ntdev] Ordering of I/O requests

I’m trying to decide if there is actually an “ordering” to I/O
requests. Say I have two threads on two processors and they both issue a
disk write in some known order on a single file handle. It seems like
both those requests will pass down the storage stack in parallel, and
not get serialized until they reach either the disk bus or possibly the
SCSI port driver target queue. As either thread can be interrupted by
DPC or ISR processing, it’s not know which request will actually happen
first. If I’m running multipathing hardware, they might even take
different routes to the drive, and get serialized there.

I care about this because I would like to be able to pipeline a
bunch of disk writes with overlapping headers and trailers, and assure
they get applied in the pipeline order. I don’t really want to wait for
one to complete before issuing the next one, which seems like the only
way to ASSURE an ordering. The end data on the disk will not be correct
unless the header of the second write is applied after the trailer of
the first write, and the header of the third write is applied after the
trailer of the second write.

I put on my user mode hat and think “of course the order the
writes get initially issued in will be preserved on the physical disk”,
but I put on my driver writer hat and say “what specifically will keep
the writes in the same order as they started in?”.

Anybody know the real answer?

Jan

Questions? First check the Kernel Driver FAQ at
http://www.osronline.com/article.cfm?id=256

You are currently subscribed to ntdev as: unknown lmsubst tag
argument: ‘’
To unsubscribe send a blank email to
xxxxx@lists.osr.com

Questions? First check the Kernel Driver FAQ at
http://www.osronline.com/article.cfm?id=256

You are currently subscribed to ntdev as: unknown lmsubst tag argument:
‘’
To unsubscribe send a blank email to xxxxx@lists.osr.com

Prokash_Sinha-1 · November 2, 2004, 12:13pm

Now again I’m lost, just out of curiosity, if a disk controller does reordering of writes and reads, and could not feed the upper interface layer with the most current data ( transaction symantics ) then I would assume it is nothing but a brick. So the question comes, when would it be really necessary to turnoff disk caching, assuming that the catching ( say at sector level ) is implemented correctly at the disk firmware level !!!

-pro

Lyndon_J_Clarke-2 · November 2, 2004, 12:22pm

Say you have concurrent read and write to same sector … now define most
current data!

“Programmers Society Prokash Sinha” wrote in message
news:xxxxx@ntdev…
> Now again I’m lost, just out of curiosity, if a disk controller does
> reordering of writes and reads, and could not feed the upper interface
> layer with the most current data ( transaction symantics ) then I would
> assume it is nothing but a brick. So the question comes, when would it be
> really necessary to turnoff disk caching, assuming that the catching ( say
> at sector level ) is implemented correctly at the disk firmware level !!!
>
> -pro
>

OSR_Community_User · November 2, 2004, 12:36pm

I have a very file systems centric view here - and 15 years ago I was
developing the transaction/journaling components of a journaling file
system, so I’ve been over this territory before.

The general rule is: nobody cares unless they explicitly ask. In other
words, if you don’t ask, the underlying system will assume that you
don’t care about the ordering of specific operations.

For a journaling file system, we have the same problem as a database.
In my personal example from so many years ago, we used an old value/new
value journal, which means that we stored the data BEFORE the change and
the data AFTER the change. We then would periodically write a block of
such change records out to disk.

There are ordering constraints here - we must ensure that pieces of the
log are committed (permanently recorded on disk) before the
corresponding changes to meta-data are written out to disk. Thus to
guarantee our transactional semantics, we needed to ensure that any
hardware level out-of-order caching was disabled. Otherwise, we
couldn’t guarantee correct recovery.

NTFS does exactly the same thing - it explicitly requests that
write-back caching be DISABLED in the disk controller and on the disk
drive itself (see IOCTL_DISK_SET_CACHE_INFORMATION and
IOCTL_DISK_SET_CACHE_SETTING for example, no doubt there are also other
mechanisms floating around through here).

If you want to implement caching, the only safe transparent way to do
this (from a single disk transactional perspective) is to guarantee no
reordering of operations. But databases where the log is on one disk
and the database on another will NOT be happy if they find out that data
they were told had committed to the log didn’t, while the updates (which
must now be aborted) were written to the 2nd disk drive. The only safe
way to do this is to disable caching on both drives, so that once data
has been acknowledged back, we know that it has been written out to
disk.

A quick search also turns up yet more information. For example
http://www.storagereview.com/guide2000/ref/hdd/if/scsi/protCQR.html
discusses tagged command queuing (and this DOES improve performance).
There is a wealth of information about this topic floating around. This
just demonstrates that systems DO reorder disks.

Regards,

Tony

Tony Mason
Consulting Partner
OSR Open Systems Resources, Inc.
http://www.osr.com

-----Original Message-----
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com] On Behalf Of Programmers Society
Prokash Sinha
Sent: Tuesday, November 02, 2004 12:12 PM
To: ntdev redirect
Subject: RE: [ntdev] Ordering of I/O requests

Now again I’m lost, just out of curiosity, if a disk controller does
reordering of writes and reads, and could not feed the upper interface
layer with the most current data ( transaction symantics ) then I would
assume it is nothing but a brick. So the question comes, when would it
be really necessary to turnoff disk caching, assuming that the catching
( say at sector level ) is implemented correctly at the disk firmware
level !!!

-pro

Questions? First check the Kernel Driver FAQ at
http://www.osronline.com/article.cfm?id=256

You are currently subscribed to ntdev as: xxxxx@osr.com
To unsubscribe send a blank email to xxxxx@lists.osr.com

Prokash_Sinha-1 · November 2, 2004, 12:40pm

The concurrent read and write can happens to any place ( memory, cache, disk cache). From the receiver’s point of view, whatever comes first. As an example, I can submit two transaction to my bank ( withdraw, and deposit > if an withdraw goes before deposit, I’m fined, but from the receiving end in this case the banking system, the serilization in time is more important, than anything in the read/write reordering at any level. If a write is withhold, and a read is allowed it is the consistency problem at that level, and read should get the cached data that is not yet committed. EVEN I DONT THINK THAT YOU COULD DO A CONCURRENT READ AND WRITE TO A SPECIFIC DATA ELEMENT ( BE IT THE SMALLEST ADDRESSABLE UNIT OR A SECTOR OR WHATEVER > WHEN YOU NEED DATA CONSISTENCY.

So still I’m not clear about this read / write reordering that could not be trusted, well of course, if implemented correctly !!!

-pro

Prokash_Sinha-1 · November 2, 2004, 12:58pm

Thanks Tony,

The first one you did send was very nice and I saved :).

Yes I agree what you are saying, but my point is very specific to single disk. The dual or more disk scenario you just gave is similar to MP caching consistency and that is a very very valid point … and I’m not sure how I’m going to point my gun to the read / write reordering or disk level caching !!!

I was partly involved in some higher than firmware level about read/write reordering, so that just go me into confusion.

Best Regards,
-pro

OSR_Community_User · November 2, 2004, 12:58pm

How do you implement it correctly if you rely upon two sectors of two
different disks? What is the inherent ordering of such operations?

Heck, the same problem arises with processors - what is the ordering of
writes between two different processors? Maybe you think that they are
well ordered, but in the real world that leads to performance
bottlenecks, so in fact the rules are generally relaxed and the order of
reads and writes are ordered for a given processors, but not between
processors. Let’s scale this up - we could have different processors,
executing different I/O operations to different disks located on
different controllers.

Sometimes it amazes me that any of this stuff works right, ever.

Regards,

Tony

Tony Mason
Consulting Partner
OSR Open Systems Resources, Inc.
http://www.osr.com

-----Original Message-----
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com] On Behalf Of Programmers Society
Prokash Sinha
Sent: Tuesday, November 02, 2004 12:39 PM
To: ntdev redirect
Subject: Re:[ntdev] Ordering of I/O requests

The concurrent read and write can happens to any place ( memory, cache,
disk cache). From the receiver’s point of view, whatever comes first. As
an example, I can submit two transaction to my bank ( withdraw, and
deposit > if an withdraw goes before deposit, I’m fined, but from the
receiving end in this case the banking system, the serilization in time
is more important, than anything in the read/write reordering at any
level. If a write is withhold, and a read is allowed it is the
consistency problem at that level, and read should get the cached data
that is not yet committed. EVEN I DONT THINK THAT YOU COULD DO A
CONCURRENT READ AND WRITE TO A SPECIFIC DATA ELEMENT ( BE IT THE
SMALLEST ADDRESSABLE UNIT OR A SECTOR OR WHATEVER > WHEN YOU NEED DATA
CONSISTENCY.

So still I’m not clear about this read / write reordering that could not
be trusted, well of course, if implemented correctly !!!

-pro

Questions? First check the Kernel Driver FAQ at
http://www.osronline.com/article.cfm?id=256

You are currently subscribed to ntdev as: xxxxx@osr.com
To unsubscribe send a blank email to xxxxx@lists.osr.com

OSR_Community_User · November 2, 2004, 1:17pm

Disk controllers that reorder writes when you have specified
WRITE_THROUGH and synchronously waited for a request to complete before
sending down another are buggy. Or they are lying so as to get a boost
in performance at the expense of correctness. You will see chkdsk
running on those machines. Caching in the controller is one thing but
not ordering writes is something else altogether, when WRITE_THROUGH is
supplied.

Actually NTFS doesn’t disable write back caching - because it assumes
ordering is never broken, it uses WRITE_THROUGH.

Ravi

-----Original Message-----
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com] On Behalf Of Tony Mason
Sent: Tuesday, November 02, 2004 9:35 AM
To: Windows System Software Devs Interest List
Subject: RE: [ntdev] Ordering of I/O requests

I have a very file systems centric view here - and 15 years ago I was
developing the transaction/journaling components of a journaling file
system, so I’ve been over this territory before.

The general rule is: nobody cares unless they explicitly ask. In other
words, if you don’t ask, the underlying system will assume that you
don’t care about the ordering of specific operations.

For a journaling file system, we have the same problem as a database.
In my personal example from so many years ago, we used an old value/new
value journal, which means that we stored the data BEFORE the change and
the data AFTER the change. We then would periodically write a block of
such change records out to disk.

There are ordering constraints here - we must ensure that pieces of the
log are committed (permanently recorded on disk) before the
corresponding changes to meta-data are written out to disk. Thus to
guarantee our transactional semantics, we needed to ensure that any
hardware level out-of-order caching was disabled. Otherwise, we
couldn’t guarantee correct recovery.

NTFS does exactly the same thing - it explicitly requests that
write-back caching be DISABLED in the disk controller and on the disk
drive itself (see IOCTL_DISK_SET_CACHE_INFORMATION and
IOCTL_DISK_SET_CACHE_SETTING for example, no doubt there are also other
mechanisms floating around through here).

If you want to implement caching, the only safe transparent way to do
this (from a single disk transactional perspective) is to guarantee no
reordering of operations. But databases where the log is on one disk
and the database on another will NOT be happy if they find out that data
they were told had committed to the log didn’t, while the updates (which
must now be aborted) were written to the 2nd disk drive. The only safe
way to do this is to disable caching on both drives, so that once data
has been acknowledged back, we know that it has been written out to
disk.

A quick search also turns up yet more information. For example
http://www.storagereview.com/guide2000/ref/hdd/if/scsi/protCQR.html
discusses tagged command queuing (and this DOES improve performance).
There is a wealth of information about this topic floating around. This
just demonstrates that systems DO reorder disks.

Regards,

Tony

Tony Mason
Consulting Partner
OSR Open Systems Resources, Inc.
http://www.osr.com

-----Original Message-----
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com] On Behalf Of Programmers Society
Prokash Sinha
Sent: Tuesday, November 02, 2004 12:12 PM
To: ntdev redirect
Subject: RE: [ntdev] Ordering of I/O requests

Now again I’m lost, just out of curiosity, if a disk controller does
reordering of writes and reads, and could not feed the upper interface
layer with the most current data ( transaction symantics ) then I would
assume it is nothing but a brick. So the question comes, when would it
be really necessary to turnoff disk caching, assuming that the catching
( say at sector level ) is implemented correctly at the disk firmware
level !!!

-pro

Questions? First check the Kernel Driver FAQ at
http://www.osronline.com/article.cfm?id=256

You are currently subscribed to ntdev as: xxxxx@osr.com To unsubscribe
send a blank email to xxxxx@lists.osr.com

Questions? First check the Kernel Driver FAQ at
http://www.osronline.com/article.cfm?id=256

You are currently subscribed to ntdev as: unknown lmsubst tag argument:
‘’
To unsubscribe send a blank email to xxxxx@lists.osr.com

OSR_Community_User · November 2, 2004, 1:44pm

This statement is STILL too strong. Here are two distinct cases that I
would consider to obey WRITE_THROUGH and yet still allow a disk
controller to reorder writes:

NTFS writes I/O operations in “clusters” that consist of one (or more)
disk sectors. A single cluster might involve I/O to disjoint regions on
the disk (sector sparing or some bizarre striping implementation).
There is *no* ordering constraint on the writes within that region.
Essentially, then, the “WRITE_THROUGH” request (which is nothing more
than a request to the disk and/or controller to disable write-back
caching for that given instance) merely says “tell me when the I/O is
really committed to disk”. Nothing within the operation requires that
the sectors be written in the correct order (I’m not sure how NTFS
handles this issue, but we used to compute a checksum over log records
to detect sector-write failures on replay).
Distinct I/O operations to distinct regions of the disk may be
interleaved. There is no “atomicity” or ordering with respect to two
different I/O operations to the same disk. Combining that with the
previous example, there’s no ordering relative to sector-level writes
split between two different I/O operations.

While Ravi’s point is correct - my comments about NTFS were overly
strong (think of it as disabling write-back caching on the data IT cares
about, rather than ALL data on the drive) the underlying point remains:
any journaling system needs to know that once its write to disk has been
acknowledged it will never go away. There is no other way to ensure
inter-disk operations remain consistent with one another. That
shouldn’t be an issue for NTFS (where, as I understand it the journal is
part of the NTFS file system) but is an issue if you store the journal
on a different disk drive (witness IBM’s AIX where JFS used a separate
logical volume for storing the journal for a file system example).

Of course, this does not equate to requiring that the data be “on disk”,
merely that it be persistent. A disk (or controller) with NVRAM can
provide blazingly fast performance by lying about such I/O operations -
but they guarantee the data will eventually be written back to disk.
That’s sufficient for our purposes.

Regards,

Tony

Tony Mason
Consulting Partner
OSR Open Systems Resources, Inc.
http://www.osr.com

-----Original Message-----
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com] On Behalf Of Ravisankar Pudipeddi
Sent: Tuesday, November 02, 2004 1:16 PM
To: ntdev redirect
Subject: RE: [ntdev] Ordering of I/O requests