Design an in-memory file system

“Design an in-memory file system: create directories, write and read files, list a directory.” Then: “now add permissions”, or “how does rename work?”

A file system is how a computer organizes files: folders (called directories) that hold files and other directories, all reached by a path like /home/ana/notes. In this problem, it lives in memory, as objects. There are no disks.

Files and directories are both things in a tree, and a directory holds things. That shape is the Composite pattern, and it gives the first half of the answer. The interesting parts are around the tree. How a path like /home/ana/../ben/./notes becomes a walk through it. Why rename is cheap in a tree and expensive in a map. What stops a directory being moved inside itself. And how a permission on one directory can hide everything below it.

The framework

1. 01Answer
2. 02Scope
3. 03Build
4. 04Full design
5. 05Stress
6. 06Wrap up

The answer in one minute

If you only have a minute, this is the design. The rest of the page explains how we get here.

1. Files and directories share one type, Entry, and a directory holds entries. That’s the Composite pattern. A directory’s size is the sum of the sizes of whatever it holds.
2. No entry stores its full path. Each one stores only its name and its parent. A path is a walk from the root. So moving a directory changes one link, however much is inside it.
3. Paths are cleaned up once, before anything else. . and empty parts are dropped, .. steps back one name, and a path that doesn’t start with / is refused.
4. Every operation goes through one walk, and the walk checks permissions. Execute permission on a directory lets you pass through it. So one closed directory hides everything inside it.
5. One read-write lock guards the tree. Reads run together. Changes run one at a time, because a move reads one place and changes others.

We’ll build this in four stages, then share the tree between threads.

Scope it

Before drawing anything, we ask a few questions. Each answer changes a class. Anything that doesn’t, we assume and move on.

Interviewerminute 0

Design an in-memory file system.

What they are testing

Whether you scope it to a data structure problem before drawing anything. Disks, blocks and inodes are a different interview. Candidates who ask “in memory, so no blocks or caching?” spend their time on the tree and the operations.

Here are the questions that matter:

• In memory, or on a disk? In memory: a tree of objects. On a disk, it’s blocks and a journal, which is an operating systems course.
• Which operations? Make a directory, write, read, list, move, delete, and size.
• Relative paths, and a current directory? No. Every path starts at the root, with /.
• Permissions? Yes: an owner and everyone else, with read, write and execute.
• Several threads at once? Yes.

These answers give us one promise that matters more than the others: every operation costs the depth of the path, not the size of the file system. Moving a directory with a million files inside must be as cheap as moving one file. Three smaller promises come with it. The tree is always a tree: nothing is ever inside itself, and a name is a file or a directory, never both. A user can’t read, change or list what the permissions forbid, even by going around them. And many threads can use it at once without losing changes.

We leave out disks, links, and relative paths.

Go deeperThree more questions, and what each changes1 min

Question	We assume	If the answer were different
Links, hard or symbolic?	No	A hard link makes the tree a graph; a symlink is a file holding a path to follow
File content as text or bytes?	Text, replaced whole	Bytes with offsets add append and partial writes
Search by name?	No	A walk of the subtree, or an index from name to entries

Common mistake

Starting with inodes and blocks

Inodes, block allocation and free lists are how a disk file system stores bytes. In an in-memory design, they add classes without answering the questions this interview asks: how a path is followed, what rename costs, and how a permission check works.

Build it

We’ll build the design in four stages. Each stage adds only the classes that a new requirement needs. In each diagram, the new parts are outlined, and the colors show what each class does (the key is under every diagram).

Stage 1: A map from path to content

Interviewerminute 3

Start simple: write a file, read it back, list a directory. What’s your first version?

What they are testing

Whether you can see, and say, why a flat map breaks down: listing looks at everything, folders don’t really exist, and rename touches every file under the folder.

Start with the smallest thing that works: a map from each file’s full path to its content. Reading and writing a file are one lookup each. Listing a directory looks at every path that starts with the directory’s name, and keeps the next name along.

Stage 1: a map of paths

Scroll or pinch to zoom, drag to pan

• Color key
• Facade
• Entity
• Value object
• Enum
• Interface
• Implementation
• New in this step

JFileSystem.javaPyfile_system.pyC#FileSystem.csGofile_system.goTSfile-system.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

// Every file is a key in one map, from its full path to its content.
class FileSystem {
    private final Map<String, String> files = new HashMap<>();

    void write(String path, String content) { files.put(path, content); }

    String read(String path) { return files.get(path); }

    // Lists the names directly inside a folder.
    // flaw 1: scans every file in the system to answer for one folder.
    // flaw 2: a folder exists only while a file is inside it, so there are no empty folders, and
    // nothing stops "/a" being a file while "/a/b" is one too.
    // flaw 3: renaming a folder means rewriting the key of every file under it.
    // flaw 4: "/a//b" and "/a/./b" are different keys for the same file.
    List<String> ls(String dir) {
        String prefix = dir.endsWith("/") ? dir : dir + "/";
        Set<String> names = new TreeSet<>();
        for (String p : files.keySet()) {
            if (p.startsWith(prefix)) names.add(p.substring(prefix.length()).split("/")[0]);
        }
        return new ArrayList<>(names);
    }
}

It works, but it has four problems, and we leave them in on purpose. Listing one directory looks at every file in the system. A directory exists only while some file is inside it, so there are no empty directories, and nothing stops /a being a file while /a/b is a file too. Renaming /home/ana to /home/anna means rewriting the key of every file under it. And /a//b and /a/./b are different keys for the same file. Three of the four come from storing full paths, so the next stage stops storing them.

Stage 2: A tree of entries

Interviewerminute 6

Make directories real: they can be empty, they can be listed without a search, and a name is either a file or a directory. What are your classes now?

What they are testing

Whether you reach the Composite pattern: a shared Entry type for files and directories, and a directory that holds entries. They also watch where the path cleaning goes, and whether .. is handled or ignored.

A file system is a tree, so we model it as one. An Entry is anything in the tree. It has a name and a parent. A File is an entry with content. A Directory is an entry with children: a map from name to entry. The root is a directory with no parent.

A directory holds entries, and doesn’t care which kind. So a directory can hold files and directories alike, to any depth. That’s the Composite pattern: one interface for a single thing and for a group of things.

Stage 2: entries in a composite tree

Scroll or pinch to zoom, drag to pan

• Color key
• Facade
• Entity
• Value object
• Enum
• Interface
• Implementation
• New in this step

size() shows what the pattern buys. A file’s size is the length of its content. A directory’s size is the sum of its children’s sizes. It doesn’t need to know which children are files: each child answers for itself, and a directory’s answer asks its own children.

Every operation now starts the same way. First we parse the path into a list of names: split on /, drop empty parts and ., let .. remove the name before it, and refuse a path that doesn’t start with /. Then we resolve the names, by walking from the root, one child lookup per name. The cost is the depth of the path, not the number of files.

Stage 2: resolving /home/ana/../ben/./notes

Scroll or pinch to zoom, drag to pan

• Color key
• The node it returns

Errors are returned as values, not thrown. NOT_FOUND means a name is missing. NOT_A_DIRECTORY means the walk met a file where it needed a directory. IS_A_DIRECTORY means someone tried to read or write a directory. Operations that return something return an Outcome: the result, plus the value when it’s OK.

JFileSystem.javaPyfile_system.pyC#FileSystem.csGofile_system.goTSfile-system.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

enum Result { OK, NOT_FOUND, NOT_A_DIRECTORY, IS_A_DIRECTORY, ALREADY_EXISTS, INVALID_PATH }

// A result and, when it is OK, a value.
record Outcome<T>(Result result, T value) {
    static <T> Outcome<T> ok(T value) { return new Outcome<>(Result.OK, value); }
    static <T> Outcome<T> fail(Result result) { return new Outcome<>(result, null); }
    boolean failed() { return result != Result.OK; }
}

// The composite. A file and a directory are both entries, so code that walks the tree, like
// size(), asks each entry the same question and lets it answer for itself.
abstract class Entry {
    String name;
    Directory parent;  // null only for the root

    Entry(String name, Directory parent) {
        this.name = name;
        this.parent = parent;
    }

    abstract long size();
}

class File extends Entry {
    String content = "";

    File(String name, Directory parent) { super(name, parent); }

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

class Directory extends Entry {
    final SortedMap<String, Entry> children = new TreeMap<>();  // sorted, so listing needs no sort

    Directory(String name, Directory parent) { super(name, parent); }

    // A directory's size is its children's, whatever they are.
    long size() {
        long total = 0;
        for (Entry e : children.values()) total += e.size();
        return total;
    }
}

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

