基于Redis的限流系统的设计

标签: | 发表时间:2017-11-18 09:51 | 作者:
出处:https://mp.weixin.qq.com

本文讲述 基于Redis的限流系统的设计,主要会谈及限流系统中 限流策略这个功能的设计;在实现方面,算法使用的是 令牌桶算法来,访问Redis使用lua脚本。

1、概念

In computer networks,  rate limiting is used to control the rate of traffic sent or received by a network interface controller and is used to prevent DoS attacks

用我的理解翻译一下:限流是对系统的 出入流量进行 控制,防止大流量出入,导致 资源不足,系统不稳定。

限流系统是对资源访问的控制组件,控制主要的两个功能: 限流策略熔断策略,对于熔断策略,不同的系统有不同的熔断策略诉求,有的系统希望直接拒绝、有的系统希望排队等待、有的系统希望服务降级、有的系统会定制自己的熔断策略,很难一一列举,所以本文只针对 限流策略 这个功能做详细的设计。

针对 限流策略 这个功能,限流系统中有两个基础概念:资源和策略。

  • 资源 :或者叫稀缺资源,被流量控制的对象;比如写接口、外部商户接口、大流量下的读接口

  • 策略 :限流策略由限流算法和可调节的参数两部分组成

熔断策略: 超出速率阈值的请求处理策略,是我自己理解的一个叫法,不是业界主流的说法。

2、限流算法

  • 限制瞬时并发数

  • 限制时间窗最大请求数

  • 令牌桶

2.1、限制瞬时并发数

定义:瞬时 并发数,系统同时处理的请求/事务数量

优点:这个算法能够实现控制并发数的效果

缺点:使用场景比较单一,一般用来对入流量进行控制

java伪代码实现

      AtomicInteger atomic =newAtomicInteger(1)        
try{    
   if(atomic.incrementAndGet() > 限流数) {  
       //熔断逻辑   } else {
       //处理逻辑
   }
}finally{    atomic.decrementAndGet(); }

2.2、限制时间窗最大请求数

定义:时间窗最大请求数,指定的时间范围内允许的最大请求数

优点:这个算法能够满足绝大多数的流控需求,通过时间窗最大请求数可以直接换算出最大的QPS(QPS = 请求数/时间窗)

缺点:这种方式可能会出现流量不平滑的情况,时间窗内一小段流量占比特别大

lua代码实现

      --- 资源唯一标识        
localkey = KEYS[1]
--- 时间窗最大并发数
localmax_window_concurrency =tonumber(ARGV[1])  
--- 时间窗
localwindow =tonumber(ARGV[2])  --- 时间窗内当前并发数
localcurr_window_concurrency =tonumber(redis.call('get', key)or0)  
ifcurrent +1> limitthen   returnfalse
else   redis.call("INCRBY", key,1)    
   ifwindow > -1then       redis.call("expire", key,window)    
   end   returntrue
end

2.3、令牌桶

算法描述

  • 假如用户配置的平均发送速率为r,则每隔1/r秒一个令牌被加入到桶中

  • 假设桶中最多可以存放b个令牌。如果令牌到达时令牌桶已经满了,那么这个令牌会被丢弃

  • 当流量以速率v进入,从桶中以速率v取令牌,拿到令牌的流量通过,拿不到令牌流量不通过,执行熔断逻辑

属性

  • 长期来看,符合流量的速率是受到令牌添加速率的影响,被稳定为:r

  • 因为令牌桶有一定的存储量,可以抵挡一定的流量突发情况

    • M是以字节/秒为单位的最大可能传输速率:M>r

    • T max = b/(M-r)    承受最大传输速率的时间

    • B max = T max * M   承受最大传输速率的时间内传输的流量

优点:流量比较平滑,并且可以抵挡一定的流量突发情况

因为我们限流系统的实现就是基于令牌桶这个算法,具体的代码实现参考下文。

3、工程实现

3.1、技术选型

  • mysql:存储限流策略的参数等元数据

  • redis+lua:令牌桶算法实现

说明:因为我们把redis 定位为:缓存、计算媒介,所以元数据都是存在db中

3.2、架构图

3.3、 数据结构

字段 描述
name 令牌桶的唯一标示
apps 能够使用令牌桶的应用列表
max_permits 令牌桶的最大令牌数
rate 向令牌桶中添加令牌的速率
created_by 创建人
updated_by 更新人

限流系统的实现是基于redis的,本可以和应用无关,但是为了做限流元数据配置的统一管理,按应用维度管理和使用,在数据结构中加入了 apps这个字段,出现问题,排查起来也比较方便。

3.4、代码实现

3.4.1、代码实现遇到的问题

参考令牌桶的算法描述,一般思路是在RateLimiter-client放一个重复执行的线程,线程根据配置往令牌桶里添加令牌,这样的实现由如下缺点:

  • 需要为每个令牌桶配置添加一个重复执行的线程

  • 重复的间隔精度不够精确:线程需要每1/r秒向桶里添加一个令牌,当r>1000 时间线程执行的时间间隔根本没办法设置(从后面性能测试的变现来看RateLimiter-client 是可以承担 QPS > 5000 的请求速率)

