API Rate Limiting for Backend Services

1. Flow Control

Caching, degradation, and rate limiting are common methods for protecting high-concurrency systems. Caching trades space for time and cuts the time spent on CPU and network calls; degradation protects the high availability of core services by delaying or refusing to handle non-core requests during peak periods; rate limiting protects the system by limiting concurrent requests.

Rate limiting means that, given limited resources, each API endpoint has a limited serving capacity per unit of time. If the number of accesses to an API endpoint is left uncontrolled, it will lead to abuse of the API endpoint and even invite DDoS attacks. At the same time, as shown in the figure below, the latency of an API endpoint also rises rapidly as the request volume increases. Therefore, the number of requests to an API endpoint per unit of time needs to be controlled.

2. What Is a Time Window

A time window refers to the time span of one statistical period. There are two kinds of time windows: the natural time window and the sliding time window.

The figure above is a natural time window, with one window per minute. For example, statistics are collected once per 15:01~15:02 interval. The problem with this approach is that if the per-minute limit is N, then the maximum value of the red time window in the figure is 2N. At that point, rate limiting loses its effect. Hence the sliding window.

The core of the sliding window is to divide time into finer granularity. For example, if the current time is 15:02:20, then the statistical sliding window is 15:01:20 ~ 15:02:20. Unlike the above, which uses minutes as the smallest granularity, this sliding window uses seconds as the smallest granularity, thereby achieving more precise traffic control.

3. Traffic Control Algorithms

Counter algorithm
The idea of the counter algorithm is to limit the number of responses for an endpoint along a certain dimension (IP, user, some resource). A counter is set up; each response increments it by one, and when the counter exceeds the threshold, service is refused. This algorithm imposes a simple limit on the total count rather than an average-rate limit.
Leaky bucket algorithm
Requests enter the leaky bucket at a certain rate, and the leaky bucket responds to requests at a certain rate; when the inflow rate is too high, service is refused.

Token bucket algorithm
Tokens are added to the bucket at a fixed rate. As time passes, the system adds a token to the bucket at a constant interval; if the bucket is already full, no more are added. When a new request arrives, it takes one token each; if no token is available, it blocks or refuses service.

The leaky bucket algorithm can limit the data transmission rate, and requests exceeding the processing rate are dropped directly; the token bucket algorithm, while limiting the average data transmission rate, can also handle burst requests by speeding up the rate at which tokens are added.

4. Different Types of Rate Limiters

Request rate limiter
Limits each user to N requests per second
Concurrent request rate limiter
Limits the maximum number of requests per second. A request rate limiter limits the cumulative amount, while a concurrency limiter limits the peak.
Usage-based load degradation
Requests are divided into critical API requests and non-critical API requests. When designing the system, a certain amount of resources is reserved for critical API requests; when non-critical API requests need to occupy the reserved resources, they are not pre-allocated and service is refused directly.
Worker-utilization-based load degradation
If a worker is too busy to handle the requests assigned to it, it slowly degrades non-critical requests, starting with test requests, of course. If, while scaling back test requests, the worker’s processing capacity recovers to a good state, then we can begin to slowly restore traffic.

5. Implementation

For rate limiting at the Nginx access layer, you can use two modules that Nginx ships with: the connection-limiting module ngx_http_limit_conn_module and the request-limiting module ngx_http_limit_req_module, which implements the leaky bucket algorithm.

ngx_http_limit_conn_module

limit_conn rate-limits the total number of network connections corresponding to a given KEY.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
http {
    # 配置限流 Key 和存放 Key 对应信息的共享内存区域大小
    limit_conn_zone $binary_remote_addr zone=addr:10m;
    # 被限流后，默认日志级别
    limit_conn_log_level error;
    # 被限流后，返回的状态码
    limit_conn_status 503;
    ...
    server {
    ...
    location /limit {
        # 配置存放 Key 和计数器的共享内存区域，指定 Key 的最大连接数
        limit_conn addr 1;
    }

Here the Key used is $binary_remote_addr, which represents the IP address; you can also use $server_name to represent the domain name. Different Key values limit traffic along different dimensions.

Test

1
ab -n 5 -c 5 http://127.0.0.1/limit/

ngx_http_limit_req_module

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
http ｛
	## 对每一个IP的请求限制为1次每秒
	limit_req_zone $binary_remote_addr zone=perip:10m rate=1r/s;
	# 被限流后，默认日志级别
    limit_conn_log_level error;
    # 被限流后，返回的状态码
    limit_conn_status 503;
    ...
    server {
    ...

	location /limit {
	    # burst 配置桶的大小，nodelay 表示非延迟模式，允许突发处理请求。
		limit_req zone=perip burst=3 nodelay;
	}
}

Test

1
ab -n 5 -c 5 http://127.0.0.1/limit/

Setting an IP allow/deny list

1
2
3
4
5
6
location / {
    allow 192.168.1.1/24;
    allow 127.0.0.1;
    deny 1.2.3.4;
    # deny  all;
}

django-ratelimit

django-ratelimit is a cache-based rate-limiting package for endpoints, using decorators to control traffic on API endpoints.

Installation

1
pip install django-ratelimit

Usage

1
2
3
4
5
6
7
8
9
from ratelimit.decorators import ratelimit

@ratelimit(key='ip')
def myview(request):
    # ...

@ratelimit(key='ip', rate='100/h')
def secondview(request):
    # ...

Here Key represents the dimension of the statistics, and can be ip, some parameter obtained from get, some parameter obtained from post, some parameter obtained from header, user, or user_or_ip. rate represents the rate limit X/u, where X is a number and u is a time unit, which can be s, m, h, or d.

rate can also be a function; it only needs to return the specified format. In this way, some special limiting features can be implemented. For example, anonymous users and logged-in users can use different limit values.

6. Distributed Flow Control

The most critical part of distributed rate limiting is to make the rate-limiting service atomic.

The solution is, through Redis + Lua or Nginx + Lua technology, to control the concurrency and total number of requests within a time window. Use Lua to implement the token bucket or leaky bucket algorithm.