new feature: add AimdLayer for adaptive request-rate control
- 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
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