[API Proposal]: Generic Rate Limiter

[BrennanConroy]

Background and motivation

This is an extension of the rate limiter work that was merged earlier in 7.0. Now that we have the building blocks for rate limiting resources, we want to grow that story by providing an API to allow rate limiting more than just a single key. Today's APIs enable you to globally rate limit a resource, or manually have a list of limiters for specifics keys on a resource (think endpoints or specific users). With a generic rate limiter API, the user can define a rate limiter that accepts a type and uses that as a key for the rate limiter to lease the resource, queue the request, or reject the request, all while having different limits apply to different keys (Admin vs. normal user, per user, per endpoint).

Use cases include rate limiting HttpClient using the HttpRequestMessage and having different rates per endpoint and per user. Implementing a middleware in ASP.NET Core to limit incoming requests using HttpContext and having different rates per User, IP, etc.

API Proposal

The proposed API for generic rate limiters will follow the API for non-generic rate limiters, because it keeps the rate limiting APIs aligned and currently, we don't see any use cases that should cause the API to differ yet.

Abstract API

public abstract class GenericRateLimiter<TResource> : IAsyncDisposable, IDisposable
{
    public abstract int GetAvailablePermits(TResource resourceID);

    public RateLimitLease Acquire(TResource resourceID, int permitCount = 1);

    protected abstract RateLimitLease AcquireCore(TResource resourceID, int permitCount);

    public ValueTask<RateLimitLease> WaitAsync(TResource resourceID, int permitCount = 1, CancellationToken cancellationToken = default);

    protected abstract ValueTask<RateLimitLease> WaitAsyncCore(TResource resourceID, int permitCount, CancellationToken cancellationToken);

    protected virtual void Dispose(bool disposing) { }

    public void Dispose()
    {
       	// Do not change this code. Put cleanup code in 'Dispose(bool disposing)' method
        Dispose(disposing: true);
        GC.SuppressFinalize(this);
    }

    protected virtual ValueTask DisposeAsyncCore()
    {
        return default;
    }

    public async ValueTask DisposeAsync()
    {
        // Perform async cleanup.
        await DisposeAsyncCore().ConfigureAwait(false);

        // Dispose of unmanaged resources.
        Dispose(false);

        // Suppress finalization.
        GC.SuppressFinalize(this);
    }
}

What is more interesting IMO is the potential implementations of a GenericRateLimiter and if we can make it easier for users to create one.
A quick implementation would likely involve a dictionary with some sort of identifier (differs per resource type) for groups of resources and a different limiter for each group.
For example, if I want to group a resource like HttpRequestMessage by request paths I might write the following helper method to get a rate limiter that will be used by a GenericRateLimiter implementation:

private readonly ConcurrentDictionary<string, RateLimiter> _limiters = new();
private readonly RateLimiter _defaultLimiter = new TokenBucketRateLimiter(new TokenBucketRateLimiterOptions(1, QueueProcessingOrder.OldestFirst, 1, TimeSpan.FromSeconds(1), 1, true));
private RateLimiter GetRateLimiter(HttpRequestMessage resource)
{
    if (!_limiters.TryGetValue(resource.RequestUri.AbsolutePath, out var limiter))
    {
        if (resource.RequestUri.AbsolutePath.StartsWith("/problem", StringComparison.OrdinalIgnoreCase))
        {
            limiter = new ConcurrencyLimiter(new ConcurrencyLimiterOptions(1, QueueProcessingOrder.NewestFirst, 1));
        }
        else
        {
            limiter = _defaultLimiter;
        }
        limiter = _limiters.GetOrAdd(resource.RequestUri.AbsolutePath, limiter);
    }

    return limiter;
}

The above starts showing some of the complexities of implementing a GenericRateLimiter.

• Concurrent rate limiter creation, handled by TryGetValue and GetOrAdd on ConcurrentDictionary.
• Having a default rate limiter.
• Maintaining a large if else or switch statement for all the groupings.

And there are additional non-obvious concerns:

• Each "grouping" of resources should have its own collection of limiters, otherwise if there is a collision of group names (e.g. "Post" HTTP method and "Post" path) then the order of requests would add a different rate limiter to the cache and not work in the expected way.
• For the TokenBucket limiter (or any limiter that may use a timer for refreshing tokens) you should create a single timer instance and call refresh on all the TokenBucket limiters for efficiency.
• There should be some sort of heuristic to retire limiters (if the limiter has all permits it can be removed from the dictionary).
  To make GenericRateLimiter's easier to create we are proposing an API to be able to build an GenericRateLimiter and manage many of the complexities of implementing a custom GenericRateLimiter.

To make GenericRateLimiter's easier to create we are proposing an API to be able to build an GenericRateLimiter and manage many of the complexities of implementing a custom GenericRateLimiter.

Builder API

public class GenericRateLimitBuilder<TResource>
{
    public GenericRateLimitBuilder<TResource> WithPolicy<TKey>(Func<TResource, TKey?> keyFactory, Func<TKey, RateLimiter> limiterFactory) where TKey : notnull;

    public GenericRateLimitBuilder<TResource> WithConcurrencyPolicy<TKey>(Func<TResource, TKey?> keyFactory, ConcurrencyLimiterOptions options) where TKey : notnull;

    // Assuming we have a ReplenishingRateLimiter limiter abstract class
    // public GenericRateLimitBuilder<TResource> WithReplenishingPolicy(Func<TResource, TKey?> keyFactory, Func<TKey, ReplenishingRateLimiter> replenishingRateLimiter) where TKey : notnull;

