File Allocation Methods

When you save a 2GB video file, something has to decide where all those bytes go on disk. The file allocation method is the strategy a file system uses to assign disk space to files. Choose the wrong allocation method and your hard drive becomes a fragmented mess. Use the right one, and your system hums along efficiently for years.

This isn’t just theory—different allocation methods directly explain why:

• FAT USB drives get slow after copying many files
• Linux file systems survive crashes without data loss
• Database systems carefully manage their own files rather than relying on the OS

Understanding allocation methods gives you insight into every storage decision you’ll ever make.

Introduction

File allocation methods are the strategies file systems use to assign physical disk blocks to files. When you save any file—documents, videos, applications—your operating system must decide which disk sectors will store each byte. The allocation method determines how efficiently your disk space is used and how quickly files can be read and written.

Three fundamental approaches exist: contiguous allocation (files stored in consecutive blocks), linked allocation (blocks scattered with pointers connecting them), and indexed allocation (a dedicated index block tracks all file blocks). Every file system—from FAT to NTFS to ext4—implements variations of these approaches, each with distinct performance and reliability trade-offs.

This article explores all three allocation methods with practical diagrams, real-world failure scenarios, and production-ready code examples. You’ll understand why FAT drives slow down with heavy use, how ext4 handles crashes without data loss, and why databases often bypass the OS file system entirely. By the end, you’ll be equipped to choose the right file system for any workload and diagnose allocation-related performance problems.

When to Use / When Not to Use

Allocation method knowledge helps with system design and troubleshooting.

When allocation method understanding helps:

• Formatting drives for specific workloads (large files vs many small files)
• Understanding why fragmentation occurs and how to prevent it
• Designing applications that interact heavily with storage
• Troubleshooting performance issues in file-heavy workloads
• Choosing the right file system for a given use case

When you can rely on defaults:

• General desktop and server use (ext4/XFS/NTFS handle this well)
• Cloud storage where abstracted block devices are provided
• Containerized workloads with overlay file systems

Architecture or Flow Diagram

graph TD
    A[File Creation Request] --> B{Allocation Strategy}

    B --> C[Contiguous Allocation]
    B --> D[Linked Allocation]
    B --> E[Indexed Allocation]

    C --> F[Find large enough hole]
    D --> G[Track free blocks with linked list]
    E --> H[Build index block for file]

    F --> I[Allocate consecutive blocks]
    G --> J[Allocate from anywhere, link blocks]
    H --> K[Pointers in index block]

    style C stroke:#ff00ff,stroke-width:2px
    style D stroke:#00fff9,stroke-width:2px
    style E stroke:#ff00ff,stroke-width:2px

Core Concepts

Contiguous Allocation

The simplest approach: allocate consecutive blocks for each file.

File "video.mp4" - 5 blocks:
[Block 100][Block 101][Block 102][Block 103][Block 104]
                   ▲ Start block
                   └────── 5 consecutive blocks ──────┘

Directory Entry:
  Name: video.mp4
  Start: 100
  Length: 5

Advantages:

• Excellent sequential read performance (no seeks between blocks)
• Simple to implement
• Small metadata overhead (only start block + length needed)

Disadvantages:

• External fragmentation (must find large enough continuous hole)
• Compaction required to reclaim space
• File growth problematic (adjacent blocks may be taken)

// Simulated contiguous allocation
typedef struct {
    char filename[255];
    int start_block;
    int length_blocks;
} FileEntry;

int allocate_contiguous(int file_id, int blocks_needed) {
    int start = find_contiguous_hole(blocks_needed);
    if (start == -1) {
        // No hole large enough
        return -1;
    }
    allocate(start, blocks_needed);
    return start;
}

Linked Allocation

Each block contains a pointer to the next block:

File "document.txt" - 4 blocks:

[Block 50][data][Block 89] -> [Block 12][data][Block 200] ->
[Block 200][data][NULL]    -> [Block 75][data][NULL]

Directory Entry:
  Name: document.txt
  Start: 50
  End: 75 (cached or NULL if unknown)

