apache / apache/opendal

new feature: add AimdLayer for adaptive request-rate control

Open
#8,036 0 comments 2 reactions 0 assignees View on GitHub
core enhancement releases-note/feat
Dominant language
Rust
Stars
5.4k
Forks
825
Avg merge
1d 14m
Merged PRs (30d)
127

Description

## Feature Description

Add an optional `AimdLayer` that adaptively controls **operation rate** (ops/s) using AIMD (Additive Increase / Multiplicative Decrease).

`AimdLayer` should:

- Admit requests through a token bucket whose fill rate is controlled by an AIMD controller.
- Increase the rate additively after successful time windows.
- Decrease the rate multiplicatively when a window observes `ErrorKind::RateLimited`.
- Keep read / write / delete / list as independent rate controllers by default.
- Remain orthogonal to existing layers: it does **not** retry, and it does **not** replace byte-bandwidth or concurrency limits.

Proposed landing place:

- New crate: `core/layers/aimd` (`opendal-layer-aimd`)
- Facade feature: `layers-aimd`
- Public type: `opendal::layers::AimdLayer`

Recommended composition:

```rust
Operator::new(service)?
.layer(AimdLayer::default()) // inner: admit + observe every attempt
.layer(RetryLayer::default()); // outer: retry temporary errors
```

With this order, every retry attempt still acquires a token and feeds throttle outcomes back into AIMD.

## Problem and Solution

### Problem

Cloud object stores often throttle clients with HTTP 429 / SlowDown / similar signals. In distributed workloads, many independent workers share one backend without a central coordinator:

- Fixed concurrency (`ConcurrentLimitLayer`) only caps in-flight requests; it does not converge to backend capacity.
- Fixed bandwidth (`ThrottleLayer`) limits bytes/s locally; it does not react to backend request-rate limits.
- Retry (`RetryLayer`) recovers single temporary failures, but retry storms can amplify overload when many workers retry together.

OpenDAL already maps throttle responses to `ErrorKind::RateLimited` (and usually marks them temporary). What is missing is a first-class adaptive request-rate controller that uses that signal.

Downstream projects such as Lance already implemented this outside OpenDAL (`AimdThrottledStore`), but had to detect throttle errors via fragile string matching on `object_store` errors. OpenDAL can provide a cleaner shared implementation because throttle taxonomy is already part of the public error model.

### Proposed design

Introduce `AimdLayer` as a new optional layer with clear responsibility boundaries:

| Layer | Controls | Adjusts by | Owns retry? |
|-------|----------|------------|-------------|
| `RetryLayer` | whether to try again | `Error::is_temporary()` | yes |
| `ConcurrentLimitLayer` | in-flight concurrency | fixed semaphore | no |
| `ThrottleLayer` | byte bandwidth (bytes/s) | fixed GCRA quota | no |
| **`AimdLayer` (new)** | request rate (ops/s) | `ErrorKind::RateLimited` feedback | **no** |

Core algorithm (aligned with battle-tested Lance AIMD):

1. Record outcomes in a discrete time window.
2. At window end:
- if throttle ratio exceeds threshold: `rate = max(rate * decrease_factor, min_rate)`
- otherwise: `rate = min(rate + additive_increment, max_rate)`
3. Enforce the current rate with a token bucket. Allow tokens to go negative so waiters queue instead of waking as a thundering herd.
4. Treat non-`RateLimited` errors as non-capacity outcomes (do not decrease rate).

Public contracts / invariants:

- Only `ErrorKind::RateLimited` triggers multiplicative decrease by default.
- Empty windows do not adjust the rate.
- Rate stays within configured `[min_rate, max_rate]`.
- API semantics of underlying services stay unchanged; only request pacing changes.
- Optional feature; disabled by default; no behavior change for existing users.

Out of scope for v1:

- Folding AIMD into `RetryLayer`
- Changing `ThrottleLayer` byte-bandwidth semantics
- Perfect per-page accounting for every streaming list implementation (use a practical approximation: acquire on list start, observe on list progression)

### Implementation sketch

1. Add `AimdConfig`, `AimdController`, token-bucket admission, and `AimdLayer` under `core/layers/aimd`.
2. Wire facade feature `layers-aimd` and re-export from `opendal::layers`.
3. Cover with fault-injection tests: increase, decrease, floor/ceiling, per-category isolation, and composition with `RetryLayer` so each attempt is observed.
4. Document layer order and responsibility boundaries next to `RetryLayer` / `ThrottleLayer` / `ConcurrentLimitLayer`.

## Additional Context

Related prior art in Lance:

- Feature request: https://github.com/lance-format/lance/issues/6235
- Implementation: https://github.com/lance-format/lance/pull/6266
- Algorithm: `lance-core` AIMD controller + `lance-io` `AimdThrottledStore`
- Related OpenDAL retry wiring in Lance: https://github.com/lance-format/lance/pull/8363 (Retry only; not AIMD)

OpenDAL already has the key building block for clean feedback: services such as S3/GCS/TOS map 429 / SlowDown / TooManyRequests to `ErrorKind::RateLimited`.

If this lands in OpenDAL, downstream OpenDAL users (including Lance's OpenDAL-backed stores) can compose:

```text
RetryLayer -> AimdLayer -> ConcurrentLimitLayer? -> ThrottleLayer? -> Service
```

instead of maintaining a separate adaptive throttle wrapper on top of `object_store`.

## Are you willing to contribute to the development of this feature?

- [x] Yes, I am willing to contribute to the development of this feature.

Contributor guide

Open the contributing guide

Research direction

Start by reading the existing layer implementations around core/layers and the facade wiring for optional features. Use the proposed core/layers/aimd crate, layers-aimd feature, and opendal::layers re-export as the entry points, then review RetryLayer, ThrottleLayer, and ConcurrentLimitLayer boundaries. Done means fault-injection coverage for increase, decrease, bounds, category isolation, and RetryLayer composition, plus documentation of layer ordering.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
backend, performance
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Quiet
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.