Table of Contents
File systems are like temples in the world of data – much happens inside that makes the outside world tick! As an OS developer or power user, understanding file system internals helps immensely. In this comprehensive guide, I‘ll explain file system facets in depth reference the decades of research driving evolution under the hood.
A Brief History of File Systems
Before looking at gritty details, some history sets good context. The early days involved paper tape, punch cards and magnetic tape drives. As disks became affordable in 70s/80s, the first file systems focused on simplistic logical structures like hierarchical directories, basic metadata and sequential access for performance.
Over decades, capabilities advanced tremendously from kilobyte files on floppies to zettabyte sized storage systems today! Let‘s see a quick evolution timeline:
1950s – First file systems to organize data on punch card files and magnetic tape archives
1960s – Multics FS supporting first Unix OS emerges with hierachical directories
1970s – Early disk-oriented file systems like FAT focused on sequential access
1980s – FFS, NTFS bought enhanced data structures like B-trees, fragmentation avoidance
1990s – Distributed network FS enabling easier data sharing across nodes
2000s – High perforamnce journaling capabilities guarding against corruption
2010s – Rapid growth of optimized file systems for SSDs and flash drives
2020s – Cloud scale FS managing exabytes of data spread worldwide!
Phew, that‘s quite a history spanning 70+ years! Now equipped with this context, let‘s get into details…
Core Objectives of the File System Layer
We often take file systems for granted. But like other OS subsystems, they enable simplified abstractions and useful facilities:
Data Persistence – Long term storage beyond runtime by saving inside ordinary files, logs, databases on disk
Access Transparency – Standardized interfaces mask complex media details allowing portability
Sharing – Between users and applications via hierarchical directories and permissions
Protection & Security – Ensuring only authorized access through permissions and access checks
Recovery – Self-healing via journaling and snapshots enabling forensic-grade auditability
Delivering these involves sophisticated interplay between algorithms and data constructs. As a developer or expert user, understanding these better will give you superpowers! 🦸
Now that we know the goals, let‘s analyze essential constructs starting with properties assigned to files.
How File Systems Identify and Track Files
As the basis of long term information storage, files need careful tracking. Here are key properties the file system assigns:
| Property | Size (Bytes) | Description |
|---|---|---|
| File Name | 255 (MAX) | Unique identifier in directory path |
| Creation Time | 8 | Timestamp when first created |
| Modified Time | 8 | Timestamp when contents updated |
| File Type | 1 | Structural format like text, Executable etc. |
| Location | 8 | Pointer to storage blocks on disk where contents saved |
| File Size | 8 | Current size of contents in bytes |
| Owner ID | 4 | Reference to registered system user who created file |
| Permissions | 1 | Access control flags – read/write/execute |
Small per-file overhead isn‘t it? But powerful primitives enabling tons of functionality!
The file system layers assign these properties, track them in internal tables / trees and enable seamless access via consistent updates and lookups.
Now let‘s shift gears to actual storage allocation and layout.
Inside File System Space Management
A key job is optimal allocation of storage space to files as needed from available volumes across disks. Goal is maximizing performance and minimizing fragmentation.
Popular allocation schemes include:
| Scheme | Description | Benefits | Drawbacks |
|---|---|---|---|
| Contiguous | File occupies a set of contiguous block addresses |
Fastest access possible by leveraging disk sequential I/O | External fragmentation over time as disks fill up |
| Linked | Each block stores address of next block in chain |
No external fragmentation Good for sequential access |
Slower random access due to extensive seeks |
| Indexed | Tables map file to list of non-contiguous blocks |
Supports fast direct access Easy to resize files |
Index table overhead per file |
To balance these tradeoffs, most native file systems leverage hybrid allocation using:
- Contiguous for initial file allocation
- Linked or Indexed for later growth
This optimization demonstrates how deep algorithms powering file systems aim to offer best of both worlds!
Digging deeper, let‘s analyze key data structures next…
Critical File System Data Structures
Internally file systems leverage a variety of specialized data structures optimized for blazing fast lookups, inserts and updates as file I/O occurs frequently.
Core data structures playing vital roles include:
- Balanced Trees
Enables O(logN) access speed for tracking free blocks, storage zones etc. Variants like AVL, Red-Black, B-Trees used.
- Buffer Cache
Frequently accessed metadata like superblock info, inodes and indirect blocks cached in-memory enabling faster access.
- Journal Logs
Key area for ensuring transactional consistency and quick recovery from failures.
- Extents
Contiguous storage regions helping avoid slow fragmentated data access especially for large files like videos.
- Volume Managers
Enable combining multiple disks into logical volumes appearing like single storage pool for efficiency.
These demonstrate how our simple view of files maps underneath to sophisticated algorithms and data constructs!
Now that we covered on-disk organization, what about presenting storage logically to users? This is where directories help…
File Directories – Logically Organizing Files
Recall that directories logically group related files together into hierarchical categories for easier management.
A key aspect is inodes acting as unique IDs enabling lookup of file attributes and storage location. Additional metadata tracked for each file entry includes:
- File name
- File type
- Current file size
- Date & timestamps
- Ownership and access permissions
This metadata assists not only end users browsing directories, but also apps quickly locating files by name instead of remembering physical locations on disk!
Additionally support for links and aliases allows a file entry in one directory to be accessible also via alternative paths. This offers flexibility adapting over time to changing organizational needs and moving data around.
Now that we covered internal structures, externally how do users and apps distinguish file types easily? Enter our familiar friend… file extensions!
File Extensions for Quick File Type Identification
Recall file extensions like .doc, .png and .exe allow quick guessing of file types from a user perspective.
Here‘s a handy summary reference:
| Extension | File Type | Description |
|---|---|---|
| .exe, .com | Executable programs | Ready-to-run machine code |
| .obj, .lib | Object code | Compiler output |
| .c, .py, .js | Source code | App source code |
| .txt,.md | Documents | Plain text docs |
| .doc, .docx | Documents | Formatted text |
| .xls,.csv | Spreadsheets | Tables of data |
| .png, .jpg | Images | Raster graphics |
| .mp3, .aac | Audio | Music files |
| .mp4, .avi | Video | Video files |
| .zip, .rar | Archives | Compressed file containers |
So while the file system handles internal identification of formats based on structural rules, extensions help external usage!
Now that we covered file system essentials, let‘s glimpse at some evolving frontiers…
Frontiers of File System Evolution
We covered core concepts rooted in decades of research and field hardening. But the pace of innovation continues! Here are some directions:
Distributed Network File Systems – Enable easier data sharing across nodes providing centralized metadata, caching and replication. Examples include CIFS/SMB, NFS and CephFS.
Exascale Global File Systems – Cloud scale file systems managing exabytes of data spread worldwide supporting map-reduce processing. Example: Colossus FS backing Google storage!
Non-Volatile Storage Integration – Optimizing for new fast non-volatile memory technologies like SSDs, NVMe and Storage Class Memory with persistent memory file systems.
New Access Methods – Support beyond traditional block based storage protocols to allow rich data workloads leveraging object and other access methods.
Metadata Search Integration – Easy attribute and tag based search capabilities for digging into massive data at petabyte scales. Requires tight coupling of metadata with search indexes.
As you see, we are entering a Cambrian explosion fueled by seismic data growth and workload needs! Exciting times ahead for sure as file systems continue evolving.
So while foundational concepts endure over decades, the quest on building performant, scalable and resilient file systems continues! This was but a fast paced glimpse into inner workings. Hopefully you now have better context of the pivotal role file systems play underneath enabling our digital lives!