From owner-freebsd-fs Tue May 7 2:11:43 2002 Delivered-To: freebsd-fs@freebsd.org Received: from thebsh.namesys.com (thebsh.namesys.com [212.16.7.65]) by hub.freebsd.org (Postfix) with SMTP id C578637B404 for ; Tue, 7 May 2002 02:11:37 -0700 (PDT) Received: (qmail 29092 invoked from network); 7 May 2002 09:11:36 -0000 Received: from laputa.namesys.com.7.16.212.in-addr.arpa (HELO laputa.namesys.com) (212.16.7.124) by thebsh.namesys.com with SMTP; 7 May 2002 09:11:36 -0000 Received: by laputa.namesys.com (Postfix on SuSE Linux 7.3 (i386), from userid 511) id 2D30FB1CE; Tue, 7 May 2002 13:11:35 +0400 (MSD) From: Nikita Danilov MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Message-ID: <15575.39495.117903.517273@laputa.namesys.com> Date: Tue, 7 May 2002 13:11:35 +0400 X-PGP-Fingerprint: 43CE 9384 5A1D CD75 5087 A876 A1AA 84D0 CCAA AC92 X-PGP-Key-ID: CCAAAC92 X-PGP-Key-At: http://wwwkeys.pgp.net:11371/pks/lookup?op=get&search=0xCCAAAC92 To: Terry Lambert Cc: Philip Homburg , fs@FreeBSD.ORG Subject: Re: Filesystem In-Reply-To: <3CD73907.7FEEA69E@mindspring.com> References: <200205040019.UAA13780@illustrious.cnchost.com> <3CD32F43.327CDA46@mindspring.com> <20020504041936.GA19646@quic.net> <3CD3FB02.3EC1DA29@mindspring.com> <20020505084827.GA3688@quic.net> <3CD6B71C.C0A502A1@mindspring.com> <3CD73907.7FEEA69E@mindspring.com> X-Mailer: VM 7.03 under 21.4 (patch 3) "Academic Rigor" XEmacs Lucid X-Tom-Swifty: "Condensed chicken soup," was Tom's canned response. Sender: owner-freebsd-fs@FreeBSD.ORG Precedence: bulk List-ID: List-Archive: (Web Archive) List-Help: (List Instructions) List-Subscribe: List-Unsubscribe: X-Loop: FreeBSD.org Terry Lambert writes: > Philip Homburg wrote: > > >#1 Binary backwards compatability with millions of installed > > > systems > > > > What kind backwards compatability? The usual Unix system calls are uneffected > > (creat, open, link, unlink, getdents, etc.). > > Even then, it is user's choice to create large directories, the system > > just supports it. > > The ability to continue using my old disks with their old data > on them, without having to buy enough backup media that I can > back them up enough times I feel safe running the command > "newfs -new_directory_format" on them, and restoring from tape > (assuming I even trust this new format). > > > > >> If somebody would like to create 1M files, and you know that, when properly > > >> implemented, directories accesses cost O(log(n)), then what's the problem? > > > > > >#1 No one has written the code to optionally store directories > > > this way (and made it publically available) > > > > A small practical problem, that can be dealt with easily. (Unless you > > are asking for production quality code :-) > > Just code the same quality as the directory handling code already > in UFS... > > > > >#2 (minor nit) A btree is O(log2(N)), which is not as happy a > > > number as your O(log(N)) > > > > O(log2(N)) = O(log(N)/log(2)) = O(log(N)) > > > > I don't see where you get the log2. The fan-out is determined by the > > avarage size of a directory. > > Balanced btree. The number of compares necessary for the lookup > for an arbitrary individual file is based on the depth of the > btree (actually, thinking about this, a Fibonnaci or Particia > tree would be a better structure, but we were talking btree > directories). Still, fanout of btree is determined by block, pointer, and key size. Binary tree (where one will get log2(N) comparisons) is horribly inefficient as external indexing method. > > > > >> I don't want to think about crash recovery of btrees in a normal FFS > > >> filesystem. > > > > > >No one does, except the people asking us to switch to their pet > > >FS by default, but not releasing it under a usable license, and > > >expecting that we would just "eat" the backward compatability > > >issue. > > > > But that is just an implementation issue. The binary backwards compatability > > issues that you hinted at are more fundamental. > > Yes. Which is why when someone who sees only the implementation > isses comes at the problem, they end up frustrated. 8-) 8-). > > -- Terry Nikita. To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe freebsd-fs" in the body of the message