Advantages:

• No external fragmentation (use any free block)
• File can grow easily (just add more blocks)
• Simple directory entry (only start block needed)

Disadvantages:

• Poor random access (must follow chain from start)
• Pointer overhead (4-8 bytes per block)
• Pointer integrity critical (corrupted pointer = data loss)
• No concept of file size without scanning

// Linked allocation block structure
typedef struct {
    char data[BLOCK_SIZE - sizeof(int)];
    int next_block;  // Pointer to next block, -1 = end of file
} LinkedBlock;

Indexed Allocation

Store all block pointers in an index block:

File "database.db" - 7 blocks:

Index Block (Block 500):
┌─────────────────────────────────┐
│ Pointer: 120                    │
│ Pointer: 45                     │
│ Pointer: 389                    │
│ Pointer: 12                     │
│ Pointer: 201                    │
│ Pointer: 88                     │
│ Pointer: 156                    │
│ Pointer: -1 (end of index)      │
└─────────────────────────────────┘

         │
         ├──> [Block 120][data]
         ├──> [Block 45][data]
         ├──> [Block 389][data]
         ├──> [Block 12][data]
         ├──> [Block 201][data]
         ├──> [Block 88][data]
         └──> [Block 156][data]

Directory Entry:
  Name: database.db
  Index Block: 500

Advantages:

• Direct random access to any block
• Good sequential performance
• Blocks can be anywhere on disk
• File metadata self-contained in index block

Disadvantages:

• Index block overhead (1 block per file regardless of size)
• Limit on file size based on index block entries
• Extra I/O to read index block first

Index Block Extension (ext2/3/4 approach): For large files, use multiple index blocks in a tree structure:

• Single indirect block (pointers to data blocks)
• Double indirect block (pointers to single indirect blocks)
• Triple indirect block (pointers to double indirect blocks)

FAT: File Allocation Table

FAT uses a variation of linked allocation with a central table:

graph LR
    A[FAT Table] --> B[Cluster 0]
    A --> C[Cluster 1]
    A --> D[Cluster 2]
    B --> E[End of file]
    C --> D
    D --> E

    style A stroke:#ff00ff,stroke-width:3px

The FAT table stores one entry per cluster:

• 0x0000: Free cluster
• 0xFFFF: End of file
• Other values: Next cluster in chain

FAT-16 Entry Example:
┌────────┬────────┬────────┬────────┐
│ Cluster│ Value  │ Meaning│ Next   │
├────────┼────────┼────────┼────────┤
│   0    │ 0xFFF8 │ Media  │ -      │
│   1    │ 0xFFFF │ EOF    │ -      │
│   2    │   5    │ Next   │ Cluster 5
│   3    │   6    │ Next   │ Cluster 6
│   4    │   0    │ Free   │ -      │
│   5    │ 0xFFFF │ EOF    │ -      │
│   6    │ 0xFFFF │ EOF    │ -      │
└────────┴────────┴────────┴────────┘

File "example.txt" starting at cluster 2:
[Cluster 2] -> [Cluster 5] -> EOF

FAT Fragmentation Physics: On FAT, fragmentation isn’t just about free space scatter—it’s about how the FAT chain grows. When a file grows, new clusters are allocated wherever free space exists. Over time, a file’s cluster chain becomes a scattered sequence across the drive.

The firmware’s read-ahead cache compounds this: it caches sequential clusters during reads, but random access patterns (like video seeking) trigger cache misses and constant head movement. A fragmented FAT USB drive performing 4MB sequential writes develops cluster chains where each chunk spans 20+ non-contiguous clusters. Reading back the video requires 20+ seeks per chunk, dropping throughput from 20MB/s to 2MB/s.

The FAT table itself stays in memory—small for 4GB drives, but grows with volume size. FAT12 (floppy era) had tiny tables; FAT16 consumed meaningful RAM on early systems; FAT32 balances table size against cluster granularity for modern removable media.

ext2/3/4: Block Bitmap and Extents

Linux’s ext file systems use bitmaps and extent trees:

