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

[Matt Mackall <mpm@selenic.com>]

On Wed, May 09, 2007 at 12:56:39AM -0700, Valerie Henson wrote:
> 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.

My reference to chunkfs here is simply that the worst-case is checking ~1
chunk, which is about 1/100th of a volume.

> > 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?

Yes, the original idea is you have to check every file that "covers" a
tile in its entirety. With Joern's fpos piece, I think we can restrict
our checks to just the section of the file that covers the tile.

-- 
Mathematics is the supreme nostalgia of our time.