06-file-systems-and-storage.md

💾 Module 06: File Systems & Storage Management

Focus: File Concepts & Inodes, Hard vs Soft Links, File Allocation Methods (Contiguous, FAT, Indexed), Virtual File System (VFS), Journaling & Crash Recovery, Disk Scheduling (SCAN, C-SCAN, LOOK), and RAID Levels.

📑 Table of Contents

  1. File Concepts, Attributes & Operations
  2. The Inode Structure & Multi-Level Indexing Math
  3. Hard Links vs Soft (Symbolic) Links
  4. Directory Implementations & Path Resolution
  5. File Allocation Methods (Contiguous, FAT, Indexed)
  6. Free Space Management Techniques
  7. The Virtual File System (VFS) Abstraction
  8. File System Consistency & Journaling (ext3/ext4)
  9. Disk Geometry & I/O Performance Metrics
  10. Disk Scheduling Algorithms (SSTF, SCAN, C-SCAN, LOOK)
  11. RAID Architectures (RAID 0, 1, 5, 6, 10) & Parity Math
  12. Common Mistakes & Gotchas
  13. Step-by-Step Numerical Practice Problems
  14. High-Yield Interview Questions & Answers

1. File Concepts, Attributes & Operations

A File is an abstract, named collection of contiguous bytes persisted on secondary storage.

┌────────────────────────────────────────────────────────┐ │ FILE ATTRIBUTES │ ├────────────────────────────────────────────────────────┤ │ • Identifier (Inode Number) : Unique integer on device │ │ • Name : Human-readable string │ │ • Type : Regular, Directory, FIFO │ │ • Size : Current file size bytes │ │ • Protection (Permissions) : Read / Write / Execute │ │ • Timestamps : atime, mtime, ctime │ │ • Location Pointer : Block addresses on disk │ └────────────────────────────────────────────────────────┘

2. The Inode Structure & Multi-Level Indexing Math

In Unix/Linux file systems (ext2/3/4), an Inode (Index Node) is a data structure storing all metadata about a file except its filename.

UNIX INODE STRUCTURE ┌─────────────────────────────────────────────────────────────────┐ │ Metadata (File Size, Owner UID, Permissions, Timestamps, Links) │ ├─────────────────────────────────────────────────────────────────┤ │ Direct Block Pointer 0 ──────► [ Data Block 0 ] │ │ Direct Block Pointer 1 ──────► [ Data Block 1 ] │ │ ... (Direct Pointers 0 to 11) │ ├─────────────────────────────────────────────────────────────────┤ │ Single Indirect Pointer ──────► [ Table of Block Pointers ] │ │ ├──► [ Data Block ] │ │ └──► [ Data Block ] │ ├─────────────────────────────────────────────────────────────────┤ │ Double Indirect Pointer ──────► [ Table of Single Indirects ] │ ├─────────────────────────────────────────────────────────────────┤ │ Triple Indirect Pointer ──────► [ Table of Double Indirects ] │ └─────────────────────────────────────────────────────────────────┘

Maximum File Size Calculation Example:

Assume:

  • Disk Block Size $= 4\text{ KB} = 4096\text{ bytes}$.
  • Disk Pointer Size $= 4\text{ bytes} \implies$ Each indirect block holds $\frac{4096}{4} = \mathbf{1024\text{ pointers}}$.
  • Inode has 12 Direct Pointers, 1 Single Indirect, 1 Double Indirect, 1 Triple Indirect.
  1. Direct Blocks: $12 \times 4\text{ KB} = \mathbf{48\text{ KB}}$.
  2. Single Indirect Block: $1024 \times 4\text{ KB} = \mathbf{4\text{ MB}}$.
  3. Double Indirect Block: $1024 \times 1024 \times 4\text{ KB} = 1,048,576 \times 4\text{ KB} = \mathbf{4\text{ GB}}$.
  4. Triple Indirect Block: $1024 \times 1024 \times 1024 \times 4\text{ KB} = 1,073,741,824 \times 4\text{ KB} = \mathbf{4\text{ TB}}$.
  • Total Max File Size: $48\text{ KB} + 4\text{ MB} + 4\text{ GB} + 4\text{ TB} \approx \mathbf{4.004\text{ TB}}$.

3. Hard Links vs Soft (Symbolic) Links

HARD LINK SOFT (SYMBOLIC) LINK Directory Entry A Directory Entry B Directory Entry A Symlink Entry B [ "file1.txt" ] [ "file2.txt" ] [ "target.txt" ] [ "link.txt" ] │ │ │ │ └───► [ Inode 405 ] ◄┘ ▼ ▼ │ [ Inode 100 ] [ Inode 200 ] ▼ │ │ [ Data Blocks ] ▼ ▼ [ Data Blocks ] [ Path String ] "target.txt"

