LLD-015 · LOW LEVEL DESIGN

In-Memory File System

Model a namespace tree with precise paths, defensive bytes and atomic ownership-preserving moves.

Local Java 21 reference verified: 128 checks. Learner drafts are not executed. Author self-review; independent review pending.

Existing introductory lesson · Version 1

Understand the problem

Design an in-memory file system with directories, byte files, mkdir/read/write/list/stat/move/delete. Prevent cycles and accidental source loss during failed moves. Explain which familiar operating-system behaviors are part of this contract and which are deliberately absent.

Before you start

• Tree ownership and Composite
• Path value normalization
• Defensive copying and aliasing
• Atomic namespace updates

Scope and explicit decisions

• An absolute-path in-memory tree with one root. No host filesystem access, persistence, symlinks, hard links, permissions, users, handles, open-file semantics, locking across processes or POSIX compatibility is implemented.
• Paths must start with slash and contain no NUL. Repeated slashes and . are ignored; .. lexically removes one component and rejects escaping above root. This happens before traversal: /missing/../archive/a resolves as /archive/a even if missing never existed.
• Names are case-sensitive Java strings. Directory listings use TreeMap natural String order (UTF-16 ordering), not locale collation. There is no normalization of Unicode-equivalent names or maximum path length.
• Trailing slash is a directory hint. read(file/) rejects; write always rejects trailing slash. Target paths are exact new names, not a POSIX “move into this existing directory” shorthand.
• mkdir creates only one level and requires an existing directory parent. Existing directory is a no-op; a file collision rejects. mkdir root is a no-op.
• write creates or replaces a file, never a directory. One file is limited to 1,048,576 bytes. Both write and read defensively copy bytes, so callers cannot mutate stored content through aliases. Total tree memory is not globally bounded.
• move requires a nonroot source and nonroot exact target, rejects target overwrite and directory-into-descendant cycles, and preserves node identity/content. Same normalized nonroot source/target is a no-op after type/path validation.
• delete rejects root. Nonrecursive deletion rejects nonempty directories; recursive deletion removes a subtree from the namespace. There are no external handles keeping it visible and no secure byte erasure guarantee.
• One global monitor serializes lookup and mutation. This provides local atomic namespace operations but no durability, crash recovery or real filesystem authorization.

Worked examples

Try before revealing

Requirements and invariants

R1 — Only directories own children; each reachable node has one parent and the root has none. move protects I1.

R2 — Caller byte-array mutation cannot alter stored file content. write protects I2.

R3 — Rejected moves leave source and target namespaces unchanged. move protects I3.

R4 — Path normalization cannot escape root or silently treat a file as a directory. parse protects I1.

I1: The namespace is an acyclic tree rooted at one Directory; only Directory stores named children.

I2: Each DataFile owns a private byte array, and read returns another copy.

I3: A successful move removes one old name and adds one new name atomically; ordinary validation failure removes neither.

Derive the design

A flat path map is simple until directory semantics matter

A flat map from full path to bytes supports basic file lookup, but moving a directory requires rewriting every descendant path and coordinating collisions. The tree model gives each directory child ownership and moves one subtree reference. File and directory remain distinct capabilities, avoiding methods such as read on a directory that have no valid meaning in this contract.

Alternative: A flat indexed namespace can be efficient with transactional prefix operations or inode/dentry models, but that is a different storage design. An operating-system filesystem already supplies many mature guarantees; this exercise studies the domain representation without claiming to replace it.

Responsibilities and ownership

Method contracts

What, when, why and how

Each concept is attached to the requirement it protects, its implementation, an alternative and a test.

Read and run the Java reference

