[轉(zhuǎn)]Nginx限速模塊初探

轉(zhuǎn)自 Nginx限速模塊初探

Nginx限速模塊分為哪幾種？按請求速率限速的burst和nodelay參數(shù)是什么意思？漏桶算法和令牌桶算法究竟有什么不同？本文將帶你一探究竟。我們會通過一些簡單的示例展示Nginx限速模塊是如何工作的，然后結(jié)合代碼講解其背后的算法和原理。

核心算法

在探究Nginx限速模塊之前，我們先來看看網(wǎng)絡(luò)傳輸中常用兩個的流量控制算法：漏桶算法和令牌桶算法。這兩只“桶”到底有什么異同呢？

漏桶算法(leaky bucket)

漏桶算法(leaky bucket)算法思想如圖所示：

漏桶算法

一個形象的解釋是：

  • 水（請求）從上方倒入水桶，從水桶下方流出（被處理）；
  • 來不及流出的水存在水桶中（緩沖），以固定速率流出；
  • 水桶滿后水溢出（丟棄）。

這個算法的核心是：緩存請求、勻速處理、多余的請求直接丟棄。

令牌桶算法(token bucket)

令牌桶算法

算法思想是：

  • 令牌以固定速率產(chǎn)生，并緩存到令牌桶中；
  • 令牌桶放滿時(shí)，多余的令牌被丟棄；
  • 請求要消耗等比例的令牌才能被處理；
  • 令牌不夠時(shí)，請求被緩存。

相比漏桶算法，令牌桶算法不同之處在于它不但有一只“桶”，還有個隊(duì)列，這個桶是用來存放令牌的，隊(duì)列才是用來存放請求的。

從作用上來說，漏桶和令牌桶算法最明顯的區(qū)別就是是否允許突發(fā)流量(burst)的處理，漏桶算法能夠強(qiáng)行限制數(shù)據(jù)的實(shí)時(shí)傳輸（處理）速率，對突發(fā)流量不做額外處理；而令牌桶算法能夠在限制數(shù)據(jù)的平均傳輸速率的同時(shí)允許某種程度的突發(fā)傳輸。

Nginx按請求速率限速模塊使用的是漏桶算法，即能夠強(qiáng)行保證請求的實(shí)時(shí)處理速度不會超過設(shè)置的閾值。

Nginx限速模塊

Nginx主要有兩種限速方式：按連接數(shù)限速(ngx_http_limit_conn_module)、按請求速率限速(ngx_http_limit_req_module)。我們著重講解按請求速率限速。

按連接數(shù)限速

按連接數(shù)限速是指限制單個IP(或者其他的key)同時(shí)發(fā)起的連接數(shù)，超出這個限制后，Nginx將直接拒絕更多的連接。這個模塊的配置比較好理解，詳見ngx_http_limit_conn_module官方文檔。

按請求速率限速

按請求速率限速是指限制單個IP(或者其他的key)發(fā)送請求的速率，超出指定速率后，Nginx將直接拒絕更多的請求。采用leaky bucket算法實(shí)現(xiàn)。為深入了解這個模塊，我們先從實(shí)驗(yàn)現(xiàn)象說起。開始之前我們先簡單介紹一下該模塊的配置方式，以下面的配置為例：

