Swift Async Algorithms Proposal: Rate Limiters

Rate Limiting

Source | Tests
Source | Tests

  • Decision Notes:
  • Bugs:

Introduction

When events can potentially happen faster than the desired consumption rate, there are multiple ways to handle the situation. One approach is to only emit values after a given period of time of inactivity, or "quiescence", has elapsed. This algorithm is commonly referred to as debouncing. A very close reelativee is an apporach to emit values after a given period has elapsed. These emitted values can be reduced from the values encountered during the waiting period. This algorithm is commonly referred to as throttling.

Proposed Solution

The debounce algorithm produces elements after a particular duration has passed between events. It transacts within a given tolerance applied to a clock. If values are produced by the base AsyncSequence during this quiet period, the debounce does not resume its next iterator until the period has elapsed with no values are produced or unless a terminal event is encountered.

The interface for this algorithm is available on all AsyncSequence types where the base type, iterator, and element are Sendable, since this algorithm will inherently create tasks to manage their timing of events. A shorthand implementation will be offered where the clock is the ContinuousClock, which allows for easy construction with Duration values.

extension AsyncSequence {
  public func debounce<C: Clock>(
    for interval: C.Instant.Duration, 
    tolerance: C.Instant.Duration? = nil, 
    clock: C
  ) -> AsyncDebounceSequence<Self, C>
  
  public func debounce(
    for interval: Duration, 
    tolerance: Duration? = nil
  ) -> AsyncDebounceSequence<Self, ContinuousClock>
}

This all boils down to a terse description of how to transform the asynchronous sequence over time.

fastEvents.debounce(for: .seconds(1))

In this case it transforms a potentially fast asynchronous sequence of events into one that waits for a window of 1 second with no events to elapse before emitting a value.

The throttle algorithm produces elements such that at least a specific interval has elapsed between them. It transacts by measuring against a specific clock. If values are produced by the base AsyncSequence the throttle does not resume its next iterator until the period has elapsed or unless a terminal event is encountered.

The interface for this algorithm is available on all AsyncSequence types. Unlike other algorithms like debounce, the throttle algorithm does not need to create additional tasks or require any sort of tolerance because the interval is just measured. A shorthand implementation will be offered in conjunction where the clock is the ContinuousClock, which allows for easy construction with Duration values. An additional shorthand is offered to reduce the values such that it provides a "latest" or "earliest" value, representing the leading or trailing edge of a throttled region of production of events.

extension AsyncSequence {
  public func throttle<C: Clock, Reduced>(
    for interval: C.Instant.Duration, 
    clock: C, 
    reducing: @Sendable @escaping (Reduced?, Element) async -> Reduced
  ) -> AsyncThrottleSequence<Self, C, Reduced>
  
  public func throttle<Reduced>(
    for interval: Duration, 
    reducing: @Sendable @escaping (Reduced?, Element) async -> Reduced
  ) -> AsyncThrottleSequence<Self, ContinuousClock, Reduced>
  
  public func throttle<C: Clock>(
    for interval: C.Instant.Duration, 
    clock: C, 
    latest: Bool = true
  ) -> AsyncThrottleSequence<Self, C, Element>
  
  public func throttle(
    for interval: Duration, 
    latest: Bool = true
  ) -> AsyncThrottleSequence<Self, ContinuousClock, Element>
}

This all boils down to a terse description of how to transform the asynchronous sequence over time.

fastEvents.throttle(for: .seconds(1))

In this case, the throttle transforms a potentially fast asynchronous sequence of events into one that waits for a window of 1 second to elapse before emitting a value.

Detailed Design

Debounce

The type that implements the algorithm for debounce emits the same element type as the base that it applies to. It also throws when the base type throws (and likewise does not throw when the base type does not throw).

public struct AsyncDebounceSequence<Base: AsyncSequence, C: Clock>: Sendable
  where Base.Element: Sendable, Base: Sendable {
}

extension AsyncDebounceSequence: AsyncSequence {
  public typealias Element = Base.Element
  
  public struct Iterator: AsyncIteratorProtocol {
    public mutating func next() async rethrows -> Base.Element? 
  }
  
