Daniel Phillips is fast becoming a major league kernel hacker.

This is an experimental attempt to optimize my previous early flush
patch by adding continuous disk bandwidth estimation. In spirit, the
new modifications are similar to Stephen Tweedie’s “sard” disk
monitoring patch, though it was only after implementing my own ideas
that I became aware of the overlap. On the other hand, what I have done
here is quite lightweight, on the order of 20 lines or so, and seems to
produce good results.

It is far from clear that this continuous bandwidth feedback from the IO
queue is the “right” approach. Alternatively, it would be quite easy to
provide an interface from userland to allow the administrator to provide
a one-time bandwidth estimate, perhaps derived from hddisk -t. On the
other hand, it would be just as easy to provide both an automatic
estimation and a manual override. One big advantage of making the
automatic method the default is that no tuning needs to be done in order
to get decent performance from a new install. Another potential
advantage is that bandwidth can change under different loads, so any
one-time estimate may prove to be sub-optimal.

The Patch
———

This is a patch set with 3 parts:

1) A lightly edited version of the early flush patch
2) Add-on bandwidth estimation
3) Add-on proc interface for bandwidth estimate and transfer rate
Each part depends on the ones before it and each results in a usable
system. I.e, to get the original early flush behavior, just omit the
second and third patches.

The second patch adds bandwidth estimation and this is where things get
interesting from the benchmarking point of view. At this point I
haven’t done any rigorous benchmarking and I can only guess at the
performance effects. On the other hand, by monitoring the bandwidth
estimate, I’ve learned some interesting things about how well we are
doing in terms of optimizing disk seeks (not spectacularly well) and I
have also noticed what appears to be a low-level problem in the disk
queue, causing short periods of unreasonably low block transfer rates on
my laptop.

To apply:

cd /usr/src/yourtree
patch -p0 <thispatch
To reverse, you must separate the patch into its 3 parts and
reverse in reverse order. Sorry. I will try to avoid placing multiple
patches in one file in the future. 😉

For example:

<edit this file into 3 parts: look for early.flush.1/2/3>
patch -p0 <early.flush.3 –reverse
patch -p0 <early.flush.2 –reverse
patch -p0 <early.flush.1 –reverse

Method
——

As expected, estimating disk bandwidth is a little tricky. There
are several problems.

– There could be several disks on the downstream end
– Some of them might not even be disks: ramdisk, flash, nbd.
– Need to know when transfers are running back to back
– Seeking can make the transfer rate highly variable

The way I decided to go at it is by considering 2 types of sample
periods: a) sample periods with continuous activity and b) sample
periods with some idle time. Sample periods that include idle time
only cause the bandwidth estimate to increase; those with continuous
activity can cause the bandwidth estimate to increase or decrease.

The bandwidth samples thus obtained tend to fluctuate rapidly. To make
them more useful, I filter them. The line:

bandwidth_sectors = (bandwidth_sectors*3 + bandwidth_sample)/4;

implements a simple low-pass filter using only shifts and adds.
In some respects, what has been implemented is a feedback loop. When
early flushing is the only active disk IO process, the estimate of disk
bandwidth will tend to be continuously improved. This happens because
the flush will try to write keep the queue full to a level somewhat
greater (150%) of the bandwidth estimation, allowing the estimate to
increase by 50% on each poll interval. When the queue has been properly
saturated with transfers the estimate can decrease as well. Hence the
flushing behavior causes migration towards a position of improved
knowledge about the underlying hardware.

Observations

————

It turns out that measured bandwidth tends to fluctuate a great deal –
by a factor of 20 to 40. This reflects the difference between
sequential transfers and those require large amounts of seeking. For
example, an IDE disk may be capable of transferring a 4K block in 250
microseconds, but if the blocks are all on separate tracks the actual
transfer time may be 5 milliseconds or so, somewhere in the range of the
disk’s average access time. This gives a factor of 20 bandwidth
difference depending on access patterns. I observed this in practice.

Interestingly, the use of smaller blocks gives an even wider variance.
This is because of the larger number of seeks possible for a given
amount of data. I see 2-3 times as much variance with 1K blocks as with
4K blocks. This is an important reason why larger block sizes are good
for throughput. (However, note that the improvement could be illusory if
the data items being transfered are significantly smaller than the block
size.)

Peak transfer rates don’t vary much with block size and remain near the
raw transfer rate of the disk as measured by hdparm -t. This is
encouraging as far correctness of the measuring method goes.