    public GenericRateLimitBuilder<TResource> WithTokenBucketPolicy<TKey>(Func<TResource, TKey?> keyFactory, TokenBucketRateLimiterOptions options) where TKey : notnull;

    public GenericRateLimitBuilder<TResource> WithNoPolicy<TKey>(Func<TResource, bool> condition);

    // might want this to be a factory if the builder is re-usable
    public GenericRateLimitBuilder<TResource> WithDefaultRateLimiter(RateLimiter defaultRateLimiter);

    public GenericRateLimiter<TResource> Build();
}

Details:

• keyFactory is called to get a grouping identifier that the resource is part of, or null if the resource doesn't apply to the factory.
• The factories are called in order until one of them returns a non-null identifier and then the limiterFactory is called to get the RateLimiter to apply to the resource (cached in a dictionary for the next time that identifier is used).

Questions:

Should the Func<TKey, RateLimiter> parameters accept the TKey?
Should we provide Func<TKey, ValueTask<RateLimiter>> overloads? Would create sync-over-async when calling RateLimiter.Acquire().

One scenario that isn't handled by the builder proposed above is the ability to combine rate limiters. Imagine you want a global limiter of 100 concurrent requests to a service and also to have a per IP limit of 1 per second.
The builder pattern only supports running a single rate limiter so there needs to be some other way to "chain" rate limiters.
We believe this can be accomplished by providing a static method that accepts any number of GenericRateLimiters and combines them to create a single GenericRateLimiter that will run them in order when acquiring a lease.

Chained Limiter API

+ static GenericRateLimiter<TResource> CreateChainedRateLimiter<TResource>(IEnumerable<GenericRateLimiter<TResource>> limiters);

Additionally, we would like to add an interface for rate limiters that refresh tokens to make it easier to handle replenishing tokens from a single timer in generic code

Timer Based Limiter API addition

+ public interface IReplenishingRateLimiter
+ {
+     public abstract bool TryReplenish();
+     // public TimeSpan ReplenishRate { get; }
+ }

public sealed class TokenBucketRateLimiter
 : RateLimiter
+ , IReplenishingRateLimiter

Alternatively, we could use a new abstract class public abstract class ReplenishingRateLimiter : RateLimiter that the TokenBucketRateLimiter implements. Adding a class would add TryReplenish to the public API that a consumer might see (if they accepted ReplenishingRateLimiter instead of RateLimiter).

And finally, we would like to add an API for checking if a rate limiter is idle. This would be used to see which rate limiters are broadcasting that they aren't being used and we can potentially remove them from our GenericRateLimiter implementations cache to reduce memory. For example, ConcurrencyLimiter and TokenBucketRateLimiter are idle when they have all their permits.

Idle Limiter API Addition

public abstract class RateLimiter : IAsyncDisposable, IDisposable
{
+    public abstract DateTime? IdleSince { get; }
// alternatives
//    bool IsInactive { get; }
//    bool IsIdle { get; }
}

Alternatively, we could add an interface, IIdleRateLimiter, that limiters can choose to implement, but we think a first-class property is more appropriate in this scenario because you should be forced to implement the property to allow for book-keeping in the GenericRateLimiter.

API Usage

var builder = WebApplication.CreateBuilder(args);
builder.Services.AddHttpClient("RateLimited", o => o.BaseAddress = new Uri("http://localhost:5000"))
    .AddHttpMessageHandler(() =>
        new RateLimitedHandler(
            new GenericRateLimitBuilder<HttpRequestMessage>()
            // TokenBucketRateLimiter if the request is a POST
            .WithTokenBucketPolicy(request => request.Method.Equals(HttpMethod.Post) ? HttpMethod.Post : null,
                new TokenBucketRateLimiterOptions(1, QueueProcessingOrder.OldestFirst, 1, TimeSpan.FromSeconds(1), 1, true))
            // ConcurrencyLimiter if above limiter returns null and has a "cookie" header
            .WithPolicy(request => request.Headers.TryGetValues("cookie", out _) ? "cookie" : null,
                _ => new ConcurrencyLimiter(new ConcurrencyLimiterOptions(1, QueueProcessingOrder.NewestFirst, 1)))
            // Final fallback to a ConcurrencyLimiter per unique URI
            .WithConcurrencyPolicy(request => request.RequestUri,
                new ConcurrencyLimiterOptions(2, QueueProcessingOrder.OldestFirst, 2))
            .Build()));

// ...

var factory = app.Services.GetRequiredService<IHttpClientFactory>();
var client = factory.CreateClient("RateLimited");
var resp = await client.GetAsync("/problem");

Alternative Designs

Provide just the GenericRateLimiter<TResource> abstraction and don't provide a builder. This would require users to manually implement their own generic limiter implementations.

Provide a concrete GenericRateLimiter<TResource> implementation instead of a builder that has some customizability (options?) but would likely be less flexible and more opinionated.

Risks

The behavior of how the internal limiters in the generic limiter implementation are used is complex and needs to be well defined so users don't see unexpected behavior.

Providing an efficient generic implementation relies on additional features like ReplenishingRateLimiter and IdleSince to optimize Timer usage and memory usage.

[ghost]

Tagging subscribers to this area: @mangod9
See info in area-owners.md if you want to be subscribed.

Issue Details

---

Background and motivation

This is an extension of the rate limiter work that was merged earlier in 7.0. Now that we have the building blocks for rate limiting resources, we want to grow that story by providing an API to allow rate limiting more than just a single key. Today's APIs enable you to globally rate limit a resource, or manually have a list of limiters for specifics keys on a resource (think endpoints or specific users). With a generic rate limiter API, the user can define a rate limiter that accepts a type and uses that as a key for the rate limiter to lease the resource, queue the request, or reject the request, all while having different limits apply to different keys (Admin vs. normal user, per user, per endpoint).

