Concurrent support for opendal list

[Xuanwo]

The issue of adding concurrent support for opendal list has been discussed for a long time: #987.

Listing a large prefix on S3 is a very slow process, as demonstrated in this image.

It would be a great improvement for OpenDAL to support concurrent list. The challenge is how to offer this as a user-friendly and effective API.

---

My current idea is that we can introduce a partitions option for list. The partitions must not overlap to ensure that the list returns only unique results.

The usage will be like:

let result = op
    .list_with("dir/")
    .partitions(["a", "m"])
    .await?;

opendal will start three list underhood: list("dir/"), list("dir/a"), list("dir/m"). Users can speed up the process by adding concurrent for them:

let result = op
    .list_with("dir/")
    .partitions(["a", "m"])
    .concurrent(3)
    .await?;

After adding partitions, the return results is not in order anymore.

---

What do you think?

[meteorgan]

Is this feature primarily intended for recursive directory listing ?
Could we design it like this ?

1. perform a non-recursive list("dir/") operation.
2. divide the result from step 1 into some groups and list every group concurrently.

The drawback is that determining an optimal splitting strategy may be challenging, but this challenge also applies in manual partitioning(maybe users have prior knowledge to guide their partitioning strategy).

[Xuanwo]

Is this feature primarily intended for recursive directory listing ?

No, it also works for non-recursive lists, as long as the service supports starts_with.

For example, S3 services can list very large directories this way.

Could we design it like this ?

1. perform a non-recursive list("dir/") operation.
2. divide the result from step 1 into some groups and list every group concurrently.

Nice idea. I didn't choose this option because it relies heavily on assumptions about the users' file structures. If our assumptions are incorrect, the resulting cost could be significant, which would go against our promise of "Fast Access" with zero overhead.

For example, users can

Have only one-level of paths. For example, a/1, a/2,.., a/1000000.

Perform a non-recursive list("dir/") operation can lead a full list and there is no place for partitions to take effects.

Have extremely number of directories, but each one contains only a small number of files. For example, it's common for users to have hash-prefixed directory structures like a9/f8/a9f8xxxxxxxx. If we group them based on either the a or a9 layers, it can lead to undesirable results.

So, my current idea is that instead of making assumptions about the user's file structure, it's better to let users decide how to split the partitions.

[meteorgan]

Understood. I initially misunderstood your solution. The partitions(["a", "m"]) approach implies three list operations: from dir/ to dir/a, from dir/a to dir/m and from dir/m onward, not three list operations: list("dir/a"), list("dir/m") and others.

[leiysky]

This is great, we are currently simulating concurrent listing by manually listing different prefix, this API will fit our requirement very well.

BTW, here's an example for reference, OSS cost about 1 second to perform a single DeleteObjects requests, without concurrent listing it will be a disaster to delete a large prefix.

[erickguan]

I skimmed s3 list objects v2. I am not sure if s3 will return objects as contents or common prefixes. Will check this.

[erickguan]

A neat API. partition and concurrent work great with multiple requests. Also, s3 directories are mostly designed when developers want performance.

I check the s3 list objects v1/v2 APIs, which return common prefixes. Thinking aloud with the API. What if users are listing:

let result = op
    .list_with("di")
    .partitions(["r", "m"])
    .concurrent(3)
    .await?;

Use s3 as an example, we will request:

• di
• dir
• dim

This will result in some repetitive entries. So I assume this API must be used when listing a dir/. A little incoherent when .partitions doesn't have effect when not listing a directory but also doesn't hurt.

[Xuanwo]

I check the s3 list objects v1/v2 APIs, which return common prefixes. Thinking aloud with the API. What if users are listing:

let result = op
    .list_with("di")
    .partitions(["r", "m"])
    .concurrent(3)
    .await?;

Use s3 as an example, we will request:

• di
• dir
• dim

In fact, we will list the following range:

• di..dir
• dir..dim
• dim..

Underhood, we will have something like the following three concurrent list:

• op.lister("di").take_while(|v|future::ready(v.path < "dir"))
• op.lister("dir").take_while(|v|future::ready(v.path < "dim"))
• op.lister("dim")

So, opendal will guarantee that the lister returns non-overlapping results after partitioning.

Maybe we can add some validation here or just sort input partitions?

[erickguan]

Aha, makes sense! Sorting is good enough because the potential list is likely to be small.