On 9/6/07, Scott Francis <darkuncle@gmail.com> wrote:
> Here's the question: how does number of objects at various levels in a
> directory structure affect memory allocation during object lookups?
> Say I'm doing a lookup on /foo/bar/baz/quux/file.jpg and /foo/bar/baz/
> contains 15000 objects (dirs and files). When I get to examining the
> contents of baz to find the quux entry, do I have to allocate memory
> sufficient to temporarily store the entire contents of baz, or do I go
> through the objects in some kind of serial order until I find the one
> I'm looking for? I'm pretty sure it's the former, since going through
> in any kind of serial order would be tremendously slow for large
> numbers of objects. Knowing the relationship between number of objects
> in the CWD and amount of memory required to hash those object names
> would be very useful.

lookup proceeds in various stages:
first, element by element, from the root, look up each directory. if
it's in the cache, bing done, move on to the next part. if it's not,
we go to the filesystem and do the lookup, then cache the result.

everything that gets looked up is cached, but we only cache the things
we look for (not the the things that get looked "at" (during the
filesystem lookup part).

for ufs, the filesystem code reads the inode, finds the datablocks,
and starts trawling through in a linear order until it finds what we
want and return it (to be cached). linear lookup can be slow, so for
very large directories, ufs keeps its own hash of all directory
entries. this was added later.

but this is only for ufs, which stores directory contents unsorted.
netapps could easily store directories in a tree structure, making
lookup fast without excessive caching.