File Systems, Disks and Storage

Files, directories and links

A file is a named sequence of bytes with metadata: size, owner, permissions, timestamps, and the location of its data blocks. In Unix file systems, metadata lives in an inode (index node); the directory is just a special file that maps names → inode numbers.

• A hard link is a second name for the same inode (ln a b); the inode has a link count, and the data is deleted only when the count reaches 0 and no process has the file open.
• A symbolic (soft) link is a small file containing a path (ln -s); it can cross file systems and point to directories, but breaks if the target is moved.

When a process opens a file, the kernel creates an entry in the open-file table (current offset, access mode) and returns a file descriptor (a small integer: 0 = stdin, 1 = stdout, 2 = stderr). Mounting attaches a file system to a directory of the global tree.

Allocation methods

The Unix inode combines direct and indirect pointers: e.g., 12 direct pointers, one single indirect (a block full of pointers), one double indirect, one triple indirect.

With 4 KiB blocks and 4-byte pointers, one block holds 1,024 pointers:

• Direct: 12 blocks = 48 KiB.
• Single indirect: 1,024 blocks = 4 MiB.
• Double indirect: 1,024² blocks = 4 GiB.
• Triple indirect: 1,024³ blocks = 4 TiB → maximum file size ≈ 4 TiB.

Reading the byte at offset 49,152 (block 12) requires reading the single indirect block, then the data block: 2 disk reads (the inode is assumed cached). Small files — the vast majority — use only direct pointers and are fast. Modern file systems (ext4, XFS) use extents (start, length) instead of individual block pointers, which is much more compact for large files.

Free-space management. A bitmap has one bit per block. A 1 TiB disk with 4 KiB blocks has 2²⁸ blocks → 2²⁸ bits = 32 MiB of bitmap — small enough to cache, and finding contiguous free runs is easy.

Caching, write-back and durability

The OS keeps recently used file blocks in the page cache (Chapter 10). Writes are usually write-back: write() copies data into the cache, marks it dirty and returns immediately; the kernel flushes dirty pages to disk later (typically within ~30 s on Linux). Write-through writes to disk immediately — safe but slow.

In the lab example, 5 writes with a 3-block cache cost 5 disk writes with write-through but only 2 with write-back; however, if the machine crashes before the flush, the latest updates to blocks 4 and 5 are lost.

Applications that need durability (databases, message queues, payment systems) call fsync(fd), which returns only when the file's data has reached stable storage. fsync is slow (milliseconds on HDD, tens to hundreds of microseconds on SSD), so databases group many transactions into one fsync (group commit).

Crash consistency

Creating a file updates several blocks: the inode, the bitmap, the directory. A crash in the middle can leave the file system inconsistent (a block marked used but belonging to no file, or a directory entry pointing to an uninitialized inode). Solutions:

• fsck — scan the whole disk after a crash and repair; takes hours on large disks.
• Journaling (ext4, NTFS, XFS): first write the intended changes to a log (journal), then a commit record, then apply them to their real locations. After a crash, replay committed transactions and ignore incomplete ones. ext4's default ordered mode journals metadata only, writing data blocks before the metadata commits.
• Copy-on-write file systems (ZFS, Btrfs, APFS): never overwrite live blocks; write new versions elsewhere and atomically switch a root pointer. Snapshots become almost free.
• Log-structured designs write everything sequentially — the idea behind SSD firmware and many databases (LSM trees in RocksDB, Cassandra).

Hard disks: why the order of requests matters

HDD access time = seek (move the arm) + rotational latency (wait for the sector) + transfer.

Example: 7,200 RPM → one rotation = 60/7200 s = 8.33 ms → average rotational latency 4.17 ms; average seek 9 ms; transfer of 4 KiB at 200 MB/s ≈ 0.02 ms → ≈ 13.2 ms per random I/O ≈ 76 IOPS. Sequential transfer, by contrast, reaches 200 MB/s. Random I/O on an HDD is ~1,000× slower than sequential — so the OS schedules requests to reduce seeks.

Disk scheduling (requests for cylinders 98, 183, 37, 122, 14, 124, 65, 67; head at 53; cylinders 0–199):

C-SCAN/C-LOOK move more but give more uniform waiting times (no request waits for two sweeps). Linux's schedulers today are mq-deadline (deadlines to avoid starvation), bfq (fairness for desktops) and none — for fast SSDs and NVMe, where there is no seek and scheduling just adds overhead.

SSDs and NVMe

Flash SSDs have no moving parts: random reads take ~50–100 µs, and NVMe drives reach hundreds of thousands to millions of IOPS using many parallel queues (one per CPU core). But flash has quirks:

• Data is written in pages (e.g., 16 KiB) but erased only in large erase blocks (e.g., several MiB); pages cannot be overwritten in place.
• The flash translation layer (FTL) maps logical blocks to physical pages, writes updates to fresh pages (log-structured), and garbage-collects blocks — copying valid pages elsewhere before erasing.
• Write amplification: the device writes more than the host asked (e.g., 2–3×), which reduces performance and lifetime.
• Cells wear out after a limited number of erase cycles → wear leveling spreads writes. TRIM tells the SSD which blocks are free, reducing garbage-collection work.

RAID: many disks as one

With 6 disks of 4 TB (200 IOPS each) and 70 % reads: RAID 5 gives 20 TB and about 1,200 / (0.7 + 0.3 × 4) ≈ 632 IOPS; RAID 10 gives 12 TB and ≈ 923 IOPS. Databases often prefer RAID 10 (write-heavy), archives RAID 6 (capacity + safety). RAID is not a backup: a deleted file or ransomware is deleted/encrypted on all disks.

Distributed and cloud storage

• Object storage (Amazon S3, MinIO): flat namespace of objects accessed over HTTP (PUT/GET), with metadata; massively scalable, no in-place updates.
• Replication: HDFS and many systems keep 3 copies on different machines/racks → 200 % overhead, tolerates 2 failures, fast reads anywhere.
• Erasure coding, e.g., Reed–Solomon RS(6, 3): split data into 6 fragments plus 3 parity fragments — any 6 of the 9 rebuild the data → only 50 % overhead, tolerates 3 failures, but recovery needs reading 6 fragments over the network.
• Consistency trade-offs: replicas may briefly disagree; systems choose between strong and eventual consistency.

At the edge, storage is small and nodes are less reliable; data placement must balance latency (keep hot data near users), bandwidth (don't ship raw video to the cloud — process it locally and send results), durability (replicate important data to the cloud) and privacy (keep personal data on campus).

Key takeaways

• Directory = name → inode; hard links share an inode (link count), symbolic links store a path.
• Allocation: contiguous (fast, fragments), linked/FAT (sequential only), indexed/inode (direct + indirect; 4 KiB blocks and 4-byte pointers → ≈ 4 TiB max). Extents in modern FS.
• Bitmap: one bit per block (1 TiB / 4 KiB → 32 MiB).
• Page cache + write-back = fast but risky; fsync for durability. Journaling or copy-on-write for crash consistency.
• HDD: seek + rotation + transfer (~13 ms, ~76 IOPS); schedule requests (SSTF, SCAN/LOOK, C-SCAN/C-LOOK). SSD/NVMe: no seek, FTL, write amplification, TRIM, scheduler none.
• RAID 0/1/5/6/10: capacity vs. fault tolerance vs. write penalty; RAID ≠ backup.
• Cloud: object storage, 3× replication vs. erasure coding; edge: place data by latency, bandwidth, durability and privacy.