Re: [Bug 417] New: htree much slower than regular ext3

Daniel Phillips
2003-03-07T17:24:11Z

On Fri 07 Mar 03 16:46, Alex Tomas wrote:
> Hi!
>
> The problem is that getdents(2) returns inodes out of order and
> du causes many head seeks. I tried to solve the problem by patch
> I included in. The idea of the patch is pretty simple: just try
> to sort dentries by inode number in readdir(). It works because
> inodes sits at fixed places in ext2/ext3. Please, look at results
> I just got:
>
> real user sys
>
> ext3+htree: 7m22.236s 0m0.292s 0m2.204s
> ext3-htree: 3m6.539s 0m0.481s 0m2.278s
> [...]
> ext3+sd-30: 2m39.658s 0m0.492s 0m2.138s

Nice. I posted a similar demonstration some time ago (could it *really* be
two years?) but I sorted the dirents in user space, which meant it was just a
demonstration, not a practical solution.

The problem I see with your approach is that the traversal is no longer in
hash order, so a leaf split in the middle of a directory traversal could
result in a lot of duplicate dirents. I'm not sure there's a way around that.

Another approach is to have the inode number correspond approximately to the
hash value. That's not as hard as it sounds, it simply means that the goal
for ext3_new_inode should be influenced by the hash value. (But watch out
for interaction with the new Orlov allocator.) It also depends on some
a priori estimate of the size of a directory so that increasing hash values
can be distributed more or less uniformly and monotonically across some
corresponding range of inode numbers. This isn't too hard either, just round
up the current size of the directory to a power of two and use that as the
size estimate. The size estimate would change from time to time over the
life of the directory, but there are only log N different sizes and that's
roughly how heavy the load on the inode cache would be during a directory
traversal. Finally, a nice property of this approach is that it stays stable
over many creates and deletes.

We've apparently got a simpler problem though: inode numbers aren't allocated
densely enough in the inode table blocks. This is the only thing I can think
of that could cause the amount of thrashing we're seeing. Spreading inode
number allocations out all over a volume is ok, but sparse allocation within
each table block is not ok because it multiplies the pressure on the cache.
We want a 30,000 entry directory to touch 1,000 - 2,000 inode table blocks,
not the worst-case 30,000. As above, fixing this comes down to tweaking the
ext3_new_inode allocation goal.

Regards,

Daniel