harvey/sys/doc/fossil.ms

.HTML "Fossil, an Archival File Server
... .FP times
... .fp 1 R R.nomath
... .fp 5 CW LucidaSansCW83
.TL
Fossil, an Archival File Server
.AU
Sean Quinlan
Jim McKie
Russ Cox
jmk,rsc@plan9.bell-labs.com
.AB
This paper describes the internals and 
operation of Fossil, an archival file server built for Plan 9.
Fossil has not yet replaced the current Plan 9 file server
and
.CW kfs ,
but that is our eventual intent.
Both fossil and this documentation are
works in progress.  Comments on either are most welcome.
.AE
.de HP
.LP
..
.NH 1
Introduction
.HP
Fossil is an archival file server built for Plan 9.
In a typical configuration, it maintains a traditional file system
in a local disk partition and periodically archives snapshots of the file system
to a Venti server.  These archives are made available through
a file system interface.
Fossil can also be run without a Venti server, in which case the
snapshots (if any) occupy local disk space.
.PP
The bulk of this paper explains the underlying data structures:
Venti trees, the Venti archival file system format, and finally Fossil's
file system format.
The end of the paper discusses the architecture of the Fossil server.
.PP
The presentation of the data structures is very detailed, perhaps
too detailed for most readers.
The intent is to record all the details necessary to make structural
changes to the file system format.
Feel free to jump ahead when boredom strikes.
.NH 1
Venti trees and directory hierarchies
.HP
Venti [3] is an archival block storage server.
Once a block is stored, it can be retrieved by presenting the 20-byte
SHA1 hash of its contents, called a
.I score .
Blocks on Venti have a maximum length of about 56 kilobytes,
though in practice smaller blocks are used.
To store a byte stream of arbitrary length, Venti uses a hash tree.
Conceptually, the data stream is broken into fixed-size (say,
.I dsize -byte)
chunks, which are stored on the Venti server.
The resulting scores are concatenated into a new pointer stream, which is
broken into fixed size (say,
.I psize -byte)
chunks, which are stored on the Venti server.
.I Psize "" (
is different from
.I dsize
so that we can ensure that each pointer block holds an
integral number of pointers.)
This yields a new pointer stream, and so on, until there is a single block
and finally a single score describing the entire tree.
The resulting structure looks like:
.PS
.ps 8
.vs 10
boxht=0.1
boxwid=0.1

B0: box invis wid 1 "\f(CWVtDataType\fP"
move right 0.1
L0a: box wid 0.2
move right 0.1
L0b: box wid 0.2
move right 0.1
L0c: box invis wid 0.2 "..."
move right 0.1

L0d: box wid 0.2
move right 0.1
L0e: box wid 0.2
move right 0.2
L0f: box invis wid 0.2 "..."
move right 0.2

L0g: box wid 0.2
move right 0.1
L0h: box wid 0.2
move right 0.1
L0i: box invis wid 0.2 "..."
move right 0.1

L0j: box wid 0.2
move right 0.1
L0k: box wid 0.2
move right 0.1
L0l: box invis wid 0.2 "..."
move right 0.1
L0m: box wid 0.2

define boxppddd {
	line from 0.2<$1.nw,$1.ne> to 0.2<$1.sw,$1.se>
	line from 0.4<$1.nw,$1.ne> to 0.4<$1.sw,$1.se>
	X: box invis at 0.1<$1.nw,$1.ne>
	Y: box invis at 0.1<$1.sw,$1.se>
	line -> from 0.5<X,Y> to $2.nw
	X: box invis at 0.3<$1.nw,$1.ne>
	Y: box invis at 0.3<$1.sw,$1.se>
	line -> from 0.5<X,Y> to $3.nw
	"..." at 0.7<$1.w,$1.e>
}

define boxppdddp {
	line from 0.2<$1.nw,$1.ne> to 0.2<$1.sw,$1.se>
	line from 0.4<$1.nw,$1.ne> to 0.4<$1.sw,$1.se>
	line from 0.8<$1.nw,$1.ne> to 0.8<$1.sw,$1.se>
	X: box invis at 0.1<$1.nw,$1.ne>
	Y: box invis at 0.1<$1.sw,$1.se>
	line -> from 0.5<X,Y> to $2.nw
	X: box invis at 0.3<$1.nw,$1.ne>
	Y: box invis at 0.3<$1.sw,$1.se>
	line -> from 0.5<X,Y> to $3.nw
	"..." at 0.6<$1.w,$1.e>
	X: box invis at 0.9<$1.nw,$1.ne>
	Y: box invis at 0.9<$1.sw,$1.se>
	line -> from 0.5<X,Y> to $4.nw
}

