9.7.11 — In-Memory File System

"Design an in-memory file system. Support mkdir, creating and appending to files, reading them, and listing a directory."

This one is asked constantly because it looks like a data-structure exercise and is actually a modelling exercise. The candidates who treat it as "build a tree" produce something that works for the four operations named and falls apart on the first follow-up. The ones who ask what a path is, and what a name is, produce something that absorbs symbolic links, permissions and renames without changing shape.

1. The questions to ask first

Is this a real file system's semantics, or a simplified tree? It matters immediately. In a real file system a file's identity is separate from its name, which is what makes two names for the same file possible. If the interviewer wants that, the model changes in section 4. Ask.

What operations, beyond the four? Delete, move, search by pattern, permissions. Each adds a specific piece, and knowing which ones are in scope stops you building the wrong generality.

How big can a file get? If files are small, content is one string. If they can be gigabytes, content is a list of chunks and appending stops being O(n).

Concurrent access? Usually deferred, and worth naming as deferred rather than silently ignoring, because section 7 shows the interesting race is not where people expect.

State the contract: "I will build the tree, path resolution, and the five core operations, with content as chunks so appending stays cheap. I am deferring permissions and concurrent access unless you want them."

2. Classify it

A part-and-whole structure, which is the Composite pattern (9.4.11), plus a resolver that turns a string into a node. Almost every operation is resolve the path, then do something small at the end of it, so getting the resolver right is most of the work.

3. The tree

abstract class Node {                                      // (1)
  constructor(
    public name: string,                                   // (2) the name lives in the parent's map
    public parent: Directory | null,
    public readonly createdAt: Instant,
  ) {}
  abstract size(): number;                                 // (3) uniform over both kinds
}

class FileNode extends Node {
  #chunks: string[] = [];                                  // (4)
  #length = 0;

  append(text: string): void {
    this.#chunks.push(text);                               // (5) O(1), not O(n)
    this.#length += text.length;
  }

