DagShell: A Content-Addressable Virtual Filesystem with Multiple Interfaces

DagShell’s architecture separates content storage from path namespace management. The system maintains two primary data structures:

1. 1.

   Node store ($N:\text{Hash}\to \text{Node}$): A mapping from SHA256 hashes to immutable node objects

2. 2.

   Path index ($P:\text{Path}\to \text{Hash}$): A mapping from absolute paths to node hashes

This separation enables the same content to exist at multiple paths (deduplication) while providing familiar path-based access patterns.

The system defines three node types, each immutable and content-addressed:

FileNode: Contains binary content and metadata (mode, uid, gid, mtime). The hash incorporates both content and metadata, ensuring that permission changes create new nodes:

DirNode: Contains a mapping from names to child node hashes. Adding or removing a child creates a new directory node with an updated children mapping:

DeviceNode: Represents virtual devices (/dev/null, /dev/random, /dev/zero) with programmatic behavior rather than stored content:

All write operations follow a copy-on-write pattern. Writing to /a/b/file.txt requires creating:

1. 1.

   A new FileNode with the updated content

2. 2.

   A new DirNode for /a/b with updated children

3. 3.

   A new DirNode for /a with updated children

4. 4.

   An updated root DirNode

This propagation of changes up the directory tree maintains referential integrity while preserving all previous states. The path index is updated to point to the new node hashes, while old nodes remain in the node store until garbage collection.

Content addressing provides automatic deduplication at the node level. If two files have identical content and metadata, they produce the same hash and share storage:

This property extends to directories: two directories with identical children share the same node. Deduplication occurs transparently without explicit user intervention.

Deletion operates through two mechanisms:

Soft delete: Removes the path mapping but preserves nodes in the node store. This enables recovery and maintains referential integrity.

Garbage collection: The purge() operation performs mark-and-sweep garbage collection, removing nodes unreachable from the path index:

The FileSystem class implements standard POSIX operations (open, read, write, mkdir, ls, rm, stat) while maintaining immutability. Each operation either queries existing nodes or creates new nodes through the copy-on-write mechanism.

Path resolution converts absolute paths to node hashes through the path index. The implementation handles special cases:

• •

  Root directory (/) is immutable and always present

• •

  Device files in /dev behave according to their type

• •

  Soft-deleted paths return None during resolution

File handles provide a familiar interface while operating on immutable content. The FileHandle class buffers writes in memory and commits changes to new nodes on close:

DagShell implements POSIX user and group semantics through special files in /etc:

• •

  /etc/passwd: User database with uid, gid mappings

• •

  /etc/group: Group database with membership information

The system performs permission checks by evaluating mode bits against user context (uid, gid set). Root user (uid 0) bypasses permission checks. This design enables realistic permission modeling while maintaining filesystem immutability.

The fluent API (dagshell_fluent.py) provides method chaining and Unix-style composition. The DagShell class maintains session state (current directory, environment variables, last result) and translates operations into FileSystem calls:

The CommandResult class enables piping by storing operation results and providing output redirection:

Text processing commands (grep, sed, sort, uniq, wc, head, tail) operate on CommandResult objects, enabling Unix-style data flow without shell parsing.

The Scheme interpreter (scheme_interpreter.py) provides a functional programming interface to filesystem operations. The implementation includes:

• •

  Complete Scheme evaluator with lexical scoping

• •

  Built-in filesystem procedures mapped to Python operations

• •

  List processing and higher-order functions for file manipulation

The Scheme environment includes filesystem operations (mkdir, write-file, read-file), text processing (grep, head, tail), and functional primitives (map, filter, reduce). This enables scripting complex filesystem operations in a functional style.

The terminal emulator (terminal.py) provides a POSIX-compliant shell interface. The implementation separates concerns:

1. 1.

   CommandParser: Parses shell syntax (pipes, redirects, operators)

2. 2.

   CommandExecutor: Translates parsed commands to fluent API calls

3. 3.

   TerminalSession: Manages REPL loop and session state

The parser handles standard shell features:

• •

  Pipes: ls | grep txt | sort

• •

  Redirects: echo "data" > file.txt

• •

  Logical operators: mkdir dir && cd dir

• •

  Sequential execution: cmd1 ; cmd2

The executor maps command names to shell methods, handles flag translation, and applies redirections to CommandResult objects. This architecture enables shell-like interaction while leveraging the fluent API for implementation.

The terminal provides special slash commands for meta-operations:

Host Integration:

