Nginx下流量拦截算法

nginx-lua-static-merger

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

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

漏桶算法优点很明显,简单、高效,能恰当拦截容量外的暴力流量。

但缺点也明显,无法对流量做频率处理,比如桶size大小设置范围内,进行并发攻击依然能大流量并发效果,桶容量不可以过小,否则容易卡死正常用户。

0x02.Token Bucket Algorithm

令牌桶算法通过发放令牌,根据令牌的rate频率做请求频率限制,容量限制等。

Token Bucket Algorithm

Token Bucket Algorithm

  • 系统根据rate(r/s)频率参数向指定桶中添加token,满则保持,不添加

  • 当用户请求Nginx时候,分析uri是否需要限制流量,限制则执行令牌桶算法

  • 如果桶满了,则请求通过,消耗令牌一枚;如果请求Redis发现key不存在,则通过size装满令牌桶;如果桶内令牌空,则废弃或等待流量。

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等,不仅限制总请求大小,还限制平均频率大小。缺点是,还是容易导致误判等问题,并切用户的信誉无法完全准确。

参考:

1.Token Bucket Algorithm

2.Token Bucket Algorithm

3.电商课题I:集群环境下业务限流


个人资料
Tony
等级:6
文章:20篇
访问:2.5w
排名: 19
上一篇: 最全最强解析:支付宝钱包系统架构内部剖析(架构图)
下一篇:Nginx重定向Rewrite分析
标签: 令牌、ngx、uri、rate、token、面试题
隐藏