3.4.2、解决方案

基于上面的缺点,参考了google的guava中RateLimiter中的实现,我们使用了触发式添加令牌的方式。


算法描述

  • 基于上述的令牌桶算法

  • 将添加令牌改成触发式的方式,取令牌的是做添加令牌的动作

  • 在去令牌的时候,通过计算上一次添加令牌和当前的时间差,计算出这段间应该添加的令牌数,然后往桶里添加

    • curr_mill_second = 当前毫秒数

    • last_mill_second = 上一次添加令牌的毫秒数

    • r = 添加令牌的速率

    • reserve_permits = (curr_mill_second-last_mill_second)/1000 * r

  • 添加完令牌之后再执行取令牌逻辑

3.4.3、 lua代码实现

      --- 获取令牌        
--- 返回码
--- 0 没有令牌桶配置
--- -1 表示取令牌失败,也就是桶里没有令牌
--- 1 表示取令牌成功
--- @param key 令牌(资源)的唯一标识
--- @param permits  请求令牌数量
--- @param curr_mill_second 当前毫秒数
--- @param context 使用令牌的应用标识
localfunctionacquire(key, permits, curr_mill_second, context)   localrate_limit_info = redis.pcall("HMGET", key,"last_mill_second","curr_permits","max_permits","rate","apps")    
   locallast_mill_second = rate_limit_info[1]    
   localcurr_permits =tonumber(rate_limit_info[2])    
   localmax_permits =tonumber(rate_limit_info[3])    
   localrate = rate_limit_info[4]    
   localapps = rate_limit_info[5]    
   --- 标识没有配置令牌桶   iftype(apps) =='boolean'orapps ==nilornotcontains(apps, context)then       return0   end   locallocal_curr_permits = max_permits;    
   --- 令牌桶刚刚创建,上一次获取令牌的毫秒数为空   --- 根据和上一次向桶里添加令牌的时间和当前时间差,触发式往桶里添加令牌   --- 并且更新上一次向桶里添加令牌的时间   --- 如果向桶里添加的令牌数不足一个,则不更新上一次向桶里添加令牌的时间   if(type(last_mill_second) ~='boolean'andlast_mill_second ~=falseandlast_mill_second ~=nil)then       localreverse_permits =math.floor(((curr_mill_second - last_mill_second) /1000) * rate)        
       localexpect_curr_permits = reverse_permits + curr_permits;        local_curr_permits =math.min(expect_curr_permits, max_permits);      
        --- 大于0表示不是第一次获取令牌,也没有向桶里添加令牌       if(reverse_permits >0)then           redis.pcall("HSET", key,"last_mill_second", curr_mill_second)      
     end   else       redis.pcall("HSET", key,"last_mill_second", curr_mill_second)  
   end   localresult = -1   if(local_curr_permits - permits >=0)then       result =1       redis.pcall("HSET", key,"curr_permits", local_curr_permits - permits)    
    else       redis.pcall("HSET", key,"curr_permits", local_curr_permits)    
   end   returnresult
end

关于限流系统的所有实现细节,我都已经放到github上,gitbub地址:https://github.com/wukq/rate-limiter,有兴趣的同学可以前往查看,由于笔者经验与知识有限,代码中如有错误或偏颇,欢迎探讨和指正。

3.4.4、管理界面

前面的设计中,限流的配置是和应用关联的,为了更够更好的管理配置,需要一个统一的管理页面去对配置进行管控:

  • 按应用对限流配置进行管理

  • 不同的人分配不同的权限;相关人员有查看配置的权限,负责人有修改和删除配置的权限

3.5、性能测试

配置:aws-elasticcache-redis 2核4g

因为Ratelimiter-client的功能比较简单,基本上是redis的性能打个折扣。

  • 单线程取令牌:Ratelimiter-client的 QPS = 250/s

  • 10个线程取令牌:Ratelimiter-client的 QPS = 2000/s

  • 100个线程取令牌:Ratelimiter-client的 QPS = 5000/s

4、总结

限流系统从设计到实现都比较简单,但是确实很实用,用四个字来形容就是: 短小强悍,其中比较重要的是结合公司的权限体系和系统结构,设计出符合自己公司规范的限流系统。

不足

  • redis 我们用的是单点redis,只做了主从,没有使用redis高可用集群(可能使用redis高可用集群,会带来新的问题)

  • 限流系统目前只做了应用层面的实现,没有做 接口网关上的实现

  • 熔断策略需要自己定制,如果实现的好一点,可以给一些常用的熔断策略模板




参考书籍:

1.《 Redis 设计与实现》
2.《 Lua编程指南》

参考文章:

1. redis官网

2. lua编码规范

3. 聊聊高并发系统之限流特技

