LOW LEVEL DESIGN · MACHINE CODING · MEDIUM · 7 OF 42

Design an In-Memory File System: Low-Level Design in Java

An in-memory file system designed and coded: the Composite pattern with a sealed Node, Directory and File, path parsing with dot and dot-dot, mkdir -p, cd, pwd and ls, create, read and append, a session per terminal for the working directory, a small shell built with the Command pattern, a read-write lock, owner and others permissions as an extension, and a full Java 17 solution.

Patterns usedCompositeCommandVisitor

  1. 1
  2. 2
  3. 3
  4. 4
  5. 5
  6. 6
  7. 7
  8. 8
  9. 9
  10. 10
  11. 11
  12. 12
  13. 13
  14. 14
  15. 15
  16. 16
  17. 17
  18. 18
  19. 19
  20. 20
  21. 21
  22. 22
  23. 23
  24. 24
  25. 25
  26. 26
  27. 27
  28. 28
  29. 29
  30. 30
  31. 31
  32. 32
  33. 33
  34. 34
  35. 35
  36. 36
  37. 37
  38. 38
  39. 39
  40. 40
  41. 41
  42. 42
1 / 18

Press play to hear the narration, or step through at your own pace. The full Java code is below.

Full Java solution

One file, Java 17, 296 lines, with a small main() demo. Save it as FileSystem.java, then run javac FileSystem.java && java FileSystem.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.EnumSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.locks.ReentrantReadWriteLock;
import java.util.function.Supplier;

/** An in-memory file system: a composite tree, per-session working directory, a tiny shell, permissions. */
public final class FileSystem {

    // ---------- the composite ----------
    enum Perm { READ, WRITE }

    /** A node is a file or a directory. Both share a name, a parent, an owner and what others may do. */
    abstract static sealed class Node permits Directory, File {
        final String name;
        final Directory parent;
        final String owner;
        final Set<Perm> others;

        Node(String name, Directory parent, String owner, Set<Perm> others) {
            this.name = name;
            this.parent = parent;
            this.owner = owner;
            this.others = others.isEmpty() ? EnumSet.noneOf(Perm.class) : EnumSet.copyOf(others);
        }

        abstract long size();

        String path() {
            if (parent == null) return "/";
            String up = parent.path();
            return (up.equals("/") ? "" : up) + "/" + name;
        }

        boolean allows(String user, Perm p) { return user.equals(owner) || others.contains(p); }
    }

    static final class Directory extends Node {
        final Map<String, Node> children = new TreeMap<>(); // sorted, so ls is ordered for free

        Directory(String name, Directory parent, String owner, Set<Perm> others) {
            super(name, parent, owner, others);
        }

        long size() { return children.values().stream().mapToLong(Node::size).sum(); }
    }

    static final class File extends Node {
        final StringBuilder content = new StringBuilder();

        File(String name, Directory parent, String owner, Set<Perm> others) {
            super(name, parent, owner, others);
        }

        long size() { return content.length(); }
    }

    /** Each terminal has its own user and current directory; the tree is shared. */
    static final class Session {
        final String user;
        Directory cwd;

        Session(String user, Directory cwd) {
            this.user = user;
            this.cwd = cwd;
        }
    }

    static final class FsException extends RuntimeException {
        private static final long serialVersionUID = 1L;

        FsException(String msg) { super(msg); }
    }

    // ---------- the file system ----------
    private final Directory root = new Directory("", null, "root", EnumSet.of(Perm.READ, Perm.WRITE));
    private final ReentrantReadWriteLock rw = new ReentrantReadWriteLock();

    Session login(String user) { return new Session(user, root); }

    /** "a/./b/../c" from cwd or "/x/y" from root. Empty parts and "." are dropped, ".." stays. */
    static List<String> parts(String path) {
        List<String> out = new ArrayList<>();
        for (String p : path.split("/")) if (!p.isEmpty() && !p.equals(".")) out.add(p);
        return out;
    }

    private static FsException denied(Node n) { return new FsException("permission denied: " + n.path()); }

