.HTML "Fossil, an Archival File Server... .FP times... .fp 1 R R.nomath... .fp 5 CW LucidaSansCW83.TLFossil, an Archival File Server.AUSean QuinlanJim McKieRuss Coxjmk,rsc@plan9.bell-labs.com.ABThis 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 serverand.CW kfs ,but that is our eventual intent.Both fossil and this documentation areworks in progress.  Comments on either are most welcome..AE.de HP.LP...NH 1Introduction.HPFossil is an archival file server built for Plan 9.In a typical configuration, it maintains a traditional file systemin a local disk partition and periodically archives snapshots of the file systemto a Venti server.  These archives are made available througha file system interface.Fossil can also be run without a Venti server, in which case thesnapshots (if any) occupy local disk space..PPThe bulk of this paper explains the underlying data structures:Venti trees, the Venti archival file system format, and finally Fossil'sfile system format.The end of the paper discusses the architecture of the Fossil server..PPThe presentation of the data structures is very detailed, perhapstoo detailed for most readers.The intent is to record all the details necessary to make structuralchanges to the file system format.Feel free to jump ahead when boredom strikes..NH 1Venti trees and directory hierarchies.HPVenti [3] is an archival block storage server.Once a block is stored, it can be retrieved by presenting the 20-byteSHA1 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 isbroken into fixed size (say,.I psize -byte)chunks, which are stored on the Venti server..I Psize "" (is different from.I dsizeso that we can ensure that each pointer block holds anintegral number of pointers.)This yields a new pointer stream, and so on, until there is a single blockand finally a single score describing the entire tree.The resulting structure looks like:.PS.ps 8.vs 10boxht=0.1boxwid=0.1 B0: box invis wid 1 "\f(CWVtDataType\fP"move right 0.1L0a: box wid 0.2move right 0.1L0b: box wid 0.2move right 0.1L0c: box invis wid 0.2 "..."move right 0.1 L0d: box wid 0.2move right 0.1L0e: box wid 0.2move right 0.2L0f: box invis wid 0.2 "..."move right 0.2 L0g: box wid 0.2move right 0.1L0h: box wid 0.2move right 0.1L0i: box invis wid 0.2 "..."move right 0.1 L0j: box wid 0.2move right 0.1L0k: box wid 0.2move right 0.1L0l: box invis wid 0.2 "..."move right 0.1L0m: 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.4L1abc: 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.LPThe 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 dsizeof 8192 bytesand.I psizeof 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)..PPData blocks are truncated to remove trailing runs of zeros beforestorage to Venti; they are zero-filled back to.I dsizebytes after retrieval from Venti.Similarly, trailing runs of pointers to zero-length blocks areremoved from and added back to pointer blocks.These simple rules happen to make it particularly efficient to storelarge runs of zeros, as might occur in a data stream with ``holes:''the zero-length block itself can be interpreted as a tree of anydepth encoding an all-zero data stream..PPReconstructing the data stream requires the score and type of thetopmost 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 thedepth of the tree and thus the type of the topmost block, but it is convenientto allow trees that are deeper than necessary.)This information is kept in a 40-byte structure called a.CW VtEntry :.P1VtEntry:.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 -bytefield called.CW name .Integers are stored in big-endian order..CW Sizereally is a 48-bit field.).CW Flagsis made up of the following bit fields..P1.ta +\w'      'u +\w'                      'u0x01	VtEntryActive	\fRentry is allocated\fP0x02	VtEntryDir	\fRentry describes a Venti directory (q.v.)\fP0x1C	VtEntryDepthMask	\fRmask for tree depth\fP0x20	VtEntryLocal	\fRreserved (q.v.)\fP.P2.LPThe depth of the described tree is stored in the 3 bits indicated:a tree with a topmost node of type.CW VtPointerType3has depth 4..PPWith.CW VtEntrywe can build more complicated data structures,ones with multiple or nested data streams.A data stream consisting of.CW VtEntrystructures is called a Venti directory.It is identical in structure to the Venti data streamwe described earlier except that the bottom-level type is.CW VtDirType ,andthe.CW VtEntrydescribing a Venti directory has the.CW VtEntryDirflag bit set.The.I dsizefor a Venti directoryis a multiple of 40 so that each data chunk holdsan integer number of.CW VtEntrystructures.By analogy with Venti directories,we call the original data stream aVenti file.Note that Venti files are assumed.I notto contain pointers to other Venti blocks.The only pointers to Venti blocks occur in .CW VtEntrystructures inVenti directories(and in the internal hash tree structure of theindividual 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..PPTo make it easier to pass hierarchies between applications,the root of a hierarchy is described in a 300-byte structurecalled a.CW VtRoot :.P1VtRoot:.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.LPThis structure is stored to Venti and its score is passedbetween applications, typically in the form``\fItype\f(CW:\fIrootscore\fR,''where.I typeis the type field from the.CW VtRootstructure, and.I rootscoreis the score of the.CW VtRootblock..CW VtRootstructures can be chained together using the.I prevfield to encode an archival historyof the data structure..PPFor example, a small Venti hierarchy might look like:.PS.ps 8.vs 10boxwid=0.1boxht=0.1f=0.9mb=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.wline -> from Root.B3 down boxwid/2+0.1+boxwid/2 then to Level1.RootMeta.wline -> from Root.B2 down boxwid/2+0.1+boxwid+0.1+boxwid/2 then to Level1.MetaSource.wline -> 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.wline -> from Level1.SB2 down boxwid/2+0.1+boxwid+0.1+boxwid/2 then to Level2.Source.wline -> 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.LPVenti files are shown as white boxes, while directories are shownas shaded boxes.  Each shaded square represents a.CW VtEntry .Arrows represent pointers from.CW VtEntrystructures to otherVenti files or directories..PPThe hierarchical structure provided by Venti files and directoriescan be used as the base for more complicated data structures.Because this structure captures all the informationabout pointers to other blocks, tools written to traverseVenti hierarchies can traverse the more complicateddata 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 islayered on a Venti hierarchy, .I venti/copycan copy it without fully understanding its structure..NH 1Vac file system format.HPThe Venti archive format.I vacbuilds a traditional file system using a Venti hierarchy.Each vac file is implemented as a Venti file;each vac directory is implemented as a Ventidirectory and a Venti file to provide traditional file system metadata.The metadata is stored in a structure called a.CW DirEntry :.P1DirEntry:.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.P2The notation.CW name[s]denotes a string stored as a two-byte lengthand then that many bytes.The above describes Version 9 of the .CW DirEntryformat.  Versions 7 and 8 are very similar; they can beread by the current.I vacsource code but are not written.Earlier versions were not widespread.A.CW DirEntrymay be followed by optional extension sections, though noneare currently used.The.CW modebits include bits commonly used byUnix and Windows, in addition to those used by Plan 9..PPThe.CW entryfield is an index into the parallel Venti directory.The.CW genfield must match the.CW gen field in the corresponding

Lines 1–500 of 1163. Load more