Full-path indexing: why renaming can move the index

One name, several changed keys

Consider a key-value catalogue whose keys are complete paths. Our example moves /work to /archive. Four keys change; their values do not. /workbench stays put. A directory boundary matters: matching every string beginning with /work would incorrectly move that neighbor.

With separately materialized full-path strings, every affected record needs a new key. With a representation that shares a prefix, the same logical result might be expressed through fewer changes. That does not yet explain how ordered searches, pending updates or concurrent readers find the right records.

The downloadable example evaluator deliberately visits all entries. It is a correctness illustration, not the efficient tree algorithm. Its tests cover boundary matching, value preservation, inverse transformations and rejection of occupied destinations. Read the generated result or reproduce it with the generator.

Run node --test full-path-rename.test.mjs and node generate-full-path-rename.mjs with the evaluator alongside them. Paths use a restricted canonical ASCII syntax. The model has no permissions, symbolic links, hard links, data blocks, crash recovery or concurrency.

Why organize around paths at all?

An ordered storage index can make nearby keys convenient to scan. B-epsilon trees combine this ordering with buffered update messages: small updates accumulate and travel down the tree in batches. Queries must account for pending messages, not just the value already stored in a leaf. Choosing the key schema therefore affects which application operations become cheap scans and which become expensive sequences of lookups. The data structure alone does not choose a useful schema. [3]

BetrFS 0.2 explored a compromise called zoning: use paths relative to a zone root, with indirection between zones. Larger zones favor locality during traversal; smaller zones reduce the amount of data implicated in a rename inside a zone. Renaming a zone root can instead update its reference. Maintaining the zones is additional work, so this is a layout policy with consequences, not a free flag. Here, a zone is a filesystem namespace partition, unrelated to the sequential-write zones of ZNS SSDs or host-managed SMR disks. [2, section 4]

Range rename needs more than a pointer swap

Zhan and colleagues combine tree restructuring with key lifting: shared prefixes are inferred from the search path, avoiding a rewrite of every interior key. Pending messages must follow the correct rename order. The downloaded paper calls the prototype BetrFS 0.4; its conference landing page uses ArborFS. [1, sections 3-5]

For an engineer, the useful question is not whether prefixes can be replaced in a string. It is whether the storage engine can preserve ordering and visibility while changing its representation. Our five-row table specifies the desired result, but gives no evidence about the I/O needed to obtain it.

The prototype permits one pending large rename and defers structural work. Its historical evaluation used at least four runs and min/max error bars, not confidence intervals. These details matter before reusing a headline speedup. [1, sections 4 and 7]

A key rewrite is not the rename contract

POSIX rename includes rules absent from the example: type compatibility, existing destinations, directory ancestry, permissions and open references. A directory cannot be moved into its own descendant; replacing a destination directory requires it to be empty. The standard also describes atomic namespace behavior. A loop that deletes old keys and inserts new ones one by one does not automatically supply that behavior. [4]

Our evaluator intentionally refuses an occupied destination instead of implementing POSIX replacement. It also rejects overlapping source and destination subtrees. Treating this narrower operation as a production rename implementation would silently change what callers are allowed to do.

Durability is a separate check. Linux documents that syncing a file does not necessarily persist its containing directory entry; the directory needs its own synchronization. Check return values and the actual filesystem's guarantees. A short namespace operation is not proof that earlier buffered file data reached persistent storage. [5] See the temporary-file publication analysis for the surrounding workflow.

Measure the whole move

A useful evaluation would hold the resulting namespace constant while recording three separate endpoints: when the operation returns, when the required state is durable, and when deferred index work has drained. Follow the move with a scan and another rename. This can expose work charged to the next operation rather than the first one.

Record subtree size, record count, path lengths, cache state, destination occupancy, concurrent requests, synchronization and final backlog. Include boundary and failure cases, not only a successful move into an empty namespace. Report latency distributions and throughput separately. Neither this example nor a historical prototype comparison ranks today's production filesystems.

Continue with buffered B-epsilon updates and deferred clone costs. Corpus records: full-path indexing and range rename.

Primary sources

1. Zhan et al. The Full Path to Full-Path Indexing. FAST 2018, pp. 123-138, sections 3-7.
2. Yuan et al. Optimizing Every Operation in a Write-optimized File System. FAST 2016, sections 4 and 7.
3. Bender et al. An Introduction to B-epsilon-trees and Write-Optimization. USENIX ;login:, October 2015, pp. 22-28.
4. The Open Group. POSIX.1-2024 rename and renameat.
5. Linux man-pages. fsync(2), description and errors.

This is a source review and a constructed namespace example. No filesystem benchmark or BetrFS replication was performed.