An article to talk about the current limiting strategy in Redis

This article will take you to understand the current limiting in Redis, and introduce the simple current limiting strategy and funnel current limiting. I hope it will be helpful to everyone!

1. Simple current limiting

Basic principles

How to organize plans when the system processing capacity is limited External requests put pressure on the system. First, let’s look at some simple current limiting strategies to prevent brute force attacks. For example, if you want to access an IP, you can only access it 10 times every 5 seconds, and if it exceeds the limit, it will be blocked. [Related recommendations: Redis Video Tutorial]

As shown above, a sliding window is generally used to count the number of visits within an interval. Use zset to record the number of IP visits. Each IP is saved through key, and score saves the current timestamp. , value Only use timestamp or UUID to implement

Code implementation

public class RedisLimiterTest {
    private Jedis jedis;

    public RedisLimiterTest(Jedis jedis) {
        this.jedis = jedis;
    }

    /**
     * @param ipAddress Ip地址
     * @param period    特定的时间内，单位秒
     * @param maxCount  最大允许的次数
     * @return
     */
    public boolean isIpLimit(String ipAddress, int period, int maxCount) {
        String key = String.format("ip:%s", ipAddress);
        // 毫秒时间戳
        long currentTimeMillis = System.currentTimeMillis();
        Pipeline pipe = jedis.pipelined();
        // redis事务，保证原子性
        pipe.multi();
        // 存放数据，value 和 score 都使用毫秒时间戳
        pipe.zadd(key, currentTimeMillis, "" + UUID.randomUUID());
        // 移除窗口区间所有的元素
        pipe.zremrangeByScore(key, 0, currentTimeMillis - period * 1000);
        // 获取时间窗口内的行为数量
        Response<Long> count = pipe.zcard(key);
        // 设置 zset 过期时间，避免冷用户持续占用内存，这里宽限1s
        pipe.expire(key, period + 1);
        // 提交事务
        pipe.exec();
        pipe.close();
        // 比较数量是否超标
        return count.get() > maxCount;
    }

    public static void main(String[] args) {
        Jedis jedis = new Jedis("localhost", 6379);
        RedisLimiterTest limiter = new RedisLimiterTest(jedis);
        for (int i = 1; i <= 20; i++) {
            // 验证IP  10秒钟之内只能访问5次
            boolean isLimit = limiter.isIpLimit("222.73.55.22", 10, 5);
            System.out.println("访问第" + i + "次, 结果：" + (isLimit ? "限制访问" : "允许访问"));
        }
    }
}

Execution result

访问第1次, 结果：允许访问
访问第2次, 结果：允许访问
访问第3次, 结果：允许访问
访问第4次, 结果：允许访问
访问第5次, 结果：允许访问
访问第6次, 结果：限制访问
访问第7次, 结果：限制访问
... ...

Disadvantages: It is necessary to record all the behavior records in the time window, which is very large. For example, the scenario of limiting the number of times to no more than 1 million times in 60 seconds is not suitable for such current limiting, because it will consume a lot of storage space.

2. Funnel current limit

Basic principle

##The capacity of the funnel is limited. If it is full, it will be filled. Not going in anymore.
• If you release the spout, the water will flow downward. After a part of it flows away, you can continue to fill it with water.
• If the flow rate of water from the spout is greater than the rate of water filling, then the funnel will never be full.
• If the flow rate of the funnel is less than the filling rate, then once the funnel is full, the filling needs to be paused and wait for the funnel to empty.

Sample code

