Current limiting

When the processing capacity of the system is limited, how to prevent unplanned requests from continuing to pressure the system is a problem that needs to be paid attention to. In this case, the flow limiting algorithm is needed to avoid excessive traffic from affecting the stable operation of the system.

In addition to traffic control, traffic limiting also aims to control user behavior and avoid spam requests. For example, on forums, users’ posts, replies, likes and other behaviors should be strictly controlled. Generally, users’ requests will receive a certain number of times within a short period of time, and if they exceed this limit, they will be rejected or processed.

Use Redis for simple traffic limiting

Then we use Redis to implement an operation that can only be done a fixed number of times in a specified period of time, beyond which we reject the operation,

We can consider using the data structure zset, use score to store the timestamp of each operation, and ensure the uniqueness of value according to the business situation.

Then every time we use the sliding time window (wide), keep the data in this window, each time the rest of the trim off, it also can avoid waste of memory space, if a user was cold, and the user behavior in the sliding time window is empty record, then the zset can be removed from the memory, no longer take up space,

Zset structure is used to record the history of user behavior. Each behavior is saved as a key in zset. The same behavior of the same user is recorded with a Zset.

Below is the code of the sliding window of Zset. We first add the user’s current behavior in Zset, and then delete the data outside the current time window.

Finally, get the total number of data in this window. If the total number does not exceed the limit, we return true; if the limit is exceeded, we return false. The time window set in main method below is 60s, and the maximum number of requests within 60s is 5.

We can see from the result that only the first 5 times get true, allow access, subsequent results are all false, denied access.

Because these consecutive operations are all for the same key, using pipeline can significantly improve redis access efficiency.

However, this scheme has its own disadvantages, because it is necessary to record all behaviors within the time window. If the amount is very large, for example, the operation cannot exceed 1 million times within 60 seconds, it is not suitable for this method, which will consume a lot of storage space.

Funnel current-limiting

Funnel flow limiting is one of the most common flow limiting methods. This algorithm is inspired by the structure of a funnel. As shown in the following figure, the capacity of a funnel is limited.

If you plug the leak and keep filling it with water, it will fill up until it can no longer hold it. If you open the leak, the water will flow out from below. After some of it has gone away, you can fill it up again.

If the leak rate is greater than the rate of irrigation, then the leak will never be filled. If the leak rate is less than the rate of irrigation, once the funnel is full, the irrigation needs to stop and wait for the funnel to vacate some space before filling.

Thus, the remaining space of the funnel represents how much of the current behavior can continue, and the flow rate of leakage represents the maximum frequency that the system allows for that behavior.

Java implementation

package com.redis.cell; import java.util.Map; import java.util.concurrent.ConcurrentHashMap; Public class FunnelRateLimiter {static class Funnel {// Funnel capacity int capacity; // Float leakingRate; Int leftQuota; // Time of last leak Long leakingTs; public Funnel(int capacity, float leakingRate) { this.capacity = capacity; this.leakingRate = leakingRate; this.leftQuota = capacity; this.leakingTs = System.currentTimeMillis(); } synchronized void makeSpace() {long nowTs = system.currentTimemillis (); // How long has it been since the last leak Long deltaTs = nowts-Leakingts; Int deltaQuota = (int) (deltaTs * leakingRate); // If (deltaQuota < 0) {this. LeakingRate = capacity; this.leakingTs = nowTs; return; } if (deltaQuota < 1) {return; } // The remaining space is greater than 0, but after adding to the outflow exceeds the maximum value, LeftQuota = 0 && (this.leftQuota + deltaQuota) < 0) {this.leakingRate = Capacity; this.leakingTs = nowTs; return; } this.leftQuota += deltaQuota; // Record the leakingtime this.leakingTs = nowTs; If (this.leftquota > this.capacity) {this.leftquota = this.capacity; }} synchronized Boolean watering(int quota) {// Compute flow and remaining capacity makeSpace(); If (this.leftQuota >= quota) {this.leftQuota -= quota; return true; } return false; } } private static Map<String, Funnel> funnelMap = new ConcurrentHashMap<>(); public static boolean isActionAllowed(String userId, String actionKey, int capacity, float leakingRate) { String key = String.format("%s:%s", userId, actionKey); Funnel funnel = funnelMap.get(key); if (funnel == null) { funnel = new Funnel(capacity, leakingRate); funnelMap.put(key, funnel); } return funnel.watering(1); } public static void main(String[] args) { for (int i = 0; i < 20; i++) { System.out.println(isActionAllowed("mn", "reply", 5, 1)); }}}Copy the code

The makeSpace method of the Funnel object is the core of the Funnel algorithm. It is called before each Funnel infusion to trigger water leakage and free up space for the Funnel. The amount of space available depends on how long it has elapsed and the rate of water flow.

The amount of space taken up by a Funnel object is no longer proportional to the frequency of the action, but is a constant.

The result of the above code is shown below. The rate is 1 millisecond, and the maximum capacity is 5. You can see the following output, after 5 true, the subsequent output is false, until the past 1 millisecond.

The above code is implemented using Java code, to achieve distributed need to use Redis to handle, we can use redis hash structure,

Object will be a good field to store the hash to remove field in the hash operation to infuse water, then put it back, but this is the atomic problem, because the process of several steps the atomicity, means that you need to lock, lock and lock the possibility of failure retry, reduced performance, affect the user experience,

However, these operations can be done using Lua scripts, but in Redis4.0 we provide a redis-cell module, this module uses the funnel algorithm to achieve flow limiting, and provides atomic flow limiting instructions for us to use, which makes it easy to use Redis to achieve flow limiting.

RedisCell

This module requires additional plug-in installation, we use Docker to install and run:

docker pull carto/redis-cell
docker run -d -p 6379:6379 --name redisCell 69846d418101
Copy the code

The module has only one instruction, cl.throttle, which has a lot of parameters and return values. Let’s see the usage instructions below

The above command means that the frequency of “like” is allowed to be 30 times in 60 seconds. The initial capacity of the funnel is 15, that is, the user can click “like” for 15 times in a row at the beginning, which will be affected by the water leakage rate later.

So the commands above user1: zan is the user’s id + behavior (key), 15 is the capacity (capacity), how many times is a total of 30 operations (operations), 60 is a long time (seconds), and finally a (quota), the consumption of each operation capacity that can not fill in, The default is also 1.

The returned results are explained below

127.0.0.1:6379> cl.throttle user1:zan 15 30 60 1 1) (integer) 0 2) (integer) 16 # Funnel capacity 3) (integer) 15 # Remaining vulnerability space 4) (integer) -1 5) (integer) 2 # How long will it take for the funnel to be completely empty (in seconds)Copy the code

When executing the flow limiting command, if it is rejected, it needs to discard or retry. The cl.throttle command has calculated the retry time, so you can directly take the fourth value of the returned result and wait for sleep and retry. If you do not want to block the thread, you can also use the asynchronous timed task to retry.

The Java code runs as follows:

The code used in this article is at: github.com/qiaomengnan…