Re: [reiserfs-dev] Re: Ext2 directory index: ALS paper and benchmarks

[Hans Reiser]

Ragnar Kjørstad wrote:

>On Sat, Dec 08, 2001 at 12:01:20AM +0300, Hans Reiser wrote:
>
>>>In the cases I've studied more closely (e.g. maildir cases) the problem
>>>with reiserfs and e.g. the tea hash is that there is no common ordering
>>>between directory entries, stat-data and file-data.
>>>
>>>When new files are created in a directory, the file-data tend to be
>>>allocated somewhere after the last allocated file in the directory. The
>>>ordering of the directory-entry and the stat-data (hmm, both?) are
>>>
>>no, actually this is a problem for v3.  stat data are time of creation 
>>ordered (very roughly speaking)
>>and directory entries are hash ordered, meaning that ls -l suffers a 
>>major performance penalty.
>>
>
>Yes, just remember that file-body ordering also has the same problem.
>(ref the "find . -type f | xargs cat > /dev/null" test wich I think
>represent maildir performance pretty closely)
>
>
>
So is this a deeply inherent drawback of offering readdir name orders 
that differ hugely from time of creation order?

The advantages of sorting for non-linear search time are obvious.....

I suppose we could use objectids based on the  hash of the first 
assigned filename plus a 60 bit global to the FS counter....

but it is too many bits I think.  I think that using substantially less 
than the full hash of the name that is used for directory entry keys  
doesn't work....  Comments welcome.  

Hans