File Systems

A file is a persistent sequence of bytes. The file system stores those bytes without deciding whether they mean text, an image or machine code. A directory gives the file a readable name; its inode number identifies it within the file system.

Open a file and check the result

open(path, flags, mode) returns a file descriptor, a nonnegative integer used in later calls. An error returns -1 and sets errno. Choose O_RDONLY, O_WRONLY or O_RDWR for access. O_CREAT creates a missing file, O_TRUNC empties an existing file, and O_APPEND places each write at the current end.

For a new file, mode requests permissions and the process's umask removes bits. Without a default directory access control list (ACL), the result is mode & ~umask. Requesting 0666 with umask 0022 gives 0644, or rw-r--r--. This argument does not change the permissions of an already existing file.

Descriptors belong to a process. Normally 0, 1 and 2 are standard input, output and error. open chooses the lowest unused descriptor, often 3. On Linux, strace cat notes.txt exposes the calls: opening the input, reading it, writing to descriptor 1, then closing the input.

Follow the offset, not the requested count

read(fd, buf, n) returns the bytes actually read, up to n. For a nonzero request on a regular file, zero means no bytes remain at or beyond end of file; -1 means an error. write also returns an actual count, which can be short. Check that count before advancing a buffer or deciding the operation is complete.

Suppose log.txt contains 300 bytes. Four requests for 100 bytes return 100, 100, 100 and 0. The offset, the position of the next operation, becomes 100, 200, 300 and 300. End of file is a returned count, not a special byte stored in the file.

lseek(fd, 200, SEEK_SET) sets the offset to 200. Reading 50 bytes then returns bytes 200–249 and leaves offset 250. SEEK_CUR measures from the current offset; SEEK_END measures from the file's end. Seeking changes a number in memory. It does not move a disk head or itself read data. pread and pwrite use an explicit position without changing this offset.

Decide which descriptors share an offset

The process's descriptor table points to entries in the kernel's open file table. Each open entry holds the access mode, offset, inode reference and reference count.

If a child seeks a shared descriptor to byte 10, the parent's next read through that entry starts at 10 too. The inode identifies the file, but the open entry holds the offset: two readers can share a file without sharing their position. Shell redirection uses dup2 to make standard output refer to another open entry. close releases one descriptor; the entry disappears after its last reference is released. Closing alone does not force buffered data to stable storage.

A successful write and a crash-safe update answer different questions. A write reports that bytes were accepted. Durability asks whether they survive a crash; atomicity asks whether an update can be observed only as a whole.

Force the bytes to stable storage

Operating systems usually buffer writes in memory and send dirty blocks to storage later, often within roughly 5–30 seconds. This combines small writes and lets the program continue quickly. A crash can erase data still waiting in those buffers.

fsync(fd) forces the file's dirty data and metadata to storage and waits for the device to report completion. A program must check its result before reporting a durable save. close releases the descriptor and is not a substitute for this wait.

A file also needs a durable name. The name-to-inode entry is data belonging to its directory, not to the file. After creating a file, synchronizing only the file can leave its bytes durable without guaranteeing that its new name survives. Open the containing directory and synchronize it when the name must persist.

Replace a file without exposing a partial version

Overwriting a document in place creates an interval in which readers can encounter incomplete contents. O_TRUNC first sets its length to zero. If a crash interrupts the later writes, the old complete copy is already gone.

Instead, write the replacement under a temporary name in the same directory. Then use rename to replace the destination. For an existing destination on the same file system, POSIX makes that replacement atomic: the destination name refers to the old file or the replacement, without an intermediate missing name. Readers do not see a mixture of their contents through that name.

For settings.json, the durable replacement sequence is:

1. Write all new contents to settings.json.tmp, checking for short writes and errors.
2. Call fsync on the temporary file and check success.
3. Call rename("settings.json.tmp", "settings.json") and check success.
4. Call fsync on the containing directory and check success.

The temporary file is complete and durable before the name changes. The final directory synchronization makes that name change durable. A crash during the sequence leaves the destination holding a complete old or complete new version; after the final successful synchronization, the new version is the durable one. Atomic name replacement alone does not promise that an unsynchronized rename survives power loss.

rename across file systems fails with EXDEV. A command that responds by copying and deleting performs several operations, so that fallback has no atomic-replacement guarantee.

Change length without writing every byte

truncate(path, length) and ftruncate(fd, length) set the file's length. Shrinking discards bytes beyond the new end. Extending makes the new region read as zeros. Seeking beyond the end and then writing also creates a zero-reading gap.

A sparse file can represent such a gap without allocating data blocks for it. Starting with an empty file, writing one byte at offset 8192 makes a file 8193 bytes long; the preceding unwritten region reads as zeros. Its logical size can exceed the space physically allocated to it.

