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

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

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.

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.

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

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

File allocation metadata remains after deletion. The actual data isn’t overwritten until blocks are reallocated. For secure deletion:

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

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

# For ext4, consider encryption (dm-crypt)
# Encrypted FS ensures data is unreadable without key

File System Integrity

Modern file systems include allocation integrity features:

# 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

Some regulations require knowing where data is physically allocated:

• Track file allocation patterns for audit
• Use file system features like ext4 dir_index for compliance tracking
• Consider LVM for volume-level control

Common Pitfalls / Anti-patterns

1. Filling Disks Above 80%

# 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

2. 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

3. Ignoring Extent Usage in ext4

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

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

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

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

Topic-Specific Deep Dives:

• ext4 Extent Tree Structure: Study how ext4 actually stores extent information in the inode. The extent header and extent node structures enable the fast directory operations that make ext4 performant.

• Delayed Allocation: ext4 uses delalloc — writes are held in the page cache and allocated later. This batches allocations and reduces fragmentation. Understanding when this can cause data loss (power failure before allocation) is important.

• Database File Management: Databases often avoid OS file systems entirely, using raw partitions or raw I/O. Understanding why (bypassing page cache, controlling fsync behavior, avoiding double buffering) explains PostgreSQL and Oracle storage configuration.

• FAT Fragmentation Physics: On FAT file systems, fragmentation isn’t just about free space scatter—it’s about how the FAT chain grows and how the firmware’s cache interacts with random writes. Understanding the physics explains why FAT USB drives degrade in ways Linux file systems don’t.

• NTFS MFT Structure: The Master File Table is itself a file. Studying how NTFS stores attribute records (resident vs non-resident), how it handles fragmentation of the MFT itself, and how the $Bitmap works explains Windows storage behavior.

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.