4. guava Ratelimiter 实现

5. Token_bucket wiki 词条


    相关 [redis 系统 设计] 推荐:

    基于Redis的限流系统的设计

    - -
    基于Redis的限流系统的设计,主要会谈及限流系统中. 限流策略这个功能的设计;在实现方面,算法使用的是. 令牌桶算法来,访问Redis使用lua脚本. rate limiting is used to control the rate of traffic sent or received by a network interface controller and is used to prevent DoS attacks.

    Redis Cluster(Redis 3.X)设计要点

    - - CSDN博客架构设计推荐文章
    Redis 3.0.0 RC1版本10.9号发布, Release Note. 这个版本支持 Redis Cluster,相信很多同学期待已久,不过这个版本只是RC版本,要应用到生产环境,还得等等. Redis Cluster设计要点:. Redis Cluster采用无中心结构,每个节点都保存数据和整个集群的状态.

    Redis系统性介绍

    - gnawux - NoSQLFan
    虽然Redis已经很火了,相信还是有很多同学对Redis只是有所听闻或者了解并不全面,下面是一个比较系统的Redis介绍,对Redis的特性及各种数据类型及操作进行了介绍. 是一个很不错的Redis入门教程. REmote DIctionary Server(Redis) 是一个由Salvatore Sanfilippo写的key-value存储系统.

    用 Redis 轻松实现秒杀系统

    - - 博客 - 伯乐在线
    曾经被问过好多次怎样实现秒杀系统的问题. 昨天又在CSDN架构师微信群被问到了. 因此这里把我设想的实现秒杀系统的价格设计分享出来. 秒杀系统,是典型的短时大量突发访问类问题. 对这类问题,有三种优化性能的思路:. 写入内存而不是写入硬盘、异步处理而不是同步处理、分布式处理. 用上这三招,不论秒杀时负载多大,都能轻松应对.

    基于Redis构建系统的经验和教训

    - - idea's blog
    Redis 是一个非常快速和强大的 Key-Value 存储(持久化)系统, 相对于一般的 NoSQL 存储系统, 它最大的特点是支持丰富的数据结构. 特别是其 zset(sorted set)数据结构, 堪称表达能力最强的结构之一(其它强大的数据结构如 sorted hashmap), 可以直接地表达业务逻辑..

    [转][转]Redis消息通知系统的实现

    - - heiyeluren的Blog
    链接:http://huoding.com/2012/02/29/146. 最近忙着用Redis实现一个消息通知系统,今天大概总结了一下技术细节,其中演示代码如果没有特殊说明,使用的都是 PhpRedis扩展来实现的. 比如要推送一条全局消息,如果真的给所有用户都推送一遍的话,那么会占用很大的内存,实际上不管粘性有多高的产品,活跃用户同全部用户比起来,都会小很多,所以如果只处理登录用户的话,那么至少在内存消耗上是相当划算的,至于未登录用户,可以推迟到用户下次登录时再处理,如果用户一直不登录,就一了百了了.

    浅谈Redis数据库的键值设计

    - 圣斌 - NoSQLFan
    NoSQL带给我们的东西很多,高性能,水平扩展性,还有不一样的思维方式. 本文来自@hoterran的个人博客运维与开发,作者列举了几种常用的应用场景,分别描述了其关系型数据库和Redis下的不同存储设计方法. 丰富的数据结构使得redis的设计非常的有趣. 不像关系型数据库那样,DEV和DBA需要深度沟通,review每行sql语句,也不像memcached那样,不需要DBA的参与.

    评价系统设计篇

    - - 互联网 - ITeye博客
    评论系统大家都见得非常多了,大到京东、淘宝、亚马逊,小到个人网站、博客都有评论系统,小型网站采用传统PHP+Mysql方式就能很快将系统搭建起来,同时采用单库单表方式就能轻松解决数据存储、数据查询等问题,但是对于上述中大型网站而言,已经远远不能支撑系统正常运行了. 接下来将从系统架构、数据存储、高性能服务等方面来揭示京东的评价系统在面对海量数据、海量请求的情况是如何处理的.

    Redis 负载监控——redis-monitor

    - - ITeye资讯频道
    redis-monitor是一个Web可视化的 redis 监控程序. 使用 Flask 来开发的,代码结构非常简单,适合移植到公司内网使用. redis 服务器信息,包括 redis 版本、上线时间、 os 系统信息等等. 实时的消息处理信息,例如处理 command 数量、连接总数量等. 内存占用、 cpu 消耗实时动态图表.

    Redis 起步

    - - 博客园_首页
    Rdis和JQuery一样是纯粹为应用而产生的,这里记录的是在CentOS 5.7上学习入门文章:. Redis是一个key-value存储系统. 和Memcached类似,但是解决了断电后数据完全丢失的情况,而且她支持更多无化的value类型,除了和string外,还支持lists(链表)、sets(集合)和zsets(有序集合)几种数据类型.