filesystem

How it is built

Architecture overview

A local file system turns a flat array of fixed-size blocks into named, growable, crash-safe files. It has three jobs: find the blocks of a file quickly (a mapping from file offset to disk block), find free space without fragmenting (an allocator), and survive a power cut in the middle of an update (an ordering discipline). Everything else, such as checksums, compression, snapshots and RAID, is layered on those three. The one idea that separates the two main families: ext4 updates in place and logs the intent first (a journal), while ZFS, Btrfs and APFS never overwrite live metadata (copy-on-write, then flip one root pointer). Above the on-disk format sits a page cache that holds file data in RAM, and below it sits a block device (SSD or disk) that has its own volatile write cache and its own internal remapping.

Parts:

• Block mapping — maps file offset to disk blocks, and names to inodes — extent-trees (no page yet), B+ tree, copy-on-write-b-tree (no page yet)
• Allocator — hands out free blocks, keeps files contiguous — free-space-management (no page yet)
• Crash safety — makes multi-block updates atomic — Write-ahead log, crash-consistency-ordering (no page yet), RCU (read-copy-update) for lock-free in-memory structures
• Integrity — detects (and with redundancy, repairs) bad blocks — CRC32C checksums, merkle-tree (no page yet), erasure-coding (no page yet)
• Data reduction — LZ4, Zstandard (zstd), Content-addressed storage (dedup, clones)
• Cache and I/O path — keeps hot data in RAM and decides when data is really on disk — mmap and the page cache, adaptive-replacement-cache (no page yet), fsync, O_DSYNC and O_DIRECT
• Device — what the blocks live on — SSD and NVMe internals

 app: open/read/write/fsync/mmap
          │
   ┌──────▼───────┐  hit   ┌────────────────────────┐
   │  VFS + page  │◄──────►│ data cache (LRU / ARC) │
   │    cache     │        └────────────────────────┘
   └──────┬───────┘
          │ dirty pages, flush on fsync / timer
   ┌──────▼───────────────────────────────────────────┐
   │ inode table / B-tree: name ─► inode ─► extents   │
   │ allocator (bitmaps / space maps)                 │
   │ checksum + compress  ◄── write path              │
   └──────┬──────────────────────┬────────────────────┘
          │ journal (ext4)       │ new tree + root flip (COW)
   ┌──────▼──────────────────────▼────────────────────┐
   │ block device: volatile cache, flush/FUA, FTL     │
   └──────────────────────────────────────────────────┘

How the parts fit together

Block mapping

An inode must answer "which disk block holds byte N of this file". Classic Unix file systems used per-block pointers, which cost one pointer for every block of a large file. Modern ones store extents: a start block and a length. The ext4 kernel documentation gives the case: with extents, mapping a contiguous run of 1,000 blocks takes one ext4_extent record with ee_len = 1000 instead of an indirect block with 1,000 entries (source: kernel.org ext4 docs, extent tree). Extents are held in a shallow tree (extent-trees, no page yet): a few records sit inside the inode and deeper levels sit in blocks of their own. Directories and large metadata sets are B+ trees because a wide, shallow tree turns a lookup into two or three block reads. Btrfs and APFS go further and keep all metadata in B-trees; in a copy-on-write file system (copy-on-write-b-tree, no page yet) a change copies the leaf and every node up to the root, so the tree is never half-modified on disk (source: Rodeh et al., BTRFS).

Allocator

free-space-management (no page yet) decides where new blocks go. The goal is contiguity for sequential files and locality between a file's data, its inode and its directory. ext4 splits the disk into block groups; with the default 4 KiB block a group is 32,768 blocks (128 MiB), and the allocator tries to keep a file's blocks inside one group (source: kernel.org ext4 docs, high-level design). Copy-on-write designs need an allocator that never reuses a block that the previous consistent version still refers to; the space only becomes free after the new root is durable and no snapshot points at it.

Crash safety

This is the contract between the file system and the disk: after a crash, either the whole update happened or none of it. Two designs:

• Journal. Write-ahead log logic applied to metadata. ext4's jbd2 writes the changed blocks to a journal, flushes, writes a commit record, and only later writes the blocks to their home location. After a crash the journal is replayed to the last commit record. In the default data=ordered mode only metadata goes through the journal; data blocks are written before the metadata that points at them, but their content is not journaled (source: kernel.org ext4 docs, journal). data=journal logs data too and is slower; data=writeback drops the ordering.
• Copy-on-write. Write new blocks, then update one root (ZFS uberblock, Btrfs superblock, APFS checkpoint). Apple states that APFS needs no journal because copy-on-write avoids in-place changes "without the write-twice overhead of journaling" (source: Apple File System Guide, FAQ). The price is write amplification up the tree and fragmentation of files that are updated in the middle. The rules for what must reach the disk before what (crash-consistency-ordering, no page yet) are the delicate part. The disk's volatile write cache means a "completed" write is not yet durable; the flush/barrier path described in fsync, O_DSYNC and O_DIRECT is how the file system buys durability. Applications depend on guarantees that differ between file systems; Pillai et al. found that many application crash protocols rely on behaviours that only some file systems provide (source: Pillai et al., OSDI 2014). In-memory structures that are read far more often than written (dentry caches, mount tables, superblock lists) use RCU, so lookups take no lock.

Integrity