http {
    limit_req_zone $binary_remote_addr zone=mylimit:10m rate=2r/s;
    ...
    server {
        ...
        location /search/ {
            limit_req zone=mylimit burst=4 nodelay;
        }

使用limit_req_zone關(guān)鍵字，我們定義了一個名為mylimit大小為10MB的共享內(nèi)存區(qū)域(zone)，用來存放限速相關(guān)的統(tǒng)計(jì)信息，限速的key值為二進(jìn)制的IP地址（$binary_remote_addr），限速上限(rate)為2r/s；接著我們使用limit_req關(guān)鍵字將上述規(guī)則作用到/search/上。burst和nodelay的作用稍后解釋。

使用上述規(guī)則，對于/search/目錄的訪問，單個IP的訪問速度被限制在了2請求/秒，超過這個限制的訪問將直接被Nginx拒絕。

實(shí)驗(yàn)1——毫秒級統(tǒng)計(jì)

我們有如下配置：

...
limit_req_zone $binary_remote_addr zone=mylimit:10m rate=2r/s;
server { 
    location / { 
        limit_req zone=mylimit;
    }
}
...

上述規(guī)則限制了每個IP訪問的速度為2r/s，并將該規(guī)則作用于跟目錄。如果單個IP在非常短的時(shí)間內(nèi)并發(fā)發(fā)送多個請求，結(jié)果會怎樣呢？

# 單個IP 10ms內(nèi)并發(fā)發(fā)送6個請求
send 6 requests in parallel, time cost: 2 ms
HTTP/1.1 503 Service Temporarily Unavailable
HTTP/1.1 200 OK
HTTP/1.1 503 Service Temporarily Unavailable
HTTP/1.1 503 Service Temporarily Unavailable
HTTP/1.1 503 Service Temporarily Unavailable
HTTP/1.1 503 Service Temporarily Unavailable
end, total time cost: 461 ms

我們使用單個IP在10ms內(nèi)發(fā)并發(fā)送了6個請求，只有1個成功，剩下的5個都被拒絕。我們設(shè)置的速度是2r/s，為什么只有1個成功呢，是不是Nginx限制錯了？當(dāng)然不是，是因?yàn)镹ginx的限流統(tǒng)計(jì)是基于毫秒的，我們設(shè)置的速度是2r/s，轉(zhuǎn)換一下就是500ms內(nèi)單個IP只允許通過1個請求，從501ms開始才允許通過第二個請求。

毫秒級統(tǒng)計(jì)

實(shí)驗(yàn)2——burst允許緩存處理突發(fā)請求

實(shí)驗(yàn)1我們看到，我們短時(shí)間內(nèi)發(fā)送了大量請求，Nginx按照毫秒級精度統(tǒng)計(jì)，超出限制的請求直接拒絕。這在實(shí)際場景中未免過于苛刻，真實(shí)網(wǎng)絡(luò)環(huán)境中請求到來不是勻速的，很可能有請求“突發(fā)”的情況，也就是“一股子一股子”的。Nginx考慮到了這種情況，可以通過burst關(guān)鍵字開啟對突發(fā)請求的緩存處理，而不是直接拒絕。

來看我們的配置：

...
limit_req_zone $binary_remote_addr zone=mylimit:10m rate=2r/s;
server { 
    location / { 
        limit_req zone=mylimit burst=4;
    }
}
...

我們加入了burst=4，意思是每個key(此處是每個IP)最多允許4個突發(fā)請求的到來。如果單個IP在10ms內(nèi)發(fā)送6個請求，結(jié)果會怎樣呢？

# 單個IP 10ms內(nèi)發(fā)送6個請求，設(shè)置burst
send 6 requests in parallel, time cost: 2 ms
HTTP/1.1 200 OK
HTTP/1.1 503 Service Temporarily Unavailable
HTTP/1.1 200 OK
HTTP/1.1 200 OK
HTTP/1.1 200 OK
HTTP/1.1 200 OK
end, total time cost: 2437 ms

相比實(shí)驗(yàn)1成功數(shù)增加了4個，這個我們設(shè)置的burst數(shù)目是一致的。具體處理流程是：1個請求被立即處理，4個請求被放到burst隊(duì)列里，另外一個請求被拒絕。通過burst參數(shù)，我們使得Nginx限流具備了緩存處理突發(fā)流量的能力。

但是請注意：burst的作用是讓多余的請求可以先放到隊(duì)列里，慢慢處理。如果不加nodelay參數(shù)，隊(duì)列里的請求不會立即處理，而是按照rate設(shè)置的速度，以毫秒級精確的速度慢慢處理。

實(shí)驗(yàn)3——nodelay降低排隊(duì)時(shí)間

實(shí)驗(yàn)2中我們看到，通過設(shè)置burst參數(shù)，我們可以允許Nginx緩存處理一定程度的突發(fā)，多余的請求可以先放到隊(duì)列里，慢慢處理，這起到了平滑流量的作用。但是如果隊(duì)列設(shè)置的比較大，請求排隊(duì)的時(shí)間就會比較長，用戶角度看來就是RT變長了，這對用戶很不友好。有什么解決辦法呢？nodelay參數(shù)允許請求在排隊(duì)的時(shí)候就立即被處理，也就是說只要請求能夠進(jìn)入burst隊(duì)列，就會立即被后臺worker處理，請注意，這意味著burst設(shè)置了nodelay時(shí)，系統(tǒng)瞬間的QPS可能會超過rate設(shè)置的閾值。nodelay參數(shù)要跟burst一起使用才有作用。

延續(xù)實(shí)驗(yàn)2的配置，我們加入nodelay選項(xiàng)：

...
limit_req_zone $binary_remote_addr zone=mylimit:10m rate=2r/s;
server { 
    location / { 
        limit_req zone=mylimit burst=4 nodelay;
    }
}
...

單個IP 10ms內(nèi)并發(fā)發(fā)送6個請求，結(jié)果如下：

# 單個IP 10ms內(nèi)發(fā)送6個請求
   實(shí)驗(yàn)3, 設(shè)置burst和nodelay       |  實(shí)驗(yàn)2, 只設(shè)置burst
send 6 requests, time cost: 4 ms |  time cost: 2 ms
HTTP/1.1 200 OK                  |  HTTP/1.1 200 OK
HTTP/1.1 200 OK                  |  HTTP/1.1 503 ...
HTTP/1.1 200 OK                  |  HTTP/1.1 200 OK
HTTP/1.1 200 OK                  |  HTTP/1.1 200 OK
HTTP/1.1 503 ...                 |  HTTP/1.1 200 OK
HTTP/1.1 200 OK                  |  HTTP/1.1 200 OK
total time cost: 465 ms          |  total time cost: 2437 ms

跟實(shí)驗(yàn)2相比，請求成功率沒變化，但是總體耗時(shí)變短了。這怎么解釋呢？實(shí)驗(yàn)2中，有4個請求被放到burst隊(duì)列當(dāng)中，工作進(jìn)程每隔500ms(rate=2r/s)取一個請求進(jìn)行處理，最后一個請求要排隊(duì)2s才會被處理；實(shí)驗(yàn)3中，請求放入隊(duì)列跟實(shí)驗(yàn)2是一樣的，但不同的是，隊(duì)列中的請求同時(shí)具有了被處理的資格，所以實(shí)驗(yàn)3中的5個請求可以說是同時(shí)開始被處理的，花費(fèi)時(shí)間自然變短了。

但是請注意，雖然設(shè)置burst和nodelay能夠降低突發(fā)請求的處理時(shí)間，但是長期來看并不會提高吞吐量的上限，長期吞吐量的上限是由rate決定的，因?yàn)閚odelay只能保證burst的請求被立即處理，但Nginx會限制隊(duì)列元素釋放的速度，就像是限制了令牌桶中令牌產(chǎn)生的速度。

