Low-level design: in-memory file system

Designing an in-memory file system is a low-level design (LLD) exercise in classes: hold a tree of directories and files in memory, and run a small shell over it that makes directories, writes and reads files, lists, moves, removes and searches. Five decisions carry the model in this case study. Files and directories share one interface, the Composite pattern, so a size or a search treats a whole tree and a single file alike. A directory maps each child’s name to the child, so a name lives in exactly one place. Every operation turns its path into nodes with one resolver that walks the tree component by component, as POSIX describes pathname resolution. A move checks everything before it changes anything, and never puts a directory inside itself. And a search is built from small filter objects, the way find combines its tests.

The prompt, the requirements and the first design

The prompt: “Design an in-memory file system with a shell-like API.” Four questions shape the answer. One user, or permissions too? Paths relative to a current directory? Links? Several threads? Here the answers are one user, both kinds of path, no links yet and one thread first, and they become the requirements:

• F1 mkdir(path) creates a directory; with parents, also the missing ones above it, like mkdir -p.
• F2 write(path, text) creates or replaces a file, read(path) returns its text and ls(path) lists names.
• F3 mv(src, dst) renames or moves, into dst when it is a directory, never into the moved directory itself.
• F4 rm(path) removes a file or an empty directory; recursive removes a whole tree.
• F5 find(path, filter) lists the paths below path that match tests of name, type, size and age.
• N1 Paths are absolute or relative; ., .. and repeated slashes mean what POSIX says.
• N2 A failed call changes nothing and names its error as POSIX does: ENOENT, ENOTDIR, EINVAL.
• N3 Time comes from a clock the file system is given, so tests choose it.

N1 decides more than it seems. A tempting shortcut cleans the path as a string, as Python’s posixpath.normpath() does, and only then looks it up. The run below resolves eight paths from /home/asha, where notes.txt is a file and src a directory, both ways:

"""Cleaning a path as a string, against walking it through the tree (lesson lld/in-memory-file-system).

posixpath.normpath() removes repeated slashes, "." and "name/.." by looking at the string alone. The resolver of
this lesson walks the tree one component at a time, as POSIX pathname resolution does, so it notices when a name
is missing or is a file. The tree is a dict of dicts, a str is a file's content, and the current directory is
/home/asha."""

import posixpath

TREE = {"home": {"asha": {"notes.txt": "buy milk", "src": {"app.py": "print('hi')"}}}, "tmp": {}}
CWD = ["home", "asha"]


def node_at(names):
    node = TREE
    for name in names:
        node = node[name]
    return node


def walk(path):
    """The absolute path that path names, or the error resolution stops with."""
    names = [] if path.startswith("/") else list(CWD)
    node = node_at(names)
    for part in path.split("/"):
        if not part:  # repeated, leading and trailing slashes
            continue
        if not isinstance(node, dict):
            return f"ENOTDIR: /{'/'.join(names)} is a file"
        if part == "..":
            names = names[:-1]  # at the root, ".." is the root
        elif part != ".":
            if part not in node:
                return f"ENOENT: /{'/'.join(names)} has no {part}"
            names.append(part)
        node = node_at(names)
    if path.endswith("/") and not isinstance(node, dict):
        return "ENOTDIR: a trailing slash needs a directory"
    return "/" + "/".join(names)


PATHS = [
    "/home//asha/./src/",
    "src/../notes.txt",
    "/../../tmp",
    "notes.txt/..",
    "missing/../notes.txt",
    "src/app.py/../../notes.txt",
    "notes.txt/",
    "//tmp",
]

print(f"{'path':28} {'cleaned as a string':22} walked through the tree")
differ = 0
for path in PATHS:
    cleaned = posixpath.normpath(posixpath.join("/home/asha", path))
    walked = walk(path)
    differ += cleaned != walked
    print(f"{path:28} {cleaned:22} {walked}")
print(f"{differ} of {len(PATHS)} paths get a different answer from the string and from the tree")

path                         cleaned as a string    walked through the tree
/home//asha/./src/           /home/asha/src         /home/asha/src
src/../notes.txt             /home/asha/notes.txt   /home/asha/notes.txt
/../../tmp                   /tmp                   /tmp
notes.txt/..                 /home/asha             ENOTDIR: /home/asha/notes.txt is a file
missing/../notes.txt         /home/asha/notes.txt   ENOENT: /home/asha has no missing
src/app.py/../../notes.txt   /home/asha/notes.txt   ENOTDIR: /home/asha/src/app.py is a file
notes.txt/                   /home/asha/notes.txt   ENOTDIR: a trailing slash needs a directory
//tmp                        //tmp                  /tmp
5 of 8 paths get a different answer from the string and from the tree

Five answers differ. notes.txt/.. names nothing, because .. needs a directory before it; the string version answers /home/asha anyway. missing/../notes.txt fails because missing does not exist, and notes.txt/ because a trailing slash names a directory. The last line is a choice, not a bug: POSIX lets an implementation give exactly two leading slashes a meaning of its own, and this design reads them as the root.

The design makes six choices, each with one main option:

• Composite nodes: File and Directory share Node, so size and search treat a tree and a leaf alike.
• Names in the parent: a directory maps names to children, so a rename changes one entry.
• Parent links: each node knows its parent, so .. and the subtree check walk upwards.
• One resolver: every operation resolves its path with the same walk, component by component.
• Checks before changes: a move or a removal validates everything first, so a failure leaves the tree as it was.
• Filters as objects: each search test is an object with matches(), combined by And, Or and Not.

The deep dives that decide whether this design holds:

1. How does one resolver serve every operation, including those that create the last component?
2. What does mv check, in which order, and what does a careless move do to the tree?
3. Should a directory compute its size or cache it, and what does each cost?
4. How do find’s tests become filter objects, with its rounding, its precedence and pruning?
5. What changes when two threads rename at once?
6. What do symbolic links add to resolution and to recursive calls?

An answer is judged on the requirements, the split between nodes, resolver and operations, the move rules, the size trade-off, the search design and the failure handling.

One resolver for every operation Pro: opens with a Pro, Premium or Ultimate pass