Use cases include rate limiting HttpClient using the HttpRequestMessage and having different rates per endpoint and per user. Implementing a middleware in ASP.NET Core to limit incoming requests using HttpContext and having different rates per User, IP, etc.

API Proposal

The proposed API for generic rate limiters will follow the API for non-generic rate limiters, because it keeps the rate limiting APIs aligned and currently, we don't see any use cases that should cause the API to differ yet.

Abstract API

public abstract class GenericRateLimiter<TResource> : IAsyncDisposable, IDisposable
{
    public abstract int GetAvailablePermits(TResource resourceID);

    public RateLimitLease Acquire(TResource resourceID, int permitCount = 1);

    protected abstract RateLimitLease AcquireCore(TResource resourceID, int permitCount);

    public ValueTask<RateLimitLease> WaitAsync(TResource resourceID, int permitCount = 1, CancellationToken cancellationToken = default);

    protected abstract ValueTask<RateLimitLease> WaitAsyncCore(TResource resourceID, int permitCount, CancellationToken cancellationToken);

    protected virtual void Dispose(bool disposing) { }

    public void Dispose()
    {
       	// Do not change this code. Put cleanup code in 'Dispose(bool disposing)' method
        Dispose(disposing: true);
        GC.SuppressFinalize(this);
    }

    protected virtual ValueTask DisposeAsyncCore()
    {
        return default;
    }

    public async ValueTask DisposeAsync()
    {
        // Perform async cleanup.
        await DisposeAsyncCore().ConfigureAwait(false);

        // Dispose of unmanaged resources.
        Dispose(false);

        // Suppress finalization.
        GC.SuppressFinalize(this);
    }
}

What is more interesting IMO is the potential implementations of a GenericRateLimiter and if we can make it easier for users to create one.
A quick implementation would likely involve a dictionary with some sort of identifier (differs per resource type) for groups of resources and a different limiter for each group.
For example, if I want to group a resource like HttpRequestMessage by request paths I might write the following helper method to get a rate limiter that will be used by a GenericRateLimiter implementation:

private readonly ConcurrentDictionary<string, RateLimiter> _limiters = new();
private readonly RateLimiter _defaultLimiter = new TokenBucketRateLimiter(new TokenBucketRateLimiterOptions(1, QueueProcessingOrder.OldestFirst, 1, TimeSpan.FromSeconds(1), 1, true));
private RateLimiter GetRateLimiter(HttpRequestMessage resource)
{
    if (!_limiters.TryGetValue(resource.RequestUri.AbsolutePath, out var limiter))
    {
        if (resource.RequestUri.AbsolutePath.StartsWith("/problem", StringComparison.OrdinalIgnoreCase))
        {
            limiter = new ConcurrencyLimiter(new ConcurrencyLimiterOptions(1, QueueProcessingOrder.NewestFirst, 1));
        }
        else
        {
            limiter = _defaultLimiter;
        }
        limiter = _limiters.GetOrAdd(resource.RequestUri.AbsolutePath, limiter);
    }

    return limiter;
}

The above starts showing some of the complexities of implementing a GenericRateLimiter.

• Concurrent rate limiter creation, handled by TryGetValue and GetOrAdd on ConcurrentDictionary.
• Having a default rate limiter.
• Maintaining a large if else or switch statement for all the groupings.

And there are additional non-obvious concerns:

• Each "grouping" of resources should have its own collection of limiters, otherwise if there is a collision of group names (e.g. "Post" HTTP method and "Post" path) then the order of requests would add a different rate limiter to the cache and not work in the expected way.
• For the TokenBucket limiter (or any limiter that may use a timer for refreshing tokens) you should create a single timer instance and call refresh on all the TokenBucket limiters for efficiency.
• There should be some sort of heuristic to retire limiters (if the limiter has all permits it can be removed from the dictionary).
  To make GenericRateLimiter's easier to create we are proposing an API to be able to build an GenericRateLimiter and manage many of the complexities of implementing a custom GenericRateLimiter.

To make GenericRateLimiter's easier to create we are proposing an API to be able to build an GenericRateLimiter and manage many of the complexities of implementing a custom GenericRateLimiter.

Builder API

public class GenericRateLimitBuilder<TResource>
{
    public GenericRateLimitBuilder<TResource> WithPolicy<TKey>(Func<TResource, TKey?> keyFactory, Func<TKey, RateLimiter> limiterFactory) where TKey : notnull;

    public GenericRateLimitBuilder<TResource> WithConcurrencyPolicy<TKey>(Func<TResource, TKey?> keyFactory, ConcurrencyLimiterOptions options) where TKey : notnull;

    // Assuming we have a ReplenishingRateLimiter limiter abstract class
    // public GenericRateLimitBuilder<TResource> WithReplenishingPolicy(Func<TResource, TKey?> keyFactory, Func<TKey, ReplenishingRateLimiter> replenishingRateLimiter) where TKey : notnull;

    public GenericRateLimitBuilder<TResource> WithTokenBucketPolicy<TKey>(Func<TResource, TKey?> keyFactory, TokenBucketRateLimiterOptions options) where TKey : notnull;

    public GenericRateLimitBuilder<TResource> WithNoPolicy<TKey>(Func<TResource, bool> condition);

    // might want this to be a factory if the builder is re-usable
    public GenericRateLimitBuilder<TResource> WithDefaultRateLimiter(RateLimiter defaultRateLimiter);

