File System Design (In-Memory and Crash-Resilient)

0) Problem Restatement

Build a file system abstraction. First, an in-memory version that supports:

• mkdir("/a/b/c"): create folders, including missing parents.
• ls(path): if it's a file, return its name; if it's a folder, return its children sorted.
• addContentToFile(path, content): create the file or append to it.
• readContentFromFile(path): return the content.

Then the follow-up: make it crash-resilient. After a power loss or kernel panic, files and folders must come back correctly, with no corrupted or half-written state.

1) Requirements

1.1 Functional

• Hierarchical paths with folders and files.
• Create, list, read, append (and delete or move as extensions).

1.2 Constraints

• Path operations should cost O(depth of the path).
• (Follow-up) Durable and consistent after a crash.
• (Follow-up) Safe with many threads.

2) Core Design: a Tree of Nodes

Each node is either a directory (with children) or a file (with content). A directory keeps its children in a hash map for O(1) lookup by name. For sorted ls output, either sort on demand or use a sorted map (a TreeMap).

2.1 Class Diagram

classDiagram
    class FileSystem {
        -Dir root
        +mkdir(path) void
        +ls(path) List
        +addContentToFile(path, content) void
        +readContentFromFile(path) String
        -walk(path, create) Node
    }
    class Node {
        +String name
    }
    class Dir {
        +Map children
    }
    class File {
        +StringBuilder content
    }
    Node <|-- Dir
    Node <|-- File
    FileSystem --> Dir

3) Code (Python)

class Dir:
    def __init__(self):
        self.children = {}          # name -> Dir or File

class File:
    def __init__(self):
        self.content = []           # list of chunks; join on read

class FileSystem:
    def __init__(self):
        self.root = Dir()

    def _parts(self, path):
        return [p for p in path.split('/') if p]

    def _walk_dir(self, parts, create=False):
        node = self.root
        for name in parts:
            nxt = node.children.get(name)
            if nxt is None:
                if not create:
                    raise FileNotFoundError(name)
                nxt = node.children[name] = Dir()
            if not isinstance(nxt, Dir):
                raise NotADirectoryError(name)
            node = nxt
        return node

    def mkdir(self, path):
        self._walk_dir(self._parts(path), create=True)

    def ls(self, path):
        parts = self._parts(path)
        if not parts:
            return sorted(self.root.children)
        parent = self._walk_dir(parts[:-1])
        node = parent.children[parts[-1]]
        return [parts[-1]] if isinstance(node, File) else sorted(node.children)

    def addContentToFile(self, path, content):
        parts = self._parts(path)
        parent = self._walk_dir(parts[:-1], create=True)
        f = parent.children.setdefault(parts[-1], File())
        f.content.append(content)

    def readContentFromFile(self, path):
        parts = self._parts(path)
        return ''.join(self._walk_dir(parts[:-1]).children[parts[-1]].content)

4) Follow-up 1 — Concurrency

• Simple: one read-write lock for the whole tree. Many readers or one writer at a time.
• Better: a lock per directory node. To create /a/b/c, lock nodes from the top down in path order. Always taking locks in the same order prevents deadlocks.
• A rename or move across folders must lock both parents, again in a fixed order (e.g., sorted by path).

5) Follow-up 2 — Surviving a Crash

Real file systems separate metadata (the tree, file names, sizes, which disk blocks belong to which file, stored in inodes) from data blocks. A crash in the middle of a multi-step update, such as "allocate a block, write the data, update the inode, add a directory entry", can leave them out of sync. Common solutions:

1. Journaling / write-ahead log (WAL): before changing the real structures, write a record of the whole change to a log ("add file x to dir /a, blocks 17–20") and fsync it (force it to disk). Then apply the change. After a crash, replay complete log records and ignore incomplete ones. ext4 and NTFS work this way. Many journal only metadata, which is faster, while also writing data blocks before the metadata that points to them.
2. Copy-on-write (COW): never overwrite in place. Write new versions of the changed blocks and parent nodes, then switch one root pointer atomically. A crash leaves either the old tree or the new tree, never a mix. ZFS and btrfs work this way, and it makes snapshots cheap.
3. Checksums on blocks detect silent corruption (e.g., a torn write or disk error). With a replica or parity, the system can repair it.

For the in-memory design, the easiest durable version is: append every operation (mkdir, append) to a WAL file with fsync, and take periodic snapshots of the tree. On restart, load the latest snapshot and replay the log after it.

6) Extensions

• Delete and move: remove from the parent's map. With a WAL, log them like any other operation.
• Large files: store content in fixed-size blocks instead of one string, so random reads and writes don't copy everything.
• Distributed file system: split metadata (a namespace service) from data (block servers), as in HDFS or GFS. See the distributed file system design.

7) Wrap-Up

Model the file system as a tree of directory nodes with hash-map children and file nodes with appended chunks, so every path operation is O(depth). Add per-node locks taken in path order for concurrency. For crash safety, use a write-ahead journal with fsync (or copy-on-write with an atomic root switch), write data before metadata, and add checksums to detect corruption.