Date: Tue, 7 May 2002 13:11:35 +0400 From: Nikita Danilov <Nikita@Namesys.COM> To: Terry Lambert <tlambert2@mindspring.com> Cc: Philip Homburg <philip@cs.vu.nl>, fs@FreeBSD.ORG Subject: Re: Filesystem Message-ID: <15575.39495.117903.517273@laputa.namesys.com> 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> <m174kb0-0014NkC@centaur.cs.vu.nl> <3CD6B71C.C0A502A1@mindspring.com> <m174qoA-000OesC@sluis.cs.vu.nl> <3CD73907.7FEEA69E@mindspring.com>
next in thread | previous in thread | raw e-mail | index | archive | help
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
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?15575.39495.117903.517273>