摘要：如果當(dāng)前需要延遲處理，又會把請求放到定時器中，等到定時器過期以后，執(zhí)行寫事件回調(diào)，這個函數(shù)里會執(zhí)行，重新進(jìn)行的個階段。

ngx_http_limit_req_module 是 Nginx 官方提供的一個 http 模塊，它工作在 NGX_HTTP_PREACCESS_PHASE 階段，通過在 nginx.conf 中進(jìn)行簡單地配置，我們可以輕易地對請求速率進(jìn)行限制。

官方文檔地址

                        Example Configuration

http {
    limit_req_zone $binary_remote_addr zone=one:10m rate=1r/s;

...

server {

    ...

    location /search/ {
        limit_req zone=one burst=5;
    }

Syntax:    limit_req zone=name [burst=number] [nodelay]; 

Default:    — 

Context:    http, server, location

該指令為名為 name 的共享內(nèi)存設(shè)置一個突發(fā)請求限制大小（burst）和一個 nodelay 標(biāo)志位

Syntax:    limit_req_log_level info | notice | warn | error; 

Default:     

limit_req_log_level error; 

Context:    http, server, location

limit_req_log_level 這條指令用來設(shè)置當(dāng)觸發(fā)請求限制時，記錄日志的級別，默認(rèn)是 error

Syntax:    limit_req_status code; 

Default:    

limit_req_status 503; 

Context:    http, server, location

limit_req_status 用來設(shè)置服務(wù)器因請求限制設(shè)置而拒絕一個請求時，返回的狀態(tài)碼，默認(rèn)是 503

Syntax:    limit_req_zone key zone=name:size rate=rate; 

Default:    —  

Context:    http

該指令用來分配一塊名為 name，大小為 size 的共享內(nèi)存，
這塊共享內(nèi)存服務(wù)于一個特定的 key，限制了請求頻率不得超過 rate，注意該指令只能配置在 http{} 塊下

為了能夠讓單機(jī)上所有的 worker 進(jìn)程共享一份最新的關(guān)于請求限制的數(shù)據(jù)，Nginx 把這些“域”的數(shù)據(jù)都放在共享內(nèi)存中。

這個模塊很靈活得允許設(shè)置多個不同的“域”（我指的“域”是指同一類的 key，例如 $binary_remote_addr$uri，每塊共享內(nèi)存用來存對應(yīng)“域”的信息），每當(dāng)一個請求來臨時，在 preaccess 階段進(jìn)行檢查，通過遍歷每個“域”，在每個“域”的紅黑樹上找對應(yīng) key 實例化以后 對應(yīng)的節(jié)點，然后根據(jù)漏桶算法，計算同一個 key 上次訪問的時間到現(xiàn)在，經(jīng)過這段時間的處理，還應(yīng)該剩下的請求數(shù)目，然后再允許有多個突發(fā)請求（這里就是令牌桶的思想了），根據(jù)是否超過突發(fā)請求限制，決定是吐對應(yīng)的禁止?fàn)顟B(tài)碼還是延遲處理這個請求。

另外一點為了不讓每個“域”的紅黑樹急劇膨脹而導(dǎo)致這個“域”的內(nèi)存耗盡，這個模塊還設(shè)置了一個 LRU 隊列（當(dāng)然也是每個“域”一個隊列），將紅黑樹上的節(jié)點按最近最久未使用排成一個隊列，然后每當(dāng)要新建節(jié)點的時候，都去嘗試淘汰一些節(jié)點（為了不長時間處于淘汰的循環(huán)中，最多淘汰 3 個節(jié)點）。
如果當(dāng)前需要延遲處理，Nginx 又會把請求放到定時器中，等到定時器過期以后，執(zhí)行寫事件回調(diào) ngx_http_limit_req_delay，這個函數(shù)里會執(zhí)行 ngx_http_core_run_phases，重新進(jìn)行 HTTP 的 11 個階段。

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;

這個數(shù)據(jù)結(jié)構(gòu)會被放在共享內(nèi)存中，記錄了一顆紅黑樹和一個隊列。

紅黑樹用來記錄每個 “域”（即根據(jù) limit_req_zone 里定義的 key 得到）目前的狀況

隊列將紅黑樹節(jié)點按更新時間從早到晚串起來，用來淘汰過于陳舊的節(jié)點（LRU）

該數(shù)據(jù)結(jié)構(gòu)可以由下面的 ngx_http_limit_req_ctx_t 里的 sh 成員索引得到。

typedef struct {
    u_char                       color;
    u_char                       dummy;
    u_short                      len;
    ngx_queue_t                  queue;
    ngx_msec_t                   last;
    /* integer value, 1 corresponds to 0.001 r/s */
    ngx_uint_t                   excess;
    ngx_uint_t                   count; /* 標(biāo)記使用的 */
    u_char                       data[1];
} ngx_http_limit_req_node_t; /* rbtree node */

表示紅黑樹節(jié)點信息的數(shù)據(jù)結(jié)構(gòu)，這個數(shù)據(jù)結(jié)構(gòu)的設(shè)計十分巧妙，由于紅黑樹上用的節(jié)點結(jié)構(gòu)只能是 ngx_rbtree_node_t，所以和它實際掛到紅黑樹上的節(jié)點的數(shù)據(jù)結(jié)構(gòu)是連續(xù)存放的，且共用了成員 color 和 dummy（也就是 ngx_rbtree_node_t 的 data 成員），另外，由于 key 是變成的，這里它只存了這個 key 的第一個字符（data），其他的字符緊跟在這個數(shù)據(jù)結(jié)構(gòu)后面，也是連續(xù)的，所以在要新建一個節(jié)點的時候，計算需要的內(nèi)存大小應(yīng)該是

size = offsetof(ngx_rbtree_node_t, color)
           + offsetof(ngx_http_limit_req_node_t, data)
           + key->len;

計算出 color 在 ngx_rbtree_node_t 里的偏移（這樣等于算出了 ngx_rbtree_node_t 在color 以前的成員占用內(nèi)存大小）；再計算出 data 在 ngx_http_limit_req_node_t 的偏移，最后加上 key 的長度，這就是整個節(jié)點信息結(jié)構(gòu)需要的內(nèi)存的大小。

另外 len 是變長 key 的長度；queue 成員是用來標(biāo)識這個節(jié)點在 LRU 隊列里的位置的，記錄了上個節(jié)點和下一個節(jié)點；last 是上次更新時間；excess 表示上次處理完后剩下來的請求數(shù) * 1000（leaky bucket algorithm）

typedef struct {
    ngx_http_limit_req_shctx_t  *sh;
    ngx_slab_pool_t             *shpool; /* slab shared memory pool */
    /* integer value, 1 corresponds to 0.001 r/s */
    ngx_uint_t                   rate; /* about limit_req_zone */
    ngx_http_complex_value_t     key; /* about limit_req_zone */
    ngx_http_limit_req_node_t   *node; /* point to one node in red-black tree */
} ngx_http_limit_req_ctx_t;

該結(jié)構(gòu)體存放根據(jù) limit_req_zone 指令創(chuàng)建的共享內(nèi)存的相關(guān)上下文信息。其中

rate 和 key 均是根據(jù)指令 limit_req_zone 而解析得到

node 成員指向了一個節(jié)點

typedef struct {
    ngx_shm_zone_t              *shm_zone;
    /* integer value, 1 corresponds to 0.001 r/s */
    ngx_uint_t                   burst;
    ngx_uint_t                   nodelay; /* unsigned  nodelay:1 */
} ngx_http_limit_req_limit_t;

存放了 limit_req 指令的相關(guān)配置信息，例如 burst 表示一個 “域”（key）最多允許的突發(fā)請求數(shù)，nodelay 表示是否要延遲處理那些超出請求速率的請求。

這個結(jié)構(gòu)體可以通過 ngx_http_limit_req_conf_t 的 limits 成員索引得到。并且shm_zone 的 data 指向了 ngx_http_limit_req_ctx_t 結(jié)構(gòu)體。

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;

這個結(jié)構(gòu)體存放配置項信息，值得提一下的是 limits 成員，這個動態(tài)數(shù)組把所有創(chuàng)建的共享內(nèi)存信息給存放起來了，每個成員都指向一個 ngx_http_limit_req_limit_t 結(jié)構(gòu)。

功能：對指令 limit_req_zone 指令進(jìn)行解析，創(chuàng)建對應(yīng)的共享內(nèi)存，設(shè)置 rate, key 等參數(shù)到 ngx_http_limit_req_ctx_t 結(jié)構(gòu)體變量中

static char *
ngx_http_limit_req_zone(ngx_conf_t *cf, ngx_command_t *cmd, void *conf)
{
    ......
    
    /* 只要解析到一條 limit_req_zone 指令，就會創(chuàng)建一個 ctx */
    ctx = ngx_pcalloc(cf->pool, sizeof(ngx_http_limit_req_ctx_t));
    if (ctx == NULL) {
        return NGX_CONF_ERROR;
    }
    
    ......

    size = 0;
    rate = 1;
    scale = 1; /* 單位轉(zhuǎn)換時用 */
    name.len = 0;

    for (i = 2; i < cf->args->nelts; i++) {

        if (ngx_strncmp(value[i].data, "zone=", 5) == 0) {
            /* 
             * 這里主要是在解析 zone 的 name 和 size 
             * 代碼比較簡單，可以自行閱讀
             */
             ......
        }

        if (ngx_strncmp(value[i].data, "rate=", 5) == 0) {
            /*
             * 這里主要是解析 rate，包括解析單位 r/s 和 r/m
             * 計算對應(yīng)的 scale
             */
             ......
        }

        ngx_conf_log_error(NGX_LOG_EMERG, cf, 0,
                           "invalid parameter "%V"", &value[i]);
        return NGX_CONF_ERROR;
    }

    ......
    
    /* 實際使用的 rate 會被放大 1000 倍 */
    ctx->rate = rate * 1000 / scale;
    
    /* 創(chuàng)建一塊共享內(nèi)存 name size tag */
    shm_zone = ngx_shared_memory_add(cf, &name, size,
                                     &ngx_http_limit_req_module);
    if (shm_zone == NULL) {
        return NGX_CONF_ERROR;
    }

    if (shm_zone->data) {
        ctx = shm_zone->data;

        ngx_conf_log_error(NGX_LOG_EMERG, cf, 0,
                           "%V "%V" is already bound to key "%V"",
                           &cmd->name, &name, &ctx->key.value);
        return NGX_CONF_ERROR;
    }

    /* 設(shè)置好自定義的初始化方法，設(shè)置好 ctx 的索引 */
    shm_zone->init = ngx_http_limit_req_init_zone;
    shm_zone->data = ctx;

    return NGX_CONF_OK;
}

功能：該函數(shù)負(fù)責(zé)初始化放在共享內(nèi)存中的上下文信息，包括紅黑樹的初始化，隊列初始化，所以每個“域”

static ngx_int_t
ngx_http_limit_req_init_zone(ngx_shm_zone_t *shm_zone, void *data)
{
    ngx_http_limit_req_ctx_t  *octx = data;

    size_t                     len;
    ngx_http_limit_req_ctx_t  *ctx;

    ctx = shm_zone->data;

    if (octx) {
        /* 
         * 這個過程發(fā)生在 reload 的時候
         * 如果對應(yīng)共享內(nèi)存的 key 沒變，直接復(fù)用就行了
         */
        if (ctx->key.value.len != octx->key.value.len
            || ngx_strncmp(ctx->key.value.data, octx->key.value.data,
                           ctx->key.value.len)
               != 0)
        {
            ngx_log_error(NGX_LOG_EMERG, shm_zone->shm.log, 0,
                          "limit_req "%V" uses the "%V" key "
                          "while previously it used the "%V" key",
                          &shm_zone->shm.name, &ctx->key.value,
                          &octx->key.value);
            return NGX_ERROR;
        }
        
        ctx->sh = octx->sh;
        ctx->shpool = octx->shpool;

        return NGX_OK;
    }

    ctx->shpool = (ngx_slab_pool_t *) shm_zone->shm.addr;

    if (shm_zone->shm.exists) {
        ctx->sh = ctx->shpool->data;

        return NGX_OK;
    }

    /* 從 slab 池申請一塊存放 ngx_http_limit_req_shctx_t 的內(nèi)存 */
    ctx->sh = ngx_slab_alloc(ctx->shpool, sizeof(ngx_http_limit_req_shctx_t));
    if (ctx->sh == NULL) {
        return NGX_ERROR;
    }

    ctx->shpool->data = ctx->sh;

    /* 初始化這個“域”的紅黑樹和 LRU 隊列 */
    ngx_rbtree_init(&ctx->sh->rbtree, &ctx->sh->sentinel,
                    ngx_http_limit_req_rbtree_insert_value);

    ngx_queue_init(&ctx->sh->queue);
    
    ......

    return NGX_OK;
}

功能：對指令 limit_req 指令進(jìn)行解析，判斷出設(shè)置的共享內(nèi)存名字，將其掛到 ngx_http_limit_req_limit_t 的 limits 數(shù)組

static char *
ngx_http_limit_req(ngx_conf_t *cf, ngx_command_t *cmd, void *conf)
{
    ......

    value = cf->args->elts;

    shm_zone = NULL;
    burst = 0;
    nodelay = 0;

    for (i = 1; i < cf->args->nelts; i++) {

        if (ngx_strncmp(value[i].data, "zone=", 5) == 0) {

            s.len = value[i].len - 5;
            s.data = value[i].data + 5;
            
            /* 
             * 如果這條 limit_req 指令在對應(yīng)聲明共享內(nèi)存的 limit_req_zone 指令
             * 之前的話，這里也會先創(chuàng)建好這個 shm_zone, 下次執(zhí)行到相應(yīng)的
             * limit_req_zone 指令，只是把 size 改變了下
             * 反之如果 limit_req_zone 先執(zhí)行，這次操作就是從 cycle->shared_memory
             * 上面把對應(yīng)的 shm_zone 拿下來而已
             */
            shm_zone = ngx_shared_memory_add(cf, &s, 0,
                                             &ngx_http_limit_req_module);
            if (shm_zone == NULL) {
                return NGX_CONF_ERROR;
            }

            continue;
        }

        if (ngx_strncmp(value[i].data, "burst=", 6) == 0) {
            
            /* 解析 burst，這個“域”允許的最大突發(fā)請求數(shù) */
            burst = ngx_atoi(value[i].data + 6, value[i].len - 6);
            if (burst <= 0) {
                ngx_conf_log_error(NGX_LOG_EMERG, cf, 0,
                                   "invalid burst rate "%V"", &value[i]);
                return NGX_CONF_ERROR;
            }

            continue;
        }

        if (ngx_strcmp(value[i].data, "nodelay") == 0) {
            nodelay = 1;
            continue;
        }

        ngx_conf_log_error(NGX_LOG_EMERG, cf, 0,
                           "invalid parameter "%V"", &value[i]);
        return NGX_CONF_ERROR;
    }

    ......

    limits = lrcf->limits.elts;

    if (limits == NULL) {
        if (ngx_array_init(&lrcf->limits, cf->pool, 1,
                           sizeof(ngx_http_limit_req_limit_t))
            != NGX_OK)
        {
            return NGX_CONF_ERROR;
        }
    }
    
    /* 假如 limit_req 重復(fù)指定一塊相同的共享內(nèi)存（由 limit_req_zone 指令指定），則會返回錯誤 */
    for (i = 0; i < lrcf->limits.nelts; i++) {
        if (shm_zone == limits[i].shm_zone) {
            return "is duplicate";
        }
    }
    
    /* 將這個“域”的 ngx_http_limit_req_limit_t 結(jié)構(gòu)體設(shè)置好，放到 limits 數(shù)組 */
    limit = ngx_array_push(&lrcf->limits);
    if (limit == NULL) {
        return NGX_CONF_ERROR;
    }
    
    /* 
     * 到時候會把 shm_zone->data 指向 ngx_http_limit_req_ctx_t
     * 這樣就和 ngx_http_limit_req_ctx_t 聯(lián)系起來了
     */
    limit->shm_zone = shm_zone;
    limit->burst = burst * 1000; /* burst 也放大 1000 倍 */
    limit->nodelay = nodelay;

    return NGX_CONF_OK;
}

功能：創(chuàng)建 ngx_http_limit_req_conf_t 結(jié)構(gòu)體，代碼比較簡單。

功能：合并配置項，代碼很簡單。

功能：設(shè)置鉤子函數(shù) ngx_http_limit_req_handler 到 ngx_http_core_main_conf 的 phases 數(shù)組里（NGX_HTTP_PREACCESS_PHASE），代碼很簡單。

功能：遍歷設(shè)置好的共享內(nèi)存，調(diào)用 ngx_http_limit_req_lookup 來判斷是否需要進(jìn)行禁用或者延遲，如果禁用，則返回設(shè)置的對應(yīng)狀態(tài)碼；如果需要延遲，則將這條連接上的寫事件處理方法設(shè)置為 ngx_http_limit_req_delay，并放入定時器中，過期時間通過 ngx_http_limit_req_account 計算出來

static ngx_int_t
ngx_http_limit_req_handler(ngx_http_request_t *r)
{
    uint32_t                     hash;
    ngx_str_t                    key;
    ngx_int_t                    rc;
    ngx_uint_t                   n, excess;
    ngx_msec_t                   delay;
    ngx_http_limit_req_ctx_t    *ctx;
    ngx_http_limit_req_conf_t   *lrcf;
    ngx_http_limit_req_limit_t  *limit, *limits;

    if (r->main->limit_req_set) {
        /* 如果這個請求的主請求已經(jīng)進(jìn)行了該階段的檢查
         * 直接返回 NGX_DCLIEND，讓下一個 HTTP 模塊介入請求
         */
        return NGX_DECLINED;
    }

    lrcf = ngx_http_get_module_loc_conf(r, ngx_http_limit_req_module);
    limits = lrcf->limits.elts;

    excess = 0;

    rc = NGX_DECLINED;

#if (NGX_SUPPRESS_WARN)
    limit = NULL;
#endif
    
    /* 遍歷設(shè)置好的“域” */
    for (n = 0; n < lrcf->limits.nelts; n++) {

        limit = &limits[n];

        ctx = limit->shm_zone->data;

        if (ngx_http_complex_value(r, &ctx->key, &key) != NGX_OK) {
            return NGX_HTTP_INTERNAL_SERVER_ERROR;
        }

        if (key.len == 0) {
            continue;
        }

        if (key.len > 65535) {
            ngx_log_error(NGX_LOG_ERR, r->connection->log, 0,
                          "the value of the "%V" key "
                          "is more than 65535 bytes: "%V"",
                          &ctx->key.value, &key);
            continue;
        }
    
        /* 計算 hash */
        hash = ngx_crc32_short(key.data, key.len);

        ngx_shmtx_lock(&ctx->shpool->mutex);
        
        /* 在這個"域" 的紅黑樹上找這個 key 對應(yīng)的節(jié)點 */
        rc = ngx_http_limit_req_lookup(limit, hash, &key, &excess,
                                       (n == lrcf->limits.nelts - 1));

        ngx_shmtx_unlock(&ctx->shpool->mutex);

        ngx_log_debug4(NGX_LOG_DEBUG_HTTP, r->connection->log, 0,
                       "limit_req[%ui]: %i %ui.%03ui",
                       n, rc, excess / 1000, excess % 1000);

        if (rc != NGX_AGAIN) {
            /* 只要 ngx_http_limit_req_lookup 返回的不是 NGX_AGAIN，就 break */
            break;
        }
    }

    if (rc == NGX_DECLINED) {
        return NGX_DECLINED;
    }

    r->main->limit_req_set = 1;

    if (rc == NGX_BUSY || rc == NGX_ERROR) {

        if (rc == NGX_BUSY) {
            ngx_log_error(lrcf->limit_log_level, r->connection->log, 0,
                          "limiting requests, excess: %ui.%03ui by zone "%V"",
                          excess / 1000, excess % 1000,
                          &limit->shm_zone->shm.name);
        }

        while (n--) {
            /* 經(jīng)歷過的 n 個“域”，取出 node，將 count-- */
            ctx = limits[n].shm_zone->data;

            if (ctx->node == NULL) {
                continue;
            }

            ngx_shmtx_lock(&ctx->shpool->mutex);

            ctx->node->count--;

            ngx_shmtx_unlock(&ctx->shpool->mutex);

            ctx->node = NULL;
        }

        return lrcf->status_code;
    }

    /* rc == NGX_AGAIN || rc == NGX_OK */

    if (rc == NGX_AGAIN) {
        excess = 0;
    }
    
    /* 計算好延遲時間 */
    delay = ngx_http_limit_req_account(limits, n, &excess, &limit);

    if (!delay) {
        return NGX_DECLINED;
    }

    ngx_log_error(lrcf->delay_log_level, r->connection->log, 0,
                  "delaying request, excess: %ui.%03ui, by zone "%V"",
                  excess / 1000, excess % 1000, &limit->shm_zone->shm.name);

    if (ngx_handle_read_event(r->connection->read, 0) != NGX_OK) {
        /* 
         * 這里處理下這條連接的讀事件，是為了如果在這段延遲的時間內(nèi)，客戶端
         * 主動關(guān)閉了連接，Nginx 也可以通過事件調(diào)度器感知到，從而及時斷開連接
         */
        return NGX_HTTP_INTERNAL_SERVER_ERROR;
    }

    r->read_event_handler = ngx_http_test_reading;
    r->write_event_handler = ngx_http_limit_req_delay;
    /* 添加到定時器紅黑樹上，等到過期時調(diào)用 ngx_http_limit_req_delay */
    ngx_add_timer(r->connection->write, delay);

    /* 
     * 這里返回 NGX_AGAIN，讓這個模塊有機(jī)會再介入這個請求，
     * 其實也很好理解，畢竟 delay 之后，不能保證那個時刻這個請求涉及到的“域”
     * 就一定沒有超過該“域” 的請求設(shè)置限制了，所以還需要再次計算
     */
    return NGX_AGAIN;
}

功能：這個函數(shù)是核心，在某個“域”的紅黑樹上找到對應(yīng) hash 值的節(jié)點，根據(jù)漏桶算法，以固定速率處理請求，但又不僅僅是漏桶算法，這里還包含了令牌桶算法的突發(fā)門限，具體表現(xiàn)在只要不超過突發(fā)門限值，就不會返回 NGX_BUSY，這樣就可以處理一定量的突發(fā)請求了。

返回值意義：

- NGX_BUSY 超過了突發(fā)門限
- NGX_OK 沒有超過限制的請求頻率
- NGX_AGAIN 超過限制的請求頻率，但是沒有到達(dá)突發(fā)門限

static ngx_int_t
ngx_http_limit_req_lookup(ngx_http_limit_req_limit_t *limit, ngx_uint_t hash,
    ngx_str_t *key, ngx_uint_t *ep, ngx_uint_t account)
{
    size_t                      size;
    ngx_int_t                   rc, excess;
    ngx_msec_t                  now;
    ngx_msec_int_t              ms;
    ngx_rbtree_node_t          *node, *sentinel;
    ngx_http_limit_req_ctx_t   *ctx;
    ngx_http_limit_req_node_t  *lr;

    now = ngx_current_msec;

    ctx = limit->shm_zone->data;

    node = ctx->sh->rbtree.root;
    sentinel = ctx->sh->rbtree.sentinel;

    while (node != sentinel) {

        if (hash < node->key) {
            node = node->left;
            continue;
        }1

        if (hash > node->key) {
            node = node->right;
            continue;
        }

        /* hash == node->key */

        lr = (ngx_http_limit_req_node_t *) &node->color;

        rc = ngx_memn2cmp(key->data, lr->data, key->len, (size_t) lr->len);
        
        /* hash 值相同，且 key 相同，才算是找到 */
        if (rc == 0) {
            /* 這個節(jié)點最近才訪問，放到隊列首部，最不容易被淘汰（LRU 思想）*/
            ngx_queue_remove(&lr->queue);
            ngx_queue_insert_head(&ctx->sh->queue, &lr->queue);

            /*
             * 漏桶算法：以固定速率接受請求，每秒接受 rate 個請求，
             * ms 是距離上次處理這個 key 到現(xiàn)在的時間，單位 ms
             * lr->excess 是上次還遺留著被延遲的請求數(shù)（*1000）
             * excess = lr->excess - ctx->rate * ngx_abs(ms) / 1000 + 1000;
             * 本次還會遺留的請求數(shù)就是上次遺留的減去這段時間可以處理掉的加上這個請求本身（之前 burst 和 rate 都放大了 1000 倍）
             */
            ms = (ngx_msec_int_t) (now - lr->last);

            excess = lr->excess - ctx->rate * ngx_abs(ms) / 1000 + 1000;

            if (excess < 0) {
                /* 全部處理完了 */
                excess = 0;
            }

            *ep = excess;

            if ((ngx_uint_t) excess > limit->burst) {
            /* 這段時間處理之后，遺留的請求數(shù)超出了突發(fā)請求限制 */
                return NGX_BUSY;
            }

            if (account) {
                /* 這個請求到了最后一個“域”的限制
                 * 更新上次遺留請求數(shù)和上次訪問時間
                 * 返回 NGX_OK 表示沒有達(dá)到請求限制的頻率
                 */
                lr->excess = excess;
                lr->last = now;
                return NGX_OK;
            }
            
            /* 
             * count++；
             * 把這個“域”的 ctx->node 指針指向這個節(jié)點
             * 這個在 ngx_http_limit_req_handler 里用到
             */
            lr->count++;
            
            /* 這一步是為了在 ngx_http_limit_req_account 里更新這些訪問過的節(jié)點的信息 */
            ctx->node = lr;
            
            /* 返回 NGX_AGAIN，會進(jìn)行下一個“域”的檢查 */
            return NGX_AGAIN;
        }

        node = (rc < 0) ? node->left : node->right;
    }
    
    /* 沒有在紅黑樹上找到節(jié)點 */
    *ep = 0;

    /* 
     * 新建一個節(jié)點，需要的內(nèi)存大小，包括了紅黑樹節(jié)點大小
     * ngx_http_limit_req_node_t 還有 key 的長度
     */
    size = offsetof(ngx_rbtree_node_t, color)
           + offsetof(ngx_http_limit_req_node_t, data)
           + key->len;
    
    /* 先進(jìn)行 LRU 淘汰，傳入 n=1，則最多淘汰 2 個節(jié)點 */
    ngx_http_limit_req_expire(ctx, 1);
    
    /* 由于調(diào)用 ngx_http_limit_req_lookup 之前已經(jīng)上過鎖，這里不用再上 */
    node = ngx_slab_alloc_locked(ctx->shpool, size);

    if (node == NULL) {
        /* 分配失敗考慮再進(jìn)行一次 LRU 淘汰，及時釋放共享內(nèi)存空間，這里 n = 0，最多淘汰 3 個節(jié)點 */
        ngx_http_limit_req_expire(ctx, 0);

        node = ngx_slab_alloc_locked(ctx->shpool, size);
        if (node == NULL) {
            ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0,
                          "could not allocate node%s", ctx->shpool->log_ctx);
            return NGX_ERROR;
        }
    }
    
    /* 設(shè)置相關(guān)的信息 */
    node->key = hash;

    lr = (ngx_http_limit_req_node_t *) &node->color;

    lr->len = (u_short) key->len;
    lr->excess = 0;

    ngx_memcpy(lr->data, key->data, key->len);

    ngx_rbtree_insert(&ctx->sh->rbtree, node);

    ngx_queue_insert_head(&ctx->sh->queue, &lr->queue);

    if (account) {
        /* 同樣地，如果這是最后一個“域”的檢查，就更新 last 和 count，返回 NGX_OK */
        lr->last = now;
        lr->count = 0;
        return NGX_OK;
    }
    
    /* 否則就令 count = 1，把節(jié)點放到 ctx 上 */
    lr->last = 0;
    lr->count = 1;

    ctx->node = lr;

    return NGX_AGAIN;
}

