Re: [fuse-devel] RFC: Moose FS - multi-disk, redundant, checksumming filesystem

[Valient G. <va...@gm...>]

On Sat, May 31, 2008 at 3:04 AM, Goswin von Brederlow <gos...@we...> wrote:
> Unsolved!
> =========
>
> One thing I'm undecided about is the actual structure to manage the
> free blocks. I can maintain a B-tree of all free blocks, which would
> be like a file consiting of the free blocks as mentioned
> above. Updating that from DiskRoot to DiskRoot is a bit complicated
> though and I might even need a 4th DiskRoot for it to work at all. The
> advantage would be that the space needed to manage this sinks the less
> blocks are free. i.e. I get more data on my disks.
>

I wrote a proof of concept that used a similar scheme.   However mine
translated the other way - it provided a block device using a
filesystem as the backing store.  Reference counting was handled by
using hard links in the underlying filesystem.

A non-leaf node in the tree contains nothing but links to other
blocks.  In my case, the name of the reference was its SHA hash.   The
block was stored as both a file and a directory of hard links to child
nodes.

As you say, using reference counts makes it easy to take snapshots -
just add a reference to a root node.  The idea of a hash tree goes
back a long ways - it's basically a Merkle tree, which has
applications in distributed systems protocols.  ZFS works in a similar
way, so you may consider looking at ZFS for ideas - or even consider
use the ZFS fuse port itself..

cheers,
Valient