3.2源码解析
ngx_http_limit_req_module在postconfiguration过程会注册ngx_http_limit_req_handler方法到HTTP处理的NGX_HTTP_PREACCESS_PHASE阶段；
ngx_http_limit_req_handler会执行漏桶算法，判断是否超出配置的限流速率，从而进行丢弃或者排队或者通过；
当用户第一次请求时，会新增一条记录（主要记录访问计数、访问时间），以客户端IP地址（配置$binary_remote_addr）的hash值作为key存储在红黑树中（快速查找），同时存储在LRU队列中（存储空间不够时，淘汰记录，每次都是从尾部删除）；当用户再次请求时，会从红黑树中查找这条记录并更新，同时移动记录到LRU队列首部；
3.2.1数据结构
limit_req_zone配置限流算法所需的存储空间（名称及大小），限流速度，限流变量（客户端IP等），结构如下：
typedef struct {
ngx_http_limit_req_shctx_t *sh;
ngx_slab_pool_t *shpool;//内存池
ngx_uint_t rate; //限流速度（qps乘以1000存储）
ngx_int_t index; //变量索引（nginx提供了一系列变量，用户配置的限流变量索引）
ngx_str_t var; //限流变量名称
ngx_http_limit_req_node_t *node;
} ngx_http_limit_req_ctx_t;
//同时会初始化共享存储空间
struct ngx_shm_zone_s {
void *data; //data指向ngx_http_limit_req_ctx_t结构
ngx_shm_t shm; //共享空间
ngx_shm_zone_init_pt init; //初始化方法函数指针
void *tag; //指向ngx_http_limit_req_module结构体
};limit_req配置限流使用的存储空间，排队队列大小，是否紧急处理，结构如下：
typedef struct {
ngx_shm_zone_t *shm_zone; //共享存储空间
ngx_uint_t burst; //队列大小
ngx_uint_t nodelay; //有请求排队时是否紧急处理，与burst配合使用（如果配置，则会紧急处理排队请求，否则依然按照限流速度处理）
} ngx_http_limit_req_limit_t;前面说过用户访问记录会同时存储在红黑树与LRU队列中，结构如下：
//记录结构体
typedef struct {
u_char color;
u_char dummy;
u_short len; //数据长度
ngx_queue_t queue;
ngx_msec_t last; //上次访问时间
ngx_uint_t excess; //当前剩余待处理的请求数（nginx用此实现令牌桶限流算法）
ngx_uint_t count; //此类记录请求的总数
u_char data[1];//数据内容（先按照key（hash值）查找，再比较数据内容是否相等）
} ngx_http_limit_req_node_t;
//红黑树节点，key为用户配置限流变量的hash值；
struct ngx_rbtree_node_s {
ngx_rbtree_key_t key;
ngx_rbtree_node_t *left;
ngx_rbtree_node_t *right;
ngx_rbtree_node_t *parent;
u_char color;
u_char data;
};
typedef struct {
ngx_rbtree_t rbtree; //红黑树
ngx_rbtree_node_t sentinel; //NIL节点
ngx_queue_t queue; //LRU队列
} ngx_http_limit_req_shctx_t;
//队列只有prev和next指针
struct ngx_queue_s {
ngx_queue_t *prev;
ngx_queue_t *next;
};思考1：ngx_http_limit_req_node_t记录通过prev和next指针形成双向链表，实现LRU队列；最新访问的节点总会被插入链表头部，淘汰时从尾部删除节点；
ngx_http_limit_req_ctx_t *ctx; ngx_queue_t *q; q = ngx_queue_last(&ctx->sh->queue); lr = ngx_queue_data(q, ngx_http_limit_req_node_t, queue);//此方法由ngx_queue_t获取ngx_http_limit_req_node_t结构首地址，实现如下： #define ngx_queue_data(q, type, link) (type *) ((u_char *) q - offsetof(type, link)) //queue字段地址减去其在结构体中偏移，为结构体首地址
思考2：限流算法首先使用key查找红黑树节点，从而找到对应的记录，红黑树节点如何与记录ngx_http_limit_req_node_t结构关联起来呢？在ngx_http_limit_req_module模块可以找到以代码：
size = offsetof(ngx_rbtree_node_t, color) //新建记录分配内存，计算所需空间大小 + offsetof(ngx_http_limit_req_node_t, data) + len; node = ngx_slab_alloc_locked(ctx->shpool, size); node->key = hash; lr = (ngx_http_limit_req_node_t *) &node->color; //color为u_char类型，为什么能强制转换为ngx_http_limit_req_node_t指针类型呢？ lr->len = (u_char) len; lr->excess = 0; ngx_memcpy(lr->data, data, len); ngx_rbtree_insert(&ctx->sh->rbtree, node); ngx_queue_insert_head(&ctx->sh->queue, &lr->queue);
通过分析上面代码，ngx_rbtree_node_s结构体的color与data字段其实是无意义的，结构体的生命形式与最终存储形式是不同的，nginx最终使用以下存储形式存储每条记录；
3.2.2限流算法
上面提到在postconfiguration过程会注册ngx_http_limit_req_handler方法到HTTP处理的NGX_HTTP_PREACCESS_PHASE阶段；
因此在处理HTTP请求时，会执行ngx_http_limit_req_handler方法判断是否需要限流；
3.2.2.1漏桶算法实现
用户可能同时配置若干限流，因此对于HTTP请求，nginx需要遍历所有限流策略，判断是否需要限流；
ngx_http_limit_req_lookup方法实现了漏桶算法，方法返回3种结果：
- NGX_BUSY：请求速率超出限流配置，拒绝请求；
- NGX_AGAIN：请求通过了当前限流策略校验，继续校验下一个限流策略；
- NGX_OK：请求已经通过了所有限流策略的校验，可以执行下一阶段；
- NGX_ERROR：出错
//limit，限流策略；hash，记录key的hash值；data，记录key的数据内容；len，记录key的数据长度；ep，待处理请求数目；account，是否是最后一条限流策略
static ngx_int_t ngx_http_limit_req_lookup(ngx_http_limit_req_limit_t *limit, ngx_uint_t hash, u_char *data, size_t len, ngx_uint_t *ep, ngx_uint_t account)
{
//红黑树查找指定界定
while (node != sentinel) {
if (hash < node->key) {
node = node->left;
continue;
}
if (hash > node->key) {
node = node->right;
continue;
}
//hash值相等，比较数据是否相等
lr = (ngx_http_limit_req_node_t *) &node->color;
rc = ngx_memn2cmp(data, lr->data, len, (size_t) lr->len);
//查找到
if (rc == 0) {
ngx_queue_remove(&lr->queue);
ngx_queue_insert_head(&ctx->sh->queue, &lr->queue); //将记录移动到LRU队列头部
ms = (ngx_msec_int_t) (now - lr->last); //当前时间减去上次访问时间
excess = lr->excess - ctx->rate * ngx_abs(ms) / 1000 + 1000; //待处理请求书-限流速率*时间段+1个请求（速率，请求数等都乘以1000了）
if (excess < 0) {
excess = 0;
}
*ep = excess;
//待处理数目超过burst（等待队列大小），返回NGX_BUSY拒绝请求（没有配置burst时，值为0）
if ((ngx_uint_t) excess > limit->burst) {
return NGX_BUSY;
}
if (account) { //如果是最后一条限流策略，则更新上次访问时间，待处理请求数目，返回NGX_OK
lr->excess = excess;
lr->last = now;
return NGX_OK;
}
//访问次数递增
lr->count++;
ctx->node = lr;
return NGX_AGAIN; //非最后一条限流策略，返回NGX_AGAIN，继续校验下一条限流策略
}
node = (rc < 0) ? node->left : node->right;
}
//假如没有查找到节点，需要新建一条记录
*ep = 0;
//存储空间大小计算方法参照3.2.1节数据结构
size = offsetof(ngx_rbtree_node_t, color)
+ offsetof(ngx_http_limit_req_node_t, data)
+ len;
//尝试淘汰记录（LRU）
ngx_http_limit_req_expire(ctx, 1);
node = ngx_slab_alloc_locked(ctx->shpool, size);//分配空间
if (node == NULL) { //空间不足，分配失败
ngx_http_limit_req_expire(ctx, 0); //强制淘汰记录
node = ngx_slab_alloc_locked(ctx->shpool, size); //分配空间
if (node == NULL) { //分配失败，返回NGX_ERROR
return NGX_ERROR;
}
}
node->key = hash; //赋值
lr = (ngx_http_limit_req_node_t *) &node->color;
lr->len = (u_char) len;
lr->excess = 0;
ngx_memcpy(lr->data, data, len);
ngx_rbtree_insert(&ctx->sh->rbtree, node); //插入记录到红黑树与LRU队列
ngx_queue_insert_head(&ctx->sh->queue, &lr->queue);
if (account) { //如果是最后一条限流策略，则更新上次访问时间，待处理请求数目，返回NGX_OK
lr->last = now;
lr->count = 0;
return NGX_OK;
}
lr->last = 0;
lr->count = 1;
ctx->node = lr;
return NGX_AGAIN; //非最后一条限流策略，返回NGX_AGAIN，继续校验下一条限流策略
}举个例子，假如burst配置为0，待处理请求数初始为excess；令牌产生周期为T；如下图所示
3.2.2.2LRU淘汰策略
上一节叩痛算法中，会执行ngx_http_limit_req_expire淘汰一条记录，每次都是从LRU队列末尾删除；
第二个参数n，当n==0时，强制删除末尾一条记录，之后再尝试删除一条或两条记录；n==1时，会尝试删除一条或两条记录；代码实现如下：
static void ngx_http_limit_req_expire(ngx_http_limit_req_ctx_t *ctx, ngx_uint_t n)
{
//最多删除3条记录
while (n < 3) {
//尾部节点
q = ngx_queue_last(&ctx->sh->queue);
//获取记录
lr = ngx_queue_data(q, ngx_http_limit_req_node_t, queue);
//注意：当为0时，无法进入if代码块，因此一定会删除尾部节点；当n不为0时，进入if代码块，校验是否可以删除
if (n++ != 0) {
ms = (ngx_msec_int_t) (now - lr->last);
ms = ngx_abs(ms);
//短时间内被访问，不能删除，直接返回
if (ms < 60000) {
return;
}
//有待处理请求，不能删除，直接返回
excess = lr->excess - ctx->rate * ms / 1000;
if (excess > 0) {
return;
}
}
//删除
ngx_queue_remove(q);
node = (ngx_rbtree_node_t *)
((u_char *) lr - offsetof(ngx_rbtree_node_t, color));
ngx_rbtree_delete(&ctx->sh->rbtree, node);
ngx_slab_free_locked(ctx->shpool, node);
}
}