功能：從隊列（ngx_http_limit_req_shctx_t->queue）尾部遍歷，將過期的紅黑樹節(jié)點刪除，及時釋放共享內(nèi)存空間

static void
ngx_http_limit_req_expire(ngx_http_limit_req_ctx_t *ctx, ngx_uint_t n)
{
    ngx_int_t                   excess;
    ngx_msec_t                  now;
    ngx_queue_t                *q;
    ngx_msec_int_t              ms;
    ngx_rbtree_node_t          *node;
    ngx_http_limit_req_node_t  *lr;

    now = ngx_current_msec;

    /*
     * n == 1 deletes one or two zero rate entries
     * n == 0 deletes oldest entry by force
     *        and one or two zero rate entries
     */
    
    /* 從這里可以看到，最多只會刪除 2 - n + 1 個節(jié)點 */
    while (n < 3) {

        if (ngx_queue_empty(&ctx->sh->queue)) {
            return;
        }
        
        /* 隊列尾部的節(jié)點最近最久沒有訪問，最有可能被淘汰 */
        q = ngx_queue_last(&ctx->sh->queue);
        
        /* 取出對應(yīng)節(jié)點 */
        lr = ngx_queue_data(q, ngx_http_limit_req_node_t, queue);

        /* 
         * 從這里可以看到，如果 count 大于 0，則不會被淘汰
         * 所以看到 ngx_http_limit_req_handler 里如果這個 key 在某個“域”超過請求限制頻率時，就把那個節(jié)點的 count++，避免不小心把節(jié)點刪除
         *  
         */
        if (lr->count) {

            /*
             * There is not much sense in looking further,
             * because we bump nodes on the lookup stage.
             */

            return;
        }

        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);
    }
}

