Btrfs: The B-tree File System

In the landscape of modern file systems, Btrfs (B-tree File System, pronounced "Butter FS" or "Better FS") represents one of the most ambitious attempts to reimagine how Linux manages storage. Born from the recognition that traditional file systems like ext4 were reaching their architectural limits, Btrfs was designed from the ground up to address the storage challenges of the 21st century.

Btrfs isn't merely an incremental improvement over its predecessors—it's a fundamental rethinking of file system architecture. Where ext4 added features like extents and journaling to the venerable ext2 foundation, Btrfs started with a clean slate, incorporating lessons learned from decades of file system research and the revolutionary ideas pioneered by Sun's ZFS.

Btrfs development began at Oracle Corporation in 2007, initiated by Chris Mason, a veteran file system developer who had previously worked on ReiserFS. The project emerged from a recognition that existing Linux file systems, despite their maturity and reliability, could not meet the evolving demands of modern storage:

The Limitations of Traditional File Systems:

• Static volume management: Traditional file systems required separate volume managers (like LVM) to pool storage, add devices, or resize partitions—operations that were complex and sometimes dangerous.

• No native checksumming: Data corruption could go undetected. Silent bit rot, controller errors, and firmware bugs could corrupt data without the file system's knowledge.

• Limited snapshot capabilities: While LVM offered snapshots, they were inefficient (requiring copy-on-write at the block level) and couldn't leverage file system semantics.

• Fixed metadata structures: File systems like ext4 used fixed-size metadata structures that couldn't adapt to varying workload characteristics.

• Single-device thinking: Most file systems assumed a single underlying block device, requiring external RAID controllers or LVM for multi-device configurations.

The Design Goals:

From its inception, Btrfs was designed with several ambitious goals:

1. Copy-on-Write Architecture: Never overwrite data in place. Instead, write modifications to new locations, enabling atomic updates and cheap snapshots.

2. Integrated Volume Management: Pool multiple devices, add/remove storage dynamically, and handle RAID without external tools.

3. Data and Metadata Checksumming: Every block of data and metadata carries a checksum, enabling detection (and with redundancy, correction) of corruption.

4. Efficient Snapshots and Clones: Create instant point-in-time copies without duplicating data.

5. Online Operations: Grow, shrink, defragment, scrub, and check the file system while it remains mounted and in use.

6. Scalability: Support exabyte-scale storage with efficient handling of billions of files.

These goals required a completely new architecture—one built around a data structure capable of efficiently handling all these operations: the B-tree.

The choice of B-trees as Btrfs's fundamental data structure wasn't arbitrary—it was a carefully considered engineering decision based on decades of database and file system research.

Understanding B-trees:

A B-tree is a self-balancing tree data structure that maintains sorted data and allows searches, sequential access, insertions, and deletions in logarithmic time. Unlike binary trees where each node has at most two children, B-tree nodes can have many children—making them particularly well-suited for storage systems that read and write data in large blocks.

Key B-tree Properties:

The B-tree Variant in Btrfs:

Btrfs uses a variant called B+ trees with copy-on-write semantics. In a traditional B+ tree:

• All actual data (values) reside in leaf nodes
• Internal nodes contain only keys and child pointers
• Leaf nodes are linked together for efficient sequential access

Btrfs extends this with copy-on-write (COW):

• When a leaf is modified, a new copy is written to a different location
• The parent pointer is updated (in a new copy of the parent)
• This propagates up to the root, which is atomically updated
• The old tree remains intact until its space is reclaimed

This COW approach enables Btrfs's snapshot functionality and ensures atomicity—either a complete, consistent update is visible, or none of it is.

Unlike traditional file systems that use separate structures for different purposes (inodes, block bitmaps, extent trees), Btrfs unifies almost everything into multiple B-trees, all sharing the same fundamental structure but storing different types of items.

The Forest of Trees:

Btrfs maintains several distinct trees, each serving a specific purpose:

The Unified Key Structure:

All Btrfs items are located using a 136-bit key consisting of three components:

[ objectid: 64 bits | type: 8 bits | offset: 64 bits ]

• objectid: Identifies the object (usually an inode number or extent address)
• type: Specifies the item type (INODE_ITEM, EXTENT_DATA, DIR_ITEM, etc.)
• offset: Context-dependent (file offset, directory hash, parent ID, etc.)

This unified key format means all trees use the same lookup algorithms, simplifying code and enabling optimizations to benefit all operations.

Example Key Types:

Understanding how Btrfs organizes data on physical storage is essential for comprehending its capabilities and performance characteristics.

The Superblock:

Like all file systems, Btrfs begins with a superblock—the fixed location where the file system's root information is stored. Btrfs maintains multiple superblock copies at fixed offsets for redundancy:

• Primary: 64 KiB offset
• Mirror 1: 64 MiB offset
• Mirror 2: 256 GiB offset (only on devices large enough)

The superblock contains:

• File system UUID and label
• Total and used bytes
• Root tree location (the entry point to all trees)
• Chunk tree location (for address translation)
• Generation number (transaction counter)
• Compatibility flags

Chunks and Block Groups:

Btrfs abstracts physical devices through a two-level address mapping:

