相关代码有两个核心数据结构：

    红黑树：通过红黑树记录每个节点（按照声明时指定的key）的统计信息，方便查找；

    LRU队列：将红黑树上的节点按照最近访问时间排序，时间近的放在队列头部，以便使用LRU队列淘汰旧的节点，避免内存溢出。

这两个关键对象存储在ngx_http_limit_req_shctx_t中：

typedef struct {
    ngx_rbtree_t                  rbtree; /* red-black tree */
    ngx_rbtree_node_t             sentinel; /* the sentinel node of red-black tree */
    ngx_queue_t                   queue; /* used to expire info(LRU algorithm) */
} ngx_http_limit_req_shctx_t;

其中除了rbtree和queue之外，还有一个叫做sentinel的变量，这个变量用作红黑树的NIL节点。

该模块的核心逻辑在函数ngx_http_limit_req_lookup()中，这个函数主要流程是怎样呢？对于每一个请求：

1. 从根节点开始查找红黑树，找到key对应的节点；

2. 找到后修改该点在LRU队列中的位置，表示该点最近被访问过；

3. 执行漏桶算法；

4. 没找到时根据LRU淘汰，腾出空间；

5. 生成并插入新的红黑树节点；

6. 执行下一条限流规则。

流程很清晰，但是代码中牵涉到红黑树、LRU队列等高级数据结构，代码写得简洁易懂

// 漏桶算法核心流程
ngx_http_limit_req_lookup(...){
  while (node != sentinel) {
      // search rbtree
    if (hash < node->key) { node = node->left; continue;} // 1. 从根节点开始查找红黑树
    if (hash > node->key) { node = node->right; continue;}
    rc = ngx_memn2cmp(key->data, lr->data, key->len, (size_t) lr->len);
    if (rc == 0) {// found
      ngx_queue_remove(&lr->queue); // 2. 修改该点在LRU队列中的位置，表示该点最近被访问过
      ngx_queue_insert_head(&ctx->sh->queue, &lr->queue);// 2
      ms = (ngx_msec_int_t) (now - lr->last);
      excess = lr->excess - ctx->rate * ngx_abs(ms) / 1000 + 1000; // 3. 执行漏桶算法
      if (excess < 0) 
          excess = 0;
      if ((ngx_uint_t) excess > limit->burst)
          return NGX_BUSY; // 超过了突发门限，拒绝
      if (account) {// 是否是最后一条规则
        lr->excess = excess;    
        lr->last = now;    
        return NGX_OK; // 未超过限制，通过
      }
      ...
      return NGX_AGAIN; // 6. 执行下一条限流规则
    }
    node = (rc < 0) ? node->left : node->right; // 1
  } // while
  ...
  // not found
  ngx_http_limit_req_expire(ctx, 1); // 4. 根据LRU淘汰，腾出空间
  node = ngx_slab_alloc_locked(ctx->shpool, size); // 5. 生成新的红黑树节点
  ngx_rbtree_insert(&ctx->sh->rbtree, node);// 5. 插入该节点，重新平衡红黑树
  ngx_queue_insert_head(&ctx->sh->queue, &lr->queue);
  if (account) {    
    lr->last = now; 
    lr->count = 0;
    return NGX_OK;
  }
  ...
  return NGX_AGAIN; // 6. 执行下一条限流规则
}

代码有三种返回值，它们的意思是：

• NGX_BUSY 超过了突发门限，拒绝

• NGX_OK 未超过限制，通过

• NGX_AGAIN 未超过限制，但是还有规则未执行，需执行下一条限流规则

上述代码不难理解，但我们还有几个问题：

1. LRU是如何实现的？

2. 漏桶算法是如何实现的？

3. 每个key相关的burst队列在哪里？

【LRU是如何实现的】

    LRU算法的实现很简单，如果一个节点被访问了，那么就把它移到队列的头部，当空间不足需要淘汰节点时，就选出队列尾部的节点淘汰掉，主要体现在如下代码中：

ngx_queue_remove(&lr->queue); // 2. 修改该点在LRU队列中的位置，表示该点最近被访问过
ngx_queue_insert_head(&ctx->sh->queue, &lr->queue);// 2
...
ngx_http_limit_req_expire(ctx, 1); // 4. 根据LRU淘汰，腾出空间

【漏桶算法是如何实现的】

    漏桶算法的实现也比我们想象的简单，其核心是这一行公式excess = lr->excess - ctx->rate * ngx_abs(ms) / 1000 + 1000，这样代码的意思是：excess表示当前key上遗留的请求数，本次遗留的请求数 = 上次遗留的请求数 - 预设速率 X 过去的时间 + 1。这个1表示当前这个请求，由于Nginx内部表示将单位缩小了1000倍，所以1个请求要转换成1000。

excess = lr->excess - ctx->rate * ngx_abs(ms) / 1000 + 1000; // 3. 执行漏桶算法
if (excess < 0) 
    excess = 0;
if ((ngx_uint_t) excess > limit->burst)
    return NGX_BUSY; // 超过了突发门限，拒绝
if (account) { // 是否是最后一条规则
    lr->excess = excess;    
    lr->last = now;    
    return NGX_OK; // 未超过限制，通过
}
...
return NGX_AGAIN; // 6. 执行下一条限流规则

上述代码受限算出当前key上遗留的请求数，如果超过了burst，就直接拒绝；由于Nginx允许多条限速规则同时起作用，如果已是最后一条规则，则允许通过，否则执行下一条规则。

【单个key相关的burst队列在哪里】

    没有单个key相关的burst队列。上面代码中我们看到当到达最后一条规则时，只要excess<limit->burst限速模块就会返回NGX_OK，并没有把多余请求放入队列的操作，这是因为Nginx是基于timer来管理请求的，当限速模块返回NGX_OK时，调度函数会计算一个延迟处理的时间，同时把这个请求放入到共享的timer队列中（一棵按等待时间从小到大排序的红黑树）。

ngx_http_limit_req_handler(ngx_http_request_t *r)
{
    ...
    for (n = 0; n < lrcf->limits.nelts; n++) {
        ...
        ngx_shmtx_lock(&ctx->shpool->mutex);// 获取锁
        rc = ngx_http_limit_req_lookup(limit, hash, &key, &excess, // 执行漏桶算法
                                       (n == lrcf->limits.nelts - 1));
        ngx_shmtx_unlock(&ctx->shpool->mutex);// 释放锁
        ...
        if (rc != NGX_AGAIN)
            break;
    }
    ...
    delay = ngx_http_limit_req_account(limits, n, &excess, &limit);// 计算当前请求需要的延迟时间
    if (!delay) {
        return NGX_DECLINED;// 不需要延迟，交给后续的handler进行处理
    }
    ...
    ngx_add_timer(r->connection->write, delay);// 否则将请求放到定时器队列里
    return NGX_AGAIN; // the request has been successfully processed, the request must be suspended until some event. http://www.nginxguts.com/2011/01/phases/
}

    我们看到ngx_http_limit_req_handler()调用了函数ngx_http_limit_req_lookup()，并根据其返回值决定如何操作：或是拒绝，或是交给下一个handler处理，或是将请求放入定期器队列。当限速规则都通过后，该hanlder通过调用函数ngx_http_limit_req_account()得出当前请求需要的延迟时间，如果不需要延迟，就将请求交给后续的handler进行处理，否则将请求放到定时器队列里。注意这个定时器队列是共享的，并没有为单独的key(比如，每个IP地址)设置队列。