    public GenericRateLimiter<TResource> Build();
}

Details:

• keyFactory is called to get a grouping identifier that the resource is part of, or null if the resource doesn't apply to the factory.
• The factories are called in order until one of them returns a non-null identifier and then the limiterFactory is called to get the RateLimiter to apply to the resource (cached in a dictionary for the next time that identifier is used).

Questions:

Should the Func<TKey, RateLimiter> parameters accept the TKey?
Should we provide Func<TKey, ValueTask<RateLimiter>> overloads? Would create sync-over-async when calling RateLimiter.Acquire().

One scenario that isn't handled by the builder proposed above is the ability to combine rate limiters. Imagine you want a global limiter of 100 concurrent requests to a service and also to have a per IP limit of 1 per second.
The builder pattern only supports running a single rate limiter so there needs to be some other way to "chain" rate limiters.
We believe this can be accomplished by providing a static method that accepts any number of GenericRateLimiters and combines them to create a single GenericRateLimiter that will run them in order when acquiring a lease.

Chained Limiter API

+ static GenericRateLimiter<TResource> CreateChainedRateLimiter<TResource>(IEnumerable<GenericRateLimiter<TResource>> limiters);

Additionally, we would like to add an interface for rate limiters that refresh tokens to make it easier to handle replenishing tokens from a single timer in generic code

Timer Based Limiter API addition

+ public interface IReplenishingRateLimiter
+ {
+     public abstract bool TryReplenish();
+     // public TimeSpan ReplenishRate { get; }
+ }

public sealed class TokenBucketRateLimiter
 : RateLimiter
+ , IReplenishingRateLimiter

Alternatively, we could use a new abstract class public abstract class ReplenishingRateLimiter : RateLimiter that the TokenBucketRateLimiter implements. Adding a class would add TryReplenish to the public API that a consumer might see (if they accepted ReplenishingRateLimiter instead of RateLimiter).

And finally, we would like to add an API for checking if a rate limiter is idle. This would be used to see which rate limiters are broadcasting that they aren't being used and we can potentially remove them from our GenericRateLimiter implementations cache to reduce memory. For example, ConcurrencyLimiter and TokenBucketRateLimiter are idle when they have all their permits.

Idle Limiter API Addition

public abstract class RateLimiter : IAsyncDisposable, IDisposable
{
+    public abstract DateTime? IdleSince { get; }
// alternatives
//    bool IsInactive { get; }
//    bool IsIdle { get; }
}

Alternatively, we could add an interface, IIdleRateLimiter, that limiters can choose to implement, but we think a first-class property is more appropriate in this scenario because you should be forced to implement the property to allow for book-keeping in the GenericRateLimiter.

API Usage

var builder = WebApplication.CreateBuilder(args);
builder.Services.AddHttpClient("RateLimited", o => o.BaseAddress = new Uri("http://localhost:5000"))
    .AddHttpMessageHandler(() =>
        new RateLimitedHandler(
            new GenericRateLimitBuilder<HttpRequestMessage>()
            // TokenBucketRateLimiter if the request is a POST
            .WithTokenBucketPolicy(request => request.Method.Equals(HttpMethod.Post) ? HttpMethod.Post : null,
                new TokenBucketRateLimiterOptions(1, QueueProcessingOrder.OldestFirst, 1, TimeSpan.FromSeconds(1), 1, true))
            // ConcurrencyLimiter if above limiter returns null and has a "cookie" header
            .WithPolicy(request => request.Headers.TryGetValues("cookie", out _) ? "cookie" : null,
                _ => new ConcurrencyLimiter(new ConcurrencyLimiterOptions(1, QueueProcessingOrder.NewestFirst, 1)))
            // Final fallback to a ConcurrencyLimiter per unique URI
            .WithConcurrencyPolicy(request => request.RequestUri,
                new ConcurrencyLimiterOptions(2, QueueProcessingOrder.OldestFirst, 2))
            .Build()));

// ...

var factory = app.Services.GetRequiredService<IHttpClientFactory>();
var client = factory.CreateClient("RateLimited");
var resp = await client.GetAsync("/problem");

Alternative Designs

Provide just the GenericRateLimiter<TResource> abstraction and don't provide a builder. This would require users to manually implement their own generic limiter implementations.

Provide a concrete GenericRateLimiter<TResource> implementation instead of a builder that has some customizability (options?) but would likely be less flexible and more opinionated.

Risks

The behavior of how the internal limiters in the generic limiter implementation are used is complex and needs to be well defined so users don't see unexpected behavior.

Providing an efficient generic implementation relies on additional features like ReplenishingRateLimiter and IdleSince to optimize Timer usage and memory usage.

Author:	BrennanConroy
Assignees:	-
Labels:	api-suggestion, area-System.Threading
Milestone:	-

[Sergio0694]

Just a question on naming: why GenericRateLimit<T>? Shouldn't it just be RateLimiter<T> and RateLimiterBuilder<T>? The "Generic" prefix doesn't seem very idiomatic and also it feels a bit redundant 🤔

[Kahbazi]

Could we also have a NoPolicy method on builder? This could be used when we don't want to have any limitation if certain condition is true and stop going to the next policy.

public class GenericRateLimitBuilder<TResource>
{
    public GenericRateLimitBuilder<TResource> WithNoPolicy<TKey>(Func<TResource, bool> condition);
}

[terrajobst]

• Why is the type called GenericRateLimiter<T>
  • Normally, we'd call it RateLimiter<T> (generic and non-generic types can have the same simple name)
  • It seems GenericRateLimiter<T> is also different in the sense that it provides resource. Maybe, ResourceRateLimiter<T> makes more sense?