Block Bitmap: One bit per block indicates free/allocated. Fast for finding free space.

Extent-Based Allocation: Instead of listing every block, ext4 uses extents—contiguous ranges:

Extent format in ext4:
Start block: 1024
Length: 50 blocks  (means blocks 1024-1073 are contiguous)

File stored in extents:
  Extent 1: start=1024, len=50   (blocks 1024-1073)
  Extent 2: start=2048, len=25    (blocks 2048-2072)
  Extent 3: start=4096, len=10    (blocks 4096-4105)

This reduces metadata overhead for large, contiguous files and minimizes fragmentation impact on performance.

Extent Tree Structure in ext4: The inode stores an extent tree rather than simple block pointers. The extent header contains:

• eh_entries: Number of valid extent entries
• eh_max: Maximum entries in this node
• eh_depth: Tree depth (0 = all extents in inode, 1+ = external nodes)

Extent entries store contiguous ranges: {start block, length, start + length - 1}. A file with blocks 1024-1073 and 2048-2099 needs only two extent entries rather than 104 individual block pointers. This dramatically reduces inode size and speeds up metadata reads.

Delayed Allocation (delalloc): ext4 batches write allocations and delays physical block assignment until writeback time. Writes accumulate in the page cache, and the allocator batches them together—reducing fragmentation from scattered small allocations.

Caveat: If power fails before delayed allocations are written, data is lost. The data=ordered mode in ext4 ensures file data hits the journal before metadata, reducing this risk at a slight performance cost.

NTFS: MFT and Attribute Records

NTFS uses the Master File Table (MFT) where each file has one or more records:

MFT Record for large file:

$DATA attribute (non-resident):
  Runlist: cluster 1000-1023, then 2048-2063, then 4096-4105

$FILE_NAME attribute:
  Name: large_video.avi
  Size: 2GB

NTFS can store data directly in the MFT for small files (under 900 bytes), or use runlists pointing to clusters scattered across the volume.

MFT Structure Details: The MFT is itself a file, stored at the beginning of the volume in a reserved zone. Each record contains attribute/value pairs:

• $STANDARD_INFORMATION: Timestamps, permissions, flags
• $FILE_NAME: File name (multiple possible for hard links)
• $DATA: File content (resident within MFT or non-resident with runlist)
• $BITMAP: For sparse files, tracks which clusters are allocated

Small files store content entirely within the MFT record—fastest possible access. Larger files store runlists pointing to data clusters scattered across the volume. The MFT can grow dynamically and maintains reserved zones for critical metadata.

NTFS Fragmentation Handling: Unlike ext4’s extent tree, NTFS uses runlists that can become fragmented when the MFT grows or large files have clusters scattered across the volume. NTFS uses update sequence numbers (USNs) to detect torn writes and ensure consistency—similar to journaling but implemented at the record level.

Production Failure Scenarios

Scenario 1: FAT Fragmentation Spiral

What happened: A security camera system wrote continuous 4MB video chunks to a FAT32 USB drive. After a week, the drive showed massive fragmentation. Read speeds dropped from 20MB/s to 2MB/s. Playback became choppy.

Why it happened: FAT can’t handle many small allocations well. Each video chunk became a linked chain of clusters scattered across the drive. Reading one file meant dozens of seeks.

Detection:

# Check fragmentation on FAT/FAT32
defrag /c: /v  # Windows

# Or use CHKDSK
chkdsk e: /r  # Scan and fix

Mitigation:

• Use larger cluster sizes when formatting (32KB instead of 4KB)
• Periodically defragment FAT drives
• For video recording, use dedicated file systems (NTFS, ext4)
• Consider exFAT for large files on removable media

Scenario 2: ext4 Inode Exhaustion vs Block Exhaustion

What happened: A mail server stored millions of tiny email files. df showed plenty of disk space, but new files couldn’t be created. The issue: inode exhaustion. All inodes were allocated even though blocks remained.

Detection:

df -i  # Check inode usage
# Filesystem   Inodes    IUsed   IFree  IUse% Mounted on
# /dev/sda1  100M       99.9M   100K   99%   /var/mail

