Chapter 1: The Story of ext
Chapter 1: The Story of ext
Filesystems evolve alongside operating systems and storage hardware. The story of the extended filesystem family (ext, ext2, ext3, ext4) is inextricably linked to the history of Linux itself. As Linux transformed from a student’s hobby project on a single Intel 386 PC into the operating system powering the world’s most demanding supercomputers and cloud hyperscalers, its primary storage architecture had to undergo four generations of major architectural reinvention.
This chapter traces the evolutionary arc of ext: from its origins as an escape from Minix filesystem limitations in 1992 to the introduction of ext2’s production block groups, ext3’s transaction journaling, ext4’s petabyte-scale extent trees, and the delicate balance of design continuity and breaking changes.
The Original ext Filesystem (1992)
When Linus Torvalds released the initial version of Linux in 1991, it did not possess its own native filesystem. Instead, Linux relied on the filesystem of the Minix operating system, authored by Andrew Tanenbaum.
While Minix served to bootstrap Linux, its design was severely constrained: - Maximum Filesystem Size: \(64\text{ Megabytes}\) (due to 16-bit block addresses). - Filename Length Limit: Strictly limited to \(14\text{ characters}\). - Single Timestamp: Maintained only a single modification timestamp per inode.
To overcome these stifling boundaries, French software engineer Rémy Card designed the Extended Filesystem (ext), merged into Linux 0.96c in April 1992. The original ext filesystem introduced two historic innovations: 1. It decoupled the Linux kernel from Minix by utilizing the newly authored Virtual Filesystem (VFS) abstraction layer. 2. It expanded maximum filesystem capacity to \(2\text{ Gigabytes}\) and allowed filenames up to \(255\text{ characters}\).
However, the original ext had significant weaknesses. It utilized linked lists rather than bitmaps to track free blocks and free inodes. Over time, as files were created, truncated, and deleted, the linked lists became heavily fragmented, causing severe performance degradation. Furthermore, ext lacked clean state tracking flags, meaning that unmounting an unclean system required an agonizing, complete disk scan.
ext2: A Production Filesystem (1993-2001)
Recognizing the architectural dead-ends of original ext, Rémy Card, along with Wayne Davison and Stephen Tweedie, completely redesigned the architecture, releasing the Second Extended Filesystem (ext2) in January 1993.
ext2 established the foundational on-disk topology that survives in ext4 today:
┌────────────────────────────────────────────────────────────────────────┐
│ EXT2 ON-DISK ARCHITECTURE │
│ │
│ Boot Block Group 0 Block Group 1 Block Group N │
│ Block (32,768 Blocks) (32,768 Blocks) (32,768 Blocks) │
│ ┌─────┐ ┌─────────────────┐ ┌─────────────────┐ ┌─────────────────┐│
│ │1 KiB│ │Superblock │ │Backup Superblock│ │Backup Superblock││
│ │ │ │Group Descriptors│ │Group Descriptor │... │Group Descriptor ││
│ │Pad │ │Block Bitmap │ │Block Bitmap │ │Block Bitmap ││
│ │ │ │Inode Bitmap │ │Inode Bitmap │ │Inode Bitmap ││
│ │ │ │Inode Table │ │Inode Table │ │Inode Table ││
│ │ │ │Data Blocks │ │Data Blocks │ │Data Blocks ││
│ └─────┘ └─────────────────┘ └─────────────────┘ └─────────────────┘│
└────────────────────────────────────────────────────────────────────────┘Key Innovations of ext2
- Block Groups: Instead of placing all inodes at the beginning of the disk and all data at the end (which caused excessive disk head travel on spinning hard drives), ext2 partitioned the disk into localized Block Groups. Each group contained its own allocation bitmaps, inode table, and data blocks, keeping file metadata physically close to the file’s data.
- Allocation Bitmaps: Replaced linked lists with compact bit arrays where each bit represents the allocated status (\(0 = \text{free}\), \(1 = \text{used}\)) of a block or inode.
- Superblock Redundancy: The master superblock (which describes the entire filesystem layout) was replicated across multiple block groups, allowing recovery if Block Group 0 suffered physical sector corruption.
- Extensible Inode Attributes: Introduced immutable (
+i) and append-only (+a) extended attributes viachattr.
ext2 became the unchallenged standard filesystem across all Linux distributions throughout the late 1990s. Its main vulnerability, however, was crash recovery: if power was lost during write operations, the filesystem was left in an inconsistent state, requiring e2fsck to scan every single inode and directory on disk—a process that could take hours or days on multi-gigabyte server disks.
ext3: Adding Journaling (2001)
In November 2001, Linux 2.4.15 merged the Third Extended Filesystem (ext3), designed by Stephen Tweedie.
The defining advancement of ext3 was Journaling via the Journaling Block Device (JBD) layer. Rather than writing metadata updates directly to disparate locations on disk, ext3 first wrote changes sequentially to a dedicated, circular log area called the journal. Once the transaction committed to the journal, the changes were written to their permanent on-disk locations (checkpointing).
┌────────────────────────────────────────────────────────────────────────┐
│ EXT3 JOURNALING PIPELINE │
│ │
│ 1. File Operation (mkdir / write / unlink) │
│ │ │
│ ▼ │
│ 2. Write Transaction to Sequential Journal Log │
│ [Descriptor Block] -> [Metadata Blocks] -> [Commit Block] │
│ │ │
│ ▼ (Transaction Committed) │
│ 3. Checkpoint asynchronously to permanent on-disk structures │
│ (Block Groups, Inode Tables, Directory Blocks) │
│ │ │
│ ▼ On Power Loss / Crash: │
│ Fast Recovery: Replay journal from last valid commit block (< 2 sec) │
└────────────────────────────────────────────────────────────────────────┘In-Place Upgrade Compatibility
A masterstroke of ext3’s design was 100% backward and forward compatibility with ext2. Because ext3 implemented journaling as an allocated inode on the existing ext2 layout (typically inode 8), an existing ext2 filesystem could be converted to ext3 online simply by running:
tune2fs -j /dev/sdb1Furthermore, an ext3 filesystem could be mounted directly by an older ext2 driver; the ext2 driver simply ignored the journal inode and treated it as a standard clean ext2 partition.
ext4: Scaling to Petabytes (2008-Present)
By the mid-2000s, storage capacities were exploding. Enterprise storage arrays were reaching tens of terabytes, exposing severe bottlenecks in ext3: - Indirect Block Limits: Mapping a multi-gigabyte file required millions of individual 4-byte block pointers, consuming excessive metadata space and causing heavy fragmentation. - Capacity Ceilings: ext3 was architecturally limited to a \(16\text{ TiB}\) filesystem size and a \(2\text{ TiB}\) maximum single file size. - Directory Lookup Bottlenecks: Searching directories with hundreds of thousands of files required linear scans of unindexed directory blocks.
In 2006, a team led by Mingming Cao, Andreas Dilger, Alex Tomas, Dave Kleikamp, and Theodore Ts’o proposed major extensions to ext3. In October 2008, Linux 2.6.28 officially declared ext4 stable and ready for enterprise production.
Core Breakthroughs of ext4
- Extents: Replaced indirect block pointer lists with compact range descriptors (\((\text{logical block}, \text{length}, \text{physical block})\)). A single extent can represent up to \(128\text{ MiB}\) of contiguous storage in only 12 bytes.
- 64-bit Block Addressing: Expanded block addressing from 32-bit to 48-bit (and 64-bit on-disk structures), raising maximum filesystem size to \(1\text{ Exabyte}\) (\(10^{18}\text{ bytes}\)) and maximum file size to \(16\text{ TiB}\).
- Multi-Block Allocator (
mballoc): Replaced slow single-block allocation loops with a buddy-bitmap allocator capable of allocating thousands of contiguous blocks in a single operation. - Delayed Allocation (
delalloc): Postpones physical block allocation until dirty pages are flushed from RAM to disk, allowingmballocto allocate larger contiguous chunks and reducing fragmentation. - HTree Directory Indexing: Replaces linear directory scans with constant-depth B-tree hashing, maintaining sub-millisecond lookup speeds in directories containing millions of files.
- Nanosecond Timestamps & Y2038 Resolution: Extended timestamp fields from 32 bits to 64 bits with nanosecond resolution, extending timestamp validity past the January 2038 Unix epoch cutoff to the year 2446.
- Metadata Checksumming (
metadata_csum): Protects all critical filesystem structures (superblocks, group descriptors, extent trees, directory entries) with hardware-accelerated CRC32c checksums to catch silent hardware data corruption.
Design Continuity and Breaking Changes
The extended filesystem family achieved unprecedented longevity by adhering to a consistent core philosophy while introducing breaking changes only when strictly necessary:
┌────────────────────────────────────────────────────────────────────────┐
│ EXT GENERATIONAL COMPARISON │
│ │
│ Feature ext2 (1993) ext3 (2001) ext4 (2008+) │
│ ─────────────────── ───────────── ───────────── ───────────── │
│ Max File Size 2 TiB 2 TiB 16 TiB │
│ Max Filesystem Size 16 TiB 16 TiB 1 Exabyte │
│ Block Mapping Indirect blocks Indirect blocks B+ Extent Tree │
│ Crash Recovery Full e2fsck JBD Journal JBD2 + Checksum│
│ Allocation Unit Single-block Single-block Multi-Block │
│ Allocation Timing Immediate Immediate Delayed │
│ Timestamps 32-bit (sec) 32-bit (sec) 64-bit (nsec) │
│ Checksumming None None CRC32c │
│ Directory Index Linear Linear / HTree HTree (B-tree) │
└────────────────────────────────────────────────────────────────────────┘The Incompat Boundary
While ext2, ext3, and ext4 share structural DNA, modern ext4 introduces feature flags marked INCOMPAT_EXTENTS and INCOMPAT_64BIT. Once ext4 writes extent-mapped files or 64-bit group descriptors to disk, legacy ext3 drivers can no longer mount the filesystem read-write.
However, backward compatibility was preserved where it mattered: the ext4 driver can mount older ext2 and ext3 filesystems natively, migrating files to modern extents on-demand.