Directories separate the names people use from the objects the file system stores. Each directory has its own inode and data blocks; its entries map names to inode numbers.

Follow paths through the tree

An absolute path starts at /. A relative path starts at the process's current working directory. The entry . names the directory itself and .. names its parent; the root's parent is the root. From /home/lee, the relative path ../shared reaches /home/shared.

An extension such as .txt is part of a name. Programs can use it to choose how to interpret the bytes, but the file system does not require a .txt file to contain text.

mkdir creates a directory containing . and ... To list entries, a program uses opendir, calls readdir until no entries remain, and calls closedir. A readdir result includes a name and inode number. Programs change directory contents through calls such as link, unlink and rename, not ordinary write calls. rmdir removes an empty directory.

Give one file two equal names

link(old, new) creates a hard link: another directory entry pointing to the same inode. Neither name is privileged as the original. The inode's link count records how many names refer to it.

Consider these commands when no process holds the file open:

echo hi > a
ln a b
rm a
cat b
rm b

Creating b raises the link count from 1 to 2. Removing a lowers it to 1; b still reaches the same bytes, so cat b prints "hi". Removing b drops the count to 0, allowing the inode and its blocks to be reclaimed.

An open descriptor adds a second lifetime rule. If the final name is unlinked while a process still has the file open, that process can keep accessing it. Reclamation waits for both zero links and no open references. This explains why deleting a large open log may not immediately release its space.

A hard link cannot cross file systems: the destination's inode number would have no meaning in the other inode table. Most Unix systems also prohibit hard links to directories to preserve a tree without cycles. In classic Unix directory accounting, an empty directory has two links, from its parent entry and its own .. Each subdirectory contributes one more through ..; three subdirectories give a count of 5.

Store a path in a symbolic link

A symbolic link, or soft link, is a separate file whose contents are a target path. ln -s /home/ana/report.txt r creates r with the 20-byte target path as its contents. Following it resolves that path. Symbolic links can cross file systems and point to directories.

A symbolic link does not increase its target's link count. Keeping the link object therefore does not keep the target alive.

A file's contents are only part of its state. Metadata records who may use it, its size and type, and when it changed. Mounting makes objects from several file systems reachable through a single tree of names.

Read the metadata correctly

stat(path, &buf) reads metadata through a path; fstat(fd, &buf) reads it through an open descriptor. The results include the inode number, type, permissions, owner and group IDs, size, allocated blocks and link count. File size counts logical bytes; allocated blocks measure storage actually used, which can be smaller for a sparse file.

Three timestamps describe different events:

ctime is not creation time. Updating atime alone does not change ctime. Classic Unix stat has no creation-time field; Linux statx can expose a recorded birth time when the file system supports it.

Decode permission bits

Read, write and execute rights are recorded separately for owner, group and others. Each class is an octal digit: read is 4, write 2 and execute 1. For rw-r-----, the owner gets 4 + 2 = 6, the group gets 4, and others get 0. chmod 640 report.txt sets those bits.

Directory permissions apply to names and traversal. Read allows listing names. Execute allows search, meaning use of the directory in a path. Write together with execute allows creating, deleting and renaming entries. Knowing a name can be enough to open a file in a directory with execute but no read permission, provided the file's own permissions allow access. Listing that directory still fails.

This difference matters for deletion: removing an entry changes its containing directory. A file's write bit controls changing its bytes; it is not the directory's permission to remove its name. Root bypasses most ordinary permission checks. Access control lists (ACLs) can grant rights to named users and groups beyond the three basic classes.

Attach another file system

mkfs initializes a file system on a partition or other device, including its own root directory and metadata. It destroys the device's previous file-system contents, so run it only on a device intended for initialization.

mount attaches that root at an existing directory called the mount point. A drive mounted at /media/usb makes its root contents accessible there. The previous contents of /media/usb are hidden while the mount is active; mounting does not merge them with the mounted tree. Running mount without arguments lists current mounts.

The kernel's virtual file system (VFS) layer gives ext4, XFS, FAT, memory-based and network file systems a common interface. Programs can call open and read through any of them. The combined namespace does not combine their inode tables: equal inode numbers on different file systems can identify unrelated files. Hard links and atomic renames therefore stay within their own file system.

A file system must remember both where bytes live and which space is available. A simple Unix-style layout makes these jobs visible by separating allocation records, inodes and contents.

Divide the partition into regions

A block is the file system's basic allocation unit. A 4 KiB block contains 4096 bytes, or eight traditional 512-byte sectors. Binary sizes use KiB, MiB and GiB; transfer rates such as MB/s use decimal millions of bytes per second.

The teaching design vsfs, the very simple file system, contains these structures:

A bitmap bit of 1 means allocated; 0 means free. The superblock tells the operating system how to interpret the rest of the partition when mounting it. The two bitmaps describe different resources: a file can have an allocated inode before it has any data blocks.