    private Directory start(Session s, String path) { return path.startsWith("/") ? root : s.cwd; }

    /** Walk to an existing node; every step but the last must be a directory. */
    private Node resolve(Session s, String path) {
        Node cur = start(s, path);
        for (String p : parts(path)) {
            if (!(cur instanceof Directory d)) throw new FsException("not a directory: " + cur.path());
            if (p.equals("..")) cur = d.parent == null ? d : d.parent;
            else {
                if (!d.allows(s.user, Perm.READ)) throw denied(d);
                cur = d.children.get(p);
                if (cur == null) throw new FsException("no such file or directory: " + path);
            }
        }
        return cur;
    }

    private Directory resolveDir(Session s, String path) {
        if (resolve(s, path) instanceof Directory d) return d;
        throw new FsException("not a directory: " + path);
    }

    private <T> T read(Supplier<T> op) {
        rw.readLock().lock();
        try { return op.get(); } finally { rw.readLock().unlock(); }
    }

    private <T> T write(Supplier<T> op) {
        rw.writeLock().lock();
        try { return op.get(); } finally { rw.writeLock().unlock(); }
    }

    /** mkdir, or mkdir -p when parents is true. */
    Directory mkdir(Session s, String path, boolean parents, Set<Perm> others) {
        return write(() -> {
            Directory cur = start(s, path);
            List<String> ps = parts(path);
            for (int i = 0; i < ps.size(); i++) {
                String p = ps.get(i);
                if (p.equals("..")) {
                    cur = cur.parent == null ? cur : cur.parent;
                    continue;
                }
                Node next = cur.children.get(p);
                boolean last = i == ps.size() - 1;
                if (next == null) {
                    if (!last && !parents) throw new FsException("no such directory: " + p + " (use -p)");
                    if (!cur.allows(s.user, Perm.WRITE)) throw denied(cur);
                    next = new Directory(p, cur, s.user, others);
                    cur.children.put(p, next);
                } else if (last && !parents) {
                    throw new FsException("already exists: " + next.path());
                }
                if (!(next instanceof Directory d)) throw new FsException("not a directory: " + next.path());
                cur = d;
            }
            return cur;
        });
    }

    void cd(Session s, String path) { s.cwd = read(() -> resolveDir(s, path)); }

    String pwd(Session s) { return read(() -> s.cwd.path()); }

    /** ls on a directory lists its children (directories end in /); ls on a file lists the file. */
    List<String> ls(Session s, String path) {
        return read(() -> {
            Node n = resolve(s, path);
            if (n instanceof File f) return List.of(f.name);
            Directory d = (Directory) n;
            if (!d.allows(s.user, Perm.READ)) throw denied(d);
            List<String> out = new ArrayList<>();
            for (Node c : d.children.values()) out.add(c instanceof Directory ? c.name + "/" : c.name);
            return out;
        });
    }

    /** Create the file if missing (its directory must exist), then overwrite or append. */
    long writeFile(Session s, String path, String text, boolean append, Set<Perm> others) {
        return write(() -> {
            List<String> ps = parts(path);
            if (ps.isEmpty()) throw new FsException("is a directory: /");
            String name = ps.get(ps.size() - 1);
            String parentPath = String.join("/", ps.subList(0, ps.size() - 1));
            String dirPath = (path.startsWith("/") ? "/" : "") + parentPath;
            Directory dir = resolveDir(s, dirPath);
            Node n = dir.children.get(name);
            if (n == null) {
                if (!dir.allows(s.user, Perm.WRITE)) throw denied(dir);
                n = new File(name, dir, s.user, others);
                dir.children.put(name, n);
            }
            if (!(n instanceof File f)) throw new FsException("is a directory: " + n.path());
            if (!f.allows(s.user, Perm.WRITE)) throw denied(f);
            if (!append) f.content.setLength(0);
            f.content.append(text);
            return f.size();
        });
    }

