Basic Concepts and Implementation of File Systems

Basic Concepts and Implementation of File Systems

Description
A file system is a mechanism within an operating system for managing data on storage devices (such as hard drives, SSDs). It is responsible for organizing, storing, retrieving, and controlling access to data. Core issues include: How are files mapped to physical storage blocks? How is disk space managed efficiently? How is data consistency ensured? The implementation principles of a classic multi-level indexed file system (such as Unix's inode scheme) are explained below as an example.

1. Core Components of a File System

  • File Control Block (FCB): Each file corresponds to a metadata structure (e.g., inode), storing metadata such as file permissions, size, timestamps, and data block locations.
  • Data Blocks: The disk is divided into fixed-size blocks (e.g., 4KB). File contents are stored scattered across multiple blocks.
  • Directory Structure: A directory is essentially a special file whose content is a mapping table from filenames to FCB indices (e.g., a.txt → inode number).

2. Multi-Level Index Addressing Process
Assume an inode contains 15 pointers, divided into three categories:

  • Direct Pointers (first 12): Directly point to the physical addresses of blocks storing file data, suitable for small files (e.g., ≤48KB).
  • Single Indirect Pointer (13th): Points to an "index block," which itself stores 256 pointers (assuming 4-byte pointers and 1KB block size), capable of addressing 256 data blocks (e.g., 1MB).
  • Double Indirect Pointer (14th): Points to an index block, where each pointer in that block points to another single indirect index block, supporting 256×256=65,536 data blocks (e.g., 256MB).

Example: Reading a byte at the end of a 500KB file:

  1. Find the inode number by looking up the file path in the directory and load the inode into memory.
  2. Calculate the logical block number where the target byte resides: Assuming a 4KB block size, the last byte of a 500KB file is in block 124 (counting from 0).
  3. Addressing process:
    • The first 12 blocks use direct pointers (blocks 0~11).
    • Blocks 12~267 are managed by the single indirect pointer: 124 - 12 = 112, find the physical block address at position 112 in the single indirect index block.
  4. Read the data based on the physical block address.

3. Space Management: Bitmap Method

  • Data Block Bitmap: A binary array where each bit indicates whether a data block is occupied (0 free, 1 occupied). When allocating a new block, the bitmap is scanned to find a free bit.
  • Inode Bitmap: Similar principle for managing space allocation in the inode area.

4. Consistency Guarantee: Journaling
To prevent data corruption due to system failures, file systems use journaling:

  1. Journal Write: First write the metadata operations about to be performed (e.g., creating a file) to a temporary space in the journal area.
  2. Commit Checkpoint: Mark the operations as valid after the journal write completes.
  3. Actual Write: Apply the operations to the main file system structures.
  4. Clean Journal: Clear the journal records after success. If a crash occurs mid-operation, unfinished operations can be recovered from the journal upon restart.

Summary
File systems decouple metadata from data through inodes, use multi-level indexing to balance efficiency for files of different sizes, manage free space with bitmaps, and ensure crash consistency with journaling mechanisms. These designs together enable efficient and reliable file storage.