Subject: Linux-Development Digest #836
From: Digestifier <Linux-Development-Request@senator-bedfellow.MIT.EDU>
To: Linux-Development@senator-bedfellow.MIT.EDU
Reply-To: Linux-Development@senator-bedfellow.MIT.EDU
Date:     Thu, 16 Jun 94 08:13:09 EDT

Linux-Development Digest #836, Volume #1         Thu, 16 Jun 94 08:13:09 EDT

Contents:
  Re: Filesystem semantics protecting meta data ... and users data (Totally Lost)

----------------------------------------------------------------------------

Crossposted-To: comp.benchmarks,comp.sys.sun.admin,comp.security.unix
From: idletime@netcom.com (Totally Lost)
Subject: Re: Filesystem semantics protecting meta data ... and users data
Date: Thu, 16 Jun 1994 00:07:07 GMT

In article <2tn6pd$5gr@fido.asd.sgi.com>,
Adam Sweeney <ajs@spareme.engr.sgi.com> wrote:
>>a file corrupted with zeros is still corrupted ... not a security
>>risk unless the file is critical to use of a system and causes
>>another form of fault that exposes you.
>>
>>The point is that file corruption, in particular undetectable
>>file corrupt is not necessary.
>
>So far your proposal seems to have been to order all writes
>to file data before any of the meta-data writes which will make
>that data permanent.  While that will probably work for newly
>written files, it doesn't do much for the consistency of
>multi-block updates to an existing file unless you go to a
>no-overwrite scheme and commit all of meta-data atomically.

Actually there is a subtle difference between what I ask for/require
and how you interpret it. I require that all data be written prior
to meta data that points to it ... period. This doesn't imply
that all data be written before any meta data for the file.
And certainly allows the filesystem to checkpoint along the
way with minimal performance lost, and a huge gain over current
sync write of all meta data.

>It seems to me that what you want is transactional file update,
>where both the meta-data and the data are protected by the
>transaction.  Is that accurate?  I think this would be very
>useful functionality for the examples you've given, i.e. mail
>files, log files, password files.  I wouldn't go so far as
>to say that all file updates require such strict behavior.

I clearly stated that while I think that multifile transactional
updates are a very good thing for any standard unix platform,
I was not mandating that this proposal be tied to it.
My point is that async ordered writes as proposed are faster than
async data and sync meta data as currently practed by nearly all
filesystem designs. This applies to all type of files.

I will go so far as to say that if a file contains any data other
than written at a crash point it will greatly increase the
recovery applications work for that file type. I will go on
to say it should be required of any filesystem to indicate
which files may be corrupt after a crash as a minimally
required function to aid the sysadm and production staff
to get the system consistant again short of rolling back
to a known checkpoint..

>
>For example, we had a customer here at SGI who was very upset
>that EFS would eat their 300 MB log file when they crashed.
>Well, it at their file because EFS was using a scheme very
>similar to what you've been proposing.  The inode would not
>go to disk until all of the data in the file had.  Since they
>never stopped writing the file long enough for this to happen
>the inode never went to disk.  We've changed the behavior of
>EFS now so that the parts of the file which have made it to
>disk become permanent, but this is just an example of how
>your all or nothing argument does not satisfy everyone.

This case is not necesary and represents a short sighted view
of the requirements. see above ...

I never made an all or nothing arguement ... please quote what
you think forms this requirement.

>
>In my opinion, what would be really nice would be multfile
>transactional file update.  Of course, this requires a
>concurrency control mechanism and all that, but it would
>be handy.  What I see at work, however, is that customers
>are not asking for this.  They want huge files with huge
>data rates to and from the files.  They want huge file systems
>that don't take days to bring back online.  Nobody asks
>for perfect data consistency semantics.

Ditto on transactional file updates as said here and elsewhere.
However your market segment has biases in file activity
that are not mirrored in 99% of the remaining market. As does
one of my clients in the medical imaging business that uses
your equipment. That aside 99% of that same clients inhouse
work on SGI development stations follows normal file usage
distributions where the ordered write issue is important,
as does a number of other production usages.