    // Creates a directory. With parents, missing directories on the way are created too, and an
    // existing directory is fine, like mkdir -p.
    Result mkdir(String path, boolean parents) {
        List<String> names = parse(path);
        if (names == null) return Result.INVALID_PATH;
        Directory dir = root;
        for (int i = 0; i < names.size(); i++) {
            boolean last = i == names.size() - 1;
            Entry next = dir.children.get(names.get(i));
            if (next == null) {
                if (!last && !parents) return Result.NOT_FOUND;
                Directory created = new Directory(names.get(i), dir);
                dir.children.put(created.name, created);
                dir = created;
            } else if (!(next instanceof Directory d)) {
                return Result.NOT_A_DIRECTORY;
            } else if (last && !parents) {
                return Result.ALREADY_EXISTS;
            } else {
                dir = d;
            }
        }
        return names.isEmpty() && !parents ? Result.ALREADY_EXISTS : Result.OK;
    }

    // Creates the file if it's missing, and replaces its content.
    Result write(String path, String content) {
        List<String> names = parse(path);
        if (names == null) return Result.INVALID_PATH;
        if (names.isEmpty()) return Result.IS_A_DIRECTORY;
        Outcome<Directory> parent = directory(names.subList(0, names.size() - 1));
        if (parent.failed()) return parent.result();
        String name = names.get(names.size() - 1);
        Entry existing = parent.value().children.get(name);
        if (existing instanceof Directory) return Result.IS_A_DIRECTORY;
        File file = existing == null ? new File(name, parent.value()) : (File) existing;
        file.content = content;
        parent.value().children.put(name, file);
        return Result.OK;
    }

    Outcome<String> read(String path) {
        Outcome<Entry> found = find(path);
        if (found.failed()) return Outcome.fail(found.result());
        if (!(found.value() instanceof File f)) return Outcome.fail(Result.IS_A_DIRECTORY);
        return Outcome.ok(f.content);
    }

    // A directory lists its children's names, in order; a file lists itself, as ls does.
    Outcome<List<String>> ls(String path) {
        Outcome<Entry> found = find(path);
        if (found.failed()) return Outcome.fail(found.result());
        if (found.value() instanceof Directory d) return Outcome.ok(List.copyOf(d.children.keySet()));
        return Outcome.ok(List.of(found.value().name));
    }

    Outcome<Long> size(String path) {
        Outcome<Entry> found = find(path);
        return found.failed() ? Outcome.fail(found.result()) : Outcome.ok(found.value().size());
    }

    private Outcome<Entry> find(String path) {
        List<String> names = parse(path);
        return names == null ? Outcome.fail(Result.INVALID_PATH) : resolve(names);
    }

    // Walks from the root, one name at a time. The cost is the path's depth, not the number of
    // files in the system.
    private Outcome<Entry> resolve(List<String> names) {
        Entry at = root;
        for (String name : names) {
            if (!(at instanceof Directory dir)) return Outcome.fail(Result.NOT_A_DIRECTORY);
            at = dir.children.get(name);
            if (at == null) return Outcome.fail(Result.NOT_FOUND);
        }
        return Outcome.ok(at);
    }

    private Outcome<Directory> directory(List<String> names) {
        Outcome<Entry> found = resolve(names);
        if (found.failed()) return Outcome.fail(found.result());
        if (!(found.value() instanceof Directory d)) return Outcome.fail(Result.NOT_A_DIRECTORY);
        return Outcome.ok(d);
    }

    // Turns "/a/./b//c/../d" into [a, b, d]. Every path is absolute, so a missing leading slash
    // is a mistake rather than something relative to guess about. ".." at the root stays there.
    static List<String> parse(String path) {
        if (!path.startsWith("/")) return null;
        List<String> names = new ArrayList<>();
        for (String part : path.split("/")) {
            if (part.isEmpty() || part.equals(".")) continue;
            if (!part.equals("..")) names.add(part);
            else if (!names.isEmpty()) names.remove(names.size() - 1);
        }
        return names;
    }
}

Common mistake

Storing the full path in every entry

It makes printing a path a simple field read, and it brings back stage 1’s rename problem: moving a directory must rewrite the path stored in everything below it. Store the name and the parent, and build a path by walking up when it’s needed, which is rare.

Go deeperCleaning up a path, one name at a time2 min

Let’s parse /home/ana/../ben/./notes by hand. We keep a list of names, and look at each part between slashes in turn.

1. The path starts with /, so it’s allowed. The list starts empty.
2. home is a normal name, so we add it. The list is [home].
3. ana is a normal name. The list is [home, ana].
4. .. means “go back one”. We remove the last name. The list is [home].
5. ben is a normal name. The list is [home, ben].
6. . means “stay here”, so we skip it.
7. notes is a normal name. The list is [home, ben, notes].

Now the walk: from the root, look up home, then ben inside it, then notes inside that. Three lookups, however many files the system holds.

Two small cases. .. at the root has nothing to remove, so it does nothing, just as cd .. at / stays at /. And // produces an empty part between the slashes, which we skip like ..

Why clean the path first, instead of following .. during the walk? Because then every operation gets the same simple list, and the walk only ever goes down. It also means .. works through a name that doesn’t exist: /home/nobody/../ben reaches /home/ben. Unix does the opposite and would refuse it. Either rule is fine, as long as you say which one you chose.

Stage 3: Move and delete

Interviewerminute 12

Add rename and move, and delete. What does moving a directory with a hundred thousand files in it cost?

What they are testing

Whether you see that a move only relinks one entry, so it costs the same for any size of directory. The red flag is missing the check that stops a directory being moved inside itself, which cuts it off from the root.

A move takes an entry out of its parent’s children, and puts it into the target directory’s children, under the new name. Rename is just a move within the same directory. Nothing below the entry stores a path, so everything inside comes along by itself. It’s one remove, one insert, and the entry’s name and parent updated.

Two checks keep the tree a tree. First, the new name must be free in the target directory. Second, a directory must not move inside itself. Moving /home/ana to /home/ana/backup/ana would make it its own ancestor, and no path from the root could reach it any more. To catch that, we walk up from the target directory to the root. If we meet the entry on the way, we refuse. The root itself can’t move.

Why walk up from the target, and not down through the entry? Walking up costs the target’s depth, usually a handful of steps. Walking down through everything inside the entry could mean millions of entries. Same answer, very different cost.

Stage 3: moving p from /home/ana to /home/ben

Scroll or pinch to zoom, drag to pan

• Color key
• The node that moves

Delete removes the entry’s name from its parent. A directory with anything in it is deleted only when the caller asks for a recursive delete, as rm -r does, so one mistyped path doesn’t take a whole subtree with it. Once the entry is unlinked, nothing points to it, and the garbage collector frees it and everything inside.

Stage 3: move and delete

Scroll or pinch to zoom, drag to pan

• Color key
• Facade
• Entity
• Value object
• Enum
• Interface
• Implementation
• New in this step

JFileSystem.javaPyfile_system.pyC#FileSystem.csGofile_system.goTSfile-system.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