• •

  /import <host> <virt>: Import files from host filesystem with safety restrictions

• •

  /export <virt> <host>: Export to host filesystem

State Management:

• •

  /save <file>: Serialize to JSON

• •

  /load <file>: Deserialize from JSON

• •

  /snapshot <name>: Create timestamped snapshot

DAG Inspection:

• •

  /status: Show filesystem statistics

• •

  /dag: Visualize DAG structure

• •

  /nodes: List content-addressed nodes

• •

  /info <hash>: Show node details

These commands operate outside the POSIX abstraction, providing direct access to the underlying DAG structure and host system integration.

DagShell implements a substantial subset of POSIX filesystem operations:

• •

  File operations: open, read, write, close, stat

• •

  Directory operations: mkdir, ls, rmdir

• •

  Path operations: cd, pwd, absolute/relative path resolution

• •

  Permission checking: Unix-style mode bits and ownership

• •

  Special files: device nodes with appropriate semantics

The implementation prioritizes correctness over performance, ensuring that operations behave consistently with POSIX specifications where applicable.

The filesystem serializes completely to JSON format. The serialization includes:

• •

  All nodes with their content (base64-encoded) and metadata

• •

  Path-to-hash mappings

• •

  Deleted path set for soft deletes

JSON serialization enables easy inspection, version control of filesystem states, and portability across systems. The deserialization process reconstructs node objects and indices, restoring complete filesystem state.

DagShell interfaces with the host filesystem through controlled import/export:

Import reads files from the host filesystem and creates corresponding nodes in the virtual filesystem. The operation:

• •

  Preserves file modes and permissions

• •

  Recursively imports directory trees

• •

  Restricts access to safe directories

• •

  Applies specified uid/gid to imported files

Export writes virtual filesystem content to the host. The operation:

• •

  Creates directories and files on the host

• •

  Preserves permissions when possible

• •

  Maps virtual uid/gid to host uid/gid

• •

  Reports the number of exported items

Safety mechanisms prevent unrestricted host access. Import and export operations validate paths against configured safe directories, preventing directory traversal attacks.

Although DagShell doesn’t implement explicit versioning, the immutable DAG structure preserves complete history. Combined with JSON serialization, users can:

• •

  Save filesystem snapshots at any point

• •

  Compare snapshots to identify changes

• •

  Restore previous states by loading snapshots

• •

  Track node-level changes through hash comparison

This design enables version control experimentation and rollback capabilities without implementing a full version control system.

DagShell provides isolated filesystem environments for testing. Applications can:

• •

  Test filesystem interactions without touching the host

• •

  Create complex directory structures programmatically

• •

  Reset to known states between test runs

• •

  Verify filesystem operations through inspection

The Python API integrates naturally with pytest and other testing frameworks. The complete test suite demonstrates this approach, achieving 99% code coverage through isolated filesystem tests.

DagShell serves as a teaching tool for filesystem concepts:

• •

  Students explore content-addressable storage without distributed systems complexity

• •

  The DAG structure makes relationships between files and directories explicit

• •

  Immutability demonstrates functional programming principles in systems context

• •

  Multiple interfaces show different abstraction levels over the same core

The Scheme interface particularly suits functional programming education, demonstrating how traditional imperative operations (filesystem modifications) can be expressed functionally.

The fluent API enables data processing pipelines with rollback:

Researchers can experiment with data transformations, saving intermediate states and comparing results across different processing strategies.

DagShell enables reproducible computational environments through:

• •

  Complete filesystem state serialization

• •

  Deterministic hashing ensures identical content produces identical hashes

• •

  JSON format integrates with version control

• •

  Import/export enables moving between virtual and real filesystems

A research workflow might maintain project data and scripts in DagShell, serialize the entire state to version control, and restore the exact environment on different machines.

The implementation includes comprehensive test suites covering:

• •

  Core filesystem operations (test_dagshell.py, test_core_filesystem_comprehensive.py)

• •

  Fluent API and pipelines (test_fluent.py)

• •

  Terminal emulation (test_terminal.py, test_enhanced_terminal.py)

• •

  Scheme interpreter (test_scheme_interpreter.py, test_scheme_integration_comprehensive.py)

• •

  Edge cases and error handling (test_edge_cases_comprehensive.py)

• •

  Persistence and import/export (test_persistence_comprehensive.py, test_import_export_comprehensive.py)

Test coverage analysis reports 99% code coverage, indicating thorough testing of core functionality and edge cases. The test suite includes over 300 individual test cases exercising different aspects of the system.

