Throttling and Token Bucket

Welcome to the second lesson of our course on Throttling API Requests. In the previous lesson, we discussed the theoretical importance of rate limiting. Now, we will transition into the practical implementation of the token bucket algorithm, a robust and industry-standard method for implementing throttling to protect your resources.

Throttling is not just about preventing malicious attacks; it is essential for maintaining the performance, reliability, and fairness of your API. Without it, a single noisy neighbor—whether a malicious bot or a buggy client script—could monopolize your server's CPU and memory, degrading the experience for all other users. By the end of this lesson, you will understand how to build a mechanism that ensures your server remains responsive, even under heavy load.

The token bucket algorithm is a widely used rate limiting strategy that balances strict traffic control with the flexibility to handle sudden bursts of activity.

Imagine an arcade game machine that requires a physical token to play.

1. The Bucket: You have a bucket representing your API's capacity.
2. Refill: A distinct process drops a new token into the bucket every second.
3. Consumption: When a user wants to make a request, they must take a token from the bucket.
4. Empty Bucket: If the bucket is empty, the user cannot play (the request is delayed or rejected).

This mechanism provides specific advantages over simple fixed-window counters:

• Burst Tolerance: If the bucket is full, a client can make several requests in rapid succession (a "burst") until the bucket empties.
• Smooth Rate: Once the burst capacity is exhausted, the client is limited to the steady refill rate of the tokens.
• Efficiency: It requires very little memory to store the current token count and the timestamp of the last refill.

Note: While Token Bucket is primarily known as a Rate Limiting algorithm, it is the bridge where rate limiting meets Throttling. In system design, the Token Bucket acts as the "controller" that decides when throttling should begin.

However, implementing this in a high-concurrency environment like ASP.NET Core requires careful handling of shared state and threading.

We will begin by creating the core TokenBucket class. This class is responsible for two things: holding the current number of tokens and replenishing them over time.

Because ASP.NET Core handles requests in parallel, this class must be thread-safe. We break the implementation down into the state definitions and the initialization logic.

public class TokenBucket : IDisposable
{
    private int _tokens;
    private readonly int _capacity;
    private readonly int _refillInterval;
    private readonly int _refillAmount;
    private readonly object _lockObject = new object();
    private PeriodicTimer? _refillTimer;
    private CancellationTokenSource? _timerCts;
    
    public TokenBucket(
        int capacity = 5,
        int refillInterval = 1000,
        int refillAmount = 1)
    {
        _capacity = capacity;
        _refillInterval = refillInterval;
        _refillAmount = refillAmount;
        _tokens = capacity; // Start with a full bucket
    }
    
    // ... Initialization and logic methods follow ...
}

The parameters here define the policy: capacity controls the burst size, while refillInterval and refillAmount control the sustained rate.

Next, we implement the replenishment logic. We use PeriodicTimer, a modern .NET feature that provides a non-blocking, async-compatible way to handle recurring events, which is far superior to legacy threading timers for this use case.

    public void Initialize()
    {
        _timerCts = new CancellationTokenSource();
        _refillTimer = new PeriodicTimer(TimeSpan.FromMilliseconds(_refillInterval));
        
        // Run the refill loop in a background task
        Task.Run(async () =>
        {
            try 
            {
                while (await _refillTimer.WaitForNextTickAsync(_timerCts.Token))
                {
                    lock (_lockObject)
                    {
                        // Add tokens, but do not exceed capacity
                        _tokens = Math.Min(_tokens + _refillAmount, _capacity);
                    }
                }
            }
            catch (OperationCanceledException)
            {
                // Timer cancelled, exit gracefully
            }
        }, _timerCts.Token);
    }

Finally, we need a method for the middleware to ask for a token. This operation must be atomic; we use a lock to ensure two requests don't grab the last token simultaneously.

    public bool ConsumeToken()
    {
        lock (_lockObject)
        {
            if (_tokens > 0)
            {
                _tokens--;
                return true;
            }
            return false;
        }
    }

    public int RemainingTokens
    {
        get { lock (_lockObject) { return _tokens; } }
    }
    
    public void Dispose()
    {
        _timerCts?.Cancel();
        _refillTimer?.Dispose();
        _timerCts?.Dispose();
    }
}

