File Systems

The previous lesson left the partition as a range drawn on the device’s body: a piece with a start, an end, and a type label, saying nothing about what is inside. The moment an arrangement is built inside that range, several decisions are made, and most of these decisions cannot be changed afterward.

This lesson’s question is this: on the same partition, with the same files, at which points do different designs diverge. There are two axes to measure — the cost of a name lookup in a directory, and whether a corrupted block is noticed during a read. Both are countable, and neither shows up in the tool’s output.

What a File System Holds

A file system keeps four separate ledgers inside the same partition. The first is the name ledger: directory entries, binding a name to an identity. The second is the metadata ledger: every file’s size, permissions, owner, timestamps, and which blocks its content sits in. The third is the space ledger: which blocks are full, which are free. The fourth is the consistency ledger: the record that keeps the on-disk structures mutually consistent if an update is interrupted halfway.

How these four ledgers are kept varies from design to design, and this is where the difference comes from. Families one might encounter include XFS, Btrfs, ZFS, and the extended file system family; this lesson measures not the names but the axes between them. There are four axes: whether the metadata ledger’s size is fixed at format time or grows as needed; whether the name ledger is a sequential list or a searchable structure; whether the space ledger is kept block by block or as contiguous ranges; whether the block read is checked for corruption.

Which family gets installed by default varies by distribution, and this lesson does not rank one family above another. What is measured is the cost of the choice, not a ranking. A design that is cheap on one axis is expensive on another, and which axis dominates depends on the workload itself; when the workload changes, the decision ages, but the file system keeps standing in place.

Which design an installed partition carries is learned by reading. lsblk -f writes every partition’s type label and identity, blkid gives the same information one at a time. The transcript below is a sample transcript showing the shape of the output; it was not run, and no numeric claim in this lesson comes from it.

NAME   FSTYPE      FSVER  LABEL   UUID                       MOUNTPOINT
sdb
├─sdb1 ext4        1.0    root    11111111-1111-1111-1111-1  /
├─sdb2 xfs                data    22222222-2222-2222-2222-2  /data
├─sdb3 ext4        1.0    log     33333333-3333-3333-3333-3  /log
└─sdb4 swap        1      swap    44444444-4444-4444-4444-4  [SWAP]

The identity field in the transcript will be useful in later lessons: a partition’s name can change, its identity cannot.

Numbers Fixed at Format Time

Building a file system on a partition means writing a header at the partition’s start and allocating space for the ledgers. This operation fixes a series of numbers, and most of what gets fixed cannot be changed afterward, or can be changed only by emptying the file system.

The first number fixed is the block size: the smallest unit the file system allocates. The second is the metadata record count; in designs that keep a fixed table, this number is set at format time and does not grow unless the file system is enlarged. The third is the directory’s internal layout, measured below. The fourth is which ledgers the checksum covers. The fifth is the consistency record’s mode: whether only metadata is journaled or data too. The file system abstraction lesson in the Operating System Concepts course measured the write multiplier of a journaled design; that measurement is not repeated here.

There is also the space ledger’s format. In a design that keeps a block list, one record is needed per block; in a design that keeps contiguous ranges, a hundred blocks running consecutively is a single record. The second produces far less metadata for large, unfragmented files, and its gain erodes as fragmentation grows. Which format gets chosen depends on the file-size distribution, and this distribution is not known at format time; the decision is made by guessing.

The destructive-command boundary begins here: the command that formats a partition irreversibly erases everything on that partition, and if the wrong partition name is written, it can run without a warning. This lesson does not give the formatting command in a runnable, complete form. The safe way to test it is mounting a file as a loop device and doing the trial there.

Same Directory, Three Internal Layouts

On the fictional server’s /data partition, the files produced by the measurement-collecting unit pile up in a single directory. A directory is a table, and that table’s internal layout is a design decision. The file system abstraction lesson in the Operating System Concepts course counted reading a directory as one step and assumed the entry count did not change the step count. This lesson pays that assumption’s cost.

• ST8 — The work measured is creating a new file. Every creation is first a lookup: does the same name already exist in the directory. What is counted are the comparisons in this lookup.
• ST9 — In the sequential-list layout, the lookup goes start to end. In the hashed layout, a name falls into a bucket and is compared only against the names in that bucket; the bucket count is 4096 and is fixed at format time. In the tree layout, a branch carries 200 names, and the lookup finishes in as many steps as the tree’s depth.
• ST10 — What is measured is the comparison count; wall-clock time is not measured.

"""Directory lookup: same files, three different internal layouts."""
BUCKETS = 4096       # bucket count in the hashed layout
BRANCH = 200         # names carried by a B-tree node