tune2fs -l /dev/sda1 | grep -i inode
# Inode count:              100000000
# Inodes per group:         8192
# Block size:               4096

Mitigation:

• Use mkfs.ext4 -N <inode_count> to provision more inodes when formatting
• Set inode ratio with mkfs.ext4 -i <bytes_per_inode>
• Monitor inode usage with alerting

Scenario 3: Database File Fragmentation

What happened: A PostgreSQL database grew to 500GB over months. Query performance degraded despite hardware having plenty of CPU and memory. Analysis showed database file fragmentation at 78%.

Detection:

# Check fragmentation on ext4
sudo fsck.ext4 -nv /dev/sda1

# Check extent tree depth
sudo debugfs -R "extents -v /path/to/database" /dev/sda1

Mitigation:

• Use e4defrag to defragment:

  sudo e4defrag /var/lib/postgresql/data/

• For databases, consider preallocate or use raw partitions

• Choose noatime mount option to reduce fragmentation

• Plan capacity to avoid >80% disk fullness

Database File Management: Why Raw I/O?

Databases like PostgreSQL and Oracle often bypass the OS file system entirely, using raw partitions or raw I/O. Understanding why:

Page cache bypass: When you write() through the OS, data goes to the page cache first. The database’s buffer pool is already a cache optimized for database access patterns. Double caching (OS page cache + database buffer pool) wastes RAM and adds CPU overhead.

fsync control: The database needs to control exactly when data is on disk. The OS may delay writes, combine them, or reorder them. For a database transaction to be durable, it needs fsync() — and the database knows exactly what needs syncing and when, without trusting the OS write-back scheduler.

Block size alignment: Database pages (typically 8KB) can be aligned to RAID stripe boundaries with raw I/O, preventing read-modify-write cycles on partial stripes.

Predictable latency: With raw I/O, I/O completion is predictable. With buffered I/O, a write might return “success” while data is still in the page cache awaiting writeback — causing durability surprises on crashes.

Implementation on Linux: posix_fallocate() for preallocation, O_DIRECT flag to bypass the page cache, and fsync() calls after critical transactions. PostgreSQL’s effective_io_concurrency setting tunes parallel I/O for raw device access.

Trade-off Table

Implementation Snippet

Simulating Block Allocation with Bitmaps (Python)

#!/usr/bin/env python3
"""Simulate file allocation with block bitmap."""

class FileSystemSimulator:
    def __init__(self, total_blocks=1000, block_size=4096):
        self.total_blocks = total_blocks
        self.block_size = block_size
        self.block_bitmap = [0] * total_blocks  # 0 = free, 1 = allocated
        self.files = {}

    def allocate_contiguous(self, filename, size_blocks):
        """Allocate contiguous blocks (First Fit)."""
        start = self._find_contiguous_hole(size_blocks)
        if start == -1:
            return None

        # Mark blocks as allocated
        for i in range(start, start + size_blocks):
            self.block_bitmap[i] = 1

        self.files[filename] = {
            'start': start,
            'length': size_blocks,
            'type': 'contiguous'
        }
        return start

    def allocate_linked(self, filename, size_blocks):
        """Allocate using linked list approach."""
        free_blocks = self._find_free_blocks(size_blocks)
        if len(free_blocks) != size_blocks:
            return None

        # Allocate and link
        for i, block in enumerate(free_blocks):
            self.block_bitmap[block] = 1
            if i < len(free_blocks) - 1:
                # Store next pointer (simplified: store in separate structure)
                pass

        self.files[filename] = {
            'start': free_blocks[0],
            'blocks': free_blocks,
            'type': 'linked'
        }
        return free_blocks[0]

    def _find_contiguous_hole(self, size_needed):
        """Find first contiguous hole of sufficient size."""
        consecutive = 0
        start = -1

        for i, allocated in enumerate(self.block_bitmap):
            if allocated == 0:
                if consecutive == 0:
                    start = i
                consecutive += 1
                if consecutive >= size_needed:
                    return start
            else:
                consecutive = 0
                start = -1

        return -1

    def _find_free_blocks(self, count):
        """Find any free blocks."""
        free = []
        for i, allocated in enumerate(self.block_bitmap):
            if allocated == 0:
                free.append(i)
                if len(free) >= count:
                    return free
        return []

    def defragment(self, filename):
        """Defragment a linked file to contiguous allocation."""
        if filename not in self.files or self.files[filename]['type'] != 'linked':
            return False

        old_blocks = self.files[filename]['blocks']
        size = len(old_blocks)
        new_start = self._find_contiguous_hole(size)

        if new_start == -1:
            return False

        # Move data (in reality, this is a complex operation)
        for i in range(size):
            self.block_bitmap[old_blocks[i]] = 0
            self.block_bitmap[new_start + i] = 1

        self.files[filename] = {
            'start': new_start,
            'length': size,
            'type': 'contiguous'
        }
        return True

    def print_status(self):
        """Display allocation status."""
        allocated = sum(self.block_bitmap)
        print(f"Total blocks: {self.total_blocks}")
        print(f"Allocated: {allocated} ({100*allocated/self.total_blocks:.1f}%)")
        print(f"Free: {self.total_blocks - allocated}")
        print(f"\nFiles: {len(self.files)}")
        for name, info in self.files.items():
            print(f"  {name}: start={info.get('start', 'N/A')}, type={info['type']}")