Nobody asks ... probably true ... I think most assume (falsely)
the reliability exists and seldom see a failing case that would worry
them. Being enlightened you might say, I see many unix
applications that scare the shit out of me knowing
what can (and has in several cases) happened to critical
data that peoples lives depend on.

All the pharmacies systems running on SCO XENIX/UNIX and other PC UNIX's
are time bombs from my point of view ... going to kill somebody
or leave them with unnecessary damage.

>Oh well, maybe someday.

I'm hoping soon, like one release life cycle away at most.
In talking with several DEC guys over this, with Advfs they hit
damn close and will probably be to market with a safe
filesystem before the rest of you guys.

>Adam Sweeney
>MTS
>Media Systems Division
>Silicon Graphics, Inc.


Since comp.os.research doesn't seem to want to handle this thread
-- my last two postings with comp.os.research included seemed to
get /dev/null'ed -- I'll go ahead in follow it here for the lack of
a better place.

One of my side arguments is that a good filesystem design would
make RAID boxes a white elephant ... instead filesystem people
at places like SGI seem to want to institutionalize them.  Any OS
on a fast enough peice of iron should be able to run circles around
any raid box since the OS with CORRECT cache mangement policy
should leave an uncachable stream visible to the raid box.
That would make any cache memory in the raid box over and above
flow buffering a total waste.

Instead I feel stupid as hell having to recommend a raid box
for my clients SGI systems because you guys don't have it
together yet.

For a look into my view of how a filesystem should look, try
the following which I prepared as a first deliverable to SCO
on contracts that never materialized. While I held off giving
them the document to slow down the Not-Inventeed-Here We-can-do-better
game - each of the facts below were presented to one or more of
the SCO team at Santa Cruz. Kip, Brian, Dean, Jeff, Michael Taht
and a few others should remember the lectures as will several of my
former staff that worked on the Altos port.

The core parts of this design happened 1981 thru 1988, then refined
at SCO during 1989 to 1992. I dusted it off in Jan this year while
tring to reopen this with the SCO London team, but they were not
serious enough to proceed past a friendly handshake. Changes of
this degree takes some serious kernel hacking. More than just an
idle weekend's play.


============================= Cut here ===============================




                  Exploring DFS (DMS Design File System)

                                  and

                       DFS Functional Specification

                               John L. Bass
                                DMS Design

                               Aug 22, 1990
                           (Revised Jul 10, 1991)
                           (Revised Jan 14, 1994)





Overview

   Current file system designs are cripled by poor locality, excessive cpu
requirements, out dated architecture, excessive rotational latency losses,
excessive seek time, and poor reliability. Various architecture and
implementation problem areas that current file systems and disk subsystems
are crippled by are brought together in this paper along with innovative
new approaches to the problems.

   These concepts and goals include:

      Replacing poor data management strategies for volumes, logical
      volumes, partitions, mirroring, stripping, and RAID parity with a
      unified multiple spindle file system that has built-in smart
      replacements for these policies on a file by file basis.

      Replacing block-at-a-time with file-at-a-time strategies which
      include semi-continugous extent based allocations of memory and disk
      spaces to reduce allocation overheads. Strict ordering of meta data
      and file data writing to provide crash security and reliability.

      Replacing early binding (allocating disk addresses when buffers are
      allocated) with late binding (allocating disk addresses just before
      writing the data) to improve locality and disk usage.

      Replacing existing file system, BIO, and driver interfaces to
      implement these new policies, rearrange policy/functionality, and
      provide new layered standardized device interfaces with simplified
      control paths between the file system and drivers.

      Replacing existing FIFO block and inode caches with heuristic
      statistical caches to greatly improve cache performance and memory
      utilization. Keep usage profiles gathered by file and directory.

      Reducing typical disk I/O's per small to medium sized file accessed,
      to an average of two or less, including directory operations for a
      busy system. A combination of caching, clustering, and revised
      on disk data structures will be used to achieve this goal.

      Replacing current disk allocation and sorting policy to reduce the
      total seek and rotational latency time for drives by 80% or more.










