\documentstyle[a4,11pt]{article}
\title{Using a Local Disc as a Block Cache}
\author{University of Cambridge Computer Laboratory\\
M. Burrows}
\date{November 5, 1986}
\begin{document}
\maketitle
 
\section{Introduction}
 
This work was done as part of a project whose goal is to create a 
{\it processor bank} \cite{pbank}
using a number of MicroVAX\footnote{MicroVAX and Ultrix are
registered trademarks of the Digital Equipment Corporation}
computers, which were provided by Digital as part of an
External Research contract.
The processor bank approach implies that:
\begin{itemize}
\item
Machines are allocated to users on demand; they are normally
allocated for a single terminal session or task.
\item
Machines are often allocated to a single user for a single session.
\item
When a machine is allocated, it is loaded with the operating
system of the user's own choice.  The operating system
is usually not trusted by other network nodes.
\item
The machines are locked in a room.  Their hardware is secure.
\end{itemize}
The main problems that must be faced when implementing a processor bank system
are:
\begin{itemize}
\item
It must be possible to reclaim an allocated machine forcibly in 
order to implement resource management policies.
\item
Users must not be tied to a particular machine --- files belonging
to a user should not be left on a machine.
\item
It must not take very long to load and boot an operating system.
This requirement can be made less important by preloading
machines with popular operating systems.
\item
Booting a client machine with an operating system should not rely on
any state that could be modified by previous users.
\end{itemize}
The first of these problems requires that the machine have an
intelligent network interface which can authenticate the request and
reboot the machine, regardless of the state of the rest of the
machine.  This is rather easier on a Cambridge Ring \cite{pbank} than on
an Ethernet \cite{ether}, and it is hoped that this will become possible
when Cambridge Fast Ring \cite{cfr} interfaces have been built for the
MicroVAXes.
 
To achieve user mobility, it was important that file access should be
done across the network.  A simple remote disc access protocol (MIT's
Remote Virtual Disc) was used to provide the means by which a user
would access his files.  RVD consists a disc block server and some client
code that makes the RVD partition behave like a (slow) local
disc.  RVD does not impose any structure on the file system used on the
disc, nor does it provide any means for hiding the details of the file
system from the client.  It was recognised that RVD has many drawbacks,
but it had the advantages of being easy to install, having a simple and
reliable protection mechanism and being easy to administer.  Its major
failing is that it does not allow the possibility of shared writable
files.
 
The original Cambridge processor bank consisted mainly of discless
machines, and so the problem of exploiting a large amount
of local storage had no immediately obvious solution.
Even though RVD uses a very simple
protocol, RVD file accesses were usually between three and six times
slower than equivalent local accesses, depending on the load at the
server.  This difference in speed is sufficient to make it worthwhile
placing commonly used files on the local disc.  Unfortunately, since
the machine may run a number of operating systems at different times,
the contents of the
disc are undefined at reboot, and loading a 70Mbyte disc across a Local
Area Network is still quite slow.  A proposed solution to this problem
was to initialize the local disc from a read-only RVD partition whenever
a block was read for the first time from a system file store. \cite{maj}
It was
soon realized that this technique could be extended to form a general
block cache for all RVD partitions being used on the machine.
 
A caching scheme was implemented under a version of the {\sc unix}\footnote{UNIX is a registered trademark of AT\&T.} Operating
System \cite{unix}, the Digital Equipment Corporation's Ultrix.
The popularity of the operating system and the availability of sources made
it the natural target environment for this work.
 
\section{A Caching Device Driver}
 
Most of work in the caching system is done by a virtual disc driver
that sits between the block I/O layer \cite{bio} and the other disc
drivers.  The block I/O system treats this virtual disc driver as it
would any other device driver, but the driver has no physical device of
its own.  Instead, it calls on other device drivers to read and write
blocks whenever this is necessary to implement the caching scheme.  The
device driver can manage a large number of logical drives, but the
maximum number must be specified at system configuration time.  Each
logical drive has an associated cache device and an initialization
device.  A system call allows almost any random access device to be
specified as the {\it cache} and {\it initialization} devices of a
particular logical drive, but in practice the cache device is usually
local to the machine while the initialization device is remote.
 
