ref: 217d2f751cae9fd59402bfc7c1f42989d6a2551e
dir: /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.