Policies for Disk, Logical Volume and Partition Management

   Under DFS multiple disks, each with a single active partition, will
contain independent filesystems, treated as unified parallel file system. 
Per file replication and parity group selection replaces partition
mirroring and RAID paritiy requirements as needed for reliability.
Per file stripping allows key large files to span disks, load balance,
and achieve higher thruput with concurrent multiple disk accesses. An
integrated backup and data migration manager transparently handles block
addressable tapes and removeable disks to extend the filesystem space,
especially where an automated changer (jukebox) is available. Sequential
tapes can be used for traditional serial archives that also can be
transparently mounted as filesystems, abeit very slow. Automatic
compression is also a per file/directory selectable attribute.

   Current high level data management policy is to sub-divide disks into
multiple partitions. These partitions may then be combined with mirroring,
stripping or simple concatenation to form logical partitions used for
file systems and swap or paging space. The reliability of stripped
partitions can be improved by using mirroring or parity, available in
several different forms (aka RAID) to offset the reliability problems
associated with spanning file systems across multiple drives. The per
file/directory selectable attributes in DFS combined with automatic
heuristics used in DFS data migration obsolete these older high level
data management policies.

   Use of multiple active partitions introduces severe performance losses
caused by excessive seeking and reduced locality of data over a single
partition design. Paritions also fragment and distribute disk free space
causing increased freespace management problems, including inability to
handle large files even though enough distributed free space is available.

   |-------------------------- single disk ---------------------------|
   |----- Partition 1 -----|                   |---- Partition N -----|
    inodes files  freespace                     inodes files freespace

     |----------------  wasted seeks  --------------|
                     |------------wasted seeks ------------------|

With this typical disk layout long expensive and unnecessary seeks
are generated by using partitions which can be avoided with a single
partition spanning the drive. There is also no incentive to develop
file system strategies that enhance locality since the volume/partition
managment interfere with locality optimization.

   Traditional Enhanced UNIX filesystems like Berkeley's UFS and LFS
specifically distroy locality. UFS does this with load balancing cylinder
groups. LFS does it by the very nature of using the entire disk as a
rolling log. Except for certain educational servers with small quota's
this policy is both wrong and worse than a traditional UNIX filesystem
(especially where bit-mapped free lists are used).

   Under DFS active heuristics and data migration policies combine to
highly localize active disk regions, nearly eliminating unnecessary
wasted rotational latency and seeks over unused data. A typical DFS
partition is organized as:

   |-------------------------- single disk ---------------------------|
    Very Active Files         Stale Files               Archived Files

where Very Active Files are files receintly created or accessed. These
files are typically automatically replicated for reliability and
enhanced retrieval performance. For files that have a continuously
high access rate they may be replicated multiple times, both on the
same spindle and across spindles to enhance retrieval times. Files
that have a history of repeated one day to one week access intervals
will be held in the stale area. Files that have a history of repeated 
longer term accesses will be held in the archive area. Files in the Stale
and Archive areas are never replicated (mirrored), instead they are
clustered into groups with multiple parity vectors. The Archived clusters
differ from Stale clusters in that they are also compressed.

   Both Fixed and Removable DFS volumes represent a complete independent
parallel filesystem rooted at /. Key paths are cached and chained
internally on mount. An unrestricted name search will always select
the latest version of a file. A naming syntax exists to select a
particular version of a file when multiple versions exist (IE a backup
volume is mounted or versioning is enabled). In addition a volume may
be mounted with an implied prefix to it's root, or only a portion of the
volume may be mounted by selecting a specific directory path to be
rooted at the (possibly prefixed) root.

   If multiple copies of a selected file version exist, all are presented
to the I/O queue upon access and the first device ready to service the
request will mark it BUSY which causes other devices to ignore the request
but keep it in their queue until the request is posted DONE. If a device
servicing a request encounters an error it removes BUSY and allows an
alternate device to attempt servicing it. Writes are handled very
similarly with a couple extensions to support writing the data to multiple
disks/tapes with a single queued request. A priority scheme is used
to schedule both I/O requests and cache usage which follows a processes
dynamic priority and niceness. The filesystem charges each process for
it's I/O usage and decay's it over time as with CPU usage. These
strategies provides superior process management, cache management,
load balancing, and error recovery strategies over traditional designs.

   With a jukebox present, files will transparently migrate between