Locate an inode by number

Take a 64-block partition with 4 KiB blocks. Put the superblock at block 0, the inode bitmap at 1, the data bitmap at 2, and the inode table in blocks 3–7. Data occupies blocks 8–63. Five inode-table blocks with 256-byte inodes hold 80 inodes, because each block holds 16. There are 56 data blocks. One 4 KiB bitmap can describe 32768 objects, so much of each bitmap is unused in this tiny layout.

Numbering inode slots from zero, inode 37 starts 37 × 256 = 9472 bytes after the table begins. The table starts at byte 12288, giving absolute byte address 21760. Dividing by 4096 gives disk block 5 with remainder 1280. Dividing by 512 instead gives sector 42 with remainder 256. Read the containing block or sector, then select the inode's bytes within it.

The general method is: table start in bytes plus inode number times inode size. Keep the table's starting address separate from the inode's offset within the table. Omitting that base address locates the wrong disk block.

Separate names, metadata and contents

An inode, or index node, records type, permissions, ownership, size, times, link count, allocated blocks and data locations. It does not contain the filename. The name belongs in a directory entry, allowing several names to share one inode.

A directory has an inode of type directory and data blocks of entries. A simple entry stores an inode number, record length, name length and name. Record length lets traversal skip the whole entry, including reusable space left by deletion. Large directories benefit from indexes: XFS uses B-trees and ext4 uses hashed tree indexes.

Creating a file finds a free inode bitmap bit and sets it. Allocating data similarly changes the data bitmap. An allocator may reserve a run of blocks so the file can grow contiguously. The bitmap says whether a block is free; the inode says which file owns it. These structures must agree.

A program sees consecutive byte offsets, but the corresponding data blocks can be scattered across the disk. The file system needs a mapping from each logical file block to its physical location.

Follow direct and indirect pointers

A direct pointer in an inode names one data block. With 4 KiB blocks, byte offset 10000 lies in logical block 2, because two full blocks use 8192 bytes. The offset within that block is 1808. Logical blocks start at 0, so block 2 uses the third direct pointer.

An indirect pointer names a block containing data-block addresses. A 4096-byte block with 4-byte addresses holds 1024 pointers. A double indirect pointer names a block whose pointers lead to 1024 indirect blocks. Triple indirection adds another level. This multi-level index is deliberately unbalanced: small files use direct pointers without extra pointer-block reads, while large files pay for additional levels.

For an inode with 12 direct pointers and one pointer of each indirect level:

These are capacities of this pointer layout. Pointer blocks occupy storage too, but their bytes are not file contents.

Count pointer blocks for a file

A 5 MiB file occupies 1280 data blocks at 4 KiB each. Assign the first 12 to direct pointers. Assign the next 1024 to the single indirect block. That leaves 244 data blocks.

Those 244 need a double indirect root and one indirect block beneath it. In total, the file needs three pointer blocks: the single indirect block, the double indirect root and its one child. Counting only the double indirect root misses the child that actually contains data addresses. Counting all 1024 possible children wastes space: only the required child is allocated.

Compare extents and chains

An extent records a starting disk block and a run length. A contiguous run of 1000 blocks can use one extent instead of 1000 separate pointers. Ext4, XFS and NTFS use extents. Ext4 can hold up to four extents in its inode, with a tree for more. Fragmentation splits runs and increases the number of extent records needed.

Linked allocation follows a chain of blocks. The File Allocation Table (FAT) stores the next-block links in a separate table, usually cached in memory. A directory entry identifies the first block, and reaching a late block requires following the earlier links. FAT does not use Unix inodes and does not support two hard links to one file.

Consecutive offsets never prove physical contiguity. The allocator chooses locations, and the mapping records those choices.

One system call can require several disk operations, or none. To trace the work, follow the structures the file system must consult and state which of them are already cached.

Walk a path before reading contents

In the simple uncached model, opening /docs/plan.txt reads five blocks:

1. The root inode, whose number is known.
2. Root directory data, to find docs.
3. The docs inode.
4. docs directory data, to find plan.txt.
5. The file's inode.

Each directory fits in one block, and no needed block begins in memory. The file system checks permissions and creates an open file entry. Opening has found the file's metadata; it has not yet read its contents. Root inode number 2 is used in ext2 and ext4.

For a deliberately uncached reading model, each block read then reads the file inode, reads the data, and writes the inode's access time. Two blocks add six I/Os, giving eleven including open. Closing needs no disk I/O in this model. These counts describe the model's explicit rereading and timestamp rules; a real cache changes them.

Account for allocation during creation

Creating /docs/log.txt needs more than finding an existing inode. In the same simple model, it performs four reads for the root and docs inodes and directory data. Reading and writing the inode bitmap adds two I/Os. Updating docs data adds one write. Reading and writing the new inode adds two, and updating the docs inode adds one. Total: ten.