define boxpdddp {
	line from 0.2<$1.nw,$1.ne> to 0.2<$1.sw,$1.se>
	line from 0.8<$1.nw,$1.ne> to 0.8<$1.sw,$1.se>
	X: box invis at 0.1<$1.nw,$1.ne>
	Y: box invis at 0.1<$1.sw,$1.se>
	line -> from 0.5<X,Y> to $2.nw
	"..." at 0.5<$1.w,$1.e>
	X: box invis at 0.9<$1.nw,$1.ne>
	Y: box invis at 0.9<$1.sw,$1.se>
	line -> from 0.5<X,Y> to $3.nw
}

bhd=0.4
L1abc: box wid 0.5 at 0.5<L0a, L0b>+(0,bhd)
boxppddd(L1abc, L0a, L0b)
L1def: box wid 0.5 at 0.5<L0d, L0e>+(0,bhd)
boxppddd(L1def, L0d, L0e)
L1ghi: box wid 0.5 at 0.5<L0g, L0h>+(0,bhd)
boxppddd(L1ghi, L0g, L0h)
L1jklm: box wid 0.5 at 0.5<L0j, L0k>+(0,bhd)
boxppdddp(L1jklm, L0j, L0k, L0m)
B1: box invis wid 1 "\f(CWVtPointerType0\fP" at B0+(0,bhd)

L2abcdef: box wid 0.5 at 0.5<L1abc,L1def>+(0,bhd)
boxppddd(L2abcdef, L1abc, L1def)
L2ghijklm: box wid 0.5 at 0.5<L1ghi,L1jklm>+(0,bhd)
boxpdddp(L2ghijklm, L1ghi, L1jklm)
B2: box invis wid 1 "\f(CWVtPointerType1\fP" at B1+(0,bhd)

L3atom: box wid 0.5 at 0.5<L2abcdef, L2ghijklm>+(0,bhd)
boxpdddp(L3atom, L2abcdef, L2ghijklm)
B3: box invis wid 1 "\f(CWVtPointerType2\fP" at B2+(0,bhd)
.PE
.LP
The leaves are the original data stream.  Those blocks have type
.CW VtDataType .
The first pointer stream has type
.CW VtPointerType0 ,
the next has type
.CW VtPointerType1 ,
and so on.
The figure ends with a single block of type
.CW VtPointerType2 ,
but in general trees can have height up to
.CW VtPointerType6 .
For a
.I dsize
of 8192 bytes
and
.I psize
of 8180 bytes (409 pointers),
this gives a maximum stream size of approximately 10 zettabytes
(2\s-2\u73\d\s+2 or 10\s-2\u22\d\s+2 bytes).
.PP
Data blocks are truncated to remove trailing runs of zeros before
storage to Venti; they are zero-filled back to
.I dsize
bytes after retrieval from Venti.
Similarly, trailing runs of pointers to zero-length blocks are
removed from and added back to pointer blocks.
These simple rules happen to make it particularly efficient to store
large runs of zeros, as might occur in a data stream with ``holes:''
the zero-length block itself can be interpreted as a tree of any
depth encoding an all-zero data stream.
.PP
Reconstructing the data stream requires the score and type of the
topmost block in the tree, the data chunk size, the pointer chunk size,
and the data stream size.
(From the data stream size and the chunk sizes we could derive the
depth of the tree and thus the type of the topmost block, but it is convenient
to allow trees that are deeper than necessary.)
This information is kept in a 40-byte structure called a
.CW VtEntry :
.P1
VtEntry:
.ta +\w'    'u +\w'            'u
	gen[4]	\fRgeneration number\fP
	psize[2]	\fRsize of pointer blocks\fP
	dsize[2]	\fRsize of data blocks\fP
	flags[1]
	zero[5]
	size[6]	\fRlength of file\fP
	score[20]	\fRscore of root block in tree\fP