功能：這個函數(shù)負(fù)責(zé)對目前的這個請求計算一個延時時間，計算規(guī)則是

遍歷每個之前在 ngx_http_limit_req_lookup 里訪問過的“域”

如果這個“域”設(shè)置了 nodelay，跳到下一個

否則根據(jù)漏桶算法，和 ngx_http_limit_req_lookup 一樣的做法，計算出從上次訪問到現(xiàn)在，應(yīng)該剩下的請求數(shù)，除以 rate，得到了這些請求數(shù)應(yīng)該延遲的時間

取最大值

其實這些值都可以在 ngx_http_limit_req_lookup 里計算出來，不過為了讓一個函數(shù)做一件事，這樣設(shè)計條理更加清晰吧。

static ngx_msec_t
ngx_http_limit_req_account(ngx_http_limit_req_limit_t *limits, ngx_uint_t n,
    ngx_uint_t *ep, ngx_http_limit_req_limit_t **limit)
{
    ngx_int_t                   excess;
    ngx_msec_t                  now, delay, max_delay;
    ngx_msec_int_t              ms;
    ngx_http_limit_req_ctx_t   *ctx;
    ngx_http_limit_req_node_t  *lr;

    /* 
     * excess 是之前在 ngx_http_limit_req_lookup 
     * 里遍歷到的最后一個“域”針對這個請求經(jīng)過漏桶計算后
     * 應(yīng)該剩下的請求數(shù); limit 則是最后一個“域”的配置
     */
    excess = *ep;

    if (excess == 0 || (*limit)->nodelay) {
        /* 配置項里設(shè)置了 nodelay 或者 excess = 0 */
        max_delay = 0;

    } else {
        ctx = (*limit)->shm_zone->data;
        /* 
         * 剩下了 excess 個請求，加請求的速率是 rate，那么延遲
         * 就是 excess * 1000 / ctx->rate，這里乘以 1000 是因為 rate 的單位是 ms
         */
        max_delay = excess * 1000 / ctx->rate;
    }

    while (n--) {
        /* 反向遍歷之前遍歷過的“域” */
        ctx = limits[n].shm_zone->data;
        /* 為了更新信息，所以才需要在 ctx 里放一個 node */
        lr = ctx->node;

        if (lr == NULL) {
            continue;
        }

        ngx_shmtx_lock(&ctx->shpool->mutex);

        now = ngx_current_msec;
        ms = (ngx_msec_int_t) (now - lr->last);

        excess = lr->excess - ctx->rate * ngx_abs(ms) / 1000 + 1000;

        if (excess < 0) {
            excess = 0;
        }
        
        /* 更新節(jié)點上的信息 */
        lr->last = now;
        lr->excess = excess;
        lr->count--;

        ngx_shmtx_unlock(&ctx->shpool->mutex);

        ctx->node = NULL;

        if (limits[n].nodelay) {
            continue;
        }

        delay = excess * 1000 / ctx->rate;

        if (delay > max_delay) {
            max_delay = delay;
            *ep = excess;
            *limit = &limits[n];
        }
    }
    
    /* 這里就計算出了一個最大延遲值 */
    return max_delay;
}

