wandering-tree-problem · shipping · also Wandering-tree update propagation

Wandering tree problem

The wandering tree problem is recursive metadata rewriting caused when out-of-place updates change addresses referenced by ancestor blocks.

Moving a data block can require rewriting its direct pointer block, then an indirect pointer block and higher metadata. F2FS reduces this propagation by assigning identifiers to nodes and maintaining their locations in NAT. The problem is address-update propagation, not directory traversal. [1]

The FAST 2015 design still maintains checkpoint metadata and performs cleaning. Removing one propagation path does not eliminate those costs or establish a workload-independent write-amplification factor. [2]

Relations

related

F2FS, F2FS Node Address Table, F2FS checkpoint, Copy-on-write (storage), Write amplification

Citations

1. Linux 6.12 F2FS documentation: wandering tree, on-disk layout and metadata structure. (accessed 2026-10-21)
2. Lee, Sim, Hwang and Cho (2015). F2FS: A New File System for Flash Storage. FAST 2015, sections 2.1, 2.2 and 2.7. (accessed 2026-10-21)

Further reading

3. F2FS: when a successful fsync is not a recovery promise (accessed 2026-10-21)

JSON: /data/terms/wandering-tree-problem.json