Skip to content

FFS

Context

// TODO: Add photo

  • File systems we use today were originally designed and optimized for spinning hard disks. However, we don't find it valuable to redesign new file systems, and that's why we keep the same design.
  • For non-volatile memory, we do have to redesign our file systems.
  • tracks in the inner part of the disk have a smaller amount of sectors because these tracks have a smaller circumference → within the same rotation time, you transfer more data in the outer tracks than the inner tracks.
  • Each surface has a head, but they all attach to the same arm → only one head is active at the same time.

Cylinder Group:

Several consecutive tracks on the same surface and all tracks that are directly above or beneath these tracks are within the same cylinder group.

  • Disk operation overhead has three components:

    • Seek time
    • Rotation time: how fast the disk spins
    • Transfer time

  • Bit density on tracks increases dramatically over time → increase the transfer rate dramatically → lower the transfer time dramatically.

  • Originally, operating systems know the structure and every single disk attached to the operating systems. Over time, disks have generated a layer of indirection

Goal

  • Performance
  • Reliability

Implementation

Original Unix File System Implementation

  • Block size: 512 byte

// TODO: Add Inode diagram

// TODO: Add Inode disk diagram

Improved FFS Implementation

Optimization

Problem FFS Solution
Random block placement
  • Cylinder group
  • Blocks are close to each other in the spatial region in terms of seek
  • Within each cylinder group, some area are used to store Inodes and some area are used to store data blocks
    		•
    Inodes are far from data blocks
  • Resolved by the same solution mentioned above
    		•  \
    Low bandwidth utilization
  • Increase block size to 4KB
    		•
    Small max file size
  • Linear increase in data block size exponentially increase maximum file size because we have indirect, double-indrecit or even tiple-indirect data block pointers → 232 byte
    • A lot of storage is wasted with large data blocks
  • Use fragments to break 4K blocks into smaller fragments
  • Fragments can only exist at the end of a file
    		•
    Recovery
  • Introduction of superblocks which includes meta data of the file system
  • Store superblocks in every single cylinder group with deterministic locations
  • (i.e. if we lose one, we can go other other cylinder groups to get it)
    		•
    Device oblivious
  • Have read/write buffers in disks for consecutive reads/writes
  • (skipping blocks is no longer needed)
    		•

    Modern Unix File System → Extent

    In modern unix file system, since going to the disk is so expensive, we read a bunch of data (e.g. 32KB, 128KB, etc...) instead of just one block. These consecutive blocks are called extent.

    Allocation

    Global Allocator:

    wiefjwoiefj

    Local Allocator:

    jijiojoij

    Takeaway

    • The INode data structure is very useful and efficient for random file access because we can just read a specific data block without having to read intermediate data blocks in between.
    • The number of INode is a parameter when you initialize the file system. It is not dynamically changed, but we often just create way more INodes than we need during initialization.
    • We lose disk capacity for storing Inodes and free spaces needed by the allocators
    • We are willing to lose the space, so that we can get good disk performance even when the file system is full

    My Question

    Author(s):
    For Questions/Corrections/Mistakes please send to my/author(s)'s email
    Back to top