if __name__ == "__main__":
    fs = FileSystemSimulator(100)

    # Test contiguous allocation
    fs.allocate_contiguous("video.mp4", 50)
    fs.allocate_contiguous("document.txt", 5)

    # Test linked allocation
    fs.allocate_linked("database.db", 20)

    fs.print_status()

Checking File Fragmentation with ext4

#!/bin/bash
# check_fragmentation.sh - Check file fragmentation on ext4

FILE=$1
if [ -z "$FILE" ]; then
    echo "Usage: $0 <filename>"
    exit 1
fi

DEVICE=$(df "$FILE" | tail -1 | awk '{print $1}')
MOUNT=$(mount | grep "$DEVICE" | awk '{print $3}')

# Use debugfs to check extent info
echo "=== Extent Information for $FILE ==="
debugfs -R "stat $FILE" "$DEVICE" 2>/dev/null | grep -E "Extent|Block|Size"

echo ""
echo "=== Fragmentation Analysis ==="
filefrag "$FILE"

echo ""
echo "=== Disk Layout ==="
ext2ls -l "$DEVICE" "$FILE" 2>/dev/null || echo "ext2ls not available"

Observability Checklist

Monitoring file allocation health:

• df -h: Check available space
• df -i: Check inode usage
• filefrag -v file: Check file fragmentation level
• e4defrag -c /mount/point: Check overall fragmentation percentage

# Comprehensive allocation monitoring script
#!/bin/bash
echo "=== Storage Allocation Report ==="
echo ""

echo "--- Space Usage ---"
df -h | grep -v tmpfs

echo ""
echo "--- Inode Usage ---"
df -i | grep -v tmpfs

