The stories of three file systems

The Portable Music Problem

In 1997, people began to carry bulky CD player to the beach (+ multiple CDs in a case). Sony’s “CD Walkman” was a cool new toy. Listening to music was no longer an indoor activity.

Flash memory in 2001 was expensive and tiny. The first USB flash drives (invented in Israel) offered only 8MB of storage. Portable music players based on flash memory could store about a dozen songs at most. Flash memory had a big advantage though: it was solid-state, meaning no moving parts. You could drop a flash-based player and it would keep working.

Hard drives offered far more capacity but came with serious drawbacks. A mechanical hard drive contains spinning magnetic platters and a read/write head that moves across them. If you dropped a hard drive or shook it while it was spinning, the head could crash into the platter and destroy data. No company was able to produce a truly portable music player with a hard drive that could survive being carried in a pocket.

FAT32

Apple was forced to adopt FAT32 (File Allocation Table 32-bit), a file system that dates back to 1996 as an extension of the much older FAT system from MS-DOS. Let’s contrast FAT32 with ext2, which we studied in lecture.

In ext2, each file has an inode that contains metadata (permissions, timestamps, size) and pointers to data blocks. The inodes are stored in a dedicated inode table, and you locate a file by first finding its inode number from a directory entry, then reading that inode to get the block locations.

FAT32 works differently. Instead of a separate inode table, FAT32 stores all its block allocation information in a single large table at the beginning of the disk called the File Allocation Table (FAT). Here is how it works:

1. The disk is divided into clusters (similar to blocks in ext2). A cluster is typically 4KB or larger.
2. The FAT is an array where each entry corresponds to one cluster on the disk. If your disk has 1 million clusters, the FAT has 1 million entries.
3. Each FAT entry contains a number that points to the next cluster in the file. This forms a linked list.

For example, suppose you have a file called song.mp3 that occupies three clusters: 100, 215, and 316. The directory entry for song.mp3 stores the starting cluster number (100) along with the filename and file size. When you read the file:

• Look at FAT entry 100, which contains the value 215 (the next cluster is 215)
• Look at FAT entry 215, which contains the value 316 (the next cluster is 316)
  
• Look at FAT entry 316, which contains a special end-of-file marker (0xFFFFFFFF)

This linked-list-traversal style means reading a file requires multiple lookups in the FAT table, especially if the file is stored in non-contiguous clusters. In ext2, the inode directly stores pointers to the first 12 data blocks and we can directly read them without traversing a chain.

The biggest advantage of FAT32 is universal compatibility. Almost every OS can read and write it without special drivers. This is why FAT32 remains standard today for UEFI boot partitions in your PC and SD cards in cameras.

However, FAT32 has many limitations:

• 4GB file size limit: Because FAT32 uses 32 bits to store file size in the directory entry, no single file can exceed 2^32 bytes = 4GB. This makes FAT32 unusable for recording 4K video today, but it worked fine for MP3 files that typically ranged from 3MB to 10MB.
• Slower file lookups: Finding all the blocks of a file requires multiple disk seeks. On a mechanical drive with slow seek times, this is noticeably slower than the direct/indirect block pointer approach in ext2 or the B-tree indexing in HFS+.
• No journaling: If power fails during a write operation, the file system can become corrupted with no easy recovery mechanism (but this is probably fine for iPod because its file-system is only written when user download the songs, which is infrequent compared to reading mp3 files during daily use).

Why Bother with HFS+?

Apple formatted every iPod as FAT32 at the factory. But this is not the end of the story. When a user connected an iPod to a Mac for the first time, iTunes would silently reformat it to HFS+. Windows users never saw this happen. Their iPods stayed as FAT32 forever. But hey, if FAT32 is fine for iPod, why did Apple reformat iPods to HFS+ when connected to Macs? The answer is probably to save battery life.

The iPod had a slow ARM processor and only 32MB of RAM. Spinning the mechanical hard drive was power-hungry and made the iPod vulnerable to shock damage. Every second the drive spent spinning was a second it could be dropped and have data corrupted.

To maximize battery life and minimize mechanical risk, the iPod used an “suck-up” buffering strategy: spin up the disk once, load about 30MB of upcoming songs into RAM as quickly as possible, then immediately stop the disk. The remaining 2MB of RAM was for the OS. The drive would only spin again when the buffer was nearly empty, which for most users meant 20 to 30 minutes of silent operation between spin-ups.

HFS+’s efficiency reduced the disk’s vulnerable timespan. On the other hand, on FAT32, if your song file is spread across 10 non-contiguous clusters, the system must read 10 different FAT entries and seek to 10 different disk locations. On a slow processor with a mechanical drive, this sucks up more battery life.

HFS+ uses B-trees to index files. A B-tree is a self-balancing tree structure where each node can have many children. This keeps the tree shallow. Instead of traversing a linked list, HFS+ can find any file’s blocks in logarithmic time. This typically means just 2 to 3 disk reads even for large directories. The iPod could load songs into memory faster and the drive could spin down sooner.

Apple released the iPod Nano in 2005 with flash memory instead of a mechanical drive. Flash memory has no moving parts. Your data remains ok even if you shake it. Nowadays, your phone could easily have 256GB flash memory at the size of a 1 NTD coin. But do you even store “1,000 songs in your pocket”??