• The way the extension methods on GenericRateLimitBuilder<T> feels a odd
  • Not clear why they only apply to GenericRateLimiter<T> but not RateLimiter
  • It's not clear that the policies aren't chained unless null is the returned as the key. In fact, returning null as the key isn't very obvious.
• IdleSince should probably return DateTimeOffset? or a TimeSpan?
  • Ideally, the implementation would use a Stopwatch to avoid issues when time changes occur
  • If it returns TimeSpan? it should be named IdleDuration
• IReplenishingRateLimiter should probably be an abstract member(s) on RateLimiter or a separate type deriving from RateLimiter

public sealed class PartitionedRateLimiter
{
    public static PartitionedRateLimiter<TResource> Create<TResource, TPartitonKey>(
        Func<TResource, TPartionKey> partitioner,
        Func<TPartitionKey, RateLimiter> rateLimiterFactory);
}

public abstract class PartitionedRateLimiter<TResource> : IAsyncDisposable, IDisposable
{
    public abstract int GetAvailablePermits(TResource resourceID);

    public RateLimitLease Acquire(TResource resourceID, int permitCount = 1);
    protected abstract RateLimitLease AcquireCore(TResource resourceID, int permitCount);

    public ValueTask<RateLimitLease> WaitAsync(TResource resourceID, int permitCount = 1, CancellationToken cancellationToken = default);
    protected abstract ValueTask<RateLimitLease> WaitAsyncCore(TResource resourceID, int permitCount, CancellationToken cancellationToken);

    protected virtual void Dispose(bool disposing);
    public void Dispose();  

    protected virtual ValueTask DisposeAsyncCore();
    public async ValueTask DisposeAsync();
}

[BrennanConroy]

The proposed static Create method on PartitionedRateLimiter would look like the following when used:

PartitionedRateLimiter.Create<HttpRequestMessage, string>(resource =>
{
    if (resource.Method.Equals(HttpMethod.Post))
    {
        return HttpMethod.Post.Method;
    }
    else if (resource.Headers.TryGetValues("cookie", out _))
    {
        return "cookie";
    }
    else
    {
        return resource.RequestUri.ToString();
    }
},
partition =>
{
    if (partition.Equals(HttpMethod.Post.Method, StringComparison.OrdinalIgnoreCase))
    {
        return new ConcurrencyLimiter(new ConcurrencyLimiterOptions(1, QueueProcessingOrder.OldestFirst, 10));
    }
    else if (partition.Equals("cookie", StringComparison.OrdinalIgnoreCase))
    {
        return new ConcurrencyLimiter(new ConcurrencyLimiterOptions(1, QueueProcessingOrder.NewestFirst, 1));
    }
    else
    {
        return new ConcurrencyLimiter(new ConcurrencyLimiterOptions(2, QueueProcessingOrder.OldestFirst, 2));
    }
})

This has the issue of duplicating the if statements which is not an ideal solution.

Below are a few different ways we could change the original builder pattern to try and make it more obvious that partitions are terminal (don't chain).

new PartitionedRateLimitBuilder<HttpRequestMessage>()
    .CreatePartitionPolicy(r => r.Method.Equals(HttpMethod.Post) ? HttpMethod.Post : null)
    .WithLimiter(_ => new ConcurrencyLimiter(new ConcurrencyLimiterOptions(1, QueueProcessingOrder.OldestFirst, 1)))
    // .CompletePolicy()
    .CreatePartitionPolicy(request => request.Headers.TryGetValues("cookie", out _) ? "cookie" : null)
    .WithLimiter(_ => new ConcurrencyLimiter(new ConcurrencyLimiterOptions(1, QueueProcessingOrder.NewestFirst, 1)))
    .WithLimiter(_ => new TokenBucketRateLimiter(new TokenBucketRateLimiterOptions(1, QueueProcessingOrder.NewestFirst, 1, TimeSpan.FromSeconds(1), 1)))
    // .CompletePolicy()
    .Build();

new PartitionedRateLimitBuilder<HttpRequestMessage>()
    .CreatePartitionPolicy(r => r.Method.Equals(HttpMethod.Post) ? HttpMethod.Post : null, builder =>
    {
        builder
            .WithLimiter(_ => new ConcurrencyLimiter(new ConcurrencyLimiterOptions(1, QueueProcessingOrder.OldestFirst, 1)))
            .WithLimiter(_ => new TokenBucketRateLimiter(new TokenBucketRateLimiterOptions(1, QueueProcessingOrder.NewestFirst, 1, TimeSpan.FromSeconds(1), 1)));
    })
    .CreatePartitionPolicy(request => request.Headers.TryGetValues("cookie", out _) ? "cookie" : null, builder =>
    {
        builder
            .WithLimiter(_ => new ConcurrencyLimiter(new ConcurrencyLimiterOptions(1, QueueProcessingOrder.OldestFirst, 1)));
    }).Build();

new PartitionedRateLimitBuilder<HttpRequestMessage>()
    .CreatePartitionPolicy(
        request => request.Method,
        key => key.Equals(HttpMethod.Post),
        key => new ConcurrencyLimiter(new ConcurrencyLimiterOptions(1, QueueProcessingOrder.OldestFirst, 1))
    )
    .CreatePartitionPolicy(
        request => request.Headers.TryGetValues("cookie", out _),
        key => key,
        key => new TokenBucketRateLimiter(new TokenBucketRateLimiterOptions(1, QueueProcessingOrder.NewestFirst, 1, TimeSpan.FromSeconds(1), 1))
    ).Build();

The first two still have the problem with returning null for fallbacks, and add support for chaining as a first class feature to try to make the fallback logic more obvious.

The last example has 2 functions for processing the key, the first one returns the value of the key and the second one determines if the key is applicable.

---

For the ReplenishingRateLimiter the shape should look something like:

+ public abstract class ReplenishingRateLimiter : RateLimiter
+ {
+     // How often the RateLimiter wants TryReplenish to be called
+     public abstract TimeSpan ReplenishmentPeriod { get; }

+     // Gets whether the RateLimiter is managing it's own replenishing, or if it requires external calls to TryReplenish
+     public abstract bool IsAutoReplenishing { get; }

+     // Attempts to replenish tokens
+     public abstract bool TryReplenish();
+ }

[Kahbazi]

• Could you please make rateLimiterFactory async and also add TResource to it? It is needed when rate limiter options is stored in a database for each resource.

public static PartitionedRateLimiter<TResource> Create<TResource, TPartitonKey>(
        Func<TResource, TPartionKey> partitioner,
        Func<TResource, TPartitionKey, ValueTask<RateLimiter>> rateLimiterFactory);

new PartitionedRateLimitBuilder<HttpContext, string>(resource =>
{
    return HttpContext.User.GetUserId();
},
async (resource, partition) =>
{
    var rateLimiterStore = resource.RequestServices.GetService<IRateLimiterStore>();
    var time = await rateLimiterStore.GetTimeSpanForUserAsync(partition);
    return new TokenBucketRateLimiter(new TokenBucketRateLimiterOptions(1, QueueProcessingOrder.NewestFirst, 1, time, 1)));
})