    String readFile(Session s, String path) {
        return read(() -> {
            if (!(resolve(s, path) instanceof File f)) throw new FsException("is a directory: " + path);
            if (!f.allows(s.user, Perm.READ)) throw denied(f);
            return f.content.toString();
        });
    }

    long du(Session s, String path) { return read(() -> resolve(s, path).size()); }

    // ---------- a tiny shell: the Command pattern ----------
    interface Command { String run(Session s, List<String> args); }

    private final Map<String, Command> commands = Map.of(
            "mkdir", (s, a) -> {
                boolean p = a.get(0).equals("-p");
                mkdir(s, a.get(p ? 1 : 0), p, EnumSet.of(Perm.READ));
                return "";
            },
            "cd", (s, a) -> { cd(s, a.isEmpty() ? "/" : a.get(0)); return ""; },
            "pwd", (s, a) -> pwd(s),
            "ls", (s, a) -> String.join("  ", ls(s, a.isEmpty() ? "." : a.get(0))),
            "write", (s, a) -> { writeFile(s, a.get(0), text(a), false, EnumSet.of(Perm.READ)); return ""; },
            "append", (s, a) -> { writeFile(s, a.get(0), text(a), true, EnumSet.of(Perm.READ)); return ""; },
            "cat", (s, a) -> readFile(s, a.get(0)),
            "du", (s, a) -> du(s, a.isEmpty() ? "." : a.get(0)) + " chars");

    private static String text(List<String> a) { return String.join(" ", a.subList(1, a.size())); }

    String exec(Session s, String line) {
        List<String> words = new ArrayList<>(Arrays.asList(line.trim().split("\\s+")));
        Command c = commands.get(words.remove(0));
        if (c == null) return "unknown command";
        try {
            return c.run(s, words);
        } catch (FsException e) {
            return "error: " + e.getMessage();
        }
    }

    // ---------- demo ----------
    static void check(boolean ok, String what) {
        if (!ok) throw new AssertionError(what);
    }

    public static void main(String[] args) throws InterruptedException {
        FileSystem fs = new FileSystem();
        Session admin = fs.login("admin");
        String[] script = {
            "mkdir -p /srv/app/logs", "mkdir /srv/app/conf", "mkdir /a/b", "cd /srv/app", "pwd",
            "write conf/app.yml port: 8080", "append conf/app.yml , debug: false", "cat conf/app.yml",
            "cd logs/../conf/.", "pwd", "ls /srv/app", "ls app.yml", "du /srv", "cd /srv/app/conf/app.yml",
        };
        for (String line : script) {
            String out = fs.exec(admin, line);
            System.out.println("$ " + line + (out.isEmpty() ? "" : "\n  " + out));
        }
        check(fs.pwd(admin).equals("/srv/app/conf"), "pwd after ..");
        check(fs.readFile(admin, "/srv/app/conf/app.yml").equals("port: 8080, debug: false"), "append");

        // Permissions: others may read the admin's files but not change them.
        Session guest = fs.login("guest");
        String seen = fs.exec(guest, "cat /srv/app/conf/app.yml");
        System.out.println("guest $ cat /srv/app/conf/app.yml\n  " + seen);
        String denied = fs.exec(guest, "append /srv/app/conf/app.yml , debug: true");
        System.out.println("guest $ append /srv/app/conf/app.yml ...\n  " + denied);
        check(denied.startsWith("error: permission denied"), "guest cannot write");
        check(guest.cwd == fs.root && admin.cwd != fs.root, "each session has its own cwd");

        // Eight threads build directories and append to one log at the same time.
        Session svc = fs.login("admin");
        fs.mkdir(svc, "/load", false, EnumSet.of(Perm.READ, Perm.WRITE));
        ExecutorService pool = Executors.newFixedThreadPool(8);
        CountDownLatch go = new CountDownLatch(1);
        for (int t = 0; t < 8; t++) {
            int id = t;
            pool.submit(() -> {
                try {
                    go.await();
                    Session me = fs.login("worker");
                    for (int i = 0; i < 100; i++) {
                        fs.mkdir(me, "/load/w" + id + "/batch" + (i % 10), true, EnumSet.of(Perm.READ));
                        fs.writeFile(me, "/load/all.log", "x", true, EnumSet.of(Perm.READ, Perm.WRITE));
                    }
                } catch (InterruptedException e) {
                    Thread.currentThread().interrupt();
                }
            });
        }
        go.countDown();
        pool.shutdown();
        check(pool.awaitTermination(5, TimeUnit.SECONDS), "pool finished");
        long logSize = fs.du(svc, "/load/all.log");
        int dirs = fs.ls(svc, "/load").size();
        System.out.println("race: 8 threads, log size " + logSize + ", entries in /load " + dirs);
        check(logSize == 800 && dirs == 9, "concurrent writes");
        System.out.println("all checks passed");
    }
}

