Redis限流实现方案-漏斗限流

漏斗限流算是很常用的限流方法之一. 初始容量有限,按照指定速率通过,超出容量部分丢弃.

假定业务场景对用户评论速率的控制

先整一个单机实现的漏斗限流

import java.util.HashMap;
import java.util.Map;

public class FunnelRateLimiter {

    static class Funnel {
        int capacity;   //初始容量
        float leakingRate;  //速率
        int leftQuota;  //剩余容量
        long leakingTs; //是一次漏水时间

        public Funnel(int capacity, float leakingRate) {
            this.capacity = capacity;
            this.leakingRate = leakingRate;
            this.leftQuota = capacity;
            this.leakingTs = System.currentTimeMillis();
        }

        void makeSapce() {
            long nowTs = System.currentTimeMillis();
            long deltaTs = nowTs-leakingTs; //距离上一次漏水过去的时间
            int deltaQuota = (int) (deltaTs * leakingRate); //时间差内产生的容量 
            if(deltaQuota < 0) {    //间隔时间太长，整数数字过大溢出
                this.leftQuota = capacity;
                this.leakingTs = nowTs;
                return;
            }
            if(deltaQuota < 1) {    //产生的空间小于1跳过
                return;
            }
            this.leftQuota += deltaQuota;   //增加剩余空间
            this.leakingTs = nowTs; //记录漏水时间
            if(this.leftQuota > this.capacity) {    //剩余空间不的大于容量
                this.leftQuota = this.capacity;
            }
        }

        boolean watering(int quota) {
            makeSapce();
            if(this.leftQuota >= quota) {
                this.leftQuota -= quota;
                return true;
            }
            return false;
        }
    }

    private Map<String,Funnel> funnels = new HashMap<String,Funnel>();

    public boolean isActionAllowed(String userId, String actionKey, int capacity, float leakingRate) {
        String key = String.format("%s:%s",userId,actionKey);
        Funnel funnel = funnels.get(key);
        if(funnel == null) {
            funnel = new Funnel(capacity,leakingRate);
            funnels.put(key,funnel);
        }
        return funnel.watering(1);
    }

    public static void main(String[] args) {
        FunnelRateLimiter funnelRateLimiter = new FunnelRateLimiter();
        for(int i=0;i<100;i++) {
            boolean f =funnelRateLimiter.isActionAllowed("userId1", "update", 16, 0.5F);
            if(!f) {
                System.out.println("too fast");
            }
        }
    }
}

Funnel对象的makeSapce方法是漏斗算法的核心,每次灌水前都会被调用以触发漏水,给漏斗腾空间.能腾出多少空间取决于过去了多久以及流水的速率.

接下来的问题是分布式的漏斗算法如何实现?

虽说也可以通过Redis的hash结构来存储漏斗的各项指标参数,但是这中间有涉及了计算以及回填过程中的原子性问题,就算加锁进行控制又会出现加锁失败和重试的问题导致性能下降,随之代码复杂度上升...

Redis-Cell

Redis4.0提供了一个限流的Redis模块-->redis-cell.该模块就使用了漏斗算法并且提供了保证原子性的限流指令.该模块只有1条指令cl.throttle

cl.throttle userId1:update 15 30 60 1

• userId1:update --> key
• 15 --> 容量
• 30 --> 速率的分子
• 60 --> 速率的分母
• 1 --> need 1 quota(可选参数,默认值也是1)