高并发系统支撑---限流算法

高并发系统支撑方式

在维护高并发系统时，我们通常通过：缓存、降级和限流来进行支撑。

• 缓存的目的是提升系统访问速度和增大系统能处理的容量，和保护后端服务免受高流量的冲击；
• 降级是当服务出问题或者影响到核心流程的性能则需要暂时屏蔽掉，待高峰或者问题解决后再打开；
• 限流的目的是通过对并发/请求进行限速或者一个时间段内的的请求进行限速来保护系统，一旦达到限制速率则可以拒绝服务（定向到错误页或告知资源没有了）、排队、等待或降级。

有些场景并不能用缓存和降级来解决，比如写服务、频繁的复杂查询，因此需有一种手段来限制这些场景的并发/请求量，即限流。

一般高并发系统常见的限流有：限制总并发数（比如数据库连接池、线程池）、限制瞬时并发数（如nginx的limit_conn模块，用来限制瞬时并发连接数）、限制时间窗口内的平均速率（nginx的limit_req模块，限制每秒的平均速率）；其他还有如限制远程接口调用速率、限制MQ的消费速率。另外还可以根据网络连接数、网络流量、CPU或内存负载等来限流。

在实际应用时，不管是在七成模型的哪个层次进行限流，一些限流算法实现是一样的只是描述不一样；具体使用哪种限流技术还是要根据实际场景来选择，不要一味去找最佳模式，能解决问题就好。

在实际工作中对于限流一直局限于使用阶段和轻度的修改，常直接使用开源应用，服务来实现，没有深究过其中的实现，这次自己好好学习了下，同时也分享给大家。限流的技术大致从限流算法、应用级限流、分布式限流、接入层限流来实现，本次先讲讲底层的限流算法。

限流算法

常见的限流算法有：令牌桶、漏桶，计数器。

1.令牌桶算法

令牌桶算法比漏桶算法稍显复杂。首先，我们有一个固定容量的桶，桶里存放着令牌（token）。桶一开始是空的，token以一个固定的速率r往桶里填充，直到达到桶的容量，多余的令牌将会被丢弃。每当一个请求过来时，就会尝试从桶里移除一个令牌，如果没有令牌的话，请求无法通过。

令牌桶算法的描述如下：

• 假设限制2r/s，则按照500毫秒的固定速率往桶中添加令牌；
• 桶中最多存放b个令牌，当桶满时，新添加的令牌被丢弃或拒绝；
• 当一个n个字节大小的数据包到达，将从桶中删除n个令牌，接着数据包被发送到网络上；
• 如果桶中的令牌不足n个，则不会删除令牌，且该数据包将被限流（要么丢弃，要么缓冲区等待）。

2.漏桶算法

首先，我们有一个固定容量的桶，有水流进来，也有水流出去。对于流进来的水来说，我们无法预计一共有多少水会流进来，也无法预计水流的速度。但是对于流出去的水来说，这个桶可以固定水流出的速率。而且，当桶满了之后，多余的水将会溢出。

漏桶算法的描述如下：

• 一个固定容量的漏桶，按照常量固定速率流出水滴；
• 如果桶是空的，则不需流出水滴；
• 可以以任意速率流入水滴到漏桶；
• 如果流入水滴超出了桶的容量，则流入的水滴溢出了（被丢弃），而漏桶容量是不变的。

3.计数器算法

计数器法是限流算法里最简单也是最容易实现的一种算法。比如我们规定，对于A接口来说，我们1分钟的访问次数不能超过100个。那么我们可以这么做：在一开始的时候，我们可以设置一个计数器counter，每当一个请求过来的时候，counter就加1，如果counter的值大于100并且该请求与第一个请求的间隔时间还在1分钟之内，那么说明请求数过多；如果该请求与第一个请求的间隔时间大于1分钟，且counter的值还在限流范围内，那么就重置counter，具体算法的示意图如下：

这个算法虽然简单，但是有一个十分致命的问题，那就是临界问题：假设有一个恶意用户，他在0:59时，瞬间发送了100个请求，并且1:00又瞬间发送了100个请求，那么其实这个用户在1秒里面，瞬间发送了200个请求。我们刚才规定的是1分钟最多100个请求，也就是每秒钟最多1.7个请求，用户通过在时间窗口的重置节点处突发请求，可以瞬间超过我们的速率限制。用户有可能通过算法的这个漏洞，瞬间压垮我们的应用。

这个问题采用滑动窗口算法即可解决，大学学过计算机网络基础的应该都还记得tcp网络的滑动窗口，算法是一样的，本质就是提高计数周期的粒度，这里就不作细讲了，可以自己去查阅相关资料。

实现demo

redis+lua

local key = KEYS[1] --限流KEY（一秒一个）
local limit = tonumber(ARGV[1])        --限流大小
local current = tonumber(redis.call('get', key) or "0")
if current + 1 > limit then --如果超出限流大小
 return 0else  --请求数+1，并设置2秒过期
redis.call("INCRBY", key,"1")
redis.call("expire", key,"2")
  return 1
end

nginx+lua

注意加锁

local locks = require "resty.lock"
local function acquire()
   local lock =locks:new("locks")
    local elapsed, err =lock:lock("limit_key") --互斥锁
   local limit_counter =ngx.shared.limit_counter --计数器   local key = "ip:" ..os.time()
    local limit = 5 --限流大小
   local current =limit_counter:get(key)
    
    if current ~= nil and current + 1> limit then --如果超出限流大小
      lock:unlock()
       return 0
   end
   if current == nil then
      limit_counter:set(key, 1, 1) --第一次需要设置过期时间，设置key的值为1，过期时间为1秒
   else
       limit_counter:incr(key, 1) --第二次开始加1即可
   end
   lock:unlock()
    return 1
end
ngx.print(acquire())

今天就写到这，之后会写一个openresty+redis+lua的限流实践。