Design an In-Memory File System in Java (Low-Level Design)

A file system is a tree of named entries: directories contain entries, files hold data. Designing an in-memory one is a classic low-level design problem because it is the textbook case for the composite pattern: a directory and a file are both "nodes", and operations such as computing a size must work uniformly on a single file or a whole subtree.

In Java the composite is an interface with one implementation per node kind. Because the set of node kinds is closed, the interface is sealed, and tree-wide operations are switch expressions that the compiler checks for completeness. This article builds the file system that way. It uses the LLD interview framework and the modeling rules from modeling domains in Java.

Requirements

Functional

Absolute paths (/home/alice) and relative paths (docs/a.txt, ../b), with . and .. segments.
mkdir creates a directory. mkdirP creates all missing ancestors.
write creates or overwrites a file. cat reads it.
ls lists a directory in a stable order, showing the kind and size of each entry.
rm removes a file or an empty directory. Removing a non-empty directory requires an explicit recursive flag.
size of a directory is the total size of everything below it.
find returns the paths under a directory whose entries satisfy a caller-supplied predicate.
cd and pwd maintain a current directory.

Non-functional

Every failure is a typed error: not found, not a directory, is a directory, already exists, not empty, invalid name.
Output order is deterministic.
The root cannot be removed and .. at the root stays at the root.

Entities and class diagram

classDiagram
    class FileSystem {
        -root: DirNode
        -cwd: List~String~
        +mkdir(path)
        +write(path, content)
        +cat(path) String
        +ls(path) List~Entry~
        +rm(path, recursive)
        +size(path) long
        +find(path, predicate) List~String~
        +cd(path)
    }
    class Node {
        <<sealed interface>>
        +size() long
    }
    class FileNode {
        <<record>>
        content: String
    }
    class DirNode {
        -children: TreeMap~String,Node~
    }
    class Entry {
        <<record>>
        name: String
        kind: Kind
        size: long
    }
    class FsException {
        -reason: Reason
        -path: String
    }
    class Reason {
        <<enumeration>>
        NOT_FOUND
        NOT_A_DIRECTORY
        IS_A_DIRECTORY
        ALREADY_EXISTS
        NOT_EMPTY
        INVALID_NAME
        CANNOT_REMOVE_ROOT
    }
    FileSystem *-- DirNode : root
    Node <|.. FileNode
    Node <|.. DirNode
    DirNode o-- Node : children by name
    FileSystem ..> Entry : returns
    FileSystem ..> FsException : throws
    FsException --> Reason

There is no parent reference in Node. A child does not know its parent, and the file system finds nodes by walking down from the root along a list of names. The tree is therefore a plain one-directional object graph with no cycles (object graphs and references), and .. is handled by dropping the last name from the path before the walk starts.

API

Java

public final class FileSystem {
    public FileSystem();
    public void mkdir(String path);
    public void mkdirP(String path);
    public void write(String path, String content);
    public String cat(String path);
    public List<Entry> ls(String path);
    public void rm(String path, boolean recursive);
    public long size(String path);
    public List<String> find(String path, BiPredicate<String, Node> predicate);
    public void cd(String path);
    public String pwd();
}

Paths are String at the API and become a List<String> of validated names as soon as they enter the class. All navigation works on that list, never on the raw text.

Failures are reported with one unchecked exception, FsException, that carries a Reason enum and the path at fault. An unchecked exception keeps every signature free of throws clauses, and the enum lets a caller branch on the reason without parsing text. Errors in domain design compares this choice with sealed result types.

Design decisions

Composite as a sealed interface. Both node kinds answer the same questions, so they implement one interface. A file is a record, because it is a value. A directory is a class, because it is mutable and owns a sorted map of children.

Java

import java.nio.charset.StandardCharsets;
import java.util.Collections;
import java.util.Map;
import java.util.SortedMap;
import java.util.TreeMap;

sealed interface Node {
    /** A file's size is its content length in bytes. A directory's size is the sum of its children. */
    default long size() {
        return switch (this) {
            case FileNode f -> f.content().getBytes(StandardCharsets.UTF_8).length;
            case DirNode d -> d.children().values().stream().mapToLong(Node::size).sum();
        };
    }