Notes

Requirements

Fix the scope. Make a directory, or a whole chain of them with dash p. Change directory and print the working directory. List a path: a directory lists its children in sorted order, a file lists just itself. Write, append and read files. Paths can be absolute or relative and may contain dot and dot dot. Several users work at once, each with their own working directory. Permissions, remove and move are extensions.

Clarify the edge cases, because each one becomes a line of code. Making a directory whose parent is missing is an error, unless dash p is given. Dash p on a directory that already exists does nothing. Dot dot at the root stays at the root, as in a real shell. Writing to a missing file creates it, but its parent directory must exist. And changing directory into a file is an error that says not a directory.

Requirements
  • mkdir path, mkdir -p path
  • cd path, pwd
  • ls path: dir lists children,
  • a file lists itself
  • write, append, cat a file
  • absolute and relative paths
  • with . and ..
  • many users, each with a cwd
  • du: total size of a subtree
  • later: permissions, rm, mv
Clarify first
  • mkdir a/b when a is missing?
  • error, unless -p
  • mkdir -p on an existing dir?
  • fine, nothing to do
  • .. at the root?
  • stays at the root
  • write to a missing file?
  • create it; parent must exist
  • cd into a file?
  • error: not a directory

Entities

The entities. The file system owns one tree that starts at the root directory. Every entry in the tree is a node, and a node is either a directory or a file. A directory contains child nodes, so the tree is recursive. The current directory does not belong to the file system: it belongs to a session, one per terminal, along with the user name. That split is what lets two users stand in different directories of the same tree.

Composite

This is the Composite pattern: a directory and a file share one parent type, and a directory holds a collection of that same type. Callers can ask any node its size or its path without caring which kind it is. In Java seventeen the node class is sealed, so it permits exactly directory and file, and a pattern-matching instance-of tells them apart safely. Children sit in a tree map, so listing comes out sorted for free.

The payoff of Composite is recursion with no type checks. A directory's size is the sum of its children's sizes, and a file's size is its length, so du on any path is one call. The path goes the other way: each node keeps a pointer to its parent, and the path is the parent's path plus a slash and the name, stopping at the root. Keeping the parent pointer is also what makes dot dot and pwd cheap.

Composite with sealed types
abstract sealed class Node
    permits Directory, File {
  String name; Directory parent;
  abstract long size();
  String path() { ... }
}
final class Directory extends Node {
  Map<String, Node> children =
      new TreeMap<>(); }
final class File extends Node {
  StringBuilder content; }
Recursion both ways
// Directory: sum of children
long size() {
  return children.values().stream()
      .mapToLong(Node::size).sum();
}
// File
long size() { return content.length(); }

String path() {  // walk to the root
  if (parent == null) return "/";
  return parentPath + "/" + name; }

Path parsing

Path parsing is where most bugs hide, so keep it in one place. An absolute path starts at the root, and a relative one starts at the session's current directory. Split on slashes and drop empty parts, which handles double slashes and a trailing slash, and drop single dots. Then walk: dot dot moves to the parent, or stays at the root, and a name looks up a child. Every step except the last must be a directory, or we report not a directory.

resolve(session, path)
start = path starts with "/"
        ? root : session.cwd
for (p : split("/"), skip "" and ".")
  if (cur is not a Directory) error
  if (p == "..")
    cur = parent, or root at root
  else cur = children.get(p)
       missing: no such file