看到這里你可能會問，加入了nodelay參數(shù)之后的限速算法，到底算是哪一個“桶”，是漏桶算法還是令牌桶算法？當(dāng)然還算是漏桶算法?？紤]一種情況，令牌桶算法的token為耗盡時(shí)會怎么做呢？由于它有一個請求隊(duì)列，所以會把接下來的請求緩存下來，緩存多少受限于隊(duì)列大小。但此時(shí)緩存這些請求還有意義嗎？如果server已經(jīng)過載，緩存隊(duì)列越來越長，RT越來越高，即使過了很久請求被處理了，對用戶來說也沒什么價(jià)值了。所以當(dāng)token不夠用時(shí)，最明智的做法就是直接拒絕用戶的請求，這就成了漏桶算法，哈哈~

源碼剖析

經(jīng)過上面的示例，我們隊(duì)請求限速模塊有了一定的認(rèn)識，現(xiàn)在我們深入剖析代碼實(shí)現(xiàn)。按請求速率限流模塊ngx_http_limit_req_module代碼位于src/http/modules/ngx_http_limit_req_module.c，900多好代碼可謂短小精悍。相關(guān)代碼有兩個核心數(shù)據(jù)結(jié)構(gòu)：

  1. 紅黑樹：通過紅黑樹記錄每個節(jié)點(diǎn)（按照聲明時(shí)指定的key）的統(tǒng)計(jì)信息，方便查找；
  2. LRU隊(duì)列：將紅黑樹上的節(jié)點(diǎn)按照最近訪問時(shí)間排序，時(shí)間近的放在隊(duì)列頭部，以便使用LRU隊(duì)列淘汰舊的節(jié)點(diǎn)，避免內(nèi)存溢出。

這兩個關(guān)鍵對象存儲在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節(jié)點(diǎn)。