enum Result { OK, NOT_FOUND, NOT_A_DIRECTORY, IS_A_DIRECTORY, ALREADY_EXISTS, NOT_EMPTY, INVALID_PATH, INVALID_MOVE }

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

    // Creates a directory. With parents, missing directories on the way are created too, and an
    // existing directory is fine, like mkdir -p.
    Result mkdir(String path, boolean parents) {
        List<String> names = parse(path);
        if (names == null) return Result.INVALID_PATH;
        Directory dir = root;
        for (int i = 0; i < names.size(); i++) {
            boolean last = i == names.size() - 1;
            Entry next = dir.children.get(names.get(i));
            if (next == null) {
                if (!last && !parents) return Result.NOT_FOUND;
                Directory created = new Directory(names.get(i), dir);
                dir.children.put(created.name, created);
                dir = created;
            } else if (!(next instanceof Directory d)) {
                return Result.NOT_A_DIRECTORY;
            } else if (last && !parents) {
                return Result.ALREADY_EXISTS;
            } else {
                dir = d;
            }
        }
        return names.isEmpty() && !parents ? Result.ALREADY_EXISTS : Result.OK;
    }

    // Creates the file if it's missing, and replaces its content.
    Result write(String path, String content) {
        List<String> names = parse(path);
        if (names == null) return Result.INVALID_PATH;
        if (names.isEmpty()) return Result.IS_A_DIRECTORY;
        Outcome<Directory> parent = directory(names.subList(0, names.size() - 1));
        if (parent.failed()) return parent.result();
        String name = names.get(names.size() - 1);
        Entry existing = parent.value().children.get(name);
        if (existing instanceof Directory) return Result.IS_A_DIRECTORY;
        File file = existing == null ? new File(name, parent.value()) : (File) existing;
        file.content = content;
        parent.value().children.put(name, file);
        return Result.OK;
    }

    Outcome<String> read(String path) {
        Outcome<Entry> found = find(path);
        if (found.failed()) return Outcome.fail(found.result());
        if (!(found.value() instanceof File f)) return Outcome.fail(Result.IS_A_DIRECTORY);
        return Outcome.ok(f.content);
    }

    // A directory lists its children's names, in order; a file lists itself, as ls does.
    Outcome<List<String>> ls(String path) {
        Outcome<Entry> found = find(path);
        if (found.failed()) return Outcome.fail(found.result());
        if (found.value() instanceof Directory d) return Outcome.ok(List.copyOf(d.children.keySet()));
        return Outcome.ok(List.of(found.value().name));
    }

    Outcome<Long> size(String path) {
        Outcome<Entry> found = find(path);
        return found.failed() ? Outcome.fail(found.result()) : Outcome.ok(found.value().size());
    }

    // Moves or renames an entry; to is its full new path. The subtree moves with it, because
    // only the entry's own parent and name change: nothing below it stores a path.
    Result move(String from, String to) {
        List<String> src = parse(from);
        List<String> dst = parse(to);
        if (src == null || dst == null) return Result.INVALID_PATH;
        if (src.isEmpty() || dst.isEmpty()) return Result.INVALID_MOVE;  // the root stays where it is
        Outcome<Entry> found = resolve(src);
        if (found.failed()) return found.result();
        Outcome<Directory> target = directory(dst.subList(0, dst.size() - 1));
        if (target.failed()) return target.result();
        String newName = dst.get(dst.size() - 1);
        if (target.value().children.containsKey(newName)) return Result.ALREADY_EXISTS;
        // A directory can't move inside itself, or it would be cut off from the root. Walking up
        // from the target to the root finds it if it's an ancestor.
        Entry entry = found.value();
        for (Directory d = target.value(); d != null; d = d.parent) {
            if (d == entry) return Result.INVALID_MOVE;
        }
        entry.parent.children.remove(entry.name);
        entry.name = newName;
        entry.parent = target.value();
        target.value().children.put(newName, entry);
        return Result.OK;
    }

    // A directory with anything in it is deleted only when asked to be recursive, like rm -r.
    // Unlinking it from its parent is enough: nothing else points into the subtree.
    Result delete(String path, boolean recursive) {
        List<String> names = parse(path);
        if (names == null || names.isEmpty()) return Result.INVALID_PATH;
        Outcome<Entry> found = resolve(names);
        if (found.failed()) return found.result();
        Entry entry = found.value();
        if (entry instanceof Directory d && !d.children.isEmpty() && !recursive) return Result.NOT_EMPTY;
        entry.parent.children.remove(entry.name);
        return Result.OK;
    }

    private Outcome<Entry> find(String path) {
        List<String> names = parse(path);
        return names == null ? Outcome.fail(Result.INVALID_PATH) : resolve(names);
    }

    // Walks from the root, one name at a time. The cost is the path's depth, not the number of
    // files in the system.
    private Outcome<Entry> resolve(List<String> names) {
        Entry at = root;
        for (String name : names) {
            if (!(at instanceof Directory dir)) return Outcome.fail(Result.NOT_A_DIRECTORY);
            at = dir.children.get(name);
            if (at == null) return Outcome.fail(Result.NOT_FOUND);
        }
        return Outcome.ok(at);
    }

    private Outcome<Directory> directory(List<String> names) {
        Outcome<Entry> found = resolve(names);
        if (found.failed()) return Outcome.fail(found.result());
        if (!(found.value() instanceof Directory d)) return Outcome.fail(Result.NOT_A_DIRECTORY);
        return Outcome.ok(d);
    }

    // Turns "/a/./b//c/../d" into [a, b, d]. Every path is absolute, so a missing leading slash
    // is a mistake rather than something relative to guess about. ".." at the root stays there.
    static List<String> parse(String path) {
        if (!path.startsWith("/")) return null;
        List<String> names = new ArrayList<>();
        for (String part : path.split("/")) {
            if (part.isEmpty() || part.equals(".")) continue;
            if (!part.equals("..")) names.add(part);
            else if (!names.isEmpty()) names.remove(names.size() - 1);
        }
        return names;
    }
}

Stage 4: Owners and permissions

Interviewerminute 17

Several users share the file system. Ana’s private notes shouldn’t be readable by Ben, and Ben shouldn’t be able to delete Ana’s files. How do you add that?

What they are testing

Whether the checks happen in one place, on the right entry for each operation, and whether you know that execute on a directory is what lets you pass through it. A design that only checks the final file lets Ben list a directory he was locked out of.

Every entry gets an owner and a Mode: three permission bits for the owner, and three for everyone else, as in Unix without groups. Read is 4, write is 2 and execute is 1, so 7 is all three, 6 is read and write, and 5 is read and execute. New directories get 7 for the owner and 5 for others. New files get 6 and 4. Every call now says which user makes it, and the superuser, root, passes every check.

On a file, the bits mean what they say. On a directory, they mean something more specific, and this is the part to get right:

Bit on a directory	Lets you	Checked by
Read	List its names	ls
Write	Add, remove or rename names in it	mkdir, creating a file, move, delete
Execute	Pass through it to anything inside	every walk, at every directory on the path

So deleting a file needs write on its directory, not on the file, because delete changes the directory’s list of names. And a directory with no execute for others (mode 7 and 0) hides everything inside it, however open the files themselves are. The walk stops at the door.

Stage 4: Ben reads /home/ana/private/diary

Scroll or pinch to zoom, drag to pan

• Color key
• Where the check fails
• The error returned

Moving needs write on both the directory it leaves and the one it enters. chmod (change the mode) is for the owner or root, and chown (change the owner) is for root only, so nobody can hand a file to someone else.

All the checks go through one method, can(user, entry, access), and the walk in resolve checks execute on each directory it passes. Every operation uses that one walk, so no operation can reach an entry without passing the same doors.

Go deeperFollowing Ben's walk to Ana's diary1 min

Ana’s private directory has mode 7 and 0: everything for Ana, nothing for anyone else. Inside it, her diary has mode 6 and 4, so others may read it. Ben asks to read /home/ana/private/diary.

1. The walk starts at the root. Ben has execute on / (others have 5), so he may pass.
2. home has mode 7 and 5. Execute for others, so he passes.
3. ana has mode 7 and 5. He passes.
4. private has mode 7 and 0. No execute for others. The walk stops here with PERMISSION_DENIED, and never looks inside.

The diary’s own bits were never checked, because Ben never reached it. That’s the point of checking execute at every door: the owner of a directory controls everything below it, without having to change the mode of every file inside.

Stage 4: owners and modes

Scroll or pinch to zoom, drag to pan

• Color key
• Facade
• Entity
• Value object
• Enum
• Interface
• Implementation
• New in this step

JFileSystem.javaPyfile_system.pyC#FileSystem.csGofile_system.goTSfile-system.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

// What a call gets back. Errors are values, as a shell prints them, not exceptions.
enum Result {
    OK, NOT_FOUND, NOT_A_DIRECTORY, IS_A_DIRECTORY, ALREADY_EXISTS, NOT_EMPTY, INVALID_PATH, INVALID_MOVE,
    PERMISSION_DENIED
}

// Who may do what with an entry: read, write and execute bits for the owner and for everyone
// else, as in Unix without groups. 7 is all three, 6 is read and write, 5 is read and execute.
// On a directory, read lets you list it, write lets you add and remove names in it, and execute
// lets you pass through it on the way to something inside.
record Mode(int owner, int others) {
    static final int READ = 4, WRITE = 2, EXECUTE = 1;

    boolean allows(boolean isOwner, int access) { return ((isOwner ? owner : others) & access) == access; }
}

// The composite. A file and a directory are both entries, so code that walks the tree, like
// size(), asks each entry the same question and lets it answer for itself.
abstract class Entry {
    String name;
    Directory parent;
    String owner;
    Mode mode;

    Entry(String name, Directory parent, String owner, Mode mode) {
        this.name = name;
        this.parent = parent;
        this.owner = owner;
        this.mode = mode;
    }

    abstract long size();
}

// A file holds text. New files start as rw-r--r--: the owner reads and writes, others read.
class File extends Entry {
    String content = "";

    File(String name, Directory parent, String owner) { super(name, parent, owner, new Mode(6, 4)); }

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

// A directory holds named entries. New ones start as rwxr-xr-x. The map is sorted, so ls lists
// names in order with no extra work.
class Directory extends Entry {
    final SortedMap<String, Entry> children = new TreeMap<>();

