Skip to main content

FAT vs ext2/3/4 vs Log-Structured File Systems

What This Concept Is​

Three archetypes cover most of what you will ever meet:

FAT (File Allocation Table)​

One big table at a fixed location. Each entry corresponds to one data block on disk and holds either FREE, EOF, or the block number of the next block in the file.

  Block: 0   1   2   3   4   5   6
 FAT  : ... 3  EOF  5  FR  7  EOF
         ^       ^           ^
         |       file2:       |
         file1: 0 -> 3 -> 5 -> 7

To read a file, you follow a linked list through the FAT. No inodes; file metadata (name, size, start block) lives in the directory entry itself.

ext-family (ext2/3/4)​

The canonical Unix layout from Cluster 2 concept 05: superblock, bitmaps, inode table, data blocks, block groups. Inodes point at data blocks directly or via (indirect, double, triple) pointer blocks in ext2/3, or via extents in ext4. Updates are in place: to change block 42, you overwrite block 42.

Log-Structured File Systems (LFS, F2FS, in spirit)​

Everything is a log. New writes (data, inodes, directory entries) append to a sequential log at the end of the device. Old copies of the same block remain until garbage collection reclaims them. An inode map (imap) gives the current location of each inode, so readers can find the latest version.

 disk -> |  dataA  dataB  inodeA  inodeB  imap |  dataA'  inodeA'  imap' | ....
          ^old versions remain           ^ overwrite of file A writes a NEW log entry

Why It Matters Here​

These are not curiosities. Each shapes what you can build on top:

  • FAT is simple enough to fit in firmware: used on SD cards, EFI boot partitions, many small embedded systems. But it has no metadata isolation (a bad write can corrupt a name), no fine-grained permissions, and large files mean long chains of pointer lookups.
  • ext-family is the default on most Linux installs. It handles large files, permissions, hard links, journaling (ext3/4). Its weakness is random-write heavy workloads because updates are in place and metadata updates require scattered writes.
  • LFS-style systems buffer writes into a segment and flush sequentially. Excellent for HDDs (no seeks during writes) and for flash (large contiguous writes align with erase blocks). Cost: requires garbage collection, which competes with foreground writes for bandwidth.

These three are also the three design points you will encounter in database storage: update-in-place (B-tree), log-structured (LSM), and hybrid.

Concrete Example​

Appending 4 KiB to a 12 KiB file that already uses blocks 100, 101, 102:

FAT: allocate a free block, say 200. Set FAT[102] from EOF to 200. Set FAT[200] = EOF. Write data to block 200. Update directory entry with new size.

ext4: allocate a free block via data bitmap (scan for zero, flip). Update inode: increment size, add block 200 to the extent list or block pointers. Write data to block 200. Write back inode.

LFS: append to the current segment:

  • write the new 4 KiB data block at head of log
  • write a new copy of the inode (updated size, updated block pointers) at head of log
  • update the in-memory inode map (later persisted as an imap block)

LFS does three contiguous sequential writes. ext4 does one data write (likely seek), one bitmap update, one inode write (seek). FAT is similar to ext4 but chains through the FAT table.

Common Confusion / Misconception​

"ext4 is log-structured because of the journal." No. ext4's journal logs intent for a short window; the actual data still goes to its in-place home after the journal commit. True LFS has no in-place home; the log is the storage.

"LFS is always faster." Not on read-heavy mixed workloads, because related data becomes scattered as the log grows, and GC steals bandwidth. LFS wins when writes dominate and data fits the segment scheme.

"FAT cannot do large files." It can, but each block access requires walking the FAT chain. The real limit is that FAT12/16/32 cap file sizes and disk sizes at 4 GiB and 2 TiB respectively.

How To Use It​

Given a workload, ask which archetype fits:

  1. Many small random updates to long-lived files: ext-style, possibly with an SSD-friendly journal.
  2. Append-mostly, many sequential readers (logging, time series): LFS or LSM-style.
  3. Tiny devices with no memory for complex allocators: FAT.

This framing also predicts which concept you should reach for in Cluster 3. ext-family needs journaling; LFS is almost a journal by construction; FAT is usually fixed by fsck on boot.

Check Yourself​

  1. Why does FAT become slow for files larger than a few megabytes?
  2. Why do flash-based file systems like F2FS borrow from LFS ideas?
  3. Under what workload does LFS waste the most space, and why?

Mini Drill or Application​

For each scenario, pick the best archetype and justify:

  1. Write-once-read-many analytics on NVMe.
  2. Boot loader reading a kernel image from a small partition.
  3. A busy mail server with millions of small mbox appends.
  4. A heavily edited source tree on a workstation SSD.

Read This Only If Stuck​