This message generated a parse failure. Raw output follows here. Please use 'back' to navigate. From devnull@lkml.org Wed Apr 24 05:12:09 2024 Received: from nic.funet.fi (nic.funet.fi [193.166.0.145]) by herbie.ucs.indiana.edu (8.10.1/8.10.1) with ESMTP id e6TDHCl07840 for ; Sat, 29 Jul 2000 08:17:13 -0500 (EST) Received: from vger.rutgers.edu ([128.6.190.2]:8748 "EHLO vger.rutgers.edu" ident: "NO-IDENT-SERVICE[2]" smtp-auth: TLS-CIPHER: ) by nic.funet.fi with ESMTP id ; Sat, 29 Jul 2000 16:16:06 +0300 Received: (majordomo@vger.rutgers.edu) by vger.rutgers.edu via listexpand id ; Sat, 29 Jul 2000 08:52:55 -0400 Received: by vger.rutgers.edu id ; Sat, 29 Jul 2000 08:52:45 -0400 Received: from hermes.mixx.net ([212.84.196.2]:4934 "HELO hermes.mixx.net") by vger.rutgers.edu with SMTP id ; Sat, 29 Jul 2000 08:52:32 -0400 Received: from mate.bln.innominate.de (cerberus.innominate.de [212.84.234.251]) by hermes.mixx.net (Postfix) with ESMTP id 3BEFDF851 for ; Sat, 29 Jul 2000 15:11:58 +0200 (CEST) Received: by mate.bln.innominate.de (Postfix, from userid 9) id 139E32CAA5; Sat, 29 Jul 2000 15:11:58 +0200 (CEST) From: Daniel Phillips Reply-To: Daniel Phillips X-Newsgroups: innominate.bln.list.linux.kernel Subject: Re: ext3-0.0.2e released Date: Sat, 29 Jul 2000 15:11:57 +0200 Organization: innominate AG Lines: 69 Distribution: local Message-Id: References: <200007062019.VAA09313@gw.chygwyn.com> <20000714143612.A7357@redhat.com> <20000726181113.F6970@archimedes.suse.com> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit X-Trace: mate.bln.innominate.de 964876317 28101 10.0.0.90 (29 Jul 2000 13:11:57 GMT) X-Complaints-To: news@innominate.de To: David Gould X-Mailer: Mozilla 4.72 [de] (X11; U; Linux 2.2.16 i586) X-Accept-Language: en To: linux-kernel@vger.rutgers.edu Sender: owner-linux-kernel@vger.rutgers.edu Precedence: bulk X-Loop: majordomo@vger.rutgers.edu David Gould wrote: > > On Tue, Jul 25, 2000 at 12:16:42PM +0200, Daniel Phillips wrote: > > Please excuse me for the delay in responding to this... > > Me too... > > > "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 > > I had not heard the term "phase tree", but from your description is sounds > exactly like what is often called "shadow paging". Which may make sense for > file systems, but none of the commercial DB engines use it, probably because > of the latency issues you mention. > > Or have I misunderstood? I checked and no, it's not 'shadow paging', at least if I can rely this description: http://lunar.cs.byu.edu/cs453/notes/html-15/tsld015.htm Some assertions: "Disadvantages of shadow page over log-based: [...] Garbage collection: find all the garbage pages & add them to the list of ?free? pages, a committed transaction causes db pages containing data changed by the transaction inaccessible which become garbage (since they are not part of the free space & do not contain usable info.) [...] Difficult to be adapted for concurrent transactions" Phase tree does not generate garbage, nor is it unsuitable for concurrent tranactions - please see the discussion under the thread "[NFS] Re: NetApps et al. <- NVRAM" on the linux-nfs list. Phase tree by itself isn't that great for high-volume low-latency transactions: you would have to have very short phases to keep latency down, and that would force quite a few redundant metadata writes. However, the addition of a *small* journal on disk or in NVRAM would knock the commit latency down to nearly zero without impacting phase tree's other advantages. -- 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/