    default int countFiles() {
        return switch (this) {
            case FileNode f -> 1;
            case DirNode d -> d.children().values().stream().mapToInt(Node::countFiles).sum();
        };
    }
}

record FileNode(String content) implements Node {}

final class DirNode implements Node {
    private final SortedMap<String, Node> children = new TreeMap<>();

    DirNode() {}

    DirNode(Map<String, Node> initial) {
        children.putAll(initial);
    }

    SortedMap<String, Node> children() {
        return Collections.unmodifiableSortedMap(children);
    }

    void put(String name, Node node) {
        children.put(name, node);
    }

    void remove(String name) {
        children.remove(name);
    }
}

public class Main {
    public static void main(String[] args) {
        var tree = new DirNode(Map.of(
            "readme.md", new FileNode("hello"),
            "src", new DirNode(Map.of(
                "Main.java", new FileNode("class A {}"),
                "empty", new DirNode()))));
        System.out.println("total size " + tree.size() + " bytes in " + tree.countFiles() + " files");
        for (var entry : tree.children().entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue().size() + " bytes");
        }
    }
}

Output

total size 15 bytes in 2 files
readme.md: 5 bytes
src: 10 bytes

size is the whole composite pattern in a few lines: a leaf answers directly, and a container asks its children and combines the answers. The same shape gives countFiles, find and rendering. This is the payoff of the composite: new tree-wide operations are new methods with a switch, not edits to every node class. DirNode hands out an unmodifiable view of its children, so only put and remove can change the tree.

The sealed interface keeps the set of node kinds honest. Suppose a symbolic link is added later. Every switch over Node that does not handle it stops compiling, and the compiler lists each place that needs a decision:

Java✗ does not compile

sealed interface Node {
    default long size() {
        return switch (this) {
            case FileNode f -> f.content().length();
            case DirNode d -> d.children().stream().mapToLong(Node::size).sum();
        };
    }
}

record FileNode(String content) implements Node {}

record DirNode(java.util.List<Node> children) implements Node {}

record Symlink(String target) implements Node {}

public class Main {
    public static void main(String[] args) {
        System.out.println(new FileNode("abc").size());
    }
}

Output

error: the switch expression does not cover all possible input values

With an open class hierarchy, a forgotten override for the new subclass compiles and misbehaves at runtime. Use a plain interface instead of a sealed one only when outside code must add node kinds, which a file system core does not need.

TreeMap for children. Directory listings must be in a stable order so that ls, find and tests are deterministic, and a TreeMap<String, Node> gives sorted order and O(log n) lookup by name. A HashMap has no defined iteration order and would need a sort on every listing.

Path resolution is a pure function. Turning "../b/./c" plus a current directory into a list of names involves no tree. Splitting it out makes it testable alone. The rules: a leading / starts at the root, otherwise start from the current directory; empty and . segments are ignored; .. removes the last name and does nothing at the root.

The checks below use plain assert statements. The checker runs Java with assertions enabled, so a failed assert stops the program with an error. No test library is needed.

Java

import java.util.ArrayList;
import java.util.List;

public class Main {
    static List<String> resolve(List<String> cwd, String path) {
        var out = new ArrayList<String>();
        if (!path.startsWith("/")) {
            out.addAll(cwd);
        }
        for (var seg : path.split("/", -1)) {
            switch (seg) {
                case "", "." -> { }
                case ".." -> {
                    if (!out.isEmpty()) {
                        out.removeLast();
                    }
                }
                default -> out.add(seg);
            }
        }
        return out;
    }