Each newly allocated data block adds five I/Os: read and write the data bitmap, read and write the file inode, and write the data block. Two blocks therefore give twenty I/Os including creation. This trace counts the simple data structures before adding journaling traffic or real cache behavior.

Keeping a ledger helps: list the structure, whether it is read or written, and why. A data write also needs an allocation record and a pointer update. A directory change also changes that directory's metadata.

Let the cache change the trace

A cache hit uses a block already in memory. Linux uses a unified page cache shared with virtual memory, not a permanently separate fixed-size file cache. A repeated open can reuse the directory and inode blocks from the previous traversal. Reading cached contents needs no device read. Linux's usual relatime policy also avoids an atime write on every read.

Write buffering delays sending dirty blocks to disk. Two nearby file creations may update the same inode bitmap in memory and later write it once. The file system can reorder work for better throughput. A short-lived temporary file may be created and removed before its contents ever reach storage.

Buffering improves performance but leaves a durability window. fsync closes that window for a file by waiting for its required writes. Linux O_DIRECT lets suitable programs bypass the page cache when they manage their own buffers; bypassing a cache is not itself the same operation as synchronizing durable storage.

A hard disk can transfer a long run of bytes quickly once its head reaches them. Small scattered requests waste time seeking and waiting for rotation. The Fast File System changes placement so ordinary file operations use more of the disk's transfer bandwidth.

Diagnose the old Unix layout

The early Unix layout placed all inodes near the start and all file data after them. Reading a file could therefore require a long seek from metadata to contents. A free list gradually scattered allocations as files were created and deleted. Even a sequential file could become many unrelated disk accesses.

Small 512-byte blocks made this worse. Each positioning delay bought only a short transfer before the next request needed another seek or rotation. Historical measurements found the old design delivering as little as 2% of the disk's bandwidth. That figure describes the measured early design, not a fixed limit of Unix interfaces.

The Fast File System (FFS), developed at Berkeley in the early 1980s, kept familiar calls such as open, read and write while changing the layout and allocation policy. Larger blocks, typically 4 KiB, increased the bytes transferred per request. Keeping metadata and contents close reduced the distance between related requests.

Build groups with their own resources

A cylinder is the set of tracks at the same radius across a disk's platter surfaces. FFS forms cylinder groups from neighboring cylinders. A file can have its inode and data in the same group, keeping a metadata-to-data seek short.

Each group contains a superblock copy, its own inode and data allocation bitmaps, part of the inode table, and data blocks. The group resembles a small file system, but all groups belong to one file system. A superblock copy also helps recovery if one copy is damaged. Ext4 keeps copies in selected groups instead of every group.

Modern drives hide their physical geometry. Ext2, ext3 and ext4 therefore use block groups, runs of consecutive logical block addresses, to pursue the same locality goal without relying on exact cylinders.

Trace a small file creation

Creating /docs/a.txt needs a free inode, a data block, allocation-map changes, and a new directory entry. FFS tries to place the file in its parent directory's group. The new inode, file data, bitmaps and directory updates can then lie nearby.

The operation still needs several distinct updates. Grouping saves positioning time; it does not collapse all metadata and data into one block. A disk-aware layout improves the cost of reaching those structures without changing the program's file operations.

FFS uses names as clues about which files a program will access together. It also limits how much space one large file can occupy in a group, balancing locality with room for future allocations.

Place directories and files

A new directory goes into a group with relatively few directories and many free inodes. This spreads different directories while leaving room for their future files. A regular file's inode goes in its parent directory's group, and its data goes near its inode.

For /a/b, /a/c and /a/d, the three files are placed near directory /a. A file /b/f follows its own parent /b, usually into another group. This exploits namespace locality: a compiler working on one project often opens several files in the same directory. The directory relation predicts access patterns; it is not a guarantee about every program.

Make an exception for a large file

One large file could consume its group's free blocks and force all later neighbors elsewhere. FFS keeps the first portion, reached by 12 direct pointers, in the inode's group. With 4 KiB blocks that is 48 KiB. Later chunks, each reached by an indirect block holding 1024 pointers, cover 4 MiB of data and go into other lightly used groups.

This sacrifices some locality within the large file to preserve locality for the directory's other files. The large file pays a positioning delay between chunks, so each chunk must be large enough to make that cost worthwhile.

Derive the chunk size

Let positioning take T seconds and transfer rate be R bytes per second. A chunk C takes C/R seconds to transfer. The fraction of total time spent transferring is:

Solving gives:

At 100 MB/s with 10 ms positioning, R times T is 1 MB. A 1 MB chunk needs 10 ms transfer plus 10 ms positioning, giving 50% of peak bandwidth. For 90%, multiply 1 MB by 0.9/0.1 to obtain 9 MB. For 99%, the multiplier is 99, giving 99 MB. Convert milliseconds to seconds before multiplying by MB/s. The denominator includes both transfer and positioning time; dividing only by transfer time would hide the overhead.

Transfer rates have improved faster than positioning delays, so achieving the same fraction of peak requires larger chunks as the gap widens.

Fit small files and preserve compatibility

FFS also used 512-byte sub-blocks so small files did not waste a whole 4 KiB block. Growing files were copied into full blocks; the C library buffered writes in 4 KiB pieces to reduce repeated movement. Historical parameterization left rotational gaps between consecutive blocks so a requested next block had not already passed the head. Modern track buffers make that technique unnecessary by fetching a track internally.

Long names, symbolic links and atomic rename were additional FFS capabilities. The layout speedup itself did not require changing existing programs.

One append looks like one action to a program. On disk it changes several structures, and a crash can leave only some of them updated. Crash consistency asks how those partial results can be prevented or repaired.

Track three independent writes

Appending one 4 KiB block to an existing file changes:

• Db, the new data block containing the appended bytes.
• I, the inode with a larger size and a pointer to that block.
• B, the data bitmap marking the block allocated.

All three reaching storage gives the intended consistent update. None reaching storage leaves the old consistent state. The danger lies in the six partial combinations. The device can reorder requests, so issuing them in a particular order without waiting does not establish completion order.

Classify each partial outcome

An inconsistency occurs when metadata disagrees, such as an inode claiming a block whose allocation bit is free. The allocator might then give that same block to another file. A space leak reserves storage no file can reach. Garbage data can be harder to detect: I and B agree perfectly even though Db never arrived.

Db alone does not leak allocated space, because the bitmap still permits that block to be reused. Writing bytes to a free location is not the same as allocating it. B alone does leak space, because allocation survived without an owning pointer.

Separate structure from meaning

A checker can compare pointers with bitmaps. It cannot generally tell whether plausible bytes are the bytes a program meant to save. The I-and-B outcome demonstrates this limit: a structurally valid file can have incorrect contents.

The desired transition is atomic across the update: recover to the complete old state or the complete new state. A simple storage model gives atomic writes only for one sector, traditionally 512 bytes. Several file-system blocks exceed that unit, so the file system must construct a stronger protocol. Real device atomic-write guarantees depend on the device and interface; the journal protocol must fit its commit record within the supported atomic unit.

Buffering increases the number of changes that can be lost, but it is not the root cause. Even immediately issuing each write leaves a crash boundary between separate completions. File creation, rename and deletion also change multiple structures. Understanding their failure states begins with the same exercise: identify every block changed and ask what happens when only a subset survives.

A file system checker repairs relationships among stored structures after damage has occurred. Its strength is a broad view of metadata; its weaknesses are the cost of scanning and its lack of knowledge about intended file contents.

Reconstruct the allocation picture

fsck, short for file system check, examines an unclean file system before normal mounting. It checks whether the superblock's size and counts make sense and can use a backup superblock if the main copy is damaged.

It then scans inodes and indirect blocks to determine which data blocks files actually reference. From that ownership information it rebuilds the allocation bitmaps. If an otherwise valid inode points to block 74 while the bitmap calls 74 free, the bitmap must change to allocated. Merely trusting the bitmap could allow a later allocation to overwrite the file's data.

The opposite mismatch is a bitmap bit marked allocated without an owning inode pointer. Reconstructing the map can reclaim that space. Repair chooses a consistent relationship; it cannot reconstruct arbitrary missing application bytes.

Check objects, names and links

Every allocated inode needs a valid type, such as regular file, directory or symbolic link. An inode that cannot be repaired is cleared and the allocation records adjusted.

Walking from the root lets fsck count directory references to each inode. It compares these observed references with recorded link counts and corrects errors. An allocated inode that no directory reaches may be moved into lost+found, giving recovered content a reachable name without knowing its original path.

Other checks include:

• Duplicate ownership: two inodes claim one data block. A repair can clear one inode or give each file a separate copy.
• Invalid addresses: pointers outside the file system's valid range must be cleared.
• Directory structure: . and .. must be valid and occupy the first entries in the simple directory layout, entries must refer to allocated inodes, and directories must not have multiple parents.

These checks interact. Clearing an invalid inode also changes which blocks should be allocated and which directory entries remain valid. A repair therefore needs a coherent view of the metadata, not just a list of suspicious individual bits.

Understand what a clean result establishes

Suppose an append's inode and bitmap reached disk but its data did not. The pointer is in range, the allocation bit is set, and the link structure is valid. fsck has no metadata disagreement to repair. The file can pass checking while holding old bytes in its newly added region.

