限流算法

学习《Redis深度历险：核心原理和应用实践》一书中，提及了两种限流算法

漏水算法

以下是算法实现

package cn.inkroom.study.redis;

/**
 * 漏水算法
 *
 * @author inkbox
 */
public class FunnelRateLimiter {

    static class Funnel {
        /**
         * 容器的容量
         */
        int capacity;
        /**
         * 流水速率，单位是 个/秒
         * 以毫秒为单位，流水速率会比较小
         */
        float leakingRate;
        /**
         * 容器内的剩余容量
         */
        int leftQuota;

        /**
         * 上次漏水时间，实际代表的是上次请求时间
         */
        long lastLeakTime;

        /**
         * 初始化限流器
         * <p>
         * 假设某个行为需要100秒内最多50次(2秒一次)，最多连续操作15次
         * 那么容器应该是15，流水速率为 50 / 100 = 0.5
         *
         * 容器会在第30秒装满，然后维持两秒一次请求通过
         *
         *
         * @param capacity    容器数量
         * @param leakingRate 流水速率
         */
        public Funnel(int capacity, float leakingRate) {
            this.capacity = capacity;
            this.leakingRate = leakingRate;
            this.leftQuota = capacity;
            this.lastLeakTime = System.currentTimeMillis();
        }


        void makeSpace() {
            long nowTs = System.currentTimeMillis();
            // 距离上次漏水差了多少时间
            long deltaTs = nowTs - lastLeakTime;
            // 计算应该流走多少数据
            int deltaQuota = (int) (deltaTs / 1000 * leakingRate);


            if (deltaQuota < 0) {// 书中注释，间隔时间太长，整数数字过大溢出
                this.leftQuota = capacity;
                this.lastLeakTime = nowTs;
                return;
            }
            // 腾出空间太小，最小单位为1
            if (deltaQuota < 1) {
                return;
            }
            // 修改剩余容量
            this.leftQuota += deltaQuota;
            this.lastLeakTime = nowTs;
            if (this.leftQuota > this.capacity) {
                this.leftQuota = this.capacity;
            }

        }

        boolean watering(int quota) {
            makeSpace();
            if (this.leftQuota >= quota) {
                // 剩余容量减小
                this.leftQuota -= quota;
                return true;
            }
            return false;
        }
    }

    public static void main(String[] args) {
        Funnel funnel = new Funnel(15, 0.5f);
        long now = System.currentTimeMillis();
        new Thread(new Runnable() {
            @Override
            public void run() {
                while (true) {
                    System.out.println("当前：" + ((System.currentTimeMillis() - now) / 1000) + " " + funnel.watering(1));
                    try {
                        Thread.sleep(1000);
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                }


            }
        }).start();
    }

}

滑动窗口算法

书中还提及了另一种简单的滑动窗口限流算法，但是给出的实现有一个小问题，会导致请求永远无法通过

以下是我自己的代码，除了书中的代码，还使用lua脚本替换原本的管道事务的方案

package cn.inkroom.study.redis;

import redis.clients.jedis.Jedis;
import redis.clients.jedis.Pipeline;
import redis.clients.jedis.Response;

/**
 * 简单限流器
 *
 * @author inkbox
 */
public class TimeLimit {

    private Jedis jedis;

    public TimeLimit() {
        jedis = new Jedis("192.168.3.64", 6379);
    }

    /**
     * 操作是否允许被执行。用户userId的action操作在period时间段内，只允许最多执行maxCount次
     *
     * @param userId   用户
     * @param action   操作类型，比如 like:123 可以代表给id为123的文章点赞
     * @param period   从现在往前的时间段，单位秒。例如过去一分钟内，60
     * @param maxCount 指定时间段内的最大次数
     * @return
     */
    public boolean allowExecute(String userId, String action, int period, int maxCount) {

// 以下是书中的实现，里面有一个小问题

        String key = String.format("limit:%s:%s", userId, action);
        long now = System.currentTimeMillis();
        Pipeline pipelined = jedis.pipelined();
        pipelined.multi();
        // 这里有个问题，假设在边界时间里不断重试，将会导致永远无法执行
        // 假设 5秒内最多执行2次，但是每秒都在重试
        // 那么除了最开始的两次，之后不管过了多少时间都无法执行
        // 解决方法就是把 add 放到 zremrange 后面，不计数无效尝试

        pipelined.zadd(key, now, now + "");
        // 移除当前时间-period时间前的所有数据
        pipelined.zremrangeByScore(key, 0, now - period * 1000L);
        Response<Long> zcard = pipelined.zcard(key);
        //设置过期时间
        pipelined.expire(key, (period) + 1);
        pipelined.exec();
        pipelined.close();

        return zcard.get() <= maxCount;
    }

    /**
     * 操作是否允许被执行。用户userId的action操作在period时间段内，只允许最多执行maxCount次
     * <p>
     * 和 {@link TimeLimit#allowExecute(String, String, int, int)} 的区别在于，该方法不会统计不被允许的执行次数
     *
     * @param userId   用户
     * @param action   操作类型，比如 like:123 可以代表给id为123的文章点赞
     * @param period   从现在往前的时间段，单位秒。例如过去一分钟内，60
     * @param maxCount 指定时间段内的最大次数
     * @return
     */
    public boolean allowExecuteIgnoreFail(String userId, String action, int period, int maxCount) {
        String key = String.format("limit:%s:%s", userId, action);
        long now = System.currentTimeMillis();

        Long size = ((Long) jedis.eval(
                "redis.call('zremrangeByScore',KEYS[1],0,ARGV[1]);"
                        + "local size=redis.call('zcard',KEYS[1]);"
                        + "if (size < tonumber(ARGV[2])) then"
                        + "  redis.call('zadd',KEYS[1],tonumber(ARGV[3]),ARGV[3]);"
                        + "end;"
                        + "redis.call('expire',KEYS[1],tonumber(ARGV[4]));"
                        + "return size"
                ,
                1, key, (now - period * 1000L) + "", maxCount + "", now + "", (period + 1) + ""));
        return size < maxCount;
        // 等同以下代码，只是具有原子性
//        jedis.zremrangeByScore(key, 0, now - period * 1000L);
//        Long size = jedis.zcard(key);
//        if (size < maxCount) {
//            //合法操作
//            jedis.zadd(key, now, now + "");
//            return true;
//        }
//        jedis.expire(key, period + 1);
//        return false;

    }

    public static void main(String[] args) {
        TimeLimit timeLimit = new TimeLimit();

        int count = 2;
        for (int i = 0; i < 100; i++) {
            System.out.println(timeLimit.allowExecuteIgnoreFail("userId-", "action", 5, count));
            try {
                Thread.sleep(1000);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }

    }

}

令牌算法

令牌算法和漏水算法大同小异，只是把一些名词做了替换，令牌就相当于剩余容量，另外允许不经过限流处理，直接通过