2.6 — File Systems

2.5 mentioned "the disk" that swap and files live on, and left it a black box. Time to open it. You save a photo called beach.jpg, and later it comes back — the same bytes, with a name, a size, a modification date, sitting in a folder. But a storage device knows nothing of names, folders, or dates; it's just an enormous array of numbered blocks, each holding a few hundred bytes, and nothing else. The file system is the software that bridges that gulf — the OS layer that turns a flat sea of numbered blocks into the named, nested, dated files and directories you actually use. This chapter builds that abstraction from the block up: what a file really is on disk (the inode), how directories are just a special kind of file, how the system survives a power cut mid-write (journaling), and — answering a genuine curiosity — why a tool like WizTree can scan your entire drive in seconds while Windows Explorer takes minutes.

1. From a sea of blocks to a file

Start at the bottom. A storage device — spinning hard drive (HDD) or solid-state drive (SSD) — presents itself to the OS as a linear array of fixed-size blocks (or sectors), historically 512 bytes, now commonly 4 KB, each identified by a number (a logical block address). That's all the hardware offers: "give me block #91,442's bytes," "write these bytes to block #4,001." No names, no structure, no notion of a "file." Everything else is an illusion the file system constructs on top.

So what must a file system track to turn that into a usable beach.jpg? Two very different things, and separating them is the key insight:

1. The file's data — the actual bytes of the photo, which occupy some set of blocks.
2. The file's metadata — everything about the file that isn't its content: its size, owner, permissions, timestamps (created/modified/accessed), and — crucially — the list of which blocks hold its data.

A big file's data blocks are usually not contiguous; they're scattered across the disk wherever free space was available (just as virtual memory scatters pages — 2.5). So the file system needs, per file, a record that holds all the metadata and points to every data block. That record is the heart of a Unix file system, and it has a name worth knowing: the inode (index node).

2. The inode: what a file actually is

An inode is a fixed-size structure — the file's identity card — and it contains everything about a file except its name and its data: the file's size, owner (user and group IDs), permission bits (read/write/execute for owner/group/others — the rwx you see in ls -l), timestamps, a link count, and a set of pointers to the data blocks that hold the content. Every file has exactly one inode, identified by a number. In a very real sense, the inode is the file — the name is just a label attached elsewhere (we'll see where in a moment).

The clever part is how the inode points to potentially huge files with a fixed-size structure. It can't just hold a list of all block numbers — a 10 GB file has millions of blocks, far more pointers than fit in a small inode. The classic solution is a tiered, tree-like scheme:

Figure 1 — An inode. A fixed-size record holding all metadata plus a few direct pointers to data blocks and an indirect pointer to a block that holds more pointers. Chaining indirection lets a small inode address enormous files.

The inode holds a handful of direct pointers (each naming one data block — enough for small files entirely), then an indirect pointer to a block that contains nothing but more block pointers, then a double-indirect pointer (to a block of pointers to blocks of pointers), and a triple-indirect. Each level of indirection multiplies the reach enormously, so a tiny inode can address a file of terabytes — while small files pay no overhead (their blocks fit in the direct pointers). It's the same "tree of pointers to scale a fixed-size root" trick as the multi-level page table in 2.5, and as B-trees in databases (Part 7) — a recurring idea.

3. Directories: names are just data

If the inode holds everything except the name, where does the name beach.jpg live? In the directory — and the revelation is that a directory is just a special file whose contents are a table mapping names to inode numbers. A folder isn't a container that holds files; it's a file that holds a list: "beach.jpg" → inode 5012, "notes.txt" → inode 88, and so on. When you open /home/you/beach.jpg, the OS walks the path: read the root directory's data to find home's inode, read that to find you's inode, read that to find the entry beach.jpg → 5012, then read inode 5012 to find the data blocks. Name resolution is a walk down a tree of these little name→inode tables.

This design instantly explains several everyday mysteries:

• Hard links. Because the name and the inode are separate, two different names can point to the same inode — the same file, two names, no copy. That's a hard link. The inode's "link count" tracks how many names point to it; the data is deleted only when the count hits zero (which is what "delete" really does — it removes a name and decrements the count, not necessarily the data).
• Renaming and moving are cheap. Renaming a huge file doesn't touch its data at all — it just changes a string in a directory's name→inode table. Moving a file within the same file system likewise just moves the directory entry, not the gigabytes of data.
• Symbolic links (symlinks) are the other kind: a tiny special file whose content is a path to another file (a pointer by name, not by inode) — which is why a symlink breaks if you delete its target, while a hard link doesn't.

4. Surviving a crash: journaling

Now a hard problem. Many file-system operations require multiple block writes that must all happen together. Creating a file, for instance: allocate an inode, write the data blocks, mark those blocks as used in the free-space map, and add the name→inode entry to the directory. What if the power fails between those writes? You could end up with blocks marked "used" that no file references (leaked space), or a directory entry pointing at an inode that was never finished (corruption), or worse. A file system left in a half-updated, inconsistent state can be unusable.

The old fix was to scan the entire disk after a crash to find and repair inconsistencies (the Unix fsck tool) — which on a large disk could take hours, an eternity for a server that needs to come back up. The modern solution is journaling, borrowed straight from databases (Part 7). Before performing a group of changes, the file system first writes a description of what it's about to do to a dedicated on-disk log — the journal (or write-ahead log, WAL). Only after the journal entry is safely written does it apply the actual changes. Now a crash is survivable: on reboot, the system just replays the journal — it re-does any change that was logged but perhaps not fully applied — restoring consistency in seconds instead of a full-disk scan. This is why modern file systems (ext4 on Linux, NTFS on Windows, and in spirit APFS on macOS) rarely need long repairs after a crash. The trade-off is a little extra write work (logging changes before making them), well worth it for crash-safety. (Many journal only metadata by default — enough to keep the file system's structure consistent, at the cost that recently-written file data might still be lost, a deliberate speed/safety balance.)