Detailed Comparison

AttributeHard Link (ln file link)Soft / Symbolic Link (ln -s file link)
InodeShares the EXACT same Inode number as original file.Has its own unique Inode; data block stores target pathname.
Inode Reference CountIncrements the inode's link counter by 1.Does not affect target file's link count.
Deleting Original FileData is NOT deleted! Inode link count decrements to 1. Hard link still reads data.Link becomes broken / dangling; points to a non-existent path.
Cross-Filesystem?No. Cannot link across different disk partitions.Yes. Can span across different drives and network mounts.
Directories?Not allowed for users (prevents recursive directory loops).Allowed for directories.

4. Directory Implementations & Path Resolution

A Directory is simply a special file containing a list of (Filename, Inode Number) pairs.

ROOT DIRECTORY (Inode 2) ┌───────────────────────────────┐ │ Inode 2 │ "." │ │ Inode 2 │ ".." │ │ Inode 14 │ "home" │ │ Inode 89 │ "etc" │ └───────────────────────────────┘ │ Lookup "home" ▼ DIRECTORY "/home" (Inode 14) ┌───────────────────────────────┐ │ Inode 14 │ "." │ │ Inode 2 │ ".." │ │ Inode 205 │ "user" │ └───────────────────────────────┘

5. File Allocation Methods (Contiguous, FAT, Indexed)

1. CONTIGUOUS ALLOCATION [ Block 10 ] [ Block 11 ] [ Block 12 ] [ Block 13 ] • Pros: Ultra-fast sequential and direct random access. • Cons: Severe external fragmentation; cannot easily grow file. 2. LINKED LIST ALLOCATION [ Block 10 | Next: 45 ] ──► [ Block 45 | Next: 19 ] ──► [ Block 19 | Next: EOF ] • Pros: Zero external fragmentation; dynamic growth. • Cons: Terrible random access ($O(N)$ sequential seek); pointer reliability loss. 3. FILE ALLOCATION TABLE (FAT - FAT32 / exFAT) • Linked list pointers moved out of data blocks into a centralized table cached in RAM. • Fast direct access lookup via in-memory table indexing. 4. INDEXED ALLOCATION (Inodes) • Each file has an Index Block containing all disk block pointers. • Excellent direct random access without external fragmentation.

6. Free Space Management Techniques

1. BITMAP / BIT VECTOR • An array of bits where 0 = Block Allocated, 1 = Block Free. • Example: 00110100 (Blocks 2, 3, 5 are free). • Fast hardware bit-scan instructions (`BSF` / `CTZ`). Requires RAM overhead. 2. LINKED FREE LIST • Free disk blocks linked together via pointers inside the free blocks themselves. • Zero RAM overhead, but slow list traversal. 3. GROUPING • First free block stores addresses of $N-1$ other free blocks + pointer to next grouping block. 4. COUNTING • Stores `(First_Block_Address, Number_of_Contiguous_Free_Blocks)`.

7. The Virtual File System (VFS) Abstraction

The Virtual File System (VFS) provides an object-oriented abstraction layer allowing user programs to use identical system calls (open, read, write) across different filesystems (ext4, NTFS, Btrfs, NFS):

┌────────────────────────────────────────────────────────┐ │ User Applications │ ├────────────────────────────────────────────────────────┤ │ Standard POSIX Syscalls (open, write) │ ├────────────────────────────────────────────────────────┤ │ VFS (Virtual File System Layer) │ │ ┌──────────────┬──────────────┬────────────────────┐ │ │ │ struct inode │ struct file │ struct super_block │ │ │ └──────┬───────┴──────┬───────┴────────┬───────────┘ │ ├─────────┼──────────────┼────────────────┼──────────────┤ │ ▼ ▼ ▼ │ │ ext4 Driver NTFS Driver NFS (Network) │ └────────────────────────────────────────────────────────┘

8. File System Consistency & Journaling (ext3/ext4)

The Crash Consistency Problem

Suppose appending to a file requires 3 disk writes:

  1. Write Data Block $D$.
  2. Update Inode pointer $I$.
  3. Update Free Bitmap $B$. If power fails between steps 1 and 2, disk metadata becomes corrupted.

Journaling (Write-Ahead Logging / WAL)

Before modifying disk structures, the OS writes a transaction intent descriptor to a dedicated circular Journal:

1. TxBegin ──► 2. Log Inode & Bitmap updates ──► 3. TxEnd (Commit) ──► 4. Checkpoint (Write to Real Disk)