  read(): string { return this.#chunks.join(""); }
  override size(): number { return this.#length; }
}

class Directory extends Node {
  readonly children = new Map<string, Node>();             // (6) name → node

  override size(): number {
    let total = 0;
    for (const child of this.children.values()) total += child.size();   // (7) recursive
    return total;
  }
}

(1) One abstract type so a directory can hold either kind without caring which.

(2) The name is stored on the node and used as the key in the parent's map. Two copies of the same fact is a smell, and section 4 explains why real file systems remove it. For a simplified version this is acceptable as long as rename updates both, which is exactly the kind of thing that goes wrong.

(3) size() on both kinds is the Composite payoff: "how big is this thing" works on a file and on the whole tree with the same call.

(4) Content as a list of chunks rather than one string.

(5) This is why. Appending to a single string means copying the whole string every time, so writing a megabyte in a thousand appends copies half a gigabyte. Chunks make append O(1) and pay only on read. If reads are frequent, cache the joined result and invalidate on append.

(6) A Map from name to node gives O(1) lookup of one child, which is what path resolution does at every step. An array would make every step a scan.

(7) Directory size is the sum of its children, computed recursively. Mention that a directory with a million files makes this expensive, and that a real system caches it and updates on change — the classic space-for-time trade.

4. What a path actually is, and the modelling decision

Here is the follow-up that catches people: "add hard links, so the same file can appear under two names."

With the model above it is impossible. FileNode has a name and a single parent, so it lives in exactly one place by construction. Making it work means changing the model rather than adding a method.

Real file systems solved this by separating two things that look like one.

The file is content plus metadata — size, timestamps, permissions. It has an identity and no name.

The directory entry is a name in a directory pointing at a file. The name lives here.

Figure 1 — The name is not part of the file. Once the two are separate, hard links, atomic rename and "delete when the last name goes" all fall out for free.

class FileObject {                                          // (1) no name field
  #chunks: string[] = [];
  linkCount = 0;                                            // (2)
  permissions = Permissions.default();
  append(text: string): void { this.#chunks.push(text); }
}

class Directory {
  readonly entries = new Map<string, FileObject | Directory>();   // (3) the name lives here
}

(1) The file knows nothing about where it is or what it is called.

(2) A count of how many names point at it. unlink decrements; the content is released only when the count hits zero. This is why deleting a file in a real system is called unlink — you are removing a name, not destroying data, and if another name remains the file is untouched.

(3) The directory owns the name-to-object mapping.

Three things become easy that were impossible before. A hard link is a second entry pointing at the same object. A rename is removing one entry and adding another with no data moved at all, which is why renaming a ten-gigabyte file is instant. And "delete" has an obvious meaning even when the file is open — the name goes, the object survives while anybody holds it.

Whether you should build this depends on the interviewer's answer to question one. For a simple tree, the first model is right and simpler. For anything mentioning links, renames or open files, this is the model, and reaching it because you asked rather than because you were corrected is the difference.

5. Path resolution

Nearly every operation is "walk the path, then do one small thing", so this function is the spine.

function resolve(path: string, from: Directory, root: Directory): Node | null {
  const parts = path.split("/").filter(p => p.length > 0);          // (1)
  let current: Node = path.startsWith("/") ? root : from;           // (2)

  for (const part of parts) {
    if (part === ".") continue;                                     // (3)
    if (part === "..") {
      current = current.parent ?? root;                             // (4) .. at root is root
      continue;
    }
    if (!(current instanceof Directory)) return null;               // (5) can't descend into a file
    const next = current.entries.get(part);
    if (!next) return null;                                         // (6) missing
    current = next;
  }
  return current;
}

(1) Filtering empty parts handles // and a trailing slash without special cases.

(2) A leading slash means start at the root; otherwise start where you are.

(3) . is a no-op.

(4) .. goes up, and at the root it stays at the root — which is a real rule, not a shortcut, and it is what stops /../../.. escaping the tree.

(5) Descending into a file is an error, and returning null rather than throwing keeps it a normal outcome.

(6) A missing component is null. Note that callers need to distinguish "does not exist" from "exists but is the wrong kind", so a richer return type is worth mentioning.

Two things worth saying out loud about this function.

It is where a security bug would live. If paths from an untrusted source are resolved without the .. handling being correct, a request for ../../etc/passwd escapes the intended directory. This is path traversal, and the defence is to resolve first and then check the result is inside the allowed subtree — never to filter the string for .., which is defeated by encoding tricks.

Resolve once, then act. Every operation calls resolve for the parent and then does one map operation. Writing separate walking logic inside mkdir, rm and mv is how the three end up disagreeing about edge cases.

6. The operations

class FileSystem {
  #root = new Directory("", null);

  mkdirp(path: string): Directory {                                  // (1) create intermediate dirs
    let current = this.#root;
    for (const part of split(path)) {
      let next = current.entries.get(part);
      if (!next) { next = new Directory(part, current); current.entries.set(part, next); }
      if (!(next instanceof Directory)) throw new NotADirectory(part);   // (2)
      current = next;
    }
    return current;
  }

  append(path: string, text: string): void {
    const { parent, name } = this.#resolveParent(path);               // (3)
    let node = parent.entries.get(name);
    if (!node) { node = new FileObject(); parent.entries.set(name, node); node.linkCount = 1; }
    if (!(node instanceof FileObject)) throw new IsADirectory(path);
    node.append(text);
  }

  ls(path: string): string[] {
    const node = this.#resolve(path);
    if (node instanceof FileObject) return [basename(path)];          // (4) ls of a file
    return [...node.entries.keys()].sort();                           // (5)
  }

  unlink(path: string): void {
    const { parent, name } = this.#resolveParent(path);
    const node = parent.entries.get(name);
    if (!node) throw new NotFound(path);
    parent.entries.delete(name);                                      // (6) remove the NAME
    if (node instanceof FileObject && --node.linkCount === 0) {
      node.release();                                                 // (7) last name gone
    }
  }
}

(1) Creating intermediate directories is the useful default and matches how people expect it to work.

(2) If a path component exists and is a file, you cannot descend. Failing loudly here beats silently overwriting.

(3) Resolving the parent and keeping the final name is the shape every mutating operation needs, because you are about to modify the parent's map.

(4) Listing a file returns the file, which is what real shells do and which candidates usually forget.

(5) Sorted output, because a Map preserves insertion order and users expect alphabetical. Small detail, and interviewers notice it.

(6) Deletion removes the name. This line is the payoff of section 4's model.

(7) Only when the last name is gone does the content go. If a hard link remains, the file is untouched.

Move is the operation that proves the model.

mv(from: string, to: string): void {
  const src = this.#resolveParent(from);
  const dst = this.#resolveParent(to);
  const node = src.parent.entries.get(src.name);
  if (!node) throw new NotFound(from);
  if (this.#isAncestor(node, dst.parent)) throw new InvalidMove();   // (1)
  dst.parent.entries.set(dst.name, node);                            // (2)
  src.parent.entries.delete(src.name);
}

(1) The check nobody remembers: moving a directory into its own subtree detaches it from the tree entirely and creates a cycle. mv /a /a/b/c must fail, and the check is walking up from the destination looking for the source.

(2) No content moves. Renaming a huge file or a huge directory is two map operations, because names and data were separated.

7. Concurrency, if asked

The interesting races are not where people expect.

Two appends to the same file are the obvious one, and the fix is a lock per file object.

The real problem is a rename racing a resolution. A thread resolves /a/b/c step by step. Between resolving /a/b and looking up c, another thread moves /a/b somewhere else. The first thread is now operating inside a directory that is no longer where it thought it was. Real file systems solve this by resolving with a lock held per component, or by making rename take a lock that ordering guarantees cannot deadlock.

Rename is also the deadlock case. Moving /a/x to /b/y needs both directories locked, and a simultaneous move from /b to /a deadlocks unless the locks are taken in a fixed order. Sort by path or by an object id (9.5.3).

A directory lock is the right granularity, not one global lock and not one per node. Operations mutate a directory's map, so that is the unit of contention, and unrelated directories never wait for each other.

8. The twists, pre-walked

"Add symbolic links." A new node kind holding a path string rather than a reference. Resolution follows it by re-resolving from that path, which introduces two things worth naming: a symlink can point at something that does not exist (a dangling link, which is legal), and a cycle of symlinks must be detected with a depth limit or resolution loops forever. Plugs in as a node kind, with one change to the resolver.

"Add permissions." Permissions live on the file object, and every operation checks them at resolution time. The detail worth mentioning is that you need execute permission on every directory in the path, not just on the target — which is why the check belongs inside resolve rather than at the end.

"Support search: find every file matching a pattern." A depth-first walk with a matcher. The interesting part is what it costs — O(n) over the whole tree — and that a real system adds an index if search is frequent, which introduces the index-invalidation problem on every write.

"Add snapshots." This one restructures, and say so. A snapshot means the tree at a point in time, and copying it is impossible for a large tree. The technique is copy-on-write: the snapshot shares every node with the live tree, and a write copies just the nodes along the path from the root to the change. That makes nodes immutable, which is a genuine redesign rather than an addition — and it is exactly how modern file systems provide instant snapshots.

9. What the interviewer will push on

"Now support two names for the same file." The question that separates models. If your FileNode has a name and a parent, it cannot be done without a redesign. The answer is to separate the file object (content, metadata, link count) from the directory entry (the name). Then a hard link is a second entry, delete becomes unlink with a link-count decrement, and rename becomes free.

"What does mv cost for a ten-gigabyte file?" Two map operations, because names and data are separate and no content moves. Candidates whose model stores the name inside the file cannot answer this cleanly.

"How do you handle .. and .?" They are checking the resolver, and specifically that .. at the root stays at the root. Follow up by naming path traversal as the security consequence, and that the defence is to resolve and then check containment rather than filtering the string.

"Appending to a file a thousand times." They want to hear that a single string makes each append O(n) so the total is quadratic, and that chunks make it O(1) with the cost moved to read. Add the refinement: cache the joined value and invalidate on append, so repeated reads are cheap too.

"Move a directory into itself." The check almost nobody writes. mv /a /a/b detaches the subtree and creates a cycle, so you walk up from the destination looking for the source and refuse.

"Two threads, one renaming and one resolving." The race people miss, because they look for it in file content. A path resolved step by step can have a middle component moved underneath it. Naming this unprompted is a strong signal, and the fix is per-directory locks taken in a fixed order.

The thing to volunteer that nobody asks for: ls should return sorted names. A Map iterates in insertion order, so the naive implementation returns creation order, which looks correct in a demo and wrong to every user. It is a one-word fix and it is the kind of detail that says you have thought about the thing being used rather than the thing being built.

Next: 9.7.12 — the text editor, where the data structure you pick decides what undo costs.

Recall

• Composite tree: one abstract node, files and directories both answer size(). Directory holds a Map from name to node for O(1) lookup at each path step.
• Content as chunks, not one string — append becomes O(1) instead of O(n), so a thousand appends stop being quadratic. Cache the joined read and invalidate on append.
• The modelling decision: separate the file object (content, metadata, link count) from the directory entry (the name). Only then are hard links expressible, mv is free regardless of size, and delete becomes unlink — remove a name, release content when the count hits zero.
• One resolve function is the spine: . is a no-op, .. goes up and stays at the root, descending into a file fails. Every operation resolves the parent and keeps the final name.
• Path traversal lives here: resolve first, then check the result is inside the allowed subtree. Never filter the string for ...
• mv must reject moving a directory into its own subtree, or the tree detaches and cycles.
• Concurrency: lock per directory, not globally and not per node. The subtle race is a rename moving a middle path component while another thread is resolving through it. Sort lock order or rename deadlocks.
• Snapshots restructure: copy-on-write with immutable nodes, copying only the path from root to the change.

Self-test: Why can't a FileNode with a name field support hard links? What does mv cost and why? What happens to .. at the root, and what security bug lives nearby? Why chunks instead of a string? Which two-thread race do people miss?

Quiz Bank

FoundationalDesign the core classes, and explain the one decision that determines whether hard links are possible later.

The obvious model is an abstract Node with name and parent, subclassed by FileNode (holding content) and Directory (holding a Map from name to node). Both implement size(), so asking "how big is this" works on a single file and on an entire subtree — the Composite payoff (9.4.11).

That model is correct for the four operations usually named, and it contains one decision that quietly forecloses the most common follow-up.

The decision is where the name lives. In that model the file carries its own name and a single parent, which asserts that a file exists in exactly one place under exactly one name. When the interviewer asks for hard links — two names for the same file — the model cannot express it, and you are redesigning under time pressure.

The fix is to separate identity from naming, exactly as real file systems do.

A file object holds content, size, timestamps, permissions and a link count. It has no name and no parent; it does not know where it lives.

A directory holds a map from name to object. The name lives in the directory, not in the thing named.

What that buys, and each item answers a follow-up you are likely to get.

Hard links are simply a second entry in some directory pointing at the same object, with the link count incremented.

Rename is free. Removing one entry and adding another moves no content, which is why renaming a ten-gigabyte file is instant. In the naive model the file's own name field has to change too, and you now have the same fact stored twice.

Delete has a sensible meaning. You remove a name and decrement the count; the content is released only at zero. This is why the system call is called unlink. It also explains why a file that is still open survives deletion — a holder counts as a reference.

Permissions have an obvious home, on the object rather than on one of its names.

Which model to build depends on the answer to your first question, which is whether the interviewer wants real semantics or a simplified tree. For a simple tree the first model is right and simpler, and choosing it deliberately is fine. Being forced into the second model by a follow-up is what you are trying to avoid, and the way to avoid it is to ask at the start.

AppliedImplement path resolution properly and say what breaks if you get it wrong.

The function walks components and returns the node, and everything else in the file system calls it.

Split on / and drop empty parts, which handles // and trailing slashes with no special cases. Start at the root if the path begins with /, otherwise at the current directory. Then for each component: . is skipped, .. moves to the parent, anything else is a lookup in the current directory's map. Descending into a file is an error, and a missing component returns nothing.

The .. rule that matters: at the root, .. stays at the root. This is real behaviour, not a shortcut, and it is what stops /../../.. walking out of the tree. Implementing it as current = current.parent ?? root is the whole of it.

Resolve the parent, not the target, for anything that mutates. mkdir, append, unlink and mv all need to modify a directory's map, so the useful helper returns { parent, finalName }. Writing separate walking logic inside each operation is how they end up disagreeing about trailing slashes and about what happens when a middle component is a file.

What breaks if you get it wrong.

Path traversal, which is a security bug rather than a correctness one. If paths come from an untrusted source — an upload service, a template loader, an archive extractor — then mishandled .. lets a caller reach files outside the intended directory. This is one of the oldest vulnerabilities there is and it is still found regularly.

The defence is to resolve first and then check containment: after resolution, verify the resulting node is inside the allowed subtree by walking up its parents. Filtering the input string for .. is the instinctive fix and it is the wrong one, because encodings, mixed separators and unusual normalisations all defeat string filtering. Resolution followed by a containment check cannot be defeated that way, because it works on the resolved node rather than on the text.

Inconsistent edge-case behaviour. If mkdir and unlink each parse paths their own way, one will accept a trailing slash and the other will not, and users will find it.

A resolver that throws instead of returning nothing makes "does this exist" an exception-handling exercise for every caller, when it is an ordinary question with an ordinary answer.

And a refinement worth mentioning if symlinks come up: following them requires re-resolving from the link's target path, which means a symlink can point at something absent (a dangling link, which is legal) and a chain of symlinks can form a cycle. Real systems cap the number of links followed — typically around forty — and return an error beyond it, because there is no way to detect the cycle cheaply otherwise.

InterviewA file is appended to a thousand times, then read once. Analyse the cost, then change the design.

With content as a single string, appending is O(n) each time, because strings are immutable in most languages, so content = content + text allocates a new string and copies everything. Append k of length m each and the total copying is m + 2m + 3m + ... + km, which is O(k²m). A thousand appends of a kilobyte copies about half a gigabyte to produce a one-megabyte file.

That is the answer they are looking for, and the shape — quadratic from a loop that looks linear — is the general lesson.

With content as a list of chunks, append is a push: O(1), no copying. A thousand appends is a thousand pushes. The cost moves to read, which joins the chunks once at O(n).

For the stated pattern — a thousand appends and one read — that is a thousand cheap operations plus one linear join, instead of a thousand increasingly expensive copies. The improvement is a factor of roughly k.

The refinement for a different access pattern. If reads are frequent rather than rare, joining on every read is now the quadratic problem in reverse. So cache the joined string and invalidate the cache on append:

class FileObject {
  #chunks: string[] = [];
  #joined: string | null = null;

  append(text: string): void { this.#chunks.push(text); this.#joined = null; }
  read(): string {
    if (this.#joined === null) { this.#joined = this.#chunks.join(""); this.#chunks = [this.#joined]; }
    return this.#joined;
  }
}

Note that reading also compacts the chunk list into one element, so a read-append-read pattern does not re-join a thousand pieces every time. Now both orders of operation are efficient, and the only cost is a few lines and one nullable field.

Two extras worth volunteering.

Fixed-size blocks are what a real file system uses, because they allow writing at an offset in the middle without shifting anything, and they let unused space be reclaimed in units. Naming the difference — variable chunks are simple and append-friendly, fixed blocks support random writes — shows you know why the real design is different.

The same reasoning appears elsewhere in the book. Building a large string in a loop is quadratic in any language, which is why every language has a builder or a join. Recognising the shape rather than the specific case is what makes it useful.

StaffAdd snapshots: the user can capture the state of a directory tree at a moment and browse it later while the live tree keeps changing. Design it.

Say first that this restructures rather than plugs in, because it changes an assumption every other operation relies on: that a node can be modified in place.

Why the naive approach fails. Deep-copying the tree at snapshot time is O(n) in nodes and O(total size) in content, so snapshotting a large tree takes minutes and doubles the memory. Snapshots are meant to be instant and cheap, so this is not a slow version of the right answer — it is a different answer.

The technique is copy-on-write, and it rests on making nodes immutable.

A snapshot is nothing more than a reference to the current root node. Taking one is O(1): store the root pointer. At that instant the snapshot and the live tree are the same tree, sharing every node.

Then, when something changes, you do not modify a node. You create a new version of the changed node, and new versions of every node on the path from the root down to it, and produce a new root. Everything not on that path is shared between the old and new roots, unchanged.

Writing a file five levels deep in a million-node tree therefore allocates six new nodes — the file and its five ancestors — and shares the other 999,994. The snapshot still points at the old root and sees the old tree; the live system points at the new root and sees the change. Neither can observe the other.

What this costs, stated honestly.

Every write allocates path-length nodes, so writes are more expensive than in-place mutation. In practice path length is small — a depth of ten is a deep tree — so this is a constant factor rather than a scaling problem.

Memory is retained by snapshots. Nodes that the live tree has replaced are kept alive by any snapshot referencing them. A long-lived snapshot of a rapidly changing tree pins a growing amount of history, which is exactly why real systems make snapshot retention an explicit policy with expiry rather than keeping them forever.

Parent pointers become a problem. A node cannot hold a parent reference, because the same node is now shared by several trees with different ancestors. So paths must be resolved downward from a root, and any operation needing a parent must carry it along the walk. This is the change that ripples through the rest of the code, and it is the reason this is a restructure.

What it buys beyond snapshots, which is why the trade is usually worth it. Reads need no locking at all, because nodes never change — a reader holding a root pointer has a consistent view for as long as it likes, with no coordination. That removes most of section 7's concurrency problems as a side effect. Writes become a compare-and-swap on the root pointer, which is optimistic concurrency (9.5.2) rather than locking. And rollback is free: restoring a snapshot is assigning an old root pointer.

The operational features that follow naturally. Diffing two snapshots is a walk that skips any subtree where the two roots are the same object, so comparing a million-node tree with one small change touches only the changed path. That makes incremental backup and change detection nearly free, and it is the property that makes this design worth its cost in real systems rather than merely elegant.

Flashcards

FlashThe modelling decision

Separate the file object (content, metadata, link count) from the directory entry (the name). Only then are hard links possible, mv is free, and delete is unlink with a count decrement.

FlashContent as chunks

A single string makes a thousand appends quadratic. Chunks make append O(1) and move the cost to read. Cache the joined value and compact on read so both patterns are cheap.

Flashresolve()

. skipped · .. up, and at the root it stays at the root · descending into a file fails · missing component returns nothing. Mutating operations resolve the parent and keep the final name.

FlashPath traversal defence

Resolve first, then check the result is inside the allowed subtree. Never filter the input string for .. — encodings defeat it.

FlashThe mv check nobody writes

Moving a directory into its own subtree detaches it and creates a cycle. Walk up from the destination looking for the source and refuse.

FlashSnapshots

Copy-on-write with immutable nodes: a snapshot is a root pointer, a write copies only the path from root to the change. Costs parent pointers; buys lock-free reads and free diffing.