Nginx下流量攔截算法
nginx-lua-static-merger
0x00.About
電商平臺營銷時候，經常會碰到的大流量問題，除了做流量分流處理，可能還要做用戶黑白名單、信譽分析，進而根據用戶ip信譽權重做相應的流量攔截、限制流量。
Nginx自身有的請求限制模塊ngx_http_limit_req_module、流量限制模塊ngx_stream_limit_conn_module基于令牌桶算法，可以方便的控制令牌速率，自定義調節限流，就能很好的限制請求數量，然而，nginx.conf問題還是在于無法熱加載。
之前做過的流量限制方案，《Nginx+Lua+Redis訪問頻率控制》，原理是動態的基于ip，實現簡單的漏桶算法，限制訪問頻率。
這里的話，就簡單分析下流量限制算法：漏桶算法、令牌桶算法、滑動窗口等在Nginx+Lua中如何動態綁定uri，動態設定rate實現。
0x01.Leaky Bucket Algorithm
漏 桶算法可以很好地限制容量池的大小，從而防止流量暴增。如果針對uri+ip作為監測的key，就可以實現定向的設定指定ip對指定uri容量大小，超出 的請求做隊列處理（隊列處理要引入消息機制）或者丟棄處理。這也是v2ex對流量攔截的算法，針對uri+ip做流量監測。
Leaky Bucket Algorithm
漏桶算法實現上來說，就是建立一個隊列，在Redis中以uri:ip作為key，隊列上實現FIFO，在請求的前奏實現插入，請求完成后實現刪除。
實現方法是在Nginx發送http數據給用戶后，通過ngx.eof()關閉TCP協議，做其他操作，可以參見請求返回后繼續執行。
下面是部分代碼：
local _M = { _VERSION = "2015.10.19", OK = 1, BUSY = 2, FORBIDDEN = 3 }
function _M.do_list(red, uri, key, size, rate)
local ok, err = red:expire(uri .. ":" .. key, size)
if not ok then
ngx.log(ngx.WARN, "redis set expire error: ", err)
return nil
end
local ok, err = red:rpush(uri .. ":" .. key, ngx.time())
if not ok then
ngx.log(ngx.WARN, "redis rpush error: ", err)
return nil
end
local res, err = red:lrange(uri .. ":" .. key, -(size rate), -1)
if not ok then
ngx.log(ngx.WARN, "redis lrange error: ", err)
return nil
end
if #res < (size rate) or res[#res] - res[1] < size then
return _M.OK
end
return nil
end</pre>
漏桶算法優點很明顯，簡單、高效，能恰當攔截容量外的暴力流量。
但缺點也明顯，無法對流量做頻率處理，比如桶size大小設置范圍內，進行并發攻擊依然能大流量并發效果，桶容量不可以過小，否則容易卡死正常用戶。
0x02.Token Bucket Algorithm
令牌桶算法通過發放令牌，根據令牌的rate頻率做請求頻率限制，容量限制等。
Token Bucket Algorithm
-
系統根據rate(r/s)頻率參數向指定桶中添加token，滿則保持，不添加
</li> -
當用戶請求Nginx時候，分析uri是否需要限制流量，限制則執行令牌桶算法
</li> -
如果桶滿了，則請求通過，消耗令牌一枚；如果請求Redis發現key不存在，則通過size裝滿令牌桶；如果桶內令牌空，則廢棄或等待流量。
</li> </ul>Nginx + Lua 模型中實現必然不能跑一個程序添加令牌了，這個時候需要在分析令牌時候，通過計算時間間隔一次性添加完令牌桶內令牌。具體算法是：rate * time_distance = token_count令牌數量， if token_count > size 桶容量， token_count = size。
實現的存儲結構是用Hash哈希存儲 uri:ip -> token_count，字段通過EXPIRE設定過期時間，達到長時間不訪問清除桶數據效果。
桶的大小、請求的頻率限制用Redis哈希表存儲，不存在則默認不做流量攔截。
用戶黑白名單通過Order SET設定信譽權重，權重越大，代表危險性越大，進而通過百分比改變接口限定rate頻率。
令牌桶算法優勢在于能針對uri做定向rate、size等，不僅限制總請求大小，還限制平均頻率大小。缺點是，還是容易導致誤判等問題，并切用戶的信譽無法完全準確。
參考：
本文出自 夏日小草,轉載請注明出處:http://homeway.me/2015/10/21/nginx-lua-traffic-limit-algorithm