Date: Mon, 06 May 2002 19:16:39 -0700 From: Terry Lambert <tlambert2@mindspring.com> To: Philip Homburg <philip@cs.vu.nl> Cc: fs@FreeBSD.ORG Subject: Re: Filesystem Message-ID: <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>
next in thread | previous in thread | raw e-mail | index | archive | help
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). > >> 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 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?3CD73907.7FEEA69E>