04. Management & Optimization

4.4.1 File-System Space Management

Files can be stored using contiguous allocation or dynamic block-based allocation. Nearly all general-purpose filesystems divide storage media into fixed-size logical blocks. Choosing how large those blocks should be, how to track available free space, and how to enforce equitable storage limits across users represents a core systems optimization challenge.

1. The Block Size Selection Dilemma

Storage drives physically transfer data in sectors (typically 512 bytes or 4096 bytes). Operating system file systems group multiple contiguous sectors into a single logical block. The choice of block size involves an inescapable engineering trade-off:

• Small Blocks (e.g., 1 KB – 2 KB):
  • Advantage: Minimizes internal fragmentation. Because files rarely match block boundaries perfectly, the final block assigned to a file is partially filled. On average, each file wastes half of its final block (B/2). For a filesystem dominated by small files (e.g., source code trees, emails, configuration files), small blocks keep storage utilization high.
  • Disadvantage: Degrades I/O throughput. Transferring a 10 MB file across 1 KB blocks requires issuing 10,240 discrete block requests, multiplying indirect pointer traversal overhead, seek latencies, and metadata footprint in memory.
• Large Blocks (e.g., 16 KB – 64 KB):
  • Advantage: Maximizes sustained transfer throughput. Reading large contiguous chunks matches the sequential burst bandwidth of physical media, minimizing seek delays and shrinking the size of inode pointer trees.
  • Disadvantage: Extreme internal fragmentation waste. A 300-byte file placed in a 64 KB block leaves 63.7 KB of unutilized dead space (an efficiency of under 0.5%).

Empirical studies across Unix distributions demonstrate that the median file size typically sits between 2 KB and 4 KB. Consequently, modern desktop and server filesystems (such as ext4 and NTFS) standardize on 4 KB blocks as the optimal equilibrium between internal fragmentation waste and transfer rate efficiency.

2. Tracking Free Blocks: Linked Lists vs. Bitmaps

To allocate space for new files, the filesystem must track every unallocated block on storage media. Two primary data structures dominate:

Approach A: The Linked Free List

Free blocks are chained together. Rather than linking blocks individually (which would require seeking to every single block just to find the next), filesystems use a Grouped Linked List:

• A dedicated disk block is filled entirely with 32-bit or 64-bit block numbers of free blocks. In a 4 KB block using 32-bit addresses, one block stores 1,023 pointers to free blocks, plus one pointer to the next list block.
• Memory Efficiency: The kernel only keeps the single active head block of the free list in RAM. When it empties, it reads the next list block into memory and frees the previous one.
• Disadvantage: Detecting contiguous free spans for large sequential allocations is difficult without walking and reading multiple list blocks off disk.

Approach B: The Bitmap (Bit Vector)

A dedicated allocation map represents the filesystem partition as an array of bits, where each bit corresponds to a single logical block: 0 indicates a free block, and 1 indicates an allocated block.

• Space Overhead: For a 1 TB drive with 4 KB blocks (2²⁸ blocks), the bitmap requires 2²⁸ bits, which equals 2²⁵ bytes (32 MB of storage)—a negligible 0.003% storage footprint.
• Contiguity Search: Finding contiguous blocks is fast. Hardware word instructions (such as finding the first trailing zero) let the allocator scan 64 blocks per CPU instruction to allocate contiguous extents.
• Memory Caching: Modern filesystems divide the volume into Block Groups (such as in ext4), giving each group its own local 1-block bitmap (e.g., 32,768 blocks per group), allowing allocation checks to operate fully within memory.

3. Disk Quotas

Multi-user operating systems prevent rogue users or buggy processes from exhausting disk capacity via Disk Quotas. Quotas track two distinct resource metrics per user or group:

• Block Quotas: Limits total storage volume (measured in kilobytes or megabytes).
• File (Inode) Quotas: Limits total number of files created. This stops users from creating millions of zero-byte files that exhaust the inode table while consuming zero data blocks.

Quotas establish two threshold limits:

• Soft Limit: A warning boundary. When a user exceeds the soft limit, writes succeed, but a warning is logged and a grace period clock (typically 7 days) begins ticking.
• Hard Limit: An absolute ceiling. Writes that attempt to push usage beyond the hard limit immediately fail with an EDQUOT error code. If the grace period expires while usage remains above the soft limit, the soft limit locks into a hard limit, barring further allocations until files are removed.

4.4.2 File-System Backups

Hardware components inevitably fail, storage drives wear out, and human operators accidentally execute destructive commands. Designing resilient backup procedures requires balancing backup window durations against recovery time objectives.

1. Physical vs. Logical Dumps

Storage architectures use two primary methodologies to extract backup copies:

• Physical Dumps (Block-Level):
  • Copies raw sectors sequentially from block 0 to the final block of the partition (e.g., using dd).
  • Pros: Extremely fast. Streams sequentially at maximum hardware throughput without parsing directory trees.
  • Cons: Inefficient. Dumps empty, unused blocks and bad sectors. Furthermore, restoring a single accidentally deleted file requires scanning and parsing an entire multi-terabyte raw disk image.
