From mboxrd@z Thu Jan 1 00:00:00 1970 From: Matt Mackall Subject: Re: [RFC] TileFS - a proposal for scalable integrity checking Date: Wed, 9 May 2007 12:06:52 -0500 Message-ID: <20070509170652.GF11115@waste.org> References: <20070428220522.GN11166@waste.org> <20070429232349.GA19937@thunk.org> <20070430014042.GL11115@waste.org> <20070509075638.GJ12859@nifty> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Cc: Theodore Tso , linux-fsdevel@vger.kernel.org To: Valerie Henson Return-path: Received: from waste.org ([66.93.16.53]:34567 "EHLO waste.org" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1754603AbXEIRHO (ORCPT ); Wed, 9 May 2007 13:07:14 -0400 Content-Disposition: inline In-Reply-To: <20070509075638.GJ12859@nifty> Sender: linux-fsdevel-owner@vger.kernel.org List-Id: linux-fsdevel.vger.kernel.org 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.