The driver is entirely responsible for the caching strategy used on any
particular virtual drive.  In the current implementation, two independent
options may be given in order to modify the behaviour of the driver.
In normal operation, reads are satisfied from either the cache or the
initialization device as required and writes affect only the cache device, but
under the write-through option, the driver will undertake to write to both
devices.  This decreases the speed of writes to below that obtained from a
single device, but the overall effect is still beneficial because:
 
\begin{itemize}
\item
reads are typically three or four times more common
than writes.
\item
the {\sc unix} buffer cache already ensures that writes are
often asynchronous.
\end{itemize}
 
Most user disc partitions are used in write-through mode to 
ensure that changes are stored on the file server as they are made.
However, standard system binaries are usually cached without
write-through, allowing a single read-only remote partition to be used
by many machines while still permitting more ambitious users to
modify their own cached copies of system directories.  A less obvious
advantage of this technique is that is obviates the need to check the
consistency of the system file stores at reboot, so decreasing the time needed
to reboot a machine.  If write-through mode is not used, modified
blocks in the cache are marked as dirty and may not be discarded
until the machine has stopped using the drive.
 
A write-through mode was chosen in preference to a delayed write-back
scheme because any delay in saving updates would have seriously affected the
robustness of the file system in the face of host and server crashes.
In fact, the Unix I/O system already introduces a delay, and this is
limited to about 30 seconds for similar reasons.
Moreover, the constraints of the {\sc unix} block I/O system would have made
the implementation of delayed write-back more involved.\footnote{
A possible implementation might use a user-space ``cache daemon''
to provide the necessary buffer space.}
 
A second driver option causes blocks to be kept on the cache disc in
the the same position as the corresponding block on the initialization
disc, rather than to use the blocks on the cache disc in any convenient
order.  In fact, this is the original algorithm used by an earlier
version of this code and it has a number of advantages:
 
\begin{itemize}
\item
The presence of a valid block on the cache disc can
be indicated by a single bit stored in a bitmap.
\item
Block address calculations are trivial.
\item
Fewer physical device reads are required to satisfy
partially cached multiblock reads.  For example, fully cached
read requests can always be satisfied with a single read.
\item
Dirty bits are not required to mark modified blocks
not written back to the initialization disc.  There
is always enough space for all blocks to be present
on the cache disc simultaneously.
\end{itemize}
 
Despite the advantage of being simpler to implement and slightly faster,
this ``block-for-block'' mode has two overwhelming disadvantages.  Firstly,
a single cache disc cannot be used to cache blocks from many initialization
discs, and secondly very large discs cannot be cached.  As a result, this
``block-for-block'' mode is very rarely used, and the following
section will concentrate
on the normal mode of operation in which a single cache device can be used
with many initialization devices.
 
In addition to the caching system itself, the kernel was modified
to allow it to make use of the network during its setup phase.  This enables
a machine booted from the network to access a remote root file system,
and even a remote swap
partition.
As a result, it is possible to boot a machine with no discs
whatsoever, though it is more common to make the local disc serve
as a cache and swap area.   This achieves one of the properties vital in
a processor bank, namely that a reboot make use of no volatile state
held by the machine itself.
 
\section{Implementation}
 
For each cache device, the caching device driver manages a table which
maps logical disc blocks onto cache blocks.  Each table entry contains
a descriptor for an 8KByte block of the cache disc, which is the unit of
cache space allocation.  A bitmap within each block descriptor entry
indicates which parts of the 8KByte block contain valid data.  The
block size was chosen deliberately so that the vast majority of {\sc unix}
file system I/O operations would not span cache block boundaries.
Table lookup is performed via a hash table pointing to linked lists of
block descriptors, allowing reasonably fast lookup, allocation and
deallocation of cache blocks.  A further linked list is used to implement
the cache block allocation strategy, which is ``least recently used''.
In the current implementation only one cache device can be active at any
given time, simply because only one array of block descriptors is
allocated.  This restriction exists mainly because of the problems
of allocating and deallocating memory within the {\sc unix} kernel, but
could be removed if it was felt to be necessary.  
 
The caching device driver is able to split logical transfers up into an 
arbitrary number of physical transfers on different devices.   Originally
this was done by using the block I/O system's ``call back'' mechanism to
start a new transfer after the end of the last.   Later, an extra call back
flag was added so that the caching driver could be used with other
device drivers that make use of call backs.
 