A Level Disk Transfer Anomaly

—————————–

I have consistently observed a troubling anomaly in low level disk
transfer throughput. On rare occasions, the low level transfer rate
seems to drop to ~10 blocks/second on my laptop. During these
periods of slow transfers, the IO queue is typically backed up by a few
tens of sectors. It is hard to imagine any hardware cause for this. I
do not think that this measurement is due to a flaw in my method of
collecting statistics, nonetheless, it is possible. If I have made no
mistake, then there is indeed something odd going on down at the lowest
levels of disk access.

Application to Early Flushing

—————————–

The early flush algorithm essentially tries to use disk bandwidth that
would otherwise be unused. When it detects a period of disk inactivity
it tries to write out as many old buffers as it can, without loading up
the disk queue so much that some higher priority user of the disk
bandwidth, such as the swapper, would be delayed too much. In other
words, it wants to submit enough sectors for io to keep the disk busy
continuously, and not a lot more than that. To do this accurately it
needs to know the disk bandwidth.

As discussed above, disk bandwidth is not a simple number, it depends on
what the disk is actually doing. It’s possible that keeping a
continuous estimate of disk throughput as I do in this patch is better
than assuming some fixed number. There are dangers too. Suppose for
example that a period of coherent IO results in a bandwidth estimate
close to the raw transfer rate of the drive, then activity ceases and
the early flush uses that estimate to begin a flush episode.
Unfortunately, the blocks being flushed turn out to be highly
fragmented, and so 20 times more blocks are scheduled for IO than would
be ideal. If there is no new demand for disk bandwidth during the
period of the flush episode, no harm is done, because the estimate will
be improved over the next few sample periods. But if there is sudden
demand, the higher priority user will be delayed by the low priority
blocks in the queue. Hopefully, such a unfortunate combination of
factors is a rare event, nonetheless I am giving consideration to how
the possible bad effects could be ameliorated.

I tested this patch just once on a live system, for a reality check. In
that test I saw a 5% improvement in kernel compile speed:

Command

time make clean bzImage modules

Vanila kernel

real 11m58.176s
user 10m37.840s
sys 0m28.740s

With early flush + bandwidth sensing

real 11m21.227s
user 8m38.160s
sys 0m48.460s

More testing needs to be done to see if this is reproducible.

Other applications

——————

There are other areas in the kernel that could benefit from using disk
bandwidth and queue size input. Once example is page laundering.

Currently, page laundering relies on a memory pressure and clean page
statistics to decide how many pages to submit for writing.
Unfortunately, under some loads, memory pressure is continuous, and that
statistic carries little useful information. Similarly, some loads use
dirty pages as fast as they are cleaned, so the clean page statistic is
not reliable either.

Alternatively, page_launder could sense the length of the io queue and
use the disk bandwidth statistic to guide its decisions on how many
pages to write out. It is counterproductive to load up the io queue
with too many dirty page writeouts, if only because a sudden relaxation
of the load can leave the system busily writing out pages when it should
be reading, e.g., swapping a gui program back in that was swapped out
under load. So instead, page_launder can write out enough pages to let
the elevator work efficiently and stop there.

Other applications will no likely be found. Even the possibilities for
opportunistic IO have hardly been mined out.

Possible Improvements

———————

The current patch is most probably sub-optimal. For one thing, it lumps
reads and writes together in one bandwidth statistic. For another, the
full/partial sample distinction is overly crude. Something along the
lines of what Stephen Tweedie does in his sard patch with idle time
measurement would likely be superior.

>From the enterprise-computing point of view, the major improvement that
needs to be made is in separate analysis of multiple block devices. This
per-device information needs to be propagated back into kernel
mechanisms such as bdflush, page_launder and the swapper. Needless to
say, this is 2.5 material.

Proc Interface

————–

In the third patch of this set I create a simple proc interface to
expose the bandwidth estimation, and another simple statistic, current
transfer rate, to user space. This is used as follows:

daniel@starship# cat /proc/bandwidth
1720 0
The first number is the current bandwidth estimate and the second is the
current transfer rate. Note that the bandwidth estimate is updated only
when there is disk activity, and it can vary a great deal as described
above. Do not be surprised to see a strangely low bandwidth estimate
when the system is sitting idle – it can easily result from a final
burst of disk access that is extremely fragmented.

I do not pretend that the this proc interface is correct in any way,
however is should be fun to play with.