One, simple current limiting

The basic principle of

How to prevent unplanned requests from pressuring the system when its capacity is limited. First let’s take a look at some simple traffic limiting strategies to prevent violent attacks. For example, to access IP, no 5s can only access 10 times, more than the interception.

As shown in the figure above, a sliding window is generally used to count the number of visits within a time interval. Zset is used to record The Times of IP access, each IP is saved by key, score saves the current timestamp, and value is only realized by timestamp or UUID

Code implementation

public class RedisLimiterTest { private Jedis jedis; public RedisLimiterTest(Jedis jedis) { this.jedis = jedis; } /** * @param ipAddress Ip address * @param period A specified period of time, @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 transaction to ensure atomicity pipe.multi(); Pipe. zadd(key, currentTimeMillis, "" + uid.randomuuid ()); ZremrangeByScore (key, 0, currentTimemillis-period * 1000); // Remove all elements in pipe.zremrangeByScore(key, 0, currentTimemillis-period * 1000); Response<Long> count = pipe.zcard(key); Expire (key, period + 1); // Set the expiration time of zset to prevent cold users from using memory. // Commit transaction 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++) {// verify that IP can only be accessed 5 times within 10 seconds Boolean isLimit = limiter.isiplimit ("222.73.55.22", 10, 5); System.out.println(" access "+ I +", result: "(isLimit? "Restricted access" : "allowed access ")); }}}Copy the code

The execution result

Access 1, Result: allowed access 2, Result: Allowed access 3, Result: Allowed access 4, Result: Allowed access 5, Result: Allowed access 6, Result: Restricted access 7, Result: Restricted access... .Copy the code

Disadvantages: It is necessary to record all behavior records in the time window, and the amount is very large. For example, it is not suitable for such traffic limiting, because it will consume a lot of storage space.

Two, funnel flow limitation

The basic principle of

  • The capacity of a funnel is limited. If you plug the leak and keep pouring water into it, it will fill up until it can’t fit any more.
  • If you let the spout go, the water will flow down, and after some of it has gone, it can be filled again.
  • If the rate of leaking water is greater than the rate of filling, the funnel will never be filled.
  • If the rate of leakage flow is less than the rate of filling, then once the funnel is full, the filling needs to be suspended and wait for the funnel to empty.

The sample code

public class FunnelLimiterTest { static class Funnel { int capacity; // Funnel size float leakingRate; Int leftQuota; // Funnel remaining space Long leakingTs; // Time of the last leak 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; // How long has it been since the last leak int deltaQuota = (int) (deltaTs * leakingRate); This. leftQuota = capacity; if (deltaQuota < 0) {this.leftQuota = capacity; this.leakingTs = nowTs; return; } if (deltaQuota < 1) {if (deltaQuota < 1) {return; } this.leftQuota += deltaQuota; This. LeakingTs = nowTs; // leakingTs = leakingTs; 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; } // All Funnel private Map<String, Funnel> funnels = new HashMap<>(); /** * @param leakingRate /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); Public static void main(String[] args) throws Exception{FunnelLimiterTest limiter = new FunnelLimiterTest(); for (int i = 1; i <= 50; Thread.sleep(1000); thread.sleep (1000); Boolean isLimit = limiter. IsIpLimit ("222.73.55.22", 2, (float)0.5/1000); System.out.println(" access "+ I +", result: "(isLimit? "Restricted access" : "allowed access ")); }}}Copy the code

The execution result

If you want to access the database for the first time, you can access the database for the second time. If you want to access the database for the first time, you can access the database for the third time. Allow access # 3, because after 2s, the funnel flow has 1 space left, so the capacity remaining 1, perform 0 access 4, result: Allow access # 5, because after 2s, the funnel flow has 1 space left, so the capacity left 1, after 0 access 6th, result: restrict access # and so on... Access 7th, result: allowed access 8th, result: restricted access 9th, Result: allowed access 10th, result: restricted accessCopy the code
  • We observeFunnelObject, we found that we could setFunnelThe contents of the object are stored by field into onehashStructure, when filling water willhashAfter a logical operation, the new value is backfilled tohashThe structure completes a behavior frequency detection.
  • But there’s a problem, we can’t guarantee the atomicity of the whole process. fromhashStructure, and then it evaluates in memory, and then it backfillshashStructure, these three processes cannot be atomized, meaning that appropriate locking control is required. Once the lock is added, it means that the lock will fail to be added. If the lock fails, you need to retry or give up.
  • If you try again, performance degrades. If you give it up, it will affect the user experience. At the same time, the complexity of the code increases significantly. It’s really a tough choice. How do we solve this problem?Redis-CellHelp is here!

Redis-Cell

Redis 4.0 provides a stream limiting Redis module called Redis – Cell. The module also uses the funnel algorithm and provides the atom’s current-limiting instructions. There is only one instruction cl.throttle in this module, and its parameters and return values are slightly complex. Let’s see how to use this instruction in detail.

> cl.throttle key:xxx 15 30 60 1
Copy the code
  • 15This is the capacity of the funnel
  • 30 to 60: 30 operations / 60 seconds This is the leakage rate
  • 1: need 1 quota (optional, default is also 1)
> throttle laoqian:reply 15 30 60 1) (integer) 0 # 0 3) (integer) 14 # Left_quota 4) (integer) -1 # If rejected, how long will it take to try again 5) (integer) 2 # How long before the funnel is completely empty (left_quota==capacity, in seconds)Copy the code

If the flow limiting instruction is rejected, it needs to be discarded or retried. The cl.throttle command is throttle wise, and you can sleep the fourth value of the result array. If you don’t want to block the thread, you can asynchronously schedule the task to retry.

Reference source

Redis Deep Adventure Core Principle and Application practice _ Qian Wenpin