Throttling API Requests with Token Bucket

Welcome to the second lesson of our course on securing your Securing your TypeScript-based REST AP. In this lesson, we will delve into the Token Bucket algorithm, a powerful method for implementing throttling.

Throttling is essential for maintaining the performance and reliability of your API. It ensures that your server is not overwhelmed by too many requests at once, which can lead to slow response times or even downtime.

The Token Bucket algorithm is a rate limiting method that allows for controlled bursts of activity while maintaining a consistent average rate. Here's how it works:

1. You have a "bucket" that holds tokens (representing request capacity)
2. Tokens are added to the bucket at a fixed rate
3. When a request arrives, it needs to consume a token to proceed
4. If the bucket is empty, the request must either wait or be rejected

Advantages:

• Allows for bursts of traffic (unlike fixed window limiters)
• Simple to implement and understand
• Low memory footprint
• Configurable parameters for different scenarios

Disadvantages:

• Requires ongoing token management (via timers)
• May introduce slight latency for token checks
• Needs careful tuning to balance performance and protection

Let's look at the key components needed to implement a token bucket throttle.

The heart of the algorithm is token management - tracking available tokens and replenishing them:

class TokenBucket {
  private tokens: number;
  private intervalId: NodeJS.Timeout | null = null;
  
  constructor(
    private readonly capacity: number = 5,
    private readonly refillInterval: number = 1000,
    private readonly refillAmount: number = 1
  ) {
    this.tokens = capacity;
  }
  
  // Core token replenishment logic
  initialize(): void {
    this.intervalId = setInterval(() => {
      this.tokens = Math.min(this.tokens + this.refillAmount, this.capacity);
    }, this.refillInterval);
  }
  
  // Basic token consumption
  consumeToken(): boolean {
    if (this.tokens > 0) {
      this.tokens--;
      return true;
    }
    return false;
  }
}

This simplified implementation shows the two essential operations:

• Token replenishment: Adding tokens back to the bucket at fixed intervals
• Token consumption: Checking for and using available tokens

The critical parameters that control throttling behavior are:

• capacity: Maximum tokens (requests) that can be processed at once
• refillInterval: How often tokens are added (in milliseconds)
• refillAmount: Number of tokens added each interval

To integrate with Express, we create middleware that uses our token bucket:

middleware(): (req: Request, res: Response, next: NextFunction) => void {
  return (req: Request, res: Response, next: NextFunction) => {
    if (this.consumeToken()) {
      // Token available, process request
      res.setHeader('X-RateLimit-Remaining', this.tokens.toString());
      next();
    } else {
      // No tokens, handle with backoff strategy
      this.retryWithBackoff(req, res, next);
    }
  };
}

The middleware performs a simple check - if a token is available, the request proceeds; otherwise, it's handled with a backoff strategy.

A sophisticated throttling implementation doesn't just reject excess requests - it can attempt to process them when capacity becomes available:

private retryWithBackoff(
  req: Request, 
  res: Response, 
  next: NextFunction, 
  attempt: number = 1
): void {
  // Calculate delay with exponential growth
  const delay = Math.min(Math.pow(2, attempt) * 100, 2000);
  
  setTimeout(() => {
    if (this.consumeToken()) {
      // Got a token on retry
      next();
    } else if (attempt < this.maxRetryAttempts) {
      // Try again with increased delay
      this.retryWithBackoff(req, res, next, attempt + 1);
    } else {
      // Exceeded retry attempts
      res.status(429).json({
        error: 'Too Many Requests'
      });
    }
  }, delay);
}

The key insight here is the exponential backoff formula: Math.pow(2, attempt) * 100. This creates increasingly longer delays between retries (100ms, 200ms, 400ms, 800ms, etc.) up to a maximum of 2 seconds. This approach prevents overwhelming the server with retry attempts, spreading the load over time.

The most challenging aspect of implementing a token bucket is proper resource management. Issues to handle include:

• Tracking pending requests: Each delayed request creates a timeout that needs to be tracked and potentially canceled.

• Client disconnection handling: When a client disconnects while waiting for a retry, we need to clean up associated resources:

// Monitor for client disconnection
res.on('close', () => {
  if (this.pendingTimeouts.has(requestId)) {
    // Clean up resources for this request
    clearTimeout(this.pendingTimeouts.get(requestId)!);
    this.pendingTimeouts.delete(requestId);
  }
});

• Application shutdown: When the application shuts down, we need to clear all intervals and timeouts:

shutdown(): void {
  // Clear the token replenishment interval
  if (this.intervalId) {
    clearInterval(this.intervalId);
    this.intervalId = null;
  }
  
  // Clean up any pending timeouts
  for (const timeout of this.pendingTimeouts.values()) {
    clearTimeout(timeout);
  }
  this.pendingTimeouts.clear();
}

• Response validation: Before processing a delayed request, check if the response is still writable:

// Check if response is still writable
if (res.writableEnded || res.finished) {
  return; // Abort processing for closed connections
}

When implementing token bucket throttling in production, consider:

1. Distributed systems: For APIs running on multiple servers, you'll need a shared token bucket, often implemented using Redis.

2. User identification: Instead of a global bucket, create buckets per user, API key, or IP address to prevent one user from consuming all capacity.

3. Informative responses: Use headers to inform clients about rate limits:

   • X-RateLimit-Limit: Maximum capacity
   • X-RateLimit-Remaining: Current tokens available
   • X-RateLimit-Reset: When the bucket will refill

4. Client guidance: Return clear error messages with retry recommendations:

{
  "error": "Too Many Requests",
  "message": "Rate limit exceeded",
  "retryAfter": 5
}

To observe throttling in action, send a burst of requests:

const axios = require('axios');

// Send 30 concurrent requests
const requests = Array(30).fill().map((_, i) => {
  return axios.get('http://localhost:3000/api/test')
    .then(response => console.log(`Request ${i+1}: Success`))
    .catch(err => console.log(`Request ${i+1}: Failed - ${err.response?.status}`));
});

Promise.all(requests);

This will demonstrate the throttling behavior:

• Initial requests succeed immediately (using available tokens)
• Subsequent requests succeed with delays (as tokens replenish)
• Final requests may fail with 429 status (after maximum retries)

In this lesson, we explored the Token Bucket algorithm for throttling API requests. We focused on the key concepts and implementation challenges:

1. Token management: Tracking and replenishing tokens at regular intervals
2. Request handling: Processing or delaying requests based on token availability
3. Exponential backoff: Intelligently spacing retry attempts to reduce server load
4. Resource management: The hardest part - properly tracking and cleaning up resources

As you move to the practice exercises, experiment with different configurations to see how changing parameters affects throttling behavior. This hands-on experience will help you understand how to apply throttling effectively in real-world scenarios.