Date: 28 Sep 1992 10:56:38 -0500
From: Anne Clark <aclark@draper.com>
Subject: Scribing
To: Umesh <umesh@lcs.mit.edu>
Message-Id: <01GPBEFNHA368WW491@ccfvx3.draper.com>
Content-Type: x-see-attachments
Content-Transfer-Encoding: 7BIT

                       Subject:                               Time:10:51 AM
  OFFICE MEMO          Scribing                               Date:9/28/92
I've enclosed a the text file under the name of "filetext."   Send me a message
if there are any problems.

Anne


<<<<<< Attached TEXT file follows >>>>>>
6.826 Principles of Computer System	   	     Fall Semester,1992 

Lecture 4: September 23, 1992

Lecturer: Butler Lampson	   	                         Scribe: Anne Clark

1 Administrative Note

	Problem Set #2  is not due next week.  Instead, it will be due in two week on
October 5, 1992.  Start early!!

2 Simple File Systems (Cont.)

	Today's lecture continues with the description of simple file systems begun
last time with emphasis on the following topics:

	Encoding/Decoding: Representing abstract types in bytes.

	Deterministic State Machines: Given a state and a set of operations on that
state, it is possible to do the sequence of operations at different times and
get the same results.

	Redo Log: Saving a sequence of read/write operations to a log so that
replaying the log gives the same result.  Note: in order for this to work, the
read/write operations must be of the form:

x := v.

3 "Standard" File System Representations

	The representation of files on a disk involves a single directory mapping a
path name to a file which is a collection of data:

Dir = PN -> F
F = D

	The most straightforward way to do this would be to store the data
continuously in a sequence of data blocks, or 

F = DA, I, size:I.

This provides sequentiality which is good for performance, but makes storage
allocation impractical.  Such a method involves the constant reorganization of
a disk.
	Another solution uses a hierarchical approach to represent the file system.  A
tree structure is built where F contains pointers to either data or to another
pointer in a lower level.  Figure 1 gives an example of such a structure where
F equals an I-node containing the data and pointer information.


Figure 1 File System Tree

The problem with this method is that it does not normally have sequentiality. 
While it is possible to provide sequentiality for performance, this in turn
results in the wasting of space.
	A third method for representing a file system is actually a generalization of
the simple sequential one outlined above.  This solution partitions the file
into disk blocks that are found at different disk addresses.  On page 7 of
Handout 9, the concept of extents is explained.  Extents are "references to
contiguous sequences of disk blocks."  They also contain a second entry
carrying the size of the extent's data block, often constant for a system (i.e.
4 kbytes per block).  F is a sequence of these extents that would be
concatenated together to get the data.

E = [da, size : I]

F = Seq E  = Cat ( f {e | ReadBlocks ( e ) } )

Problems with this implementation occur when F is not a reasonable size,
because the file is still being read individually.  This is usually solved by
building a hierarchical structure like the one described above using extents so
that when the file gets too big, it can be chopped up and made into a
multi-level tree.  Most implementations use B-trees to prevent the structure
getting unbalanced and keep the pointers fixed-size with the data in
variable-sized packets.

4 Allocation

	Allocation involves the assigning of free space in order to extend a current
file or form a new one.  This free space is defined as all blocks that are not
reachable from the directory and is constantly changing as data is added and
deleted on the disk.  A file system needs some method of keeping track of what
space is free to prevent data from being lost.  A reasonable invariant for this
is to assume is that a disk address only appears once in an entire file
structure.  This invariant makes writing safe, because in order to assign a block,
it must not already have been used, preventing current data from being
over-written by new data.
	The most basic way of allocating space would be to define reachable data (disk
addresses already in the file structure) as

Reachable (da) = { pn | da is in DA (dir (pn))}.

When another disk block is needed, adding da to a file simply involves saying

VAR da | ~ Reachable (da)

This system is very inefficient, because it explores the entire file system
each time a new disk address is needed.  It is useful though, because when a
more optimized solution is found, we can ask if it is a restriction of above. 
If it is, the new method is proved to be correct without doing a long, tedious
proof.
	A better solution to the free space problem would be to define a variable
"free" which points to a disk address that is not reachable, or

VAR free: DA -> Bool

free (da) =>  ~ Reachable(da).

The standard way of representing free is through a bit table with 1 bit per
disk block.  If the array gets too big, the extent trick is then used.  The
definition of free contains implication instead of equality in order to solve
the problem of making the table persistent.  Each update involves two writes: 
to the disk address of the file and to update the table.  The problem is that a
crash could occur between these two atomic operations.  If the system writes to
a file and then crashes before it updates the table, the disk address could be
allocated to another file, breaking our invariant.  With the implication, it is
permissible to update the table and then the file contents.  If a crash occurs
between the writes, the block is lost, but there is no loss of data.  This can
cause problems after a time if too many blocks are lost, so most systems now
include a garbage collection system.  Many systems also amortize the bit table
by taking a large batch of free addresses at one time so the system is not
slowed down by having to do two writes for each file update.

5 Encoding / Decoding

	Programs are written using abstract types to define variables and
relationships.  This information must be preserved when the data is saved in a
file.  Encoding involves representing these types as sequences of bytes.  Any
system that is used to do this must 1) be total (work for any type T), and 2)
if we decode the information that is encoded, we must get T, or

(for all t ,  T.Decode (T.Encode (t)) = t).

	The standard encoding/decoding technique is called TLV, or Type-Length-Value. 
This method first encodes, in sequence, the type, then the size of the
variable, and finally the variable itself:

ed.enc (x) = EncodeType(x) + (ed.enc(x).size).enc + x.enc.

This technique is completely self-describing, but often carries extra baggage,
needs a naming scheme for the types, and involves the cost of making the
structure.

6 Crash Recovery

	A generic way is needed to deal with stable and volatile variables after a
system has crashed.  The stable variables are not affected by a crash, while
the volatile ones are reset.  We assume that writes to disk blocks are atomic
and will either be completed or not done at all.  Any writes involving larger
sets of data can be interrupted by a crash.  This is not a bad assumption when
you consider that a disk block write only takes about 1ms, which would not be
affected by the system losing power, the most common form of crash.  
	The basic idea is to build a system with both stable and volatile states:

S : state
A : Action = S -> (V,S0

ss (stable state) : S := is
vs (volatile state) : S := is

The system would then need to provide means of doing actions which would affect
the volatile state, a procedure to commit the volatile state to the stable
state, and a crash recovery procedure that copies the stable state into the
volatile one.

DO (a : A) -> V = VAR v | (vs,v) := a (vs)
	RET v

COMMIT ( ) = ss := vs

CRASH ( ) = vs := ss

6.1 Crash Recovery Implementation

	The common way to implement crash recovery is to use a deterministic state
machine with a log containing a list of actions.  The Commit ( ) procedure
involves applying actions to a stable log, sl, while recovery would apply the
actions contained in the log to ss.  This method depends on being able to
atomically assign actions to the log as well as being able to do actions in the
log repeatedly and still get the correct results.  Most implementations
decompose actions into updates (disk blocks) in order to guarantee that the log
is written atomically.
	The abstraction function for this technique is on page 12, Handout 9. 
Briefly, it involves

sl : SEQ U
vl : SEQ U

Abstrac. 	Imple.
ss	=	ss + sl
vs	=	ss + vl

Commit ( ) = sl := vl
Crash ( ) : Redo (replay the sl)