但是请注意，虽然设置burst和nodelay能够降低突发请求的处理时间，但是长期来看并不会提高吞吐量的上限，长期吞吐量的上限是由rate决定的，因为nodelay只能保证burst的请求被立即处理，但Nginx会限制队列元素释放的速度，就像是限制了令牌桶中令牌产生的速度。
看到这里你可能会问，加入了nodelay参数之后的限速算法，到底算是哪一个“桶”，是漏桶算法还是令牌桶算法？当然还算是漏桶算法。考虑一种情况，令牌桶算法的token为耗尽时会怎么做呢？由于它有一个请求队列，所以会把接下来的请求缓存下来，缓存多少受限于队列大小。但此时缓存这些请求还有意义吗？如果server已经过载，缓存队列越来越长，RT越来越高，即使过了很久请求被处理了，对用户来说也没什么价值了。所以当token不够用时，最明智的做法就是直接拒绝用户的请求，这就成了漏桶算法，哈哈~
源码剖析经过上面的示例，我们队请求限速模块有了一定的认识，现在我们深入剖析代码实现。按请求速率限流模块ngx_http_limit_req_module代码位于src/http/modules/ngx_http_limit_req_module.c，900多好代码可谓短小精悍。相关代码有两个核心数据结构：
红黑树：通过红黑树记录每个节点（按照声明时指定的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()中，这个函数主要流程是怎样呢？对于每一个请求：
从根节点开始查找红黑树，找到key对应的节点；
找到后修改该点在LRU队列中的位置，表示该点最近被访问过；
执行漏桶算法；
没找到时根据LRU淘汰，腾出空间；
生成并插入新的红黑树节点；
执行下一条限流规则。
流程很清晰，但是代码中牵涉到红黑树、LRU队列等高级数据结构，是不是会写得很复杂？好在Nginx作者功力深厚，代码写得简洁易懂，哈哈~
// 漏桶算法核心流程 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 未超过限制，但是还有规则未执行，需执行下一条限流规则
上述代码不难理解，但我们还有几个问题：
LRU是如何实现的？
漏桶算法是如何实现的？
每个key相关的burst队列在哪里？
LRU是如何实现的