Each logical transfer request received by the device driver is split into 
four major components, which are performed in the order:
\begin{enumerate}
\item
read from the cache device
\item
read from the initialization device
\item
write to the initialization device
\item
write to the cache device
\end{enumerate}
These components are further subdivided if the cache blocks are not
stored contiguously, or if a read request must be satisfied partially from
each device.   Some optimizations are made to reduce the number of
physical transfers based on the assumption
that device latency is high compared to transfer times.  For example, if a read
is partially cached but the copy on the initialization disc is up to date,
the entire
transfer is read from the initialization disc and subsequently written
to the cache disc.  However, the {\sc unix} buffer cache system
ensures that there are very few transfers of partially cached sections, so
the utility of these optimizations is questionable.
 
During the normal boot procedure, the network interface is initialized
only after the system has started to access its root file store.
In order to remove the need for a valid file store on the local disc,
the kernel was modified
to initialize the network interface before the first file system operations,
so that those operations could be remote.
When a machine is booted by a boot server, a generic kernel is loaded together
with an information block containing the identity the machine is to assume, 
and the names and network addresses of any remote partitions it may need.
The kernel calls routines internally that correspond to system calls to
initialize the interface and make connections with file servers.
 
\section{Problems Encountered}
 
Unfortunately, it was not possible to implement the caching
device driver without some changes to other parts of the kernel.
The most important of these changes was the addition of some extra fields 
to the kernel disc buffer header to allow the indirection required for
the caching device driver to call on other device drivers.  In the standard
{\sc unix} buffer cache, the device number and disc block number are used both
as an index to a logical block and as physical
unit and block numbers.  These two functions must be separated in the caching
device driver, since a logical block may exist on one of two devices and
may be in any physical block.  Four fields were added to the buffer
header structure to keep track of the logical device number, the 
logical block number, the logical transfer size and the logical transfer
memory address.   Each of these corresponds to an existing field which
holds the physical parameter for the current section of the 
transfer.  The kernel buffer management routines were modified to set
both physical and logical device and block numbers, allowing unmodified device
drivers to be used directly by the block I/O system, as well as
permitting the caching device driver to redirect the transfer to any device
and location.
 
Another necessary modification was associated with the use of call backs.
These are used by the caching device driver to gain control of a buffer
as soon as it is released by a real driver, so that a new transfer can be
queued.  Unfortunately, the driver for the MicroVAX local disc controller
would invariably release a buffer before it had completed its transactions with
the controller, causing a new request to be queued in such a way as to
redo the previous transfer.  Fortunately, once the culprit had been found, 
it was relatively simple to make the driver reentrant.
 
In fact, call backs are avoided whenever possible; the simple cases
where a transfer can be done in one operation are recognised and
optimized.   Additionally, when a block has been read from the
initialization device, it can be marked as dirty by setting the
``delayed write'' bit the buffer header.   This has the effect of writing
the block to the cache device asynchronously, resulting in a
performance improvement and avoiding a call back.  Unfortunately, the
technique is not applicable to demand paging traffic, which seriously
limits its utility.  This problem would disappear if the virtual memory
system were better integrated with the file system code.
 
\section{Experiences}
 
The caching device driver has already proved to be successful in improving
the performance of accesses to remote discs.  This has been particularly
noticed by users of language subsystems which have their own specialized
network file systems containing a large amount of library code that is
frequently accessed.   More importantly, once a machine has
cached the most commonly used files locally,
it runs without any significant overhead due to the network when accessing
standard system files.
 
An improvement that was not envisaged when the scheme was first conceived was
in the time taken to boot a machine.  It was found that booting over the
network is inherently faster than booting from a disc bootstrap, 
because fewer levels of bootstrap are required, and there is no need
for each bootstrap level to initialize the disc controller,
an operation that takes several seconds.  As a result, a kernel can now be
booted to single user mode in approximately 22 seconds --- about 3 times faster
than when booting from disc.   When the system file space resides on a
read-only network partition, the rest of the bootstrap code is also
much faster, as there is no need to check for file system inconsistencies.
At the moment, a machine can now be booted to its normal multiuser state
in 61 seconds if the bootserver and network are not heavily loaded.  This
is again about 3 times faster than booting with a local file system.
Of course, there is some penalty to pay as each commonly used file
is fetched from the file server and cached, but this has not proved to be
especially great.  If the initial delay of loading certain programmes was
found to be too annoying,  it would be trivial to cause them to be 
cached before any user logged in by reading them with an asynchronous
process during the startup sequence.
 
