File Systems

Learning outcomes:

  • Describe how files and directories are organized, including Linux paths, links, and mounting
  • Compare file allocation and free space methods, and identify where they're used in file systems today such as ext4, NTFS, and FAT
  • Explain what metadata a file system keeps, and how partitions, formatting, and mounting work
  • Describe how journaling and copy-on-write protect data when a system crashes

Would you like to download my PowerPoint to follow along?

  • Files
    • A file is a named collection of data that is handled as a unit, such as a photo, a song, an essay, or a program (Wikipedia: File system)
    • Files live on secondary storage, which keeps data when the power is off (more in the Storage, I/O, and Backups week)
    • Operating systems give you an interface to find and organize your files, such as File Explorer, Finder, or the Linux command line
      • File systems can protect data from corruption, or from total loss after a disaster
      • Systems that manage large amounts of shared data, such as a store's inventory, often use a database instead of plain files
  • Bits, Bytes, and Files
    • Bit: a single 1 or 0, the smallest piece of data
    • Byte: 8 bits, enough for one basic character like the letter A
    • Character: a byte or group of bytes that stands for a letter, number, symbol, or emoji
      • Unicode is the standard today. It covers almost every writing system in the world, plus emoji
      • UTF-8 is the most common way to store Unicode. About 99% of websites use it (W3Techs: character encodings)
      • ASCII is the original 128 English characters. UTF-8 was designed so that plain ASCII text is also valid UTF-8
      • Historical note: EBCDIC is an older character set made by IBM. Still worth knowing because IBM mainframes in banks and government still use it, and data moved off them has to be converted (IBM: The EBCDIC character set)
    • A file is a sequence of bytes
      • A text file's bytes are characters you can read
      • A photo's bytes are compressed image data that a photo app turns back into a picture
      • The program that opens the file decides what the bytes mean
  • File Systems
    • Organize files and manage access to data
    • Keep track of where each file's data is stored, and which space is free
    • Device independence: users should be able to use names like /home/sam/essay.docx instead of physical device names like /dev/nvme0n1
    • Protect files with permissions, so only the right people can use them
    • Help the system recover after a crash (see journaling, below)
    • May provide encryption, so the data is only useful to the people it's meant for
      • Full-disk encryption is now common: LUKS on Linux, BitLocker on Windows, and FileVault on macOS
      • If a laptop is stolen, the thief can't read the drive without the password or key
  • Directories
    • Directories (folders) are files that hold the names and locations of other files, to organize and quickly find them
    • A directory entry stores information such as the file name, location, size, type, when it was last accessed, and when it was created and modified
    • Folders inside folders make a tree, which is the hierarchical file system below
  • Hierarchical file system
    • The simplest design, a flat (single-level) file system, keeps every file in one directory, so no two files can share a name and finding a file means searching the whole list. It was used on some very early computers, and shows why hierarchies were invented
    • A root indicates where on the storage device the root directory begins
    • The root directory points to the various directories, each of which contains an entry for each of its files
    • File names only need to be unique within a single directory
    • The name of a file is usually formed as the pathname from the root directory to the file
    • Linux has one tree starting at / (root). Windows gives each drive its own tree with a letter, such as C:\
    • Common Linux directories (Linux manual page: hier, the official description of the Linux directory layout):
      • /home: each user's personal files
      • /etc: system settings (configuration files)
      • /var/log: log files
      • /tmp: temporary files
      • /dev: devices, such as drives. On Linux, almost everything is treated like a file
      • /media and /mnt: where USB drives and other storage get attached
  • Hierarchical file system example
    • A tree of directories, with files at the ends of the branches
  • Pathnames
    • The working directory is the directory you're "in" right now. On Linux, the pwd command shows it
    • The pathname of a file lists the folders you go through to travel down the tree to the file.
    • The absolute path is the list of folders from the root of the tree to the file
      • Linux: /home/sam/Documents/essay.docx
      • Windows: C:\Users\sam\Documents\essay.docx (note the backslashes)
    • A relative path starts from the working directory instead of the root
      • If you're in /home/sam, the relative path is Documents/essay.docx
      • . means "this directory" and .. means "the directory above this one"
    • The absolute path is unique for every file. Two different files can have the same name as long as their paths are different
  • Links
    • A link is a directory entry that points to a file or directory somewhere else in the tree
    • Soft link (symbolic link, or symlink) (Linux manual page: symlink)
      • A shortcut that stores the path to another file
      • Breaks if the original file is moved, renamed, or deleted
      • Can point to directories, and to files on other drives
      • Linux command: ln -s
      • Windows shortcuts and macOS aliases work the same way. NTFS and macOS also support real symbolic links
    • Hard link (Linux manual page: ln)
      • A second name for the same file. Both names point to the same inode (see Metadata below)
      • Renaming or moving the other name doesn't break it
      • The data is only deleted when every hard link to it is deleted
      • Can't point to a different file system, and usually can't point to directories
      • Linux command: ln
    • Red Hat: Hard links and soft links in Linux explained
  • Metadata
    • Metadata is data about the data: name, size, owner, permissions, timestamps, and where the file's blocks are stored
      • Users can't edit it directly. The operating system changes it for you, such as when you rename a file or change its permissions
      • On Linux, a file's metadata is stored in its inode (Linux manual page: inode). The ls -l and stat commands show it
      • Permissions are metadata too. ls -l shows them in a form like -rw-r-----, which means the owner can read and write, the group can read, and everyone else gets nothing. Permissions are covered in Week 12, Security and Protection
    • Many file systems create a superblock to store critical information about the whole file system
      • A superblock might contain:
        • The file system identifier
        • The location of the storage device's free blocks
      • To reduce the risk of data loss, most file systems keep extra copies of the superblock across the storage device
  • Open Files
    • The operating system keeps a list of which programs have which files open
      • That's why Windows sometimes won't let you delete or rename a file, saying the file is open in another program. Close the program, then try again
      • Linux usually lets you delete it anyway. The data stays until the program closes the file
    • On Linux, the lsof command lists open files. lsof means "list open files" (Linux manual page: lsof)
    • Behind the scenes, the operating system gives a program a number for each file it opens (a file descriptor), like a coat check ticket
  • Partitions and Formatting
    • A drive can be split into sections called partitions. Each partition acts like its own drive
    • Formatting a partition puts a file system on it, and erases whatever was there
    • When you format a USB drive, you pick a file system, usually FAT32, exFAT, or NTFS
    • The map of where each partition starts and ends is the partition table, covered in the Storage, I/O, and Backups week
  • Mounting a File System
    • Mounting attaches a file system to a directory in the tree, so its files show up there (Linux manual page: mount)
    • On Linux, a USB drive usually appears under /media/your-username/
    • The mount command shows what's mounted. The /etc/fstab file lists drives to mount automatically at startup
    • Windows does something similar by giving each drive a letter, such as D:
  • Meet the File Systems
    • ext4 (fourth extended file system): the default on Debian and Ubuntu since about 2008. It uses journaling, inodes, and extents (Linux kernel documentation: ext4)
    • XFS: the default on Red Hat Enterprise Linux, built for very large files and drives (Linux kernel documentation: XFS)
    • Btrfs and ZFS: copy-on-write file systems with built-in snapshots. Btrfs is the default on Fedora, and ZFS is popular on file servers and NAS boxes (Btrfs documentation, OpenZFS documentation)
    • NTFS (New Technology File System): the Windows default since Windows XP, with journaling, permissions, and the Master File Table. Windows servers can also use ReFS for very large storage (Microsoft: NTFS overview)
    • APFS (Apple File System): used on Macs, iPhones, and iPads since 2017. Built for SSDs, with copy-on-write, snapshots, and encryption (Apple: File system formats in Disk Utility)
    • FAT32 and exFAT: simple, and work on almost every device, so they're used on USB drives and SD cards
    • F2FS (Flash-Friendly File System): built for flash storage, and used on many Android phones (Linux kernel documentation: F2FS)
  • File allocation
    • Storage is split into small fixed-size chunks
      • Sector: the drive's smallest piece
      • Block: the file system's unit, often 4 KB. Windows calls it a cluster
      • Extent: a run of blocks in a row
    • Handing out and freeing blocks on storage is a lot like handing out main memory (covered in Week 11, Memory Management)
    • Files tend to grow or shrink over time, and users rarely know in advance how large their files will be
    • Contiguous allocation systems have mostly been replaced by more flexible noncontiguous allocation systems
  • Contiguous File Allocation
    • Contiguous allocation
      • Place file data in one unbroken run of blocks on the storage device
      • Advantages
        • Each part of the file sits right next to the next part, so reading it is fast
      • Disadvantages
        • External fragmentation: free space gets broken into small gaps that are too small to use
        • Poor performance can result if files grow and shrink over time
        • If a file grows beyond its space and there's no room next to it, the whole file has to be moved somewhere bigger
      • Still used on read-only discs like DVDs, where files never grow
  • Linked-List Noncontiguous File Allocation
    • A directory entry points to the first block of a file
    • Each block holds data plus a pointer to the file's next block, so the blocks form a chain (a linked list)
      • Like a scavenger hunt, where each clue tells you where the next one is
    • To find something, the chain must be followed from the beginning, which can be slow
    • On a hard drive, each jump means physically moving the arm (a seek). SSDs have no moving parts, so scattered blocks slow them down much less
    • Inserting or deleting is done by changing the pointer in the previous block
    • FAT, below, is this same idea with the pointers moved out of the blocks and into one table
  • Tabular Noncontiguous File Allocation
    • Moves the "next block" pointers out of the blocks and into one table
    • The directory entry gives a file's first block, and the block allocation table gives each next block. The last block's entry is empty (null)
    • The table can be kept in memory (cached), so the chain of blocks can be followed quickly
    • But finding the end of a big file can mean following many pointers
    • Real example: Microsoft's FAT (File Allocation Table) file system
  • FAT Today
  • Indexed noncontiguous file allocation
    • Each file has an index block or several index blocks
    • Index blocks contain a list of pointers to the file's data blocks, like a table of contents
    • A file's directory entry points to its index block, which may save the last few entries to point to more index blocks, a technique called chaining
    • Advantages over the linked-list method:
      • Searching can happen in the index blocks themselves, without reading the data
      • File systems usually place index blocks near the data blocks they point to, so the data can be read quickly after the index block is loaded
    • Real examples: ext4 (inodes) and NTFS (the Master File Table)
  • Index block chaining
    • Index blocks are called inodes (index nodes) in Unix and Linux
    • The classic Unix inode has direct pointers to data blocks, plus indirect pointers that lead to more pointers, so very large files can be reached
    • ext4 uses extents instead, so one pointer can cover a whole run of neighboring blocks
  • Windows NTFS File System
    • New Technology File System, introduced with Windows NT in 1993, and still the default on Windows 11
    • The Master File Table (MFT) has a record for every file, with its name, permissions, and where its data is stored
    • Journaling to recover after a crash, plus permissions, encryption, and compression
    • Macs can read NTFS drives but can't write to them without extra software, which is one reason USB drives usually use exFAT
  • Tracking Free Space
    • The file system must always know which blocks are free
    • Free list: a linked list of the free blocks
      • Blocks are handed out from the front of the list, and freed blocks are added to the end
      • Low overhead, but files end up in scattered blocks, which is slower on hard drives
    • Bitmap: one bit for each block on the storage device. A 1 means used and a 0 means free
      • The file system can quickly tell if neighboring blocks are free
      • But it may need to search the entire bitmap to find a free block
      • ext4 uses bitmaps to track free blocks and inodes
    • SSDs need extra help keeping track of free space (TRIM), covered in the Storage, I/O, and Backups week
  • Crashing in the Middle of a Save
    • If the power goes out halfway through saving a file, the data can be left half-written (inconsistent)
    • Atomic transactions: do a group of steps completely or not at all
      • Think of a bank transfer: the money must leave one account and arrive in the other, never just one of those
      • If a transaction can't finish, it is rolled back to how things were before it started
    • Checkpoints: mark the last point where everything was safely saved to permanent storage
      • After a crash, the system only has to check what happened after the checkpoint, instead of everything
    • Databases rely on these same ideas
  • How File Systems Survive Crashes
    • Journaling file systems (Linux kernel documentation: the ext4 journal)
      • Before changing anything, write a note in the journal about what's going to change
      • After a crash, the system reads the journal to finish or undo the changes, instead of checking the whole drive
      • Examples: ext4, XFS, and NTFS
    • Copy-on-write file systems (Btrfs documentation: Introduction)
      • Never overwrite data in place. Write the new version somewhere free, then switch the pointer to it
      • This makes snapshots fast and cheap
      • Examples: Btrfs, ZFS, APFS, and ReFS
    • Log-structured file systems always write new data at the end, like a diary. F2FS, used on many Android phones, works this way, which suits flash storage (Linux kernel documentation: F2FS)
  • Multiple File System Types
    • Each partition has a single file system
    • One computer can use several different file system types at once, such as ext4 for the main drive and exFAT for a USB drive
    • Modern systems handle this with a Virtual File System (VFS) (Linux kernel documentation: Overview of the Linux Virtual File System)
    • The VFS gives programs one way to open, read, and save files, no matter what file system or device is underneath
  • File Servers and Distributed Systems
    • One approach to sharing files across a network is to send all requests to a file server
      • A computer that's dedicated to storing and sharing files
      • Keeps control in one place
      • The file server can become a bottleneck, because every client sends every request to it
    • Common ways to share files today:
      • NFS: the Linux and Unix way to share files over a network (Ubuntu Server documentation: NFS)
      • SMB: the Windows way to share files. Linux uses Samba to talk SMB (Microsoft: What is SMB file sharing?)
      • NAS (network-attached storage): a small file server for a home or office
      • Cloud storage and sync, such as OneDrive, Google Drive, and Dropbox
    • A better approach for very large systems is to spread files across many computers that talk to each other directly (more in Week 14, Distributed Systems)

Suggested Activities and Discussion Topics:

  • Activity: look at the properties of a file on your computer. What metadata can you see, and what do you think the file system stores that you can't see?
  • Activity: find out which file system your computer's main drive uses, and which one a USB drive or SD card uses. On Windows, right-click the drive in File Explorer and choose Properties. On macOS, open Disk Utility. On Linux, type df -T in a terminal. Why do you think they're different?
  • Activity: plug in a USB drive and open the Format window (on Windows, right-click the drive in File Explorer and choose Format). Don't click Start! Which file systems can you choose from, and which would you pick for a drive you share between a Windows PC and a Mac?
  • Discussion: a file's name, size, and dates are all metadata. What could someone learn about you from the metadata of your files, even without opening them?

Would you like to see some more classes? Click here