Evaluation & Benchmarking

To evaluate the practical viability of the LIST Filesystem Wrapper (LFW), we analyzed its performance through both theoretical complexity analysis and empirical benchmarking against standard hierarchical filesystems.

Computational Complexity

The computational overhead of LFW is primarily concentrated in the initialization phase (building the virtual tree) and the per-operation latency of the FUSE layer.

Tree Construction

The time complexity for building the internal graph structure from the LFW root is modeled as:

\[T_{\text{build}} = O(N \cdot P \cdot D)\]

Where: * \(N\) is the total number of entries (singletons and bundles) in the LFW root. * \(P\) is the average depth of the directory paths associated with each entry. * \(D\) is the total number of unique directory nodes in the constructed tree.

This complexity arises from a linear scan of all \(N\) metadata files, where for each file, the system must traverse a path of length \(P\) and perform lookups against the existing directory set \(D\) to ensure structural integrity. Space complexity for this structure is \(O(N + D)\).

File Operation Latency

Once the tree is mounted, the time complexity for standard POSIX operations (read, write, create) is:

\[T_{\text{op}} = O(P)\]

The operation cost is dominated by node resolution, where the system traverses the virtual tree from the root to the target leaf node based on the provided virtual path. Once the node is resolved, retrieval of the unique identifier (UUID) and access to the physical file in the LFW root occur in constant time \(O(1)\).

Experimental Results

We conducted benchmarks simulating real-world filesystem data across three scales: 50,000, 100,000, and 500,000 files.

Benchmark results for 50,000 files.

Metric	Hierarchical File System	LFW File System
Total Storage	214 MB	404 MB
Average Read Time	0.092 ms	2.333 ms
Average Write Time	0.080 ms	3.413 ms
Average Create Time	0.138 ms	3.876 ms

Benchmark results for 100,000 files.

Metric	Hierarchical File System	LFW File System
Total Storage	458 MB	776 MB
Average Read Time	0.078 ms	2.522 ms
Average Write Time	0.082 ms	3.393 ms
Average Create Time	0.127 ms	3.826 ms

Benchmark results for 500,000 files.

Metric	Hierarchical File System	LFW File System
Total Storage	2.3 GB	3.9 GB
Average Read Time	0.751 ms	3.524 ms
Average Write Time	0.747 ms	4.435 ms
Average Create Time	0.132 ms	4.209 ms

Storage Overhead

Experimental data shows a storage overhead of approximately \(1.7\times\) to \(1.9\times\) compared to native hierarchical storage. This is primarily due to the requirement of the LIST specification to maintain a dedicated metadata file for every atom.

It is important to note that this overhead is disproportionately high in our tests because the sample files were small (100–1000 bytes), making them comparable in size to the metadata files themselves. In real-world scenarios where average file sizes are significantly larger, the percentage of storage dedicated to metadata becomes negligible.

Latency and Scaling

The per-operation latency in LFW is higher than in native filesystems, with a performance gap ranging from \(5\times\) to \(43\times\). This overhead is attributed to two factors: 1. The FUSE (Filesystem in Userspace) layer, which introduces context-switching overhead between the kernel and userspace. 2. The additional metadata lookup required to resolve immutable IDs.

Interestingly, as the dataset size increases to 500k files, the relative performance gap narrows. While native hierarchical filesystems experience increased latency as the directory tree deepens and search times grow, LFW’s latency grows more moderately, suggesting better scalability for extremely large, flat-stored collections.