This implementation ensures that token operations remain thread-safe and that background timers are properly disposed of when the application shuts down.

With our logic encapsulated in the TokenBucket class, we need to inject this behavior into the ASP.NET Core request pipeline. We do this using Middleware.

The middleware acts as a gatekeeper. Before the request reaches your controller, the middleware checks the bucket. If a token is available, the request passes through. If not, the middleware initiates a "backoff" strategy to wait for a token.

public class TokenBucketMiddleware
{
    private readonly RequestDelegate _next;
    private readonly TokenBucket _tokenBucket;
    private readonly int _maxRetryAttempts;
    
    public TokenBucketMiddleware(
        RequestDelegate next,
        TokenBucket tokenBucket,
        int maxRetryAttempts = 3)
    {
        _next = next;
        _tokenBucket = tokenBucket;
        _maxRetryAttempts = maxRetryAttempts;
    }
    
    public async Task InvokeAsync(HttpContext context)
    {
        if (_tokenBucket.ConsumeToken())
        {
            // Happy Path: Token available
            context.Response.Headers.Add(
                "X-RateLimit-Remaining", 
                _tokenBucket.RemainingTokens.ToString());
            
            await _next(context);
        }
        else
        {
            // Sad Path: No tokens, enter wait queue
            await RetryWithBackoffAsync(context, attempt: 1);
        }
    }
    
    // ... Retry logic follows ...
}

To activate this, you would instantiate the bucket as a Singleton (since state must be shared across requests) and register the middleware in your Program.cs file.

A sophisticated throttling system differs from a simple firewall by attempting to salvage the request. Instead of immediately failing with a 429 Too Many Requests error, we can make the client wait briefly to see if a token becomes available.

We use an Exponential Backoff strategy. We wait a short time, check for a token, and if we fail, we wait a longer time. This reduces pressure on the system during high load.

private async Task RetryWithBackoffAsync(HttpContext context, int attempt)
{
    // Formula: 100ms, 200ms, 400ms, etc., capped at 2000ms
    var delay = Math.Min(Math.Pow(2, attempt) * 100, 2000);
    
    try
    {
        // Vital: Pass RequestAborted to stop waiting if client disconnects
        await Task.Delay(
            TimeSpan.FromMilliseconds(delay), 
            context.RequestAborted);
        
        if (_tokenBucket.ConsumeToken())
        {
            // Token secured after waiting
            context.Response.Headers.Add(
                "X-RateLimit-Remaining", 
                _tokenBucket.RemainingTokens.ToString());
            await _next(context);
        }
        else if (attempt < _maxRetryAttempts)
        {
            // Still no token, wait longer
            await RetryWithBackoffAsync(context, attempt + 1);
        }
        else
        {
            // Give up
            context.Response.StatusCode = StatusCodes.Status429TooManyRequests;
            await context.Response.WriteAsJsonAsync(new
            {
                error = "Too Many Requests",
                message = "Rate limit exceeded. Please try again later."
            });
        }
    }
    catch (OperationCanceledException)
    {
        // Client gave up, we stop processing
    }
}

The mathematical formula Math.Pow(2, attempt) * 100 is the key here. It prevents a "thundering herd" problem where all waiting requests retry at the exact same moment.

Implementing this in a production environment introduces complexity regarding resource management. The "Hard Part" is ensuring that we don't leak memory or process requests for clients that have already disconnected.

1. Client Disconnection: In the code above, notice the usage of context.RequestAborted inside Task.Delay. If a user gets tired of waiting and closes their browser, the CancellationToken fires, throwing an exception that cancels the delay. This frees up the server thread immediately.