該模塊的核心邏輯在函數(shù)ngx_http_limit_req_lookup()中，這個函數(shù)主要流程是怎樣呢？對于每一個請求：

  1. 從根節(jié)點(diǎn)開始查找紅黑樹，找到key對應(yīng)的節(jié)點(diǎn)；
  2. 找到后修改該點(diǎn)在LRU隊(duì)列中的位置，表示該點(diǎn)最近被訪問過；
  3. 執(zhí)行漏桶算法；
  4. 沒找到時(shí)根據(jù)LRU淘汰，騰出空間；
  5. 生成并插入新的紅黑樹節(jié)點(diǎn)；
  6. 執(zhí)行下一條限流規(guī)則。

流程很清晰，但是代碼中牽涉到紅黑樹、LRU隊(duì)列等高級數(shù)據(jù)結(jié)構(gòu)，是不是會寫得很復(fù)雜？好在Nginx作者功力深厚，代碼寫得簡潔易懂，哈哈~

// 漏桶算法核心流程
ngx_http_limit_req_lookup(...){
  while (node != sentinel) {
    // search rbtree
    if (hash < node->key) { node = node->left; continue;} // 1\. 從根節(jié)點(diǎn)開始查找紅黑樹
    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\. 修改該點(diǎn)在LRU隊(duì)列中的位置，表示該點(diǎn)最近被訪問過
      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\. 執(zhí)行漏桶算法
      if (excess < 0) 
        excess = 0;
      if ((ngx_uint_t) excess > limit->burst)
        return NGX_BUSY; // 超過了突發(fā)門限，拒絕
      if (account) {// 是否是最后一條規(guī)則
        lr->excess = excess;    
        lr->last = now;    
        return NGX_OK; // 未超過限制，通過
      }
      ...
      return NGX_AGAIN; // 6\. 執(zhí)行下一條限流規(guī)則
    }
    node = (rc < 0) ? node->left : node->right; // 1
  } // while
  ...
  // not found
  ngx_http_limit_req_expire(ctx, 1); // 4\. 根據(jù)LRU淘汰，騰出空間
  node = ngx_slab_alloc_locked(ctx->shpool, size); // 5\. 生成新的紅黑樹節(jié)點(diǎn)
  ngx_rbtree_insert(&ctx->sh->rbtree, node);// 5\. 插入該節(jié)點(diǎn)，重新平衡紅黑樹
  ngx_queue_insert_head(&ctx->sh->queue, &lr->queue);
  if (account) {    
    lr->last = now; 
    lr->count = 0;
    return NGX_OK;
  }
  ...
  return NGX_AGAIN; // 6\. 執(zhí)行下一條限流規(guī)則
}

代碼有三種返回值，它們的意思是：

  • NGX_BUSY 超過了突發(fā)門限，拒絕
  • NGX_OK 未超過限制，通過
  • NGX_AGAIN 未超過限制，但是還有規(guī)則未執(zhí)行，需執(zhí)行下一條限流規(guī)則

上述代碼不難理解，但我們還有幾個問題：

  1. LRU是如何實(shí)現(xiàn)的？
  2. 漏桶算法是如何實(shí)現(xiàn)的？
  3. 每個key相關(guān)的burst隊(duì)列在哪里？

LRU是如何實(shí)現(xiàn)的

LRU算法的實(shí)現(xiàn)很簡單，如果一個節(jié)點(diǎn)被訪問了，那么就把它移到隊(duì)列的頭部，當(dāng)空間不足需要淘汰節(jié)點(diǎn)時(shí)，就選出隊(duì)列尾部的節(jié)點(diǎn)淘汰掉，主要體現(xiàn)在如下代碼中：

ngx_queue_remove(&lr->queue); // 2\. 修改該點(diǎn)在LRU隊(duì)列中的位置，表示該點(diǎn)最近被訪問過
ngx_queue_insert_head(&ctx->sh->queue, &lr->queue);// 2
...
ngx_http_limit_req_expire(ctx, 1); // 4\. 根據(jù)LRU淘汰，騰出空間

漏桶算法是如何實(shí)現(xiàn)的