Logical Addresses → Chunks → Physical Addresses

1. Logical Address Space: A single unified address space spanning potentially multiple devices. The file system internally uses logical addresses everywhere.

2. Chunks: Contiguous regions of logical address space. Each chunk maps to one or more physical device locations.

3. Block Groups: Logical groupings of chunks with the same allocation purpose (data, metadata, system) and redundancy profile (single, DUP, RAID0, RAID1, etc.).

This abstraction enables Btrfs to:

• Span multiple devices transparently
• Implement various RAID profiles at the chunk level
• Move data between devices online
• Add and remove devices without reformatting

Node Size and Sector Size:

Btrfs uses a configurable node size (default: 16 KiB) for its tree nodes and a sector size (typically 4 KiB) for data allocation. The node size affects:

• Fanout: Larger nodes hold more items, creating shallower trees
• I/O efficiency: Larger nodes amortize metadata I/O but may waste space for small updates
• Fragmentation: Smaller nodes adapt better to random updates

The separation of node size from sector size allows metadata to use larger, more efficient blocks while data can be allocated at sector granularity.

Btrfs reimagines the traditional Unix inode concept, storing inode data as variable-sized items within its B-trees rather than fixed structures in a dedicated inode table.

The INODE_ITEM:

Each file or directory has an inode item containing:

struct btrfs_inode_item {
    __le64 generation;     // Creation transaction
    __le64 transid;        // Last modification transaction
    __le64 size;           // File size in bytes
    __le64 nbytes;         // Actual bytes used
    __le64 block_group;    // Preferred allocation group
    __le32 nlink;          // Hard link count
    __le32 uid;            // Owner user ID
    __le32 gid;            // Owner group ID
    __le32 mode;           // File mode/permissions
    __le64 rdev;           // Device ID (for device files)
    __le64 flags;          // Inode flags
    __le64 sequence;       // Sequence for fsync
    struct btrfs_timespec atime;  // Access time
    struct btrfs_timespec ctime;  // Change time
    struct btrfs_timespec mtime;  // Modification time
    struct btrfs_timespec otime;  // Creation time
};

Key Differences from Traditional Inodes:

Inline Data:

For very small files, Btrfs can store file data inline within the EXTENT_DATA item itself, eliminating the need for a separate data extent allocation:

• Files under ~2KB (depending on node size and metadata) can be fully inline
• Reduces I/O by fetching metadata and data together
• Saves space by avoiding extent allocation overhead
• Automatically promoted to regular extents as files grow

This optimization is particularly beneficial for workloads with many tiny files (configuration files, Git object stores, etc.).

The Inode Namespace:

Unlike ext4's global inode number space, Btrfs inodes are scoped to their subvolume. Each subvolume has its own inode number space starting from 256 (the first non-reserved inode). This means:

• The same inode number can exist in different subvolumes
• Cross-subvolume hard links are not possible
• Subvolumes provide namespace isolation

Btrfs uses extents to map file data to disk locations—contiguous ranges of disk blocks that store file contents. This extent-based approach provides significant advantages over traditional block mapping.

EXTENT_DATA Items:

For each contiguous range of file data, Btrfs creates an EXTENT_DATA item in the file's inode tree:

Key: [inode, EXTENT_DATA, file_offset]
Value: {
    generation,
    ram_bytes,      // Uncompressed size
    compression,    // Compression type (none/zlib/lzo/zstd)
    encryption,     // Encryption type (reserved)
    type,           // Regular, inline, or prealloc
    disk_bytenr,    // Disk location of extent
    disk_num_bytes, // Size on disk (may differ due to compression)
    offset,         // Offset within the extent
    num_bytes       // Bytes used from this extent
}

Extent Sharing and Reflinks:

One of Btrfs's most powerful features is extent sharing. Multiple files (or multiple regions of the same file) can reference the same physical extent:

• Snapshots: A snapshot shares all extents with its source; only modified extents diverge
• Reflinks (cp --reflink): Instantly copy files by sharing extents
• Deduplication: Tools can identify identical blocks and merge them

To track sharing, Btrfs maintains back-references in the extent tree:

The Extent Tree:

The extent tree is Btrfs's allocation manager, tracking:

1. Which extents are allocated (EXTENT_ITEM)
2. Who references each extent (back-references)
3. Free space (implicitly or via Free Space Tree)

Back-references are crucial for:

• Determining when an extent can be freed (reference count → 0)
• Relocating data during balance operations
• Verifying file system integrity during scrub

Free Space Tracking:

Historically, Btrfs tracked free space by walking the extent tree—an expensive operation that caused mount delays on large file systems. Modern Btrfs includes a dedicated Free Space Tree that explicitly tracks free regions, dramatically improving mount time and allocation speed.

Understanding Btrfs's position relative to other file systems helps clarify when it's the right choice.

Btrfs vs. ext4:

Btrfs vs. ZFS:

When to Choose Btrfs:

We've established the foundational understanding of Btrfs architecture. Let's consolidate the essential concepts:

What's Next:

With the B-tree architecture understood, we'll explore Btrfs's Copy-on-Write (COW) semantics in depth—the mechanism that makes atomic updates, snapshots, and data integrity guarantees possible.