User: Password:
Subscribe / Log in / New account

Wandering Tree?

Wandering Tree?

Posted Apr 3, 2008 9:57 UTC (Thu) by deleteme (guest, #49633)
In reply to: Wandering Tree? by Mithrandir
Parent article: UBIFS

There is a whitepaper on the UBIFS page, and LWN wrote about it in the LogFS article.
The on-flash tree looks much like the structure used by ext2. There are some differences in how it is managed, however. The log structure of the filesystem implies that blocks cannot be rewritten in place; any time a block is changed it must be moved and written to a new location. If there are pointers to the moved block (think about the usual indirect blocks used to store the layout of larger files), the blocks containing the pointers must also be changed, and thus moved. That, in turn, will require changes at the next level up in the tree. Thus changes at the bottom of the tree will propagate upward all the way to the root. This is the "wandering tree" algorithm. One of the advantages is that the old filesystem structure remains valid until the root is rewritten - a crash could cause the loss of the last operation, but it will leave previous data and the structure of the filesystem intact.

Actually managing the entire directory tree as a wandering tree would be expensive; beyond that, files with multiple hard links break the tree structure and make wandering trees much harder to implement. So the actual tree implemented by LogFS just has two levels. There is an "inode file" containing the inode structures for every file and directory existing within the filesystem; each inode then points to the associated blocks holding the file's data. Directory entries contain a simple integer index giving the inode offset within the inode file. So changes to an inode only require writing the inode itself and the inode file; the rest of the directory structure need not be touched.

(Log in to post comments)

Wandering Tree?

Posted Apr 8, 2008 10:43 UTC (Tue) by saffroy (subscriber, #43999) [Link]

It's been a while since I read about it, but this approach sounds similar to the method used
by WAFL, the filesystem used by NetApp and described here:

This is great for snapshots, but I think it's patented (maybe someone can confirm?).

Speaking of patents, from what I read in this article, I don't see what's different between
UBI and FTL, the latter being patented too.

Wandering Tree?

Posted Apr 11, 2008 16:48 UTC (Fri) by anton (subscriber, #25547) [Link]

Netapp has patents, but if wandering trees are among them, then that's a weak patent, because there is quite a bit of very well-documented prior art: They were used in log-structured file system implementations, and are also the technique that people programming in functional and logic programming languages use to manage trees.

Copyright © 2017, Eklektix, Inc.
Comments and public postings are copyrighted by their creators.
Linux is a registered trademark of Linus Torvalds