Journaling Modes in ext4:

  • Journal Mode (Full Data Journaling): Both file data and metadata written to journal. Highest safety, lowest performance.
  • Ordered Mode (Default): File data written to disk first; metadata written to journal. Prevents garbage data in files upon crash.
  • Writeback Mode: Metadata journaled, data written whenever. Fastest, but crash can cause stale data exposure.

9. Disk Geometry & I/O Performance Metrics

HDD DISK GEOMETRY ┌────────┐ Spindle ─►│ │ │ ┌───┐ │ ◄── Platter Surface Track ─►│ │ │ │ └──┼───┼─┘ │ │ Read/Write│ └─── Sector (512B / 4KB) Head ───►═══

$$\text{Total Access Time} = \text{Seek Time} + \text{Rotational Latency} + \text{Transfer Time} + \text{Controller Overhead}$$

  • Seek Time: Time for mechanical arm to position read/write head over target track (dominant delay: ~3–9 ms).
  • Rotational Latency: Time for target sector to spin under head: $$\text{Average Rotational Latency} = \frac{1}{2} \times \frac{60}{\text{RPM}} \text{ seconds}$$ (For 7200 RPM: $\frac{60}{7200} = 8.33\text{ ms} \implies \text{Avg} = 4.17\text{ ms}$).

10. Disk Scheduling Algorithms (SSTF, SCAN, C-SCAN, LOOK)

Disk Request Queue: 98, 183, 37, 122, 14, 124, 65, 67 (Initial Head Position = 53, Disk Range = 0 to 199).

1. FCFS (First-Come First-Served): Path: 53 -> 98 -> 183 -> 37 -> 122 -> 14 -> 124 -> 65 -> 67 Total Head Movement = 640 Cylinders (Wild mechanical oscillations). 2. SSTF (Shortest Seek Time First): Selects closest request to current position. Path: 53 -> 65 -> 67 -> 37 -> 14 -> 98 -> 122 -> 124 -> 183 Total Head Movement = 236 Cylinders. (Risk: Starvation for outer tracks). 3. SCAN (Elevator Algorithm): Moves in one direction to the DISK END (199), then reverses towards 0. Path (Moving Right): 53 -> 65 -> 67 -> 98 -> 122 -> 124 -> 183 -> [199] -> 37 -> 14 Total Head Movement = (199 - 53) + (199 - 14) = 146 + 185 = 331 Cylinders. 4. C-SCAN (Circular SCAN): Moves right to DISK END (199), jumps back to 0 without servicing, then moves right. Provides uniform wait time. Path: 53 -> 65 -> 67 -> 98 -> 122 -> 124 -> 183 -> [199] -> [0] -> 14 -> 37 Total Head Movement = (199 - 53) + (199 - 0) + (37 - 0) = 146 + 199 + 37 = 382 Cylinders. 5. LOOK & C-LOOK (Practical Optimization): Like SCAN/C-SCAN, but only travels as far as the LAST REQUEST in that direction (does not go to 199 or 0). LOOK Path: 53 -> 65 -> 67 -> 98 -> 122 -> 124 -> 183 -> 37 -> 14 Total Head Movement = (183 - 53) + (183 - 14) = 130 + 169 = 299 Cylinders!

11. RAID Architectures (RAID 0, 1, 5, 6, 10) & Parity Math

RAID (Redundant Array of Independent Disks) combines multiple physical disks into a single logical volume:

RAID 0 (Striping) RAID 1 (Mirroring) RAID 5 (Distributed Parity) ┌──────┐ ┌──────┐ ┌──────┐ ┌──────┐ ┌──────┐ ┌──────┐ ┌──────┐ │ A1 │ │ A2 │ │ A1 │ │ A1 │ │ A1 │ │ A2 │ │ Ap │ │ A3 │ │ A4 │ │ A2 │ │ A2 │ │ B1 │ │ Bp │ │ B2 │ │ A5 │ │ A6 │ │ A3 │ │ A3 │ │ Cp │ │ C1 │ │ C2 │ └──────┘ └──────┘ └──────┘ └──────┘ └──────┘ └──────┘ └──────┘ (0 Redundancy) (100% Redundancy) (Survives 1 Disk Failure)

RAID Comparison Table

RAID LevelMinimum DisksUsable Storage CapacityFault ToleranceRead SpeedWrite Speed
RAID 0 (Striping)2$N \times \text{Size}$ ($100%$)0 Disks (1 failure loses ALL data)Fast ($N\times$)Fast ($N\times$)
RAID 1 (Mirroring)2$1 \times \text{Size}$ ($50%$)$1 \text{ Disk}$ (out of 2)Fast ($2\times$)Standard
RAID 5 (Block Parity)3$(N - 1) \times \text{Size}$1 DiskFast ($(N-1)\times$)Slower (Parity Overhead)
RAID 6 (Dual Parity)4$(N - 2) \times \text{Size}$2 DisksFast ($(N-2)\times$)Slow (Double Parity)
RAID 10 (1+0)4$(N / 2) \times \text{Size}$1 Disk per sub-arrayVery FastFast

