Nginx Source Code Notes – HTTP Module – Flow Control

Table of Contents

• ngx_http_limit_conn_module
  
  • Usage
  • Implementation

• nginx-http-limit-req-module
  • Usage
  • Leaky bucket algorithm as a meter
  • Structures
  • Flow

ngx_http_limit_conn_module

Key areas of focus: methods for calculating concurrent connections; methods for using shared memory; methods for using red-black trees;

The ngx_http_limit_conn_module module is used to limit the number of connections per the defined key, in particular, the number of connections from a single IP address.

Not all the connections are counted. A connection is counted only if it has a request processed by the server and the whole request header has already been read.

Usage

# http
limit_conn_zone $binary_remote_addr zone=addr:10m;
...
# http, server, location
limit_conn addr 1;
#
# when several `limit_conn` directives are specified, any configured limit
# will apply.

Implementation

This module is simpler to implement than nginx-http-limit-req-module. It directly counts connections with the same variable value, returning a 503 error if the limit is exceeded.

Simultaneously, connections that pass the rate limiting check need to have their count in this module updated (decremented by 1) when they are closed after processing. A memory pool cleanup callback function is used here.

In practice, since there is only one pending request on a connection at any given time, and due to the existence of keepalive connections and the inability to know the connection status (new or old connection) in each PHASE handler function, the limit_conn module uses the number of requests being processed as the number of connections.

The nginx-http-limit-req-module focuses on: how the rate is calculated; how requests that cannot be processed immediately are cached; how the Leak Bucket algorithm works; how shared memory is used; and how red-black trees are used.

The ngx_http_limit_req_module (0.7.21) limits the request processing rate per defined key, specifically, the processing rate of requests from a single IP address. This limitation is achieved using the “leaky bucket” method.

Usage

# http
limit_req_zone $var zone=limit:10m rate=1r/s;
...
# http, server, location
limit_req zone=limit burst=5 nodelay;

If the requests rate exceeds the rate configured for a zone and nodelay is off:

• if the number of requests is lower than the maximum burst size, their processing is delayed such that requests are processed at the defined rate.
• if the number of requests exceeds the maximum burst size, the newly received requests are terminated with an error 503.

Leaky bucket algorithm as a meter

Leaky bucket

An algorithm can be used in either traffic policing (nonconforming packets are discarded) or traffic shaping (nonconforming packets are delayed until they conform).

The ngx-http-limit-req-module actually uses one of the Leaky Bucket algorithms: The Leaky Bucket Algorithm as a Meter. The requirements of this algorithm are excerpted below:

The Leaky Bucket algorithm is based on, and gets it name from, an analogy of a bucket that has a hole in the bottom through which any water it contains will leak away at a constant rate, until or unless it is empty. Water can be added intermittenly, i.e. in bursts, but if too much is added at once, or it is added at too high an average rate, the water will exceed the capacity of the bucket, which will overflow.

Hence, this leaky bucket determines whether adding some amount of water would exceed or conform to a limit on the average rate at which water can be added, set by the leak rate, and a limit on how much water can be added in a burst, set by the depth of the bucket.

• Leaky bucket algorithm as a meter – the analogue of the bucket is a counter or variable, separate from the flow of traffic or scheduling of events.
  • This counter is used only to check that the traffic or events conform to the limits.
  • For a packet to conform, it has to be possible to add a specific amount of water to the bucket: The specific amount added by a conforming packet can be the same for all packets, or can be proportional to the length of the packet.
  • Algorithm parameters – the bandwidth limit and burstiness limit.
    • bandwidth limit may be specified as: packet rate, byte rate or as an emission interval
    • burstiness limit may be specified as: delay vaiation tolerance or as a maximum burst size (MBS)
• Leaky bucket algorithm as a queue – The leaky bucket consists of a finite queue. When a packet arrives, if there is room on the queue it is appended to the queue; otherwise it is discarded. At every clock tick one packet is transmitted (unless the queue is empty).
• An implementation of the leaky bucket as a queue is therefore always a form of traffic policing function.

The main variables in this module are defined as follows:

• rate – 1 corresponds to 0.001 requests per second (r/s), then 1000 corresponds to 1 r/s. In terms of the leaky bucket algorithm, it’s the bandwidth limit.
• burst – 1 corresponds to 0.001 requests per second (r/s). burst defines how many requests a client can make in excess of a specified rate. In terms of the leaky bucket algorithm, it’s the bucket capacity.
• excess – Total queue size = bucket capacity + number of requests not yet entered into the bucket. It’s on the same order of magnitude as the above two parameters (1 corresponds to 0.001 requests).
• count – refcount

The main operations of this module are:

excess = lr->excess - ctx->rate * ngx_abs(ms) / 1000 + 1000;
/*       ----------   ------------------------------   ----
          Last time      Over the past period of time (s) At normal speed, the current request...
          Queue size: How many requests were processed?
*/

/* If the total queue size is still greater than the bucket's maximum capacity, postpone processing the current request. */
if ((ngx_uint_t) excess > limit->burst) {
    return NGX_BUSY;
}


ngx_http_limit_req_node_t::count - Reference count; a value greater than 0 indicates that this node is currently in a reference count.
During the lookup process, `ngx_http_limit_req_expire` cannot reclaim this node in non-mandatory mode.

Structures

• ngx_http_limit_req_conf_t is the configuration structure for the module in the location {} scope.

typedef struct {
    ngx_array_t             limits;
    ngx_uint_t              limit_log_level;
    ngx_uint_t              delay_log_level;
    ngx_uint_t              status_code;
} ngx_http_limit_req_conf_t;

• The limit_req_zone configuration directive defines a batch of leaky buckets (ngx_http_limit_req_ctx_t) based on the directive’s variables. Each leaky bucket uses the shared memory storage (ngx_http_limit_req_node_t) defined by this directive (i.e., a variable of type ngx_http_limit_req_node_t can be considered a leaky bucket), and is distinguished by the variable value instantiated from the request-related data (stored and searched in ngx_rbtree_t).

typedef struct {
    ngx_http_limit_req_shctx_t  *sh;
    ngx_slab_pool_t             *shpool; /* Shared memory slab management structure */
    ngx_uint_t                  rate;
    ngx_int_t                   index; /* The variable used to distinguish leaky buckets is in
                                          Index value in the variable system*/
    ngx_str_t                   var;   /* variable name */
    ngx_http_limit_req_node_t   *node; /*The lookup just performed and returned the leaky bucket node for EAGAIN. */
} ngx_http_limit_req_ctx_t;

• Multiple limit_req configuration directives can be configured within the same scope, and each configuration directive corresponds to a configuration structure ngx_http_limit_req_limit_t; all configuration structures within the same scope are stored in the array ngx_http_limit_req_conf_t::limits.

Flow

• ngx_http_limit_req_lookup
  • NGX_OK – The leaky bucket in the current limit_req_zone corresponding to this request (and defined by the last limit_req in the current scope) is allowed to continue being processed by Nginx.
  • NGX_AGAIN – The leaky bucket in the current limit_req_zone corresponding to this request allows the request to continue processing (the bucket is not full), but there are other leaky buckets specified by limit_req in the current scope, and the module needs to use these leaky buckets to attempt to rate-limit the request.
  • NGX_BUSY – The leaky bucket corresponding to this request in the current limit_req_zone is full (the number of pending requests exceeds the preset burst value), and Nginx directly returns a 503 error for this request.
  • NGX_ERROR – Shared memory allocation failed.
• excess

burst <= excess: return 503
burst > excess:  delay this request for `excess * 1000 / rate` ms
excess == 0:      process this request right away

• Leaky buckets in the same scope can affect a request simultaneously: a leaky bucket may reject the request; the processing of the request may be delayed for a certain period of time (the maximum delay calculated based on the status of each leaky bucket); or the current request may be processed immediately when all leaky buckets are idle.
• Requests that have been delayed will be bypassed by this module when processing resumes next time; that is, each request will only be processed by this module once (limit_req_set).

Don’t leave me so easily, please leave something behind…