    Directory(String name, Directory parent, String owner) { super(name, parent, owner, new Mode(7, 5)); }

    long size() {
        long total = 0;
        for (Entry e : children.values()) total += e.size();
        return total;
    }
}

// Every call names the user making it. New entries belong to that user. The superuser, root,
// passes every check.
class FileSystem {
    static final String ROOT = "root";
    private final Directory root = new Directory("", null, ROOT);

    // Walks the path one name at a time. With parents (like mkdir -p) missing directories on the
    // way are created, and an existing one is fine.
    Result mkdir(String user, String path, boolean parents) {
        List<String> names = parse(path);
        if (names == null) return Result.INVALID_PATH;
        Directory dir = root;
        for (int i = 0; i < names.size(); i++) {
            if (!can(user, dir, Mode.EXECUTE)) return Result.PERMISSION_DENIED;
            boolean last = i == names.size() - 1;
            Entry next = dir.children.get(names.get(i));
            if (next == null) {
                if (!last && !parents) return Result.NOT_FOUND;
                if (!can(user, dir, Mode.WRITE)) return Result.PERMISSION_DENIED;
                Directory created = new Directory(names.get(i), dir, user);
                dir.children.put(created.name, created);
                dir = created;
            } else if (!(next instanceof Directory d)) {
                return Result.NOT_A_DIRECTORY;
            } else if (last && !parents) {
                return Result.ALREADY_EXISTS;
            } else {
                dir = d;
            }
        }
        return names.isEmpty() && !parents ? Result.ALREADY_EXISTS : Result.OK;
    }

    // Changing a file's content needs write on the file; creating one needs write on its directory.
    Result write(String user, String path, String content) {
        List<String> names = parse(path);
        if (names == null) return Result.INVALID_PATH;
        if (names.isEmpty()) return Result.IS_A_DIRECTORY;
        Outcome<Directory> parent = directory(user, names.subList(0, names.size() - 1));
        if (parent.failed()) return parent.result();
        String name = names.get(names.size() - 1);
        Entry existing = parent.value().children.get(name);
        if (existing instanceof Directory) return Result.IS_A_DIRECTORY;
        if (!can(user, existing == null ? parent.value() : existing, Mode.WRITE)) return Result.PERMISSION_DENIED;
        File file = existing == null ? new File(name, parent.value(), user) : (File) existing;
        file.content = content;
        parent.value().children.put(name, file);
        return Result.OK;
    }

    Outcome<String> read(String user, String path) {
        Outcome<Entry> found = find(user, path);
        if (found.failed()) return Outcome.fail(found.result());
        if (!(found.value() instanceof File f)) return Outcome.fail(Result.IS_A_DIRECTORY);
        if (!can(user, f, Mode.READ)) return Outcome.fail(Result.PERMISSION_DENIED);
        return Outcome.ok(f.content);
    }

    // A directory lists its children. A file lists just its own name, as ls does.
    Outcome<List<String>> ls(String user, String path) {
        Outcome<Entry> found = find(user, path);
        if (found.failed()) return Outcome.fail(found.result());
        if (!(found.value() instanceof Directory d)) return Outcome.ok(List.of(found.value().name));
        if (!can(user, d, Mode.READ)) return Outcome.fail(Result.PERMISSION_DENIED);
        return Outcome.ok(List.copyOf(d.children.keySet()));
    }

    // Only needs to reach the entry. A stricter version would also need read on every directory
    // it adds up, as du does.
    Outcome<Long> size(String user, String path) {
        Outcome<Entry> found = find(user, path);
        return found.failed() ? Outcome.fail(found.result()) : Outcome.ok(found.value().size());
    }

    // Taking a name out of one directory and putting it in another changes both, so both need
    // write. The entry's own mode doesn't matter, as in Unix.
    Result move(String user, String from, String to) {
        List<String> src = parse(from);
        List<String> dst = parse(to);
        if (src == null || dst == null) return Result.INVALID_PATH;
        if (src.isEmpty() || dst.isEmpty()) return Result.INVALID_MOVE;
        Outcome<Entry> found = resolve(user, src);
        if (found.failed()) return found.result();
        Outcome<Directory> target = directory(user, dst.subList(0, dst.size() - 1));
        if (target.failed()) return target.result();
        Entry entry = found.value();
        if (!can(user, entry.parent, Mode.WRITE) || !can(user, target.value(), Mode.WRITE)) {
            return Result.PERMISSION_DENIED;
        }
        String newName = dst.get(dst.size() - 1);
        if (target.value().children.containsKey(newName)) return Result.ALREADY_EXISTS;
        // A directory can't move inside itself: walk up from the target and make sure we never meet it.
        for (Directory d = target.value(); d != null; d = d.parent) {
            if (d == entry) return Result.INVALID_MOVE;
        }
        entry.parent.children.remove(entry.name);
        entry.name = newName;
        entry.parent = target.value();
        target.value().children.put(newName, entry);
        return Result.OK;
    }

    // Needs write on the directory the name is removed from. Unix also needs write on every
    // directory inside a recursive delete; this version doesn't check below the top.
    Result delete(String user, String path, boolean recursive) {
        List<String> names = parse(path);
        if (names == null || names.isEmpty()) return Result.INVALID_PATH;
        Outcome<Entry> found = resolve(user, names);
        if (found.failed()) return found.result();
        Entry entry = found.value();
        if (!can(user, entry.parent, Mode.WRITE)) return Result.PERMISSION_DENIED;
        if (entry instanceof Directory d && !d.children.isEmpty() && !recursive) return Result.NOT_EMPTY;
        entry.parent.children.remove(entry.name);
        return Result.OK;
    }

    // Only the owner, or root, changes an entry's mode.
    Result chmod(String user, String path, Mode mode) {
        Outcome<Entry> found = find(user, path);
        if (found.failed()) return found.result();
        if (!user.equals(ROOT) && !user.equals(found.value().owner)) return Result.PERMISSION_DENIED;
        found.value().mode = mode;
        return Result.OK;
    }

    // Only root gives an entry away, so nobody can push a file onto someone else.
    Result chown(String user, String path, String owner) {
        Outcome<Entry> found = find(user, path);
        if (found.failed()) return found.result();
        if (!user.equals(ROOT)) return Result.PERMISSION_DENIED;
        found.value().owner = owner;
        return Result.OK;
    }

    // The one permission check. Root passes; everyone else gets the owner bits or the others bits.
    private boolean can(String user, Entry entry, int access) {
        return user.equals(ROOT) || entry.mode.allows(user.equals(entry.owner), access);
    }

    private Outcome<Entry> find(String user, String path) {
        List<String> names = parse(path);
        return names == null ? Outcome.fail(Result.INVALID_PATH) : resolve(user, names);
    }

    // Passing through a directory needs execute on it, so a directory with no execute for
    // others hides everything inside, however open the files themselves are.
    private Outcome<Entry> resolve(String user, List<String> names) {
        Entry at = root;
        for (String name : names) {
            if (!(at instanceof Directory dir)) return Outcome.fail(Result.NOT_A_DIRECTORY);
            if (!can(user, dir, Mode.EXECUTE)) return Outcome.fail(Result.PERMISSION_DENIED);
            at = dir.children.get(name);
            if (at == null) return Outcome.fail(Result.NOT_FOUND);
        }
        return Outcome.ok(at);
    }

    // Like resolve, but the entry must be a directory: where a new name is about to go.
    private Outcome<Directory> directory(String user, List<String> names) {
        Outcome<Entry> found = resolve(user, names);
        if (found.failed()) return Outcome.fail(found.result());
        if (!(found.value() instanceof Directory d)) return Outcome.fail(Result.NOT_A_DIRECTORY);
        return Outcome.ok(d);
    }

    // Turns "/a/./b/../c" into [a, c]. Only absolute paths are accepted; ".." at the top stays at
    // the top, as in Unix. Returns null for a path that isn't absolute.
    static List<String> parse(String path) {
        if (!path.startsWith("/")) return null;
        List<String> names = new ArrayList<>();
        for (String part : path.split("/")) {
            if (part.isEmpty() || part.equals(".")) continue;
            if (!part.equals("..")) names.add(part);
            else if (!names.isEmpty()) names.remove(names.size() - 1);
        }
        return names;
    }
}

Go deeperMode bits, or an access list per entry1 min