The running time also depends mainly on the file system's size, not the amount changed before a crash. A crash during one three-block update can still require scanning all metadata. On a large file system this can take minutes to hours, keeping normal access unavailable during the scan.

Journaling reduces normal crash-recovery work by recording recent updates. It does not make a checker obsolete: software bugs or failing hardware can damage structures outside what journal replay can repair. fsck remains a repair tool for those cases.

A journal records an update before the file system overwrites its ordinary locations. After a crash, that record tells recovery which complete changes can be redone. This is write-ahead logging. Ext3, ext4, XFS and NTFS use journaling, although their exact log formats differ.

Describe an update as a transaction

For an append, data journaling logs copies of the new inode I, bitmap B and data block Db. A transaction-begin record, TxB, carries an ID and the blocks' final destinations. A transaction-end record, TxE, carries the matching ID and marks commitment.

Logging complete replacement block images is physical logging. Logging an operation description instead is logical logging. Physical redo has a useful property: writing the same image to the same address again has the same effect. Recovery can therefore repeat a checkpoint that partly finished before the crash.

Put commitment after the payload

The basic protocol has four stages:

1. Journal write: write TxB and I, B and Db to the journal, and wait for durable completion.
2. Commit: write TxE, and wait. The transaction is now committed.
3. Checkpoint: copy I, B and Db from the journal to their final locations.
4. Free: release that transaction's journal space for later reuse.

TxE must not become durable before its payload. If all five blocks were issued without an ordering guarantee, a device could complete TxB and TxE while leaving Db unwritten. Recovery would mistake an incomplete transaction for a valid one. In the basic model, TxE fits within one atomic sector write, so it is either present or absent as a complete commit record.

Device write caches must respect the durability boundary too. Cache flushes or forced writes prevent a volatile device cache from making the protocol believe a payload is safe when power loss could still erase it.

Recover from two crash points

A crash after the payload but before TxE leaves an uncommitted transaction. Recovery ignores it, keeping the old file state.

A crash after TxE but during checkpointing leaves a committed transaction. Recovery writes all its images to their final locations in order. Some writes may repeat work already done, which is harmless for these block images. This is redo recovery. Journal space cannot be reused until the committed images have reached their final locations.

The journal is a circular log. Its superblock tracks the active range, allowing completed space to be reused. Batching several updates into one transaction can log one shared directory block or bitmap once. Ext4's default commit interval is 5 seconds, so commitment is not automatically immediate after every application write.

Separate checksums from durability

A transaction checksum can reveal missing or torn payload blocks even when a commit record is present. A checksum-based protocol can issue journal writes together and accept only transactions whose validation succeeds. Checksums detect incomplete records; cache flushes establish whether acknowledged bytes really survive.

An application's buffered, uncommitted write can still disappear. A program requiring durable completion uses fsync and checks success.

Data journaling writes file contents to the journal and then to their final locations. Journaling only metadata reduces that traffic, but the order between data and metadata still determines what recovery can expose.

Keep data ahead of committed pointers

In ordered metadata journaling, Db goes directly to its final location. TxB, I and B go to the journal. These two sets of writes may run in parallel, but both must finish before TxE commits the metadata. After commitment, I and B can be checkpointed and the journal space freed.

The dependency is the key: the block a pointer names must be ready before that pointer becomes recoverable. If I commits first, recovery may install a valid pointer to bytes left by an earlier user of the block. Metadata would agree without holding the intended data.

Ordered mode is the default. Metadata journaling alone does not imply ordered mode: writeback mode can recover structurally sound files with stale contents. The data-journal mode illustrates the full protocol but costs a second write of the file data.

Prevent replay from damaging a reused block

Directory contents count as metadata. Suppose a directory block at address 1000 is logged, then the directory is removed and the same address becomes ordinary file data. That new user data is not logged in metadata-only mode. Replaying the old directory image after a crash would overwrite the new file's bytes.

A committed revoke record tells recovery to skip logged copies of that block from transactions up to and including the revoking transaction. It does not forbid every future use of the address. If a later transaction logs that block again, the later image can still be replayed. This time boundary distinguishes revocation from permanently marking a block unusable.

Compare alternatives

Soft updates enforce dependencies between ordinary writes without a journal. Writing initialized data before a pointer prevents reachable garbage, although interrupted operations can leak space for a later background check to reclaim. FreeBSD’s FFS uses this approach. Tracking all dependencies makes implementation difficult.

Copy-on-write (COW) writes changed blocks to unused locations and uses an atomic root-pointer switch to publish the new tree. The old tree remains available until the switch. ZFS, Btrfs and WAFL use related designs; preserving old blocks also enables snapshots.

Backpointer-based research designs record ownership from data back to inodes so incomplete updates leave detectable mismatches. Optimistic crash consistency reduces waiting and uses checksums and other checks to detect incomplete work. Each approach trades write traffic, recovery guarantees and implementation complexity. Ordered metadata journaling keeps recovery short while writing ordinary file data once.