• With only one PartitionedRateLimiter.Create method, what should be the TPartitonKey when there are different kind of partitions? For example I want to have different level of rate limiter on an incoming http request. First based on IP, then based on the Endpoint name (which is unique) and then based on User Id. How should I handle this? Should I create my own custom TResource?

• Is there any plan to support parallel rate limiter as well? Or should users implement it themselves? For example there are three rate limiter rules. One for IP, one for Endpoint and one for User Id and whichever reaches its limit I want to reject the request. Should I create three separate rate limiter and call Acquire on each of them myself or will PartitionedRateLimiter somehow support that as well?

[BrennanConroy]

The issue with PartitionedRateLimiter.Create needing to duplicate the users' if statements can be solved if we change the API to return a tuple of key and factory.

PartitionedRateLimiter.Create<HttpRequestMessage, string>(resource =>
{
    if (resource.Method.Equals(HttpMethod.Post))
    {
        return (HttpMethod.Post.Method, s => new ConcurrencyLimiter(...));
    }
    else if (resource.Headers.TryGetValues("cookie", out _))
    {
        return ("cookie", s => new ConcurrencyLimiter(...));
    }
    else
    {
        // Do not write code like this, it is unbounded and merely for demonstration purposes
        return (resource.RequestUri.ToString(), s => new ConcurrencyLimiter(...));
    }
});

We could further improve this by providing a type that is easier to use and could provide convenient methods for specific limiter types like the originally proposed builder pattern.

PartitionedRateLimiter<HttpContext> limiter = PartitionedRateLimiter.Create<HttpContext, PathString>(resource =>
{
    if (resource.Method.Equals(HttpMethod.Post))
    {
        return RateLimitPartition.Create(HttpMethod.Post.Method, s => new ConcurrencyLimiter(...));
    }
    else if (resource.Headers.TryGetValues("cookie", out _))
    {
        return RateLimitPartition.CreateTokenBucketLimiter("cookie", s => new TokenBucketLimiterOptions(...));
    }
    else if (resource.Headers.TryGetValues("admin", out _))
    {
        return RateLimitPartition.CreateNoLimiter("admin");
    }
    else
    {
        return RateLimitPartition.CreateConcurrencyLimiter(resource.RequestUri.ToString(), s => new ConcurrencyLimiterOptions(...));
    }
});

There are two more concepts that we believe should be provided that can be built on top of the new PartitionedRateLimiter. A method for chaining PartitionedRateLimiters and a method for mapping one resource type to another with a PartitionedRateLimiter.
In the first scenario it can be useful to have multiple layers of limiting, for example a global limiter and an endpoint specific limiter. You will want to apply both and for that you would need to have two different places in your app acquire the different limiters. With chaining you can have a single place to acquire both limiters with a simple API.

stateDiagram-v2
    state ChainedLimiter {
        Global_Concurrency --> PartitionedLimiter
        PartitionedLimiter -->Concurrency : Request.Path == admin
        PartitionedLimiter -->TokenBucket : Request.UserName
        PartitionedLimiter -->No_limit! : Has Special Cookie
    }

Loading

This can be achieved with a single method PartitionedRateLimiter<TResource> CreateChainedRateLimiter<TResource>(params PartitionedRateLimiter<TResource>[] limiters); and it would just go in order through the limiters until they were all acquired. We would probably want to discuss the details of what happens when one lease acquisition fails.

The second scenario is useful when you have a PartitionedRateLimiter that is provided by a third-party or is written for generic use and you want to use it for a specific resource. For example you have named policies so the resource that the limiter accepts is a string that maps to the name of a policy.

namedPoliciesLimiter = PartitionedRateLimiter.Create<string, string>(resource =>
{
    switch (resource)
    {
        case "Policy1":
            return RateLimitPartition.Create(resource, _ => new ConcurrencyLimiter(...));
        case "Policy2":
            return RateLimitPartition.Create(resource, _ => new TokenBucketRateLimiter(...));
        default:
            return RateLimitPartition.Create(resource, _ => new ConcurrencyLimiter(...));
    }
});