echo ""
echo "--- Largest Files in /var (if exists) ---"
if [ -d /var ]; then
    du -sh /var/* 2>/dev/null | sort -rh | head -10
fi

echo ""
echo "--- Fragmentation Levels (ext4) ---"
for mount in $(mount | grep ext4 | awk '{print $3}'); do
    echo "Checking $mount..."
    sudo e4defrag -c "$mount" 2>/dev/null | grep -E "Fragmentation|total"
done

Common Pitfalls / Anti-Patterns

Secure File Deletion

When you rm a file, the file system just marks the file’s blocks as free in the allocation bitmap. The actual data stays on disk until those blocks get overwritten by something else. That gap between “deleted” and “really gone” is a genuine security risk — anyone with disk access or the right recovery tools can pull the data back.

Modern file systems make this worse in subtle ways. ext4’s delayed allocation means your file’s data might still be sitting in the page cache when you delete it, not written to disk yet. NTFS can retain MFT attribute records for deleted files. Even after blocks are truly freed, lab equipment can sometimes recover residual magnetic traces.

Three approaches actually work here:

1. Overwrite before delete: shred writes random data over file contents several times before unlinking. The -u flag removes the file after overwriting. This works on magnetic disks but SSDs are a different story — the wear-leveling controller maps logical blocks to physical cells however it wants, so the cell you think you’re overwriting might not be the one holding your data.

2. Full-disk secure deletion: sfill from the secure-delete package writes patterns across all free space on a mount point. Run it periodically on systems handling sensitive data.

3. Encryption at rest: This is the most reliable approach for SSDs. If the whole volume is encrypted with dm-crypt/LUKS, throwing away the key makes all the data unreadable instantly. No overwriting needed, and it works uniformly regardless of wear leveling. This is why compliance frameworks increasingly list encryption as the primary data-at-rest control instead of post-deletion overwriting.

# Overwrite file contents before deletion
shred -vu /path/to/file

# Or secure-delete entire directory
sfill -f /mount/point

# For ext4, encryption (dm-crypt) is more effective than overwriting on SSDs
# Create an encrypted container:
dd if=/dev/urandom of=/secure.img bs=1M count=1000
losetup /dev/loop0 /secure.img
cryptsetup luksFormat /dev/loop0
cryptsetup open /dev/loop0 secure_vol
mkfs.ext4 /dev/mapper/secure_vol

File System Integrity

File systems do more than just track which blocks belong to which files. They maintain several interlocking mechanisms to keep the structure consistent, and knowing what each does helps you diagnose when things go wrong.

Journaling (ext3/ext4, NTFS, XFS) writes metadata changes to a dedicated log area before applying them to the main file system. If a crash cuts off a write mid-operation, the journal can replay the incomplete transaction or roll it back. Without a journal, a crash leaves the allocation bitmap potentially corrupted — blocks marked free that are actually in use, or the reverse. ext2 has no journal. A crash means the next boot runs fsck across the entire partition, which on multi-terabyte drives can take an hour or more.

fsck consistency checks look for contradictions: inodes pointing to blocks marked free in the bitmap, directory entries referencing inodes that don’t exist, circular directory links. Running with -n does a read-only check — reported problems aren’t fixed. Run this on an unmounted filesystem to avoid the check itself changing state.

tune2fs intervals set when automatic checks fire. The filesystem increments a mount counter on each mount and a time counter daily. When either hits its limit, the next reboot triggers e2fsck. For servers that barely reboot, the mount-count threshold is more useful than time-based checks.

Block group invariants in ext2/3/4 are lower-level rules: bitmaps within each block group must be internally consistent, the inode table can’t overlap with data blocks, directory entries must point to valid inodes. Violations here usually point to hardware problems — bad RAM or a failing disk — rather than software bugs.

# Check ext4 metadata consistency
sudo e2fsck -n /dev/sda1  # -n = read-only, no changes

# Enable periodic file system checks
sudo tune2fs -l /dev/sda1 | grep -E "Check|state"
# Mount count: 50
# Check interval: 0 days

# Set automatic check interval (in days or mount count)
sudo tune2fs -c 30 /dev/sda1  # Check every 30 mounts
sudo tune2fs -i 90d /dev/sda1  # Check every 90 days

Compliance: Data Localization

Regulations like GDPR, HIPAA, and SOX require proof of where data lives, not just that it exists somewhere in a volume. Allocation metadata becomes your paper trail.

What triggers allocation tracking requirements:

Data sovereignty rules (GDPR Article 44-49) demand proof that files don’t cross jurisdictional boundaries. When a single file spans multiple physical disks across regions, auditors want to see exactly which blocks sit where.

Financial audits under SOX and PCI-DSS need documented proof that specific records were written to known locations and stayed there. Scattered allocation defeats this documentation.

Healthcare regulations under HIPAA require demonstrable retention controls. If defragmentation silently moves a patient record, can you prove it wasn’t altered?

Why allocation methods affect compliance:

Contiguous allocation makes residency proof straightforward. A file’s blocks occupy a known range, and the volume geometry determines the physical location. Linked and indexed allocation scatter blocks, complicating verification.

For regulated workloads, LVM snapshots at key timestamps create verifiable allocation snapshots. ext4’s dir_index tracks which files existed and where. Stricter requirements may need application-level logging that records file-to-block mappings independently of the file system.

# Create timestamped allocation snapshot for audit trail
sudo lvm snapshot /dev/vg0/data_vol -s audit_snap_$(date +%Y%m%d%H%M)
sudo debugfs -R "ls -l /audit_snap_20260519/data" /dev/vg0/audit_snap

# Track allocation patterns with audit tool
auditctl -w /data -p rw -k allocation_tracking
ausearch -k allocation_tracking

Filling Disks Above 80%

When disk usage climbs above 80%, three separate problems appear — and they make each other worse.

Fragmentation gets worse. With little free space scattered across the drive, the allocator picks from what’s available rather than what makes sense. A file that should take 100 contiguous blocks gets split across dozens of scattered regions instead. Sequential reads that should need one seek now need dozens. On ext4, files stop fitting in single extents and extent tree depth grows.

Allocation fails before the disk is actually full. The file system needs free blocks to carry out write operations themselves — not just to hold data. Creating a file means allocating directory entry blocks and inode entries. Extending a file means updating indirect pointers and extent trees. If a directory has thousands of entries, each new file needs a free inode somewhere. At 95% capacity, you may not be able to copy a 100MB file even though hundreds of megabytes of “free” space appear to exist — because the allocator can’t find the metadata blocks it needs for the operation itself.

ext4’s delayed allocation makes this sneakier. delalloc batches up write allocations and delays assigning physical blocks until writeback. When many delayed allocations pile up and the writeback thread finally runs against a nearly-full disk, it may not find contiguous runs for sequential writes. Processes block waiting for the allocator. The system looks idle but everything touching disk is stalled.

The actual threshold depends on the file system. ext4’s block group allocator performs best below 80%; beyond that, cross-group allocations increase. XFS with its allocation groups handles high utilization better but still degrades. Most admins treat 80% as a soft warning and 90-95% as an emergency cutoff.

# BAD: Let disk fill above 85%
# Causes: fragmentation, allocation failures, performance degradation

# GOOD: Monitor and alert
df -h | awk '{if ($5+0 > 80) print "WARNING: "$0}'

# Set up in /etc/rc.local or cron
# Also use iostat to check for allocation stalls:
iostat -x 1 | awk '$6 ~ /[0-9]+\.[0-9]/ && $6 > 50 {print "High await: "$0}'

Using Wrong Block Size

# Creating file system with wrong block size
# Small block (4KB): Good for many small files, wastes space on large files
# Large block (8KB): Good for large files, wastes inodes for small files

# Choose based on workload:
# Database: larger blocks
# Mail server: smaller blocks (many small files)

# Check current block size
tune2fs -l /dev/sda1 | grep "Block size"

# Recreate with different block size (requires backup)
sudo mkfs.ext4 -b 8192 /dev/sda1

Ignoring Extent Usage in ext4

ext4 replaced the old direct/indirect block pointer system from ext2/3 with extent-based allocation. Most files on ext4 use extents by default since kernel 2.6.23, but certain situations still produce non-extent files — and it matters more than you’d think.

Why extents are faster. A traditional Unix inode has 12 direct block pointers plus three levels of indirect pointers. A 10MB file with 4KB blocks needs roughly 2,560 block pointers distributed across the inode and several indirect blocks. Every read has to follow pointer chains through multiple metadata blocks before reaching the actual data. An extent entry stores a contiguous range as one pair: {start_block, length}. That same 10MB file fits in about 20 extent entries. Less metadata per file means fewer disk reads to pull up the same data.

When files fall back to block pointers. Retroactively converting a file requires rewriting its inode — e4defrag does this during defragmentation. Very old files migrated from ext2/3 may still use block pointers. Files patched heavily with dd or accessed with O_DIRECT can bypass extent allocation. Historically, the chattr +c flag (the compressed attribute, which ext4 doesn’t actually implement) caused the filesystem to fall back to block mapping.

How to check and fix. debugfs shows whether a file uses extents and how many entries its extent tree has. Files with Extent End depth greater than zero still use extents but have external extent tree nodes — this happens with very large files where the inode’s built-in extent entries overflow. chattr +e forces extent allocation for future writes but won’t convert an existing file retroactively. Run e4defrag to rewrite a file’s allocation in optimal extent format.

The performance difference shows up most on large files accessed sequentially. A 100GB database file using block pointers might need thousands of indirect block reads before reaching an offset. The same file in extent format resolves the same offset with a fraction of the metadata operations.

# Check if files are using extents
debugfs -R "ex list <path>" /dev/sda1

# Force extent usage (disable block mapping) for new allocations
chattr +e /path/to/file

# Check for non-extent files or files with deep extent trees
debugfs -R "stat <path>" /dev/sda1 | grep -i extent

# Defragment to convert to optimal extent layout
e4defrag /path/to/file

Quick Recap Checklist

• Contiguous allocation: Fast but causes fragmentation
• Linked allocation: Flexible but slow random access
• Indexed allocation: Good random access, overhead per file
• FAT: Linked list in a table; fragmentation kills performance
• ext2/3/4: Bitmap allocation with extent-based files
• NTFS: MFT with runlists for flexible allocation
• Monitor inode usage (not just space usage)
• Keep disk usage below 80% to prevent fragmentation

Interview Questions

# View current reservation
tune2fs -l /dev/sda1 | grep Reserved
Change reservation to 1%
tune2fs -m 1 /dev/sda1
Disable entirely (not recommended for root)
tune2fs -m 0 /dev/sda1

Further Reading

• ext4 Documentation — Extent Structure: Official Linux kernel documentation covering extent tree implementation and extent header structures.
• NTFS Documentation — Microsoft Docs: Microsoft documentation on NTFS file record structure, MFT attributes, and update sequence numbers.
• FAT File System Specification — Microsoft: Official FAT specification including FAT12, FAT16, FAT32 cluster chain formats and media descriptor bytes.
• PostgreSQL — Raw Devices and O_DIRECT: PostgreSQL documentation on bypassing the OS file system for raw I/O and fsync behavior control.
• e4defrag man page — Linux: Manual for ext4 online defragmentation tool, including fragmentation detection and extent reorganization.
• Tune2fs man page — Linux: Documentation for ext2/3/4 filesystem tuning, including inode reservation and automatic check intervals.
• Btrfs Architecture — Kernel.org: Comparison of Btrfs copy-on-write allocation against traditional block-pointer approaches in ext4.
• XFS Allocation Groups — Oracle: Technical comparison of XFS allocation groups versus ext4 block groups and their implications for parallel allocation.
• File System Abstraction: /blog/technical/file-system-abstraction/ — foundational concepts of how file systems present a unified interface to applications
• Directory Implementation: /blog/technical/directory-implementation/ — how directory entries organize file metadata and name-to-inode mappings

Conclusion

File allocation methods determine how disk space gets assigned to files, with direct consequences for performance and fragmentation. Contiguous allocation delivers excellent sequential throughput but suffers from external fragmentation that eventually requires compaction. Linked allocation eliminates fragmentation but destroys random access performance. Indexed allocation balances both, though with per-file overhead.

Modern file systems combine these approaches: FAT uses a central table for linked-style allocation, ext4 uses extent-based allocation that stores contiguous ranges efficiently, and NTFS uses the MFT with runlists for maximum flexibility. The key insight is that no single approach wins universally — the right choice depends on your workload characteristics.

For continued learning, study how databases implement their own file allocation strategies to bypass OS buffering, why ext4’s delayed allocation reduces fragmentation compared to ext3, and how the trade-offs between allocation methods manifest in real-world performance benchmarks. Understanding these fundamentals helps you diagnose storage performance issues and choose file systems appropriate for your use case.