功能：該模塊自定義的紅黑樹節(jié)點插入方法，key 就是根據(jù)用戶配置的 limit_req_zone 指令里的 key 字段，hash 方法是 ngx_crc32_short

static void
ngx_http_limit_req_rbtree_insert_value(ngx_rbtree_node_t *temp,
    ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel)
{
    ngx_rbtree_node_t          **p;
    ngx_http_limit_req_node_t   *lrn, *lrnt;

    for ( ;; ) {

        if (node->key < temp->key) {

            p = &temp->left;

        } else if (node->key > temp->key) {

            p = &temp->right;

        } else { /* node->key == temp->key */
            /*
             * 值相等不見得 key 一定相同，存在 hash 沖突的
             * 前面說過，ngx_http_limit_req_node_t 和 ngx_rbtree_node_t 
             * 復(fù)用了 color 和 data 這兩個字段，ngx_http_limit_req_node_t 的地址
             * 就是 ngx_rbtree_node_t 里的 color 字段的地址
             */
            lrn = (ngx_http_limit_req_node_t *) &node->color;
            lrnt = (ngx_http_limit_req_node_t *) &temp->color;

            p = (ngx_memn2cmp(lrn->data, lrnt->data, lrn->len, lrnt->len) < 0)
                ? &temp->left : &temp->right;
        }

        if (*p == sentinel) {
            break;
        }

        temp = *p;
    }

    *p = node;
    node->parent = temp;
    node->left = sentinel;
    node->right = sentinel;
    /* 新加入節(jié)點需要涂成紅色 */
    ngx_rbt_red(node);
}

功能：作為寫事件回調(diào)，再次運行 ngx_http_core_run_phases ，執(zhí)行 HTTP 的 11 個階段處理。

static void
ngx_http_limit_req_delay(ngx_http_request_t *r)
{
    ngx_event_t  *wev;

    ngx_log_debug0(NGX_LOG_DEBUG_HTTP, r->connection->log, 0,
                   "limit_req delay");

    wev = r->connection->write;

    if (!wev->timedout) {

        if (ngx_handle_write_event(wev, 0) != NGX_OK) {
            ngx_http_finalize_request(r, NGX_HTTP_INTERNAL_SERVER_ERROR);
        }

        return;
    }

    wev->timedout = 0;

    if (ngx_handle_read_event(r->connection->read, 0) != NGX_OK) {
        ngx_http_finalize_request(r, NGX_HTTP_INTERNAL_SERVER_ERROR);
        return;
    }

    r->read_event_handler = ngx_http_block_reading;
    r->write_event_handler = ngx_http_core_run_phases;

    ngx_http_core_run_phases(r);
}

Nginx模塊開發(fā)（10）—limit_req模塊分析

Ngx_http_limit_req_module分析

y123456yz/reading-code-of-nginx-1.9.2