Now you want to use the limiter for your Http endpoints with an HttpContext but because the resource is HttpContext you need to map the resource.

limiter = AdaptPartitionedRateLimiter<HttpContext, string>(namedPoliciesLimiter, context =>
{
    if (context.Request.Path.StartsWithSegments("/limited"))
    {
        return "Policy1";
    }
    if (context.Request.Path.StartsWithSegments("/token"))
    {
        return "Policy2";
    }
    return "Default";
});

With the AdaptPartitionedRateLimiter method we can wrap the limiter with a mapping function and allow the policy name based limiter to be used with HttpContext.
PartitionedRateLimiter<TOuter> AdaptPartitionedRateLimiter<TOuter, TInner>(PartitionedRateLimiter<TInner> limiter, Func<TOuter, TInner> keyAdapter);

First based on IP, then based on the Endpoint name (which is unique) and then based on User Id. How should I handle this? Should I create my own custom TResource?

This sounds like you want to chain limiters. The PartitionedRateLimiter will run a single limiter per resource by default. If you want multiple limiters to apply you either need to write your own custom code or use the CreateChainedRateLimiter that's being proposed.

Is there any plan to support parallel rate limiter as well?

No parallel support is planned.

+ public sealed class PartitionedRateLimiter
+ {
+     public static PartitionedRateLimiter<TResource> Create<TResource, TPartitionKey>(
+         Func<TResource, RateLimitPartition<TPartitionKey>> partitioner) where TPartitionKey : notnull;

+     public static PartitionedRateLimiter<TOuter> AdaptPartitionedRateLimiter<TOuter, TInner>(PartitionedRateLimiter<TInner> limiter, Func<TOuter, TInner> keyAdapter);

+     public static PartitionedRateLimiter<TResource> CreateChainedRateLimiter<TResource>(params PartitionedRateLimiter<TResource>[] limiters);
+ }

+ public static class RateLimitPartition
+ {
+     public static RateLimitPartition<TKey> Create<TKey>(TKey partitionKey, Func<TKey, RateLimiter> factory);

+     public static RateLimitPartition<TKey> CreateConcurrencyLimiter<TKey>(TKey partitionKey, Func<TKey, ConcurrencyLimiterOptions> factory);

+     public static RateLimitPartition<TKey> CreateNoLimiter<TKey>(TKey partitionKey);

+     public static RateLimitPartition<TKey> CreateTokenBucketLimiter<TKey>(TKey partitionKey, Func<TKey, TokenBucketRateLimiterOptions> factory);
+ }

+ public sealed class RateLimitPartition<TKey>
+ {
+     public RateLimitPartition(TKey partitionKey, Func<TKey, RateLimiter> factory);
+ }

+ public static class PartitionedRateLimiterExtensions
+ {
+     public static PartitionedRateLimiter<TOuter> AdaptPartitionedRateLimiter<TOuter, TInner>(this PartitionedRateLimiter<TInner> limiter, Func<TOuter, TInner> keyAdapter);

+     public static PartitionedRateLimiter<TResource> ChainRateLimiters<TResource>(this PartitionedRateLimiter<TResource> limiter, params PartitionedRateLimiter<TResource>[] limiters);
+ }

[terrajobst]

Video

• The code sample is show casing a problematic pattern because it allows an attacker to flood the internal dictionary with data they control (i.e. they can flood the server with random URLs causing the app to OOM). It might be worthwhile to invest in an analyzer that detects known bad patterns and warns about them (e.g. passing in the request URI directly as a key).

  else
  {
      return RateLimitPartition.CreateConcurrencyLimiter(resource.RequestUri.ToString(), s => new ConcurrencyLimiterOptions(...));
  }

• PartitionedRateLimiter.Create should allow to pass in an IEqualityComparer<TPartitionKey>
• RateLimitPartition<TKey> should probably be a struct and at least expose the key as a get-only property, mostly for debugging purposes
• PartitionedRateLimiterExtensions should be removed -- we already have the methods on PartitionedRateLimiter
  • AdaptPartitionedRateLimiter should just be an instance method
  • CreateChainedRateLimiter should just be CreateChained. Params seem fine.
• ReplenishingRateLimiter and making TokenBucketRateLimiter seems fine.
• Consider rename TKey to just T

namespace System.Threading.RateLimiting;

public sealed class PartitionedRateLimiter
{
    public static PartitionedRateLimiter<TResource> Create<TResource, TPartitionKey>(
        Func<TResource, RateLimitPartition<TPartitionKey>> partitioner,
        IEqualityComparer<TPartitionKey> equalityComparer = null) where TPartitionKey : notnull;

    public PartitionedRateLimiter<TOuter> TranslateKey<TOuter, TInner>(
        Func<TOuter, TInner> keyAdapter);

    public static PartitionedRateLimiter<TResource> CreateChained<TResource>(
        params PartitionedRateLimiter<TResource>[] limiters);
}

public static class RateLimitPartition
{
    public static RateLimitPartition<TKey> Create<TKey>(
        TKey partitionKey, Func<TKey, RateLimiter> factory);
    public static RateLimitPartition<TKey> CreateConcurrencyLimiter<TKey>(
        TKey partitionKey, Func<TKey, ConcurrencyLimiterOptions> factory);
    public static RateLimitPartition<TKey> CreateNoLimiter<TKey>(TKey partitionKey);
    public static RateLimitPartition<TKey> CreateTokenBucketLimiter<TKey>(
        TKey partitionKey,
        Func<TKey, TokenBucketRateLimiterOptions> factory);
}

