Redis高并发限流策略之漏斗限流算法

原创
2020/05/30 16:25
阅读数 841

在双11活动当天凌晨,打折活动开始前多少名客户下单可以半折甚至是免单优惠,客户当然不会放过这个一年一次的机会,疯狂开始。这时候我们程序员小哥哥就苦了,稍一个不注意,服务器驾崩了,次日头条见。那么为了防止在当天凌晨压死服务器的并发,我们想到了一个很好的策略,一分钟搞不定的事情,我们可以两分钟搞定,至少保证我们的服务器不会瘫痪,就是说,假如我们的服务器并发量是1w左右,那么我们可以限制在9000的并发量,超过这个预警我们就严格限制请求访问量不能做越过这个警戒线,做到削峰或者说是平滑这个爆发点。

很快我们程序员小哥哥想到了两个绝佳算法令牌桶和漏斗算法,关于这两种算法,我们接下来就简单介绍下。

令牌桶算法:是网络流量整形速率限制中最常使用的一种算法。典型情况下,令牌桶算法用来控制发送到网络上的数据的数目,并允许突发数据的发送。

      a. 按特定的速率向令牌桶投放令牌

    b. 根据预设的匹配规则先对报文进行分类,不符合匹配规则的报文不需要经过令牌桶的处理,直接发送;

    c. 符合匹配规则的报文,则需要令牌桶进行处理。当桶中有足够的令牌则报文可以被继续发送下去,同时令牌桶中的令牌 量按报文的长度做相应的减少;

    d. 当令牌桶中的令牌不足时,报文将不能被发送,只有等到桶中生成了新的令牌,报文才可以发送。这就可以限制报文的流量只能是小于等于令牌生成的速度,达到限制流量的目的。

漏斗算法:主要目的是控制数据注入到网络的速率,平滑网络上的突发流量。漏斗算法提供了一种机制,通过它,突发流量可以被整形以便为网络提供一个稳定的流量

令牌桶和漏斗对比:

两者主要区别在于漏斗算法能够强行限制数据的传输速率,而令牌桶算法在能够限制数据的平均传输速率外,还允许某种程度的突发传输。在令牌桶算法中,只要令牌桶中存在令牌,那么就允许突发地传输数据直到达到用户配置的门限,所以它适合于具有突发特性的流量。

Redis Cell的使用

简单的介绍这两种限流算法后,我们今天要来使用的是redis4.0提供的漏斗算法Redis Cell,redis只提供了一个命令cl.throttle

cl.throttle user 15 30 60 1              ▲   ▲  ▲  ▲ ▲              |   |  |  | └─── apply 1 token  #每次申请一个token,默认为1              |   |  └──┴───── 30 tokens / 60 seconds  #速率,60秒生成30个token              |   └─────────── 15 max_burst     #默认最大初始值              └─────────────── key "user"    #key值
> cl.throttle user 15 30 60 11) (integer) 0    # 0 表示允许,1表示拒绝2) (integer) 15   # 漏斗总容量3) (integer) 14   # 漏斗剩余空间4) (integer) -1   # 如果拒绝了,需要多长时间后再试(漏斗有空间了,单位秒)5) (integer) 2    # 表示多久后令牌桶中的令牌会存满(单位秒)

在执行限流指令时,如果被拒绝了,就需要丢弃或重试。cl.throttle指令考虑的非常周到,连重试时间都帮你算好了,直接取返回结果数组的第四个值进行sleep即可,如果不想阻塞线程,也可以异步定时任务来重试。

实现漏斗算法

这里我们简单的模拟一下漏斗算法

private static class Funnel {        private int capacity;        private float leakingRate;        private int leftQuota;        private long leakingTs;
public Funnel(int capacity, int count, int perSecond) { this.capacity = capacity; // 因为计算使用毫秒为单位的 perSecond *= 1000; this.leakingRate = (float) count / perSecond; }
/** * 根据上次水流动的时间,腾出已流出的空间 */ private void makeSpace() { long now = System.currentTimeMillis(); long time = now - leakingTs; int leaked = (int) (time * leakingRate); if (leaked < 1) { return; } leftQuota += leaked; // 如果剩余大于容量,则剩余等于容量 if (leftQuota > capacity) { leftQuota = capacity; } leakingTs = now; }
/**         * 漏斗漏水 * @param quota 流量 * @return 是否有足够的水可以流出(是否允许访问) */ public boolean watering(int quota) { makeSpace(); int left = leftQuota - quota; if (left >= 0) { leftQuota = left; return true; } return false; } }

漏斗限速方法:

public class FunnelRateLimiter {    private Map<String, Funnel> funnelMap = new ConcurrentHashMap<>();    /**     * 根据给定的漏斗参数检查是否允许访问     * @param username   用户名     * @param action     操作     * @param capacity   漏斗容量     * @param allowQuota 每单个单位时间允许的流量     * @param perSecond  单位时间(秒)     * @return 是否允许访问     */    public boolean isActionAllowed(String username, String action, int capacity, int allowQuota, int perSecond) {        String key = "funnel:" + action + ":" + username;        if (!funnelMap.containsKey(key)) {            funnelMap.put(key, new Funnel(capacity, allowQuota, perSecond));        }        Funnel funnel = funnelMap.get(key);        return funnel.watering(1);    }}

测试:

    public static void main(String[] args) throws InterruptedException {        FunnelRateLimiter limiter = new FunnelRateLimiter();        int testAccessCount = 30;        int capacity = 5;        int allowQuota = 5;        int perSecond = 30;        int allowCount = 0;        int denyCount = 0;        for (int i = 0; i < testAccessCount; i++) {            boolean isAllow = limiter.isActionAllowed("user""doSomething"5530);            if (isAllow) {                allowCount++;            } else {                denyCount++;            }            System.out.println("访问权限:" + isAllow);            Thread.sleep(1000);        }        System.out.println("报告:");        System.out.println("漏斗容量:" + capacity);        System.out.println("漏斗流动速率:" + allowQuota + "次/" + perSecond + "秒");        System.out.println("测试次数=" + testAccessCount);        System.out.println("允许次数=" + allowCount);        System.out.println("拒绝次数=" + denyCount);    }


一名正在抢救的coder

笔名:mangolove

CSDN地址:https://blog.csdn.net/mango_love

GitHub地址:https://github.com/mangoloveYu


本文分享自微信公众号 - 架构技术栈(gh_f036ff0c58eb)。
如有侵权,请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部