Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money.

1, requirements,

Limit a user’s behavior to N times within a specified time T. Let’s say T is 1 second and N is 1000 times.

2. Common design mistakes

The programmer designs a traffic limiting scheme that allows only 1000 accesses per minute, as shown in the figure below. The biggest problem with this design is that requests may be requested 1000 times between 01:59-02:00 s. 1000 requests were made between 02:00s and 02:01s, in this case 2000 requests were made between 01:59s and 02:01s at an interval of 0.02s, obviously this design is wrong.

3. Sliding window algorithm

3.1 Solutions

Within a specified time T, N times are allowed. We can think of this given time, T, as a sliding time window. We use Redis’ zset basic data type score to circle the sliding time window. In the actual operation of Zset, we only need to retain the data within this sliding time window and leave the other data alone.

  • Each user action is stored as a zset, score as a millisecond timestamp, and value as a millisecond timestamp (more memory efficient than UUID).
  • Keep only the behavior records during the sliding window time. If zset is empty, remove zset and no longer occupy memory (save memory).

​

3.2 Pipeline code implementation

The logic of the implementation of the code is to count the number of actions in zSET in the sliding window, and compare it directly with the threshold maxCount to determine whether the current behavior is allowed. There are multiple Redis operations involved, so using pipeline can greatly improve efficiency

package com.lizba.redis.limit; import redis.clients.jedis.Jedis; import redis.clients.jedis.Pipeline; import redis.clients.jedis.Response; /** ** <p> ** @author: Liziba * @date: 2021/9/6 18:11 */ public class SimpleSlidingWindowByZSet { private Jedis jedis; public SimpleSlidingWindowByZSet(Jedis jedis) { this.jedis = jedis; } /** * check whether the action is allowed ** @param userId userId * @param actionKey actionKey * @param period flow limiting period * @param maxCount maximum number of requests (sliding window size) * @return */ public boolean isActionAllowed(String userId, String actionKey, int period, int maxCount) { String key = this.key(userId, actionKey); long ts = System.currentTimeMillis(); Pipeline pipe = jedis.pipelined(); pipe.multi(); pipe.zadd(key, ts, String.valueOf(ts)); ZremrangeByScore (key, 0, ts - (period * 1000)); Response<Long> count = pipe.zcard(key); // Set the expiration time of the behavior. If the data is cold, zset will delete it to save memory space pipe.expire(key, period); pipe.exec(); pipe.close(); return count.get() <= maxCount; } /** * @param userId * @param actionKey * @return */ public String key(String userId, String userId) String actionKey) { return String.format("limit:%s:%s", userId, actionKey); }}Copy the code

Test code:

package com.lizba.redis.limit; import redis.clients.jedis.Jedis; /** * * @Author: Liziba * @Date: 2021/9/6 20:10 */ public class TestSimpleSlidingWindowByZSet { public static void main(String[] args) { Jedis jedis = New Jedis (" 192.168.211.108 ", 6379); SimpleSlidingWindowByZSet slidingWindow = new SimpleSlidingWindowByZSet(jedis); for (int i = 1; i <= 15; i++) { boolean actionAllowed = slidingWindow.isActionAllowed("liziba", "view", 60, 5); System.out.println(" "+ I +") + (actionAllowed? "Success" : "failure ")); } jedis.close(); }}Copy the code

Test effect:As can be seen from the test output data, it has played the effect of limiting the flow. All the request operations after the 11th time are failed, but this error is relatively large compared with the 5 times we allow. CurrentTimeMillis () may be tested in the same milliseconds and value is the same, causing elements in zset to be overwritten! Modify code tests:Sleep for just 1 millisecond during the cycle, and the test results were as expected!

 TimeUnit.MILLISECONDS.sleep(1);
Copy the code

3.3 LuA code implementation

We will be using atomic Lua steps to implement flow limiting more often in our projects, so a version of Lua based on zset is also provided here

package com.lizba.redis.limit; import com.google.common.collect.ImmutableList; import redis.clients.jedis.Jedis; import redis.clients.jedis.Pipeline; import redis.clients.jedis.Response; /** ** <p> ** @author: Liziba * @date: 2021/9/6 18:11 */ public class SimpleSlidingWindowByZSet { private Jedis jedis; public SimpleSlidingWindowByZSet(Jedis jedis) { this.jedis = jedis; } /** * @param userId * @param actionKey * @param period * @param maxCount * @return */ public Boolean isActionAllowedByLua(String userId, String actionKey, int period, int maxCount) { String luaScript = this.buildLuaScript(); String key = key(userId, actionKey); long ts = System.currentTimeMillis(); System.out.println(ts); ImmutableList<String> keys = ImmutableList.of(key); ImmutableList<String> args = ImmutableList.of(String.valueOf(ts),String.valueOf((ts - period * 1000)), String.valueOf(period)); Number count = (Number) jedis.eval(luaScript, keys, args); return count ! = null && count.intValue() <= maxCount; } /** * @param userId * @param actionKey * @return */ private String key(String userId, String actionKey) { return String.format("limit:%s:%s", userId, actionKey); } private String buildLuaScript() {return "redis. Call ('ZADD', KEYS[1], tonumber(ARGV[1]), ARGV[1])" + "\nlocal c" + "\nc = redis.call('ZCARD', KEYS[1])" + "\nredis.call('ZREMRANGEBYSCORE', KEYS[1], 0, tonumber(ARGV[2]))" + "\nredis.call('EXPIRE', KEYS[1], tonumber(ARGV[3]))" + "\nreturn c;" ; }}Copy the code

CurrentTimeMillis () = system.currentTimemillis () = system.currentTimemillis () = system.currentTimemillis () Think more about the problem, technology is actually in the heart!