    public static void main(String[] args) {
        var cwd = List.of("home", "alice");

        assert resolve(cwd, "/tmp/x").equals(List.of("tmp", "x"));
        assert resolve(cwd, "/").isEmpty();
        System.out.println("absolute paths ignore the cwd");

        assert resolve(cwd, "docs/a.txt").equals(List.of("home", "alice", "docs", "a.txt"));
        assert resolve(cwd, "../bob/./x").equals(List.of("home", "bob", "x"));
        System.out.println("relative paths start at the cwd");

        assert resolve(cwd, "docs///./a//").equals(List.of("home", "alice", "docs", "a"));
        assert resolve(cwd, "//docs").equals(List.of("docs"));
        System.out.println("extra slashes and dots are ignored");

        assert resolve(List.of(), "../../..").isEmpty();
        assert resolve(cwd, "../../../../etc").equals(List.of("etc"));
        System.out.println("dot-dot at the root stays at the root");
    }
}

Output

absolute paths ignore the cwd
relative paths start at the cwd
extra slashes and dots are ignored
dot-dot at the root stays at the root

Errors say what is wrong and where. Each exception carries the offending path, so cat("/home/alice/todo.md/x") reports NOT_A_DIRECTORY /home/alice/todo.md and not a vague failure.

Validation at the boundary. A name is valid if it is non-empty, is not . or .., and contains no NUL character. Slashes cannot occur because the path is split on them. The check runs once, when a path is resolved, so the rest of the code deals only with valid names (encapsulation and invariants).

Descent without parent references. To modify a directory, the code walks from the root with a Node cur variable that is reassigned at each step. This replaces a parent reference: the variable only ever moves deeper into the tree, and each step checks with instanceof that the current node is a directory.

Full implementation

Java

import java.nio.charset.StandardCharsets;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Map;
import java.util.SortedMap;
import java.util.TreeMap;
import java.util.function.BiPredicate;
import java.util.function.Supplier;

enum Reason {
    NOT_FOUND, NOT_A_DIRECTORY, IS_A_DIRECTORY, ALREADY_EXISTS, NOT_EMPTY, INVALID_NAME, CANNOT_REMOVE_ROOT
}

final class FsException extends RuntimeException {
    private final Reason reason;
    private final String path;

    FsException(Reason reason, String path) {
        super(reason + " " + path);
        this.reason = reason;
        this.path = path;
    }

    Reason reason() {
        return reason;
    }

    String path() {
        return path;
    }
}

sealed interface Node {
    default long size() {
        return switch (this) {
            case FileNode f -> f.content().getBytes(StandardCharsets.UTF_8).length;
            case DirNode d -> d.children().values().stream().mapToLong(Node::size).sum();
        };
    }
}

record FileNode(String content) implements Node {}

final class DirNode implements Node {
    private final SortedMap<String, Node> children = new TreeMap<>();

    SortedMap<String, Node> children() {
        return Collections.unmodifiableSortedMap(children);
    }

    void put(String name, Node node) {
        children.put(name, node);
    }

    void remove(String name) {
        children.remove(name);
    }
}

enum Kind { FILE, DIR }

record Entry(String name, Kind kind, long size) {}

final class FileSystem {
    private final DirNode root = new DirNode();
    private List<String> cwd = List.of();

    private static String display(List<String> comps) {
        return "/" + String.join("/", comps);
    }

    private static boolean validName(String name) {
        return !name.isEmpty() && !name.equals(".") && !name.equals("..") && name.indexOf('\0') < 0;
    }

    private static Entry entry(String name, Node node) {
        var kind = node instanceof DirNode ? Kind.DIR : Kind.FILE;
        return new Entry(name, kind, node.size());
    }

    /** Turns text into a list of validated names, applying "." and ".." against the cwd. */
    private List<String> resolve(String path) {
        var out = new ArrayList<String>();
        if (!path.startsWith("/")) {
            out.addAll(cwd);
        }
        for (var seg : path.split("/", -1)) {
            switch (seg) {
                case "", "." -> { }
                case ".." -> {
                    if (!out.isEmpty()) {
                        out.removeLast();
                    }
                }
                default -> {
                    if (!validName(seg)) {
                        throw new FsException(Reason.INVALID_NAME, seg);
                    }
                    out.add(seg);
                }
            }
        }
        return out;
    }