2. Lifecycle Management: The TokenBucket contains a background timer. If the application shuts down, that timer must be disposed of cleanly.

   C#

   // In Program.cs
   var tokenBucket = new TokenBucket(capacity: 5, refillInterval: 1000, refillAmount: 1);
   tokenBucket.Initialize();
   
   var lifetime = app.Services.GetRequiredService<IHostApplicationLifetime>();
   
   // Register a callback to clean up the bucket when the server stops
   lifetime.ApplicationStopping.Register(() =>
   {
       tokenBucket.Dispose();
   });

3. Distributed Systems: The implementation shown here is "in-memory." If you run your API on 5 different servers, each server has its own bucket. In a microservices architecture, you would typically replace the internal _tokens integer with a call to a centralized Redis cache using Lua scripts to ensure atomic operations across the cluster.

By addressing these constraints, you ensure that your throttling mechanism scales reliably without introducing memory leaks or inconsistent states.

To truly understand how your throttle performs, it is best to write a small C# console application that simulates a burst of traffic. This allows you to see the 429 errors and the successful requests side-by-side.

Here is a test harness using HttpClient. It launches 20 concurrent requests against an API configured with a capacity of 5 tokens.

// TestClient.cs
using System.Diagnostics;

var client = new HttpClient();
var baseUrl = "http://localhost:5000/api/weatherforecast";

Console.WriteLine("Starting burst of 20 requests...");
var stopwatch = Stopwatch.StartNew();

var tasks = Enumerable.Range(1, 20).Select(async i =>
{
    try
    {
        var response = await client.GetAsync(baseUrl);
        var time = stopwatch.ElapsedMilliseconds;
        
        if (response.IsSuccessStatusCode)
        {
            Console.WriteLine($"req {i:D2} | {time}ms | Success (200)");
        }
        else
        {
            Console.WriteLine($"req {i:D2} | {time}ms | Failed ({response.StatusCode})");
        }
    }
    catch (Exception ex)
    {
        Console.WriteLine($"req {i:D2} | Failed: {ex.Message}");
    }
});

await Task.WhenAll(tasks);
Console.WriteLine("Test complete.");

This test harness allows you to simulate high-concurrency scenarios that are difficult to replicate manually, ensuring your rate limits hold up under pressure.

When you run this test against your throttled API, you will see output similar to the following. Note the timing differences:

Starting burst of 20 requests...
req 01 | 50ms   | Success (200)  <-- Consumed initial capacity
req 02 | 55ms   | Success (200)
req 03 | 58ms   | Success (200)
req 04 | 60ms   | Success (200)
req 05 | 61ms   | Success (200)  <-- Bucket empty
req 06 | 215ms  | Success (200)  <-- Waited for 1st retry, got replenished token
req 07 | 420ms  | Success (200)  <-- Waited for longer backoff
req 08 | 1250ms | Success (200)
req 09 | 2050ms | Failed (429)   <-- Retries exhausted, rejected
req 10 | 2055ms | Failed (429)
...

1. Immediate Success (01-05): The first 5 requests consume the initial capacity immediately.
2. Delayed Success (06-08): These requests found an empty bucket, entered the RetryWithBackoffAsync loop, waited, and eventually found a new token that the PeriodicTimer added.
3. Failure (09-20): These requests waited through all retry attempts. The incoming request rate was simply too high for the refill rate to catch up, resulting in a 429 Too Many Requests.

This sequence confirms that the middleware is correctly enforcing the policy: allowing bursts, smoothing traffic via backoff, and ultimately capping the load.

In this lesson, we have moved from theory to a concrete implementation of the Token Bucket algorithm in C#. We explored how to manage state safely with locks, how to use PeriodicTimer for background replenishment, and how to implement middleware that intelligently handles backpressure using exponential backoff.

We also highlighted the importance of testing your throttling logic with concurrent requests to ensure it behaves as expected under load. This implementation provides a solid foundation, but remember that in a large-scale distributed system, this logic often moves from application memory to a shared store like Redis.

In the upcoming practice exercises, you will take this code and modify the refillInterval and capacity parameters to observe how different configurations drastically change the API's behavior.