专栏首页极客运维高并发系统支撑---限流算法

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

高并发系统支撑方式

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

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

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

一般高并发系统常见的限流有:限制总并发数(比如数据库连接池、线程池)、限制瞬时并发数(如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的限流实践。

本文分享自微信公众号 - 极客运维(hypernetworker)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2017-07-07

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Node.js 中实践基于 Redis 的分布式锁实现

    在一些分布式环境下、多线程并发编程中,如果对同一资源进行读写操作,避免不了的一个就是资源竞争问题,通过引入分布式锁这一概念,可以解决数据一致性问题。

    五月君
  • 测试开发进阶(三十九)

    zx钟
  • Activiti开发案例之会签多实例任务

    Activiti 中有互斥网关和并行网关,但是在实际项目开发中,经常会出现一些看起来离奇的需求,比如任务分配给多人审批,只要指定数量的人审批通过就可以进入下一个...

    小柒2012
  • Nginx开启Google Brotli压缩

    Brotli是Google推出的开源压缩算法,通过变种的LZ77算法、Huffman编码以及二阶文本建模等方式进行数据压缩,与其他压缩算法相比,它有着更高的压缩...

    行 者
  • UCloud 云服务内容鉴黄 Java 版本实现

    最近不少小伙伴反映上传小黄图偶尔性的异常,并且不能上传动态图片,很是苦恼!无她,鉴黄API还没有这么智能,毕竟是自己训练的,不是那么专业!为了更好的服务广大网友...

    小柒2012
  • 循环、递归与魔术(五)——再谈递归的魔术逻辑与欣赏

    在前面的系列文章里,我们谈到了循环和递归的数理逻辑和魔术艺术逻辑,今天我们就递归的魔术逻辑,通过一个优雅的魔术,来最后对整个系列做一个收尾。

    magic2728
  • EFCore批量操作,你真的清楚吗

    EntityFramework Core有许多新的特性,其中一个重要特性便是批量操作。批量操作意味着不需要为每次Insert/Update/Delete操作发送...

    心莱科技雪雁
  • 100天搞定机器学习|Day57 Adaboost知识手册(理论篇)

    Adaboost模型内容较多,我将分为理论篇和实践篇分别介绍,本文为理论篇,主要介绍Boostting算法、Adaboost基本概念,算法原理、公式推导、Skl...

    统计学家
  • 使用Simulink快速搭建视频处理硬件加速仿真平台

    前言:这一讲我们使用Simulink来快速搭建图像/视频处理硬件加速平台。以简单的RGB2GREY算法为例。我们主要使用的Toolbox为HDL Coder和V...

    FPGA开源工作室
  • 从SpringBoot构建十万博文聊聊限流特技

    在开发十万博客系统的的过程中,前面主要分享了爬虫、缓存穿透以及文章阅读量计数等等。爬虫的目的就是解决十万+问题;缓存穿透是为了保护后端数据库查询服务;计数服务解...

    小柒2012

扫码关注云+社区

领取腾讯云代金券