Lab L13 · Java + Go

Implementing an in-memory file system

Build an in-memory file system addressed by absolute paths such as /docs/a.txt. It supports creating directories, writing and reading files as byte arrays, listing a directory's children in sorted order, and moving a file or a whole directory subtree to a new path in one atomic step.

The task

This is the classic “design an in-memory file system” prompt, and the same shape as any hierarchical namespace: object-store prefixes, feature-flag folders, configuration trees. The difficulty is not the happy path but the rules: what counts as a valid path, what happens when the parent is missing, why read must return a copy, and why moving /a into /a/b must fail. Any representation works; the reference stores a flat map from normalised path to node.

A move rewrites the prefix of every path in the subtree in one locked step. Moving a directory beneath itself would create a cycle, so it is rejected.

What you implement

public final class MemoryFileSystem {
    public MemoryFileSystem();                       // the root "/" exists
    public void mkdir(String path);
    public void write(String path, byte[] data);     // create or replace a file
    public byte[] read(String path);
    public List<String> list(String directory);      // child names, sorted
    public void move(String from, String to);        // file or whole subtree
}

Rules

Paths must start with / and must not contain . or .. components or a NUL character → otherwise IllegalArgumentException. Repeated or trailing slashes are normalised: /a//b/ is /a/b.
The parent of a new path must exist and be a directory → otherwise IllegalStateException. There is no implicit mkdir -p.
mkdir on an existing path → IllegalStateException. write to a directory → IllegalStateException; to an existing file → replaces it.
read of a missing path or a directory → IllegalStateException. write stores a copy and read returns a copy: mutating either array later must not change stored content.
list returns names only (not full paths) of direct children, sorted; missing path or a file → IllegalStateException.
move: moves the node and every descendant at once. Moving / or into its own descendant → IllegalArgumentException; missing source, existing destination or missing destination parent → IllegalStateException; from.equals(to) → no-op.
All methods are thread-safe; a concurrent reader sees either the whole tree before a move or the whole tree after it.

Worked example

mkdir("/docs"), write("/docs/a.txt", "hi"), mkdir("/docs/img"). list("/docs") → [a.txt, img].
write("/x/y.txt", …) → IllegalStateException (no /x).
move("/docs", "/archive") → list("/") → [archive]; read("/archive/a.txt") → "hi".
move("/archive", "/archive/img/old") → IllegalArgumentException.

Files and commands

Read the tests first, then replace each TODO in the starter until they pass. Java starter: MemoryFileSystem.java · tests: MemoryFileSystemTest.java. Go starter: fs.go · tests: fs_test.go.

cd java
./gradlew test --tests 'labs.filesystem.*'

cd go
go test -race -count=1 ./filesystem

Reveal the reference solutions

Java: MemoryFileSystem.java
Go: fs.go

When to use

Use this lab for a small local file-tree model: create directories, create or replace byte-content files, read independent copies, list direct children, and atomically move a subtree. The root directory exists at construction. Parents must already exist. Moving the root, overwriting an existing destination, creating directory cycles, and accessing missing files fail explicitly. Moving an existing non-root path to itself succeeds without a change.

This is not an operating-system filesystem implementation. There are no permissions, symlinks, file handles, durable storage, host path access, or deletion API. Resource limits are not enforced: file count, path length, and total bytes can grow. Do not use the path checker as evidence that arbitrary host filesystem operations are sandboxed.

Steps

Choose a canonical namespace. Require absolute slash-separated paths and reject NUL, dot, and parent-dot components. Collapse repeated separators and trailing separators. Treat names case-sensitively. These rules intentionally avoid platform-specific drive letters or backslash interpretation; the in-memory namespace is independent of the host OS.
Hide mutable storage. Keep node records behind one lock. Copy byte arrays on write and on read, so a caller cannot mutate stored contents after the operation finishes. Directory listings are sorted independent result collections, not live map views.
Validate before mutation. For create, check parent existence and directory type. A write may replace a file but may not replace a directory. For move, check source, destination, destination parent, and descendant-cycle conditions before altering nodes.
Move a whole subtree. Gather the source and every descendant using a separator-aware prefix, construct the replacement keys, remove old keys, and install new keys under one lock. A source named /a must not include /ab. No observer may see half the rename. Returned bytes remain snapshots even after their source moves.
Test aliasing and failed operations. Change the original write buffer and a later read buffer, verifying stored bytes stay unchanged. Reject a move into the source subtree, then successfully move the directory and check that the old descendant disappears while the new descendant preserves its content. Test direct-child listings and forbidden dot components.
State costs and evolution seams. The flat-map representation makes a subtree move and listing O(total node count), with temporary storage for the moved keys. Read and write copy file bytes. A node-based trie can make subtree moves cheaper, but needs the same public contract and characterization tests. Before adding deletion, specify recursive behavior, open-handle semantics if any, and ownership of detached data.

Checklist

Recall and variation

Rebuild subtree move before reading Go or Java. Variation: move /a beside /ab and mutate an old read buffer. Acceptance: /ab is untouched and stored bytes do not change through the caller's alias.

Paths have one documented canonical representation
Read and write buffers cannot alias stored mutable bytes
Move validation occurs before any visible mutation
Subtree prefix matching respects separators
Storage, permission, and durability limitations are explicit

Signals

Working: moving a directory preserves all descendants and a failed move leaves the original tree intact.

Going wrong: a caller mutates a file through a returned array, an update leaves nodes under both old and new paths, or string prefix matching moves similarly named siblings accidentally. Locking protects the map, not an eventual external filesystem or another process.