	Owner and others bits (our choice)	An access control list per entry
What it can say	Two classes of user	Any user or group, any right
Size per entry	Two small numbers	A list that can grow
Cost of a check	A bit mask	A search through the list
Familiar to readers	Yes, it’s chmod 750	Yes, it’s Windows and cloud storage

Bits are enough to show the design. An access control list could replace Mode behind the same can method, which is the point of having one method for every check.

This is enough for a mid-level answer. A composite tree, paths cleaned up and walked, move as a relink with the inside-itself check, and permissions checked. The rest of the page is what makes it a senior answer.

The full design

Here is everything together. FileSystem is what callers use, and it does every walk and every check. SharedFileSystem wraps it with a lock for many threads. The tree itself is Directory and File, both kinds of Entry.

File system: full class diagram

Scroll or pinch to zoom, drag to pan

• Color key
• Facade
• Entity
• Value object
• Enum
• Interface
• Implementation

</>file-system· read only

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

Explorer

• JAllInOne.java
• src
• JDirectory.java
• JEntry.java
• JFile.java
• JFileSystem.java
• JMode.java
• JOutcome.java
• JResult.java
• JSharedFileSystem.java

JAllInOne.java

AllInOne.javasrc/Directory.javasrc/Entry.javasrc/File.javasrc/FileSystem.javasrc/Mode.javasrc/Outcome.javasrc/Result.javasrc/SharedFileSystem.java

AllInOne.java

// The complete design, built from every stage on this page.

import java.util.*;
import java.util.concurrent.locks.*;
import java.util.function.*;

// Every call names the user making it. New entries belong to that user. The superuser, root,
// passes every check.
class FileSystem {
    static final String ROOT = "root";
    private final Directory root = new Directory("", null, ROOT);

    // Walks the path one name at a time. With parents (like mkdir -p) missing directories on the
    // way are created, and an existing one is fine.
    Result mkdir(String user, String path, boolean parents) {
        List<String> names = parse(path);
        if (names == null) return Result.INVALID_PATH;
        Directory dir = root;
        for (int i = 0; i < names.size(); i++) {
            if (!can(user, dir, Mode.EXECUTE)) return Result.PERMISSION_DENIED;
            boolean last = i == names.size() - 1;
            Entry next = dir.children.get(names.get(i));
            if (next == null) {
                if (!last && !parents) return Result.NOT_FOUND;
                if (!can(user, dir, Mode.WRITE)) return Result.PERMISSION_DENIED;
                Directory created = new Directory(names.get(i), dir, user);
                dir.children.put(created.name, created);
                dir = created;
            } else if (!(next instanceof Directory d)) {
                return Result.NOT_A_DIRECTORY;
            } else if (last && !parents) {
                return Result.ALREADY_EXISTS;
            } else {
                dir = d;
            }
        }
        return names.isEmpty() && !parents ? Result.ALREADY_EXISTS : Result.OK;
    }

    // Changing a file's content needs write on the file; creating one needs write on its directory.
    Result write(String user, String path, String content) {
        List<String> names = parse(path);
        if (names == null) return Result.INVALID_PATH;
        if (names.isEmpty()) return Result.IS_A_DIRECTORY;
        Outcome<Directory> parent = directory(user, names.subList(0, names.size() - 1));
        if (parent.failed()) return parent.result();
        String name = names.get(names.size() - 1);
        Entry existing = parent.value().children.get(name);
        if (existing instanceof Directory) return Result.IS_A_DIRECTORY;
        if (!can(user, existing == null ? parent.value() : existing, Mode.WRITE)) return Result.PERMISSION_DENIED;
        File file = existing == null ? new File(name, parent.value(), user) : (File) existing;
        file.content = content;
        parent.value().children.put(name, file);
        return Result.OK;
    }

    Outcome<String> read(String user, String path) {
        Outcome<Entry> found = find(user, path);
        if (found.failed()) return Outcome.fail(found.result());
        if (!(found.value() instanceof File f)) return Outcome.fail(Result.IS_A_DIRECTORY);
        if (!can(user, f, Mode.READ)) return Outcome.fail(Result.PERMISSION_DENIED);
        return Outcome.ok(f.content);
    }

    // A directory lists its children. A file lists just its own name, as ls does.
    Outcome<List<String>> ls(String user, String path) {
        Outcome<Entry> found = find(user, path);
        if (found.failed()) return Outcome.fail(found.result());
        if (!(found.value() instanceof Directory d)) return Outcome.ok(List.of(found.value().name));
        if (!can(user, d, Mode.READ)) return Outcome.fail(Result.PERMISSION_DENIED);
        return Outcome.ok(List.copyOf(d.children.keySet()));
    }

    // Only needs to reach the entry. A stricter version would also need read on every directory
    // it adds up, as du does.
    Outcome<Long> size(String user, String path) {
        Outcome<Entry> found = find(user, path);
        return found.failed() ? Outcome.fail(found.result()) : Outcome.ok(found.value().size());
    }

    // Taking a name out of one directory and putting it in another changes both, so both need
    // write. The entry's own mode doesn't matter, as in Unix.
    Result move(String user, String from, String to) {
        List<String> src = parse(from);
        List<String> dst = parse(to);
        if (src == null || dst == null) return Result.INVALID_PATH;
        if (src.isEmpty() || dst.isEmpty()) return Result.INVALID_MOVE;
        Outcome<Entry> found = resolve(user, src);
        if (found.failed()) return found.result();
        Outcome<Directory> target = directory(user, dst.subList(0, dst.size() - 1));
        if (target.failed()) return target.result();
        Entry entry = found.value();
        if (!can(user, entry.parent, Mode.WRITE) || !can(user, target.value(), Mode.WRITE)) {
            return Result.PERMISSION_DENIED;
        }
        String newName = dst.get(dst.size() - 1);
        if (target.value().children.containsKey(newName)) return Result.ALREADY_EXISTS;
        // A directory can't move inside itself: walk up from the target and make sure we never meet it.
        for (Directory d = target.value(); d != null; d = d.parent) {
            if (d == entry) return Result.INVALID_MOVE;
        }
        entry.parent.children.remove(entry.name);
        entry.name = newName;
        entry.parent = target.value();
        target.value().children.put(newName, entry);
        return Result.OK;
    }

    // Needs write on the directory the name is removed from. Unix also needs write on every
    // directory inside a recursive delete; this version doesn't check below the top.
    Result delete(String user, String path, boolean recursive) {
        List<String> names = parse(path);
        if (names == null || names.isEmpty()) return Result.INVALID_PATH;
        Outcome<Entry> found = resolve(user, names);
        if (found.failed()) return found.result();
        Entry entry = found.value();
        if (!can(user, entry.parent, Mode.WRITE)) return Result.PERMISSION_DENIED;
        if (entry instanceof Directory d && !d.children.isEmpty() && !recursive) return Result.NOT_EMPTY;
        entry.parent.children.remove(entry.name);
        return Result.OK;
    }

    // Only the owner, or root, changes an entry's mode.
    Result chmod(String user, String path, Mode mode) {
        Outcome<Entry> found = find(user, path);
        if (found.failed()) return found.result();
        if (!user.equals(ROOT) && !user.equals(found.value().owner)) return Result.PERMISSION_DENIED;
        found.value().mode = mode;
        return Result.OK;
    }

    // Only root gives an entry away, so nobody can push a file onto someone else.
    Result chown(String user, String path, String owner) {
        Outcome<Entry> found = find(user, path);
        if (found.failed()) return found.result();
        if (!user.equals(ROOT)) return Result.PERMISSION_DENIED;
        found.value().owner = owner;
        return Result.OK;
    }

    // The one permission check. Root passes; everyone else gets the owner bits or the others bits.
    private boolean can(String user, Entry entry, int access) {
        return user.equals(ROOT) || entry.mode.allows(user.equals(entry.owner), access);
    }

    private Outcome<Entry> find(String user, String path) {
        List<String> names = parse(path);
        return names == null ? Outcome.fail(Result.INVALID_PATH) : resolve(user, names);
    }

    // Passing through a directory needs execute on it, so a directory with no execute for
    // others hides everything inside, however open the files themselves are.
    private Outcome<Entry> resolve(String user, List<String> names) {
        Entry at = root;
        for (String name : names) {
            if (!(at instanceof Directory dir)) return Outcome.fail(Result.NOT_A_DIRECTORY);
            if (!can(user, dir, Mode.EXECUTE)) return Outcome.fail(Result.PERMISSION_DENIED);
            at = dir.children.get(name);
            if (at == null) return Outcome.fail(Result.NOT_FOUND);
        }
        return Outcome.ok(at);
    }

    // Like resolve, but the entry must be a directory: where a new name is about to go.
    private Outcome<Directory> directory(String user, List<String> names) {
        Outcome<Entry> found = resolve(user, names);
        if (found.failed()) return Outcome.fail(found.result());
        if (!(found.value() instanceof Directory d)) return Outcome.fail(Result.NOT_A_DIRECTORY);
        return Outcome.ok(d);
    }

