File Systems
A disk stores numbered blocks and nothing else. A file system is the layer that turns those blocks into named, growable, permissioned files — and that keeps the naming intact when the power fails mid-write.
Files, Inodes, and Directories
A file system is the layer that turns a device's numbered blocks into named, growable, permissioned files. A file is an abstraction the hardware knows nothing about — storage devices expose numbered blocks. The file system supplies the name, the growable size, the permissions, and the guarantee that block 4,192 and block 91,006 are consecutive parts of one document.
In Unix-style file systems operating system designers favour, the metadata lives in an inode: size, owner, group, permission mode, timestamps, link count, and the list of data blocks. The inode does not contain the file's name, which surprises people and is the design's most important detail.
The name lives in the directory, which is itself just a file whose contents are name-to-inode-number mappings. Opening /home/notes.txt means reading the root directory to find home's inode, reading that to find notes.txt's inode number, then reading that inode to find the data blocks.
That separation explains hard links immediately: two directory entries pointing at one inode are equally real, neither is the original, and the file's data disappears only when the link count reaches zero. A symbolic link is different in kind — a small file containing a path string, which may point at nothing at all and breaks if the target moves.
- Inode holds metadata and block pointers, never the name
- A directory is a file mapping names to inode numbers
- Hard links are equal entries sharing one inode
- Symlinks store a path and can dangle
Allocation Methods
Contiguous allocation stores a file in consecutive blocks. Reading is optimal — one seek then a straight run — and random access is a single addition. It fails for the reason contiguous memory allocation fails: external fragmentation, plus the impossible requirement of knowing a file's final size when you create it. It survives only where files never change, as on read-only media.
Linked allocation puts a pointer to the next block in each block. Files grow freely and nothing fragments, but random access is ruinous — reaching block 5,000 means reading 5,000 blocks — and one corrupted pointer severs the entire tail of the file. FAT improves this by lifting the pointers into a File Allocation Table kept in memory, so the chain can be walked without touching the data blocks.
Indexed allocation gives each file an index block listing its data blocks. Random access is one lookup, and there is no fragmentation problem. The question becomes how to handle files larger than one index block can describe.
Unix answers with a multi-level index. An inode holds roughly 12 direct block pointers, then a single indirect pointer (a block full of pointers), a double indirect, and a triple indirect. Small files — the overwhelming majority — are reachable with no indirection at all, while the triple indirect still allows terabyte files. Cost scales with file size instead of being paid uniformly.
| Method | Random access | Grows freely | Fragmentation | Fails when |
|---|---|---|---|---|
| Contiguous | O(1) | No | External | Final size is unknown |
| Linked | O(n) | Yes | None | One pointer is corrupted |
| Indexed | O(1) via index | Yes | None | File outgrows one index block |
| Multi-level index | O(1), 0–3 indirections | Yes | None | (Unix answer — scales with size) |
- Contiguous: fastest reads, needs the final size up front
- Linked: grows freely, random access is O(n), fragile chains
- Indexed: one lookup for random access, no fragmentation
- Unix multi-level index keeps small files indirection-free
Terms, operations, and practical uses
Naming
- InodeSize, owner, mode, timestamps, and block pointers — never the name.
- DirectoryA file mapping names to inode numbers.
- Hard linkA second equal directory entry for one inode.
- Symbolic linkA small file holding a path; it can dangle.
Allocation
- ContiguousFastest reads; needs the final size known up front.
- LinkedGrows freely; random access is O(n) and chains are fragile.
- IndexedAn index block per file; random access is one lookup.
- Multi-level indexDirect, single, double, triple indirect — small files stay direct.
Crash consistency
- JournalIntent written and committed before the real structures change.
- Ordered modeext4 default: data lands before the metadata naming it.
- Copy-on-writeZFS and btrfs never overwrite live data.
- fsyncThe only call that promises bytes reached the device.
Resolve a path the way the disk does
# Path lookup the way the disk does it: directory maps name to inode number,
# inode holds everything else. That split is why a hard link costs nothing.
directory = {"notes.txt": 42, "backup.txt": 42} # two names, one inode
inodes = {
42: {"size": 9000, "mode": 0o644, "links": 2, "blocks": [12, 17, 22]},
}
def resolve(name):
inode_num = directory[name] # step 1: name -> number
return inode_num, inodes[inode_num] # step 2: number -> metadata
num, inode = resolve("notes.txt")
other, _ = resolve("backup.txt")
blocks = ",".join(str(b) for b in inode["blocks"])
print(f"notes.txt -> inode {num} -> blocks [{blocks}] "
f"| {inode['links']} links, same inode" if num == other else "mismatch")#include <iostream>
#include <map>
#include <string>
#include <vector>
using namespace std;
// Path lookup the way the disk does it: directory maps name to inode number,
// inode holds everything else. That split is why a hard link costs nothing.
struct Inode {
int size;
int mode;
int links;
vector<int> blocks;
};
int main() {
map<string, int> directory = {{"notes.txt", 42}, {"backup.txt", 42}};
map<int, Inode> inodes = {{42, {9000, 0644, 2, {12, 17, 22}}}};
int num = directory["notes.txt"]; // step 1: name -> number
Inode inode = inodes[num]; // step 2: number -> metadata
int other = directory["backup.txt"];
cout << "notes.txt -> inode " << num << " -> blocks [";
for (size_t i = 0; i < inode.blocks.size(); i++) {
if (i) cout << ',';
cout << inode.blocks[i];
}
cout << "] | " << inode.links << " links, "
<< (num == other ? "same inode" : "different inodes") << "\n";
}import java.util.List;
import java.util.Map;
class Main {
// Path lookup the way the disk does it: directory maps name to inode
// number, inode holds everything else -- why a hard link costs nothing.
record Inode(int size, int mode, int links, List<Integer> blocks) {
}
public static void main(String[] args) {
Map<String, Integer> directory = Map.of("notes.txt", 42, "backup.txt", 42);
Map<Integer, Inode> inodes = Map.of(42,
new Inode(9000, 0644, 2, List.of(12, 17, 22)));
int num = directory.get("notes.txt"); // step 1: name -> number
Inode inode = inodes.get(num); // step 2: number -> metadata
int other = directory.get("backup.txt");
StringBuilder sb = new StringBuilder();
for (int i = 0; i < inode.blocks().size(); i++) {
if (i > 0) sb.append(',');
sb.append(inode.blocks().get(i));
}
System.out.println("notes.txt -> inode " + num + " -> blocks [" + sb
+ "] | " + inode.links() + " links, "
+ (num == other ? "same inode" : "different inodes"));
}
}notes.txt and backup.txt, one inode, three blocksnotes.txt -> inode 42 -> blocks [12,17,22] | 2 links, same inodeRun the example step by step
Free Space and Modern Layouts
The file system must also track which blocks are free. A bitmap uses one bit per block — 1 for used, 0 for free — which is compact (a 1 TB disk with 4 KB blocks needs 32 MB) and makes finding contiguous runs easy, since that is a search for consecutive zero bits.
A free list chains free blocks together instead, using no extra space at all because the pointers live in blocks nobody is using. The drawback is that finding contiguous free space requires walking the list, so most modern systems use bitmaps, often with grouping to speed the search.
Extents replace per-block bookkeeping with (start, length) pairs. A 1 GB contiguous file needs one extent rather than 262,144 block pointers, which shrinks metadata enormously and makes sequential reads fast. ext4, XFS, NTFS, and APFS are all extent-based.
Layout policy matters as much as the structures. Placing an inode near its data blocks, and keeping a directory's files near each other, turns many small seeks into few — which mattered enormously on spinning disks and still matters on SSDs for reducing request count, even though seek time is gone.
- Bitmaps: compact, and contiguous runs are easy to find
- Free lists: zero overhead, poor at finding contiguous space
- Extents replace block lists with (start, length) pairs
- Locality of inode and data still reduces request count
Crash Consistency and Journaling
A single logical operation touches several structures. Creating a file writes a directory entry, initialises an inode, and updates the free-space bitmap. A crash between any two leaves the file system inconsistent — an inode with no name, or blocks marked used that nothing references.
The old repair was fsck, scanning the entire file system to find and fix contradictions. It works and takes time proportional to the disk, which became untenable as disks grew: hours of downtime after an unclean shutdown.
Journaling fixes this by writing intent before action. The changes are recorded in a journal and committed there first; only then are the real structures updated; then the journal entry is cleared. After a crash, recovery replays or discards journal entries and finishes in seconds regardless of disk size.
The mode matters. Journal mode logs data and metadata — safest, slowest, every write happens twice. Ordered mode (the ext4 default) journals only metadata but guarantees data blocks are written before the metadata referencing them, which prevents an inode pointing at a stranger's old data. Writeback journals metadata with no ordering guarantee, which is fastest and can expose garbage in a file after a crash. Alternatives exist: copy-on-write systems like ZFS and btrfs never overwrite live data, so a crash simply leaves the previous consistent version intact.
The crucial caveat is that journaling protects the file system's consistency, not your data. A write sitting in the page cache is not on the device. Only fsync forces it down and returns when the device has it — which is why databases call fsync at every commit and why 'the file was empty after the crash' is a fsync bug, not a file system bug.
| Mode | Journals | Guarantees | Cost |
|---|---|---|---|
| Journal | Metadata and data | Strongest — no stale or lost data | Every write happens twice |
| Ordered | Metadata only | Data lands before the metadata naming it | Moderate — the ext4 default |
| Writeback | Metadata only | Consistency only, not ordering | Fastest; a file may show garbage |
- Journal records intent before the structures are touched
- Recovery replays the journal in seconds, not an fsck scan
- ext4 ordered mode stops inodes pointing at stale data
- Journaling protects metadata; only fsync protects your bytes