fixed disks and archive media upon reference or going stale. Without
a jukebox an operator interface is provided to handle volume change
requests. Using this feature a fast crash recovery is possible allowing
even giga/terabyte sized filesystems to come back online while recovery
restores are in progress with specially constructed logical image backups
which have files sorted by reference history. Multiple archive devices
can be used in parallel to speed generation and recovery from logical
image backups.

   At boot time, all configured fixed disks, removable disks, and ready
tape drives which have an automount flag set in the the super block will
be mounted. At any idle period, each file system volume will go to sleep
by flushing caches to the media. Should the system crash during a sleep
period the disk will be known as consistant at startup, with the
exception of flagged open written files.




Policies for Directory, File, Free Space management.   

   While DFS still uses metadata objects like a super block, inodes,
indirect blocks, and directories - how they are used and maintained
in memory and on disk varies greatly from traditional practice. First
extents are used to describe the blocks used to store file and directory
data, a major departure from block lists. Secondly there is not a separate
inode area, most inodes reside immediately before the data on disk,
or with the primary directory entry for this file. Most small files
data is encapsulated in the primary directories cluster. All small
files and directory clusters are internally check summed to aid in
detection of corruption. Every cluster written includes a timestamp/seqno
in the meta data to determine which replicated content versions are
current.  Secondary file references (links) contain a subset of the inode
information to speed access. Primary and secondary references are
cross chained to support update of inode information. This slows some
heavy meta data operations and greatly speed most others. All this
is traded off with improved cache and I/O performance.

   These policies allow small file operations to average a sustained,