5. A tour of real file systems — and the WizTree mystery

Different file systems make different trade-offs, and one comparison answers a real curiosity.

• ext4 (Linux's long-time default) — a mature, inode-based, journaling file system; solid, fast, reliable.
• APFS (Apple, 2017) — built for SSDs, with copy-on-write (the 2.2 trick!): it never overwrites data in place, so snapshots and file copies are near-instant (they just share blocks until one side changes). Crash-safe by design.
• NTFS (Windows, since 1993) — journaling, with a distinctive core structure that explains the WizTree magic.

Here's the curiosity, answered. WizTree can scan an entire multi-terabyte drive and show you what's using space in seconds, while Windows Explorer's "calculate folder size" crawls for minutes. The secret is how it reads the metadata. NTFS keeps all its file records in one central structure called the Master File Table (MFT) — essentially NTFS's table of inodes, one record per file, stored contiguously in a special region of the disk. Explorer (and most tools) find a folder's size the slow way: they walk the directory tree recursively, opening each folder, listing its files, stat-ing each one to read its size — millions of small, scattered metadata reads, each with syscall and seek overhead (2.1). WizTree instead reads the MFT directly, in one big sequential gulp — it slurps the entire table of file records (names, sizes, parent references) in a few large sequential reads, then reconstructs the whole directory tree and every folder's size in memory from that one dump. Sequential bulk read of one contiguous table versus millions of random small reads: that's a difference of orders of magnitude, and it's why WizTree feels instant. The lesson is a beautiful, transferable one: how you access data — one big sequential read vs many small random ones — can matter far more than how much data there is — the same 1.6 locality principle, now at disk scale. ^{⚑What is WizTree and how does it work? [EQ-79]}

6. The VFS: one interface for all of them

Your programs call open, read, write, close and never care whether the file lives on ext4, NTFS, a USB stick's FAT32, a network share, or even something that isn't a disk at all. That uniformity comes from the Virtual File System (VFS) — an abstraction layer inside the kernel that defines a common interface ("a file system must provide these operations: open, read, lookup, …") and lets each concrete file system implement it. Your read() syscall hits the VFS, which dispatches to the right file system's implementation. This is the polymorphism/interface pattern (Part 9) applied in the kernel, and its payoff is enormous: it's why the same programs work across every storage type, why Linux can mount dozens of file-system types, and — elegantly — why Unix can present things that aren't files as files. The /proc filesystem (Chapter 2.8) exposes live kernel and process info as readable "files"; devices appear under /dev; this is the famous Unix philosophy that "everything is a file" — a single, uniform interface (open/read/write) for storage, devices, processes, and more, all unified by the VFS.

7. The expert lens

SSDs changed the rules, and file systems adapted. For decades, file systems were designed around the physics of spinning disks, where the dominant cost was seek time — physically moving the read head to a track (milliseconds), making random access catastrophically slower than sequential. That's why laying files out contiguously and minimizing seeks mattered so much. SSDs have no moving parts, so random access is nearly as fast as sequential — but they bring new constraints: flash memory can't overwrite in place (it must erase a whole block before rewriting) and each cell wears out after a finite number of writes. So SSD-era design shifted to wear leveling (spreading writes evenly so no cell dies early), the TRIM command (letting the drive know which blocks are free to reclaim), and copy-on-write/log-structured designs (APFS, F2FS, and log-structured merge trees in databases — Part 7) that turn random writes into sequential ones. Understanding which storage physics you're on still shapes performance decisions — an echo of the "know your hardware" theme from Part 1.

Caching makes file I/O feel fast — and creates a durability question. The OS keeps recently-used file data in a page cache in RAM (using free memory as a cache, per 1.6 — this is why your second read of a file is instant, and why "free" RAM is often mostly cache). But this means a write() usually just updates RAM and returns before the data reaches disk — fast, but the data is not yet durable. If the power fails, that "written" data is gone. This is the crux of durability: to guarantee data is on disk, a program must call fsync to force the cache to flush. Databases obsess over this (Part 7) — the "D" in ACID (durability) hinges on fsync at the right moments — and getting it wrong is how apps lose data they thought they'd saved. The performance-vs-durability trade (buffer in RAM for speed, or flush for safety) is a decision you'll make consciously in any system that must not lose data.

File-system layout is a data-structure choice, and it echoes everywhere. The inode's tiered pointers, directories as name→inode tables, journaling for crash recovery, B-tree-indexed directories in modern file systems — these are the same data structures and techniques you'll meet in databases (Part 7): B+ trees for indexing, write-ahead logs for durability, copy-on-write for snapshots. A file system is, essentially, a specialized database for a particular workload (large blobs with hierarchical names). Recognizing that unifies two topics people usually learn separately, and it's why file-system knowledge transfers directly to understanding how databases persist data.

Next chapter: we've treated reading and writing as if the data just appears, but talking to a disk (or network card) is itself a rich problem — the CPU is far faster than any device, so how does it hand off work and get notified when it's done without wasting cycles waiting? Chapter 2.7 covers I/O: interrupts, DMA, blocking vs non-blocking, epoll, and the IOPS metric.

Recall

• A storage device is just a numbered array of fixed-size blocks; the file system builds named, nested files and directories on top. Every file separates data (its bytes, scattered across blocks) from metadata (size, owner, permissions, timestamps, and the list of its data blocks).
• The inode holds all a file's metadata plus tiered pointers to its data blocks (direct, then indirect/double/triple — a pointer tree that lets a small inode address huge files). The inode is the file; the name lives elsewhere.
• A directory is just a file whose contents map names → inode numbers. Hence hard links (two names, one inode), cheap rename/move (edit a directory entry, not the data), and symlinks (a file containing a path).
• Journaling writes intended changes to a log first, so a crash is recovered by replaying the journal in seconds instead of a full-disk fsck. Used by ext4, NTFS, (COW-style) APFS.
• NTFS stores all file records contiguously in the Master File Table; WizTree reads the MFT in one sequential bulk read (vs Explorer's millions of small random stats) — access pattern beats data size. The VFS gives one uniform open/read/write interface across all file systems (and "everything is a file").

Self-test: What's the difference between a file's data and its inode? How does a small fixed-size inode address a terabyte file? What actually is a directory, and what's a hard link? How does journaling make crash recovery fast? Why is WizTree so much faster than Explorer at computing folder sizes?

Quiz Bank

FoundationalWhat is an inode, and what does it contain?

An inode (index node) is a fixed-size on-disk structure representing a single file. It contains all of the file's metadata — size, owner (user/group), permission bits, timestamps, link count — plus pointers to the data blocks that hold the file's actual content. It does not contain the file's name (that lives in the directory) or its data (that's in the blocks it points to). Effectively, the inode is the file's identity; every file has exactly one, identified by an inode number.

FoundationalWhat actually is a directory?

A directory is just a special file whose contents are a table mapping names to inode numbers — e.g. "beach.jpg" → 5012. It doesn't "contain" files; it holds a list of name→inode entries. Opening a path means walking these tables from the root: read each directory to find the next component's inode, until you reach the target file's inode. This is why a folder can be huge yet its own "size" is tiny (it's just a name list), and why renaming/moving is cheap.

