File allocation and free space

Why it matters

Whether a 50 GB Postgres table is a handful of extents or ten thousand scattered blocks decides whether a sequential scan streams or crawls. The File system structure and Inodes and directories lessons cover the on-disk layout and the inode; this lesson is one field of it: which blocks a file gets, and how free blocks are tracked.

The idea

For every file the file system decides where its blocks go, how to find block n and how to grow it; for the volume, which blocks are free. The four classic allocation methods answer the first question differently.

Contiguous allocation

Each file is one run of consecutive blocks; the directory stores start and length. Block n is start plus n, a sequential read is one pass, and the metadata is two numbers. The cost is external fragmentation: free space splinters into gaps too small for new files, and a file cannot grow unless the block after it is free. CD-ROMs (ISO 9660) use it; the image is written once.

Linked allocation and the FAT

Each block points to the next; the directory stores the first. No external fragmentation and files grow freely, but reaching block n follows n pointers, each a disk read, and one corrupt pointer loses the rest. The File Allocation Table moves the pointers into one table at the start of the volume: entry b holds the block after b, an end marker, or zero for free. Chains are walked in a cached table; FAT32 and exFAT still run on every USB stick.

Indexed allocation and the classic inode

Collect a file's block numbers in an index block: random access is one lookup and growth appends a pointer. When a file outgrows one block of pointers, the Unix inode adds levels: twelve direct pointers, a single indirect pointer to a block of pointers, a double indirect pointer to a block of pointers to pointer blocks, and a triple indirect pointer one level deeper.

With 4 KB blocks and 4-byte block numbers a pointer block holds 1,024 entries, so the maximum file size is 12 direct blocks (48 KB) plus 1,024 via single indirect (4 MB) plus 1,024² via double (4 GB) plus 1,024³ via triple (4 TB): about 4 TB. Small files never touch an indirect block; a 1 GB file needs 256 pointer blocks.

Extents and why they won

Block pointers describe a contiguous 1 GB file with 262,144 numbers; an extent does it with three: logical start, physical start, length. ext4's extent is 12 bytes (48-bit physical block, 15-bit length, so up to 128 MB each); the inode holds four inline, then a B+ tree. XFS keeps a B+ tree of extents per file, NTFS stores data runs in the MFT record, Btrfs keeps extents in its copy-on-write B-tree. Extents won because metadata grows with fragments, not file size, and sequential I/O becomes a few large requests rather than thousands of small ones.

Free-space management

1. 1

   Bitmap

   One bit per block; ext4 keeps one per 128 MB block group (32,768 blocks, one 4 KB bitmap block), and a free run is found by word scan.
2. 2

   Free list

   Free blocks chained through pointers stored in the free blocks; cheap, but poor at finding contiguous space.
3. 3

   Grouping

   The first free block lists the next n free blocks, the last of which lists more; one read finds many.
4. 4

   Counting

   Store runs as start plus count; XFS indexes free extents in two B+ trees, by start and by length, to find the nearest run or one of a given size fast.

Locality and delayed allocation

ext4 divides the disk into block groups of 128 MB and places a file's blocks near its inode and directory. Delayed allocation postpones choosing physical blocks until writeback, when it knows how much data is coming and can allocate one large extent rather than a block per write call; ext4 (delalloc), XFS and Btrfs all do it, and the Journaling and crash consistency lesson covers what a crash before writeback loses. Programs that know a file's final size call fallocate to reserve one extent, as databases do for WAL segments.

Seeing and fixing fragmentation

filefrag -v lists a file's extents; tens of thousands means scattered. e4defrag -c scores an ext4 path and e4defrag rewrites files into fewer extents; xfs_fsr is the XFS equivalent. Append-heavy files, sparse files written out of order and volumes over 90 percent full fragment most; SSDs care far less.

Trade-offs

Contiguous allocation is fastest and least flexible. Linked allocation never fragments externally but random access and reliability are poor. Indexed allocation is cheap to access and costly in pointers. Extents keep metadata small and I/O large only while contiguous space exists, hence block groups, delayed allocation and preallocation.

In an interview

Tie structure to number: "4 KB blocks and 4-byte pointers give 1,024 pointers per block, so direct, single, double and triple indirect reach about 4 TB from a 128-byte inode." On a production choice: "We preallocate WAL segments with fallocate so each is one extent."