> ...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!
The 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.)
You’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.
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!