less than one I/O per file accessed, in busy directories. For compiler
header files (/usr/include/*), mail folders, and many net news directories
this is a huge performance boost.

   DFS contains a number of per file attributes that are not normally
found on a typical POSIX system. These attributes are transparently
handled by defaulted inheritence from either the directory or creating
applications template.

   Extensive access profile statistics are kept on active, clusters,
files and directories which are used to create additional replication
to enhance retrieval times. In addition, these metrics are used to
predict effectiveness of caching, and for cache life. These stats are used
and updated over time to determine archiving requirements and placement.
In addition highly referenced clusters maintain an in memory history
of successor clusters accessed, and is used to drive a prefetch
where certain series of small-med file clusters are accessed.

   The logical disk allocation size is not fixed, and ranges between
128 bytes upto a system max on a per file basis. The physical cluster
sizes also vary. The upper end for both of these is tunable per system.

   Internally the old system global buffer chains are gone. Buffer headers
are now chained off either directory cluster caches, the in memory inode
structures, or the volume free list. Buffer headers are more complex, do
not have statically allocated buffer memory, and are not used to queue
I/O requests. The I/O request structure includes a pointer to the
traditional buffer header, the per devices addresses for this file to
support replication, and a doubly linked list that ties it all together.
Allocations for both disk and buffer cache space are done with a
combination of best fit and N-way lazy buddy to reduce fragmentation.
Disk addresses preserved where convient, or are bound at I/O queuing
time to facilitate request clustering operations. This late binding
is important for the creation of new files, especially large ones.
To avoid running out of space, a reservation system makes sure that
space is available for all unbound data.

   A demon process runs in the background to handle defragmentation
operations, data migration, archiving and volume change services.



Changes to the kernel API and device driver level interfaces

   Open, read, write, lseek, Fcntl, stat and close interfaces will be
maintained for POSIX compatability and application portability. These
will not be the prefered interfaces for most files however.

   The prefered way to read small to medium sized files will be to
use open with a new flag O_DIRECT_MAPPED which will cause open to
return a pointer to the file data mapped copy on write into the
processes virtual address space. A read request for the entire file
will be queued at open time.  Calling close with the same address
will free the virtual address space.

   The prefered way to create small to medium sized files will be
using open with O_DIRECT_MAPPED|O_CREAT|O_TRUNC and passing it both
the file mode and data buffer address. The call will return zero if
successful, and -1 with errno if not.

   Where possible page flipping between the filesystem and application
will be used, so writing modulo system page size with page aligned
buffers is a significant win.

   For the most part the driver interface is similar, except the
strategy routine is prohibted from sorting the request list and rather
than doing a wakeup on the request header a callback thru the I/O
request structure is done. The driver is suggested to be fairly dumb,
and only implement a few extended device specific operations to
provide geometry, error recovery, and bad block mapping services.




Changes to optimize seek, head switch, and rotational latency times.

   Most existing systems attempt to optimize seek time by doing some
form of queue sorting. In most cases this queue sorting is done wrong
allowing low priority processes to hog the disk subsystem or otherwise
provide unfair service distribution. Particular attention will be
paid to provide uniform prioritized service with some "fair share"
attributes.

   Traditional scheduling algoritms treat the disk as a sequential
array of tracks and cylinders with almost no rotational/seek based
optimization of the queue processing. For instance:

    |------------R4--------- Cyl 0 Trk 0 -------------------------R9-|
    |--------R3------------- Cyl 0 Trk 1 ----------------------------|
    |----R2----------------- Cyl 0 Trk 2 ----------------------------|
    |R1--------------------- Cyl 0 Trk 3 ----------------------------|

    |---------------------R6 Cyl 1 Trk 0 ----------------------------|
    |-----------------R5---- Cyl 1 Trk 1 ----------------------------|
    |----------------------- Cyl 1 Trk 2 ------------------R8 -------|
    |----------------------- Cyl 1 Trk 3 -------------R7-------------|

Would be normally serviced as 4, 9, 3, 2, 1, 6, 5, 8, and 7 using a
total of 8 revolutions of the disk. Given acceptable head switch and
short seek times these might be completed in one revolution in sequential
order. Knowing short seek performance guidlines, head switch times,
track skew factors for each zone plus the driver and controller command
setup times and completion posting latencies can yeild significant
performance gains. Selecting the queue order primarily on priority
and enhancing it with "free requests" can maintain both high thruput
and outstanding priority driven response times. This is particulary
important since many new drives are reaching short seeks times nearly
equivalent to head switch times.

   In a default mode, the filesystem and driver will operate with
some default parameters based upon the device size and assume basic
timing numbers from a quickie startup test. A generic placement and
queue scheduling routine will be used for this filesystem.

   For devices that advertise their geometery across one or more
zones along with bad block mapping information that data will be used
to optimize data placement and request scheduling. Customized
placement and scheduling routines will be available for qualified
vendors.

   We will aid disk and system manufacturers with a white paper that
clearly outlines expected operation guidelines to achieve maximum
disk subsystem performance. This will include both a requested standard
as well as guidelines on how to enhance or modify the standard without
invalidating the placement and scheduling modules that exist. We
will also clearify the performance impacts of using software based
scatter/gather controllers which produce data underruns and rotational
latency losses at page boundries.

   SCSI write behind buffering and caching will be supported by both
the driver and filesystem. Non-SCSI devices will be able to use the
basic model in their drivers.

   Request concatination/chaining will be used where possible to
improve read/write performance.

   Careful design consideration will be applied to these cases in order
to achieve "average transfer rate" over "raw transfer rate" ratios as
near one as possible.

------------------------------


** FOR YOUR REFERENCE **

The service address, to which questions about the list itself and requests
to be added to or deleted from it should be directed, is:

    Internet: Linux-Development-Request@NEWS-DIGESTS.MIT.EDU

You can send mail to the entire list (and comp.os.linux.development) via:

    Internet: Linux-Development@NEWS-DIGESTS.MIT.EDU

Linux may be obtained via one of these FTP sites:
    nic.funet.fi				pub/OS/Linux
    tsx-11.mit.edu				pub/linux
    sunsite.unc.edu				pub/Linux

End of Linux-Development Digest
******************************
