Technique for redundancy
control in a distributed
hierarchical filestore
K Lunn and K H Bennett*

A means o f controlling multiple-copy redundancy o f files
through a hierarchical directory system is described.
Both the access paths to and the individual copies o f files
are replicated in such a way that a file can be located if
and only if there exists a volume online which contains a
copy o f that file. A simple mechanism based on timestamps is used to resolve inconsistencies between files
before access. The algorithm is suitable for a distributed
filestore on a local area network, or even fo r a multiplevolume filestore on a stand-alone machine. It is notproposed as a sensible solution to wide area networkfile
storage on a large scale. The hierarchy is UNIX-like(U NIX is a trademark o f Bell Laboratories), but without
links.
Keywords: file organization, redundancy control, distri­buted filestorage
IN T R O D U C T IO N
Distributed filestorage is a topical subject that has been
investigated in different ways. One approach is effectively
to ignore user-naming and concentrate on low-level
details concerning location, access and update of files,
and the control of replication1. Files are referred to bysystem-interpreted names, called unique identifiers, andthe mapping of user names to unique identifiers is imple­
mented by a higher layer of software. Another approach is
to combine stand-alone filestores to provide a distributed
filestore by linking together the name spaces to give alarger name space5.
This article describes an approach that concentrates on
the user-oriented file naming scheme. There is a general
University of Bradford, West Yorkshire BD7 1DP, UK•University of Keele, Staffs ST5 5BG, UK

vol 3 no 3 1984

consenus that hierarchical organization of directories andfiles provides a useful naming scheme, e.g., UNIX.
Hierarchies are typically spread across a number ofvolumes. There are several ways to construct a namespace for multiple-volume filestores. This article presents
an alternative method that provides extra reliability and issuitable for a multiple-volume filestore on either a single
machine or a network. The name of a file is independent of
the location of copies of the file, and the location can bechanged without changing the name. The naming schemeand the associated algorithms have been described by
Lunn3,4.
Essentially, the naming scheme provides multiple copy
redundancy of both files and directories. The higher
echelons of the hierarchy have the highest levels of
redundancy. It is possible to trace any file on a volume,using its full path name, if that volume is accessible.
Consistency between copies of a file is ensured before
access to any of those copies is allowed.
The naming scheme has been implemented as aprototype on a local area network. Two LSI11/02 micro­
computers each ran a single volume file server, and the
directory system. The filestore was accessed by a personal
workstation over a Cambridge Ring.

C O N S T R U C T IN G M U L T IPL E -V O L U M E
F IL E ST O R E S
U N IX
Each volume in a U N IX filestore is organized as ahierarchical file system. One system is designated as theroot file system. Other volumes can be mounted on theroot file system, so that the root of the mounted file system
replaces a directory in the root file system. Further

0144-817X /84/03015 7-05 $03.00 © 1984 Butterworth & Co (Publishers) Ltd

157

volumes can be mounted on mounted file systems, and soon. Thus a typical file system might look like

Unix

Bin

Usr

A common way of uniting file systems on volumes istypified by the VAX/VMS operating system. All online
volumes are uniquely named. The name may be that of thedrive on which it is mounted, or a user-provided name. A
typical configuration might look like

US I

Staff

Student

TMP

Ken

SYSTEM ( DRAO)

File IUK

SYSTEM B

MATHS

COMPUTING//COMPUTING

Here SYSTEMA, SYSTEMB and SYSTEMC are namesof computers on a network. A file on SYSTEMA might
have the name USER1 : [KEN.FILE1]. A user on
SYSTEMB would refer to it as SYSTEMA :: U S E R 1 :[KEN.FILE1].
A n alternative approach
Lunn’s3 approach to naming differs from the above. Eachvolume contains a complete set of directories enabling all
files on that volume to be traced without reference to othervolumes. Multiple volume filestores are constructed by anoverlay of all the file systems of individual volumes. Thus,
two volumes may be combined like this
/
Usr

Us 2

Us 3

Us 2

Us 3

to give
ENGINEERING

Usr