    private Node node(List<String> comps) {
        Node cur = root;
        for (int i = 0; i < comps.size(); i++) {
            if (!(cur instanceof DirNode dir)) {
                throw new FsException(Reason.NOT_A_DIRECTORY, display(comps.subList(0, i)));
            }
            cur = dir.children().get(comps.get(i));
            if (cur == null) {
                throw new FsException(Reason.NOT_FOUND, display(comps.subList(0, i + 1)));
            }
        }
        return cur;
    }

    /** The directory at {@code comps}, for modification. */
    private DirNode dirAt(List<String> comps) {
        if (node(comps) instanceof DirNode dir) {
            return dir;
        }
        throw new FsException(Reason.NOT_A_DIRECTORY, display(comps));
    }

    public void mkdir(String path) {
        var comps = resolve(path);
        if (comps.isEmpty()) {
            throw new FsException(Reason.ALREADY_EXISTS, "/");
        }
        var name = comps.getLast();
        var parent = dirAt(comps.subList(0, comps.size() - 1));
        if (parent.children().containsKey(name)) {
            throw new FsException(Reason.ALREADY_EXISTS, display(comps));
        }
        parent.put(name, new DirNode());
    }

    /** Creates the directory and any missing ancestors. Existing directories are fine. */
    public void mkdirP(String path) {
        var comps = resolve(path);
        Node cur = root;
        for (int i = 0; i < comps.size(); i++) {
            if (!(cur instanceof DirNode dir)) {
                throw new FsException(Reason.NOT_A_DIRECTORY, display(comps.subList(0, i)));
            }
            Node next = dir.children().get(comps.get(i));
            if (next == null) {
                next = new DirNode();
                dir.put(comps.get(i), next);
            }
            cur = next;
        }
        if (!(cur instanceof DirNode)) {
            throw new FsException(Reason.NOT_A_DIRECTORY, display(comps));
        }
    }

    public void write(String path, String content) {
        var comps = resolve(path);
        if (comps.isEmpty()) {
            throw new FsException(Reason.IS_A_DIRECTORY, "/");
        }
        var name = comps.getLast();
        var parent = dirAt(comps.subList(0, comps.size() - 1));
        if (parent.children().get(name) instanceof DirNode) {
            throw new FsException(Reason.IS_A_DIRECTORY, display(comps));
        }
        parent.put(name, new FileNode(content));
    }

    public String cat(String path) {
        var comps = resolve(path);
        return switch (node(comps)) {
            case FileNode f -> f.content();
            case DirNode d -> throw new FsException(Reason.IS_A_DIRECTORY, display(comps));
        };
    }

    /** A directory lists its children in name order. A file lists itself. */
    public List<Entry> ls(String path) {
        var comps = resolve(path);
        return switch (node(comps)) {
            case DirNode d -> d.children().entrySet().stream()
                .map(e -> entry(e.getKey(), e.getValue()))
                .toList();
            case FileNode f -> List.of(entry(comps.getLast(), f));
        };
    }

    public long size(String path) {
        return node(resolve(path)).size();
    }

    public void rm(String path, boolean recursive) {
        var comps = resolve(path);
        if (comps.isEmpty()) {
            throw new FsException(Reason.CANNOT_REMOVE_ROOT, "/");
        }
        var name = comps.getLast();
        var parent = dirAt(comps.subList(0, comps.size() - 1));
        var target = parent.children().get(name);
        if (target == null) {
            throw new FsException(Reason.NOT_FOUND, display(comps));
        }
        if (target instanceof DirNode inner && !inner.children().isEmpty() && !recursive) {
            throw new FsException(Reason.NOT_EMPTY, display(comps));
        }
        parent.remove(name);
    }

    /** Absolute paths of every entry below {@code path} (not the path itself) that satisfies the predicate. */
    public List<String> find(String path, BiPredicate<String, Node> predicate) {
        var prefix = new ArrayList<>(resolve(path));
        var out = new ArrayList<String>();
        walkFind(node(prefix), prefix, predicate, out);
        return out;
    }

    private static void walkFind(Node node, List<String> prefix, BiPredicate<String, Node> predicate, List<String> out) {
        if (node instanceof DirNode dir) {
            for (var child : dir.children().entrySet()) {
                prefix.add(child.getKey());
                if (predicate.test(child.getKey(), child.getValue())) {
                    out.add(display(prefix));
                }
                walkFind(child.getValue(), prefix, predicate, out);
                prefix.removeLast();
            }
        }
    }

