Re: [RFC] TileFS - a proposal for scalable integrity checking

[Valerie Henson <val_henson@linux.intel.com>]

On Sun, Apr 29, 2007 at 08:40:42PM -0500, Matt Mackall wrote:
> 
> This does mean that our time to make progress on a check is bounded at
> the top by the size of our largest file. If we have a degenerate
> filesystem filled with a single file, this will in fact take as long
> as a conventional fsck. If your filesystem has, say, 100 roughly
> equally-sized files, you're back in Chunkfs territory.

Hm, I'm not sure that everyone understands, a particular subtlety of
how the fsck algorithm works in chunkfs.  A lot of people seem to
think that you need to check *all* cross-chunk links, every time an
individual chunk is checked.  That's not the case; you only need to
check the links that go into and out of the dirty chunk.  You also
don't need to check the other parts of the file outside the chunk,
except for perhaps reading the byte range info for each continuation
node and making sure no two continuation inodes think they both have
the same range, but you don't check the indirect blocks, block
bitmaps, etc.

There is one case where you do need to do a full check of all links
that cross chunks - if a continuation inode's pointers have been
corrupted, and you might end up with orphan continuation inodes or
dangling links in other chunks.  I expect that to be relatively rare.

> So we should have no trouble checking an exabyte-sized filesystem on a
> 4MB box. Even if it has one exabyte-sized file! We check the first
> tile, see that it points to our file, then iterate through that file,
> checking that the forward and reverse pointers for each block match
> and all CRCs match, etc. We cache the file's inode as clean, finish
> checking anything else in the first tile, then mark it clean. When we get
> to the next tile (and the next billion after that!), we notice that
> each block points back to our cached inode and skip rechecking it.

If I understand correctly then, if you do have a one exabyte sized
file, and any part of it is in a dirty tile, you will need to check
the whole file?  Or will Joern's fpos proposal fix this?

This is interesting stuff, thanks!

-VAL