File Systems

Describe the general evolution of Unix file formats inode, BSD FFS,
and journaling file systems and give their design tradeoff.
   a)Early Unix file systems used four discrete areas. From low to high
     block addresses they were the Super Block, inodes, allocated
     blocks, and free blocks. Allocated blocks were a mix of regular
     and directory file types.
   b)Keeping all the inodes in one disk zone and file blocks in another
     led to many extra seek operations between the two zones.
   c)The BSD Fast File System (FFS) improved on the original Unix design
     by creating a series of 10s to 100s of mini-disk images within a
     disk partition or file system. Thus, for most file access, the R/W
     head only had to move between inodes and file blocks within the
     mini-disk.
   d)Unix file systems led the trend of keeping new files or modified
     files in the data cache to improve I/O speed. To prevent data loss,
     the data cache was flushed every 30 seconds.
   e)The Linux Ext3 file system format employs the BSD FSS improvements
     and a journaling feature which saves the recently modified disk
     blocks in a scratch pad area along with a record of the sequence of
     operations on the file that contained the new blocks. In this way,
     if the OS crashed, then the file could be rebuilt by repeating the
     series of recorded actions on the file.
   f)Although these changes reduced R/W head movement and improved data
     integrity they also introduced more indexing overhead of tracking
     mini-disks and more disk writes saving modified disk blocks.  At
     least one study indicated a 22% increase in overhead resulting
     from these design "benefits."
   See: http://www.namesys.com/benchmarks.html
Describe the forthcoming changes in hard disks and the effects it will
have on OS file system design for reading and writing files.
   a)       Parameter    2006  2009  2013  Improvement
          Capacity (GiB) 500   2000  8000     16x
        Bandwidth (Mb/s) 1000  2000  5000      5x
     Read seek time (ms) 8     7.2   6.5     1.2x
   b)It takes an hour or more to sequentially read today's 500 GiB drives.
   c)In 2013, it will take about 3.5 hours, an increase of 3 times.
   d)Random I/O will take even more time since seek times are nearly flat
     for the foreseeable future.  For example, database random I/O
     accessing 10% of the disk will take much longer on an 8TiB 2013-era
     disk drive than it on today's 500GiB disk drives.
   e)I/O errors will be more frequent even though the total per-bit error
     rate will drop.
Describe the problem with consistency checking future disk drives.
   a)Journaling file systems are designed to stop synchronization errors
     with the CPU, but not low-level media errors. Today's file systems
     assume low frequency I/O error storage devices.
   b)Increasing number of I/O errors in the future mean that fsck will
     be run more often.
   c)Fsck on multi-terabinarybyte file systems today can easily take two
     days.
   d)Recently, the Linux kernel source server suffered file system
     corruption. It took over a week for fsck to repair the large ext3
     file system, when it would have taken far less time to restore from
     backup.
Fix the last-file-block problem and evaluate the impact this will have on
future capacity disk drives, and give a possible way to mitigate the problem.
    a)Linux uses 4KiB pages, 4KiB logical OS blocks, and files are stored
      in 4KiB blocks (even though the physical record of a disk is 512
      bytes).
    b)Regardless of file size, the last file block may be full or contain
      just one byte. The left over space goes unused.
    c)Thus, the average file system leaks (number of files * 2KiB) bytes
      due to last-file-block fragmentation. Assuming 60K files per 70GiB,
      thats 1.2MiB or about two percent (0.017%). For today's 500GiB hard
      disks that would be about 100MiB of fragmentation.
    d)As disk capacity grows, so will last-file-block fragmentation. An
      8TiB Drive will have about 1.3GiB of last-file-block fragmentation.
    e)Approximately half of the files stored on a file system are 2KiB
      or less. A typical distribution of disk file sizes look like this:
      File size  % total
        <= 1 KB  25-30%
        <= 2 KB  40-45%
        <= 3 KB  50-60%
        <= 4 KB  55-65%
    c)Thus, if these small files could be stored, or combined with, the
      file's meta data area, then the average file system block leak could
      be reduced by 25% or recapture 25MiB with today's disk drives or
      recapture 325MiB in a 8TiB drive of the future.