AppliedHow can a small, fixed-size inode address a multi-gigabyte file?

Through tiered indirection. The inode holds a few direct pointers (each to one data block — covering small files), then an indirect pointer to a block that contains only more block pointers, then a double-indirect (a block of pointers to blocks of pointers), then triple-indirect. Each indirection level multiplies reach enormously, so a small inode can address terabytes, while small files stay cheap (using only direct pointers). It's the same "tree of pointers to scale a fixed root" idea as multi-level page tables (2.5) and B-trees (Part 7).

AppliedWhat is the difference between a hard link and a symbolic link?

A hard link is an additional name (directory entry) pointing to the same inode as an existing file — two names, one file, one set of data; the inode's link count tracks how many names reference it, and the data is freed only when it hits zero. A symbolic link (symlink) is a separate small file whose content is a path to another file — it points by name, not by inode. Consequences: deleting the original leaves a hard link fully working (the data persists) but breaks a symlink (its target path no longer resolves); hard links can't cross file systems (inode numbers are per-filesystem), symlinks can.

InterviewWhat is journaling and what problem does it solve?

Many file-system operations require several block writes that must all take effect together (e.g. creating a file updates the inode, data blocks, free-space map, and directory). A crash midway leaves the file system inconsistent. Journaling solves this by first writing the intended changes to a dedicated on-disk log (the journal/write-ahead log), then applying them. After a crash, the system simply replays the journal to reach a consistent state — recovering in seconds, versus the old approach of scanning the whole disk (fsck) for hours. Many file systems journal metadata only (structure stays consistent; recent file data may still be lost) as a speed/safety balance. Used by ext4, NTFS, etc.

