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, funnel flow limit

3.1 Solutions

Funnel capacity is limited, when the speed of water is less than the speed of water, the funnel will overflow with water, using this principle we can design the limiting code! The remaining space of the funnel represents the number of ongoing actions (requests), and the flow rate of the funnel represents the maximum frequency of actions (requests) allowed to occur by the system, which is usually set after weighing the processing capacity of the installed system.

3.2 Java code implementation

package com.lizba.redis.limit; import java.util.Map; import java.util.concurrent.ConcurrentHashMap; /** * <p> ** @author: Liziba */ public class FunnelRateLimiter {/** private map <String, Funnel> funnels = new ConcurrentHashMap<>(); /** * whether the request is allowed ** @param userId userId * @param actionKey actionKey * @param capacity funnel capacity * @param leakingRate remaining capacity ** @param quota number of requests * @return */ public Boolean isActionAllowed(String userId, String actionKey, int capacity, float leakingRate, int quota) { 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.waterLeaking(quota); } /** * Funnel type */ class Funnel {/** Funnel size */ int capacity; /** Funnel flow rate, allowable flow rate per millisecond (request) */ float leakingRate; /** / int leftCapacity; /** Last leak time */ long leakingTs; public Funnel(int capacity, float leakingRate) { this.capacity = this.leftCapacity = capacity; this.leakingRate = leakingRate; leakingTs = System.currentTimeMillis(); } /** * count space */ void makeSpace() {long nowTs = system.currentTimemillis (); long intervalTs = nowTs - leakingTs; int intervalCapacity = (int) (intervalTs * leakingRate); // int overflow if (intervalCapacity < 0) {this.leftCapacity = this.capacity; this.leakingTs = nowTs; return; If (intervalCapacity < 1) {return; } this.leftCapacity += intervalCapacity; this.leakingTs = nowTs; If (this.leftCapacity > this.capacity) {this.leftCapacity = this.capacity; if (this.leftCapacity > this.capacity) {this.leftCapacity = this.capacity; }} /** * leaking (int quota) {return */ Boolean waterLeaking(int quota) {// leaking (int quota); if (this.leftCapacity >= quota) { leftCapacity -= quota; return true; } return false; }}}Copy the code

Timeunit.seconds.sleep (2); timeunit.seconds.sleep (2); The emulated client will wait some time before requesting it. Set the funnel capacity to 10, allow 0.002 requests per millisecond (2 requests per second), and the number of requests per session to 1;

package com.lizba.redis.limit; import java.util.concurrent.TimeUnit; /** * @Author: Liziba */ public class TestFunnelRateLimit { public static void main(String[] args) throws InterruptedException { FunnelRateLimiter limiter = new FunnelRateLimiter(); for (int i = 1; i <= 20; i++) { if (i == 15) { TimeUnit.SECONDS.sleep(2); } // Set the funnel capacity to 10, allowing 0.002 requests per millisecond (2 requests per second), Boolean SUCCESS = limiter. IsActionAllowed ("Liziba", "commit", 10, 0.002f, 1); System.out.println(" I "+" request "+ (success? "Success" : "failure ")); }}}Copy the code

Test results:

  1. 01-10 requests succeeded. The initial funnel size is 10, so the first 10 requests succeeded
  2. 11-14 requests failed because the funnel was full and the flow rate of the funnel did not release 1 between the four requests
  3. 15-18 requests are successful because the main thread sleeps for 2 seconds when I == 15 and the funnel flows out for 2 seconds10002 = 4, so these four requests are successful
  4. 19 to 20 requests failed, which is the same as 11 to 14 requests failed

3.3 Implementation with Redis

We use a hash structure, and put the Funnel property field into the hash and operate it in the code

package com.lizba.redis.limit; import redis.clients.jedis.Jedis; import java.util.HashMap; import java.util.Map; /** * <p> ** redis hash funnel limit * </p> ** @author: Liziba * @date: 2021/9/7 23:46 */ public class FunnelRateLimiterByHash { private Jedis client; public FunnelRateLimiterByHash(Jedis client) { this.client = client; } /** * Whether the request was successful ** @param userId * @param actionKey * @param capacity * @Param leakingRate * @param quota * @return */ public boolean isActionAllowed(String userId, String actionKey, int capacity, float leakingRate, int quota) { String key = this.key(userId, actionKey); long nowTs = System.currentTimeMillis(); Map<String, String> funnelMap = client.hgetAll(key); if (funnelMap == null || funnelMap.isEmpty()) { return initFunnel(key, nowTs, capacity, quota); } long intervalTs = nowTs - Long.parseLong(funnelMap.get("leakingTs")); int intervalCapacity = (int) (intervalTs * leakingRate); If (intervalCapacity < 0) {intervalCapacity = 0; initFunnel(key, nowTs, capacity, quota); If (intervalCapacity < 1) {intervalCapacity = 0; } int leftCapacity = Integer.parseInt(funnelMap.get("leftCapacity")) + intervalCapacity; if (leftCapacity > capacity) { leftCapacity = capacity; } return initFunnel(key, nowTs, leftCapacity, quota); } /** * save to redis, Initial funnel * * @param key * @param nowTs * @param capacity * @param quota * @return */ private Boolean initFunnel(String) key,long nowTs, int capacity, int quota) { Map<String, String> funnelMap = new HashMap<>(); funnelMap.put("leftCapacity", String.valueOf((capacity > quota) ? (capacity - quota) : 0)); funnelMap.put("leakingTs", String.valueOf(nowTs)); client.hset(key, funnelMap); return capacity >= quota; } /** * @param userId * @param actionKey * @return */ private String key(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; import java.util.concurrent.TimeUnit; /** * @Author: Liziba */ public class TestFunnelRateLimiterByHash { public static void main(String[] args) throws InterruptedException {Jedis Jedis = new Jedis("192.168.211.108", 6379); FunnelRateLimiterByHash limiter = new FunnelRateLimiterByHash(jedis); for (int i = 1; i <= 20; i++) { if (i == 15) { TimeUnit.SECONDS.sleep(2); } Boolean success = limiter. IsActionAllowed ("liziba", "view", 10, 0.002f, 1); System.out.println(" I "+" request "+ (success? "Success" : "failure ")); } jedis.close(); }}Copy the code

Test results:The same structure as the Java code above

4, summarize

The above mentioned two methods of funnel limiting are the same, but both of them can not be used in distributed environment, even in the single-machine environment is not accurate, there are thread safety problems/atomicity problems, so we generally use the flow limiting module redis-cell provided by Redis to limit the flow. Redis-cell provides the atomic cl.throttle throttle instruction, which I’ll leave to the future. I’m going to bed!