Code an in-memory file system

12 min read · last reviewed 2026-10-17

Open in the interactive app: practice, quiz, mock interview →

In one minute

An in-memory file system is a tree of named nodes with two kinds of node, files and directories. The Composite pattern gives both a common interface, and nearly every operation becomes "resolve a path to a node, then act on it".
Path resolution is the core algorithm. Normalise once (split on /, drop empty parts and ., pop on ..), then walk from the root, failing with a precise error at the first component that is missing or is a file.
Separate the name from the node. A directory maps names to child nodes; the node does not need to know its own name. That one decision makes rename cheap, makes hard links possible later, and mirrors how Unix splits directory entries from inodes.
mv is the operation that exposes weak designs: it must refuse to move a directory into its own subtree, must not clobber an existing target silently, and must look atomic to concurrent readers.
The shape is finding things fast in a hierarchy, plus contention when several threads mutate the same subtree. The same tree-with-paths design appears in configuration stores (ZooKeeper znodes, etcd key prefixes), URL routers, and cloud console resource hierarchies.

Requirements

Functional:

Absolute paths such as /home/ana/notes.txt. Support . and .. and tolerate repeated slashes.
mkdir creates a directory and any missing parents.
write creates or overwrites a file, with an append mode; the parent directory must already exist.
read returns a file's content; ls lists a directory's children in sorted order, or a file's own name.
rm removes a file or an empty directory, or a whole subtree when asked to recurse.
mv renames or moves a file or directory to a new full path.
du reports the total bytes under a path.

Non-functional:

Every operation costs O(depth) for resolution plus the work of the operation itself, independent of the total number of files.
Errors are specific and deterministic (no such path, not a directory, is a directory, directory not empty, already exists), because callers branch on them.
Safe under concurrent callers in one process.

Out of scope: persistence, permissions and owners, symbolic links, file handles with seek offsets, and quotas.

Entities and relationships

Node is the abstract component: anything that can live in a directory. It exposes size() and isDir().
File is a leaf. It holds content.
Directory is the composite. It holds a map from child name to node. Its size is the sum of its children.
Path is a value object: a list of normalised components. It is parsed once at the API boundary.
FileSystem is the facade with the public operations. It owns the root directory and the lock.
Metadata (created, modified, size) belongs on the node, not in the directory entry, so that two names pointing at one node (a hard link) agree on it.

Relationships: a directory is composed of its children; removing a directory removes them. The file system composes the root. A path does not reference nodes at all; it is resolved on every call, which is what keeps it valid across renames.

Class diagram

classDiagram
    class FileSystem {
      -root: Directory
      -lock: RWLock
      +mkdir(path) void
      +write(path, data, append) void
      +read(path) string
      +ls(path) string[]
      +rm(path, recursive) void
      +mv(src, dst) void
      +du(path) int
    }
    class Node {
      <<abstract>>
      +isDir() bool
      +size() int
    }
    class File {
      -content: string
      +append(data) void
    }
    class Directory {
      -children: Map~string, Node~
      +child(name) Node
      +attach(name, node) void
      +detach(name) Node
    }
    class Path {
      +parts: string[]
      +parent() Path
      +name() string
      +isPrefixOf(other) bool
    }
    FileSystem *-- Directory : root
    Node <|-- File
    Node <|-- Directory
    Directory "1" *-- "many" Node : children
    FileSystem ..> Path : parses

Key flows

mv /docs/a /docs/archive/a resolves both parents, checks for a cycle and an existing target, then detaches and reattaches the node under one write lock. No content is copied.

sequenceDiagram
    participant C as Caller
    participant F as FileSystem
    participant P as Path
    participant S as srcParent
    participant D as dstParent
    C->>F: mv("/docs/a", "/docs/archive/a")
    F->>P: normalise both paths
    F->>F: dst under src? no
    F->>F: write lock
    F->>S: child("a")
    S-->>F: node
    F->>D: child("a")?
    D-->>F: none
    F->>S: detach("a")
    F->>D: attach("a", node)
    F->>F: unlock
    F-->>C: ok

