You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@opendal.apache.org by "Xuanwo (via GitHub)" <gi...@apache.org> on 2025/04/28 06:08:36 UTC

Concurrent support for opendal list

GitHub user Xuanwo created a discussion: Concurrent support for opendal list

The issue of adding concurrent support for opendal list has been discussed for a long time: https://github.com/apache/opendal/issues/987.

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

https://user-images.githubusercontent.com/5351546/214228987-44ea1306-a175-4fee-8c36-636a84800342.png

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:

```rust
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:

```rust
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?

GitHub link: https://github.com/apache/opendal/discussions/6115

----
This is an automatically sent email for dev@opendal.apache.org.
To unsubscribe, please send an email to: dev-unsubscribe@opendal.apache.org


Re: Concurrent support for opendal list

Posted by "meteorgan (via GitHub)" <gi...@apache.org>.
GitHub user meteorgan edited a comment on the discussion: Concurrent support for opendal list

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).


GitHub link: https://github.com/apache/opendal/discussions/6115#discussioncomment-12966993

----
This is an automatically sent email for dev@opendal.apache.org.
To unsubscribe, please send an email to: dev-unsubscribe@opendal.apache.org


Re: Concurrent support for opendal list

Posted by "meteorgan (via GitHub)" <gi...@apache.org>.
GitHub user meteorgan added a comment to the discussion: Concurrent support for opendal list

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.


GitHub link: https://github.com/apache/opendal/discussions/6115#discussioncomment-12970013

----
This is an automatically sent email for dev@opendal.apache.org.
To unsubscribe, please send an email to: dev-unsubscribe@opendal.apache.org


Re: Concurrent support for opendal list

Posted by "erickguan (via GitHub)" <gi...@apache.org>.
GitHub user erickguan added a comment to the discussion: Concurrent support for opendal list

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

GitHub link: https://github.com/apache/opendal/discussions/6115#discussioncomment-13054632

----
This is an automatically sent email for dev@opendal.apache.org.
To unsubscribe, please send an email to: dev-unsubscribe@opendal.apache.org


Re: Concurrent support for opendal list

Posted by "erickguan (via GitHub)" <gi...@apache.org>.
GitHub user erickguan added a comment to the discussion: Concurrent support for opendal list

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

GitHub link: https://github.com/apache/opendal/discussions/6115#discussioncomment-13090716

----
This is an automatically sent email for dev@opendal.apache.org.
To unsubscribe, please send an email to: dev-unsubscribe@opendal.apache.org


Re: Concurrent support for opendal list

Posted by "Xuanwo (via GitHub)" <gi...@apache.org>.
GitHub user Xuanwo added a comment to the discussion: Concurrent support for opendal list

> I check the s3 list objects v1/v2 APIs, which return common prefixes. Thinking aloud with the API. What if users are listing:
> 
> ```rust
> 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?

GitHub link: https://github.com/apache/opendal/discussions/6115#discussioncomment-13088984

----
This is an automatically sent email for dev@opendal.apache.org.
To unsubscribe, please send an email to: dev-unsubscribe@opendal.apache.org


Re: Concurrent support for opendal list

Posted by "erickguan (via GitHub)" <gi...@apache.org>.
GitHub user erickguan added a comment to the discussion: Concurrent support for opendal list

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:

```rust
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.

GitHub link: https://github.com/apache/opendal/discussions/6115#discussioncomment-13088176

----
This is an automatically sent email for dev@opendal.apache.org.
To unsubscribe, please send an email to: dev-unsubscribe@opendal.apache.org


Re: Concurrent support for opendal list

Posted by "Xuanwo (via GitHub)" <gi...@apache.org>.
GitHub user Xuanwo added a comment to the discussion: Concurrent support for opendal list

> 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`.

GitHub link: https://github.com/apache/opendal/discussions/6115#discussioncomment-12967642

----
This is an automatically sent email for dev@opendal.apache.org.
To unsubscribe, please send an email to: dev-unsubscribe@opendal.apache.org


Re: Concurrent support for opendal list

Posted by "Xuanwo (via GitHub)" <gi...@apache.org>.
GitHub user Xuanwo edited a discussion: Concurrent support for opendal list

The issue of adding concurrent support for opendal list has been discussed for a long time: https://github.com/apache/opendal/issues/987.

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

![](https://user-images.githubusercontent.com/5351546/214228987-44ea1306-a175-4fee-8c36-636a84800342.png)

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:

```rust
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:

```rust
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?

GitHub link: https://github.com/apache/opendal/discussions/6115

----
This is an automatically sent email for dev@opendal.apache.org.
To unsubscribe, please send an email to: dev-unsubscribe@opendal.apache.org


Re: Concurrent support for opendal list

Posted by "meteorgan (via GitHub)" <gi...@apache.org>.
GitHub user meteorgan added a comment to the discussion: Concurrent support for opendal list

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).


GitHub link: https://github.com/apache/opendal/discussions/6115#discussioncomment-12966993

----
This is an automatically sent email for dev@opendal.apache.org.
To unsubscribe, please send an email to: dev-unsubscribe@opendal.apache.org


Re: Concurrent support for opendal list

Posted by "leiysky (via GitHub)" <gi...@apache.org>.
GitHub user leiysky added a comment to the discussion: Concurrent support for opendal list

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.

GitHub link: https://github.com/apache/opendal/discussions/6115#discussioncomment-12977456

----
This is an automatically sent email for dev@opendal.apache.org.
To unsubscribe, please send an email to: dev-unsubscribe@opendal.apache.org


Re: Concurrent support for opendal list

Posted by "Xuanwo (via GitHub)" <gi...@apache.org>.
GitHub user Xuanwo edited a comment on the discussion: Concurrent support for opendal list

> I check the s3 list objects v1/v2 APIs, which return common prefixes. Thinking aloud with the API. What if users are listing:
> 
> ```rust
> 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?

GitHub link: https://github.com/apache/opendal/discussions/6115#discussioncomment-13088984

----
This is an automatically sent email for dev@opendal.apache.org.
To unsubscribe, please send an email to: dev-unsubscribe@opendal.apache.org