\documentstyle[fullpage,10pt]{article}
\title{File System Tuning For a RAID Level 5 Disk Array}
\author{Greg Hudson}
\begin{document}
\maketitle

The allocation and layout policy of the Berkeley Fast File System
(FFS) assumes that the file system will be stored on a single disk.
Thus, the allocation and layout policy attempts to locate consecutive
file system blocks at rotationally optimal positions on a cylinder of
a cylinder group.

For high-speed, fault-tolerant systems, it may be preferrable to store
a file system on multiple disks, for instance in a RAID level-5 disk
array.  In such an array, a group of G+1 disks are used to store G
disk's worth of data, with the remaining disk data stored used for
parity bits.  The parity bits are organized into parity sectors spread
out across the disks.  Thus, up to G+1 reads or up to (G+1)/2 writes
can be performed in parallel.

The FFS layout policy will not yield good performance on a RAID disk
array when the processor is accessing only a single file at one time.
Because most of the file data will reside on a single cylinder group
on a single disk, one cannot exploit the parallelism of the disk
array.  Instead, it would be preferrable to spread out related data
among all of the disks.

So, as a first attempt at taking advantage of parallelism, the block
allocator should attempt to allocate a block on the next disk after
the disk containing the previous block.  In this way, sequential reads
and writes can access all the disks at one time.  (Under the Unix
programming interface, there are some difficulties with this approach,
since the read system call is a synchronous operation, but these
problems can be solved with read-ahead caching by the operating
system.)

While this scheme can achieve maximum throughput with all disks
transferring data at a time, it ignores seek time and rotation delay.
If blocks are allocated at random places on their disks, each block
transfer will be preceded by a seek and rotation, severely limiting
performance.  We can reduce the seek requirements by attempting to
allocate disk sectors in the same cylinder as previous blocks from the
same file (or on nearby cylinders if the cylinder is full); this does
nothing to reduce rotation delay, however.  To attack that problem, we
can take one of two avenues.  First, we can allocate more than one
block on each disk before moving on to the next disk.  This increases
the length of the sequential read necessary before one can exploit a
given level of parallelism, but it means waiting for rotation delay
less often.  Second, we can try to allocate disk blocks at consecutive
sectors on a cylinder (even though they are not consecutive blocks in
the file) and transfer multiple blocks at a time from each disk.  This
requires that the operating system be able to anticipate long
sequential reads well.  The above reasoning applies to writes equally
well as it does to reads.

In summary, the best block layout policy for a RAID disk array spreads
the blocks of a file among the different disks of the array, either by
moving from disk after each block or after several blocks.  Within
each disk, the allocator should attempt to allocate consecutive
sectors on the same cylinder or on nearby cylinders, to reduce the
time spent in seek or rotation delay.

\end{document}