    // Turns "/a/./b/../c" into [a, c]. Only absolute paths are accepted; ".." at the top stays at
    // the top, as in Unix. Returns null for a path that isn't absolute.
    static List<String> parse(String path) {
        if (!path.startsWith("/")) return null;
        List<String> names = new ArrayList<>();
        for (String part : path.split("/")) {
            if (part.isEmpty() || part.equals(".")) continue;
            if (!part.equals("..")) names.add(part);
            else if (!names.isEmpty()) names.remove(names.size() - 1);
        }
        return names;
    }
}

// What a call gets back. Errors are values, as a shell prints them, not exceptions.
enum Result {
    OK, NOT_FOUND, NOT_A_DIRECTORY, IS_A_DIRECTORY, ALREADY_EXISTS, NOT_EMPTY, INVALID_PATH, INVALID_MOVE,
    PERMISSION_DENIED
}

// A result and, when it is OK, a value.
record Outcome<T>(Result result, T value) {
    static <T> Outcome<T> ok(T value) { return new Outcome<>(Result.OK, value); }
    static <T> Outcome<T> fail(Result result) { return new Outcome<>(result, null); }
    boolean failed() { return result != Result.OK; }
}

// The composite. A file and a directory are both entries, so code that walks the tree, like
// size(), asks each entry the same question and lets it answer for itself.
abstract class Entry {
    String name;
    Directory parent;
    String owner;
    Mode mode;

    Entry(String name, Directory parent, String owner, Mode mode) {
        this.name = name;
        this.parent = parent;
        this.owner = owner;
        this.mode = mode;
    }

    abstract long size();
}

// A file holds text. New files start as rw-r--r--: the owner reads and writes, others read.
class File extends Entry {
    String content = "";

    File(String name, Directory parent, String owner) { super(name, parent, owner, new Mode(6, 4)); }

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

// A directory holds named entries. New ones start as rwxr-xr-x. The map is sorted, so ls lists
// names in order with no extra work.
class Directory extends Entry {
    final SortedMap<String, Entry> children = new TreeMap<>();

    Directory(String name, Directory parent, String owner) { super(name, parent, owner, new Mode(7, 5)); }

    long size() {
        long total = 0;
        for (Entry e : children.values()) total += e.size();
        return total;
    }
}

// Who may do what with an entry: read, write and execute bits for the owner and for everyone
// else, as in Unix without groups. 7 is all three, 6 is read and write, 5 is read and execute.
// On a directory, read lets you list it, write lets you add and remove names in it, and execute
// lets you pass through it on the way to something inside.
record Mode(int owner, int others) {
    static final int READ = 4, WRITE = 2, EXECUTE = 1;

    boolean allows(boolean isOwner, int access) { return ((isOwner ? owner : others) & access) == access; }
}

// One read-write lock for the whole tree. Reads (read, ls, size) share it, so they run in
// parallel; anything that changes the tree takes it alone. A move touches two directories and
// checks every ancestor of the target, so a lock per directory would need a fixed order to
// avoid deadlock, and a walk that takes and drops locks down the path. One lock is correct by
// construction, and an in-memory tree operation takes microseconds, so it is rarely the
// bottleneck.
class SharedFileSystem {
    private final FileSystem fs;
    private final ReadWriteLock lock = new ReentrantReadWriteLock();

    SharedFileSystem(FileSystem fs) { this.fs = fs; }

    Result mkdir(String user, String path, boolean parents) { return writing(() -> fs.mkdir(user, path, parents)); }

    Result write(String user, String path, String content) { return writing(() -> fs.write(user, path, content)); }

    Result move(String user, String from, String to) { return writing(() -> fs.move(user, from, to)); }

    Result delete(String user, String path, boolean recursive) { return writing(() -> fs.delete(user, path, recursive)); }

    Result chmod(String user, String path, Mode mode) { return writing(() -> fs.chmod(user, path, mode)); }

    Outcome<String> read(String user, String path) { return reading(() -> fs.read(user, path)); }

    Outcome<List<String>> ls(String user, String path) { return reading(() -> fs.ls(user, path)); }

    Outcome<Long> size(String user, String path) { return reading(() -> fs.size(user, path)); }

    // Many readers at once, or one writer alone. finally releases the lock even if the call throws.
    private <T> T reading(Supplier<T> op) {
        lock.readLock().lock();
        try {
            return op.get();
        } finally {
            lock.readLock().unlock();
        }
    }

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

Read onlyJava 21Every file builds in CI9 files296 lines

Explorer

• Pyall_in_one.py
• file_system
• Pycommon.py
• Pydirectory.py
• Pyentry.py
• Pyfile.py
• Pyfile_system.py
• Pymode.py
• Pyoutcome.py
• Pyresult.py
• Pyshared_file_system.py

Pyall_in_one.py

all_in_one.pyfile_system/common.pyfile_system/directory.pyfile_system/entry.pyfile_system/file.pyfile_system/file_system.pyfile_system/mode.pyfile_system/outcome.pyfile_system/result.pyfile_system/shared_file_system.py

all_in_one.py

Read onlyPython 3.12Every file builds in CI10 files332 lines

Explorer

• C#AllInOne.cs
• src
• C#Directory.cs
• C#Entry.cs
• C#File.cs
• C#FileSystem.cs
• C#Mode.cs
• C#Outcome.cs
• C#Result.cs
• C#SharedFileSystem.cs

C#AllInOne.cs

AllInOne.cssrc/Directory.cssrc/Entry.cssrc/File.cssrc/FileSystem.cssrc/Mode.cssrc/Outcome.cssrc/Result.cssrc/SharedFileSystem.cs

AllInOne.cs

Read onlyC# · .NET 10Every file builds in CI9 files287 lines

Explorer

• Goall_in_one.go
• Godirectory.go
• Goentry.go
• Gofile.go
• Gofile_system.go
• Gomode.go
• Gonode.go
• Goresult.go
• Goshared_file_system.go

Goall_in_one.go

all_in_one.godirectory.goentry.gofile.gofile_system.gomode.gonode.goresult.goshared_file_system.go

all_in_one.go

Read onlyGo 1.24Every file builds in CI9 files424 lines

Explorer

• TSall-in-one.ts
• src
• TSdirectory.ts
• TSentry.ts
• TSfile-system.ts
• TSfile.ts
• TSmode.ts
• TSoutcome.ts
• TSresult.ts
• TSshared-file-system.ts

TSall-in-one.ts

all-in-one.tssrc/directory.tssrc/entry.tssrc/file-system.tssrc/file.tssrc/mode.tssrc/outcome.tssrc/result.tssrc/shared-file-system.ts

all-in-one.ts

Read onlyTypeScript, strictEvery file builds in CI9 files313 lines

Three ideas hold it together:

• Every entry knows only its name and its parent. Paths are worked out, never stored. So a move is one relink, and the tree can never disagree with a stored path. Files and directories are handled alike (Composite).
• Every operation goes through one walk. Parsing, resolving and the execute check happen in the same place for every call, behind one class that callers use with plain paths (Facade).
• The tree stays a tree. Names are unique in a directory, and a directory never moves inside itself. Thread safety is added around it, without changing it (Decorator).

Stress it

So far, one call runs at a time. Now a web server with many threads shares the file system.

Two threads change the tree at once

Interviewerminute 23

The file system is shared by a web server with many threads. Two requests create files in the same directory at the same moment. What can go wrong, and how do you stop it?

What they are testing

Whether you name what’s shared (each directory’s children map, and the parent links a move changes), pick how much to lock, and can say why a lock per directory is harder than it looks once move is involved.

Each directory’s children map is shared. Two threads adding a name to the same directory at once can corrupt the map, or lose one of the names. Go’s runtime even stops the program when two threads write one map at once.

A move is worse. It reads the target’s ancestors, then changes two directories and the entry’s parent. Picture two moves at the same time:

1. Thread A moves /a into /b/x. It walks up from /b/x and doesn’t meet /a. Check passed.
2. Thread B moves /b into /a/y. It walks up from /a/y and doesn’t meet /b. Check passed.
3. Both moves happen. Now /a is inside /b, and /b is inside /a. Neither can be reached from the root.

Each check was right about the tree it saw. But the tree changed between the check and the move.

The clearly correct fix is one read-write lock for the whole tree. Reads (read, ls, size) share it, so they run in parallel. Anything that changes the tree takes it alone, so each change sees a tree nobody else is changing. It lives in a wrapper, SharedFileSystem, so the tree code stays single-threaded and easy to test.

Sequence: two moves that each pass the ancestor check

Scroll or pinch to zoom, drag to pan

The better fix, only if measured, is a lock per directory. Unrelated writes could then run in parallel. But a move touches two paths and checks ancestors, so it must lock both paths in a fixed order, or two moves could each hold a lock the other needs, and wait forever (a deadlock). That is real complexity, so it’s worth it only when one lock is shown to be the bottleneck.

Option	How	Correct with move?	Cost
1. One read-write lock for the tree (our choice)	Changes go alone, reads go together	Yes	Writes to unrelated directories wait for each other
2. A lock per directory, taken down the path	Take the child’s lock, then drop the parent’s	Needs care	Move must lock two paths in a fixed order to avoid deadlock
3. A thread-safe map per directory	Thread-safe children maps, no other locks	No	Each map is safe; the ancestor check across them isn’t
4. Copy on write	Every change builds a new path to the root and swaps it in	Yes	Each write copies the path; readers never wait

JSharedFileSystem.javaPyshared_file_system.pyC#SharedFileSystem.csGoshared_file_system.goTSshared-file-system.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

// One read-write lock for the whole tree. Reads (read, ls, size) share it, so they run in
// parallel; anything that changes the tree takes it alone. A move touches two directories and
// checks every ancestor of the target, so a lock per directory would need a fixed order to
// avoid deadlock, and a walk that takes and drops locks down the path. One lock is correct by
// construction, and an in-memory tree operation takes microseconds, so it is rarely the
// bottleneck.
class SharedFileSystem {
    private final FileSystem fs;
    private final ReadWriteLock lock = new ReentrantReadWriteLock();