Parity Math via XOR ($\oplus$)

In RAID 5, parity block $P = D_1 \oplus D_2 \oplus D_3$.
If Disk 2 dies, data $D_2$ is recovered via: $$D_2 = D_1 \oplus D_3 \oplus P$$

12. Common Mistakes & Gotchas

[!CAUTION]

1. Deleting a File with Active Open File Descriptors

In Unix, when you rm file.txt, the directory entry is removed, but if a process currently holds an open file descriptor (fd), the Inode and data blocks remain on disk until the process calls close(fd) or terminates!

[!WARNING]

2. RAID is NOT a Backup

RAID protects against hardware disk failures. It does NOT protect against accidental deletion (rm -rf /), filesystem corruption, malware/ransomware, or fire.

13. Step-by-Step Numerical Practice Problems

Problem 1: LOOK Disk Scheduling

Question: Disk head is at cylinder 50. Requests are in queue: 82, 170, 43, 140, 24, 16, 190.
Head is moving towards higher cylinder numbers. Calculate total head movements using the LOOK algorithm.

Solution:

  1. Requests in ascending order: 16, 24, 43, [50], 82, 140, 170, 190.
  2. Move right from 50 to maximum request: $50 \rightarrow 82 \rightarrow 140 \rightarrow 170 \rightarrow 190$.
    • Distance $= 190 - 50 = 140\text{ cylinders}$.
  3. Reverse direction and move left to minimum request: $190 \rightarrow 43 \rightarrow 24 \rightarrow 16$.
    • Distance $= 190 - 16 = 174\text{ cylinders}$.
  4. Total Head Movement $= 140 + 174 = \mathbf{314\text{ cylinders}}$.

Problem 2: RAID 5 Usable Capacity & Parity Reconstruction

Question: An array consists of five 4TB hard drives configured in RAID 5.

  1. What is the total usable storage capacity?
  2. Data bits on disks 1, 2, 3, 4 are 1, 0, 1, 1. What is the parity bit $P$? If disk 3 fails, show how its bit is reconstructed.

Solution:

  1. Usable capacity $= (N - 1) \times \text{Drive Size} = (5 - 1) \times 4\text{ TB} = \mathbf{16\text{ TB}}$.
  2. Parity $P = 1 \oplus 0 \oplus 1 \oplus 1 = \mathbf{1}$.
  3. Reconstruction of Disk 3: $$D_3 = D_1 \oplus D_2 \oplus D_4 \oplus P = 1 \oplus 0 \oplus 1 \oplus 1 = \mathbf{1}\text{ (Successfully restored!)}$$

14. High-Yield Interview Questions & Answers

Q1: What happens under the hood when a file is deleted in Linux?

Answer:

  1. The kernel removes the directory entry (filename, inode_number) from the parent directory block.
  2. The kernel decrements the i_links_count field in the file's Inode.
  3. If i_links_count == 0 AND no running process has an open file descriptor pointing to the inode:
    • The data blocks pointed to by the inode are marked as free in the block allocation bitmap.
    • The inode itself is marked as free in the inode bitmap.
    • Note: Raw data is not immediately overwritten in flash/magnetic medium, which is how undelete tools work.

Q2: What is the difference between a Hard Link and a Soft (Symbolic) Link?

Answer:

  • A Hard Link is an additional directory entry pointing directly to the existing file's Inode number. It shares all permissions, attributes, and data blocks. Deleting the original name does not destroy data as long as the hard link exists. Hard links cannot span across different file systems.
  • A Soft Link is a distinct, independent file with its own unique Inode whose data block simply stores the string path to the target file. If the target file is deleted or renamed, the soft link breaks. Soft links can freely span across different filesystems and link directories.

Q3: Why is Journaling essential in modern file systems like ext4?

Answer: Without journaling, if a system crashes or loses power midway through updating filesystem metadata (e.g., allocating an inode, modifying free block bitmaps, and appending directory entries), the filesystem becomes corrupted and inconsistent, requiring hours of slow fsck disk consistency checks on reboot.
Journaling solves this by executing transactions with Write-Ahead Logging: metadata changes are first committed to a dedicated journal log before modifying actual file system blocks. On reboot after a crash, the OS simply replays or rolls back incomplete journal transactions in seconds.

Proceed to Module 07: Interview Prep, Scenarios & 100+ Question Bank!