6 ms·
> And listing files is slow. While the joy of Amazon S3 is that you can read and write at extremely, extremely, high bandwidths, listing out what is there is mu
by orf 3y ago
> And listing files is slow. While the joy of Amazon S3 is that you can read and write at extremely, extremely, high bandwidths, listing out what is there is much much slower. Slower than a slow local filesystem
This misses something critical. Yes, s3 has fast reading and writing, but that’s not really what makes it useful.
What makes it useful is listing. In an unversioned bucket (or one with no delete markers), listing any given prefix is essentially constant time: I can take any given string, in a bucket with 100 billion objects, and say “give me the next 1000 keys alphabetically that come after this random string”.
What’s more, using “/“ as a delimiter is just the default - you can use any character you want and get a set of common prefixes. There are no “directories”, ”directories” are created out of thin air on demand.
This is super powerful, and it’s the thing that lets you partition your data in various ways, using whatever identifiers you need, without worrying about performance.
If listing was just “slow”, couldn’t list on file prefixes and got slower proportional to the number of keys (I.e a traditional unix file system), then it wouldn’t be useful at all.
- adrian_b 3y agoSince 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.
- orf 3y agoYes 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.
- adrian_b 3y agoThe 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.
- orf 3y agoYes. 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…
- anamexis 3y ago> 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.
- nh2 3y ago> listing based on file prefixes is extremely fast This functionality does not exist to my knowledge. ext4 and XFS return directory entries in pseudo-random order (due to hashing), not lexicographically. For an example, see e.g. https://righteousit.wordpress.com/2022/01/13/xfs-part-6-btree-directories/ https://righteousit.wordpress.com/2022/01/13/xfs-part-6-btre... If you know a way to return lexicographical order directly from the file system, without the need to sort, please link it.
- kbolino 3y agoResolving 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.
- jacobsimon 3y agoWhat is it about S3 that enables this speed, and why can’t traditional Unix file systems do the same?
- orf 3y agoS3 doesn’t have directories, it could be thought of a flat + sorted list of keys. UNIX (and all operating systems) differentiate between a file and a directory. To list the contents of a directory, you need to make an explicit call. That call might return files or directories. So to list all files recursively, you need to list, sort, check if an entry is a directory, recurse”. This isn’t great.
- bradleyjg 3y agoCode written against s3 is not portable either. It doesn’t support azure or gcp, much less some random proprietary cloud.
- arcfour 3y agoI've seen several S3-compatible APIs and there are open-source clients. If anything it's the de-facto standard.
- zaphar 3y agoGCP storage buckets implement the S3 api. You can treat them like they were an s3 bucket. Something I do all the time.
- cuno 3y agoActually we've found it's often much worse than that. Code written against AWS S3 using the AWS SDK often doesn't work on a great many "S3-compatible" vendors (including on-prem versions). Although there's documentation on S3, it's vague in many ways, and the AWS SDKs rely on actual AWS behaviour. We've had to deal with a lot of commercial and cloud vendors that subtly break things. This includes giant public cloud companies. In one case a giant vendor only failed at high loads, making it appear to "work" until it didn't, because its backoff response was not what the AWS SDK expected. It's been a headache that we've had to deal for cunoFS, as well as making it work with GCP and Azure. At the big HPC conference Supercomputing 2023, when we mentioned supporting "S3 compatible" systems, we would often be told stories about applications not working with their supposedly "S3 compatible" one (from a mix of vendors).
- aeyes 3y agoAnd if for some reason you need a complete listing along with object sizes and other attributes you can get one every 24 hours with S3 inventory report. That has always been good enough for me.
- harshaw 3y agoWhen you have billions of objects this is really the only way to go - and build workflows around inventory (including athena, spark, etc)
- tjoff 3y agoIs listing really such a key feature that people use it as a database to find objects? Have not used S3, but that is not how I imagined using it.
- orf 3y agoSure. It's kind of an index - limited to prefix-only searching, but useful. Say you store uploads associated with a company and a user. You'd maybe naively store them as `[company-uuid]/[user-id].[timestamp]`. If you need to list a given users (123) uploads after a given date, you'd list keys after `[company-uuid]/123.[date]`. If you need to list all users uploads, you'd list `[company-uuid]/123.`. If you need to get a set of all users who have photos, you'd list `[company-uuid]/` with a Delimiter set to `.` The point is that it's flexible and with a bit of thought it allows you to "remove all a users uploads between two dates", "remove all a companies uploads" or "remove all a users uploads" with a single call. Or whatever specific stuff is important to your use-case, that might otherwise need a separate DB. It's not perfect - you can't reverse the listing (i.e you can't get the latest photo for a given user by sorting descending for example), and needs some thought about your key structure.
- tjoff 3y agoBut surely you need to track that elsewhere anyway? That some niche edge-case runs efficiently doesn't sound like a defining feature of S3. On the contrary many common operations map terrible to S3, so you kind of need the logic to be elsewhere.
- orf 3y agoMy overall point can be summarised as this: - Listing things is a very common operation to do. - The POSIX api and the directory/file hierarchy it provides is a restrictive one. - S3 does not suffer from this, you can recursively list and group keys into directories at “list time”. - If you find yourself needing to list gigantic numbers of keys in one go, you can do better by only listing a subset. S3 isn’t a filesystem, you shouldn’t need to list 1k+ keys sequentially apart from during maintenance tasks. - This is actually quite fast, compared to alternatives. Whether or not you see a use case for this is sort of irrelevant: they exist. it’s what allows you to easily put data into s3 and flexibly group/scan it by specific attributes.
- calpaterson 3y agoI have to say that I'm not hugely convinced. I don't really think that being able to pull out the keys before or after a prefix is particularly impressive. That is the basis for database indices going back to the 1970s after all. Perhaps the use-cases you're talking about are very different from mine. That's possible of course. But for me, often the slow speed of listing the bucket gets in the way. Your bucket doesn't have to get very big before listing the keys takes longer than reading them. I seem to remember that listing operations ran at sub-1mbps, but admittedly I don't have a big bucket handy right now to test that.
- orf 3y agoIt depends on a few factors. The list objects call hides deleted and noncurrent versions, but it has to skip over them. Grouping prefixes also takes time, if they contain a lot of noncurrent or deleted keys. A pathological case would be a prefix with 100 million deleted keys, and 1 actual key at the end. Listing the parent prefix takes a long time in this case - I’ve seen it take several minutes. If your bucket is pretty “normal” and doesn’t have this, or isn’t versioned, then you can do 4-5 thousand list requests a second, at any given key/prefix, in constant time. Or or you can explicitly list object versions (and not skip deleted keys) also in constant time. It all depends on your data: if you need to list all objects then yeah it’s gonna be slow because you need to paginate through all the objects. But the point is that you don’t have to do that if you don’t want to, unlike a traditional filesystem with a directory hierarchy. And this enables parallelisation: why list everything sequentially, when you can group the prefixes by some character (i.e “-“), then process each of those prefixes in parallel. The world is your oyster.
- cuno 3y agoWe and our customers use S3 as a POSIX filesystem, and we generally find it faster than a local filesystem for many benchmarks. For listing directories we find it faster than Lustre (a real high performance filesystem). Our approach is to first try listing directories with a single ListObjectV2 (which on AWS S3 is in lexicographic order) and if it hasn't made much progress, we start listing with parallel ListObjectV2. Once you start parallelising the ListObjectV2 (rather than sequentially "continuing") you get massive speedups.
- hayd 3y agoYou can set up cloud watch events to trigger a lambda function to store meta data about the s3 file in a regular database. That way you can index it how you expect to list. Very effective for our use case.
- deleted 3y ago[deleted]
- foldr 3y ago>What makes it useful is listing. I think 99% of S3 usage just consists of retrieving objects with known keys. It seems odd to me to consider prefix listing as a key feature.
- bostik 3y agoWhen you embed the relevant (not necessarily that of object creation) timestamp as a prefix, it sure becomes one. Whether that prefix is part of the "path" (object/path/prefix/with/<4-digit year/)" or directly part of the basename (object/path/prefix/to/app-specific/files/<4-digit year>-<2-digit month>-....), being able to limit the search space server-side becomes incredibly useful. You can try it yourself: list objects in a bucket prefix with lots of files, and measure the time it takes to list all of them vs. the time it takes to list only a subset of them that share a common prefix.
- gamache 3y ago> ...listing any given prefix is essentially constant time: I can take any given string, in a bucket with 100 billion objects, and say “give me the next 1000 keys alphabetically that come after this random string”. I'm not sure we agree on the definition of "constant time" here. Just because you get 1000 keys in one network call doesn't imply anything about the complexity of the backend!
- orf 3y agoConstant time irregardless of the number of objects in the bucket and irregardless of the initial starting position of your list request.
- hobobaggins 3y agoThe technical implementation is indeed impressive that it operates more-or-less within constant time, but probably very few use cases actually fit that narrow window, so this technical strength is moot when it comes to actual usage. Since each request is dependent upon the position received in the last request, 1000 arbitrary keys on your 3rd or 1000th attempt doesn't really help unless you found your needle in the haystack in that request (and in that case the rest of that 1000 key listing was wasted.)
- orf 3y agoYou’re assuming you’re paginating through all objects from start to finish. A request to list objects under “foo/“ is a request to list all objects starting with “foo/“, which is constant time irregardless of the number of keys before. Same applies for “foo/bar-“, or any other list request for any given prefix. There are no directories on s3.
- nh2 3y agoThe key difference between lexicographically keyed flat hierarchies, and directory-nested filesystem hierarchies, becomes clear based on this example: dir1/a/000000 dir1/a/... dir1/a/999999 dir1/b On a proper hierarchical file file system with directories as tree interior nodes, `ls dir1/` needs to traverse and return only 2 entries ("a" and "b"). A flat string-indexed KV store that only supports lexicographic order, without special handling of delimters, needs to traverse 1 million dirents ("a/00000" throuh "a/999999") before arriving at "b". Thus, simple flat hierarchies are much slower at listing the contents of a single dir: O(all recursive children), vs. O(immediate children) on a "proper" filesystem. Lexicographic strings cannot model multi-level tree structures with the same complexities; this may give it the reputation of "listing files is slow". UNLESS you tell the listing algorithm what the delimter character is (e.g. `/`). Then a lexicographical prefix tree can efficiently skip over all subtrees at the next `/`. Amazon S3 supports that, with the docs explicitly mentioning "skipping over and summarizing the (possibly millions of) keys nested at deeper levels" in the `CommonPrefixes` field: https://docs.aws.amazon.com/AmazonS3/latest/userguide/using-prefixes.html#prefixes-list-example https://docs.aws.amazon.com/AmazonS3/latest/userguide/using-... I have not tested whether Amazon's implemented actually saves the traversal (or whether it traverses and just returns less results), but I'd hope so.
- nh2 3y agoFor completeness: The orignal post says: S3 has no rename or move operation. Renaming is CopyObject and then DeleteObject. CopyObject takes linear time to the size of the file(s). This comes up fairly often when someone has written a lot of files to the wrong place - moving the files back is very slow. This is right: In a normal file system, renaming a directory is fast O(1), in S3 it's slow O(all recursive children). And Amazon S3 has not added a delimiter-based function to reduce its complexity, even though that would be easily possible in a lexicographic prefix tree (re-rooting the subtree). So here the original post has indeed found a case where S3 is much slower than a normal file system.