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.
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.
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
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
jkroon@plastiekpoot /usr/portage $ find *-* -maxdepth 1 -type d | wc -l
jkroon@plastiekpoot /usr/portage $ for i in *-*; do echo $(find $i
-maxdepth 1 -type d | wc -l) $i; done | sort -g | tail -n10
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.