Why did FAT suffer from fragmentation and scalability limits?

The File Allocation Table file system, commonly known as FAT, was designed for early personal computers with small floppy disks and simple storage needs. Because it relied on a centralized linked-list table and fixed cluster addressing, it struggled as disk capacities grew and workloads became more complex. Its design lacked modern allocation strategies, which led to severe file fragmentation, wasted disk space, and hard limits on volume and file sizes.

Centralized Linked-List Allocation and Fragmentation

At the core of FAT is a single table that maps every cluster on a storage volume. Each entry in the table points to the next cluster belonging to a file, forming a singly linked list. When a file is created or extended, the operating system scans the table for the first available free cluster and links it to the chain.

This first-fit allocation strategy works well on an empty disk, but it breaks down quickly as files are created, modified, and deleted. Free space becomes scattered into small, non-contiguous gaps across the volume. Because FAT does not reserve contiguous space in advance or use extent-based allocation, new data is written into whatever gaps are available. Over time, a single file can be split into hundreds or thousands of fragments. On mechanical hard drives, reading a fragmented file requires frequent, slow head seeks, which degrades system performance.

Cluster Size and Internal Fragmentation

To address growing disk capacities without redesigning the table structure, early versions of FAT increased the size of each cluster. A cluster is the smallest unit of disk space that the file system can allocate to a file. Even if a file is only a few bytes long, it consumes an entire cluster.

When a volume grows larger while the number of addressable clusters remains fixed, each cluster must cover more sectors. For example, on a 2 GB FAT16 partition, a single cluster can be 32 KB. If a directory contains thousands of small configuration or text files, each file wastes most of its allocated cluster. This wasted space inside allocated clusters is known as internal fragmentation, and it can consume a significant percentage of a drive's total capacity.

Addressing Limits and Volume Scalability

The scalability of FAT is strictly bounded by the bit width of its table entries, which determines the maximum number of clusters a volume can address. In FAT12, FAT16, and FAT32, the number of bits per entry limits the total addressable clusters to \(2^{12}\), \(2^{16}\), and \(2^{28}\) respectively, minus a few reserved values.

The maximum volume size \(V_{\max}\) is given by the product of the maximum number of clusters \(C_{\max}\) and the cluster size \(S\):

\[V_{\max} = C_{\max} \times S\]

Because \(C_{\max}\) is fixed for a given FAT variant, increasing the volume size requires increasing \(S\), which worsens internal fragmentation. Furthermore, FAT32 stores file sizes in a 32-bit unsigned integer field within each directory entry. This imposes a hard limit on the maximum size of any single file:

\[F_{\max} = 2^{32} - 1 \text{ bytes} \approx 4 \text{ GB}\]

This 4 GB ceiling made FAT32 unsuitable for large database files, virtual machine images, and high-definition video.

Directory Structure and Lookup Overhead

FAT also scales poorly with large numbers of files in a single directory. Directories in FAT are stored as simple linear arrays of 32-byte entries. There is no B-tree, hash table, or indexing mechanism to speed up searches.

To find a file or check if a filename already exists, the operating system must scan the directory entries sequentially from start to finish. As a directory grows to thousands of files, file creation and lookup times increase linearly, causing noticeable delays. Combined with the lack of journaling, permissions, and crash recovery features, these limitations eventually pushed operating systems toward more modern file systems like NTFS and ext4.