new feature: add AimdLayer for adaptive request-rate control

[Xuanwo]

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:

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: Feature Request: Implement AIMD (Additive Increase/Multiplicative Decrease) Adaptive Retry lance-format/lance#6235
• Implementation: feat: add aimd throttled object store lance-format/lance#6266
• Algorithm: lance-core AIMD controller + lance-io AimdThrottledStore
• Related OpenDAL retry wiring in Lance: feat(io): add retry support for OpenDAL stores lance-format/lance#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:

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?

• Yes, I am willing to contribute to the development of this feature.