Skip to content

File System

  • files: a named collection of bytes stored on durable storage like a disk
  • file metadata: properties of a file, such as its name, size, and location on disk
  • file types: link, character, block, directory, use file name extension
  • directory: a list of entries, , list is unordered
    • in linux, directories are also file with a special type "everything is a file"

File Characteristics

  • most files are small ~8KB

  • most of the disk is allocated to a few large files

  • spatial locality - accessing files under same directory

  • temporal locality - accessing metadata at the same time of the file

File System Layout

  • fixed sized file system blocks - the smallest unit of data that can be read/written to the disk, typically 4KB.

    • Contiguous Layout - files are stored in contiguous blocks on disk, which is fast for both sequential and random access, but can lead to fragmentation and hard to grow files

      alt text

    • Linked List Layout - files are stored in linked list of blocks, which is slower for random access, but can avoid fragmentation and easy to grow files

      alt text

    • Indexed Layout - use a special block called an index block that contains pointers to the data blocks, which is fast for random access and avoids fragmentation, and support file grow, but can be slower for sequential access (limited bandwidth)

      alt text

    • multi level index layout - Use a special index block to store pointers to the data blocks and indirect blocks to store more pointers to data blocks. can support very large files and avoid fragmentation, but can be slower for sequential access due to multiple levels of indirection.

      • single indirect block: points to a block of pointers to data blocks
      • double indirect block: points to a block of pointers to single indirect blocks
      • triple indirect block: points to a block of pointers to double indirect blocks

      alt text

Unix File System

  • inode - each file has an inode that contains metadata about the file, unique

    • including: file type, size, permissions, timestamps, and pointers to data blocks
    • view using ls -alu command to list files with their inode numbers, and stat command to view inode details
    • 256 bytes in size
    • 15 pointers. 12 direct pointers to data blocks, 1 single indirect pointer, 1 double indirect pointer, and 1 triple indirect pointer

  • super block - points to the first inode /

  • freemap - a bitmap that tracks which blocks are free or allocated
navigate to /one
  1. find and read the super block in memory, points to the first inode /
  2. open and read the inode for /, which contains pointers to the data blocks for the directory
  3. find and read the data for the directory /one inside the data blocks of /
  4. open and read the inode for /one, which contains pointers to the data blocks for the file

a directory entry that points to an inode, allowing multiple names for the same file ln file1 alias

alt text

in this case, both file1 and alias point to the same inode, so they share the same data blocks and metadata. If you modify the file through either name, the changes will be reflected in both names.

a directory entry that points to another file by name, allowing for more flexible linking ln -s file1 alias use symlink system call to create a symbolic link

alt text

link.txt -> inode1 -> inode_content: foo.txt -> foo.txt -> inode2 -> inode_content: content of foo.txt

Physical File system

  • simple disk layout - inodes are in an array of outmost tracks, data blocks (512 B) are in the inner tracks, and the super block is at the beginning of the disk
    • fixed number of inodes, and inodes are far
  • Fast file system (FFS) - 4kb block size, bitmap

File buffer cache

why? because disk access is slow, and file reading/writing has strong spatial locality

alt text

  • caches all file blocks (super, inode, data)
  • speed ~~ memory

  • system-wide cache, shared by all processes

  • uses LRU replacement policy

  • on read:

  • check if the block is in the cache
  • if yes, return the block
  • if no, evict, read the block from disk and copy it to the cache
  • on write:
  • yes? write data to the cache
  • no? evict, copy data to cache, and write to cache

Write-through vs Write-back

  • write-through: write data to both cache and disk immediately
  • write-back: write data to cache first, and write to disk later (when the block is evicted)

File system Reliability

  1. accidential / malicious deletion/modification of files
  2. use hard links to create backups of important files
  3. use soft links to create shortcuts to important files
  4. disk failure
  5. power failure (crash consistence)
  6. use journaling to log file system changes before applying them, so that in case of a crash, the file system can recover to a consistent state
  7. use checksums to verify the integrity of data blocks and inodes