Date: Sat, 04 May 2002 13:39:07 -0700 From: Bakul Shah <bakul@bitblocks.com> To: Terry Lambert <tlambert2@mindspring.com> Cc: Scott Hess <scott@avantgo.com>, "Vladimir B. Grebenschikov" <vova@sw.ru>, fs@FreeBSD.ORG Subject: Re: Filesystem Message-ID: <200205042039.QAA16949@glatton.cnchost.com> In-Reply-To: Your message of "Fri, 03 May 2002 17:45:55 PDT." <3CD32F43.327CDA46@mindspring.com>
next in thread | previous in thread | raw e-mail | index | archive | help
> Generally the "large amount of object in a directory" objection > is brought up by some [FS] advocate, who wants to advocate their > pet FS, and isn't really noticing a real problem: instead, they > are implementing a solution, and then trying to invent a problem > that requires it. So they really don't care about portability, > they care about advocacy. If anything, I am advocating the zero, one and infinity rule. Don't place arbitrary limits and justify it as a good thing. A directory provides a namespace and using it for that purpose for any number of files is a perfectly sane thing to do. If it worked well enough, you wouldn't see abominations like ftp.netcom.com:users/ba/bakul (where they had use a two level scheme to improve access time). BTW, I too have come across a couple of cases where tens of thousands of files were stored in one dir. In one case it was a "throw away" program that ended up being a critical tool and the prototype got used and expended instead of being simply rewritten. By the time I got involved, it also depededed on Sybase but they couldn't figure out what to do with those zillion existing files! > > My frustration is with the 70s mindset when it comes to > > extending basic capabilities. Reasoning like: the disk > > access speed is very slow so the speed of directory access is > > not an issue. And since speed is not an issue a linear > > search is fine and dandy. Never mind that with a large > > buffer cache, chances are you will find dir. blocks in core > > and a linear search is not a great searching strategy when > > you have more than 10 to 20 items. And this is not the > > only such instance in the kernel. > > This case is an externalized interface used by programs, which > have a choice in their implementation, and choose badly. Can you please translate that in simple english? > I agree that there is a lot of room for extending the basic OS > capabilities; I would also argue that there is generally a lot > of research in that area, as well, and that research isn't being > put into practice, for the most part, for a reason other than > "not invented here" or "it's too hard: let's go shopping" (though > that is sometimes the reason). The main reason I think applies > is that legacy interoperability has more value than the other > benefits that the change brings. XFS from SGI also has btree directories so at least some vendors are doing this. I suspect in the free software community the reason is likely to be a) it is not hip enough, b) people who care & have expertise don't have time and/or inclination, c) NIH -- let us do our own cool thing even if it is just a tiny variation. BTW, I don't look down on any of these reasons. It is just the way things are. > For FS research, Poul and Kirk are working on UFS2. It would be > wise to appeal to them to include sufficient mechanisms in the > way of extension fields so that you could (for example) mark a > directory as being "btree" or "patricia tree" or "trie" or > whatever, and have it work transparently with legacy support for > linear directory block layout. Poul has already stated that he > and Kirk do not intend to change the directory layout to a btree, > even though they have an on disk format change that they will be > making, so this is the most logical compatability break. I don't > know if they intend to provide sufficient extension instertion > points for this type of thing (this would include extensions to > the soft updates system being pluggable, as well -- so I doubt > it). Either way, they haven't said, so you could always ask Kirk. I don't recall the goals of UFS2 being published except extending some limits. But to me this is a perfect example of NIH (I admit I don't know the details but seems that way). Why not just clone XFS? SGI can already achieve amazing data rates with it, its design is proven by fire and it has a lot of good features. Note that a number of companies are currently doing a lot of research in the FS area but I am afraid most of it will die with the companies. > Fast dir search won't be picked up until important applications > start to rely on it. And important applications won't rely on > it until it's generally available. So the only real way to break > the log-jam is to come up with a killer app, which relies on some > feature you want to proselytize. No app has to critically rely on fast dir search for it to be useful. It can be done (almost) transparently and most all look ups will speedup. Store a "dir type code" somewhere in the dir. inode. Use that to select the appropriate function table from namei(). Add a way to convert between dir types. 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?200205042039.QAA16949>