Please excuse me for the delay in responding to this...
"Stephen C. Tweedie" wrote:
>
> On Thu, Jul 06, 2000 at 09:19:58PM +0100, Steve Whitehouse wrote:
> > can you explain "phase tree" and/or give a reference ?
>
> For a reference, wait until ALS and see the ext2-derived filesystem
> report. :-)
Which is when I'll deliver my white paper on Tux2fs - thanks for
being mysterious and building up the anticpation. ;-)
> For basic background, look up some of the WAFL white papers from
> NetApps. The basic idea is an old database one: you have your
> filesystem in a tree, and whenever you modify the tree, you write into
> new blocks. Then the next level up in the tree --- which contains
> pointers to the old blocks --- gets modified to point to the new
> blocks, and those changes too get written to new blocks, so you then
> need to update the pointers in the _next_ level up the tree.
>
> So you do your changes right up the tree, allocating all your new
> blocks in sequential order on disk somewhere (anywhere, unlike a LFS),
> and now all you need to do to make the entire new set of writes
> visible after a reboot is to move the root node pointer for the
> filesystem from the old root block to the new one. It's a beautiful
> mechanism for achieving transactional consistency, and it lends itself
This is right on the money except for the part about "allocating all
your new blocks in sequential order". Tux2's tree phase algorithm
allocates rewritten blocks as near as it can to their original
locations, thereby avoiding the kind of read fragmentation that
log-structured filesystems (for example) suffer from. Naturally it
is desireable that the allocations for sequential rewrites also be
sequential, but Ext2's existing goal-directed allocation should take
care of this nicely.
There are other important differences between Tux2's tree phase and
the WAFL algorithm, but as you say, the WAFL white papers are a good
starting point.
-- Daniel- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.rutgers.edu Please read the FAQ at http://www.tux.org/lkml/
This archive was generated by hypermail 2b29 : Mon Jul 31 2000 - 21:00:18 EST