• Logical Dumps (File-Level):
  • Traverses the directory tree starting from a designated directory root, inspecting directory entries and extracting individual files, inodes, and permissions recursively.
  • Pros: Highly flexible. Skips unused space, supports selective per-file restoration, and allows cross-filesystem migrations (e.g., restoring an ext4 dump onto an XFS volume).
  • Cons: Requires heavy path resolution overhead and recursive directory scanning.

2. Full vs. Incremental Dump Strategies

Executing a complete, full backup of an enterprise storage cluster every single night is rarely feasible in practice. The physical backup window (the maintenance period during which user modifications must be frozen or minimized) is too short, and the sheer volume of data exceeds available network and tape bandwidth. To solve this, storage administrators deploy a hierarchical Incremental Dump Strategy combining base references with delta captures.

The Backup Level Hierarchy

Unix and Linux backup architectures (historically instantiated by the dump utility) organize backups into hierarchical numeric Dump Levels ranging from Level 0 to Level 9:

• Level 0 (Full Backup): Copies every active file and directory on the entire filesystem partition, regardless of its modification history. This serves as the foundational recovery baseline. Every incremental chain must trace its root back to a Level 0 dump.
• Level N (Incremental Backup): Backs up only files and directories that have been created or modified since the last backup taken at a *lower* level than N (i.e., any level < N).

Concrete Weekly Schedule Example: Consider a standard enterprise rotation operating across a seven-day cycle:

• Sunday (Level 0): A complete full backup copies the entire partition.
• Monday (Level 1): Captures all files modified since Sunday's Level 0.
• Tuesday (Level 2): Captures all files modified since Monday's Level 1.
• Wednesday (Level 2): Captures files modified since Tuesday's Level 2.
• Thursday (Level 1): Captures files modified since Sunday's Level 0 (because Level 1 is lower than the previous Level 2).

Tracking Changes & The Recovery Trade-off

To determine whether a file requires archiving during an incremental run, the backup utility compares the file's last modified timestamp (mtime / ctime) against the timestamp embedded in the metadata header of the previous reference backup level. Furthermore, directory change markers trigger the Four-Pass Traversal Algorithm (Scanning inodes, marking ancestor directories, dumping directory structures, and streaming modified file data blocks).

While incremental strategies minimize nightly backup windows, they introduce an inverse penalty during Disaster Recovery. Restoring from a Level 0 full dump requires only a single tape; restoring from an incremental chain requires a multi-step restoration cascade (Level 0 + Level 1 + Level 2 + Level 2). If any single incremental tape in the chain is damaged, restoration fails.

3. Consistency During Live Backups: Snapshots

If an incremental dump executes on a live filesystem, users and background daemons continue writing to files. If a user moves a file from directory /A to directory /B while the backup is traversing /B, the file may either be dumped twice or skipped completely, leaving an inconsistent backup archive.

Modern storage architectures resolve this using Filesystem Snapshots (supported by LVM, ZFS, and Btrfs). A snapshot creates a frozen, read-only logical view of the volume at an exact point in time. When blocks are modified post-snapshot, the underlying driver uses Copy-on-Write (CoW): preserving the original block in a snapshot region while writing updates to a new block. The backup utility walks the frozen snapshot view without freezing user applications or risking corruption.

4.4.3 File-System Consistency

When an unjournaled filesystem crashes (or when hardware bit rot corrupts a journaled filesystem), the operating system runs an integrity checking utility upon reboot (such as fsck in Unix or chkdsk in Windows).

The integrity checker performs a comprehensive Two-Dimensional Audit: validating physical block allocations against logical filesystem references, and validating directory entry trees against inode link counts.

1. Block Consistency Audits

The checker builds two independent tracking arrays in memory:

• Track_Block[B]: Tracks how many times block B is claimed by active inodes.
• Free_Block[B]: Tracks whether block B is present in the filesystem's free list or allocation bitmap.

The checker reads every inode. For each direct and indirect pointer, it increments Track_Block[B]. It then inspects the free list or bitmap. In a healthy filesystem, every block on disk must satisfy mutually exclusive parity: it must either be referenced by exactly one inode ($1$) or marked free ($0$). Discrepancies generate four critical error states:

2. Directory & Link Count Audits

The second dimension validates directory tree linkages against inode metadata. The checker initializes a counter array Link_Count[I]:

1. Start at the filesystem root directory (inode 2).
2. Walk all directory entries recursively, incrementing Link_Count[I] every time an entry references inode I.
3. Compare Link_Count[I] against the inode's internal hard link counter (inode.i_nlink).

Two discrepancies can occur:

• inode.i_nlink > Actual Directory References: If a crash occurred during file deletion, the link count may be 2 while only 1 directory reference exists. If a user deletes that file later, the count drops to 1 rather than 0; the blocks and inode will never be freed. Repair: Overwrite inode.i_nlink with the actual reference count.
• inode.i_nlink < Actual Directory References (or actual references exist, but i_nlink is 0): Worse, an active file might have no directory entries pointing to it at all (orphaned file). Repair: The checker creates a new directory entry linking the orphaned inode into the /lost+found directory so the system administrator can inspect and recover data.