Subject: Re: File Structure for Disk Doubler

From: [email-masked] (Paul E. Campbell)
Date: 2 Dec 1994 17:04:38 -0500

Art Pollard ([email-masked]) wrote:
: I am familier with the Log Structured File System (Sprite) which has been 
: used in one study (by DEC) to create a compressed file system.  However, 
: the resources for this method are too great for a mere PC.  There are 
: several other approaches simular to this with which I am familier 
: however, they all have memory requirements which are too great for PCs or 
: would fragment too quickly to support the high sequential access 
: across blocks needed while reading a file efficiently.

This is what I worked out when I had the time and desire to build a log
structured file system (I no longer have the time)...

First, you need to do a fast compression routine.

Second, on average, most systems use say 8-16K block sizes for good
compression. 4K is really too small.

Third, the way the LFS structures work is pretty good assuming you have that
1 megabyte free to use for those purposes. So this is my proposed alternative:

First, the segment idea is sound.

Instead of keeping it in memory, do this:

Continuously ADD to the current segment as you get stuff to write to it. This
may entail more writing than the other methods (oh well...). Trust your system
at least enough to do some caching. On the first pass, don't worry about
following a block size requirement religiously.

Store each new chunk of data sequentially in the log. Store EVERYTHING in
8-16K chunks. Pack in the data as close to your arbitrary size as possible.
Put a CRC on each chunk. That way, when you have to restart (someone shuts
off the machine), just start reading in the last segment you marked as in
use (in your "superblock" equivalent). Keep reading blocks until you fail to
get a good CRC. Even put file pointers in these "chunks".

Pointers to "sectors" or other arbitrary pieces of files look like this:
<Segment #>,<Block start>,<Block offset>

That way, you can find the right block to read with:
Offset=<Segment #>*segment size+Block start

When writing, the rule for whether to write to the current block or start a
new one is simple:
Known:	The size of the block so far
	The desired block size
	The size of the data to write out (no compression)
If (Desired block size-Current size)>(size needed), append it

Then when you finish your write, stick on the extra bits for "end of block"
and CRC. When you write again, you start on the current sector where the
"end of block" section is at, but overwrite that part (you end up rewriting
a few bytes but that doesn't matter too much). Caching helps reduce the
number of writes and rewrites you'd normally end up doing.

As far as DOS's usual "FAT's" or the equivalent structures in Unix systems,
you don't use them. You supply both OS's with as much of a legitimate view
of the system (given their myopic view of the world) as possible and handle
everything else yourself.

The advantage of this system is that you get compression, the advantages of
a log structured system, and low memory overhead.