"logs/../conf/." from /srv/app
  is /srv/app/conf

Flow: mkdir -p

Making directories walks the parts the same way, but creates what is missing. Without dash p, only the last part may be new, so mkdir slash a slash b fails when a does not exist, with a hint to use dash p. With dash p, every missing part is created and an existing one is simply passed through. In both modes, a file sitting where a directory is needed is an error, never silently replaced.

mkdir(path, parents)
for each part:
  next = cur.children.get(part)
  missing and not last and not -p:
    error: use -p
  missing: create a Directory
  exists, last, not -p:
    error: already exists
  next is a File: not a directory
  cur = next

Flow: cd and pwd

Change directory resolves the path and insists the result is a directory, then stores that directory object in the session. Storing the node, not a string, means pwd is just the node's path, and relative paths start from a real object without parsing anything. Changing into a file fails with not a directory, and the session keeps its old working directory.

cd and pwd
void cd(Session s, String path) {
  s.cwd = resolveDir(s, path);
}
String pwd(Session s) {
  return s.cwd.path();
}

cd /srv/app/conf/app.yml
  error: not a directory

Flow: files

Files follow one flow. Resolve the parent directory from every part except the last, look up the name, and create an empty file if it is missing. If the name is a directory, refuse. Then either clear the content and write, or append. Reading resolves the path and returns the content. Listing a directory returns its children with a slash after directories, and listing a file returns just its own name, exactly as a real shell does.

writeFile(path, text, append)
dir = resolveDir(all parts but last)
n = dir.children.get(name)
if (n == null) create a File
if (n is a Directory) error
if (!append) content.setLength(0)
content.append(text)

ls on a file: just its name
ls on a dir: children, dirs end /

Command pattern

The shell uses the Command pattern. Each verb, make directory, change directory, list, write, append, read and disk usage, is a small object with one run method, stored in a map by name. Executing a line splits it into words, looks up the first word and runs it with the rest. A new verb is one more entry, not another branch in a growing switch. Errors are caught in one place and printed as error lines.

Shell commands
interface Command {
  String run(Session s, List<String> a);
}
Map<String, Command> commands = Map.of(
  "mkdir", (s, a) -> ...,
  "cd",    (s, a) -> ...,
  "cat",   (s, a) -> readFile(..));

exec(s, "cd /srv/app"):
  split, look up "cd", run it,
  errors become "error: ..."

Concurrency

Concurrency. The tree is shared, so one read-write lock guards it. Listing, reading, changing directory and computing sizes take the read lock and run in parallel. Making directories and writing files take the write lock. A session belongs to one terminal, so its working directory needs no lock. In the demo eight threads each make a hundred nested directories and append to one shared log, and the log ends up exactly eight hundred characters long.

One read-write lock
  • read lock: ls, cat, cd, pwd,
  • du, every resolve
  • write lock: mkdir, write,
  • append, later rm and mv
  • session: one per thread,
  • so cwd needs no lock
  • test: 8 threads x 100
  • mkdir -p + append to one log
  • log size 800, 9 entries

Extension: permissions

Permissions arrive as an extension. Each node records its owner and a set of what everyone else may do, read or write. The owner may do anything. Walking into a directory needs read, creating inside it needs write, and changing a file needs write on that file. In the demo a guest can read the admin's config file but appending to it fails with permission denied. Groups and execute bits are the same idea with more fields.

allows(user, perm)
boolean allows(String user, Perm p) {
  return user.equals(owner)
      || others.contains(p);
}
walk into a dir: needs READ
create in a dir: needs WRITE
write a file:    needs WRITE

guest cat app.yml: works
guest append: permission denied

Extensibility

Other extensions fit the same shape. Remove unlinks a node from its parent, and recursive remove is needed for a non-empty directory. Move unlinks and relinks, after checking that a directory is not being moved inside itself. Symbolic links become a third node kind added to the sealed list, with a hop limit so loops cannot hang the walk. Find is a visitor walking the composite with a predicate.