    SharedFileSystem(FileSystem fs) { this.fs = fs; }

    Result mkdir(String user, String path, boolean parents) { return writing(() -> fs.mkdir(user, path, parents)); }

    Result write(String user, String path, String content) { return writing(() -> fs.write(user, path, content)); }

    Result move(String user, String from, String to) { return writing(() -> fs.move(user, from, to)); }

    Result delete(String user, String path, boolean recursive) { return writing(() -> fs.delete(user, path, recursive)); }

    Result chmod(String user, String path, Mode mode) { return writing(() -> fs.chmod(user, path, mode)); }

    Outcome<String> read(String user, String path) { return reading(() -> fs.read(user, path)); }

    Outcome<List<String>> ls(String user, String path) { return reading(() -> fs.ls(user, path)); }

    Outcome<Long> size(String user, String path) { return reading(() -> fs.size(user, path)); }

    // Many readers at once, or one writer alone. finally releases the lock even if the call throws.
    private <T> T reading(Supplier<T> op) {
        lock.readLock().lock();
        try {
            return op.get();
        } finally {
            lock.readLock().unlock();
        }
    }

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

Why is this correct? A move holds the write lock from its ancestor check until its last change. No other change can run in between, so the tree it checked is the tree it changes. Reads hold the read lock, so they never see a move half done.

What does it cost? Two writes to unrelated directories wait for each other. Most file system work is reading, and a write here is a few map operations, so the wait is short.

Common mistake

Thread-safe maps and nothing else

Making each directory’s children a thread-safe map stops the maps from being corrupted. It does nothing for operations that read one place and change another. The two-move race above happens with every map safe on its own. The lock has to cover the whole operation, not each data structure it touches.

Go deeperHow each language does the lock1 min

Java, C# and Go use a real read-write lock. Python’s standard library has none, so every call takes one plain lock, which is still correct, just with less parallel reading. TypeScript runs on one thread, and every tree method finishes without an await, so the tree needs no lock at all.

What TypeScript needs instead is order, when a change must also be saved somewhere slow, like a journal on disk. Each change and its journal write go through a promise chain one at a time. So the journal holds the changes in the order they were applied, and replaying it rebuilds the same tree.

How you’d prove it works

The tree is plain objects with no threads, so most tests call it directly and check the results. Every test starts with /home/ana owned by Ana, and /home/ben owned by Ben. The tests that matter:

• Paths with ., .. and doubled slashes reach the same file. A relative path is refused.
• mkdir without parents refuses a missing parent. With parents, it creates them, and accepts a directory that already exists.
• A file can’t be used as a directory, and a directory can’t be read or written as a file.
• Listing is in name order, and a directory’s size adds up everything below it.
• A move carries everything inside. A directory can’t move into itself or onto a taken name.
• A non-empty directory needs a recursive delete.
• Ben can read Ana’s file, but not change, delete or move it, or create anything in her directory.
• A directory closed to others hides even an open file inside it. Root can still read it.
• Eight threads creating 1,000 files each in one directory leave exactly 8,000.

Go deeperThe tests in five languages2 min

The last test runs on SharedFileSystem. Without the lock, it fails about half the time in Java, and always in Go under the race detector. In TypeScript, the journal test fails every time without the promise chain.

JMain.javaPyexample.pyC#Program.csGomain.goTSexample.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

static final String ROOT = FileSystem.ROOT;
FileSystem fs;

// /home/ana belongs to ana and /home/ben to ben, as root would set them up.
@BeforeEach
void setUp() {
    fs = new FileSystem();
    for (String user : List.of("ana", "ben")) {
        fs.mkdir(ROOT, "/home/" + user, true);
        fs.chown(ROOT, "/home/" + user, user);
    }
}

@Test
void pathsAreNormalisedAndMustBeAbsolute() {
    assertEquals(Result.OK, fs.mkdir("ana", "/home/ana/docs", false));
    assertEquals(Result.OK, fs.write("ana", "/home/ana/./docs/../docs//a.txt", "hi"));
    assertEquals("hi", fs.read("ana", "/home/ana/docs/a.txt").value());
    assertEquals(List.of("a.txt"), fs.ls("ana", "/home/ana/docs/").value());
    assertEquals(Result.INVALID_PATH, fs.read("ana", "home/ana/docs/a.txt").result());
}

@Test
void mkdirNeedsTheParentsUnlessAskedToCreateThem() {
    assertEquals(Result.NOT_FOUND, fs.mkdir("ana", "/home/ana/x/y", false));
    assertEquals(Result.OK, fs.mkdir("ana", "/home/ana/x/y", true));
    assertEquals(Result.OK, fs.mkdir("ana", "/home/ana/x/y", true));
    assertEquals(Result.ALREADY_EXISTS, fs.mkdir("ana", "/home/ana/x/y", false));
}

@Test
void filesAndDirectoriesAreNotInterchangeable() {
    fs.write("ana", "/home/ana/f", "x");
    assertEquals(Result.NOT_A_DIRECTORY, fs.mkdir("ana", "/home/ana/f/g", true));
    assertEquals(Result.IS_A_DIRECTORY, fs.read("ana", "/home/ana").result());
    assertEquals(Result.IS_A_DIRECTORY, fs.write("ana", "/home/ana", "x"));
    assertEquals(List.of("f"), fs.ls("ana", "/home/ana/f").value());
}

@Test
void listingIsSortedAndSizeAddsUpTheSubtree() {
    fs.write("ana", "/home/ana/b.txt", "12345");
    fs.write("ana", "/home/ana/a.txt", "123");
    fs.mkdir("ana", "/home/ana/sub", false);
    fs.write("ana", "/home/ana/sub/c", "12");
    assertEquals(List.of("a.txt", "b.txt", "sub"), fs.ls("ana", "/home/ana").value());
    assertEquals(10L, (long) fs.size("ana", "/home/ana").value());
}

@Test
void moveRenamesAndCarriesTheSubtree() {
    fs.mkdir("ana", "/home/ana/p/q", true);
    fs.write("ana", "/home/ana/p/q/n", "x");
    assertEquals(Result.OK, fs.move("ana", "/home/ana/p", "/home/ana/r"));
    assertEquals("x", fs.read("ana", "/home/ana/r/q/n").value());
    assertEquals(Result.NOT_FOUND, fs.read("ana", "/home/ana/p/q/n").result());
}

@Test
void aDirectoryCannotMoveIntoItselfOrOntoAName() {
    fs.mkdir("ana", "/home/ana/p/q", true);
    fs.write("ana", "/home/ana/f", "x");
    assertEquals(Result.INVALID_MOVE, fs.move("ana", "/home/ana/p", "/home/ana/p/q/p"));
    assertEquals(Result.ALREADY_EXISTS, fs.move("ana", "/home/ana/f", "/home/ana/p"));
    assertEquals(Result.INVALID_MOVE, fs.move(ROOT, "/", "/home/root"));
}

@Test
void deletingADirectoryWithContentsMustBeRecursive() {
    fs.mkdir("ana", "/home/ana/p/q", true);
    assertEquals(Result.NOT_EMPTY, fs.delete("ana", "/home/ana/p", false));
    assertEquals(Result.OK, fs.delete("ana", "/home/ana/p", true));
    assertEquals(Result.NOT_FOUND, fs.ls("ana", "/home/ana/p").result());
}

@Test
void othersCanReadButNotChange() {
    fs.write("ana", "/home/ana/notes", "hello");
    assertEquals("hello", fs.read("ben", "/home/ana/notes").value());
    assertEquals(Result.PERMISSION_DENIED, fs.write("ben", "/home/ana/notes", "mine now"));
    assertEquals(Result.PERMISSION_DENIED, fs.mkdir("ben", "/home/ana/x", false));
    assertEquals(Result.PERMISSION_DENIED, fs.delete("ben", "/home/ana/notes", false));
    assertEquals(Result.PERMISSION_DENIED, fs.move("ben", "/home/ana/notes", "/home/ben/notes"));
}

@Test
void aClosedDirectoryHidesEverythingInside() {
    fs.mkdir("ana", "/home/ana/private", false);
    fs.write("ana", "/home/ana/private/diary", "dear diary");
    assertEquals(Result.OK, fs.chmod("ana", "/home/ana/private", new Mode(7, 0)));
    assertEquals(Result.PERMISSION_DENIED, fs.read("ben", "/home/ana/private/diary").result());
    assertEquals(Result.PERMISSION_DENIED, fs.ls("ben", "/home/ana/private").result());
    assertEquals(Result.PERMISSION_DENIED, fs.chmod("ben", "/home/ana/private", new Mode(7, 7)));
    assertEquals("dear diary", fs.read(ROOT, "/home/ana/private/diary").value());
}

@Test
void concurrentCreatesInOneDirectoryAllLand() throws Exception {
    SharedFileSystem shared = new SharedFileSystem(fs);
    CountDownLatch start = new CountDownLatch(1);
    List<Thread> threads = new ArrayList<>();
    for (int t = 0; t < 8; t++) {
        int id = t;
        Thread th = new Thread(() -> {
            try {
                start.await();
            } catch (InterruptedException e) {
                return;
            }
            for (int i = 0; i < 1000; i++) shared.write("ana", "/home/ana/f" + id + "-" + i, "x");
        });
        th.start();
        threads.add(th);
    }
    start.countDown();
    for (Thread th : threads) th.join();
    assertEquals(8000, shared.ls("ana", "/home/ana").value().size());
    assertEquals(8000L, (long) shared.size("ana", "/home/ana").value());
}

Go deeperEvery edge case, and where it is handled2 min

Case	What happens	Where
.. at the root	Stays at the root	parse
Relative path	INVALID_PATH	parse
mkdir -p of a directory that exists	OK	mkdir
A file where a directory was needed	NOT_A_DIRECTORY	resolve, mkdir
Read or write a directory	IS_A_DIRECTORY	read, write
Move onto an existing name	ALREADY_EXISTS; nothing is overwritten	move
Move a directory inside itself	INVALID_MOVE	move, the walk up
Move or delete the root	INVALID_MOVE or INVALID_PATH	move, delete
Delete a directory with contents	NOT_EMPTY unless recursive	delete
A closed directory on the path	PERMISSION_DENIED before anything inside is seen	resolve
Recursive delete of directories you can’t write	Allowed: only the top is checked, unlike Unix	delete
Two threads change one directory	One at a time, under the tree’s write lock	SharedFileSystem

Wrap up

The decisions, and what each one costs

Decision	We chose	We gave up
Structure	A composite tree of Entry, File and Directory	One-lookup access by full path
Paths	Cleaned up once, followed by walking; never stored	A path is a walk to work out
Move	Relink one entry; refuse a move into itself	Nothing: it’s cheap and safe
Delete	Unlink; a non-empty directory needs recursive	Checks on each directory inside a recursive delete
Permissions	Owner and others bits, execute checked on every directory	Groups and per-user lists
Threads	One read-write lock around the tree	Parallel writes to unrelated directories

Go deeperGenuinely different designs, and when to pick them2 min

A path-keyed map with a sorted index. Stage 1 isn’t always wrong. Object stores like S3 keep flat keys, and list a “directory” by reading a range of a sorted index. That costs the number of results, not the number of keys. They give up cheap rename, which is why renaming a folder in S3 copies every object.

A tree that never changes in place. Every change creates new nodes from the changed entry up to a new root, and shares everything else with the old tree. Readers keep the root they started with and never wait, snapshots are free, and undo is just keeping old roots. Git’s trees work this way. Each write costs a path’s worth of new nodes.

Inodes and directory entries. Separate the file (the inode: content, owner, mode, link count) from its names (entries in directories). This is what real file systems do, and it’s what makes hard links possible. In an interview, it’s worth naming as the next step, not starting with.

How to spend 45 minutes

• 0 to 3. In memory, absolute paths, the operations, permissions, threads.
• 3 to 5. The promises. Name “the cost is the path’s depth, even for a big move” as the hard one.
• 5 to 22. The flat map and its problems, the composite tree with parse and resolve, move with the ancestor check and delete, then owners and mode bits. Code resolve and move.
• 22 to 24. Walk through the full diagram: names and parents only, one walk for everything.
• 24 to 29. One read-write lock, and why a lock per directory is harder with move.
• 29 to 45. Links, then your own questions.

If time is short, skip permissions and spend it on move and the walk. The ancestor check and the cost of a move are what this question is decided on.

Follow-up questions

Interviewerminute 29

Users want shortcuts: a name in one directory that points to a file or directory somewhere else. What changes?

What they are testing

Whether you know the two kinds of link, and what each does to the tree. A hard link makes it a graph, which breaks the parent link and “delete frees everything inside”. A symbolic link keeps it a tree, but makes the walk follow a path, which can loop.

Most extensions fit into one place:

Extension	What changes	Changes the tree’s shape?
Symbolic links	A Link entry; resolve follows it, with a limit on hops	No
Hard links	Names separate from files; a link count; no single parent	Yes
Groups	A group per entry, a third set of bits, a user’s groups	No
Find by name	A walk of the subtree, or a name index updated on every change	No
Byte content and append	File holds bytes; append and read(offset, length)	No
Quotas	A size counter per user, updated by write, move and delete	No

Go deeperAdding links, step by step2 min

A symbolic link (symlink) is the easy one.

1. Add a new kind of entry, Link, whose content is a path. It sits in a directory like any file.
2. Teach resolve to follow it. When the walk meets a link in the middle of a path, it parses the link’s path and carries on from there, with the rest of the original path added on.
3. Guard against loops. a can point to b, and b back to a. So resolve counts the links it has followed, and gives up after a limit, as Unix does after 40.

The tree stays a tree: a link is just an entry with one parent. Deleting the target leaves the link pointing at nothing, which is allowed, and reads through it return NOT_FOUND.

A hard link is a much bigger change. It puts the same file in two directories, under two names.

1. Separate names from files. A directory now maps names to files, and a file no longer has one name or one parent.
2. Count names per file. Deleting a name lowers the count. The file is freed only when the count reaches zero.
3. Forbid hard links to directories. With them, a directory could be inside itself through a second name, and the inside-itself check would no longer work. Unix forbids them for this reason.

This separation of names from files is exactly what Unix calls the inode, which is why it’s the “next step” design above.

Go deeperFour more follow-up questions2 min

Interviewer asksHow would you print an entry's full path?

Walk up through the parents to the root, collecting names, then reverse them. It costs the depth, and it’s always right, because a path is worked out from the tree, not stored beside it.

Interviewer asksHow would you support a current directory and relative paths?

A session per user holds its current directory, as an entry, not a path, so moving that directory doesn’t break the session. A relative path is resolved starting from that entry instead of the root. cd is a resolve that must end at a directory the user has execute on.

Interviewer asksWhat if directories hold millions of entries?

A hash map of children keeps lookup O(1), but listing in order means sorting. A sorted map keeps listing in order, at O(log n) per lookup. For very large directories, listing should also come in pages, returning a cursor instead of every name at once.

Interviewer asksHow do you make it survive a restart?

Add every change to a journal before applying it, and replay the journal at startup, with a snapshot of the whole tree now and then, so replay stays short. The TypeScript version of the threads stage shows why the journal’s order must match the order the changes were applied.

Further reading

• Design a logging framework, another design with one facade over a tree-shaped configuration
• Design an LRU cache, for when the children map needs eviction
• The Linux path_resolution(7) man page, how a real kernel walks a path and checks permissions
• Refactoring.Guru: Composite, the pattern this design is built on