Introduction
File systems are the backbone of any operating system’s storage management. They transform raw disk sectors into organized, accessible files and directories. Understanding file system architecture is essential for system administrators, developers, and anyone working with storage.
In this comprehensive guide, we’ll explore everything from fundamental concepts to modern file system implementations.
File System Fundamentals
What is a File System?
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
โ FILE SYSTEM OVERVIEW โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโค
โ โ
โ A file system provides: โ
โ โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ โ
โ โ 1. STORAGE ORGANIZATION โ โ
โ โ โข Files and directories โ โ
โ โ โข Hierarchical structure โ โ
โ โ โข Metadata (permissions, dates, etc.) โ โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ โ
โ โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ โ
โ โ 2. DATA ACCESS โ โ
โ โ โข Read/write operations โ โ
โ โ โข File naming โ โ
โ โ โข Access control โ โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ โ
โ โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ โ
โ โ 3. SPACE MANAGEMENT โ โ
โ โ โข Allocation of disk space โ โ
โ โ โข Free space tracking โ โ
โ โ โข Fragmentation handling โ โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ โ
โ โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ โ
โ โ 4. INTEGRITY & RECOVERY โ โ
โ โ โข Crash recovery โ โ
โ โ โข Data consistency โ โ
โ โ โข Error detection โ โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ โ
โ โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
File System Layers
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
โ FILE SYSTEM LAYERS โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโค
โ โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ โ
โ โ Application Programs โ โ
โ โ (ls, cp, cat, text editors, etc.) โ โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโฌโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ โ
โ โ โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโผโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ โ
โ โ System Call Interface (POSIX) โ โ
โ โ (open, read, write, close, stat, mkdir, etc.) โ โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโฌโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ โ
โ โ โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโผโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ โ
โ โ Virtual File System (VFS) - Linux โ โ
โ โ (unified interface for all file systems) โ โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโฌโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ โ
โ โ โ
โ โโโโโโโโโโโโโโโโโโโโโโผโโโโโโโโโโโโโโโโโโโโโ โ
โ โ โ โ โ
โ โผ โผ โผ โ
โ โโโโโโโโโโโโ โโโโโโโโโโโโ โโโโโโโโโโโโ โ
โ โ ext4 โ โ Btrfs โ โ NFS โ โ
โ โ โ โ โ โ โ โ
โ โโโโโโฌโโโโโโโ โโโโโโฌโโโโโโ โโโโโโฌโโโโโโ โ
โ โ โ โ โ
โ โผ โผ โผ โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ โ
โ โ Block Device Layer โ โ
โ โ (SDD/HDD, RAID controllers, etc.) โ โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโฌโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ โ
โ โ โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโผโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ โ
โ โ Physical Storage Device โ โ
โ โ (Disk or SSD) โ โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ โ
โ โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
File Organization
Contiguous Allocation
The simplest allocation method - each file occupies consecutive blocks.
"""Contiguous file allocation simulation."""
class ContiguousAllocation:
"""
Contiguous allocation stores files in consecutive disk blocks.
Pros:
- Simple to implement
- Fast sequential access
- Good random access performance
Cons:
- External fragmentation
- Difficult to grow files
"""
def __init__(self, disk_size: int, block_size: int = 4096):
self.disk_size = disk_size # Total blocks
self.block_size = block_size
self.free_blocks = set(range(disk_size))
self.files = {} # filename -> (start_block, size)
def allocate(self, filename: str, size: int) -> bool:
"""Allocate space for a file."""
num_blocks = (size + self.block_size - 1) // self.block_size
# Find consecutive blocks
allocated = []
for start in range(self.disk_size):
if all((start + i) in self.free_blocks for i in range(num_blocks)):
# Found consecutive blocks
for i in range(num_blocks):
self.free_blocks.remove(start + i)
self.files[filename] = (start, num_blocks)
return True
return False
def deallocate(self, filename: str) -> bool:
"""Free allocated space."""
if filename not in self.files:
return False
start, size = self.files[filename]
for i in range(size):
self.free_blocks.add(start + i)
del self.files[filename]
return True
def get_fragmentation(self) -> float:
"""Calculate external fragmentation."""
if not self.free_blocks:
return 1.0
# Count gaps between free blocks
sorted_free = sorted(self.free_blocks)
gaps = 0
for i in range(len(sorted_free) - 1):
if sorted_free[i + 1] - sorted_free[i] > 1:
gaps += 1
return gaps / max(len(self.free_blocks), 1)
Linked Allocation
Each block contains a pointer to the next block - blocks don’t need to be contiguous.
"""Linked list file allocation."""
class LinkedAllocation:
"""
Linked allocation uses pointers in each block.
Pros:
- No external fragmentation
- Easy to grow files
Cons:
- Poor random access (must follow pointers)
- Pointer overhead in each block
-ๅฏ้ ๆง้ฎ้ข (pointer corruption = data loss)
"""
def __init__(self, disk_size: int):
self.disk_size = disk_size
self.free_blocks = set(range(disk_size))
self.files = {} # filename -> [first_block]
self.fat = [-1] * disk_size # File Allocation Table
def allocate(self, filename: str, size_blocks: int) -> bool:
"""Allocate blocks for a file using linked list."""
if len(self.free_blocks) < size_blocks:
return False
# Allocate blocks
blocks = []
for _ in range(size_blocks):
block = self.free_blocks.pop()
blocks.append(block)
# Set up links
for i in range(len(blocks) - 1):
self.fat[blocks[i]] = blocks[i + 1]
self.fat[blocks[-1]] = -1 # End of file marker
self.files[filename] = blocks[0]
return True
def read_chain(self, filename: str) -> list:
"""Read all blocks in a file."""
if filename not in self.files:
return []
blocks = []
current = self.files[filename]
while current != -1:
blocks.append(current)
current = self.fat[current]
return blocks
Indexed Allocation
Uses an index block to store pointers to all data blocks.
"""Indexed file allocation."""
class IndexedAllocation:
"""
Indexed allocation uses an index block for pointers.
Pros:
- Fast random access
- No external fragmentation
- Direct block addressing
Cons:
- Index block overhead
- Limited max file size (by index block entries)
- Need extra I/O for index
"""
def __init__(self, disk_size: int, index_size: int = 256):
self.disk_size = disk_size
self.index_size = index_size # Max blocks per file
self.free_blocks = set(range(disk_size))
self.files = {} # filename -> index_block
def allocate(self, filename: str, size_blocks: int) -> bool:
"""Allocate blocks with index."""
if size_blocks > self.index_size:
return False # File too large
if len(self.free_blocks) < size_blocks + 1: # +1 for index
return False
# Allocate index block
index_block = self.free_blocks.pop()
# Allocate data blocks
data_blocks = []
for _ in range(size_blocks):
data_blocks.append(self.free_blocks.pop())
# Would store data_blocks in index_block in real implementation
self.files[filename] = {
'index': index_block,
'blocks': data_blocks
}
return True
def read_block(self, filename: str, block_num: int) -> int:
"""Read a specific block."""
if filename not in self.files:
return -1
file_info = self.files[filename]
if block_num >= len(file_info['blocks']):
return -1
return file_info['blocks'][block_num]
Comparison
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
โ ALLOCATION METHOD COMPARISON โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโค
โ โ
โ โโโโโโโโโโโโโโโฌโโโโโโโโโโโโโฌโโโโโโโโโโโโโฌโโโโโโโโโโโโโโโโโโ โ
โ โ Method โ Sequential โ Random โ External โ โ
โ โ โ Access โ Access โ Fragmentation โ โ
โ โโโโโโโโโโโโโโโผโโโโโโโโโโโโโผโโโโโโโโโโโโโผโโโโโโโโโโโโโโโโโโค โ
โ โ Contiguous โ Excellent โ Excellent โ High โ โ
โ โ Linked โ Excellent โ Poor โ None โ โ
โ โ Indexed โ Good โ Excellent โ None (index) โ โ
โ โ Extent-basedโ Excellent โ Good โ Low โ โ
โ โโโโโโโโโโโโโโโดโโโโโโโโโโโโโดโโโโโโโโโโโโโดโโโโโโโโโโโโโโโโโโ โ
โ โ
โ Modern file systems (ext4, Btrfs, NTFS) use extent-based โ
โ allocation - groups of consecutive blocks allocated together โ
โ โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
The Inode Structure
The inode (index node) is the fundamental structure for storing file metadata in Unix-like file systems.
Inode Structure
// Traditional Unix inode structure (simplified)
struct inode {
// File type and permissions
mode_t i_mode; // File type and permissions
uid_t i_uid; // Owner UID
gid_t i_gid; // Owner GID
// File size
off_t i_size; // File size in bytes
// Timestamps
time_t i_atime; // Last access time
time_t i_mtime; // Last modification time
time_t i_ctime; // Last status change time
// Link count
nlink_t i_nlink; // Number of hard links
// Block pointers (ext2/3/4 style)
// Direct blocks: 12 pointers to data blocks
blkcnt_t i_blocks; // Number of blocks allocated
unsigned long i_block[15]; // Block pointers
// i_block[0-11]: 12 direct blocks
// i_block[12]: singly indirect
// i_block[13]: doubly indirect
// i_block[14]: triply indirect
// File attributes
unsigned int i_flags; // File flags
unsigned int i_fop; // File operations
void *i_private; // Private data
};
Inode Visualization
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
โ INODE STRUCTURE โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโค
โ โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ โ
โ โ inode โ โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโค โ
โ โ Mode: 0o100644 (regular file, rw-r--r--) โ โ
โ โ UID: 1000 (user) โ โ
โ โ GID: 1000 (group) โ โ
โ โ Size: 16384 bytes (4 blocks) โ โ
โ โ Links: 1 โ โ
โ โ ATime: 2026-02-27 10:30:00 โ โ
โ โ MTime: 2026-02-27 10:30:00 โ โ
โ โ CTime: 2026-02-27 10:30:00 โ โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโค โ
โ โ Block Pointers: โ โ
โ โ โ โ
โ โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ โ โ
โ โ โ 0 โโโโโโบ Block 1001 โ โ โ
โ โ โ 1 โโโโโโบ Block 1002 โ โ โ
โ โ โ 2 โโโโโโบ Block 1003 โ โ โ
โ โ โ ... โ โ โ
โ โ โ 11 โโโโโโบ Block 1012 โ โ โ
โ โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโค โ โ
โ โ โ 12 โโโโโโบ Indirect Block (singly) โ โ โ
โ โ โ Points to more data blocks โ โ โ
โ โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโค โ โ
โ โ โ 13 โโโโโโบ Double Indirect Block โ โ โ
โ โ โ Points to indirect blocks โ โ โ
โ โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโค โ โ
โ โ โ 14 โโโโโโบ Triple Indirect Block โ โ โ
โ โ โ Points to double indirect blocks โ โ โ
โ โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ โ โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ โ
โ โ
โ Max file size with 4KB blocks: โ
โ - Direct: 12 ร 4KB = 48 KB โ
โ - Single indirect: 1024 ร 4KB = 4 MB โ
โ - Double indirect: 1024ยฒ ร 4KB = 4 GB โ
โ - Triple indirect: 1024ยณ ร 4KB = 4 TB โ
โ โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
Inode Implementation
"""Inode simulation."""
from dataclasses import dataclass, field
from typing import List, Optional
from datetime import datetime
@dataclass
class Inode:
"""Simplified inode structure."""
inode_number: int
mode: int = 0o100644 # Regular file
uid: int = 1000
gid: int = 1000
size: int = 0
atime: datetime = field(default_factory=datetime.now)
mtime: datetime = field(default_factory=datetime.now)
ctime: datetime = field(default_factory=datetime.now)
nlink: int = 1
blocks: int = 0
# Block pointers
direct_blocks: List[int] = field(default_factory=lambda: [0] * 12)
singly_indirect: Optional[int] = None
doubly_indirect: Optional[int] = None
triple_indirect: Optional[int] = None
def add_block(self, block_num: int):
"""Add a data block to the inode."""
if self.blocks < 12:
self.direct_blocks[self.blocks] = block_num
elif self.blocks < 12 + 256: # Single indirect
# Would add to singly indirect block
pass
# etc.
self.blocks += 1
self.size = self.blocks * 4096
class FileSystem:
"""Simple file system simulation with inodes."""
def __init__(self, num_blocks: int, block_size: int = 4096):
self.num_blocks = num_blocks
self.block_size = block_size
self.free_blocks = set(range(num_blocks))
self.inodes = {} # inode_number -> Inode
self.next_inode = 1
# Superblock would go here
self.total_inodes = num_blocks // 10
def create_file(self, name: str, size_blocks: int) -> Optional[Inode]:
"""Create a new file."""
# Allocate inode
inode_num = self.next_inode
self.next_inode += 1
# Allocate blocks
blocks = []
for _ in range(size_blocks):
if not self.free_blocks:
return None
blocks.append(self.free_blocks.pop())
# Create inode
inode = Inode(inode_num=inode_num, blocks=size_blocks)
for i, block in enumerate(blocks[:12]):
inode.direct_blocks[i] = block
self.inodes[inode_num] = inode
return inode
def get_inode(self, inode_num: int) -> Optional[Inode]:
"""Get inode by number."""
return self.inodes.get(inode_num)
Directory Structure
Directory Entry
// Traditional Unix directory entry (struct dirent)
struct dirent {
ino_t d_ino; // Inode number
off_t d_off; // Offset to next entry
unsigned short d_reclen; // Length of this record
unsigned char d_type; // File type (DT_REG, DT_DIR, etc.)
char d_name[256]; // Filename (null-terminated)
};
// Linux-specific with flexible array member
struct linux_dirent {
unsigned long d_ino; // Inode number
unsigned long d_off; // Offset to next dirent
unsigned short d_reclen; // Length of this dirent
char d_name[]; // Filename (null-terminated)
};
Directory Implementation
"""Directory structure simulation."""
from dataclasses import dataclass
from typing import Dict, List, Optional
@dataclass
class DirEntry:
"""A directory entry."""
name: str
inode: int
file_type: str # 'file', 'directory', 'symlink', etc.
class Directory:
"""Directory structure."""
def __init__(self, inode_num: int, name: str = "/"):
self.inode_num = inode_num
self.name = name
self.entries: Dict[str, DirEntry] = {}
# Special entries
self.entries['.'] = DirEntry('.', inode_num, 'directory')
self.entries['..'] = DirEntry('..', inode_num, 'directory')
def add_entry(self, name: str, inode: int, file_type: str):
"""Add an entry to the directory."""
self.entries[name] = DirEntry(name, inode, file_type)
def remove_entry(self, name: str) -> bool:
"""Remove an entry."""
if name in self.entries and name not in ['.', '..']:
del self.entries[name]
return True
return False
def lookup(self, name: str) -> Optional[DirEntry]:
"""Look up an entry by name."""
return self.entries.get(name)
def list_entries(self) -> List[str]:
"""List all entries."""
return [name for name in self.entries.keys() if name not in ['.', '..']]
class PathResolver:
"""Resolve file paths to inodes."""
def __init__(self, root_dir: Directory):
self.root = root_dir
self.cwd = root_dir
def resolve(self, path: str) -> Optional[int]:
"""Resolve path to inode number."""
if path == '/':
return self.root.inode_num
# Absolute or relative path
if path.startswith('/'):
current = self.root
components = path[1:].split('/')
else:
current = self.cwd
components = path.split('/')
for component in components:
if not component or component == '.':
continue
if component == '..':
# Would need parent pointer
continue
entry = current.lookup(component)
if entry is None:
return None
# Would need to look up inode and check if directory
return entry.inode if entry else None
Directory Tree Example
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
โ DIRECTORY STRUCTURE โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโค
โ โ
โ / (inode 2) โ
โ โโโ bin/ (inode 3) โ
โ โ โโโ bash (inode 100) โ
โ โ โโโ ls (inode 101) โ
โ โ โโโ cat (inode 102) โ
โ โ โ
โ โโโ home/ (inode 4) โ
โ โ โโโ user/ (inode 5) โ
โ โ โโโ documents/ (inode 10) โ
โ โ โ โโโ report.pdf (inode 20) โ
โ โ โ โโโ notes.txt (inode 21) โ
โ โ โโโ pictures/ (inode 11) โ
โ โ โ โโโ vacation.jpg (inode 30) โ
โ โ โ โโโ family.png (inode 31) โ
โ โ โโโ .bashrc (inode 12) โ
โ โ โ
โ โโโ var/ (inode 6) โ
โ โโโ log/ (inode 7) โ
โ โโโ syslog (inode 40) โ
โ โโโ error.log (inode 41) โ
โ โ
โ Each directory entry maps a name to an inode number โ
โ โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
Journaling File Systems
Journaling protects against crashes by logging changes before applying them.
Journaling Concepts
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
โ JOURNALING OVERVIEW โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโค
โ โ
โ Problem: Without journaling โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ โ
โ โ 1. Write begins โ โ
โ โ 2. Write partially completes โ โ
โ โ 3. CRASH! โ โ
โ โ 4. On recovery: inconsistent state, data loss โ โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ โ
โ โ
โ Solution: Write-Ahead Logging (Journal) โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ โ
โ โ 1. Write intent to journal (metadata) โ โ
โ โ 2. Journal write completes (durable) โ โ
โ โ 3. Write data to actual location โ โ
โ โ 4. Mark journal entry as complete โ โ
โ โ 5. CRASH! Recovery: replay journal = consistent โ โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ โ
โ โ
โ Journal Modes: โ
โ โข Journal (data + metadata): Fullest protection, slowest โ
โ โข Ordered (metadata only): Default for ext4 โ
โ โข Writeback (metadata only, async): Fastest, least safe โ
โ โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
Journal Implementation
"""Journal implementation simulation."""
from dataclasses import dataclass, field
from enum import Enum
from typing import List
from datetime import datetime
class OperationType(Enum):
"""Types of journal operations."""
CREATE = 1
DELETE = 2
MODIFY = 3
RENAME = 4
@dataclass
class JournalEntry:
"""A journal log entry."""
transaction_id: int
operation: OperationType
inode: int
block_numbers: List[int]
timestamp: datetime = field(default_factory=datetime.now)
committed: bool = False
class Journal:
"""Write-ahead logging journal."""
def __init__(self, max_size: int = 1000):
self.max_size = max_size
self.entries: List[JournalEntry] = []
self.current_transaction = 1
self.transaction_log = []
def begin_transaction(self) -> int:
"""Start a new transaction."""
tid = self.current_transaction
self.current_transaction += 1
self.transaction_log.append(tid)
return tid
def log_operation(self, tid: int, operation: OperationType,
inode: int, blocks: List[int]):
"""Log an operation to the journal."""
entry = JournalEntry(
transaction_id=tid,
operation=operation,
inode=inode,
block_numbers=blocks
)
self.entries.append(entry)
# Enforce max size
if len(self.entries) > self.max_size:
self._clean_old_entries()
def commit_transaction(self, tid: int):
"""Mark transaction as committed."""
for entry in self.entries:
if entry.transaction_id == tid:
entry.committed = True
def recover(self) -> List[JournalEntry]:
"""Recover from crash using journal."""
# Find committed transactions
committed = [e for e in self.entries if e.committed]
# Incomplete transactions need to be rolled back
incomplete = [e for e in self.entries if not e.committed]
return committed
def _clean_old_entries(self):
"""Remove old committed entries."""
# Keep only recent entries
self.entries = self.entries[-self.max_size//2:]
class JournalingFileSystem:
"""File system with journaling support."""
def __init__(self):
self.journal = Journal()
self.data_blocks = {}
self.inodes = {}
def write(self, inode: int, data: str, blocks: List[int]):
"""Write data with journaling."""
tid = self.journal.begin_transaction()
# Log the intent
self.journal.log_operation(
tid,
OperationType.MODIFY,
inode,
blocks
)
# Write actual data (simulated)
for i, block in enumerate(blocks):
self.data_blocks[block] = data[i*4096:(i+1)*4096]
# Commit transaction
self.journal.commit_transaction(tid)
def recover(self):
"""Recover from crash."""
print("Starting recovery...")
committed = self.journal.recover()
print(f"Replaying {len(committed)} committed transactions")
# Replay committed operations
for entry in committed:
# In real implementation, would redo the operation
print(f" Transaction {entry.transaction_id}: {entry.operation}")
print("Recovery complete")
Modern File Systems
ext4 (Fourth Extended Filesystem)
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
โ EXT4 FILE SYSTEM โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโค
โ โ
โ Overview: โ
โ โข Default Linux file system since 2008 โ
โ โข Journaling with extents โ
โ โข Backward compatible with ext2/3 โ
โ โ
โ Key Features: โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ โ
โ โ Extents: Instead of block-by-block, allocate ranges โ โ
โ โ โข Reduced metadata overhead โ โ
โ โ โข Better for large files โ โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ โ
โ โ Delayed Allocation: Don't allocate until data is โ โ
โ โ written to disk, allows better grouping โ โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ โ
โ โ Journal Checksumming: Detect journal corruption โ โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ โ
โ โ 48-bit block numbering: Supports up to 1 EB โ โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ โ
โ โ Defragmentation: Online defrag with e4defrag โ โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ โ
โ โ
โ Limitations: โ
โ โข Not copy-on-write (can cause fragmentation) โ
โ โข Limited scalability for very large storage โ
โ โข No built-in RAID, compression, or deduplication โ
โ โ
โ Tools: โ
โ โข mkfs.ext4 - Create ext4 filesystem โ
โ โข tune2fs - Adjust parameters โ
โ โข e4defrag - Online defragmentation โ
โ โข dumpe2fs - Dump superblock info โ
โ โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
Btrfs (B-Tree File System)
// Btrfs uses B-trees for all metadata and data
// Key structures (simplified)
struct btrfs_header {
u8 csum[32]; // Checksum
u8 fsid[16]; // Filesystem ID
__le64 blocknr; // Block number
__le64 flags; // Flags
__le64 chunk_tree_uid; // Chunk tree UUID
};
struct btrfs_root_item {
// Location of root tree
struct btrfs_key location;
__le64 bytenr; // Logical address
__le64 byte_limit;
__le64 bytes_used;
__le64 last_snapshot;
__le64 generation;
__le64 tree_root_id; // Tree root ID
// ... more fields
};
struct btrfs_extent_item {
__le64 generation;
__le64 num_bytes;
__le64 disk_byte_nr;
__le64 disk_len;
__le64 flags;
// For data extents:
// struct btrfs_extent_data_ref ref;
// struct btrfs_shared_data_ref ref;
};
Btrfs Features
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
โ BTRFS FILE SYSTEM โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโค
โ โ
โ Overview: โ
โ โข Copy-on-Write (COW) - never overwrites data in place โ
โ โข Built-in RAID (0, 1, 5, 6, 10) โ
โ โข Compression (zstd, zlib, lzo) โ
โ โข Snapshots and subvolumes โ
โ โข Built-in deduplication โ
โ โข Checksums for data integrity โ
โ โ
โ Copy-on-Write: โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ โ
โ โ Original: โ โ
โ โ Block A โโโบ Data โ โ
โ โ โ โ
โ โ Write new data: โ โ
โ โ Block A โโโบ Old Data (unchanged) โ โ
โ โ Block B โโโบ New Data (new location) โ โ
โ โ Update metadata to point to Block B โ โ
โ โ โ โ
โ โ Benefit: Crash-consistent, no corruption โ โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ โ
โ โ
โ Subvolumes: โ
โ โข Independent file system-like containers โ
โ โข Can be snapshotted independently โ
โ โข Can have separate quotas โ โ
โ โ
โ Snapshots: โ
โ โข Read-only or read-write copies of subvolumes โ โ
โ โข Essentially zero-cost (COW) โ โ
โ โข Foundation for incremental backups โ โ
โ โ
โ Limitations: โ
โ โข Still considered experimental by some โ โ
โ โข RAID5/6 had stability issues โ โ
โ โข Can have slower performance for some workloads โ โ
โ โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
ZFS (Zettabyte File System)
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
โ ZFS FILE SYSTEM โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโค
โ โ
โ Overview: โ
โ โข Originally from Sun Microsystems (now OpenZFS) โ
โ โข Combined file system and volume manager โ
โ โข Extremely scalable (128-bit) โ
โ โข Enterprise-grade features โ
โ โ
โ Architecture: โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ โ
โ โ ZFS Pool (ZPOOL) โ โ
โ โ โข Physical storage pool from devices โ โ
โ โ โข Virtual devices (vdevs) โ โ
โ โ โข RAID-Z configurations โ โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโค โ
โ โ ZFS Dataset โ โ
โ โ โข File systems within the pool โ โ
โ โ โข Can have independent properties โ โ
โ โ โข Quotas and reservations โ โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโค โ
โ โ Copy-on-Write โ โ
โ โ โข Transaction groups (TXG) โ โ
โ โ โข No in-place overwrites โ โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ โ
โ โ
โ Key Features: โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ โ
โ โ Data Integrity: Every block has checksum โ โ
โ โ โข Self-healing with redundancy โ โ
โ โ โข End-to-end checksums โ โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ โ
โ โ Snapshots: Instant, zero-space (until changed) โ โ
โ โ โข Send/receive for backup โ โ
โ โ โข Clones โ โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ โ
โ โ Compression: Multiple algorithms โ โ
โ โ โข lz4 (fast, good ratio) โ โ
โ โ โข zstd (better ratio, variable) โ โ
โ โ โข gzip (maximum compression) โ โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ โ
โ โ Deduplication: Block-level โ โ
โ โ โข Can require lots of RAM โ โ
โ โ โข Optional compression-first approach โ โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ โ
โ โ RAID-Z: Variable-length RAID โ โ
โ โ โข Better than traditional RAID5 โ โ
โ โ โข RAID-Z1/2/3 (1-3 parity disks) โ โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ โ
โ โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
File System Comparison
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
โ FILE SYSTEM COMPARISON โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโค
โ โ
โ โโโโโโโโโโโโฌโโโโโโโโโฌโโโโโโโโโฌโโโโโโโโโฌโโโโโโโโโฌโโโโโโโโโโโ โ
โ โ Feature โ ext4 โ Btrfs โ ZFS โ XFS โ NTFS โ โ
โ โโโโโโโโโโโโผโโโโโโโโโผโโโโโโโโโผโโโโโโโโโผโโโโโโโโโผโโโโโโโโโโโค โ
โ โ Max Size โ 1 EB โ 16 EB โ 256 TB โ 16 TB โ 256 TB โ โ
โ โโโโโโโโโโโโผโโโโโโโโโผโโโโโโโโโผโโโโโโโโโผโโโโโโโโโผโโโโโโโโโโโค โ
โ โ Max File โ 16 TB โ 16 EB โ 16 EB โ 8 exb โ 16 TB โ โ
โ โโโโโโโโโโโโผโโโโโโโโโผโโโโโโโโโผโโโโโโโโโผโโโโโโโโโผโโโโโโโโโโโค โ
โ โ Journal โ Yes โ Yes โ Yes โ Yes โ Yes โ โ
โ โโโโโโโโโโโโผโโโโโโโโโผโโโโโโโโโผโโโโโโโโโผโโโโโโโโโผโโโโโโโโโโโค โ
โ โ COW โ No โ Yes โ Yes โ No โ No โ โ
โ โโโโโโโโโโโโผโโโโโโโโโผโโโโโโโโโผโโโโโโโโโผโโโโโโโโโผโโโโโโโโโโโค โ
โ โRAID Builtโ No โ Yes โ Yes โ No โ No โ โ
โ โโโโโโโโโโโโผโโโโโโโโโผโโโโโโโโโผโโโโโโโโโผโโโโโโโโโผโโโโโโโโโโโค โ
โ โCompress โ No โ Yes โ Yes โ No โ Yes โ โ
โ โโโโโโโโโโโโผโโโโโโโโโผโโโโโโโโโผโโโโโโโโโผโโโโโโโโโผโโโโโโโโโโโค โ
โ โSnapshots โ No* โ Yes โ Yes โ No* โ Yes โ โ
โ โโโโโโโโโโโโผโโโโโโโโโผโโโโโโโโโผโโโโโโโโโผโโโโโโโโโผโโโโโโโโโโโค โ
โ โChecksum โ Meta โ Yes โ Yes โ Meta โ Yes โ โ
โ โโโโโโโโโโโโผโโโโโโโโโผโโโโโโโโโผโโโโโโโโโผโโโโโโโโโผโโโโโโโโโโโค โ
โ โDefrag โ Yes โ Limitedโ Yes โ Yes โ Yes โ โ
โ โโโโโโโโโโโโดโโโโโโโโโดโโโโโโโโโดโโโโโโโโโดโโโโโโโโโดโโโโโโโโโโโ โ
โ โ
โ * Can be added via LVM or other tools โ
โ โ
โ When to use what: โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ โ
โ โ ext4: General purpose, compatibility, simplicity โ โ
โ โ Btrfs: Modern Linux, COW features, container storage โ โ
โ โ ZFS: Enterprise storage, data integrity, large pools โ โ
โ โ XFS: Large files, large directories, high performance โ โ
โ โ NTFS: Windows compatibility, dual-boot โ โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ โ
โ โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
Virtual File System (VFS)
VFS Overview
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
โ VIRTUAL FILE SYSTEM (VFS) โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโค
โ โ
โ VFS provides a unified interface for different file systems: โ
โ โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ โ
โ โ Application โ โ
โ โ open(), read(), write(), stat(), etc. โ โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโฌโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ โ
โ โ โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโผโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ โ
โ โ System Call Interface โ โ
โ โ (POSIX) โ โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโฌโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ โ
โ โ โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโผโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ โ
โ โ VFS Layer โ โ
โ โ โข Superblock, inode, dentry operations โ โ
โ โ โข Generic file operations โ โ
โ โ โข Cache management โ โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโฌโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ โ
โ โ โ
โ โโโโโโโโโโโโโโฌโโโโโโโโโโโโโผโโโโโโโโโโโโโฌโโโโโโโโโโโโโ โ
โ โผ โผ โผ โผ โผ โ
โ โโโโโโโโโโ โโโโโโโโโโ โโโโโโโโโโ โโโโโโโโโโ โโโโโโโโโโโ โ
โ โ ext4 โ โ Btrfs โ โ XFS โ โ NFS โ โ ProcFS โ โ
โ โโโโโโโโโโ โโโโโโโโโโ โโโโโโโโโโ โโโโโโโโโโ โโโโโโโโโโโ โ
โ โ
โ Key VFS Structures: โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ โ
โ โ struct super_block: Mounted filesystem info โ โ
โ โ struct inode: Generic inode (file metadata) โ โ
โ โ struct dentry: Directory entry (name -> inode mapping) โ โ
โ โ struct file: Open file instance โ โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ โ
โ โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
File System Commands
Linux File System Commands
# Create file systems
mkfs.ext4 /dev/sdb1
mkfs.btrfs /dev/sdb1
mkfs.xfs /dev/sdb1
# Check and repair
fsck /dev/sdb1
fsck.ext4 -n /dev/sdb1 # Dry run
fsck -fy /dev/sdb1 # Force repair
# Tune parameters
tune2fs -l /dev/sdb1 # List
tune2fs -c 50 /dev/sdb1 # Check interval
tune2fs -m 5 /dev/sdb1 # Reserved blocks
tune2fs -O ^has_journal /dev/sdb1 # Remove journal
# Mount options
mount /dev/sdb1 /mnt/data
mount -o remount,rw /mnt/data # Remount
mount -o loop file.img /mnt/iso # Loop device
# Information
df -h # Disk usage
du -sh /directory # Directory size
ls -li # Show inodes
stat file # File metadata
# defragment (ext4)
e4defrag -c /dev/sdb1 # Check
e4defrag /dev/sdb1 # Defrag
# Btrfs
btrfs filesystem df /mountpoint # Show space info
btrfs balance start /mountpoint # Rebalance
btrfs subvolume list /mountpoint # List subvolumes
# ZFS
zpool list # List pools
zpool status # Pool health
zfs list # List datasets
zfs snapshot pool@snapshot # Create snapshot
Conclusion
File systems are complex but essential components of any operating system. Key takeaways:
- Multiple allocation strategies exist - Contiguous, linked, indexed, and extent-based each have trade-offs
- Inodes are fundamental - All Unix file systems use inodes to store metadata
- Journaling prevents corruption - Write-ahead logging ensures consistency after crashes
- Modern file systems add features - COW, compression, snapshots, built-in RAID
- VFS unifies access - Linux’s VFS allows transparent access to different file system types
Choosing the right file system depends on your use case: ext4 for simplicity, Btrfs for modern Linux features, ZFS for enterprise storage with data integrity.
External Resources
Books
- “Operating System Concepts” - Silberschatz, Galvin, Gagne
- “Understanding the Linux Kernel” - Bovet & Cesati
- “The Art of Unix Programming” - Eric S. Raymond
Comments