Token bucket limit<\/h3>\n
Token bucket is an algorithm that derives its name from describing how it works. Imagine there is a bucket filled to the brim with tokens. When a request comes in, it takes a token and keeps it forever. After some consistent period of time, someone adds a pre-determined number of tokens back to the bucket, never adding more than the bucket can hold. If the bucket is empty, when a request comes in, the request is denied access to the resource.<\/p>\n
To give a more concrete example, let’s say the bucket can hold 10 tokens and every minute 2 tokens are added to the bucket. When a request comes in it takes a token so we’re left with 9, 3 more requests come in and each take a token leaving us with 6 tokens, after a minute has passed we get 2 new tokens which puts us at 8. 8 requests come in and take the remaining tokens leaving us with 0. If another request comes in it is not allowed to access the resource until we gain more tokens, which happens every minute. After 5 minutes of no requests the bucket will have all 10 tokens again and won’t add any more in the subsequent minutes unless requests take more tokens.<\/p>\n
Fixed window limit<\/h3>\n
The fixed window algorithm uses the concept of a window which will be used in the next algorithm as well. The window is an amount of time that our limit is applied before we move on to the next window. In the fixed window case moving to the next window means resetting the limit back to its starting point. Let’s imagine there is a movie theater with a single room that can seat 100 people, and the movie playing is 2 hours long. When the movie starts we let people start lining up for the next showing which will be in 2 hours, up to 100 people are allowed to line up before we start telling them to come back some other time. Once the 2 hour movie is finished the line of 0 to 100 people can move into the movie theater and we restart the line. This is the same as moving the window in the fixed window algorithm.<\/p>\n
Sliding window limit<\/h3>\n
The sliding window algorithm is similar to the fixed window algorithm but with the addition of segments. A segment is part of a window, if we take the previous 2 hour window and split it into 4 segments, we now have 4 30 minute segments. There is also a current segment index which will always point to the newest segment in a window. Requests during a 30 minute period go into the current segment and every 30 minutes the window slides by one segment. If there were any requests during the segment the window slides past, these are now refreshed and our limit increases by that amount. If there weren’t any requests our limit stays the same.<\/p>\n
For example, let’s use the sliding window algorithm with 3 10 minute segments and a 100 request limit. Our initial state is 3 segments all with 0 counts and our current segment index is pointing to the 3rd segment.<\/p>\n
![\"Sliding](\"https:\/\/devblogs.microsoft.com\/dotnet\/wp-content\/uploads\/sites\/10\/2022\/07\/sliding_part1.png\")
<\/p>\n
During the first 10 minutes we receive 50 requests all of which are tracked in the 3rd segment (our current segment index). Once the 10 minutes have passed we slide the window by 1 segment also moving our current segment index to the 4th segment. Any used requests in the 1st segment are now added back to our limit. Since there were none our limit is at 50 (as 50 are already used in the 3rd segment).<\/p>\n
![\"Sliding](\"https:\/\/devblogs.microsoft.com\/dotnet\/wp-content\/uploads\/sites\/10\/2022\/07\/sliding_part2.png\")
<\/p>\n
During the next 10 minutes we recieve 20 more requests, so we have 50 in the 3rd segment and 20 in the 4th segment now. Again, we slide the window after 10 minutes passes, so our current segment index is pointing to 5 and we add any requests from segment 2 to our limit.<\/p>\n
![\"Sliding](\"https:\/\/devblogs.microsoft.com\/dotnet\/wp-content\/uploads\/sites\/10\/2022\/07\/sliding_part3.png\")
<\/p>\n
10 minutes later we slide the window again, this time when the window slides the current segment index is at 6 and segment 3 (the one with 50 requests) is now outside of the window. So we get the 50 requests back and add them to our limit, which will now be 80, as there are still 20 in use by segment 4.<\/p>\n
![\"Sliding](\"https:\/\/devblogs.microsoft.com\/dotnet\/wp-content\/uploads\/sites\/10\/2022\/07\/sliding_part4.png\")
<\/p>\n
RateLimiter APIs<\/h2>\n
Introducing the new, in .NET 7, nuget package System.Threading.RateLimiting<\/a>!<\/p>\n This package provides the primitives for writing rate limiters as well as providing a few commonly used algorithms built-in. The main type is the abstract base class In the example above we attempt to acquire 1 permit using the synchronous The other method for trying to acquire permits is Here we show our first example of using one of the built-in rate limiting implementations, The In this example there are 2 threads trying to acquire permits. If thread 1 runs first it will acquire the 2 permits successfully and the If thread 2 runs first it will immediately get a So far we’ve seen the Here we show the If And Going back to the mention of metadata earlier, let’s show an example of where metadata might be useful.<\/p>\n In this example we are making a rate limited RateLimiter<\/code>.<\/p>\npublic abstract class RateLimiter : IAsyncDisposable, IDisposable\r\n{\r\n public abstract int GetAvailablePermits();\r\n public abstract TimeSpan? IdleDuration { get; }\r\n\r\n public RateLimitLease Acquire(int permitCount = 1);\r\n public ValueTask<RateLimitLease> WaitAsync(int permitCount = 1, CancellationToken cancellationToken = default);\r\n\r\n public void Dispose();\r\n public ValueTask DisposeAsync();\r\n}<\/code><\/pre>\nRateLimiter<\/code> contains Acquire<\/code> and WaitAsync<\/code> as the core methods for trying to gain permits for a resource that is being protected. Depending on the application the protected resource may need to acquire more than 1 permits, so Acquire<\/code> and WaitAsync<\/code> both accept an optional permitCount<\/code> parameter. Acquire<\/code> is a synchronous method that will check if enough permits are available or not and return a RateLimitLease<\/code> which contains information about whether you successfully acquired the permits or not. WaitAsync<\/code> is similar to Acquire<\/code> except that it can support queuing permit requests which can be de-queued at some point in the future when the permits become available, which is why it’s asynchronous and accepts an optional CancellationToken<\/code> to allow canceling the queued request.<\/p>\nRateLimitLease<\/code> has an IsAcquired<\/code> property which is used to see if the permits were acquired. Additionally, the RateLimitLease<\/code> may contain metadata such as a suggested retry-after period if the lease failed (will show this in a later example). Finally, the RateLimitLease<\/code> is disposable and should be disposed when the code is done using the protected resource. The disposal will let the RateLimiter<\/code> know to update its limits based on how many permits were acquired. Below is an example of using a RateLimiter<\/code> to try to acquire a resource with 1 permit.<\/p>\nRateLimiter limiter = GetLimiter();\r\nusing RateLimitLease lease = limiter.Acquire(permitCount: 1);\r\nif (lease.IsAcquired)\r\n{\r\n \/\/ Do action that is protected by limiter\r\n}\r\nelse\r\n{\r\n \/\/ Error handling or add retry logic\r\n}<\/code><\/pre>\nAcquire<\/code> method. We also use using<\/code> to make sure we dispose the lease once we are done with the resource. The lease is then checked to see if the permit we requested was acquired, if it was we can then use the protected resource, otherwise we may want to have some logging or error handling to inform the user or app that the resource wasn’t used due to hitting a rate limit.<\/p>\nWaitAsync<\/code>. This method allows queuing permits and waiting for the permits to become available if they aren’t. Let’s show another example to explain the queuing concept.<\/p>\nRateLimiter limiter = new ConcurrencyLimiter(\r\n new ConcurrencyLimiterOptions(permitLimit: 2, queueProcessingOrder: QueueProcessingOrder.OldestFirst, queueLimit: 2));\r\n\r\n\/\/ thread 1:\r\nusing RateLimitLease lease = limiter.Acquire(permitCount: 2);\r\nif (lease.IsAcquired) { }\r\n\r\n\/\/ thread 2:\r\nusing RateLimitLease lease = await limiter.WaitAsync(permitCount: 2);\r\nif (lease.IsAcquired) { }<\/code><\/pre>\nConcurrencyLimiter<\/code>. We create the limiter with a maximum permit limit of 2 and a queue limit of 2. This means that a maximum of 2 permits can be acquired at any time and we allow queuing WaitAsync<\/code> calls with up to 2 total permit requests.<\/p>\nqueueProcessingOrder<\/code> parameter determines the order that items in the queue are processed, it can be the value of QueueProcessingOrder.OldestFirst<\/code> (FIFO<\/a>) or QueueProcessingOrder.NewestFirst<\/code> (LIFO<\/a>). One interesting behavior to note is that using QueueProcessingOrder.NewestFirst<\/code> when the queue is full will complete the oldest queued WaitAsync<\/code> calls with a failed RateLimitLease<\/code> until there is space in the queue for the newest queue item.<\/p>\nWaitAsync<\/code> in thread 2 will be queued waiting for the RateLimitLease<\/code> in thread 1 to be disposed. Additionally, if another thread tries to acquire permits using either Acquire<\/code> or WaitAsync<\/code> it will immediately receive a RateLimitLease<\/code> with an IsAcquired<\/code> property equal to false, because the permitLimit<\/code> and queueLimit<\/code> are already used up.<\/p>\nRateLimitLease<\/code> with IsAcquired<\/code> equal to true, and when thread 1 runs next (assuming the lease in thread 2 hasn’t been disposed yet) it will synchronously get a RateLimitLease<\/code> with an IsAcquired<\/code> property equal to false, because Acquire<\/code> does not queue and the permitLimit<\/code> is used up by the WaitAsync<\/code> call.<\/p>\nConcurrencyLimiter<\/code>, there are 3 other limiters we provide in-box. TokenBucketRateLimiter<\/code>, FixedWindowRateLimiter<\/code>, and SlidingWindowRateLimiter<\/code> all of which implement the abstract class ReplenishingRateLimiter<\/code> which itself implements RateLimiter<\/code>. ReplenishingRateLimiter<\/code> introduces the TryReplenish<\/code> method as well as a couple properties for observing common settings on the limiter. TryReplenish<\/code> will be explained after showing some examples of these rate limiters.<\/p>\nRateLimiter limiter = new TokenBucketRateLimiter(new TokenBucketRateLimiterOptions(tokenLimit: 5, queueProcessingOrder: QueueProcessingOrder.OldestFirst,\r\n queueLimit: 1, replenishmentPeriod: TimeSpan.FromSeconds(5), tokensPerPeriod: 1, autoReplenishment: true));\r\n\r\nusing RateLimitLease lease = await limiter.WaitAsync(5);\r\n\r\n\/\/ will complete after ~5 seconds\r\nusing RateLimitLease lease2 = await limiter.WaitAsync();<\/code><\/pre>\nTokenBucketRateLimiter<\/code>, it has a few more options than the ConcurrencyLimiter<\/code>. The replenishmentPeriod<\/code> is how often new tokens (same concept as permits, just a better name in the context of token bucket) are added back to the limit. In this example tokensPerPeriod<\/code> is 1 and the replenishmentPeriod<\/code> is 5 seconds, so every 5 seconds 1 token is added back to the tokenLimit<\/code> up to the max of 5. And lastly, autoReplenishment<\/code> is set to true which means the limiter will create a Timer<\/code> internally to handle the replenishment of tokens every 5 seconds.<\/p>\nautoReplenishment<\/code> is set to false then it is up to the developer to call TryReplenish<\/code> on the limiter. This is useful when managing multiple ReplenishingRateLimiter<\/code> instances and wanting to lower the overhead by creating a single Timer<\/code> instance and managing the replenish calls yourself, instead of having each limiter create a Timer<\/code>.<\/p>\nReplenishingRateLimiter[] limiters = GetLimiters();\r\nTimer rateLimitTimer = new Timer(static state =>\r\n{\r\n var replenishingLimiters = (ReplenishingRateLimiter[])state;\r\n foreach (var limiter in replenishingLimiters)\r\n {\r\n limiter.TryReplenish();\r\n }\r\n}, limiters, TimeSpan.FromSeconds(1), TimeSpan.FromSeconds(1));<\/code><\/pre>\nFixedWindowRateLimiter<\/code> has a window<\/code> option which defines how long it takes for the window to update.<\/p>\nnew FixedWindowRateLimiter(new FixedWindowRateLimiterOptions(permitLimit: 2,\r\n queueProcessingOrder: QueueProcessingOrder.OldestFirst, queueLimit: 1, window: TimeSpan.FromSeconds(10), autoReplenishment: true));<\/code><\/pre>\nSlidingWindowRateLimiter<\/code> has a segmentsPerWindow<\/code> option in addition to window<\/code> which specifies how many segments there are and how often the window will slide.<\/p>\nnew SlidingWindowRateLimiter(new SlidingWindowRateLimiterOptions(permitLimit: 2,\r\n queueProcessingOrder: QueueProcessingOrder.OldestFirst, queueLimit: 1, window: TimeSpan.FromSeconds(10), segmentsPerWindow: 5, autoReplenishment: true));<\/code><\/pre>\nclass RateLimitedHandler : DelegatingHandler\r\n{\r\n private readonly RateLimiter _rateLimiter;\r\n\r\n public RateLimitedHandler(RateLimiter limiter) : base(new HttpClientHandler())\r\n {\r\n _rateLimiter = limiter;\r\n }\r\n\r\n protected override async Task<HttpResponseMessage> SendAsync(HttpRequestMessage request, CancellationToken cancellationToken)\r\n {\r\n using RateLimitLease lease = await _rateLimiter.WaitAsync(1, cancellationToken);\r\n if (lease.IsAcquired)\r\n {\r\n return await base.SendAsync(request, cancellationToken);\r\n }\r\n var response = new HttpResponseMessage(System.Net.HttpStatusCode.TooManyRequests);\r\n if (lease.TryGetMetadata(MetadataName.RetryAfter, out var retryAfter))\r\n {\r\n response.Headers.Add(HeaderNames.RetryAfter, ((int)retryAfter.TotalSeconds).ToString(NumberFormatInfo.InvariantInfo));\r\n }\r\n return response;\r\n }\r\n}\r\n\r\nRateLimiter limiter = new TokenBucketRateLimiter(new TokenBucketRateLimiterOptions(tokenLimit: 5, queueProcessingOrder: QueueProcessingOrder.OldestFirst,\r\n queueLimit: 1, replenishmentPeriod: TimeSpan.FromSeconds(5), tokensPerPeriod: 1, autoReplenishment: true));;\r\nHttpClient client = new HttpClient(new RateLimitedHandler(limiter));\r\nawait client.GetAsync(\"https:\/\/example.com\");<\/code><\/pre>\nHttpClient<\/code> and if we fail to acquire the requested permit we want to return a failed http request with a 429 status code (Too Many Requests) instead of making an HTTP request to our downstream resource. Additionally, 429 responses can contain a “Retry-After” header that let’s the consumer know when a retry might be successful. We accomplish this by looking for metadata on the RateLimitLease<\/code> using TryGetMetadata<\/code> and MetadataName.RetryAfter<\/code>. We also use the TokenBucketRateLimiter<\/code> because it is able to calculate an estimate of when the number of requested tokens will be available as it knows how often it replenishes tokens. Whereas the ConcurrencyLimiter<\/code> would have no way of knowing when permits would become available, so it wouldn’t provide any RetryAfter<\/code> metadata.<\/p>\n