It is expected that the ability to run all machines from the same copy
of the system file space will reduce the time spent in keeping machines
up to date when code is modified.   Also, this technique allows a totally
different set of system files to be loaded by changing a single boot
parameter, making it trivial to test new kernels and systems programmes.
 
 
However, there are some problems associated with 
the cached nature of the system file space, and these are mainly associated
with volatile files such as the password file and files that customize
users' logins.  The problem of the password file is easily avoided by 
having each machine read its password file from a trusted server at boot time.
The password file of the machine is then periodically merged with the
permanent database to incorporate any changes that users might make.  A better
solution might be to use a scheme such as SUN's Yellow Pages \cite{yp}, but this has
not yet been done.  Users' home directories are initialized by copying
the contents of a small RVD partition owned by the user onto the local
cache of the machine.  Users' typically have three or four files needed
in their login sequences in this small RVD partition, which is normally
not mounted on any machine.
Each time the user logs in, a check is made that
the cached files are up to date, ensuring that the user need only change
his RVD partition when he wishes to change his login script.  This
scheme is not ideal, but was found to be a satisfactory compromise given
the infelicities of RVD itself.  Of course, it would be trivial to set
aside a small area for user home directories on each local disc if 
a processor bank environment was not required.
 
Another problem is that of updating the system partition, which
cannot be written to while it is being used by a client machine.  The standard
technique used with RVD partition of this type is to swap the name with another
partition which has the new contents, so allowing newly booted machines
to pick up the modified files.   However, this is an expensive operation,
and all the client machines must be rebooted before an RVD is reused.  Since
system files may need to be changed on a day to day basis, a second partition
is provided.   The contents of this partition are copied into the local cache
of a machine when it boots, enabling changes to be made without swapping
RVD partitions.   Immediate changes must be made by copying to each machine
in turn, or by rebooting them.
 
There are some benefits derived from the ability to run without a local
disc, rather than from the caching system.   For example, it is
possible to manipulate a local disc in a controlled way, simply because
the new kernel guarantees not to touch the disc.  This technique has
found application in a disc backup strategy for another operating
system.  Interestingly, the simplest way of administering such systems
is to use the same read-only root partition as on the caching machines.
Of course, one then needs a cache partition, but that is easily
provided by another RVD.   It may seem strange to cache remote blocks on
another remote device, but the purpose here is to avoid multiple copies
of file systems, rather than to improve performance.
 
In conclusion, the caching system and the related work on booting MicroVAXes
using only the network interface have made processor bank style
working possible, with very little overhead.  The simplicity of the
administration of machines working in this way is attractive, and
other machines not associated with the processor bank work may soon
be converted to caching systems.   A fully operational processor bank could
now be constructed with only a few changes to the existing system:
 
\begin{itemize}
\item
new network interfaces are required to allow preemption
from the network.  This should happen when the MicroVAX
Fast Ring interfaces are completed.
\item
A resource manager must be constructed for allocating
machines.
\item
If full security is required, software must be changed
to wipe the discs and memory of machines before they are
reallocated.
\end{itemize}
 
\begin{thebibliography}{9}
 
\bibitem{pbank}
R.M. Needham and A.J. Herbert,
{\it The Cambridge Distributed Computing System},
Addison-Wesley Publishing Company, 1982,
International Computer Science Series.
 
\bibitem{ether}
Xerox Palo Alto Research Centre,
``The Ethernet Local Network: 3 Reports'',
Feb. 1980, CSL-80-2
 
\bibitem{cfr}
S. Temple,
``The Design of a Ring Communications Network'',
PhD Thesis,
University of Cambridge, 1984
\bibitem{maj}
M.A. Johnson,
private communication.
 
\bibitem{unix}
D.M. Ritchie and K. Thompson,
``The {\sc unix} Time Sharing System'',
{\it Bell Systems Technical Journal},
(Special Issue), 57 (6), part 2, July-August 1978, 
 
\bibitem{bio}
K. Thompson,
``{\sc unix} Implementation'',
{\it Bell Systems Technical Journal},
(Special Issue), 57 (6), part 2, July-August 1978, 
 
\bibitem{yp}
SUN MicroSystems,
``Networking on the SUN Workstation'',
The Yellow Pages Protocol Specification,
Feb 1986
 
\end{thebibliography}
\end{document}