漏桶算法的實(shí)現(xiàn)也比我們想象的簡單，其核心是這一行公式excess = lr->excess - ctx->rate * ngx_abs(ms) / 1000 + 1000，這樣代碼的意思是：excess表示當(dāng)前key上遺留的請求數(shù)，本次遺留的請求數(shù) = 上次遺留的請求數(shù) - 預(yù)設(shè)速率 X 過去的時(shí)間 + 1。這個1表示當(dāng)前這個請求，由于Nginx內(nèi)部表示將單位縮小了1000倍，所以1個請求要轉(zhuǎn)換成1000。

excess = lr->excess - ctx->rate * ngx_abs(ms) / 1000 + 1000; // 3\. 執(zhí)行漏桶算法
if (excess < 0) 
    excess = 0;
if ((ngx_uint_t) excess > limit->burst)
    return NGX_BUSY; // 超過了突發(fā)門限，拒絕
if (account) { // 是否是最后一條規(guī)則
    lr->excess = excess;    
    lr->last = now;    
    return NGX_OK; // 未超過限制，通過
}
...
return NGX_AGAIN; // 6\. 執(zhí)行下一條限流規(guī)則

上述代碼受限算出當(dāng)前key上遺留的請求數(shù)，如果超過了burst，就直接拒絕；由于Nginx允許多條限速規(guī)則同時(shí)起作用，如果已是最后一條規(guī)則，則允許通過，否則執(zhí)行下一條規(guī)則。

單個key相關(guān)的burst隊(duì)列在哪里

沒有單個key相關(guān)的burst隊(duì)列。上面代碼中我們看到當(dāng)?shù)竭_(dá)最后一條規(guī)則時(shí)，只要excess<limit->burst限速模塊就會返回NGX_OK，并沒有把多余請求放入隊(duì)列的操作，這是因?yàn)镹ginx是基于timer來管理請求的，當(dāng)限速模塊返回NGX_OK時(shí)，調(diào)度函數(shù)會計(jì)算一個延遲處理的時(shí)間，同時(shí)把這個請求放入到共享的timer隊(duì)列中（一棵按等待時(shí)間從小到大排序的紅黑樹）。

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, // 執(zhí)行漏桶算法
                                       (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);// 計(jì)算當(dāng)前請求需要的延遲時(shí)間
    if (!delay) {
        return NGX_DECLINED;// 不需要延遲，交給后續(xù)的handler進(jìn)行處理
    }
    ...
    ngx_add_timer(r->connection->write, delay);// 否則將請求放到定時(shí)器隊(duì)列里
    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()調(diào)用了函數(shù)ngx_http_limit_req_lookup()，并根據(jù)其返回值決定如何操作：或是拒絕，或是交給下一個handler處理，或是將請求放入定期器隊(duì)列。當(dāng)限速規(guī)則都通過后，該hanlder通過調(diào)用函數(shù)ngx_http_limit_req_account()得出當(dāng)前請求需要的延遲時(shí)間，如果不需要延遲，就將請求交給后續(xù)的handler進(jìn)行處理，否則將請求放到定時(shí)器隊(duì)列里。注意這個定時(shí)器隊(duì)列是共享的，并沒有為單獨(dú)的key(比如，每個IP地址)設(shè)置隊(duì)列。關(guān)于handler模塊背景知識的介紹，可參考Tengine團(tuán)隊(duì)撰寫的Nginx開發(fā)從入門到精通

關(guān)于按請求速率限速的原理講解，可參考Rate Limiting with NGINX and NGINX Plus，關(guān)于源碼更詳細(xì)的解析可參考ngx_http_limit_req_module 源碼分析以及y123456yz的Nginx源碼分析的git項(xiàng)目

結(jié)尾

本文主要講解了Nginx按請求速率限速模塊的用法和原理，其中burst和nodelay參數(shù)是容易引起誤解的，雖然可通過burst允許緩存處理突發(fā)請求，結(jié)合nodelay能夠降低突發(fā)請求的處理時(shí)間，但是長期來看他們并不會提高吞吐量的上限，長期吞吐量的上限是由rate決定的。需要特別注意的是，burst設(shè)置了nodelay時(shí)，系統(tǒng)瞬間的QPS可能會超過rate設(shè)置的閾值。

本文只是對Nginx管中窺豹，更多關(guān)于Nginx介紹的文章，可參考Tengine團(tuán)隊(duì)撰寫的Nginx開發(fā)從入門到精通。

標(biāo)簽: Nginx, 限速模塊, 令牌桶算法, 漏桶算法

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容