ext4 readdir performance - was Re: [gentoo-dev] New distfile mirror layout

[Richard Yao]

On 10/22/19 2:51 AM, Jaco Kroon wrote:
> Hi All,
>
>
> On 2019/10/21 18:42, Richard Yao wrote:
>>
>> If we consider the access frequency, it might actually not be that
>> bad. Consider a simple example with 500 files and two directory
>> buckets. If we have 250 in each, then the size of the directory is
>> always 250. However, if 50 files are accessed 90% of the time, then
>> putting 450 into one directory and that 50 into another directory, we
>> end up with the performance of the O(n) directory lookup being
>> consistent with there being only 90 files in each directory.
>>
>> I am not sure if we should be discarding all other considerations to
>> make changes to benefit O(n) directory lookup filesystems, but if we
>> are, then the hashing approach is not necessarily the best one. It is
>> only the best when all files are accessed with equal frequency, which
>> would be an incorrect assumption. A more human friendly approach might
>> still be better. I doubt that we have the data to determine that though.
>>
>> Also, another idea is to use a cheap hash function (e.g. fletcher) and
>> just have the mirrors do the hashing behind the scenes. Then we would
>> have the best of both worlds.
>
>
> Experience:
>
> ext4 sucks at targeting name lookups without dir_index feature (O(n)
> lookups - scans all entries in the folder).  With dir_index readdir
> performance is crap.  Pick your poison I guess.  Most of our larger
> filesystems (2TB+, but especially the 80TB+ ones) we've reverted to
> disabling dir_index as the benefit is outweighed by the crappy readdir()
> and glob() performance.
My read of the ext4 disk layout documentation is that the read operation
should work mostly the same way, except with a penalty from reading
larger directories caused by the addition of the tree's metadata and
from having more partially filled blocks:

https://ext4.wiki.kernel.org/index.php/Ext4_Disk_Layout#Directory_Entries

The code itself is the same traversal code:

https://github.com/torvalds/linux/blob/v5.3/fs/ext4/dir.c#L106

However, a couple of things stand out to me here at a glance:

1. `cond_resched()` adds scheduler delay for no apparent reason.
`cond_resched()` is meant to be used in places where we could block
excessively on non-PREEMPT kernels, but this doesn't strike me as one of
those places. The fact that we block on disk on uncached reads naturally
serves the same purpose, so an explicit rescheduling point here is
redundant. PREEMPT kernels should perform better in readdir() on ext4 by
virtue of making `cond_resched()` a no-op.

2. read-ahead is implemented in a way that appears to be over-reading
the directory whenever the needed information is not cached. This is
technically read-ahead, although it is not a great way of doing it. A
much better way to do this would be to pipeline `readdir()` by
initiating asynchronous read operations in anticipation of future reads.

Both of thse should affect both variants of ext4's directories, but the
penalties I mentioned earlier mean that the dir_index variant would be
affected more.

If you have a way to benchmark things, a simple idea to evaluate would
be deleting the `cond_resched()` line. If we had data showing an
improvement, I would be happy to send a small one-line patch deleting
the line to Ted to get the change into mainline.

> There doesn't seem to be a real specific tip-over point, and it seems to
> depend a lot on RAM availability and harddrive speed (obviously).  So if
> dentries gets cached, disk speeds becomes less of an issue.  However, on
> large folders (where I typically use 10k as a value for large based on
> "gut feeling" and "unquantifiable experience" and "nothing scientific at
> all") I find that even with lots of RAM two consecutive ls commands
> remains terribly slow. Switch off dir_index and that becomes an order of
> magnitude faster.
>
> I don't have a great deal of experience with XFS, but on those systems
> where we do it's generally on a VM, and perceivably (again, not
> scientific) our experience has been that it feels slower.  Again, not
> scientific, just perception.
>
> I'm in support for the change.  This will bucket to 256 folders and
> should have a reasonably even split between folders.  If required a
> second layer could be introduced by using the 3rd and 4th digits of the
> hash for a second layer.  Any hash should be fine, it really doesn't
> need to be cryptographically strong, it just needs to provide a good
> spread and be really fast.  Generally a hash table should have a prime
> number of buckets to assist with hash bias, but frankly, that's over
> complicating the situation here.
>
> I also agree with others that it used to be easy to get distfiles as and
> when needed, so an alternative structure could mirror that of the
> portage tree itself, in other words "cat/pkg/distfile". This perhaps
> just shifts the issue:
>
> jkroon@plastiekpoot /usr/portage $ find . -maxdepth 1 -type d -name
> "*-*" | wc -l
> 167
> jkroon@plastiekpoot /usr/portage $ find *-* -maxdepth 1 -type d | wc -l
> 19412
> jkroon@plastiekpoot /usr/portage $ for i in *-*; do echo $(find $i
> -maxdepth 1 -type d | wc -l) $i; done | sort -g | tail -n10
> 347 net-misc
> 373 media-sound
> 395 media-libs
> 399 dev-util
> 505 dev-libs
> 528 dev-java
> 684 dev-haskell
> 690 dev-ruby
> 1601 dev-perl
> 1889 dev-python
>
> So that's average 116 sub folders under the top layer (only two over
> 1000), and then presumably less than 100 distfiles maximum per package? 
> Probably overkill but would (should) solve both the too many files per
> folder as well as the easy lookup by hand issue.
>
> I don't have a preference on either solution though but do agree that
> "easy finding of distfiles" are handy.  The INDEX mechanism is fine for me.
>
> Kind Regards,
>
> Jaco
>