Understanding Rate Limiting: An Essential Guide for Developers

What is API Throttling / Rate Limiting?

Rate limiting is a crucial technique used to manage the consumption of resources by an application, an individual user, or an entire service. It plays a vital role in preventing misuse and overuse of resources, ensuring fair distribution among all users, and maintaining the overall stability and performance of the system.

Why Do Applications Rate Limit?

Protection Against DDoS Attacks:
DDoS (Distributed Denial of Service) attacks aim to overwhelm a server with a flood of requests, rendering it unavailable to legitimate users. Rate limiting helps mitigate these attacks by restricting the number of requests a user can make in a given time frame, thus protecting the server from being overwhelmed.

Server Stability and Consistency:
By controlling the load on the server, rate limiting ensures that legitimate traffic can be handled without degradation in performance. This consistency in service delivery is critical for maintaining user satisfaction and trust.

Cost Control:
In cloud environments, resource consumption directly impacts operational costs. Rate limiting helps manage and predict these costs by capping resource usage, preventing unexpected spikes in expenditure.

Rate Limiting Techniques

Let's explore various rate-limiting techniques that can be implemented to ensure efficient resource management:

1. Concurrency Limiter

Description:
This technique controls the number of concurrent requests being processed at any given time.

Algorithm:

1. Maintain a counter for the current number of concurrent requests.
2. Define a maximum concurrency limit.
3. For each incoming request:
   • If the current number of concurrent requests is less than the limit, increment the counter and process the request.
   • If the limit is reached, deny the request or queue it for later processing.
4. Upon completion of the request, decrement the counter to free up space for new requests.

Pseudocode:

class ConcurrencyLimiter {
    int maxConcurrency;
    int currentConcurrency;

    ConcurrencyLimiter(int maxConcurrency) {
        this.maxConcurrency = maxConcurrency;
        this.currentConcurrency = 0;
    }

    bool AllowRequest() {
        if (currentConcurrency < maxConcurrency) {
            currentConcurrency += 1;
            return true;
        } else {
            return false;
        }
    }

    void CompleteRequest() {
        if (currentConcurrency > 0) {
            currentConcurrency -= 1;
        }
    }
}

2. Fair Queuing

Description:
This technique ensures fair distribution of requests among multiple clients by maintaining separate queues for each client and processing them in a round-robin fashion.

Algorithm:

1. Maintain separate queues for each client.
2. Add each request to the respective client's queue.
3. Process requests from each client's queue in a round-robin manner.
4. If a client's queue is empty, skip to the next client.

Pseudocode:

class FairQueuing {
    Dictionary<string, Queue<Request>> clientQueues;
    List<string> clientList;
    int currentClientIndex;

    FairQueuing() {
        this.clientQueues = new Dictionary<string, Queue<Request>>();
        this.clientList = new List<string>();
        this.currentClientIndex = 0;
    }

    void AddRequest(string clientId, Request request) {
        if (!clientQueues.ContainsKey(clientId)) {
            clientQueues[clientId] = new Queue<Request>();
            clientList.Add(clientId);
        }
        clientQueues[clientId].Enqueue(request);
    }

    Request GetNextRequest() {
        while (clientList.Count > 0) {
            string clientId = clientList[currentClientIndex];
            currentClientIndex = (currentClientIndex + 1) % clientList.Count;

            if (clientQueues[clientId].Count > 0) {
                return clientQueues[clientId].Dequeue();
            }
        }
        return null;
    }
}

3. Fixed Window

Description:
This technique limits the number of requests in a fixed time window (e.g., 100 requests per minute). Once the limit is reached, further requests are denied until the next window.

Algorithm:

1. Define the maximum number of requests and the size of the time window.
2. For each request, check the current time against the start of the window.
3. If the window has elapsed, reset the request count and start a new window.
4. If the request count is within the limit, allow the request and increment the count.
5. If the request count exceeds the limit, deny the request.

Pseudocode:

class FixedWindow {
    int maxRequests;
    TimeSpan windowSize;
    DateTime windowStart;
    int requestCount;

    FixedWindow(int maxRequests, TimeSpan windowSize) {
        this.maxRequests = maxRequests;
        this.windowSize = windowSize;
        this.windowStart = DateTime.Now;
        this.requestCount = 0;
    }

    bool AllowRequest() {
        DateTime currentTime = DateTime.Now;

        if ((currentTime - windowStart) > windowSize) {
            windowStart = currentTime;
            requestCount = 0;
        }

        if (requestCount < maxRequests) {
            requestCount += 1;
            return true;
        } else {
            return false;
        }
    }
}

4. Sliding Window

Description:
Similar to the Fixed Window technique, but uses a rolling time window to more accurately account for request times, providing a smoother rate limit.

Algorithm:

1. Define the maximum number of requests and the size of the time window.
2. For each request, remove timestamps of requests outside the current window.
3. If the number of requests within the window is within the limit, allow the request and add the current timestamp.
4. If the number of requests exceeds the limit, deny the request.

Pseudocode:

class SlidingWindow {
    int maxRequests;
    TimeSpan windowSize;
    Queue<DateTime> requestTimestamps;

    SlidingWindow(int maxRequests, TimeSpan windowSize) {
        this.maxRequests = maxRequests;
        this.windowSize = windowSize;
        this.requestTimestamps = new Queue<DateTime>();
    }

    bool AllowRequest() {
        DateTime currentTime = DateTime.Now;

        while (requestTimestamps.Count > 0 
            && (currentTime - requestTimestamps.Peek()) > windowSize) {
            requestTimestamps.Dequeue();
        }

        if (requestTimestamps.Count < maxRequests) {
            requestTimestamps.Enqueue(currentTime);
            return true;
        } else {
            return false;
        }
    }
}

5. Token Bucket

Description:
Tokens are added to a bucket at a fixed rate (e.g., 10 tokens per second). Each request consumes a token. When no tokens are available, requests are either denied or delayed.

Algorithm:

1. Initialize the bucket with a certain capacity and refill rate.
2. For each request, calculate the number of tokens to be added based on the elapsed time since the last refill.
3. If the bucket has enough tokens, allow the request and decrement the token count.
4. If the bucket does not have enough tokens, deny the request.

Pseudocode:

class TokenBucket {
    int capacity;
    double tokens;
    double refillRate;
    DateTime lastRefillTime;

    TokenBucket(int capacity, double refillRate) {
        this.capacity = capacity;
        this.refillRate = refillRate;
        this.tokens = capacity;
        this.lastRefillTime = DateTime.Now;
    }

    bool AllowRequest() {
        DateTime currentTime = DateTime.Now;
        double elapsedTime = (currentTime - lastRefillTime).TotalSeconds;

        tokens = Math.Min(capacity, tokens + elapsedTime * refillRate);
        lastRefillTime = currentTime;

        if (tokens >= 1) {
            tokens -= 1;
            return true;
        } else {
            return false;
        }
    }
}

6. Leaky Bucket

Description:
Similar to the Token Bucket, but ensures a smooth outflow of requests. Excess requests are buffered and processed at a steady rate.

Algorithm:

1. Initialize the bucket with a certain capacity and leak rate.
2. For each request, calculate the amount of water (requests) leaked since the last check.
3. If the bucket has enough capacity, allow the request and increase the water level.
4. If the bucket is full, deny the request.

Pseudocode:

class LeakyBucket {
    int capacity;
    double leakRate;
    double waterLevel;
    DateTime lastChecked;

    LeakyBucket(int capacity, double leakRate) {
        this.capacity = capacity;
        this.leakRate = leakRate;
        this.waterLevel = 0;
        this.lastChecked = DateTime.Now;
    }

    bool AllowRequest() {
        DateTime currentTime = DateTime.Now;
        double elapsedTime = (currentTime - lastChecked).TotalSeconds;
        lastChecked = currentTime;
        double leakedWater = elapsedTime * leakRate;
        waterLevel = Math.Max(0, waterLevel - leakedWater);

        if (waterLevel < capacity) {
            waterLevel += 1;
            return true;
        } else {
            return false;
        }
    }
}

Rate Limiting Implications

Server Perspective

• Decide on an Identity for Throttling:

  • Choose an identifier such as IP address, client name, or API key to apply rate limits.

• Determine Your Application's Traffic Volume:

  • Assess the traffic load and establish the maximum capacity your server can manage without performance degradation.

• Implement Rate Limiting:

  • Utilize existing rate-limiting libraries tailored for your programming language or develop custom solutions to manage request rates effectively.

Client Perspective

• Use Retry Policies:

  • Exponential Backoff:
  • Gradually increase the wait time between retries to reduce server load.
  • Jitter:
  • Introduce randomness in the wait time to prevent synchronized retries that could overwhelm the server.
  • Retry Limit:
  • Define a maximum number of retries to avoid infinite retry loops and potential resource exhaustion.

• Be Fault Tolerant:

  • Design your application to handle failures gracefully by providing fallback mechanisms and ensuring continuity of service even during rate limiting scenarios.

Learning Resources

Refer to the following resources if you would like to learn more about rate limiting and API throttling:

1. Polly Rate Limiting Strategies and Techniques:

   • Explore Polly's comprehensive guide on implementing rate limiting strategies and techniques in .NET applications.

2. Rate Limiting Pattern - Azure Architecture Center:

   • This article from Microsoft's Azure Architecture Center provides detailed insights into the rate-limiting pattern, including its implementation and benefits in cloud-based applications.

3. ASP.NET Core Performance - Rate Limiting:

   • Learn how to implement rate limiting in ASP.NET Core applications to enhance performance and ensure fair resource distribution.