public struct RateLimitPartition<TKey>
{
    public RateLimitPartition(TKey partitionKey, Func<TKey, RateLimiter> factory);
    public TKey PartitionKey { get; }
}

public partial class RateLimiter
{
    public abstract TimeSpan? IdleDuration { get; }
}

public abstract class ReplenishingRateLimiter : RateLimiter
{
    public abstract TimeSpan ReplenishmentPeriod { get; }
    public abstract bool IsAutoReplenishing { get; }
    public abstract bool TryReplenish();
}

public partial class TokenBucketRateLimiter : ReplenishingRateLimiter
{   
}

[BrennanConroy]

While starting to look at implementing the approved APIs I realize we didn't explicitly approve the main abstract class for the PartitionedRateLimiter<TResource> which I'll show below. Additionally, we put the TranslateKey method as an instance method on the non-generic PartitionedRateLimiter which I believe we intended to put on the generic PartitionedRateLimiter.

public abstract class PartitionedRateLimiter<TResource> : IAsyncDisposable, IDisposable
{
    public abstract int GetAvailablePermits(TResource resourceID);

    public RateLimitLease Acquire(TResource resourceID, int permitCount = 1);
    protected abstract RateLimitLease AcquireCore(TResource resourceID, int permitCount);

    public ValueTask<RateLimitLease> WaitAsync(TResource resourceID, int permitCount = 1, CancellationToken cancellationToken = default);
    protected abstract ValueTask<RateLimitLease> WaitAsyncCore(TResource resourceID, int permitCount, CancellationToken cancellationToken);

    protected virtual void Dispose(bool disposing);
    public void Dispose();  

    protected virtual ValueTask DisposeAsyncCore();
    public async ValueTask DisposeAsync();
}

public abstract class PartitionedRateLimiter<TResource> : IAsyncDisposable, IDisposable
{
+    public PartitionedRateLimiter<TOuter> TranslateKey<TOuter>(
+        Func<TOuter, TResource> keyAdapter);
}

- public sealed class PartitionedRateLimiter
+ public static class PartitionedRateLimiter
{
    public static PartitionedRateLimiter<TResource> Create<TResource, TPartitionKey>(
        Func<TResource, RateLimitPartition<TPartitionKey>> partitioner,
        IEqualityComparer<TPartitionKey> equalityComparer = null) where TPartitionKey : notnull;

-    public PartitionedRateLimiter<TOuter> TranslateKey<TOuter, TInner>(
-        Func<TOuter, TInner> keyAdapter);

    public static PartitionedRateLimiter<TResource> CreateChained<TResource>(
        params PartitionedRateLimiter<TResource>[] limiters);
}

[bugproof]

Currently, I use https://github.com/David-Desmaisons/RateLimiter in my project to limit the number of requests sent e.g. I set it to 100 requests per minute (TimeLimiter.GetFromMaxCountByInterval(100, TimeSpan.FromSeconds(60));) because server relies on a client to implement rate-limiting. I can see it uses SemaphoreSlim and a custom timer implementation to achieve its goal. I'm not really sure what should I use to replace it with System.Threading.RateLimiting APIs. I could see it using the token bucket limiter but not sure if there will be any regression.

In the original proposal, there were 2 additional APIs FixedWindowRateLimiter and SlidingWindowRateLimiter that more closely resemble what the library made by David Desmaisons does. Were they dropped because the token bucket limiter meets all the requirements or because of something else?

[BrennanConroy]

FixedWindow and SlidingWindow have not been dropped, they are in progress and will be in .NET along-side Concurrency and TokenBucket.

[pentp]

The proposal mentions limiting incoming requests based on user and/or IP as a use case. But the implementation looks very costly to achieve this.

For token buckets specifically, using a timer to update every bucket every time it fires is a lot of unnecessary work. Token buckets replenishment can be directly calculated based on last state + time passed when someone wants to acquire a permit. This also applies to buckets where something is waiting to acquire a permit (you can calculate the time it would take for the requested number of tokens to become available).

Moreover, there doesn't seem to be any way to evict old partitions from the dictionary, which is effectively a memory leak when the number of partitions is sufficiently large (e.g., IP addresses). Token buckets again are very well suited for such a case because you could throw away all buckets that are calculated to be full.

Building a partitioned rate limiter using the basic rate limiters as building blocks in such a way doesn't look like a very efficient architecture and also precludes a lot of future optimization opportunities.

[davidfowl]

Building a partitioned rate limiter using the basic rate limiters as building blocks in such a way doesn't look like a very efficient architecture and also precludes a lot of future optimization opportunities.

The PartitionedRateLimiter is an abstraction, that means it should be possible to build something the understands the TContext that doesn't use a RateLimiter as an implementation detail. Are you saying that the abstraction itself is problematic or the default implementations?

[pentp]

The PartitionedRateLimiter abstraction itself is OK, but PartitionedRateLimiter.Create and everything related to RateLimitPartition looks like it will push users on a really inefficient path and these API-s are locked and probably very hard to make efficient later.

If CreateTokenBucketLimiter, CreateFixedWindowLimiter, etc. methods were on PartitionedRateLimiter then it would be possible to later create efficient implementations at least.

RateLimitPartition.Create* methods are inefficient on API level already because they force delegation allocations (because they have to convert a Func<Key, Options> to Func<Key, RateLimiter>) and they don't allow for efficient implementations because they work on the RateLimiter level.

[mangod9]

Is this still planned for 7? Since this is filed under threading area its still showing up in queries for 7. Thx!

[BrennanConroy]

Done for .NET 7.