.\" Hey, Emacs!  Edit this file in -*- nroff-fill -*- mode!
.\"
.\" $Id: paper.mm,v 1.5 1998/08/31 02:35:41 grog Exp grog $
.nr std 10
.de Ds
.br
.nr Ds*s \\n(.s
.nr Ds*v \\n(.v
.nr Ds*i \\n(.i
.nr Ds*j \\n(.j
.nr Ds*ft \\n(.f
.ie \\n(.$>3 .nr Ds*skip \\$4
.el .nr Ds*skip 1
.sp \\n[Ds*skip]
.ie \\n(.$>2 .ft \\$3   \" set font
.el .ft CW
.ie \\n(.$>1 .in +\\$2  \" set indent
.el .in +.5m
.ie \\n(.$>0 \{\
.       ps \\$1z
.       vs \\$1
.\}
.el \{\
.       ps 9z
.       vs 9
.\}
.nf
.na
..
.de Dx
.br
.ne 5
.Ds 8
..
.de De
.\" Size: \\n[.s] Indent: \\n[.i] Vertical spacing \\n[.v]u
.\" Font: \\n[.f] Fill mode: \\n[.j] Parameter count: \\n(.$
.br
.\"
.fi
.ad \\n[Ds*j]
.ft \\n[Ds*ft]
.ps \\n[Ds*s]
.in \\n[Ds*i]u
.vs \\n[Ds*v]u
.sp \\n[Ds*skip]
..
.nr lix*tb-nr 0 1
.de TB
.lix@print-line tb Lt \\n+[lix*tb-nr] "\\$1" "\\$2" "\\$3" "\\$4"
..
.de Tn
.tm ><PAGENO:\.ds \\$1 \\n[lix*tb-nr]
.tm ><PAGENO:\.ds \\$1-page \\n%
..
.de Figure-heading\" just put a heading into the Tables list
.ps \n[std]
.vs 12p
.ce
\fBFigure \\n+[lix*tb-nr]: \\$1\fP
.sp
..
.de Ls
.nr Pi 5
.ie "\\$1"B" .Blist
.el .LB \\n(Pi 0 0 1 \\$1
..
.de Blist
.LB 16p 0 0 0 \s+1\(bu\s0
..
.de Le
.LE
.P
..
.de H2
.br
.ne 8
.sp 1.5v
.vs 14p
\s+2\fB\\$1\fR\\s0
.if n \{\
.br
.nr XX \w@\\$1@/24
\l'\\n(XX'
.\}
.br
.vs
.sp 1
..
.de H3
.br
.sp 1
.ne 4
\s+1\fB\\$1\fR\\s0
.ie n \{\
.br
.nr XX \w@\\$1@/24
\l'\\n(XX'
.sp
.\}
.el .sp .5v
..
.\" End of macro definitions.  Let's get started.
.so xref.mm
.ce 7
.nf
.na
.vs 17p
.ps 14
The Vinum Volume Manager
.P
.vs 14p
.ps 12
Greg Lehey
\fINan Yang Computer Services Ltd.\fP\|
\f(CWgrog@lemis.com\fP
.fi
.ad
.ps 10
.vs 12p
.sp 3
.in +.5i
.ll -.5i
.ce
\fIABSTRACT\fP\|
.P
The \fIVinum Volume Manager\fP is a block device driver which implements virtual
disk drives.  It isolates disk hardware from the block device interface and maps
data in ways which result in an increase in flexibility, performance and
reliability compared to the traditional slice view of disk storage.  Vinum
implements the RAID-0, RAID-1 and RAID-5 models, both individually and in
combination.
.in
.ll
.ps 10
.nr @ps 12\" Footnote fonts are derived from @ps
.vs 12p
.sp 2v
.2C
.nr pg*column-sep .25i
.nr pg*column-size 3.125i
.H2 Introduction
Disk hardware is evolving rapidly, and the current UNIX disk abstraction is
inadequate for a number of modern applications.  In particular, file systems
must be stored on a single disk partition, and there is no kernel support for
redundant data storage.  In addition, the direct relationship between disk
volumes and their location on disk make it generally impossible to enlarge a
disk volume once it has been created.  Performance can often be limited by the
maximum data rate which can be achieved with the disk hardware.
.P
The largest modern disks store only about 50 GB, but large installations, in
particular web sites, routinely have more than a terabyte of disk storage, and
it is not uncommon to see disk storage of several hundred gigabytes even on PCs.
Storage-intensive applications such as Internet World-Wide Web and FTP servers
have accelerated the demand for high-volume, reliable storage systems which
deliver high performance in a heavily concurrent environment.
.H2 "The problems"
Various solutions to these problems have been proposed and implemented:
.H3 "Disks are too small"
The \fIufs\fP\| file system can theoretically span more than a petabyte
(2\u\s-450\s0\d or 10\u\s-415\s0\d bytes) of storage, but no current disk drive
comes close to this size.  Although the size problem is not as acute as it was
ten years ago, there is a simple solution: the disk driver can create an
abstract device which stores its data on a number of disks.  A number of such
implementations exist, though none appear to have become mainstream.
.H3 "Access bottlenecks"
Modern systems frequently need to access data in a highly concurrent manner.
For example, the FTP server \fIwcarchive.cdrom.com\fP\| maintains up to 3,600
concurrent \fIFTP\fP\| sessions and has a 100 Mbit/s connection to the outside
world, corresponding to about 12 MB/s.
.P
Current disk drives can transfer data sequentially at up to 30 MB/s, but this
value is of little importance in an environment where many independent processes
access a drive, where they may achieve only a fraction of these values.  In such
cases it's more interesting to view the problem from the viewpoint of the disk
subsystem: the important parameter is the load that a transfer places on the
subsystem, in other words the time for which a transfer occupies the drives
involved in the transfer.
.P
In any disk transfer, the drive must first position the heads, wait for the
first sector to pass under the read head, and then perform the transfer.  These
actions can be considered to be atomic: it doesn't make any sense to interrupt
them.
.P
.Pn latency
Consider a typical transfer of about 10 kB: the current generation of
high-performance disks can position the heads in an average of 6 ms.  The
fastest drives spin at 10,000 rpm, so the average rotational latency (half a
revolution) is 3 ms.  At 30 MB/s, the transfer itself takes about 350 µs, almost
nothing compared to the positioning time.  In such a case, the effective
transfer rate drops to a little over 1 MB/s and is clearly highly dependent on
the transfer size.
.P
The traditional and obvious solution to this bottleneck is ``more spindles'':
rather than using one large disk, it uses several smaller disks with the same
aggregate storage space.  Each disk is capable of positioning and transferring
independently, so the effective throughput increases by a factor close to the
number of disks used.
.P
The exact throughput improvement is, of course, smaller than the number of disks
involved: although each drive is capable of transferring in parallel, there is
no way to ensure that the requests are evenly distributed across the drives.
Inevitably the load on one drive will be higher than on another.
.P
The evenness of the load on the disks is strongly dependent on the way the data
is shared across the drives.  In the following discussion, it's convenient to
think of the disk storage as a large number of data sectors which are
addressable by number, rather like the pages in a book.  The most obvious method
is to divide the virtual disk into groups of consecutive sectors the size of the
individual physical disks and store them in this manner, rather like taking a
large book and tearing it into smaller sections.  This method is called
\fIconcatenation\fP\| and has the advantage that the disks do not need to have
any specific size relationships.  It works well when the access to the virtual
disk is spread evenly about its address space.  When access is concentrated on a
smaller area, the improvement is less marked.  Figure \*[concat] illustrates the
sequence in which storage units are allocated in a concatenated organization.
.PS
h = .15i
dh = .01i
dw = .4i
down
[
        [
                boxht = h; boxwid = dw
.\" 
move right .5i; down
          A:    box dotted ht h "\f(CW0\fP"
          B:    box dotted ht h "\f(CW1\fP"
          C:    box dotted ht h "\f(CW2\fP"
          D:    box dotted ht h "\f(CW3\fP"
          E:    box dotted ht h "\f(CW4\fP"
          F:    box dotted ht h "\f(CW5\fP"
                box ht h * 6 at C.s

          A1:   box dotted at A+(dw*1.6,0) ht h "\f(CW6\fP"
          B1:    box dotted ht h "\f(CW7\fP"
          C1:    box dotted ht h "\f(CW8\fP"
          D1:    box dotted ht h "\f(CW9\fP"
                box ht h * 4 at C1.n

          A2:   box dotted at A1+(dw*1.6,0) "\f(CW10\fP"
          F2:    box dotted ht h "\f(CW11\fP"
                box ht h * 2 at A2.s

          A3:   box dotted at A2+(dw*1.6,0) ht h "\f(CW12\fP"
          B3:    box dotted ht h "\f(CW13\fP"
          C3:    box dotted ht h "\f(CW14\fP"
          D3:    box dotted ht h "\f(CW15\fP"
          E3:    box dotted ht h "\f(CW16\fP"
          F3:    box dotted ht h "\f(CW17\fP"
                box ht h * 6 at C3.s

.\" "Offset" at ORIG.n+(0,.1i)
"Disk 1" at A.n+(0,.1i)
"Disk 2" at A1.n+(0,.1i)
"Disk 3" at A2.n+(0,.1i)
"Disk 4" at A3.n+(0,.1i)
              ]
]
.PE
.ce
.Figure-heading "Concatenated organization"
.Tn concat
.P
An alternative mapping is to divide the address space into smaller, even-sized
components and store them sequentially on different devices.  For example, the
first 256 sectors may be stored on the first disk, the next 256 sectors on the
next disk and so on.  After filling the last disk, the process repeats until the
disks are full.  This mapping is called \fIstriping\fP or RAID-0, though the
latter term is somewhat misleading: it provides no redundancy.  Striping
requires somewhat more effort to locate the data, and it can cause additional
I/O load where a transfer is spread over multiple disks, but it can also provide
a more constant load across the disks.  Figure \*[striped] illustrates the
sequence in which storage units are allocated in a striped organization.
.PS
h = .15i
dh = .01i
dw = .4i
down
[
        [
                boxht = h; boxwid = dw

move right .5i; down
          A:    box ht h "\f(CW0\fP"
          B:    box ht h "\f(CW4\fP"
          C:    box ht h "\f(CW8\fP"
          D:    box ht h "\f(CW12\fP"
          E:    box ht h "\f(CW16\fP"
          F:    box ht h "\f(CW20\fP"

          A1:   box at A+(dw*1.6,0) ht h "\f(CW1\fP"
          B1:    box ht h "\f(CW5\fP"
          C1:    box ht h "\f(CW9\fP"
          D1:    box ht h "\f(CW13\fP"
          E1:    box ht h "\f(CW17\fP"
          F1:    box ht h "\f(CW21\fP"

          A2:   box at A1+(dw*1.6,0) ht h "\f(CW2\fP"
          B2:    box ht h "\f(CW6\fP"
          C2:    box ht h "\f(CW10\fP"
          D2:    box ht h "\f(CW14\fP"
          E2:    box ht h "\f(CW18\fP"
          F2:    box ht h "\f(CW22\fP"

          A3:   box at A2+(dw*1.6,0) ht h "\f(CW3\fP"
          B3:    box ht h "\f(CW7\fP"
          C3:    box ht h "\f(CW11\fP"
          D3:    box ht h "\f(CW15\fP"
          E3:    box ht h "\f(CW19\fP"
          F3:    box ht h "\f(CW23\fP"

.\" "Offset" at ORIG.n+(0,.1i)
"Disk 1" at A.n+(0,.1i)
"Disk 2" at A1.n+(0,.1i)
"Disk 3" at A2.n+(0,.1i)
"Disk 4" at A3.n+(0,.1i)

               ]
]
.PE
.Figure-heading "Striped organization"
.Tn striped
.H3 "Data integrity"
The final problem with current disks is that they are unreliable.  Although disk
drive reliability has increased tremendously over the last few years, of all the
core components of a server they are still the most likely to fail.  When they
do, the results can be catastrophic: replacing a failed disk drive and restoring
data to it can take days.
.P
The traditional way to approach this problem has been \fImirroring\fP, keeping
two copies of the data on different physical hardware.  Since the advent of the
RAID levels, this technique has also been called \fIRAID level 1\fP\| or
\fIRAID-1\fP.  Any write to the volume writes to both locations; a read can be
satisfied from either, so if one drive fails, the data is still available on the
other drive.
.P
Mirroring has two problems:
.Ls B
.LI
The price.  It requires twice as much disk storage as a non-redundant solution.
.LI
The performance impact.  Writes must be performed to both drives, so they take
up twice the bandwidth of a non-mirrored volume.  Reads do not suffer from a
performance penalty: it even looks as if they are faster.  This issue will be
discussed in the ``Performance issues'' section.
.LE
.P
An alternative solution is \fIparity\fP, implemented in the RAID levels 2, 3, 4
and 5.  Of these, RAID-5 is the most interesting.  As implemented in Vinum, it
is a variant on a striped organization which dedicates one block of each stripe
to parity of the other blocks.  In RAID-5, the location of this parity block
changes from one stripe to the next.  Figure \*[raid-organization] shows the
RAID-5 organization.  The numbers in the data blocks indicate the relative block
numbers.
.PS
h = .15i
dh = .01i
dw = .4i
down
[
        [
                boxht = h; boxwid = dw

.\"     ORIG:   box invis "\f(CW0\fP"
.\"             box invis "\f(CW1\fP"
.\"             box invis "\f(CW2\fP"
.\"             box invis "\f(CW3\fP"
.\"             box invis "\f(CW4\fP"
.\"             box invis "\f(CW5\fP"
.\" 
.\"
move right .5i; down
          A:    box ht h "\f(CW0\fP"
          B:    box ht h "\f(CW3\fP"
          C:    box ht h "\f(CW6\fP"
          D:    box ht h "Parity" filled 0.2
          E:    box ht h "\f(CW12\fP"
          F:    box ht h "\f(CW15\fP"

          A1:   box at A+(dw*1.6,0) ht h "\f(CW1\fP"
          B1:    box ht h "\f(CW4\fP"
          C1:    box ht h "Parity" filled 0.2
          D1:    box ht h "\f(CW9\fP"
          E1:    box ht h "\f(CW13\fP"
          F1:    box ht h "\f(CW16\fP"

          A2:   box at A1+(dw*1.6,0) ht h "\f(CW2\fP"
          B2:    box ht h "Parity" filled 0.2
          C2:    box ht h "\f(CW7\fP"
          D2:    box ht h "\f(CW10\fP"
          E2:    box ht h "\f(CW14\fP"
          F2:    box ht h "Parity" filled 0.2

          A3:   box at A2+(dw*1.6,0) ht h "Parity" filled 0.2
          B3:    box ht h "\f(CW5\fP"
          C3:    box ht h "\f(CW8\fP"
          D3:    box ht h "\f(CW11\fP"
          E3:    box ht h "Parity" filled 0.2
          F3:    box ht h "\f(CW17\fP"

.\" "Offset" at ORIG.n+(0,.1i)
"Disk 1" at A.n+(0,.1i)
"Disk 2" at A1.n+(0,.1i)
"Disk 3" at A2.n+(0,.1i)
"Disk 4" at A3.n+(0,.1i)

               ]
]
.PE
.Figure-heading "RAID-5 organization"
.Tn raid-organization
.P
Compared to mirroring, RAID-5 has the advantage of requiring significantly less
storage space.  Read access is similar to that of striped organizations, but
write access is significantly slower, approximately 25% of the read performance.
If one drive fails, the array can continue to operate in degraded mode: a read
from one of the remaining accessible drives continues normally, but a read from
the failed drive is recalculated from the corresponding block from all the
remaining drives.
.H2 "Current implementations"
The problems of size, performance and reliability have solutions that are only
partially compatible.  In particular, redundant data storage and performance
improvements require different solutions and affect each other negatively.
.P
The current trend is to realize such systems in \fIdisk array\fP hardware, which
looks to the host system like a very large disk.  Disk arrays have a number of
advantages:
.Ls B
.LI
They are portable.  Since they have a standard interface, usually SCSI, but
increasingly also IDE, they can be installed on almost any system without kernel
modifications.
.LI
They have the potential to offer impressive performance: they offload the
calculations (in particular, the parity calculations for RAID-5) to the array,
and in the case of replicated data, the aggregate transfer rate to the array is
less than it would be to local disks.  Striping (``RAID-0'') and RAID-5
organizations also spread the load more evenly over the physical disks, thus
improving performance.  Nevertheless, an array is typically connected via a
single SCSI connection, which can be a bottleneck, and some implementations show
surprisingly poor performance which cannot be explained by the hardware
configuration.  Installing a disk array does not guarantee better performance.
.LI
They are reliable.  A good disk array offers a large number of features designed
to enhance reliability, including enhanced cooling, hot-plugging (the ability to
replace a drive while the array is running) and automatic failure recovery.
.Le
On the other hand, disk arrays are relatively expensive and not particularly
flexible.  An alternative is a software-based \fIvolume manager\fP\| which
performs similar functions in software.  A number of these systems exist,
notably the VERITAS\(rg volume manager [Veritas], Solaris \fIDiskSuite\fP\|
[Solstice], IBM's \fILogical Volume Facility\fP\| [IBM] and SCO's \fIVirtual
Disk Manager\fP\| [SCO].  An implementation of RAID software is also available
for Linux [Linux].
.H3 "Vinum"
\fIVinum\fP\| is an open source [OpenSource] volume manager implemented under
FreeBSD [FreeBSD].  It was inspired by the VERITAS\(rg volume manager and
implements many of the concepts of VERITAS\(rg.  Its key features are:
.Ls B
.LI
Vinum implements RAID-0 (striping), RAID-1 (mirroring) and RAID-5 (rotated
block-interleaved parity).  In RAID-5, a group of disks are protected against
the failure of any one disk by an additional disk with block checksums of the
other disks.\*F
.FS
\s-2The RAID-5 functionality is currently available under license from Cybernet,
Inc. [Cybernet].  It will be released as open source at a later date.\s0
.FE
.LI
Drive layouts can be combined to increase robustness, including striped mirrors
(so-called ``RAID-10'').
.LI
Vinum implements only those features which appear useful.  Some commercial
volume managers appear to have been implemented with the goal of maximizing the
size of the spec sheet.  Vinum does not implement ``ballast'' features such as
RAID-4.  It would have been trivial to do so, but the only effect would have
been to further confuse an already confusing topic.
.LI
Volume managers initially emphasized reliability and performance rather than
ease of use.  The results are frequently down time due to misconfiguration, with
consequent reluctance on the part of operational personnel to attempt to use the
more unusual features of the product.  Vinum attempts to provide an
easier-to-use non-GUI interface.
.Le
.H2 "How Vinum addresses the Three Problems"
As mentioned above, Vinum addresses three main deficiencies of traditional disk
hardware.  This section examines them in more detail.
.H3 "Vinum objects"
In order to address these problems, vinum implements a four-level hierarchy of
objects:
.Ls B
.LI
The most visible object is the virtual disk, called a \fIvolume\fP.  Volumes
have essentially the same properties as a UNIX disk drive, though there are some
minor differences.  They have no size limitations.
.LI
Volumes are composed of \fIplexes\fP, each of which represent the total address
space of a volume.  This level in the hierarchy thus provides redundancy.
.LI
Since Vinum exists within the UNIX disk storage framework, it would be possible
to use UNIX partitions as the building block for multi-disk plexes, but in fact
this turns out to be too inflexible: UNIX disks can have only a limited number
of partitions.  Instead, Vinum subdivides a single UNIX partition (the
\fIdrive\fP\|) into contiguous areas called \fIsubdisks\fP, which it uses as
building blocks for plexes.
.LI
Subdisks reside on Vinum \fIdrives\fP, currently UNIX partitions.  Vinum drives
can contain any number of subdisks.  With the exception of a small area at the
beginning of the drive, which is used for storing configuration and state
information, the entire drive is available for data storage.
.Le
The following sections describe the way these objects provide the functionality
required of Vinum.
.H3 "Volume size considerations"
Plexes can include multiple subdisks spread over all drives in the Vinum
configuration.  As a result, the size of an individual drive does not limit the
size of a plex, and thus of a volume.
.H3 "Redundant data storage"
Vinum provides both mirroring and RAID-5.  It implements mirroring by attaching
multiple plexes to a volume.  Each plex is a representation of the data in a
volume.  A volume may contain between one and eight plexes.
.P
Although a plex represents the complete data of a volume, it is possible for
parts of the representation to be physically missing, either by design (by not
defining a subdisk for parts of the plex) or by accident (as a result of the
failure of a drive).  As long as at least one plex can provide the data for the
complete address range of the volume, the volume is fully functional.
.P
From an implementation standpoint, it is not practical to represent a RAID-5
organization as a collection of plexes.  This issue is discussed below.
.H3 "Performance issues"
By spreading data across multiple disks, Vinum can deliver much higher
performance than a single disk.  This issue will be discussed in more detail below.
.H3 "RAID-5"
Conceptually, RAID-5 is used for redundancy, but in fact the implementation is a
kind of striping.  This poses problems for the implementation of Vinum: should
it be a kind of plex or a kind of volume?  It would have been possible to
implement it either way, but it proved to be simpler to implement RAID-5 as a
plex type.  This means that there are two different ways of ensuring data
redundancy: either have more than one plex in a volume, or have a single RAID-5
plex.  These methods can be combined.
.H3 "Which plex organization?"
Vinum implements only that subset of RAID organizations which make sense in the
framework of the implementation.  It would have been possible to implement all
RAID levels, but there was no reason to do so.  Each of the chosen organizations
has unique advantages:
.Ls B
.LI
Concatenated plexes are the most flexible: they can contain any number of
subdisks, and the subdisks may be of different length.  The plex may be extended
by adding additional subdisks.  They require less CPU time than striped or
RAID-5 plexes, though the difference in CPU overhead from striped plexes is not
measurable.  On the other hand, they are most susceptible to ``hot spots'',
where one disk is very active and others are idle.
.LI
The greatest advantage of striped (RAID-0) plexes is that they reduce hot spots:
by choosing an optimum sized stripe (empirically determined to be in the order
of 256 kB), the load on the component drives can be made more even.  The
disadvantages of this approach are (fractionally) more complex code and
restrictions on subdisks: they must be all the same size, and extending a plex
by adding new subdisks is so complicated that Vinum currently does not implement
it.  Vinum imposes an additional, trivial restriction: a striped plex must have
at least two subdisks, since otherwise it is indistinguishable from a
concatenated plex.
.LI
RAID-5 plexes are effectively an extension of striped plexes.  Compared to
striped plexes, they offer the advantage of fault tolerance, but the
disadvantages of higher storage cost and significantly higher overhead,
particularly for writes.  The code is an order of magnitude more complex than
for concatenated and striped plexes.  Like striped plexes, RAID-5 plexes must
have equal-sized subdisks and cannot be extended.  Vinum enforces a minimum of
three subdisks for a RAID-5 plex, since any smaller number would not make any
sense.
.Le
These are not the only possible organizations.  In addition, the following could
have been implemented:
.Ls B
.LI
RAID-4, which differs from RAID-5 only by the fact that all parity data is
stored on a specific disk.  This simplifies the algorithms somewhat at the
expense of drive utilization: the activity on the parity disk is a direct
function of the read to write ratio.  Since Vinum implements RAID-5, RAID-4's
only advantage is nullified.
.LI
RAID-3, effectively an implementation of RAID-4 with a stripe size of one byte.
Each transfer requires reading each disk (with the exception of the parity disk
for reads).  Without spindle synchronization (where the corresponding sectors
pass the heads of each drive at the same time), RAID-3 would be very inefficient.
In a multiple-access system, it also causes high latency.
.P
An argument for RAID-3 does exist where a single process requires very high data
rates.  With spindle synchronization, this would be a potentially useful
addition to Vinum.
.LI
RAID-2, which uses two subdisks to store a Hamming code, and which otherwise
resembles RAID-3.  Compared to RAID-3, it offers a lower data density, higher
CPU usage and no compensating advantages.
.Le
In addition, RAID-5 can be interpreted in two different ways: the data can be
striped, as in the Vinum implementation, or it can be written serially,
exhausting the address space of one subdisk before starting on the other,
effectively a modified concatenated organization.  There is no recognizable
advantage to this approach, since it does not provide any of the other
advantages of concatenation.
.H2 "Some examples"
Vinum maintains a \fIconfiguration database\fP\| which describes the objects
known to an individual system.  Initially, the user creates the configuration
database from one or more configuration files with the aid of the
\fIvinum(8)\fP\| utility program.  Vinum stores a copy of its configuration
database on each drive under its control.  This database is updated on each
state change, so that a restart accurately restores the state of each Vinum
object.
.H3 "The configuration file"
The configuration file describes individual Vinum objects.  The definition of a
simple volume might be:
.Dx
drive a device /dev/da3h
volume myvol
  plex org concat
    sd length 512m drive a
.De
This file describes a four Vinum objects:
.Ls B
.LI
The \f(CWdrive\fP line describes a disk partition (\fIdrive\fP\|) and its
location relative to the underlying hardware.  It is given the symbolic name
\fIa\fP.  This separation of the symbolic names from the device names allows
disks to be moved from one location to another without confusion.
.LI
The \f(CWvolume\fP line describes a volume.  The only required attribute is the
name, in this case \f(CWmyvol\fP.
.LI
The \f(CWplex\fP line defines a plex.  The only required parameter is the
organization, in this case \f(CWconcat\fP.  No name is necessary: the system
automatically generates a name from the volume name by adding the suffix
\&\f(CW.p\f(BIx\fR, where \f(BIx\fP\| is the number of the plex in the volume.
Thus this plex will be called \fImyvol.p0\fP.
.LI
The \f(CWsd\fP line describes a subdisk.  The minimum specifications are the
name of a drive on which to store it, and the length of the subdisk.  As with
plexes, no name is necessary: the system automatically assigns names derived
from the plex name by adding the suffix \f(CW.s\f(BIx\fR, where \f(BIx\fP\| is
the number of the subdisk in the plex.  Thus Vinum gives this subdisk the name
\fImyvol.p0.s0\fP
.Le
.P
This particular volume has no specific advantage over a conventional disk
partition.  It contains a single plex, so it is not redundant.  The plex
contains a single subdisk, so there is no difference in storage allocation from
a conventional disk partition.  The following sections illustrate various more
interesting configurations.
.H3 "Increased resilience: mirroring"
The resilience of a volume can be increased either by mirroring or by using
RAID-5 plexes.  When laying out a mirrored volume, it is important to ensure
that the subdisks of each plex are on different drives, so that a drive failure
will not take down both plexes.  The following configuration mirrors a volume:
.Dx
drive b device /dev/da4h
volume mirror
  plex org concat
    sd length 512m drive a
  plex org concat
    sd length 512m drive b
.De
In this example, it was not necessary to specify a definition of drive \fIa\fP\|
again, since Vinum keeps track of all objects in its configuration database.
.P
In this example, each plex contains the full 512 MB of address space.  As in the
previous example, each plex contains only a single subdisk.
.H3 "Optimizing performance"
The mirrored volume in the previous example is more resistant to failure than an
unmirrored volume, but its performance is less: each write to the volume
requires a write to both drives, using up a greater proportion of the total disk
bandwidth.  Performance considerations demand a different approach: instead of
mirroring, the data is striped across as many disk drives as possible.  The
following configuration shows a volume with a plex striped across four disk
drives:
.Dx
drive c device /dev/da5h
drive d device /dev/da6h
volume stripe
  plex org striped 512k
    sd length 128m drive a
    sd length 128m drive b
    sd length 128m drive c
    sd length 128m drive d
.De
.P
As before, it is not necessary to define the drives which are already known to
Vinum.
.H2 "Increased resilience: RAID-5"
The alternative approach to resilience is RAID-5.  A RAID-5 configuration might
look like:
.Dx
drive e device /dev/da6h
volume raid5
  plex org raid5 512k
    sd length 128m drive a
    sd length 128m drive b
    sd length 128m drive c
    sd length 128m drive d
    sd length 128m drive e
.De
Although this plex has five subdisks, its size is the same as the plexes in the
other examples, since the equivalent of one subdisk is used to store parity
information.
.P
On creation, RAID-5 plexes are in the \fIinit\fP\| state: before they can be
used, the parity data must be created.  Vinum currently initializes RAID-5
plexes by writing binary zeros to all subdisks, though a probable future
alternative is to rebuild the parity blocks, which allows better recovery of
crashed plexes.
.H3 "Resilience and performance"
.Pn resilience
With sufficient hardware, it is possible to build volumes which show both
increased resilience and increased performance compared to standard UNIX
partitions.  Mirrored disks will always give better performance than RAID-5, so
a typical configuration file might be:
.Dx
volume raid10
  plex org striped 512k
    sd length 102480k drive a
    sd length 102480k drive b
    sd length 102480k drive c
    sd length 102480k drive d
    sd length 102480k drive e
  plex org striped 512k
    sd length 102480k drive c
    sd length 102480k drive d
    sd length 102480k drive e
    sd length 102480k drive a
    sd length 102480k drive b
.De
The subdisks of the second plex are offset by two drives from those of the first
plex: this helps ensure that writes do not go to the same subdisks even if a
transfer goes over two drives.
.H3 "Creating file systems"
Volumes appear to the system to be identical to disks, with one exception.
Unlike UNIX drives, Vinum does not partition volumes, which thus do not contain
a partition table.  This has required modification to some disk utilities,
notably \fInewfs\fP\|, which previously tried to interpret the last letter of a
Vinum volume name as a partition identifier.  For example, a disk drive may have
a name like \fI/dev/wd0a\fP\| or \fI/dev/da2h\fP.  These names represent the
first partition (\f(CWa\fP) on the first (0) IDE disk (\f(CWwd\fP) and the
eighth partition (\f(CWh\fP) on the third (2) SCSI disk (\f(CWda\fP)
respectively.  By contrast, a Vinum volume might be called
\fI/dev/vinum/concat\fP, a name which has no relationship with a partition name.
.P
Normally, \fInewfs(8)\fP\| interprets the name of the disk and complains if it
cannot understand it.  For example:
.Dx
# \f(CBnewfs /dev/vinum/concat\fP
newfs: /dev/vinum/concat: can't figure out 
file system partition
.De
In order to create a file system on this volume, use the \f(CW-v\fP option to
\fInewfs(8)\fP\|:
.Dx
# \f(CBnewfs -v /dev/vinum/concat\fP
.De
.sp -1v
.H2 "Startup"
Vinum stores configuration information on the disk slices in essentially the
same form as in the configuration files.  When reading from the configuration
database, Vinum recognizes a number of keywords relating to object state which
are not allowed in the configuration files.  Vinum does not store information
about drives in the configuration information: it finds the drives by scanning
the configured disk drives for partitions with a Vinum label.  This enables
Vinum to identify drives correctly even if they have been assigned different
UNIX drive IDs.
.P
At system startup, Vinum reads the configuration database from one of the Vinum
drives.  Under normal circumstances, each drive contains an identical copy of
the configuration database, so it does not matter which drive is read.  After a
crash, however, Vinum must determine which drive was updated most recently and
read the configuration from this drive.
.H2 "Performance issues"
At present only superficial performance measurements have been made.  They show
that the performance is very close to what could be expected from the underlying
disk driver performing the same operations as Vinum performs: in other words,
the overhead of Vinum itself is negligible.  This does not mean that Vinum has
perfect performance: the choice of requests has a strong impact on the overall
subsystem performance, and there are some known areas which could be improved
upon.  In addition, the user can influence performance by the design of the
volumes.
.P
The following sections examine some factors which influence performance.
.Aside
\fBNote:\fP The performance measurements in this section were done on some very
old pre-SCSI-1 disk drives.  The absolute performance is correspondingly poor.
The intention of the following graphs is to show relative performance, not
absolute performance.  Other tests indicate that the performance relationships
also apply to modern high-end hardware.
.End-aside
.H3 "The influence of stripe size"
In striped and RAID-5 plexes, the stripe size has a significant influence on
performance.  In all plex structures with more than one subdisk, the possibility
exists that a single transfer to or from a volume will be remapped into more
than one physical I/O request.  This is never desirable, since the average
latency for multiple transfers is always larger than the average latency for
single transfers to the same kind of disk hardware.  Spindle synchronization
does not help here, since there is no deterministic relationship between the
positions of the data blocks on the different disks.  Within the bounds of the
current BSD I/O architecture (maximum transfer size 128 kB) and current disk
hardware, this increase in latency can easily offset any speed increase in the
transfer.
.P
In the case of a concatenated plex, this remapping occurs only when a request
overlaps a subdisk boundary, which is seldom enough to be negligible.  In a
striped or RAID-5 plex, however, the probability is an inverse function of the
stripe size.  For this reason, a stripe size of 256 kB appears to be optimum: it
is small enough to create a relatively random mapping of file system hot spots
to individual disks, and large enough to ensure than 99% of all transfers
involve only a single data subdisk.  Figure \*[mirroring] shows the effect of
stripe size on read and write performance, obtained with \fIrawio\fP\| [rawio].
This measurement used eight concurrent processes to access volumes with striped
plexes with different stripe sizes.  The graph shows the disadvantage of small
stripe sizes, which can cause a significant performance degradation even
compared to a single disk.
.H3 "The influence of RAID-1 mirroring"
.Pn mirroring-performance
Mirroring has different effects on read and write throughput.  A write to a
mirrored volume causes writes to each plex, so write performance is less than
for a non-mirrored volume.  A read from a mirrored volume, however, reads from
only one plex, so read performance can improve.
.P
There are two different scenarios for these performance changes, depending on
the layout of the subdisks comprising the volume.  Two basic possiblities exist
for a mirrored, striped plex.
.H4 "One disk per subdisk"
The optimum layout, both for reliability and for performance, is to have each
subdisk on a separate disk.  An example might be the following configuration,
similar to the sample ``RAID-10'' configuration seen above.
.Dx
volume raid10
  plex org striped 512k
    sd length 102480k drive a
    sd length 102480k drive b
    sd length 102480k drive c
    sd length 102480k drive d
  plex org striped 512k
    sd length 102480k drive e
    sd length 102480k drive f
    sd length 102480k drive g
    sd length 102480k drive h
.De
In this case, the volume is spread over a total of eight disks.  This has the
following effects:
.Ls B
.LI
Read access: by default, read accesses will alternate across the two plexes,
giving a performance improvement close to 100%.
.LI
Write access: writes must be performed to both disks, doubling the bandwidth
requirement.  Since the available bandwidth is also double, there should be
little difference in througput.
.Le
At present, due to lack of hardware, no tests have been made of this
configuration.
.H4 "Both plexes on the same disks"
An alternative layout is to spread the subdisks of each plex over the same
disks:
.Dx
volume raid10
  plex org striped 512k
    sd length 102480k drive a
    sd length 102480k drive b
    sd length 102480k drive c
    sd length 102480k drive d
  plex org striped 512k
    sd length 102480k drive c
    sd length 102480k drive d
    sd length 102480k drive a
    sd length 102480k drive b
.De
In this configuration, the subdisks covering a specific plex address space have
been placed on different drives, thus improving both performance and resilience
This configuration has the following properties:
.Ls B
.LI
Read access: by default, read accesses will alternate across the two plexes.
Since there is no increase in bandwidth, there will be little difference in
performance through the second plex.
.LI
Write access: writes must be performed to both disks, doubling the bandwidth
requirement.  In this case, the bandwidth has not increase, so write throughput
will decrease by approximately 50%.
.Le
Figure \*[mirroring] also shows the effect of mirroring in this manner.  The
results are very close to the theoretical predictions.
.H3 "The influence of request size"
As seen above, the throughput of a disk subsystem is the sum of the latency (the
time taken to position the disk hardware over the correct part of the disk) and
the time to transfer the data to or from the disk.  Since latency is independent
of transfer size and much larger than the transfer time for typical transfers,
overall throughput is strongly dependent on the size of the transfer, as Figure
\*[transfer-size] shows.  Unfortunately, there is little that can be done to
influence the transfer size.  In FreeBSD, it tends to be closer to 10 kB than to
30 kB.
.H3 "The influence of concurrency"
Vinum aims to give best performance for a large number of concurrent processes
performing random access on a volume.  Figure \*[concurrent-random] shows the
relationship between number of processes and throughput for a raw disk volume
and a Vinum volume striped over four such disks with between one and 128
concurrent processes with an average transfer size of 16 kB.  The actual
transfers varied between 512 bytes and 32 kB, which roughly corresponds to ufs
usage.
.P
This graph clearly shows the differing effects of multiple concurrent processes
on the Vinum volume and the relative lack of effect on a single disk.  The
single disk is saturated even with one process, while Vinum shows a continual
throughput improvement with up to 128 processes, by which time it has
practically leveled off.
.H3 "The influence of request structure"
For concatenated and striped plexes, Vinum creates request structures which map
directly to the user-level request buffers.  The only additional overhead is the
allocation of the request structure, and the possibility of improvement is
correspondingly small.
.P
With RAID-5 plexes, the picture is very different.  The strategic choices
described above work well when the total request size is less than the stripe
width.  By contrast, it does not perform optimally when a request is larger than
the size of all blocks in a stripe.  The requests map to contiguous space on the
disk but non-contiguous space in the user buffer.  An optimal implementation
would perform one I/O request per drive and map to the user buffer in software.
By contrast, Vinum performs separate I/O requests for each stripe.
.P
In practice, this inefficiency should not cause any problems: as discussed
above, the optimum stripe size is larger than the maximum transfer size, so this
situation arises only when an inappropriately small stripe size is chosen.
.P
Figure \*[raidplot] shows the RAID-5 tradeoffs:
.Ls B
.LI
The RAID-5 write throughput is approximately half of the RAID-1 throughput in
figure \*[mirroring], and one-quarter of the write throughput of a striped plex.
.LI
The read throughput is similar to that of striped volume of the same size.
.Le
Although the random access performance increases continually with increasing
stripe size, the sequential access performance peaks at about 20 kB for writes
and 35 kB for reads.  This effect has not yet been adequately explained, but may
be due to the nature of the test (8 concurrent processes writing the same data
at the same time).
.H2 "Availability"
Vinum is available without RAID-5 functionality under a Berkeley-style copyright
as part of the FreeBSD 3.1 distribution.  It is also available at [vinum].  The
RAID-5 functionality is available under licence from Cybernet, Inc. [Cybernet],
and is included in their \fINetMAX\fP\| Internet connection package.
.H2 "Future directions"
The current version of Vinum implements the core functionality.  A number of
additional features are under consideration:
.Ls B
.LI
\fIHot spare\fP\| capability: on the failure of a disk drive, the volume manager
automatically recovers the data to another drive.
.LI
\fILogging\fP\| changes to a degraded volume.  Rebuilding a plex usually
requires copying the entire volume.  In a volume with a high read to write
ratio, if a disk goes down temporarily and then becomes accessible again (for
example, as the result of controller failure), most of the data is already
correct and does not need to be copied.  Logging pinpoints which blocks require
copying in order to bring the stale plex up to date.
.LI
\fISnapshots\fP of a volume.  It is often useful to freeze the state of a
volume, for example for backup purposes.  A backup of a large volume can take
several hours.  It can be inconvenient or impossible to prohibit updates during
this time.  A snapshot solves this problem by maintaining \fIbefore images\fP, a
copy of the old contents of the modified data blocks.  Access to the plex reads
the blocks from the snapshot plex if it contains the data, and from another plex
if it does not.
.P
Implementing snapshots in Vinum alone would solve only part of the problem:
there must also be a way to ensure that the data on the file system is
consistent from a user standpoint when the snapshot is taken.  This task
involves such components as file systems and databases and is thus outside the
scope of Vinum.
.LI
A \fISNMP interface\fP for central management of Vinum systems.
.LI
A \fIGUI\fP\| interface is currently \fInot\fP\| planned, though it is
relatively simple to program, since no kernel code is needed.  As the number of
failures testify, a good GUI interface is apparently very difficult to write,
and it tends to gloss over important administrative aspects, so it's not clear
that the advantages justify the effort.  On the other hand, a graphical output
of the configuration could be of advantage.
.LI
An \fIextensible ufs\fP.  It is possible to extend the size of some modern file
systems after they have been created.  Although ufs (the \fIUNIX File System\fP,
previously called the Berkeley \fIFast File System\fP\|) was not designed for
such extension, it is trivial to implement extensibility.  This feature would
allow a user to add space to a file system which is approaching capacity by
first adding subdisks to the plexes and then extending the file system.
.LI
\fIRemote data replication\fP\| is of interest either for backup purposes or for
read-only access at a remote site.  From a conceptual viewpoint, it could be
achieved by interfacing to a network driver instead of a local disk driver.
.LI
\fIExtending striped and RAID-5 plexes\fP\| is a slow complicated operation, but
it is feasible.
.Le
.H2 "References"
.na
[CMD] CMD Technology, Inc June 1993, \fIThe Need For RAID, An Introduction\fP.
\fIhttp://www.fdma.com/info/raidinto.html\fP\|
.P
[Cybernet] \fIThe NetMAX Station\fP,
\fIhttp://www.cybernet.com/netmax/index.html\fP.  The first product using the
Vinum Volume Manager.
.P
[FreeBSD] FreeBSD home page, \fIhttp://www.FreeBSD.org/\fP\|
.P
[IBM] \fIAIX Version 4.3 System Management Guide: Operating System and Devices,
Logical Volume Storage Overview\fP\|
.br
\fIhttp://www.austin.ibm.com/doc_link/en_US/a_doc_lib/
aixbman/baseadmn/lvm_overview.htm\fP
.P
[Linux] \fILogical Volume Manager for Linux\fP\|,
\fIhttp://linux.msede.com/lvm/\fP.
.P
[McKusick] Marshall Kirk McKusick, Keith Bostic, Michael J. Karels, John
S. Quarterman.  \fIThe Design and Implementation of the 4.4BSD Operating
System\fP, Addison Wesley, 1996.
.P
[OpenSource] \fIThe Open Source Page\fP, \fIhttp://www.opensource.org/\fP\|
.P
[rawio] A raw disk I/O benchmark. \fIftp://ftp.lemis.com/pub/rawio.tar.gz\fP\|
.P
[SCO] \fISCO Virtual Disk Manager\fP,
\fIhttp://www.sco.com/products/layered/ras/virtual.html\fP.
.\" This document gives a good overview of a technology similar to Vinum.
.P
[Solstice] \fIhttp://www.sun.com/solstice/em-products/system/disksuite.html\fP\|
.P
.nf
[veritas] The VERITAS\(rg Volume manager,
\fIhttp://www.veritas.com/product-info/vm/index.htm\fP\|.
.fi
.P
[vinum] Greg Lehey, \fIThe Vinum Volume Manager\fP,
\fIhttp://www.lemis.com/vinum.html\fP.  An extended version of this paper.
.P
[Wong] Brian Wong, \fIRAID: What does it mean to me?\fP, SunWorld Online,
September 1995.
\fIhttp://www.sunworld.com/sunworldonline/swol-09-
1995/swol-09-raid5.html\fP\|
.br
.1C
.H2 "Illustrations"
.PSPIC stripesize.ps
.Figure-heading "The influence of stripe size and mirroring"
.Tn mirroring
.PSPIC "striped-by-transfer-size.ps"
.sp
.Figure-heading "Throughput as function of transfer size"
.Tn transfer-size
.PSPIC plot.2
.P
.Figure-heading "Concurrent random access"
.Tn concurrent-random
.PSPIC raidplot.ps
.Figure-heading "RAID-5 performance against stripe size"
.Tn raidplot