Here MATHS, CO M PUTIN G and EN G IN EER IN G
represent roots of separate filestores on separate
machines. A user on the CO M PUTIN G machine mightrefer to a file by the path name /usr/ken/filel. A user onanother machine would refer to it relative to the global
root (denoted //) as //C O M PU TIN G /usr/ken/filel.

158

SYSTEMC

KEELE

UK, BRADFORD, KEELE, M ATHS and COM­
PU TIN G are the roots of separate U N IX systems. The
files of these separate U N IX systems can be accessed
as if they were part of the local filestore. Further
U N IX systems may be mounted on, for example, theBRADFORD, KEELE or CO M PUTIN G systems.
Similarly, the UK system could be mounted in anotherU N IX system. Thus, it is possible to build an infinitely
extensible filestore (both upwards and downwards) out ofa number of separate U N IX filestores.
Another technique for uniting multiple UNIX-likefilestores is popular. A global root is constructed fromunique names given to all the file stores on the network. A
user accesses local file names in the normal way, andspecifies a full path name from the global root to accessremote files. Thus a system might look likeMATHS

USER2(DRA2)

There are three discs mounted on drives DRAO, D R A I
and DRA2, with names SYSTEM, USER1 and USER2
respectively. A user may name a file in two ways, using
the drive name or the volume name as the name in theapparent root directory. Thus USER1 : [KEN.FILE1]
and D R A I : [KEN.FILE1] refer to the same file. The
name between “ [” and “ ]” is a path name delimited by
and a full hierarchy can be constructed.
The network version of this uses names of systems. A
configuration might look like

SYSTEM A

BRADFORD

Usr

USER I ( DRAI)

File 2

Here a volume has been mounted at US1, and the filesystem for that volume becomes a subtree of the total
online filestore. Similarly a volume has been mounted at
TMP. Thus the filestore naming scheme is infinitely
extensible.
This approach has been extended to cover a distributed
filestore by the Newcastle Connection, which implements
a network operating system using standard U N IX
operating systems. As well as mounting the file system ofa volume it is possible to mount the filestore of another
UN IX system. Thus, we might see a filestore with a naming
scheme likeBin

V A X /V M S

Us IFurther volumes may be overlaid on this newly createdstructure. The file naming is the same as in standard
UNIX.

information technology

With the overlay technique it is possible to have multiple
copies of files and directories. For example, we mightoverlay the following two structures

a

a

6

c

•

A ssociated volum escd

to give
£7(2)

6(1)

rf(l)

The number in brackets indicates the number of objects
with that name. It is possible to overlay arbitrarily
complex trees. For example:

a

b e d
h

c
t

i

a

d
»

e

d

e
k

j

a
f
/

k

e

f

m

n

g

to give

a(4)
1
6(1)

c(2)

\

d(3)
6(2)

/(I)

6(3)

j(2)

A(2)

/(I)

777

(1)

77

(1)

Thus an arbitrary level of replication can be introduced.
Mounting a file is simply the addition of an overlay, anddismounting the removal of an overlay. To access a file itis merely necessary to trace the path from root to the given
file; if two or more copies exist, an arbitrary choice
can be made.
The overlay scheme has some quite distinct properties
from the previously described naming schemes.
• It can cope with multiple-copy redundancy within thenaming scheme.
• The path name of a file remains the same, irrespectiveof the location of the volume.
In U N IX , the full path name of a file on a non-root systemdepends on where that file system is mounted. In the otherschemes, it may well depend on which system it is located.
The ability to name an object uniquely irrespective of its
location is highly important where names are bound into
other objects or programs. On the other hand, there is no
possibility of constructing an ‘infinite network’ like the
Newcastle Connection.
Extra controls are required for a dynamic system. For
example, how are updates to replicated files controlled?
W hat happens if a volume is offline for a period? On whatvolumes should a file be replicated? The solutions describedby Lunn 3 are presented here. Alternative solutions, basedon the overlay technique are possible, and perhaps prefer­able in many instances, and some of these are discussed.
IM P L E M E N T A T IO N O F T H E N A M IN G
SC H E M E
The techiques used to implement a prototype of the abovevol 3 no 3 1984

On creation, a directory is given a set of volumes, called
the associated volumes for that directory, which must be asubset of the associated volumes of its parent, i.e.,(1) assocvols (P/d ) C assocvols (P)

c(2)

a

naming scheme are described here. However, they are notideal, and possible alternative means will be discussed.

where P is the path name of a directory and d is a subdirec­
tory of P. Clearly, the set of volumes available are
precisely the associated volumes of the root directory.
All files referenced by a directory are stored on all the
associated volumes of the directory. A directoiy is stored
on all its associated volumes, In this way, redundancy ofboth files and access paths is controlled. The access path
to a file can be traced if a volume containing it isonline.
Associated volumes allow tailoring of the hierarchy tomeet specific requirements. For example, a user with data
which must be online with a higher expectancy might beallocated a directory with three or more associatedvolumes. A user with multiple associated volumes in his/her home directory may create subdirectories with fewer
associated volumes for less critical applications. Suitableaccounting should prevent profligate misuse of available
redundancy. Clearly the higher echelons of the hierarchy
should not generally be used for storing files.
Primitives may be required to increase or decrease theset of associated volumes of a directory. This is necessary
to add new volumes to the system, or to remove volumes
from the system. Clearly these must not violate theconstraint (1) above. Thus if a directory gains an associatedvolume, that volume must be associated with the parent
director. If a directory loses an associated volume, thenthat volume must be disassociated with all subdirectories.

The active filestore
In a large filestore, only a part is likely to be in use at any
one time. The algorithms3 take advantage of this fact. Allfiles which are open, and the directories on paths tothose files are said to constitute the active filestore. For
each directory in the active filestore, a single process iscreated to administer activities in that directory. In theimplemented prototype, a single site was elected to run all
the directory processes. Clearly, these processes could be
distributed according to the location of data or according
to other criteria such as load balancing.
The choice of a single directory process for each active
directory solves synchronization problems. However, it
does imply an unfortunate overhead in process creation. It
may also cause problems if a directory process fails,
breaking the path to an open file. Other solutions tosynchronization may be worthy of consideration. In asense, the process-per-directory is a move toward acentralized solution, but it is one way of enforcing
consistency constraints on a directory.
The notion of an active filestore is largely introduced
for efficiency. Ideally, a process for each directory should
be running or ready to run all the time. It would be very
difficult to implement this on existing hardware andoperating systems.

159

C onsistency resolution
For high accessibility, it must be possible to access files
even if a number of volumes are offline. This can lead tosituations where copies of files are out of date. On creationa directory process resolves whatever consistencies it can
detect before allowing access to the contents of thedirectory.
Each file on a volume is timestamped, the timestamp
being stored in the copy of the parent directory on thatvolume. This implements a function
time: volume, pathname — integer
If P is the path name of a directory on vl and v2, and vl
and v2 are online, the directory process enforces theconstraint(2) tim e(vl, P/n) = time(v2, Pin)for all files named n in directory P. The directory uses
a careful replacement strategy for update, and on updateof a file it copies the replacement file to all (online)
volumes on which it should be stored, and allocates a newtime to the copies. If constraint (2) is violated, the direc­
tory process selects the online volume vl for which
tim e(vl, P/n) > time(v2, P/n)
for all online v2 in assocvols(P). Whenever v2 violates theconstraint ( 2 ), the directory process replaces the copy ofthe file on v2 with the version on v l, and updates thetimestamp on v2 so thatalgorithms provide weak consistency, in the sense thatthey will ensure consistency between currently online
volumes, but may result in problems over a period of time.
For example, suppose vl and v2 are die associatedvolumes ofP, and that they are online at different times. If
a user creates a file P/n on v l, and later cannot find it
because vl is offline, so he recreates it on v2 , when vl andv2 are online together, which one does the user really wantto keep (it may not be the most recently created). Morecomplex examples can be created with more than twovolumes.
If the likelihood of a volume being accessible is high,the above algorithm may suffice, and the occasional
problems may be infrequent enough to be ignored.
However, on a complex system, where volumes may bedismounted frequently, or where network partitioning
may occur, an extra constraint may be necessary.
Strong consistency
The extra constraint of requiring a majority of associatedvolumes to be online for activation of a directory process
removes a number of problems. Clearly, under thisconstraint, whenever a file is created, updated or deleted,the current majority will intersect with any future majority,
so that the most recent change to a file will always bereflected in an online directory. This constraint must be
taken into account when increasing or decreasing theassociated volumes of a directory.

time'(v2, P/n) = tim e(vl, P/n)
where time' is the time function after resolving inconsis­
tencies. In this way, files can be updated when somecopies are offline, and the offline copies can catch up.
Another problem arises if a file is created when some of
the associated volumes of the directory in which it iscreated are offline. The directory process enforces theconstraint(3) P/n e n a m e s(v l) A N D v2 eassocvols (P)=> P/n G names (v2)where names (v) is the set of path names of objects onvolume v, and where vl and v2 are online. That is, if a file
exists in a directory on a volume, then it must exist on all
the associated volumes. This is simply done by copying a
version of a file onto all volumes which should but which
do not contain it. Files created in this way are given thetimestamp of the file which is copied.
Finally, it is possible to delete a file where not all copies
are online. This is done by leaving an assassin for the filein the online directories so that future activations of thedirectory can remove any remaining copies of a file. The
assassins are given timestamps, so that a recreated filecannot be deleted because of an old assassin. Thus iftime (P/n, vl) < time (P/n, v2)
and P/n is the name of an assassin on v2 and a file on vl,
the file on vl is replaced by an assassin. If P/n is the nameof an assassin on v I and a file on v2 , then the assassin on
vl is replaced by a copy of the file on v2. When all
associated volumes of a directory are online it is safe toremove any assassins in that directory.
W eak consistency
By allowing access to any file which is online, the above

160

Tim estam pingWhilst a timestamp is used to detect and resolve inconsis­
tencies between copies of a file, any guaranteed monotonically increasing value might be used. If the majority
online constraint is used, then an integer stored in eachcopy of a directory will suffice, the integer being increased
every time a file is created, updated or deleted. An integer
per file (a version number effectively) would also suffice.
RecoveryCareful replacement was used as a means of updating
files. This simplified the prototype implementation, but it
is recognized that such a policy would generally be unsuit­able. Alternative means of roll-forward recovery for files
which fall behind may be considered. For example, anaudit trail might be stored on all online associatedvolumes of a directory when one or more associatedvolumes are offline. Such an audit trail would clearly
depend on the semantics of the operations on the files
involved.

C O N C L U S IO N
This article has attempted to distil some of the ideas
described by Lunn3. A large amount of detail has been
omitted, especially concerning performance, operations
on files, and protection. However, the overlay technique
should be applicable independently of the file accessmethods used. In fact, the technique should be applicableto the naming of objects other than files where multiple

information technology

copy techniques are appropriate. The technique does notdepend upon the implementation loosely described above;
alternative methods of error detection, consistency
resolution, error recovery and directory administration
could readily be devised. Work is continuing at Keele toadapt the overlay technique using the Newcastle
Connection.

2

3
4

ACKNOW LEDGEM ENTS
The above work was undertaken as part of a project
investigating distributed file storage at the .University of
Keele, funded by the Science and Engineering ResearchCouncil; we are duly grateful for their support. Special
thanks are due to Pearl Brereton and Paul Singleton for
their contribution of constructive criticism and expertisein software and hardware.
REFERENCES
1

Sturgis, H, Mitchel, J and Isreal, J ‘Issues in thedesign and use of a distributed filestore’ AC M
Operating Syst. Rev. Vol 14 No 3 (July 1980)

vol 3 no 3 1984

Brownbridge, D R, Marshall, L F and Randell, B
R ‘The Newcastle Connection — or UNIXes of theworld unite!’ Software Pract. <6 Exper. (GB) Vol 12(December 1982) pp 1147-1162
Lunn, K Reliable file storage in a distributed
computing system PhD Thesis, University of Keele(1983)
Lunn, K and Bennett, K H ‘A highly reliable distri­buted filestore directory system’Proc. 2nd Int. Conf
Distrib. Comput. Syst. IEEE catalogue 81 C H I5917 (April 1981) pp 299-307

B IB L IO G R A P H Y
Lamport, L ‘Time, clocks and the ordering of events ina distributed system’ Commun. A C M Vol 21 N o 7(July 1978) pp 558-565
Randell, B, Lee, P A and Treleaven, P C ‘Reliability
issues in computing system design’ Comput. Surv. Vol
10 No 2 (June 1978)
Salter, J H Naming and binding objects, operating
systems — an advanced course Springer-Verlag, FRG(1979) pp 99-208

161