Extension points
  • rm: unlink from the parent;
  • rm -r on a non-empty dir
  • mv: unlink + relink, check the
  • target is not inside itself
  • symlinks: a third Node type,
  • limit hops to stop loops
  • find / visitor: walk the
  • composite with a predicate
  • big files: chunks, not one
  • StringBuilder

Testing

The full code is below the player. The demo drives the shell with a script: make nested directories with and without dash p, change directory with dot and dot dot, write and append a config file, list a directory and a file, total the sizes, and try to change into a file. A guest session reads but cannot write. Then eight threads build directories and append to one log at once, and the totals are asserted.

Run it
$ mkdir /a/b
  error: no such directory: a (use -p)
$ cd logs/../conf/.   then pwd
  /srv/app/conf
$ ls /srv/app
  conf/  logs/
$ du /srv          24 chars
guest $ append /srv/app/conf/app.yml
  error: permission denied
race: log size 800, entries 9
all checks passed

Follow-ups

Expect follow-ups. Why is the working directory in the session? Because two users must be able to stand in different places. Why not a lock per directory? It allows more parallel writes, but a move touches two directories, so you must lock them in a fixed order to avoid deadlock. Recursive listing is recursion on the composite. And to survive a restart, append every change to a journal and replay it on startup.

Follow-ups to expect
  • why is cwd not in FileSystem?
  • each user needs their own
  • lock per directory?
  • faster, but mv needs two
  • locks in a fixed order
  • ls -R or find?
  • recursion on the composite
  • paths with spaces?
  • a real tokenizer with quotes
  • persist it? a journal of ops

Say it like this

The short version. It is a composite: a sealed node is either a directory or a file, and a directory keeps child nodes in a sorted map, so size and listing are simple recursion. One resolver handles absolute and relative paths with dot and dot dot. The current directory lives in a session per user, not in the tree. Shell verbs are commands in a map, and a read-write lock lets readers share the tree.

In the interview
  • "Composite: a sealed Node is
  • a Directory or a File, and a
  • directory holds Nodes in a
  • TreeMap. One resolver handles
  • absolute, relative, . and ..
  • The cwd lives in a Session.
  • Shell verbs are Commands; a
  • read-write lock guards the tree."

Interview questions

Why is the Composite pattern a good fit for a file system?

A directory contains files and other directories, and callers want to treat both alike: ask for a size, a path, or list them. With a common Node type and a Directory that holds Nodes, size and search are plain recursion with no special cases for each level.

How do you resolve a path with . and ..?

Start at the root for an absolute path or at the session's current directory for a relative one. Split on slashes, drop empty parts and single dots, then walk: .. moves to the parent (or stays at the root) and a name looks up a child. Every step except the last must be a directory.

How does mkdir -p differ from plain mkdir?

Plain mkdir requires every parent to exist and fails if the target exists. With -p each missing part is created and existing directories are passed through. In both cases a file in the way is an error.

Where should the current working directory live?

In a Session object per user or terminal, not in the shared FileSystem. Two users can then work in different directories of the same tree, and the session needs no locking because one thread uses it.

Why keep children in a TreeMap rather than a HashMap?

ls must print names in sorted order. A TreeMap keeps them sorted on insert, so listing is a simple walk; a HashMap would need sorting on every ls. Lookups are O(log n), which is fine for directory sizes.

How do you make the file system safe for many users?

Guard the tree with a ReentrantReadWriteLock: ls, cat, cd, pwd and du take the read lock and run together, while mkdir, write and append take the write lock. A finer design locks per directory, but operations like mv then need two locks taken in a fixed order.

How would you add permissions?

Give each node an owner and a set of permissions for others. The owner may do anything; others need READ to walk into or read a node and WRITE to create inside a directory or change a file. Check on every step of the walk and before every change.

How would you implement mv safely?

Resolve source and target directory, refuse if the target is the source or inside it, refuse a name clash, then remove the node from the old parent and add it to the new one under a write lock, updating its parent pointer.