  public func makeAsyncIterator() -> Iterator
}

Since the stored types comprising AsyncDebounceSequence must be Sendable; AsyncDebounceSequence is unconditionally always Sendable. It is worth noting that the iterators are not required to be Sendable.

Throttle

The type that implements the algorithm for throttle emits the same element type as the base that it applies to. It also throws when the base type throws (and likewise does not throw when the base type does not throw).

public struct AsyncThrottleSequence<Base: AsyncSequence, C: Clock, Reduced> {
}

extension AsyncThrottleSequence: AsyncSequence {
  public typealias Element = Reduced
  
  public struct Iterator: AsyncIteratorProtocol {
    public mutating func next() async rethrows -> Reduced?
  }
  
  public func makeAsyncIterator() -> Iterator
}

extension AsyncThrottleSequence: Sendable 
  where Base: Sendable, Element: Sendable { }

The AsyncThrottleSequence is conditionally Sendable if the base types comprising it are Sendable.

The time in which events are measured are from the previous emission if present. If a duration has elapsed between the last emission and the point in time the throttle is measured then that duration is counted as elapsed. The first element is considered not throttled because no interval can be constructed from the start to the first element.

Alternatives Considered

An alternative form of debounce could exist similar to the reductions of throttle, where a closure would be invoked for each value being set as the latest, and reducing a new value to produce for the debounce.

It was considered to only provide the "latest" style APIs, however the reduction version grants more flexibility and can act as a funnel to the implementations of latest.

Credits/Inspiration

The naming for debounce comes as a term of art; originally this term was inspired by electronic circuitry. When a physical switch closes a circuit it can easily have a "bouncing" behavior (also called chatter) that is caused by electrical contact resistance and the physical bounce of springs associated with switches. That phenomenon is often addressed with additional circuits to de-bounce (removing the bouncing) by ensuring a certain quiescence occurs.

http://reactivex.io/documentation/operators/debounce.html

https://developer.apple.com/documentation/combine/publishers/debounce/

http://reactivex.io/documentation/operators/sample.html

https://developer.apple.com/documentation/combine/publishers/throttle/

11 Likes

When I was learning these operators, I would constantly have to check the definitions of throttle and debounce to determine what behaviour I really wanted or needed. For example, debounce is a pretty esoteric name (as explained in the Credits/Inspiration) and throttle isn't very clear on what side of a window of time you'll receive events.

So what do you think of the idea of also adding less obscure extensions on AsyncSequence? For example, off the top of my head (quality may vary!):

for await quake in quakes.last(within: .seconds(1)) {
   // this stream is debounced
}

for await quake in quakes.first(within: .seconds(1)) {
   // this stream is throttled
}

Even these names are not great because they might suggest a fixed windowing strategy. But I think you get the idea? To be clear, I'm suggesting a friendlier set of names in addition to the existing terms of art.

1 Like

Hi Philippe,

Great to see this being added, both are extremely useful additions.

The link to the debounce code gives a 404 and there's not corresponding source file in the repo?

Also, in alternatives considered it is ambiguous what is actually provided for debounce, the first part says that an alternative form could exist that does reduce similar to throttle, while the second part says that it was considered to only provide 'latest' style API but that reduction is more powerful - so I wanted to go to the source code (the 404) to see which one it was (hoping for optional reduction support for both cases).

Awesome to have reducing for throttle, looking forward to question above.

I need to spend some time digging into the implementation to see how it works (what are the implications of running e.g. a few thousand throttled sequences for example in terms of resource usage) - but will return with further questions in that case.

EDIT:

I found the missing path for anyone else (and the answer to the question - no reduction/conflation support for debounce) - the comment above about the alternatives considered unclarity remains (looks like initially reduction was supported but that it was changed...)

And on a bikeshed color note, I've encountered 'conflation' as the term of art for 'reduction' in the proposal many times, but just a side note - YMMV.

The standard library uses reduce, and the swift-algorithms package uses reductions so I think the naming on that is relatively codified and perhaps would feel weird going with a different name on that part.

1 Like

Fixed the link in the post. There recently was a refactor to adjust Sendable conformances and the source file had moved.

1 Like