.P2
(In this notation,
.CW name[sz]
indicates a
.CW sz -byte
field called
.CW name .
Integers are stored in big-endian order.
.CW Size
really is a 48-bit field.)
.CW Flags
is made up of the following bit fields.
.P1
.ta +\w'      'u +\w'                      'u
0x01	VtEntryActive	\fRentry is allocated\fP
0x02	VtEntryDir	\fRentry describes a Venti directory (q.v.)\fP
0x1C	VtEntryDepthMask	\fRmask for tree depth\fP
0x20	VtEntryLocal	\fRreserved (q.v.)\fP
.P2
.LP
The depth of the described tree is stored in the 3 bits indicated:
a tree with a topmost node of type
.CW VtPointerType3
has depth 4.
.PP
With
.CW VtEntry
we can build more complicated data structures,
ones with multiple or nested data streams.
A data stream consisting of
.CW VtEntry
structures is called a Venti directory.
It is identical in structure to the Venti data stream
we described earlier except that the bottom-level type is
.CW VtDirType ,
and
the
.CW VtEntry
describing a Venti directory has the
.CW VtEntryDir
flag bit set.
The
.I dsize
for a Venti directory
is a multiple of 40 so that each data chunk holds
an integer number of
.CW VtEntry
structures.
By analogy with Venti directories,
we call the original data stream a
Venti file.
Note that Venti files are assumed
.I not
to contain pointers to other Venti blocks.
The only pointers to Venti blocks occur in 
.CW VtEntry
structures in
Venti directories
(and in the internal hash tree structure of the
individual files and directories).
Note also that these directories are nothing more than pointer lists.
In particular, there are no names or metadata like in a file system.
.PP
To make it easier to pass hierarchies between applications,
the root of a hierarchy is described in a 300-byte structure
called a
.CW VtRoot :
.P1
VtRoot:
.ta +\w'    'u +\w'                'u
	version[2]	\f(CW2\fP
	name[128]	\fRname of structure (just a comment)\fP
	type[128]	\fRstring describing structure (\f(CWvac\fR)\f(CW
	score[20]	\fRpointer to \f(CWVtDirType\fP block\f(CW
	blockSize[2]	\fRmaximum block size in structure\fP
	prev[20]	\fRprevious \f(CWVtRoot\fP in chain, if any\fP
.P2
.LP
This structure is stored to Venti and its score is passed
between applications, typically in the form
``\fItype\f(CW:\fIrootscore\fR,''
where
.I type
is the type field from the
.CW VtRoot
structure, and
.I rootscore
is the score of the
.CW VtRoot
block.
.CW VtRoot
structures can be chained together using the
.I prev
field to encode an archival history
of the data structure.
.PP
For example, a small Venti hierarchy might look like:
.PS
.ps 8
.vs 10
boxwid=0.1
boxht=0.1
f=0.9
mb=0.16

VtRoot: [
	right
	B1: box
	move right 0.1
	"\f(CWVtRoot\fP" ljust
]

Root: [
	right
	B1: box fill f
	B2: box fill f
	B3: box fill f
	move right 0.1
] with .nw at VtRoot.sw+(0.2,-.1)
Level1: [
	RootMeta: [
		box wid mb
	]
	MetaSource: [
		right
		B1: box wid 5*mb
	] with .nw at RootMeta.sw+(0,-.1)

	Source: [
		right
		B1: box fill f
		B2: box fill f
		B3: box fill f
		B4: box fill f
		B5: box fill f
		B6: box fill f
		B7: box fill f
		B8: box fill f
	] with .nw at MetaSource.sw+(0,-.1)
	SB1: box invis at Source.B1
	SB2: box invis at Source.B2
	SB3: box invis at Source.B3
] with .nw at Root.sw+(0.4,-.1)
Level2: [
	MetaSource: [
		right
		B1: box wid 5*mb
	] 
	Source: [
		right
		B1: box fill f
		B2: box fill f
		B3: box fill f
		B4: box fill f
		B5: box fill f
		B6: box fill f
		B7: box fill f
		B8: box fill f
	] with .nw at MetaSource.sw+(0,-.1)
	File: box wid 0.8 with .nw at Source.sw+(0,-.1)
] with .nw at Level1.sw+(0.6,-.1)

line -> from VtRoot.B1 down boxwid/2+0.1+boxwid/2 then to Root.w
line -> from Root.B3 down boxwid/2+0.1+boxwid/2 then to Level1.RootMeta.w
line -> from Root.B2 down boxwid/2+0.1+boxwid+0.1+boxwid/2 then to Level1.MetaSource.w
line -> from Root.B1 down boxwid/2+0.1+boxwid+0.1+boxwid+0.1+boxwid/2 then to Level1.Source.w

line -> from Level1.SB3 down boxwid/2+0.1+boxwid/2 then to Level2.MetaSource.w
line -> from Level1.SB2 down boxwid/2+0.1+boxwid+0.1+boxwid/2 then to Level2.Source.w
line -> from Level1.SB1 down boxwid/2+0.1+boxwid+0.1+boxwid+0.1+boxwid/2 then to Level2.File.w

[
	KEY: box wid 1.5 invis "Key"
	line from KEY.sw to KEY.se
	k = -.1
	kk=0.5
	A: [
		box wid 4*boxwid
		"Venti file" ljust with .w at last box .w+(kk,0)
	] with .nw at KEY.sw+(0,2*k)
	B: [
		box fill f
		"Venti entry (\f(CWVtEntry\fP)" ljust with .w at last box .w+(kk,0)
	] with .nw at A.sw+(0,k)
	C: [
		right
		CC: box fill f
		box fill f
		box fill f
		box fill f
		"Venti directory" ljust with .w at CC.w+(kk,0)
	] with .nw at B.sw+(0,k)
	D: [
		line -> right 3*boxwid
		"Venti pointer (score)" ljust with .w at last line .w+(kk, 0)
	] with .nw at C.sw+(0,k)
] with .nw at VtRoot.nw+(3,0)
.PE
.LP
Venti files are shown as white boxes, while directories are shown
as shaded boxes.  Each shaded square represents a
.CW VtEntry .
Arrows represent pointers from
.CW VtEntry
structures to other
Venti files or directories.
.PP
The hierarchical structure provided by Venti files and directories
can be used as the base for more complicated data structures.
Because this structure captures all the information
about pointers to other blocks, tools written to traverse
Venti hierarchies can traverse the more complicated
data structures as well.
For example,
.I venti/copy
(see
.I venti (1))
copies a Venti hierarchy from one Venti server to another,
given the root
.CW VtEntry .
Because the traditional file system described in later sections is
layered on a Venti hierarchy, 
.I venti/copy
can copy it without fully understanding its structure.
.NH 1
Vac file system format
.HP
The Venti archive format
.I vac
builds a traditional file system using a Venti hierarchy.
Each vac file is implemented as a Venti file;
each vac directory is implemented as a Venti
directory and a Venti file to provide traditional file system metadata.
The metadata is stored in a structure called a
.CW DirEntry :
.P1
DirEntry:
.ta +\w'    'u +\w'            'u
	magic[4]	\f(CW0x1c4d9072\fP (DirMagic)\fP
	version[2]	\f(CW9\fP
	elem[s]	\fRname (final path element only)\fP
	entry[4]	\fRentry number for Venti file or directory\fP
	gen[4]	\fRgeneration number\fP
	mentry[4]	\fRentry number for Venti file holding metadata\fP
	mgen[4]	\fRgeneration number\fP
	qid[8]	\fRunique file serial number\fP
	uid[s]	\fRowner\fP
	gid[s]	\fRgroup\fP
	mid[s]	\fRlast modified by\fP
	mtime[4]	\fRlast modification time\fP
	ctime[4]	\fRcreation time\fP
	atime[4]	\fRlast access time\fP
	mode[4]	\fRmode bits\fP
.P2
The notation
.CW name[s]
denotes a string stored as a two-byte length
and then that many bytes.
The above describes Version 9 of the 
.CW DirEntry
format.  Versions 7 and 8 are very similar; they can be
read by the current
.I vac
source code but are not written.
Earlier versions were not widespread.
A
.CW DirEntry
may be followed by optional extension sections, though none
are currently used.
The
.CW mode
bits include bits commonly used by
Unix and Windows, in addition to those used by Plan 9.
.PP
The
.CW entry
field is an index into the parallel Venti directory.
The
.CW gen
field must match the
.CW gen 
field in the corresponding
.CW VtEntry
in the directory;
it is used to detect
stale indices.
Similarly,
.CW mentry
and
.CW mgen
are the index and generation number
for the metadata Venti file,
if the
.CW DirEntry
describes a vac directory.
.PP
The relation between Venti files and directories and
vac files and directories can be seen in this figure:
.PS
.ps 8
.vs 10
boxwid=0.1
boxht=0.1
f=0.9
mb=0.16

VtRoot: [
	right
	B1: box
	move right 0.1
	"\f(CWVtRoot\fP" ljust
]

SuperRoot: [
	right
	B1: box fill f
	move right 0.1
	"fs root block" ljust
] with .nw at VtRoot.sw + (0.2, -.2)
Root: [
	right
	B1: box fill f
	B2: box fill f
	B3: box fill f
	move right 0.1
	"root directory info block" ljust
] with .nw at SuperRoot.sw+(0.2, -.2)
Level1: [
	RootMeta: [
		box wid mb
		move right 0.1
		"root metadata" ljust
	]
	MetaSource: [
		right
		B1: box wid mb
		B2: box wid mb
		B3: box wid mb
		B4: box wid mb
		B5: box wid mb
	] with .nw at RootMeta.sw+(0,-.2)
	MB1: box wid mb invis at MetaSource.B1
	MB2: box wid mb invis at MetaSource.B2
	MB3: box wid mb invis at MetaSource.B3
	MB4: box wid mb invis at MetaSource.B4
	MB5: box wid mb invis at MetaSource.B5

	Source: [
		right
		B1: box fill f
		B2: box fill f
		B3: box fill f
		B4: box fill f
		B5: box fill f
		B6: box fill f
		B7: box fill f
		B8: box fill f
	] with .nw at MetaSource.sw+(0,-.1)
	SB1: box invis at Source.B1
	SB2: box invis at Source.B2
	SB3: box invis at Source.B3
	SB4: box invis at Source.B4
	SB5: box invis at Source.B5
	SB6: box invis at Source.B6
	SB7: box invis at Source.B7
	SB8: box invis at Source.B8
] with .nw at Root.sw+(0.4,-.2)
Level2: [
	MetaSource: [
		right
		B1: box wid mb
		B2: box wid mb
		B3: box wid mb
		B4: box wid mb
		B5: box wid mb
	] 
	Source: [
		right
		B1: box fill f
		B2: box fill f
		B3: box fill f
		B4: box fill f
		B5: box fill f
		B6: box fill f
		B7: box fill f
		B8: box fill f
	] with .nw at MetaSource.sw+(0,-.1)
	File: box wid 0.8 with .nw at Source.sw+(0,-.2)
] with .nw at Level1.sw+(0.6,-.2)

line -> from VtRoot.B1 down boxwid/2+0.2+boxwid/2 then to SuperRoot.w
line -> from SuperRoot.B1 down boxwid/2+0.2+boxwid/2 then to Root.w
line -> from Root.B3 down boxwid/2+0.2+boxwid/2 then to Level1.RootMeta.w
line -> from Root.B2 down boxwid/2+0.2+boxwid+0.2+boxwid/2 then to Level1.MetaSource.w
line -> from Root.B1 down boxwid/2+0.2+boxwid+0.1+boxwid+0.2+boxwid/2 then to Level1.Source.w

line -> from Level1.SB3 down boxwid/2+0.2+boxwid/2 then to Level2.MetaSource.w
line -> from Level1.SB2 down boxwid/2+0.2+boxwid+0.1+boxwid/2 then to Level2.Source.w
line -> from Level1.SB1 down boxwid/2+0.2+boxwid+0.1+boxwid+0.2+boxwid/2 then to Level2.File.w

arrowwid = arrowwid/2
arrowht = arrowht/2
line -> from Level1.MB1 to Level1.SB1.n
line -> from Level1.MB2 to Level1.SB2.n
line -> from Level1.MB2 to Level1.SB3.n
line -> from Level1.MB4 to Level1.SB7.n
line -> from Level1.MB5 to Level1.SB5.n
arrowwid = arrowwid * 2
arrowht = arrowht * 2

box dashed with .nw at Level1.MetaSource.nw+(-.05,.05) wid 0.8+.05*2 ht .3+.05*2
box dashed with .nw at Level2.MetaSource.nw+(-.05,.05) wid 0.8+.05*2 ht .3+.05*2
box dotted with .nw at Level2.File.nw+(-.05,.05) wid 0.8+0.05*2 ht .1+.05*2

[
	KEY: box wid 1.5 invis "Key"
	line from KEY.sw to KEY.se
	k = -.1
	kk=0.5
	A: [
		box wid 4*boxwid
		"Venti file" ljust with .w at last box .w+(kk,0)
	] with .nw at KEY.sw+(0,2*k)
	B: [
		box fill f
		"Venti entry (\f(CWEntry\fP)" ljust with .w at last box .w+(kk,0)
	] with .nw at A.sw+(0,k)
	C: [
		right
		CC: box fill f
		box fill f
		box fill f
		box fill f
		"Venti directory" ljust with .w at CC.w+(kk,0)
	] with .nw at B.sw+(0,k)
	D: [
		line -> right 3*boxwid
		"Venti pointer (score)" ljust with .w at last line .w+(kk, 0)
	] with .nw at C.sw+(0,k)
	DD: [
		box dotted wid 4*boxwid
		"Vac file" ljust with .w at last box .w+(kk,0)
	] with .nw at D.sw+(0,k)
	E: [
		box wid mb
		"Vac entry (\f(CWDirEntry\fP)" ljust with .w at last box .w+(kk,0)
	] with .nw at DD.sw+(0,k)
	G: [
		box dashed wid 4*boxwid
		"Vac directory" ljust with .w at last box .w+(kk,0)
	] with .nw at E.sw+(0,k)
	H: [
		arrowwid = arrowwid/2
		arrowht = arrowht/2
		line -> right 1.5*boxwid
		"Vac pointer (integer index)" ljust with .w at last line .w+(kk, 0)
		arrowwid = arrowwid * 2
		arrowht = arrowht * 2
	] with .nw at G.sw+(0,k)
] with .nw at VtRoot.nw+(3,0)
.PE
.LP
In reality, the story is slightly more complicated.
The metadata file in a Vac directory
is not just the concatenation of
.CW DirEntry
structures.
Instead, it is the concatenation of
.CW MetaBlocks .
A
.CW MetaBlock
contains some number of
.CW DirEntry
structures along with a sorted index to make it easy
to look for a particular
.CW DirEntry
by its
.CW elem 
field.
The details are in the source code.
.PP
As shown in the diagram,
the root directory of the file system is summarized by
three
.CW VtEntry
structures describing
the Venti directory for the children of the root,
the Venti file for the metadata describing the children of the root,
and a Venti file holding metadata for the root directory itself.
These
.CW VtEntry
structures are placed in a Venti directory of their own,
described by the single 
.CW VtEntry
in the
root block.
.NH 1
Fossil file system format
.HP
Fossil uses the vac format, with some small changes.
The changes only affect the data on the local disk; the data
archived to Venti is exactly in vac format.
.PP
Blocks stored on local disk may contain scores pointing at local disk
blocks or at Venti blocks. 
Local block addresses are stored as 20-byte scores in which the first 16 bytes
are all zero and the last 4 bytes specify a block number in the disk.
Before a block is archived, all the
blocks it points to must be archived, and the local scores in the block
must be changed to Venti scores.
Using block addresses rather than content hashes for local data
makes the local file system easier to manage: if a local block's contents
change, the pointer to the block does not need to change.
.NH 2
Snapshots
.HP
Fossil is an archival file server.
It takes periodic snapshots of the file system,
which are made accessible through the file system.
Specifically, the active file system is presented in
.CW /active .
Ephemeral snapshots (those that are kept on local disk and eventually deleted)
are presented in
\f(CW/snapshot/\fIyyyy\f(CW/\fImmdd\f(CW/\fIhhmm\fR,
where
.I yyyy
is the full year,
.I mm
is the month number,
.I dd
is the day number,
.I hh
is the hour,
and
.I mm
is the minute.
Archival snapshots (those that are archived to Venti and persist forever)
are presented in
\f(CW/archive/\fIyyyy\f(CW/\fImmdds\fR,
where
.I yyyy ,
.I mm ,
and
.I dd
are year, month, and day as before,
and
.I s
is a sequence number if more than one
archival snapshot is done in a day.
For the first snapshot,
.I s
is null.
For the subsequent snapshots,
.I s
is
.CW .1 ,
.CW .2 ,
.CW .3 ,
etc.
.PP
To implement the snapshots, the file server maintains a
current
.I epoch
for the active file system.
Each local block has a label that records, among other things,
the epoch in which the block was allocated.
If a block was allocated in an epoch earlier than the current one,
it is immutable and treated as copy-on-write.
Taking a snapshot can be accomplished by
recording the address of the current root block and then 
incrementing the epoch number.
Notice that the copy-on-write method makes
snapshots both time efficient and space efficient.
The only time cost is waiting for all current file system
requests to finish and then incrementing a counter.
After a snapshot, blocks only get copied when they are
next modified, so the per-snapshot
space requirement is proportional
to the amount of new data rather than the total
size of the file system.
.PP
The blocks in the archival snapshots are moved to Venti,
but the blocks in the ephemeral snapshots take up space
in the local disk file.
To allow reclamation of this disk space, the file system
maintains a 
.I low
.I epoch ,
which is the epoch of the earliest ephemeral snapshot
still available.
Fossil only allows access to snapshots with epoch numbers
between the 
low epoch and the current epoch
(also called the high epoch).
Incrementing the low epoch thus makes old
snapshots inaccessible.
The space required to store those snapshots can then
be reclaimed, as described below.
.NH 2
Local blocks
.HP
The bulk of the local disk file is the local blocks.
Each block has a 14-byte label associated with it, of the format:
.P1
Label:
.ta +\w'    'u +\w'                'u
	state[1]	\fRblock state\fP
	type[1]	\fRblock type\fP
	epoch[4]	\fRallocation epoch\fP
	epochClose[4]	\fRclose epoch\fP
	tag[4]	\fRrandom tag\fP
.P2
.LP
The
.CW type
is an analogue of the block types described earlier,
though different names are used, to distinguish between
pointers blocks in a hash tree for a data stream
and pointer blocks for a directory stream.
The
.CW epoch
was mentioned in the last section.
The other fields are explained below.
.PP
There are two distinguished blocks states
.CW BsFree
.CW 0x00 ) (
and
.CW BsBad
.CW 0xFF ), (
which mark blocks that are available for allocation
and blocks that are bad and should be avoided.
If
.CW state
is not one of these values, it is a bitwise
.I or ' `
of the following flags:
.P1
.ta +\w'      'u +\w'                'u
0x01	BsAlloc	\fRblock is in use\fP
0x02	BsCopied	\fRblock has been copied\fP
0x04	BsVenti	\fRblock has been stored on Venti\fP
0x08	BsClosed	\fRblock has been unlinked from active file system\fP
.P2
.LP
The flags are explained as they arise in the discussions below.
.PP
It is convenient to store some extra fields in the
.CW VtEntry
structure when it describes a Venti file or directory
stored on local disk.
Specifically, we set the
.CW VtEntryLocal
flag bit
and then use the bytes 7-16 of the score (which would
otherwise be zero, since it is a local score) to hold these fields:
.P1
.ta +\w'    'u +\w'                'u
	archive[1]	\fRboolean: this is an archival snapshot\fP
	snap[4]	\fRepoch number if root of snapshot\fP
	tag[4]	\fRrandom tag\fP
.P2
.LP
The extended
.CW VtEntry
structure is called an
.CW Entry .
The
.CW tag
field
in the
.CW Label
and the
.CW Entry
is used to identify dangling pointers or other file system corruption:
all the local blocks in a hash tree must
have tags matching the tag in the
.CW Entry .
If this
.CW Entry
points at the root of a snapshot,
the
.CW snap
field is the epoch of the snapshot.
If the snapshot is intended to be archived to Venti,
the
.CW archive
field is non-zero.
.NH 2
Block reclamation
.HP
The blocks in the active file system form a tree: each
block has only one parent.
Once a copy-on-write block 
.I b
is replaced by its copy, it is no longer
needed by the active file system.
At this point,
.I b
is unlinked from the active file system.
We say that
.I b
is now
.I closed :
it is needed only for snapshots.
When a block is closed, the
.CW BsClosed
bit is set in its state, and the current epoch (called the block's closing epoch)
is stored in the
.CW epochClose
label field.
(Open blocks have an
.CW epochClose
of
.CW ~0 ).
.PP
A block is referenced by snapshots with epochs
between the block's allocation epoch and its closing epoch.
Once the file system's low epoch grows to be greater than or equal to the block's
closing epoch, the block is no longer needed for any snapshots
and can be reused.
.PP
In a typical configuration, where nightly archival snapshots
are taken and written to Venti, it is desirable to reclaim
the space occupied by now-archived blocks if possible.
To do this, Fossil keeps track of whether the pointers
in each block are unique to that block.
When a block
.I bb
is allocated, a pointer to
.I bb
is written into exactly one active block (say,
.I b ).
In the absence of snapshots, the pointer to
.I bb
will remain unique to
.I b ,
so that if the pointer is zeroed,
.I bb
can be immediately reused.
Snapshots complicate this invariant:
when
.I b
is copied-on-write, all its pointers
are no longer unique to it.
At time of the copy, the
.CW BsCopied
state bit in the block's label
is set to note the duplication of the pointers contained within.
.NH 2
Disk layout
.HP
The file system header describes the file system layout and has this format:
.P1
.ta +\w'    'u +\w'                'u
Header:
	magic[4]	\fR0x3776AE89 (HeaderMagic)\fP
	version[2]	\fR1 (HeaderVersion)\fP
	blockSize[2]	\fIfile system block size\fP
	super[4]	\fRblock offset of super block\fP
	label[4]	\fRblock offset of labels\fP
	data[4]	\fRdata blocks\fP
	end[4]	\fRend of file system\fP
.P2
.LP
The corresponding file system layout is:
.PS
.ps 8
.vs 9
boxwid=0.75
boxht=0.15
Empty: box "empty" ht 0.25
Header: box "header" with .n at Empty.s
Empty2: box "empty" with .n at Header.s
Super: box "super block" with .n at Empty2.s
Label: box "label" "blocks" with .n at Super.s ht 0.25
Data: box "data" "blocks" with .n at Label.s ht 0.3
"  0" ljust at Empty.ne
"  128kB" ljust at Header.ne
"  \f5super\fP \(mu \f(CWblockSize\fP" ljust at Super.ne
"  \f5label\fP \(mu \f(CWblockSize\fP" ljust at Label.ne
"  \f5data\fP \(mu \f(CWblockSize\fP" ljust at Data.ne
"  \f5end\fP \(mu \f(CWblockSize\fP" ljust at Data.se
"" at (-1,0)
"" at (6,0)
.PE
.LP
The numbers to the right of the blocks are byte offsets
of the boundaries.
.LP
The super block describes the file system itself and looks like:
.P1
.ta +\w'    'u +\w'                'u
Super:
	magic[4]	\fR0x2340A3B1 (SuperMagic)\fP
	version[2]	\fR1 (SuperVersion)\fP
	epochLow[4]	\fRfile system low epoch\fP
	epochHigh[4]	\fRfile system high (active) epoch\fP
	qid[8]	\fRnext qid to allocate\fP
	active[4]	\fRdata block number: root of active file system\fP
	next[4]	\fRdata block number: root of next file system to archive\fP
	current[4]	\fRdata block number: root of file system currently being archived\fP
	last[20]	\fRVenti score of last successful archive\fP
	name[128]	\fRname of file system (just a comment)\fP
.P2
.LP
.NH 1
Fossil server
.HP
The Fossil server is a user-space program that runs on a standard Plan 9 kernel.
.NH 2
Process structure
.PP
The file server is structured as a set of processes synchronizing
mostly through message passing along queues.
The processes are given names, which can be seen in the output of
.CW ps 
.CW -a .
.PP
.CW Listen
processes announce on various network addresses.
A
.CW con
process handles each incoming connection, reading 9P requests
and adding them to a central message queue.
.CW Msg
processes remove 9P requests from the queue,
handle them, and write the responses to the appropriate
file descriptors.
.PP
The
.CW disk
process handles disk I/O requests made by the other processes.
The
.CW flush
process writes dirty blocks from the in-memory block cache to disk.
The
.CW unlink
process frees previously linked blocks once the blocks that point at them
have been written to disk.
.PP
A
.CW consI
reads from each console file (typically a pipe posted in
.CW /srv ),
adding the typed characters to the input queue.
The
.CW cons
process echoes input and runs the commands, saving
output in a ring buffer.
Because there is only one
.CW cons
process, only one console command may be executing at a time.
A
.CW consO
process copies this ring buffer to each console file.
.PP
The
.CW periodic
process runs periodic events, like
flushing the root metadata to disk or
taking snapshots of the file system.
.NH 2
Block cache
.HP
Fossil maintains an in-memory block cache which 
holds both local disk blocks and Venti blocks.
Cache eviction follows a least recently used policy.
Dirty blocks are restricted to at most half the cache.
This can be changed by editing
.CW DirtyPercentage
in 
.CW dat.h .
.PP
The block cache uses soft updates [1] to ensure that the on-disk
file system is always self-consistent.
Thus there is no
.I halt
console command
and no need to check a file system 
that was shut down without halting.
.NH 2
Archiving
.HP
A background process writes blocks in archival snapshots to Venti.
Although
.CW /archive/\fIyyyy\fP/\fImmdds\fR
is a copy of only
.CW /active
at the time of the snapshot,
the archival process archives the
entire file tree rather than just
the subtree rooted at
.CW /active .
The snapshots
.CW /snapshot/\fIyyyy\fP/\fImmdd\fP/\fIhhmm
are stored as empty directories.
Once all the blocks have been archived,
a 
.CW VtRoot
header for the file system is archived.
The score of that header is recorded in
.CW super.score
and also printed on the file server console.
The score can used by
.I flfmt
to restore a file system (see
.I fossil (4)).
.NH 2
Contrast with the old file server
.HP
The most obvious difference between Fossil and the 
old Plan 9 file server [2] is that Fossil uses a Venti server as 
its archival storage in place of a WORM juke box.
There are a few other architectural differences to be 
aware of.
.PP
Fossil is a user-level program run on a standard kernel.
.PP
Fossil does not have any way to concatenate, stripe, or
mirror disk files.  For functionality similar to the old file server's
configuration strings, use the experimental file stack device 
(see
.I fs (3)).
.PP
Fossil speaks only 9P2000.  Old 9P (aka 9P1) is not supported.
.PP
... XXX words about converting an old file system to fossil?
.NH 1
References
.LP
[1] Gregory R. Ganger, Marshall Kirk McKusick, Craig A. N. Soules,
and Yale N. Patt.
``Soft Updates: A Solution to the Metadata Update Problem
in File Systems,''
.I "ACM Transactions on Computer Systems" ,
Vol 18., No. 2, May 2000, pp. 127\-153.
.LP
[2] Sean Quinlan, ``A Cached WORM File System,''
.I "Software\(emPractice and Experience" ,
Vol 21., No 12., December 1991, pp. 1289\-1299.
.LP
[3] Sean Quinlan and Sean Dorward, ``Venti: A New Approach to Archival Storage,''
.I "Usenix Conference on File and Storage Technologies" ,
2002.