A log-structured file system turns scattered small updates into large sequential writes. This helps a disk whose transfer rate is high but whose seek and rotation delays remain costly.

Gather updates into a segment

Berkeley's LFS, developed by Rosenblum and Ousterhout and published in 1991, started from changing workloads. Larger memories served more reads from cache, making writes a greater share of disk traffic. Sequential bandwidth grew faster than positioning speed. FFS still needed several short metadata and data writes for a small file creation, and small writes also worked poorly with parity RAID.

LFS buffers changed data, inodes and mapping information together in memory. It writes them to an unused disk region as one large segment. Updating a block creates a new version at a new address; the previous version remains physically present until cleaning reclaims its segment.

Segments amortize positioning just as large FFS chunks do. With rate R, positioning time T and desired transfer-time fraction F, the buffered size is:

At 200 MB/s and 5 ms, 95% requires 19 MB. Transfer takes 95 ms, positioning takes 5 ms, and the effective rate is 19 MB per 0.1 s = 190 MB/s. A high target fraction can require a segment larger than the usual hundreds of kilobytes to several megabytes. The required size follows the device and target, not the word "segment."

Find an inode that keeps moving

The fixed inode-table formula no longer works: every inode update writes a new address. LFS adds an inode map, or imap, mapping each inode number to its newest disk address. Updated imap pieces are written into the log beside the inodes they describe.

A fixed checkpoint region (CR) records where the newest imap pieces are. It is updated periodically, for example every 30 seconds, so the occasional fixed-location write does not dominate traffic.

The lookup chain is:

1. Read the CR at mount to find the current imap pieces.
2. Load the imap into memory.
3. Look up the requested inode number in the imap.
4. Read that newest inode and follow its data pointers.

Once the imap is cached, ordinary file reads use much the same inode-to-data path as in FFS. The extra mapping makes movement affordable without changing the file's stable identity.

Keep directory entries stable

A directory stores names and inode numbers. If /docs/report.txt is updated, its inode moves but keeps its number. The imap changes; the directory entry need not change merely because of that movement.

Without this indirection, a directory containing physical inode addresses would need rewriting whenever a child inode moved. Its own inode would then move, forcing a change in its parent, continuing toward the root. The imap breaks this recursive update problem.

LFS makes writes sequential, not all reads. A file's unchanged blocks can remain in older segments while later versions of other blocks move elsewhere. Reading that file may still seek between segments; large memory caches are part of the design's motivation.

Writing new versions to unused locations keeps old bytes physically present. LFS needs to distinguish old unreachable versions from live blocks, reclaim large free regions, and recover a usable mapping after a crash.

Clean whole segments

The cleaner reads partly occupied segments, copies their live blocks into fewer new segments, and frees the old segments. If four equal-size segments each have one quarter live data, their combined live data fills one new segment. Freeing the four old segments after the copy gains three segments of usable capacity.

Cleaning whole segments preserves large contiguous regions for future sequential writes. Copying has a cost: live blocks are read and written again even though no application changed them. A nearly full disk with mostly live segments may require much copying to recover little free space.

Decide whether a block is live

A segment summary identifies each block's owner inode and logical file-block offset. To test a block at address A, use the imap to find that owner's newest inode. Follow its pointer for the recorded logical block. If the pointer still equals A, this is the live version. If it points elsewhere, A is obsolete.

For example, a summary associates address 600 with inode 14, logical block 2. The current inode 14 points logical block 2 to address 920. Block 600 is dead even if its bytes look like valid data. Liveness depends on current reachability, not how recently a block was written or whether its contents look useful.

Version numbers speed up rejection. Deleting a file or truncating it to zero advances its version in the imap. A segment block carrying an older version can be classified dead without reading the inode.

Cleaning policy also considers expected change. Hot segments contain frequently overwritten blocks; waiting can let more of their blocks die without copying. Cold segments change little, so the original LFS policy cleans them sooner. Policy must balance live fraction, age and available space; a segment's temperature alone does not measure the immediate copying cost.

Recover the mapping and recent work

LFS keeps two checkpoint regions at opposite ends of the disk and alternates updates. Each update writes a timestamped header, the body, and a final matching timestamp. Recovery chooses the newest region whose beginning and end match. An interrupted newer update does not displace an older complete checkpoint.

The checkpoint may not include the most recent completed segments. Recovery therefore rolls forward from its recorded log end, finding valid subsequent updates and applying them to rebuild the current mapping. Data that never formed a valid recoverable update cannot be recreated from memory after power loss.