Design patterns used and why

Composite is the backbone. du, recursive rm and recursive copy all treat a file and a directory uniformly: a directory's size is the sum of its children's sizes, a file's size is its length. Without Composite, every recursive operation grows an if file ... else ... ladder, and adding a third node type (symlink) touches all of them. See Composite for the pattern itself.
Facade: FileSystem is the only public type. Callers never hold a Directory reference, which is what lets the lock protect everything and lets you change internals (a sorted map, a trie of path segments) without breaking callers.
Value object for paths. Normalisation is subtle (/a/./b//../c is /a/c), so do it in one place and test it hard. Error messages then quote the normalised path, which makes them stable.
Visitor or a plain recursive walk for reporting operations such as du, find and tree. With two node types, a recursive method on Node is clearer than a full Visitor; switch when operations multiply faster than node types. See Visitor.
Command and Memento become relevant if you add undo or snapshots: each mutation is a command with an inverse, or the tree is copied on write so old roots stay readable. The Design Version Control System lesson takes that idea further.

What not to put in the model: a parent pointer on every node unless you need upward walks, because it must be updated on every move and is easy to leave stale; and the node's own name, for the reasons above.

Concurrency and edge cases

Moving a directory into itself. mv /a /a/b/c would detach /a and attach it under its own descendant, creating a cycle that is unreachable from the root. Compare normalised components: if src is a prefix of dst, refuse. Compare components, not strings, or /ab looks like it is under /a.
Moving onto an existing name. Unix rename(2) silently replaces an existing file target. Interview designs usually refuse instead, and say so. Whatever you choose, never replace a non-empty directory.
Root. rm / and mv / /x must fail. .. at the root stays at the root, as on Unix.
A file in the middle of a path. mkdir /a/b when /a is a file must fail with "not a directory", not overwrite the file.
Writing to a directory path fails with "is a directory"; reading a directory likewise.
Concurrent readers and writers. The simplest correct design is one readers-writer lock for the whole tree: read, ls and du share it, mutations take it exclusively. It serialises writers, which is fine for an in-process tool. Per-directory locks scale better but turn mv into a two-lock operation that needs a global ordering (Linux takes a filesystem-wide rename mutex for cross-directory renames for exactly this reason) to avoid deadlock.
Very deep or very wide trees. Recursive du and rm -r can overflow the stack on pathological depth; use an explicit stack. A directory with a million entries makes sorted ls cost O(n log n) each call; keep children in a sorted structure if ls is hot.

Down the stack

Layer 1The contract

Every operation either succeeds completely or fails with one specific error and changes nothing. After mv(src, dst) returns, src does not resolve and dst resolves to the same node with the same content, and no reader ever sees both or neither. ls returns names in byte order. du equals the sum of content lengths of all files under the path at one instant. Resolution cost is proportional to path depth, not to the number of files.

Layer 2The mechanism

Linux splits the same ideas into objects you can name. A dentry (directory entry) maps a name in a parent to an inode; the inode holds size, timestamps, link count and the pointers to data. The dentry cache (dcache) is a hash table keyed by (parent dentry, name), so path walking is one hash lookup per component, mostly lock-free under RCU. rename(2) is atomic with respect to lookups: another process sees either the old name or the new one. Linux's own tmpfs is an in-memory file system built from exactly these pieces, with page-cache pages as file content. On disk, ext4 stores large directories as an HTree, a hashed B-tree of names, so lookup in a 100,000-entry directory stays a few block reads. Our design is the same shape in miniature: the directory map plays the dentry role, the node object plays the inode role.

Layer 3The machine

Each path component in the in-memory design costs one hash of a short string (a few ns) and one map probe, which is usually one or two cache misses at around 80 ns each from DRAM. A 6-level path resolves in well under a microsecond. Memory per entry is dominated by overhead: a Go map entry plus string header plus node struct is roughly 100 to 200 bytes before any content, so a million empty files cost on the order of 150 MB. An uncontended sync.RWMutex read lock costs tens of nanoseconds, but on many cores the shared reader counter becomes a contended cache line, which is why the kernel uses RCU for path walks instead of a reader lock.

Why it's built this way

Users think in paths, but paths are just names; the stable thing is the node. So directories map names to nodes and nodes do not store their names.
Because names live only in directories, rename is "remove one map entry, add another", O(1) and with no data copied, even for a directory holding gigabytes.
Cheap rename invites misuse (moving a directory under itself), so the cycle check is mandatory at the one place that changes structure.
Lookups vastly outnumber mutations, so reads share a lock (or, in the kernel, avoid locks with RCU), while structural changes serialise.
Recursive operations dominate the rest of the API, so the node hierarchy is a Composite and each recursion is written once.

Extensibility

Symbolic links: a third node type holding a target path. Resolution follows it with a hop limit (Linux uses 40) to break loops. Composite keeps du and rm working; only resolution changes.
Hard links: allow two directory entries to point at one node and add a link count on the node. rm decrements the count and frees the node at zero. This works only because names are not stored on nodes.
Permissions: add owner and mode bits to the node and check them during resolution (execute permission on every directory you traverse) and at the final node. The check sits in the facade, not scattered in callers.
Persistence: add a write-ahead log of mutations (mkdir, write, mv) and replay it at startup, or snapshot the tree periodically. The facade already funnels every mutation through one place, which is where the log hook goes.
Watchers: an Observer registry keyed by path prefix, notified after each mutation commits, outside the lock, so a slow watcher cannot stall writers.

Leadership lens

Build first: path normalisation and resolution with an exhaustive test table, then mv with the cycle check. Almost every bug in this design traces back to one of those two.
Ask in review: where are paths normalised; are names stored in one place only; what does mv do when the target exists; how is the cycle check done (components or strings); what is the locking story for cross-directory moves.
Decide early whether you are mimicking POSIX semantics exactly or choosing safer ones (refusing to overwrite on mv). Mixed semantics produce surprising bugs for callers who know Unix.
In an interview, write the resolver and Composite nodes in the first 15 minutes, then spend the rest on mv, errors and concurrency.

Check yourself

Why should a node not store its own name?
Show answer
Because the name belongs to the directory entry. Storing it in two places means rename must update both, and hard links (two names for one node) become impossible to represent correctly.
How do you detect that mv /a /a/b would create a cycle, and why compare components rather than strings?
Show answer
Check whether the source's components are a prefix of the destination's. A string prefix check wrongly treats /ab as inside /a.
Why is a whole-tree readers-writer lock acceptable here, and when would you abandon it?
Show answer
It is simple and correct, and in-process mutations are microseconds, so writers rarely wait long. Abandon it when many cores contend on the reader count or writers in unrelated subtrees block each other; then move to per-directory locks with a global order for renames, or to copy-on-write.
du on a directory and size() on a file share a signature. Which pattern makes that natural, and what does it save?
Show answer
Composite. Recursive operations are written once against Node, and adding a new node type does not require editing every caller.

Watch

Google Coding Interview Question, Leetcode 588 (WorkWithGoogler): the classic interview form of this problem, with the tree structure built step by step.
588. Design In-Memory File System (Programming Live with Larry): a live solve that shows where path handling trips people up.
Design In-Memory File System, Leetcode 588 in Python (Cracking FAANG): a compact Python implementation to compare with the practice solution.

Free resources

Overview of the Linux Virtual File System (kernel.org): how the kernel separates dentries from inodes and resolves paths, the real version of this design.
Files and Directories (OSTEP): a clear chapter on the file system API, hard links, rename and why names are separate from inodes.
File System Implementation (OSTEP): how directories and inodes are laid out on disk.
rename(2) manual page (man7.org): the exact atomicity and error semantics of the system call your mv imitates.
Composite pattern (Refactoring.Guru): the pattern that lets files and directories share one interface.
Inode (Wikipedia): background on inodes, link counts and what directory entries actually store.

Open in the interactive app: practice, quiz, mock interview →