def build_cost(n, layout):
    """Every new name is first LOOKED UP (does it exist). Total comparisons."""
    if layout == "linear":
        return n * (n - 1) // 2
    if layout == "hashed":
        return sum(i // BUCKETS + 1 for i in range(n))
    depth, total = 1, 0
    for i in range(1, n + 1):
        if i > BRANCH ** depth:
            depth += 1
        total += depth
    return total


LAYOUTS = ("linear", "hashed", "tree")
SCALE = (1000, 5000, 10000, 30000, 100000)
BASELINE = {d: build_cost(1000, d) for d in LAYOUTS}

print("file count    ", "  ".join(f"{d:>12s}" for d in LAYOUTS))
for n in SCALE:
    print(f"{n:12d}  ", "  ".join(f"{build_cost(n, d):12d}" for d in LAYOUTS))
print()
print("estimate scaled linearly from 1000 files, vs actual")
print("file count  layout        estimate       actual  deviation ratio  wrong diagnosis")
wrong = 0
for n in SCALE:
    for d in LAYOUTS:
        estimate = BASELINE[d] * n // 1000
        actual = build_cost(n, d)
        ratio = actual / estimate
        y = ratio > 2
        wrong += y
        print(f"{n:12d}  {d:10s} {estimate:12d} {actual:12d}  {ratio:10.2f}  {str(y):>11s}")
print("wrong diagnosis:", wrong, "/", len(SCALE) * len(LAYOUTS))

file count           linear        hashed          tree
        1000         499500          1000          1800
        5000       12497500          5904          9800
       10000       49995000         17712         19800
       30000      449985000        125312         59800
      100000     4999950000       1271200        259800

estimate scaled linearly from 1000 files, vs actual
file count  layout        estimate       actual  deviation ratio  wrong diagnosis
        1000  linear           499500       499500        1.00        False
        1000  hashed             1000         1000        1.00        False
        1000  tree               1800         1800        1.00        False
        5000  linear          2497500     12497500        5.00         True
        5000  hashed             5000         5904        1.18        False
        5000  tree               9000         9800        1.09        False
       10000  linear          4995000     49995000       10.01         True
       10000  hashed            10000        17712        1.77        False
       10000  tree              18000        19800        1.10        False
       30000  linear         14985000    449985000       30.03         True
       30000  hashed            30000       125312        4.18         True
       30000  tree              54000        59800        1.11        False
      100000  linear         49950000   4999950000      100.10         True
      100000  hashed           100000      1271200       12.71         True
      100000  tree             180000       259800        1.44        False
wrong diagnosis: 6 / 15

Three numbers side by side. The oracle: creating 30,000 files in a single directory is 449,985,000 comparisons in the sequential-list layout, 125,312 in the hashed layout, 59,800 in the tree layout. The tool’s output: all three directories give the same 30,000 names with ls, and the directory entry count is equal across all three; the internal layout is not in the output. Wrong diagnosis: an estimate measured on a small directory and scaled linearly deviates by more than double in six of fifteen cases.

There is no superiority in the table, only a difference in curves. At a thousand files, the tree layout is more expensive than the hashed layout (1800 against 1000); at a hundred thousand files, it is five times cheaper. The hashed layout also shows a limit of its own: because the bucket count is fixed at format time, the chains lengthen, and at 100,000 files the cost climbs to 12.71 times the linear estimate. Every number that gets fixed is a debt paid as the scale grows.

Reading With and Without a Checksum

The second axis is the correctness of a read. A block can corrupt itself on disk; even though it no longer holds what was written, the device returns it without error. If the design does not check for this, the corruption is silent: the application takes the wrong byte for the right one.

• ST11 — The shared definition’s /data file system carries 30,000 files, and every file holds one block. The inode table is 2048 blocks; 16 inodes fit in one block.
• ST12 — Reading a file touches two blocks: its own data block, and the table block where its inode sits.
• ST13 — 40 blocks get corrupted; which ones is chosen by the generator. A design that carries a checksum catches the corruption at read time; one that does not, does not.

"""Checksum: is a corrupted block caught during a read."""
SEED = 20260218
BLOCK = 4096
FILES = 30000                 # the shared definition's /data file system
INODES_PER_BLOCK = 16         # 16 inodes (256 bytes) fit in a 4096-byte block
META_BLOCKS = 2048            # a 32768-inode table, in blocks
CORRUPT = 40


def generator(seed):
    d = seed

    def next_value(n):
        nonlocal d
        d = (d * 1103515245 + 12345) % 2147483648
        return d % n
    return next_value


def corrupted(seed=SEED, count=CORRUPT, files=FILES, meta=META_BLOCKS):
    """Oracle: which blocks really got corrupted. The first `files` are data blocks."""
    r = generator(seed)
    return {r(files + meta) for _ in range(count)}


def reads(design, corrupt, files=FILES):
    """Every file reads its own data block and its block in the inode table."""
    data_checksum, meta_checksum = design
    caught = silent = 0
    for i in range(files):
        data_bad = i in corrupt
        meta_bad = (files + i // INODES_PER_BLOCK) in corrupt
        if (data_bad and data_checksum) or (meta_bad and meta_checksum):
            caught += 1
        elif data_bad or meta_bad:
            silent += 1
    return {"caught": caught, "silent": silent}


DESIGN = {"no checksum": (False, False), "meta checksum": (False, True),
          "data+meta checksum": (True, True)}
corrupt = corrupted()
print("corrupted blocks:", len(corrupt), "| data blocks:", sum(1 for x in corrupt if x < FILES),
      "| metadata blocks:", sum(1 for x in corrupt if x >= FILES))
print("oracle: reads touching a corrupted block:", reads((True, True), corrupt)["caught"],
      "/", FILES)
print()
print("design                 returns with error  returns corrupted silently  wrong diagnosis")
for name, t in DESIGN.items():
    o = reads(t, corrupt)
    print(f"  {name:20s} {o['caught']:13d}  {o['silent']:20d}  {o['silent']:11d}")
overhead = -(-(FILES + META_BLOCKS) * 4 // BLOCK)
print("checksum storage:", overhead, "blocks |", round(overhead / (FILES + META_BLOCKS) * 100, 3),
      "percent")
print()
for seed in (SEED, 20260219):
    c2 = corrupted(seed)
    print(f"seed {seed}: no checksum silent {reads((False, False), c2)['silent']:4d}"
          f"  meta checksum {reads((False, True), c2)['silent']:4d}"
          f"  full checksum {reads((True, True), c2)['silent']:4d}")

corrupted blocks: 40 | data blocks: 38 | metadata blocks: 2
oracle: reads touching a corrupted block: 54 / 30000

design                 returns with error  returns corrupted silently  wrong diagnosis
  no checksum                      0                    54           54
  meta checksum                   16                    38           38
  data+meta checksum              54                     0            0
checksum storage: 32 blocks | 0.1 percent

seed 20260218: no checksum silent   54  meta checksum   38  full checksum    0
seed 20260219: no checksum silent   70  meta checksum   38  full checksum    0

Three numbers side by side. The oracle: 40 blocks got corrupted, and the number of reads touching them is 54 — 38 files are affected through their own data block, 16 files through two corrupted table blocks. The tool’s output: in the design that carries no checksum, every read call returns without error; no tool reports anything. Wrong diagnosis: in that design, 54 reads take a corrupted byte for a correct one; this drops to 38 once a metadata checksum is added, and to zero once data is checksummed too.

The cost is in the table: the checksum for 32,048 blocks takes up 32 blocks, that is, 0.1 percent. The space cost is small; the processing cost is a computation added to every read, and this lesson does not count it. In the second seed, the corrupted-block distribution changes, the silent-read count comes out to 70 instead of 54; the ordering does not change. The number itself depends on the fiction, the gap from zero does not.

The real conclusion here is this: in a design with no checksum, a “no error” output does not mean “the data is correct.” Corruption only surfaces once a consistency check is run or once the data is used; both come after the read. The course’s third claim holds here too — one who looks late sees little.

A consistency check is not free either, and what it does must be watched. Tools of the fsck class walk the ledgers from end to end and look at whether they are mutually consistent; they leave repairing whatever inconsistency they find, and repair sometimes means moving a file into a directory where orphaned records are collected. This work cannot be done on a mounted file system: the file system must not change while the tool is running, or the tool invalidates the very ledger it is reading. This is why the repair command on a mounted file system is not given in a runnable, complete form; testing is done after the file system is unmounted, or with the report-only option.

What the check can find also has a limit. Inconsistency between ledgers is found; a data block’s content having changed is not found, because there is no record saying what the correct content was. What the checksum buys in the table is exactly this: a 32-block record that serves not to know what the correct content is, but to realize that it is wrong.

Summary

• A file system keeps a name ledger, a metadata ledger, a space ledger, and a consistency ledger in the same partition; the difference between families is how these four ledgers are kept, not a ranking of superiority.
• Creating 30,000 files in a single directory is 449,985,000 comparisons in the sequential-list layout, 125,312 in the hashed layout, 59,800 in the tree layout; all three directories give the same list with ls.
• An estimate measured on a small directory and scaled linearly deviates by more than double in six of fifteen cases; the bucket count being fixed at format time in the hashed layout overshoots the estimate by 12.71 times at 100,000 files.
• In a design carrying no checksum, all 54 of the reads that touch a corrupted block return without error; this becomes 38 with a metadata checksum, 0 with a data checksum. The storage cost is 32 blocks, 0.1 percent.
• Every number fixed at format time is a ceiling; the next lesson measures what hitting one of those ceilings looks like.

Next Step

This lesson counted the metadata ledger as a design axis but did not look inside it: the record itself, carrying everything about a file except its name, is a resource, and it can be exhausted. The next lesson measures that record and produces the course’s most striking number — in the same file system, a write fails while block usage sits at 0.0125. The disk is one percent full and the system is full; the diagnosis drawn from the usage percentage is flatly wrong here.