Related copy-on-write systems preserve old blocks to support snapshots; ZFS, Btrfs and WAFL share that broad idea. SSD controllers commonly use log-structured flash translation layers, while F2FS applies log-structured ideas at the file-system level for flash storage. Each still needs a way to reclaim space left by obsolete versions.

A distributed file system keeps files on a server while programs on client machines use familiar file calls. The client translates those calls into network requests. Delays and failures introduce a question local calls usually hide: what should a client do when it cannot tell whether a request completed?

Keep open-file state on the client

Sun's Network File System (NFS) began in the 1980s. NFSv2 made its server stateless with respect to open files. The server stores files but does not remember each client's descriptors or current offsets. Every request carries enough information to execute without an earlier open request.

A file handle identifies the server volume, inode number and inode generation. The generation changes when an inode number is reused, preventing an old handle from accidentally naming a different file in that reused slot.

To open /home/ana/notes.txt, the client starts with a root handle and sends LOOKUP for home, ana and notes.txt. It retains the resulting handle in its own open-file state. Reading the first 4 KiB becomes a READ request containing that handle, offset 0 and count 4096. Closing the local descriptor needs no NFSv2 CLOSE request because the server has no open entry to release.

Retry without repeating an effect

If no reply arrives, the client cannot distinguish a lost request, an unavailable server or a lost reply. It resends the request after a timeout.

An operation is idempotent when repeating it has the same effect as performing it once. READ, LOOKUP and GETATTR do not modify stored contents. An explicit-offset WRITE also safely repeats the same bytes at the same location in this model. Repeating a request that says "append these bytes at the current end" would instead add a second copy; the offset in an NFS WRITE avoids that ambiguity.

Some requests need extra care. Retrying a successful MKDIR after its reply was lost can return "already exists." The directory is present, but the repeated response differs from the original success. Stateless recovery does not turn every operation into a simple repeatable request.

Make acknowledgments trustworthy

NFSv2 must make a WRITE durable before acknowledging success. Otherwise the server could acknowledge a block, lose it from memory during a crash, and then accept later blocks. The client would believe all writes succeeded while the file contained a missing middle update.

Stable replies avoid that failure at a performance cost. NFSv3 added unstable writes followed by COMMIT, allowing several writes to become durable together. The client must distinguish an unstable acknowledgment from durable completion.

Separate versions of the protocol

A stateful protocol needs machinery to recover open and locking state after a server restart and reclaim state from crashed clients. NFSv4 deliberately accepts that complexity: it has OPEN, CLOSE, locks and time-limited leases that clients renew. The Linux client normally tries version 4.2 first, falling back when necessary. Calling NFSv2 stateless therefore does not describe every NFS version.

Client caching saves network trips but creates multiple copies of shared files. The consistency rule determines when another machine must stop using an old copy and fetch the writer's changes.

Validate NFS caches at sharing boundaries

Under NFS close-to-open consistency, closing a modified file flushes buffered writes to the server. A later open on another client checks freshness and sees those changes. GETATTR or related validation compares server attributes with cached attributes, discarding stale cached data when a change is detected.

Checking on every access would burden the server. Linux caches regular-file attributes for default intervals ranging from 3 to 60 seconds. A process that keeps a file open can therefore read stale cached data between checks. Opening is a stronger sharing boundary than an arbitrary read through an already open descriptor. Close-to-open behavior does not promise immediate visibility of every individual write.

Reuse whole files with AFS callbacks

The Andrew File System (AFS) was designed at Carnegie Mellon in the 1980s to support many clients per server. When no valid local copy exists, opening fetches the whole file to local disk. Reads and writes then use that copy, and closing a modified file sends the whole new version to the server. A valid cached copy can be reopened without downloading it again.

AFSv1 checked validity on every open and left path traversal to the server. AFSv2 shifted traversal to clients, which cache directories, and introduced callbacks. The server promises to notify a client when a cached object changes. Until that promise is broken, the client reuses its copy without repeated checks. Its file identifier includes a volume, a file identifier and a uniquifier.

Follow two overlapping sessions

Suppose clients A and B both open a file. A changes its local copy and closes, sending the new version to the server. The server breaks other clients' callbacks. A later open on B fetches the new version, but B's already open session keeps its existing copy until close and reopen.

If both machines modify their copies, the last one to close replaces the server's whole file. Blocks from the two copies are not merged. Two edits to different offsets can still lose one client's changes because last closer wins chooses a complete version. Processes on one client machine see each other's writes immediately.

Callbacks are server state. After a client restart, cached files are suspect because notifications may have been missed. After a server restart, clients must detect the lost callback promises, through heartbeats or a server notice, and revalidate.

Match caching to the workload

AFS also offered a global namespace, access control lists and administrator-managed volumes. AFSv2 historically increased server scale to about 50 clients from roughly 20 for AFSv1. Neither design's cache rule replaces explicit coordination, such as file locks, when programs need safe shared updates.