DagShell prioritizes correctness and simplicity over performance. Key performance characteristics:

Node creation: $O(1)$ time complexity for adding nodes to the store. Hashing dominates the cost, with SHA256 computation proportional to content size.

Path resolution: $O(k)$ where $k$ is the path depth, requiring dictionary lookups through the path index.

Write operations: $O(d)$ where $d$ is directory depth, due to copy-on-write propagation up the directory tree.

Garbage collection: $O(n)$ where $n$ is the total number of nodes, using mark-and-sweep traversal.

Serialization: $O(n)$ for serializing all nodes to JSON, with base64 encoding overhead for binary content.

The in-memory design eliminates I/O overhead but limits filesystem size to available memory. For the target use cases (testing, education, experimentation), this tradeoff proves acceptable.

Memory consumption scales linearly with content size and number of unique nodes. Deduplication reduces memory usage when multiple paths reference identical content. The Python object overhead (approximately 56 bytes per object) adds constant overhead per node.

For typical test scenarios (hundreds of files, megabytes of content), memory usage remains well within modern system constraints. Large-scale usage would require external storage and selective loading.

Git [1] pioneered practical content-addressed storage for version control. Git represents commits, trees, and blobs as content-addressed objects in a similar DAG structure. Key differences:

• •

  Git tracks history explicitly through commit objects; DagShell provides snapshots without built-in history

• •

  Git optimizes for large repositories through pack files; DagShell maintains individual nodes

• •

  Git focuses on source code; DagShell provides a general filesystem interface

DagShell applies Git’s content-addressing principles to a full POSIX-like filesystem rather than specialized version control.

IPFS [2] implements distributed content-addressed storage with a focus on peer-to-peer data sharing. IPFS and DagShell share content-addressing principles but differ in scope:

• •

  IPFS emphasizes distribution and discovery; DagShell focuses on single-system filesystem semantics

• •

  IPFS uses Merkle DAGs for verification; DagShell uses SHA256 hashing for deduplication

• •

  IPFS integrates with networking protocols; DagShell provides programming interfaces

DagShell can be viewed as exploring content-addressing without the complexity of distributed systems.

The Nix [3] package manager uses content-addressed storage for reproducible package management. Nix stores packages in /nix/store with paths derived from content hashes. Similarities include:

• •

  Both use content addressing for determinism and deduplication

• •

  Both enable rollback through immutability

• •

  Both provide isolation from the system

However, Nix focuses on package management with derivations and dependency tracking, while DagShell provides a general filesystem interface.

Plan 9’s [4] ”everything is a file” philosophy influenced DagShell’s device node design. Plan 9 represents processes, networks, and system services as files in synthetic filesystems. DagShell adopts this approach for virtual devices while focusing on content-addressability rather than distribution.

Union filesystems like UnionFS and OverlayFS provide copy-on-write semantics over existing filesystems. These systems optimize write operations through layering. DagShell differs by:

• •

  Maintaining all nodes explicitly rather than differencing layers

• •

  Using content hashes for identification rather than layer ordering

• •

  Providing multiple programming interfaces rather than FUSE mounting

The current mark-and-sweep garbage collection runs synchronously. Future work could explore:

• •

  Incremental garbage collection for large filesystems

• •

  Reference counting to avoid full traversal

• •

  Generational collection based on node age

• •

  User-controlled retention policies for history

Content compression could reduce memory usage and serialization size. Strategies include:

• •

  Transparent compression of file node content

• •

  Delta compression for similar files

• •

  Dictionary-based compression for common patterns

The tradeoff between compression overhead and memory savings warrants investigation.

While DagShell currently operates on a single system, the content-addressed design enables distribution:

• •

  Node sharing across systems through hash-based lookup

• •

  Merkle tree verification for integrity

• •

  Synchronization protocols for state replication

• •

  Conflict resolution for concurrent modifications

This direction would position DagShell closer to IPFS while maintaining its filesystem abstraction.

Several optimizations could improve performance:

• •

  Path index caching for frequently accessed paths

• •

  Lazy loading for large directory trees

• •

  Binary serialization format replacing JSON

• •

  Persistent storage backend with memory-mapped files

These optimizations would enable larger-scale usage while maintaining the design principles.

Explicit version control features could leverage the existing DAG:

• •

  Commit objects linking snapshots with metadata

• •

  Branch and merge operations

• •

  Diff computation between filesystem states

• •

  History visualization tools

This work would create a Git-like system with full filesystem semantics rather than just file tracking.