1import java.util.*;
2/** Absolute-path in-memory tree. No symlinks, permissions, handles or persistence. */
3public final class Solution {
4    private Solution() {}
5    private abstract static sealed class Node permits Directory,DataFile {}
6    private static final class Directory extends Node { final Map<String,Node> children=new TreeMap<>(); }
7    private static final class DataFile extends Node { final byte[] data; DataFile(byte[] data){this.data=data.clone();} }
8    public record Stat(boolean directory,int bytes,int children){}
9    private record Path(List<String> parts,boolean directoryHint){public Path{parts=List.copyOf(parts);}}
10    public static final class FileSystem {
11        private final Directory root=new Directory();
12        private static Path parse(String raw){
13            if(raw==null||!raw.startsWith("/")||raw.indexOf('\0')>=0)throw new IllegalArgumentException("absolute path");
14            var parts=new ArrayList<String>();for(String part:raw.split("/")){
15                if(part.isEmpty()||part.equals("."))continue;
16                if(part.equals("..")){if(parts.isEmpty())throw new IllegalArgumentException("path escapes root");parts.removeLast();}
17                else parts.add(part);
18            }return new Path(parts,raw.endsWith("/"));
19        }
20        private Node resolve(List<String> parts){Node node=root;for(String part:parts){if(!(node instanceof Directory d))throw new IllegalStateException("not a directory");node=d.children.get(part);if(node==null)throw new IllegalArgumentException("not found");}return node;}
21        private Node resolve(Path path){var node=resolve(path.parts());if(path.directoryHint()&&!(node instanceof Directory))throw new IllegalStateException("trailing slash needs directory");return node;}
22        private Directory parent(Path path){if(path.parts().isEmpty())throw new IllegalArgumentException("root operation");var parent=resolve(path.parts().subList(0,path.parts().size()-1));if(!(parent instanceof Directory d))throw new IllegalStateException("parent not directory");return d;}
23        private static String name(Path path){return path.parts().getLast();}
24        public synchronized void mkdir(String raw){
25            var path=parse(raw);if(path.parts().isEmpty())return;var parent=parent(path);var old=parent.children.get(name(path));if(old instanceof Directory)return;if(old!=null)throw new IllegalStateException("file exists");parent.children.put(name(path),new Directory());
26        }
27        public synchronized void write(String raw,byte[] data){
28            Objects.requireNonNull(data);if(data.length>1_048_576)throw new IllegalArgumentException("file byte limit");var path=parse(raw);if(path.directoryHint())throw new IllegalArgumentException("file trailing slash");var parent=parent(path);if(parent.children.get(name(path)) instanceof Directory)throw new IllegalStateException("directory exists");var replacement=new DataFile(data);parent.children.put(name(path),replacement);
29        }
30        public synchronized byte[] read(String raw){var node=resolve(parse(raw));if(!(node instanceof DataFile file))throw new IllegalStateException("not file");return file.data.clone();}
31        public synchronized List<String> list(String raw){var node=resolve(parse(raw));if(!(node instanceof Directory dir))throw new IllegalStateException("not directory");return List.copyOf(dir.children.keySet());}
32        public synchronized Stat stat(String raw){var node=resolve(parse(raw));return node instanceof Directory dir?new Stat(true,0,dir.children.size()):new Stat(false,((DataFile)node).data.length,0);}
33        public synchronized void move(String source,String target){
34            var from=parse(source);var to=parse(target);var node=resolve(from);var oldParent=parent(from);var newParent=parent(to);
35            if(to.directoryHint()&&!(node instanceof Directory))throw new IllegalStateException("target trailing slash");
36            if(from.parts().equals(to.parts()))return;
37            if(node instanceof Directory&&to.parts().size()>from.parts().size()&&to.parts().subList(0,from.parts().size()).equals(from.parts()))throw new IllegalArgumentException("directory cycle");
38            if(newParent.children.containsKey(name(to)))throw new IllegalStateException("target exists");
39            oldParent.children.remove(name(from));newParent.children.put(name(to),node);
40        }
41        public synchronized void delete(String raw,boolean recursive){
42            var path=parse(raw);var node=resolve(path);var parent=parent(path);
43            if(node instanceof Directory dir&&!recursive&&!dir.children.isEmpty())throw new IllegalStateException("directory not empty");parent.children.remove(name(path));
44        }
45    }
46}
47

Complexity and limits

• Parsing costs O(L) for path length L. Traversal at depth D performs TreeMap lookups, roughly O(sum(log children_i)) plus String comparison cost; it is not unconditional O(D) hash lookup.
• list copies C names in existing sorted order: O(C). There is no additional sort because Directory uses TreeMap. stat is O(path traversal) plus constant direct metadata extraction.
• read/write copy B bytes: O(B) time and returned/stored buffer space. The per-file cap is 1 MiB, but total namespace memory is unbounded.
• move changes two directory maps after traversal/cycle checks, independent of descendant count; recursive delete unlinks a subtree, with eventual garbage-collection work proportional to its contents. No secure erasure or handle semantics are provided.

Walk through the actual reference

These walkthrough fixtures are emitted only after the Java harness verifies their operations and expected state. Concurrency tests additionally exercise competing callers.

Mistakes and counterexamples

Engineer → Senior → Staff

Open focused practice →

Provenance and scope of evidence

Original teaching material. The local contract is implemented by Solution.java and tested by Test.java on Java 21. Distributed persistence, real provider/device adapters and deployment are not claimed.

Reference verification is not independent editorial review, production deployment verification or a claim that distributed adapters are implemented.