Since 30 years ago (starting with XFS in 1993, which was inspired by HPFS) all the good UNIX file systems implement the directories as some kind of B trees.
Therefore they do not get slower proportional to the number of entries and listing based on file prefixes is extremely fast.
Resolving random file system paths still gets slower proportional to their depth, which is not the case for S3, where the prefix is on the entire object key and not just the "basename" part of it, like in a filesystem.
Yes they do. What APIs does Linux offer that allows you to list a directories contents alphabetically starting at a specific filename in constant time? You have to iterate the directory contents.
You can maybe use “d_off” with readdir in some way, but that’s specific to the filesystem. There’s no portable way to do this with POSIX.
Regardless of if you can do it with a single directory, you can’t do it for all files recursively under a given prefix. You can’t just ignore directories, or say that “for this list request, ‘-‘ is my directory separator”.
The use of b-trees in file systems is completely beside the point.
The POSIX API is indeed even older, so it is not helpful.
But as you say, there are filesystem-specific methods or operating-system specific methods to reach the true performance of the filesystem.
It is likely that for maximum performance one would have to write custom directory search functions using directly the Linux syscalls, instead of using the standard libc functions, but I would rather do that instead of paying for S3 or something like it.
Yes. You could also just use a SQLite table with two columns (path, contents), then just query that. Or do any number of other things.
The question isn’t if it’s possible, because of course it is, the question is if it’s portable and well supported with the POSIX interface. Because if it’s not, then…
> The question isn’t if it’s possible, because of course it is, the question is if it’s portable and well supported with the POSIX interface. Because if it’s not, then…
Where did this goalpost come from? S3 is not portable or POSIX compliant.
From the article we're commenting on, which is comparing the interface of S3 to the POSIX interface. Not any given filesystem + platform specific interface.
The article starts out by making a comparison between the posix api filesystem calls and S3's api. The context is very much a comparison between those two api surface areas.
Therefore they do not get slower proportional to the number of entries and listing based on file prefixes is extremely fast.