    public void cd(String path) {
        var comps = resolve(path);
        if (!(node(comps) instanceof DirNode)) {
            throw new FsException(Reason.NOT_A_DIRECTORY, display(comps));
        }
        cwd = List.copyOf(comps);
    }

    public String pwd() {
        return display(cwd);
    }

    /** An indented listing of the whole tree with sizes. */
    public String tree() {
        var out = new StringBuilder();
        walkTree("", root, 0, out);
        return out.toString();
    }

    private static void walkTree(String name, Node node, int depth, StringBuilder out) {
        var indent = "  ".repeat(depth);
        switch (node) {
            case FileNode f -> out.append("%s%s (%d B)\n".formatted(indent, name, f.size()));
            case DirNode d -> {
                out.append("%s%s/ (%d B)\n".formatted(indent, name, d.size()));
                for (var child : d.children().entrySet()) {
                    walkTree(child.getKey(), child.getValue(), depth + 1, out);
                }
            }
        }
    }
}

public class Main {
    static void ok(Runnable op) {
        try {
            op.run();
            System.out.println("Ok");
        } catch (FsException e) {
            System.out.println("Err(" + e.getMessage().replace("\0", "\\0") + ")");
        }
    }

    static void value(Supplier<?> op) {
        try {
            System.out.println("Ok(" + op.get() + ")");
        } catch (FsException e) {
            System.out.println("Err(" + e.getMessage().replace("\0", "\\0") + ")");
        }
    }

    public static void main(String[] args) {
        var fs = new FileSystem();
        fs.mkdirP("/home/alice/docs");
        fs.mkdir("/tmp");
        fs.write("/home/alice/docs/notes.txt", "buy milk\n");
        fs.write("/home/alice/todo.md", "- write\n- test\n");
        fs.write("/tmp/log.txt", "ok");

        System.out.print(fs.tree());
        System.out.println("ls /home/alice: " + fs.ls("/home/alice"));
        System.out.println("size /home = " + fs.size("/home") + ", size / = " + fs.size("/"));
        System.out.println("cat: " + fs.cat("/home/alice/todo.md").replace("\n", "\\n"));

        fs.cd("/home/alice");
        fs.write("docs/readme.md", "hi");
        System.out.println("pwd " + fs.pwd() + " | cat ../alice/./docs/readme.md = " + fs.cat("../alice/./docs/readme.md"));
        fs.cd("../../..");
        System.out.println("pwd after cd ../../.. = " + fs.pwd());

        System.out.println("find *.md: " + fs.find("/", (name, n) -> name.endsWith(".md")));
        System.out.println("find files over 5 B: " + fs.find("/home", (name, n) -> n instanceof FileNode && n.size() > 5));
        System.out.println("find dirs: " + fs.find("/", (name, n) -> n instanceof DirNode));

        System.out.print("cat missing: ");
        value(() -> fs.cat("/nope"));
        System.out.print("cat a dir: ");
        value(() -> fs.cat("/home"));
        System.out.print("mkdir existing: ");
        ok(() -> fs.mkdir("/home/alice"));
        System.out.print("below a file: ");
        ok(() -> fs.write("/home/alice/todo.md/x", "?"));
        System.out.print("bad name: ");
        ok(() -> fs.mkdir("/a/b\0c"));
        System.out.print("rm non-empty: ");
        ok(() -> fs.rm("/home", false));
        System.out.print("rm root: ");
        ok(() -> fs.rm("/", true));
        System.out.print("rm -r: ");
        ok(() -> fs.rm("/home", true));
        System.out.println("ls /: " + fs.ls("/").stream().map(Entry::name).toList());
    }
}

Output

/ (26 B)
  home/ (24 B)
    alice/ (24 B)
      docs/ (9 B)
        notes.txt (9 B)
      todo.md (15 B)
  tmp/ (2 B)
    log.txt (2 B)
