Operating Systems: Three Easy Pieces Ch. 41

Locality and the fast file system

• Old file system was simple
  • The problem: Poor Performance
  • UNIX file system treated the disk like it was a random-access memory
  • Data was spread all over the place
  • the data blocks of a file were often very far away from its inode, thus inducing an expensive seek
  • Fragmented
  • Degramententation Tool
    • minimize the internal fragmentation
• FFS: Disk Awareness
  • Fast File System
  • interface
    • open, read, write, and close
  • Cylinder groups
    • Single cylinder is a set of tracks on different surfaces of a hard drive
    • Block groups
    • Consecutive portion of the disk’s address space
    • placing two files within the same group
    • Super block, ib, db, inode, data block
• how to allocate
  • find the cylinder group with a low number of allocated directories (to balance directories across groups) and a high number of free inodes (to subsequently be able to allocate a bunch of files), and put the directory data and inode in that group
  • to allocate the data blocks of a file in the same group as its inode
  • it places all files that are in the same directory in the cylinder group of the directory they are in
• FFS policies
  • the data blocks of each file are near each file’s inode, and files in the same directory are near one another
  • common sense
• Measuring File Locality
  • The random trace was generated by selecting files from within an existing SEER trace in random order and calculating the distance metric between these randomly-ordered accesses
  • 40% of file accesses were to either the same file or to one in the same director
  • a large file would entirely fill the block group it is first placed within
  • FFS instead spreads the file spread across groups
  • amortization
• Internal fragmentation
  • internal fragmentation could thus lead to roughly half the disk being wasted for a typical file system
  • sub-blocks
    • 512-byte little blocks that the file system could allocate to files
    • the file system will continue allocating 512-byte blocks to it until it acquires a full 4KB of data
  • A second neat thing that FFS introduced was a disk layout that was optimized for performance
  • Parameterization
    • How many blocks need to skip to avoid extra rotation
  • FFS was one of the first file systems to allow for long file names
  • symbolic link