Skip to content
Tutorials Center
My learning

Topics

Lesson 52 of 57 ยท Low-Level Design Projects

Project: In-Memory File System

Design an in-memory file system step by step: files and directories as a Composite tree, path resolution, mkdir, read, write, ls, mv and rm, with runnable Node.js code.

"Design an in-memory file system" is a favorite low-level design question, and it is a perfect place to use the Composite pattern. A directory contains files and other directories; you want to ask any of them for its size or its path without caring which kind it is. In this project you will turn a short problem statement into classes, then into a runnable model with mkdir, write, read, ls, find, tree, mv, rm and size.

The process is the one from How to Approach a Low-Level Design Problem: clarify, find the entities, define the API, then apply a pattern where change is expected.

Step 1: requirements

State your assumptions before drawing anything.

  • Paths look like /docs/notes/todo.txt: a slash-separated list of names starting at the root /.
  • Everything lives in memory. No persistence, permissions, links, timestamps or concurrent users (these are the extensions at the end).
  • Operations: mkdir(path) creates a directory and any missing parents; write(path, text) creates or overwrites a file; read(path); ls(path) lists names in a directory; size(path) returns the total size; rm(path); mv(from, to); plus find and tree for exploring.
  • Errors (missing path, reading a directory, writing into a file) must be clear, not silent.

Step 2: entities and relationships

The nouns are file, directory, path and file system. A file and a directory are both nodes with a name and a parent, so they share a base class. A directory owns its children (composition: deleting a directory deletes everything under it). The FileSystem is a facade: callers speak in paths, and only the facade knows how to walk the tree.

classDiagram
    class FsNode {
      +name
      +parent
      +path
      +size
      +isDir() bool
    }
    class File {
      +content
    }
    class Directory {
      +children Map
    }
    class FileSystem {
      +mkdir(path)
      +write(path, text)
      +read(path) text
      +ls(path) names
      +size(path) number
      +rm(path)
      +mv(from, to)
    }
    FsNode <|-- File
    FsNode <|-- Directory
    Directory "1" *-- "0..*" FsNode : children
    FileSystem --> Directory : root

Composite: a directory holds nodes, and a directory is itself a node.

Two decisions are worth saying out loud. First, a directory keeps its children in a Map keyed by name, so a lookup is O(1) and duplicate names are impossible by construction. Second, the node knows its parent, which gives every node a cheap path and makes mv easy. The price is that parent and child links must be kept consistent, which is why only a few methods are allowed to change them.

Step 3: the Composite in action

size is the classic Composite operation. A file answers with its own length. A directory asks each child and adds the answers; it never checks what kind of child it has. Adding a new kind of node later (for example a symbolic link) means one new class that answers size, with no change to the directory.

Path resolution is the other core piece. #walk starts at the root and follows one name at a time; if it meets a file in the middle of a path, or a name that does not exist, it throws a clear FsError.

Node.js A complete in-memory file system

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with node:readline or process.stdin), it gets the next line from this box.

Step 4: why the design holds up

  • Open for extension. A Symlink or Device node adds a class and changes only the places where its behavior differs.
  • One place for path logic. #walk and #parentOf are private. If you later switch paths to include . and .., or add a current-directory concept, you change those two methods.
  • Correctness lives in mv. Moving a directory into one of its own descendants would create a cycle, so the loop up the parent chain rejects it. This is the kind of edge case interviewers look for.
  • Errors are values of one type. FsError lets callers catch file-system problems without catching every bug.

The size question: compute or cache?

size above walks the whole subtree on every call: simple and always correct, but O(n) in the number of nodes. If size is called often and files change rarely, cache each directory's size and update it on write, rm and mv, walking up the parent links to adjust the totals. That trades a faster read for more bookkeeping in every write. State this trade-off aloud in an interview and pick one.

Node.js Cached sizes by walking the parent chain

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with node:readline or process.stdin), it gets the next line from this box.

Extensions to mention

Extension How the design absorbs it
Permissions and owners Add fields to FsNode; check them in the facade before each operation
Timestamps Set on write and mkdir; injected clock for tests, as in the parking lot
Undo Wrap each operation in a Command object that knows how to reverse itself
Copy A clone() method on each node, an application of Prototype
Watching changes Directories publish events to subscribers (Observer)
Many threads Lock per directory, or one lock for the whole tree, as in the parking lot race
Disk persistence Hide storage behind an interface, as in Repository

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Which pattern lets you ask a file or a directory for its size through one interface?

    Composite treats single objects (files) and containers (directories) uniformly, so a directory just asks each child for its size.
  2. 2. Why does a directory store its children in a Map keyed by name?

    A keyed collection gives fast lookup by name and enforces unique names without extra code.
  3. 3. What bug does the loop over parent nodes in mv() prevent?

    If the destination's ancestor chain contains the moved node, the tree would loop; walking up from the destination detects it.
  4. 4. What is the trade-off of caching directory sizes?

    A cache moves work from reads to writes and adds a consistency obligation.

Summary

  • Files and directories are nodes of a Composite tree; a directory holds nodes and is itself a node.
  • The FileSystem facade turns paths into walks over the tree and keeps path logic in one place.
  • Keyed children give O(1) lookup and unique names; parent links give paths and make mv simple.
  • Edge cases to state: missing path, file used as a directory, directory moved into itself, overwriting a file.
  • Computing sizes on demand is simple; caching them is faster to read but must be kept in sync.
  • Permissions, undo, copy and watching are extensions that fit through Command, Prototype and Observer.

Next lesson: Design Pattern Exercises with Solutions.