InterviewWhy can WizTree scan a whole drive's folder sizes in seconds while Explorer takes minutes?

Because of how each reads metadata. Windows Explorer computes a folder's size the slow way: recursively walking the directory tree and issuing a stat for each of potentially millions of files — countless small, random, syscall-laden metadata reads. WizTree instead reads NTFS's Master File Table (MFT) directly — the contiguous central table of all file records — in a few large sequential reads, then reconstructs the entire tree and all folder sizes in memory from that single bulk dump. One big sequential read of a contiguous table beats millions of small random reads by orders of magnitude. The transferable lesson: access pattern (sequential vs random, bulk vs piecemeal) often dominates performance far more than the amount of data — the locality principle at disk scale.

StaffYour application calls write() and returns success, but after a power loss some 'saved' data is missing. Explain why, and how to guarantee durability.

write() typically only copies data into the OS page cache in RAM and returns immediately — the data is not yet on disk. The kernel flushes dirty pages to storage later (or the file system journals metadata but not necessarily your file data). So on power loss, anything still in the cache and not yet flushed is gone, even though write() reported success. This is the standard performance/durability trade: buffering in RAM makes writes fast but not durable. To guarantee durability, the program must call fsync (or fdatasync) on the file after writing, which forces the cached data to physical storage and returns only once it's durably written; for directory operations (like the file's name appearing), you may also need to fsync the containing directory. Databases do exactly this at carefully chosen points — the "D" (durability) in ACID depends on fsync — and they often combine it with their own write-ahead log. The staff-level point: "write succeeded" ≠ "data is durable"; durability requires an explicit flush, and you trade throughput for it deliberately (e.g. batching fsyncs, group commit).

Flashcards

FlashWhat a storage device offers the OS

Just a numbered array of fixed-size blocks/sectors (512 B or 4 KB); files, names, folders are all built on top by the file system.

FlashInode contents

All file metadata (size, owner, permissions, timestamps, link count) + pointers to data blocks. Not the name (in the directory) or the data.

FlashWhat a directory really is

A file whose contents map names → inode numbers.

FlashHard link vs symlink

Hard link: another name for the same inode (same file). Symlink: a file containing a path to another file (points by name; breaks if target deleted).

FlashJournaling

Write intended changes to an on-disk log first, then apply them; after a crash, replay the log to restore consistency in seconds.

FlashWhy WizTree is fast

Reads NTFS's Master File Table (MFT) in one sequential bulk read, vs Explorer's millions of small random stat calls.

FlashVFS

Kernel abstraction giving one uniform open/read/write interface across all file systems (and 'everything is a file').

Scenario Drill

DrillA backup script copies millions of tiny files and is agonizingly slow, far slower than copying one large file of the same total size. Explain why, using this chapter, and suggest a faster approach.

Copying many tiny files is dominated by per-file overhead, not data volume. Each file requires: a directory lookup to resolve its name→inode, reading its inode (metadata), reading its (few, scattered) data blocks, then on the destination creating an inode, writing a directory entry, updating the free-space map and journal — a burst of small, often random metadata operations and syscalls (2.1) per file. Multiply by millions and the seek/metadata/syscall overhead swamps the actual bytes; on a spinning disk the random seeks are especially brutal. One large file of the same total size touches the file-system structures once and streams its data in big sequential reads/writes — vastly less overhead. Faster approaches, all reducing per-file overhead:

(1) archive first — tar/zip the many files into one big file, so the copy becomes a single sequential streaming transfer (this is exactly why backups and deploys ship tarballs); (2) use tools that batch metadata and parallelize (e.g. rsync, or file-system-level snapshots/cp --reflink on COW file systems like APFS/Btrfs, which clone by sharing blocks instantly instead of copying); (3) leverage the file system — a snapshot (COW) captures millions of files in O(1) by sharing blocks rather than reading and rewriting them. The transferable insight matches WizTree's: with lots of small items, the number of operations and their access pattern dominates — convert many small random operations into few large sequential ones.