A journal protects against crashes; it does not notice a disk that returns wrong bytes. Checksums do. ext4 and Btrfs use CRC32C, cheap because modern CPUs have an instruction for it; Btrfs documents crc32c as its default and offers stronger options (source: Btrfs docs, checksumming). ZFS's property documentation names fletcher4 as the current default, with sha256, sha512, skein, edonr and blake3 as options (source: OpenZFS zfsprops(7)); APFS uses a Fletcher checksum for metadata (source: Apple File System Guide, FAQ). Where the checksum is stored matters: ZFS and Btrfs keep the checksum in the parent block pointer, not next to the data, so a block that was written to the wrong place or lost is detected, not just one that rotted. Parent-held checksums form a Merkle tree (merkle-tree, no page yet) over the whole pool, and self-healing needs a second copy to read from: mirrors or parity (erasure-coding, no page yet; OpenZFS raidz is a distributed-parity layout that avoids the RAID-5 "write hole" because writes are copy-on-write; source: OpenZFS zpoolconcepts(7)).

Data reduction

Per-block compression is cheap with a fast codec. LZ4 is the "always on" choice; Zstandard trades CPU for ratio and has levels. Compression has to happen before the checksum and the allocation, because the allocator needs the compressed size. Content-addressed storage appears as deduplication (blocks found by hash), and as cheap copies: OpenZFS tracks cloned blocks in a Block Reference Table with "minimal overhead", unlike its deduplication table (source: OpenZFS zfsconcepts(7)). Apple chose clones over dedup because individual extents can be encrypted (source: Apple File System Guide, FAQ).

Cache and I/O path

mmap and the page cache is where reads are served and writes are delayed: a write() copies into a dirty page and returns, and a flusher thread or fsync pushes it to the device. Replacement policy is pluggable: Linux uses an LRU variant; ZFS runs its own cache (ARC) because it owns the checksums and its blocks do not map to the page cache one to one. adaptive-replacement-cache (no page yet) balances recency and frequency lists with a learning rule (source: Megiddo and Modha, FAST 2003). Databases that run their own cache bypass this layer with O_DIRECT (fsync, O_DSYNC and O_DIRECT).

Device

SSD and NVMe internals explain why the file system cares about erase blocks, TRIM and the flash translation layer. Apple notes that on flash, writing two copies of metadata offers no extra protection because the translation layer may place both in the same NAND block, which is why APFS does not duplicate metadata (source: Apple File System Guide, FAQ). TRIM is sent only after the metadata change is persisted (same source).

Data and control flow

Appending 4 KiB to a file and calling fsync (ext4, data=ordered):

1. write() finds the file's inode, allocates a block (delayed allocation may defer the choice), copies the data into a page-cache page and marks it dirty. No disk I/O yet.
2. fsync() forces the dirty data block out first (ordered mode), waits for completion.
3. The metadata changes (inode size, extent record, bitmap) are collected into a jbd2 transaction and written to the journal, followed by a flush and then the commit record.
4. The call returns. The metadata is written to its final location later, in the background.
5. Time goes to the two device flushes (data and journal commit), not to CPU. On an SSD the cost of a flush depends on the drive's power-loss protection.

The same append on a copy-on-write file system (ZFS):

1. write() goes into the open transaction group in RAM.
2. If the call is synchronous, the change is also written to the intent log (ZIL), so fsync can return before the next transaction group commits. The ZIL is only read after a crash; by default it lives in the main pool and can be moved to a separate log device (source: OpenZFS zpoolconcepts(7)).
3. When the transaction group closes, data blocks are compressed, checksummed and written to new locations; the parent blocks are rewritten with new pointers and checksums up to the uberblock.
4. The uberblock write makes the whole group visible atomically; old blocks are freed unless a snapshot holds them.

Scaling

Limits, in the order you hit them:

1. Sync latency is bound by device flush time. Levers: a device with power-loss protection, a separate log device (ZFS) or an external journal (ext4), batching of commits, fewer fsync calls in the application.
2. Metadata operations (create, rename, stat on millions of files) are bound by tree depth and locking. Levers: wider B+ tree nodes, directory indexes, per-CPU or RCU-protected caches, spreading files over block groups.
3. Fragmentation under random overwrites, worst for copy-on-write. Levers: bigger extents, delayed allocation, defragmentation or rewrite tools, keeping free space headroom.
4. Memory for cache and checksum/dedup tables. Levers: ARC sizing, compression, avoiding dedup (its table must be fast to look up).
5. Capacity and bit rot across many disks. Levers: parity or mirrors, scrubs that re-read and verify every checksum.

Failure modes

Real implementations

Sources

• Linux kernel documentation, ext4: high-level design, journal (jbd2), extent tree
• OpenZFS manual pages: zfsprops(7), zpoolconcepts(7), zfsconcepts(7)
• Btrfs documentation: introduction, checksumming
• O. Rodeh, J. Bacik, C. Mason, BTRFS: The Linux B-Tree Filesystem, ACM Transactions on Storage 9(3), 2013. doi:10.1145/2501620.2501623
• Apple, Apple File System Guide, FAQ; Apple File System Reference (format spec, listed not read)
• T. S. Pillai et al., All File Systems Are Not Created Equal: On the Complexity of Crafting Crash-Consistent Applications, OSDI 2014. page
• N. Megiddo, D. S. Modha, ARC: A Self-Tuning, Low Overhead Replacement Cache, FAST 2003. page