public class FunnelLimiterTest {

    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 makeSpace() {
            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) {
            makeSpace();
            if (this.leftQuota >= quota) { // 判断剩余空间是否足够
                this.leftQuota -= quota;
                return true;
            }
            return false;
        }
    }

    // 所有的漏斗
    private Map<String, Funnel> funnels = new HashMap<>();

    /**
     * @param capacity    漏斗容量
     * @param leakingRate 漏嘴流水速率 quota/s
     */
    public boolean isIpLimit(String ipAddress, int capacity, float leakingRate) {
        String key = String.format("ip:%s", ipAddress);
        Funnel funnel = funnels.get(key);
        if (funnel == null) {
            funnel = new Funnel(capacity, leakingRate);
            funnels.put(key, funnel);
        }
        return !funnel.watering(1); // 需要1个quota
    }

    public static void main(String[] args) throws Exception{
        FunnelLimiterTest limiter = new FunnelLimiterTest();
        for (int i = 1; i <= 50; i++) {
            // 每1s执行一次
            Thread.sleep(1000);
            // 漏斗容量是2 ，漏嘴流水速率是0.5每秒，
            boolean isLimit = limiter.isIpLimit("222.73.55.22", 2, (float)0.5/1000);
            System.out.println("访问第" + i + "次, 结果：" + (isLimit ? "限制访问" : "允许访问"));
        }
    }
}

Execution results

访问第1次, 结果：允许访问    # 第1次，容量剩余2，执行后1
访问第2次, 结果：允许访问    # 第2次，容量剩余1，执行后0
访问第3次, 结果：允许访问    # 第3次，由于过了2s, 漏斗流水剩余1个空间，所以容量剩余1，执行后0
访问第4次, 结果：限制访问    # 第4次，过了1s, 剩余空间小于1， 容量剩余0
访问第5次, 结果：允许访问    # 第5次，由于过了2s, 漏斗流水剩余1个空间，所以容量剩余1，执行后0
访问第6次, 结果：限制访问    # 以此类推...
访问第7次, 结果：允许访问
访问第8次, 结果：限制访问
访问第9次, 结果：允许访问
访问第10次, 结果：限制访问

We observe
• Funnel Several fields of the object, we found that the contents of the Funnel object can be stored in a hash structure by field, and the fields of the hash structure will be added when filling. After taking it out and performing logical operations, the new value is backfilled into the hash structure to complete a behavior frequency detection.
But there is a problem, we cannot guarantee the atomicity of the entire process. Get the value from the
• hash structure, then operate it in the memory, and then backfill it into the hash structure. These three processes cannot be atomic, which means that appropriate locking control is required. Once the lock is locked, it means there will be a lock failure. If the lock fails, you need to choose to retry or give up.
If you try again, it will cause performance degradation. If you give up, it will affect the user experience. At the same time, the complexity of the code has also increased a lot. This is a really hard choice, how do we solve this problem?
• Redis-Cell The savior is here!

Redis-Cell

Redis 4.0 provides a current-limiting Redis module called

redis-cell. This module also uses the funnel algorithm and provides atomic current limiting instructions. This module has only one instruction cl.throttle, and its parameters and return values ​​are slightly complicated. Next, let us take a look at how to use this instruction.

> cl.throttle key:xxx 15 30 60 1

• 15 : 15 capacity This is the funnel capacity
• 30 60 : 30 operations / 60 seconds This is the water leakage rate
• 1 : need 1 quota (optional parameter, default value is also 1)

> cl.throttle laoqian:reply 15 30 60
1) (integer) 0   # 0 表示允许，1表示拒绝
2) (integer) 15  # 漏斗容量capacity
3) (integer) 14  # 漏斗剩余空间left_quota
4) (integer) -1  # 如果拒绝了，需要多长时间后再试(漏斗有空间了，单位秒)
5) (integer) 2   # 多长时间后，漏斗完全空出来(left_quota==capacity，单位秒)

When executing the current limiting instruction, if it is rejected, it needs to be discarded Or try again.

cl.throttle The instruction is very thoughtful, and even the retry time is calculated for you. Just take the fourth value of the returned result array and perform sleep. If you don’t want to block Threads can also be retried with asynchronous scheduled tasks.

For more programming related knowledge, please visit:

Programming Video! !

The above is the detailed content of An article to talk about the current limiting strategy in Redis. For more information, please follow other related articles on the PHP Chinese website!