ls /home/alice: [Entry[name=docs, kind=DIR, size=9], Entry[name=todo.md, kind=FILE, size=15]]
size /home = 24, size / = 26
cat: - write\n- test\n
pwd /home/alice | cat ../alice/./docs/readme.md = hi
pwd after cd ../../.. = /
find *.md: [/home/alice/docs/readme.md, /home/alice/todo.md]
find files over 5 B: [/home/alice/docs/notes.txt, /home/alice/todo.md]
find dirs: [/home, /home/alice, /home/alice/docs, /tmp]
cat missing: Err(NOT_FOUND /nope)
cat a dir: Err(IS_A_DIRECTORY /home)
mkdir existing: Err(ALREADY_EXISTS /home/alice)
below a file: Err(NOT_A_DIRECTORY /home/alice/todo.md)
bad name: Err(INVALID_NAME b\0c)
rm non-empty: Err(NOT_EMPTY /home)
rm root: Err(CANNOT_REMOVE_ROOT /)
rm -r: Ok
ls /: [tmp]

Compare the output with the rules. The tree is sorted by name because of TreeMap, and every directory's size includes everything below it. Relative paths and .. resolve against the current directory, and cd ../../.. from /home/alice stops at the root. The find predicate receives the entry name and the node, so one function serves name patterns, kind filters and size filters. Every failure is a distinct reason that names the path at fault, and rm of a non-empty directory succeeds only with the explicit flag.

Two details in the code are worth explaining in an interview. First, find implements the recursion with a helper method and a shared prefix list that is pushed and popped, which builds each path without allocating a new list for every entry. Second, node and mkdirP walk down with a reassigned Node cur variable and test each step with instanceof, so a path that runs through a file fails with NOT_A_DIRECTORY and the path of that file.

Extensions

Follow-up question	Answer
Move or rename (`mv`)	Remove the node from the old parent, then insert it into the new parent. Check first that the destination is not inside the source, or the subtree would vanish.
Copy a directory	Add a recursive `copy` that creates a new `DirNode` and copies each child. File records are immutable and can be shared between the copies.
Symbolic links	Add `record Symlink(List<String> target) implements Node` and resolve it during walking with a depth limit to catch loops. The compiler points at every `switch` that needs updating.
Permissions and owners	Wrap each node in a record with metadata, `record Inode(Meta meta, Node data)`, and check permissions in the walk.
Timestamps	Inject a `Clock`, as in design a key-value store with TTL, and store created and modified times in the metadata.
Large files	Store `byte[]` or chunks instead of `String`. Keep `size` derived, or cache it and update it on write.
Size of directories is slow	Cache aggregate sizes in each directory and update the ancestors on every write and remove, trading write cost for O(1) reads.
Glob patterns in `find`	The predicate takes a name, so a glob matcher is a lambda: `find(path, (n, node) -> glob.matches(n))`.
Concurrent access	Guard the file system with a `ReadWriteLock`: `ls`, `cat`, `size` and `find` take the read lock, mutations take the write lock. For finer granularity, lock per directory, and take locks in path order to avoid deadlock; see thread-safe components.
Undo of file operations	Represent operations as commands with inverses; see design a text editor with undo and redo.
Watch a directory for changes	Publish events on each mutation; see event bus and observers.

Summary

A file system is a composite: files are leaves, directories are containers, and both answer the same questions such as size and find. In Java, model the node as sealed interface Node with a FileNode record and a DirNode class that owns a TreeMap<String, Node>.
Operations over the tree are recursive switch expressions over the sealed interface. A new permitted type makes the compiler flag every switch that must handle it.
Use TreeMap for children so listings and search results are deterministic without extra sorting.
Keep no parent references. Resolve a path to a validated list of names first (handling ., .. and the root), then walk down from the root. Path resolution is a pure function that is easy to test.
To mutate a nested directory, descend with a reassigned Node variable and an instanceof check at each step rather than storing parent links.
Throw a typed exception that names the failing path and carries a Reason enum, and validate names once at the boundary.
find takes a BiPredicate<String, Node>, so name, kind and size searches share one traversal.