preface
In the project, we often encountered the need for frequency limit, such as SMS captcha can only be sent once per minute, 10 times per day. We can do this using Redis.
Noun explanation
Refresh at a fixed time point
Fixed time refresh is, we set the number of refreshes every night like 24 o ‘clock or 6 o ‘clock in the morning, so that at that time, the user can refresh the maximum number of requests. Of course, it doesn’t have to be once a day, we usecron
The expression can be set to refresh at 23:48 minutes and 5 seconds, refresh once every hour, refresh once every 5 minutes and other complex requirements. Below is a diagram that can request 6 times per day and refresh at 6 a.m. every day.
Fixed delay refresh
The fixed delay refresh is the maximum number of flush-times after the delay is set, starting at the point in time when the user first requests to start. As shown in the figure below, requests can be made twice every 5 minutes. The first request is 19.57, so the maximum number of refresh requests is 2 at 20.02. The second request is 20.05, so the maximum number of refresh requests is 2 at 20.10.
Range of refreshing
A range refresh is similar to a fixed-delay refresh, but the number of requests is not a one-time refresh, but a gradual refresh. As shown in the following figure, the refresh time is 5 minutes, and the maximum number of requests is 2. As shown in Figure 19.58, the user sends the request, so the number of available requests will increase by one at 20.03, the number of available requests will increase by one at 20.00, the number of available requests will increase by one at 20.05, the number of available requests will increase by one at 20.04, and the number of available requests will increase by one at 20.09.If the number of available requests is 1, then fixed delay refresh and range refresh have the same effect.
Redis implements the principle of frequency limiter
parameter
- Key Requires the frequency limiting key
- Frequency frequency
- ExpireAt Indicates the expiration timestamp
- CurrentTime Indicates the current timestamp
Fixed time point refresh Redis implementation principle
Use the string structure.
For example, if we refresh every morning at 6 am, we can use the next 6 am timestamp as expireAt. Redis first determines whether the value of the key (using GET command) is greater than or equal to frequency (if the key does not exist, consider it as 0). If so, reject, otherwise use INCR to increase the value of the key. And set the key to expireAt expireAt (using the expireAt command).
Fixed delay refresh Redis implementation principle
Use the string structure.
For example, if we have 2 requests every 5 minutes, we can set expireAt = current time + 5 minutes. First, judge Redis whether the value of the key (using GET command) is greater than or equal to frequency (if the key does not exist, consider it as 0). If so, reject, otherwise use INCR to increase the value of the key. If the key in the first step does not exist, Set the key to expireAt expireAt (using the expireAt command).
The only difference here is the last step from a fixed time refresh. For a fixed time refresh, it doesn’t matter whether the key exists or not, because every expireAt is the same until the next time. However, the fixed delay refresh must not exist to set the expiration time of the key, because each expireAt is the current time + the delay time.
Range refresh frequency limit Redis implementation principle
Use the list structure.
We store expireAt in the list, and then count the length of the list as the number of requests that have been used. At this time, we must make the expireAt in the list be deleted, so each time the operation process is as follows.
We first get the first element of the list (using the LINDEX command), and if the element’s value is less than currentTime, we delete it (using the LPOP command). Then determine if the length of the list (using LLEN) is greater than or equal to the frequency, reject if it is, otherwise add expireAt to the right of the queue using RPUSH and set the key to expireAt expireAt (using expireAt).
There may be questions
If list has multiple values less than currentTime, why not delete them all at once?
Since we can RPUSH only once at most, we only need one space. If you delete all the expired elements in the list at once, in the worst case, the list will have one expired element, which causes the request to suddenly become O(frequency), whereas if you delete only one element, each request will have O(1).
This article main class structure diagram
FrequencyLimiter
Is the core interface,DefaultFrequencyLimiter
Is the concrete implementation class.FrequencyLimitAspect
useFrequencyLimiter
The implementation class to implement annotations using frequency limits.FixedPointRefreshFrequencyLimit
,FixedDelayRefreshFrequencyLimit
,RangeRefreshFrequencyLimit
The note identifies each of the three refresh types of frequency limiter.
Frequency limiter Redis Lua script implementation
Why use the Redis Lua implementation
If Java code is used together with RedisTemplate or Jedis, users may get more requests than frequency under concurrent conditions, and multiple Redis network requests are required. So using The Redis Lua implementation ensures atomicity while avoiding multiple network requests.
Noun explanation
The token is the increment of an integer in the string or the length of the list.
Lua scripts are refreshed at a fixed point in time and at a fixed delay
The two refreshes are simply computed differently in expireAt, so we use a script to implement them.
--[[KEYS[1] Need to limit the frequency of key ARGV[1] frequency ARGV[2] expire timestamp --]]
-- Obtain the number of tokens corresponding to the key
local tokenNumbers = redis.call('GET', KEYS[1])
If the corresponding key exists and the number of keys is greater than or equal to frequency, return
if tokenNumbers and tonumber(tokenNumbers) >= tonumber(ARGV[1]) then
return false
end
-- Increase the number of tokens and set the expiration time
redis.call('INCR', KEYS[1])
If the original key does not exist, set the expiration time
if not tokenNumbers then
redis.call('PEXPIREAT', KEYS[1], ARGV[2])
end
return true
Copy the code
Scope refreshes Lua scripts
--[[KEYS[1] Need to limit the frequency of key ARGV[1] ARGV[2] Expire timestamp ARGV[3] Current timestamp --]]
Delete the first expired token
local expireTime = redis.call('LINDEX', KEYS[1].0)
if expireTime and (tonumber(expireTime) <= tonumber(ARGV[3])) then
redis.call('LPOP', KEYS[1])
end
If the number of tokens is greater than or equal to frequency, return the token
if redis.call('LLEN', KEYS[1]) >= frequency) then
return false
end
Add expireAt as value to the list of keys and set the expiration time of the list
redis.call('RPUSH', KEYS[1], ARGV[2])
redis.call('PEXPIREAT', KEYS[1], ARGV[2])
return true
Copy the code
Integrate into a Lua script
There are three types of frequency limits that can be manipulated using a Lua script. Therefore, you need to add an additional parameter of the frequency limiting type.
--[[KEYS[1] Need to limit the key ARGV[1] frequency ARGV[2] Expire timestamp ARGV[3] Limit frequency type ARGV[4] Current timestamp --]]
-- Reject the request directly if the frequency is 0
local frequency = tonumber(ARGV[1])
if frequency == 0 then
break
end
-- Range refresh
if ARGV[3] = ='RANGE_REFRESH' then
Delete the first expired token
local expireTime = redis.call('LINDEX', KEYS[1].0)
if expireTime and (tonumber(expireTime) <= tonumber(ARGV[4])) then
redis.call('LPOP', KEYS[1])
end
If the number of tokens is greater than or equal to frequency, return the token
if redis.call('LLEN', KEYS[1]) >= frequency) then
return false
end
Add expireAt as value to the list of keys and set the expiration time of the list
redis.call('RPUSH', KEYS[1], ARGV[2])
redis.call('PEXPIREAT', KEYS[1], ARGV[2])
-- fixed point in time refresh and fixed delay refresh
else
-- Obtain the number of tokens corresponding to the key
local tokenNumbers = redis.call('GET', KEYS[1])
If the corresponding key exists and the number of keys is greater than or equal to frequency, return
if tokenNumbers and tonumber(tokenNumbers) >= tonumber(ARGV[1]) then
return false
end
-- Increase the number of tokens and set the expiration time
redis.call('INCR', KEYS[1])
If the original key does not exist, set the expiration time
if not tokenNumbers then
redis.call('PEXPIREAT', KEYS[1], ARGV[2])
end
end
return true
Copy the code
Using scripts in Spring Boot
Define the Bean of the script
/** * Frequency limiting Lua script classpath path */
private static final String FREQUENCY_LIMIT_LUA_SCRIPT_CLASS_PATH = "/redis/lua/FrequencyLimit.lua";
/** * Redis script Bean */
@Bean("frequencyLimitRedisScript")
public RedisScript<Boolean> frequencyLimitRedisScript(a) {
DefaultRedisScript<Boolean> frequencyLimitRedisScript = new DefaultRedisScript<>();
frequencyLimitRedisScript.setResultType(Boolean.class);
frequencyLimitRedisScript.setScriptSource(new ResourceScriptSource(
new ClassPathResource(FREQUENCY_LIMIT_LUA_SCRIPT_CLASS_PATH)));
return frequencyLimitRedisScript;
}
Copy the code
Execute the script using the RedisTemplate
@Override
public Boolean isAllowed(FrequencyLimitType frequencyLimitType, String key, long frequency, long expireAt, long currentTime) {
return redisTemplate.execute(frequencyLimitRedisScript, Collections.singletonList(key),
frequency.toString(), String.valueOf(expireAt), frequencyLimitType.name(), String.valueOf(currentTime));
}
Copy the code
The problem with multiple frequency limiting
If you use multiple frequency is limited to the limit of the frequency, such as a minute two range (refresh), 10 times a day (refresh) fixed time points, then there will be a problem: if the first limit through, failed to pass the second limitation in accordance with the implementation of the above, the first limit will not be automatically release (the list will be one more element). The first limit in this case is only 1 minute which is fine, the user only has to wait 1 minute. But if the limit is one hour, then the user must wait an hour before he can try again for the second limit.
Therefore, in the case of multiple constraints, if a constraint does not pass, we need to release the previously passed constraint.
The solution
We can record each previous limit passed, and then restore the passed limit if one is not passed.
Lua script implementation
This is similar to the previous script, except now you pass in all the frequency limiting requests you need to get at once and loop through them, using the tokenMap to record all the limiting keys that have passed, and then restore all the keys in the tokenMap if a limit fails.
Also, the return values are no longer true and false, because we need to tell the caller which limiting operation failed on failure, so return the subscript of the failed limiting operation (starting from 0) and -1 on success.
--[[KEYS[I] Specifies the key ARGV[(i-1) * 3 + 1] frequency ARGV[(i-1) * 3 + 2] Expired timestamp ARGV[(i-1) * 3 + 3] Specifies the frequency type ARGV[#KEYS * 3 + 1] Current timestamp --]]
-- Record the key that has been obtained successfully, and the value is the operation that needs to be performed in case of failure
local tokenMap = {}
local currentTime = tonumber(ARGV[#KEYS * 3 + 1])
The last key index to get success
local lastIndex = 0
-- Loop through each frequency limiting request
for i = 1, #KEYS do
-- Reject the request directly if the frequency is 0
local frequency = tonumber(ARGV[(i - 1) * 3 + 1])
if frequency == 0 then
break
end
-- Range refresh
if ARGV[(i - 1) * 3 + 3] = ='RANGE_REFRESH' then
Delete the first expired token
local expireTime = redis.call('LINDEX', KEYS[i], 0)
if expireTime and (tonumber(expireTime) <= currentTime) then
redis.call('LPOP', KEYS[i])
end
If the number of tokens is greater than or equal to frequency, break the token
if redis.call('LLEN', KEYS[i]) >= frequency then
break
end
Add expireAt as value to the list of keys and set the expiration time of the list
local expireAt = ARGV[(i - 1) * 3 + 2]
redis.call('RPUSH', KEYS[i], expireAt)
redis.call('PEXPIREAT', KEYS[i], expireAt)
tokenMap[KEYS[i]] = 'RPOP'
-- fixed point in time refresh and fixed delay refresh
else
-- Obtain the number of tokens corresponding to the key
local tokenNumbers = redis.call('GET', KEYS[i])
-- If the corresponding key exists and the number of keys is greater than or equal to frequency, directly break
if tokenNumbers and tonumber(tokenNumbers) >= frequency then
break
end
-- Increase the number of tokens and set the expiration time
redis.call('INCR', KEYS[i])
If the original key does not exist, set the expiration time
if not tokenNumbers then
redis.call('PEXPIREAT', KEYS[i], ARGV[(i - 1) * 3 + 2])
end
tokenMap[KEYS[i]] = 'INCRBY'
end
lastIndex = i
end
-- Determine whether all the finite frequencies are successful. If they fail, release the successful tokens
if lastIndex < #KEYS then
for key, token in pairs(tokenMap) do
if token == 'RPOP' then
redis.call('RPOP', key)
else
redis.call('INCRBY', key, - 1)
end
end
return lastIndex
end
return - 1
Copy the code
Extension 1: Encapsulated as a frequency limiter
It is still troublesome to use lua script directly, which needs to be combined with RedisTemplate, etc., so we encapsulate it as a frequency limiter.
The implementation code
A method that can request multiple frequency limits at the same time and a method that can only request one frequency limit are implemented here. At the same time, we will add the prefix of corresponding type of frequency limit to each key, which can not only prevent the same key from conflicts under different frequency limit types, but also prevent conflicts with other Redis keys in the project.
/** * Default frequency limiter **@author xhsf
* @create 2020/12/18 15:41
*/
public class DefaultFrequencyLimiter implements FrequencyLimiter {
/** * Fixed time point refresh frequency limit Redis Key prefix */
private static final String FIXED_POINT_REFRESH_FREQUENCY_LIMIT_REDIS_KEY_PREFIX =
"frequency-limit:fixed-point-refresh:";
/** * Fixed delay refresh frequency limit Redis Key prefix */
private static final String FIXED_DELAY_REFRESH_FREQUENCY_LIMIT_REDIS_KEY_PREFIX =
"frequency-limit:fixed-delay-refresh:";
/** * Range refresh frequency limit Redis Key prefix */
private static final String RANGE_REFRESH_FREQUENCY_LIMIT_REDIS_KEY_PREFIX =
"frequency-limit:range-fresh:";
/** * Lua script return value */ when allowed
private static final int LUA_RETURN_VALUE_WHEN_ALLOWED = -1;
/** * Lua script that can get multiple keys at the same time */
private static final String REPEATABLE_FREQUENCY_LIMIT_LUA =
"--[[\n" +
"KEYS[I] need frequency limited key\n" +
"ARGV[(i-1) * 3 + 1] frequency \n" +
"ARGV[(i-1) * 3 + 2] expire timestamp \n" +
"ARGV[(i-1) * 3 + 3] limited frequency type \n" +
"ARGV[#KEYS * 3 + 1] current timestamp \n" +
"--]]\n" +
"\n" +
"-- Record the key that has been successfully obtained and the value is the operation to be performed on failure \n" +
"local tokenMap = {}\n" +
"local currentTime = tonumber(ARGV[#KEYS * 3 + 1])\n" +
"\n" +
"-- the last successful key subscript \n" +
"local lastIndex = 0\n" +
"\n" +
"-- loop through each frequency limiting request \n" +
"for i = 1, #KEYS do\n" +
"-- Reject the request directly if frequency is 0 \n" +
" local frequency = tonumber(ARGV[(i - 1) * 3 + 1])\n" +
" if frequency == 0 then\n" +
" break\n" +
" end\n" +
"\n" +
"-- range refresh \n" +
" if ARGV[(i - 1) * 3 + 3] == 'RANGE_REFRESH' then\n" +
"-- Delete the first expired token\n" +
" local expireTime = redis.call('LINDEX', KEYS[i], 0)\n" +
" if expireTime and (tonumber(expireTime) <= currentTime) then\n" +
" redis.call('LPOP', KEYS[i])\n" +
" end\n" +
"\n" +
"-- Break \n if the number of tokens is greater than or equal to frequency" +
" if redis.call('LLEN', KEYS[i]) >= frequency then\n" +
" break\n" +
" end\n" +
"\n" +
"-- add expireAt as value to the list of keys and set the expiration time of the list \n" +
" local expireAt = ARGV[(i - 1) * 3 + 2]\n" +
" redis.call('RPUSH', KEYS[i], expireAt)\n" +
" redis.call('PEXPIREAT', KEYS[i], expireAt)\n" +
" tokenMap[KEYS[i]] = 'RPOP'\n" +
"\n" +
"-- fixed point in time refresh and fixed delay refresh \n" +
" else\n" +
"-- get the number of tokens for the key \n" +
" local tokenNumbers = redis.call('GET', KEYS[i])\n" +
"\n" +
"-- break\n if the corresponding key exists and the number of keys is greater than or equal to frequency" +
" if tokenNumbers and tonumber(tokenNumbers) >= frequency then\n" +
" break\n" +
" end\n" +
"\n" +
"-- Increase the number of tokens and set the expiration time \n" +
" redis.call('INCR', KEYS[i])\n" +
"-- If the original key does not exist, set the expiration time \n" +
" if not tokenNumbers then\n" +
" redis.call('PEXPIREAT', KEYS[i], ARGV[(i - 1) * 3 + 2])\n" +
" end\n" +
" tokenMap[KEYS[i]] = 'INCRBY'\n" +
" end\n" +
" lastIndex = i\n" +
"end\n" +
"\n" +
"-- determine if all the finite frequencies are successful, and if they fail, release the tokens \n that have succeeded." +
"if lastIndex < #KEYS then\n" +
" for key, token in pairs(tokenMap) do\n" +
" if token == 'RPOP' then\n" +
" redis.call('RPOP', key)\n" +
" else\n" +
" redis.call('INCRBY', key, -1)\n" +
" end\n" +
" end\n" +
" return lastIndex\n" +
"end\n" +
"\n" +
"return -1";
/** * StringRedisTemplate */
private final StringRedisTemplate stringRedisTemplate;
/** * Get multiple key frequency limiting script */
private final RedisScript<Long> repeatableFrequencyLimitRedisScript;
public DefaultFrequencyLimiter(StringRedisTemplate stringRedisTemplate) {
this.stringRedisTemplate = stringRedisTemplate;
// A frequency limiting script that can get multiple keys
DefaultRedisScript<Long> repeatableFrequencyLimitRedisScript = new DefaultRedisScript<>();
repeatableFrequencyLimitRedisScript.setResultType(Long.class);
repeatableFrequencyLimitRedisScript.setScriptText(REPEATABLE_FREQUENCY_LIMIT_LUA);
this.repeatableFrequencyLimitRedisScript = repeatableFrequencyLimitRedisScript;
}
/** * query whether a key is allowed to operate **@paramFrequencyLimitType frequencyLimitType *@paramThe format of the key should be {service name}:{specific business name}:{unique identifier}, for example, SMS :auth-code:15333333333 *@paramFrequency frequency *@paramExpireAt Expiration timestamp *@paramCurrentTime Indicates the current timestamp *@returnWhether to allow */
@Override
public boolean isAllowed(FrequencyLimitType frequencyLimitType, String key, long frequency, long expireAt,
long currentTime) {
String[] args = {String.valueOf(frequency), String.valueOf(expireAt), frequencyLimitType.name(),
String.valueOf(currentTime)};
return isAllowed(Collections.singletonList(key), args) == LUA_RETURN_VALUE_WHEN_ALLOWED;
}
/** * select tokens ** from tokens **@paramKeys requires a frequency limiting key *@paramArgs Parameter list, The format is [frequency1, expireAt1, frequencyLimitType1, * frequency2, expireAt2, frequencyLimitType2... frequencyN, expireAtN, frequencyLimitTypeN, * currentTime] *@return-1 indicates yes. Other values indicate the subscript (*/) of the failure to obtain
public int isAllowed(List<String> keys, String[] args) {
for (int i = 0; i < keys.size(); i++) {
String frequencyLimitType = args[i * 3 + 2];
if (frequencyLimitType.equals(FrequencyLimitType.FIXED_POINT_REFRESH.name())) {
keys.set(i, FIXED_POINT_REFRESH_FREQUENCY_LIMIT_REDIS_KEY_PREFIX + keys.get(i));
} else if (frequencyLimitType.equals(FrequencyLimitType.RANGE_REFRESH.name())){
keys.set(i, RANGE_REFRESH_FREQUENCY_LIMIT_REDIS_KEY_PREFIX + keys.get(i));
} else{ keys.set(i, FIXED_DELAY_REFRESH_FREQUENCY_LIMIT_REDIS_KEY_PREFIX + keys.get(i)); }}returnstringRedisTemplate.execute(repeatableFrequencyLimitRedisScript, keys, args).intValue(); }}Copy the code
Interface FrequencyLimiter
/** **@author xhsf
* @create 2020/12/18 15:41
*/
public interface FrequencyLimiter {
/** * query whether a key is allowed to operate **@paramFrequencyLimitType frequencyLimitType *@paramThe format of the key should be {service name}:{specific business name}:{unique identifier}, for example, SMS :auth-code:15333333333 *@paramFrequency frequency *@paramExpireAt Expiration timestamp *@paramCurrentTime Indicates the current timestamp *@returnWhether to allow */
boolean isAllowed(FrequencyLimitType frequencyLimitType, String key, long frequency, long expireAt,
long currentTime);
/** * select tokens ** from tokens **@paramKeys requires a frequency limiting key *@paramArgs Parameter list, The format is [frequency1, expireAt1, frequencyLimitType1, * frequency2, expireAt2, frequencyLimitType2... frequencyN, expireAtN, frequencyLimitTypeN, * currentTime] *@return-1 indicates yes. Other values indicate the subscript (*/) of the failure to obtain
int isAllowed(List<String> keys, String[] args);
}
Copy the code
Frequency limiting type FrequencyLimitType
/** * Description: Frequency limit type **@author xhsf
* @create2020/12/18 as * /
public enum FrequencyLimitType {
/** * Fixed time point refresh */
FIXED_POINT_REFRESH,
/** * Fixed delay refresh */
FIXED_DELAY_REFRESH,
/** * Range refresh */
RANGE_REFRESH
}
Copy the code
Extension 2: Encapsulated as annotations
Using a frequency limiter can be tricky, especially when using the isAllowed(List
keys, String[] args) method, so it needs to be further wrapped into annotations.
Using annotations can reduce intrusion into business code and improve ease of use. Here the key implements an EL + placeholder expression; Supports multiple annotations for multiple frequency limiting types simultaneously; The fixed time point refresh annotation uses cron expression, which only needs to write cron expression. ErrorMessage can also be expressed using EL; Meet most needs.
The use of annotations is recommended.
EL expressions and parsers
Refer to the article SpEL for a brief analysis of spring-expression implementation principles that you are interested in.
For example, the expression = SMS :auth-code:#{#user.phone}, the parameter =(UserDTO user), where user = {name: XXX, phone: 1333333333}. SMS :auth-code:#{#user.phone} = SMS :auth-code:1333333333
Cron expression
Cron expressions can be explained in detail by referring to the article cron expressions and the time of cron expressions calculated according to CronSequenceGenerator.
For example, 0 0 6 * * * indicates 6 o ‘clock every morning; 33 15 23 * * * indicates 23 ∶ 15 ∶ 33 seconds per day; 0 0/5 * * * * : indicates the 0, 5, 10, 15… , 55 minutes.
Placeholder expression
Messageformat.format (key, parameters).
For example messageFormat. format(” SMS :auth-code:{0}:{1}”, “fixed-refresh”, “#{#phone}”) -> SMS :auth-code:fixed-refresh:#{#phone}.
Annotations corresponding to the three frequency limiting types
Refreshes annotations at fixed time points
/** * Description: fixed time point refresh frequency limit annotated by {@linkFrequencyLimitAspect} Implements * *@author xhsf
* @createThe 2020-12-18 then * /
@Target({ElementType.METHOD})
@Retention(RetentionPolicy.RUNTIME)
@Documented
@Repeatable(FixedPointRefreshFrequencyLimit.List.class)
public @interface FixedPointRefreshFrequencyLimit {
/** * limit the frequency of key, support EL expression, such as #{#user.phone} *@see#parameters() Support placeholder padding * such as value =" user:{0}:phone", parameters="#{#user.id}" will be converted to value =" user:#{#user.id}:phone" */
String key(a);
/** * Fill in the placeholder parameter */
String[] parameters() default {};
/** * cron expression * 1. Cron has 7 digits, but the last digit is the year (1970-2099), which can be left blank, so we can write 6 digits in order: ** second (0-59) * minute (0-59) * hour (0-23) * day (month) (0-31) But you need to consider the days of your month) * Month (0~11) * Week (1~7 1=SUN, MON, TUE, WED, THU, FRI, SAT) * * Some special symbols of cron * (*) asterisk: Every second, every minute, every day, every month, every year Question mark: * The question mark can only appear in the date and the week, indicating that the value of this position is uncertain. It is executed every day at 3 o 'clock. Therefore, we do not need to pay attention to the position of the sixth week, * is the uncertain value. Also: Date and week are mutually exclusive elements, and no value is specified by the question mark. For example, January 10, such as Monday, * if the location of the week is another Tuesday, there is a conflict. * (-) minus: * indicates a range, such as "10-12" in the hour field, from 10 to 12, that is, 10,11,12 * (,) comma: * indicates a list value, such as "1,2,4" in the week field, indicating Monday, Tuesday, and Thursday * (/) slash: for example: X /y, x is the starting value, y is the step size, such as in the first (second) 0/15 is, start at 0 seconds, every 15 seconds, and end at 0, 15, 30, 45, 60 * and: *\/y, which is the same as 0/y * *@see org.springframework.scheduling.support.CronSequenceGenerator
*/
String cron(a);
/** * Frequency */
long frequency(a);
/** * Error message when the token fails to be obtained. EL expression */ is supported
String errorMessage(a) default "Too many request.";
/** * Description: Frequency limit annotation array **@author xhsf
* @createThe 2020-12-18 then * /
@Target({ElementType.METHOD})
@Retention(RetentionPolicy.RUNTIME)
@Documented
@interface List {
/** * limit the frequency of the annotation array */FixedPointRefreshFrequencyLimit[] value(); }}Copy the code
Fixed delay for refreshing annotations
/** * Description: Frequency limit annotation array **@author xhsf
* @createThe 2020-12-18 then * /
@Target({ElementType.METHOD})
@Retention(RetentionPolicy.RUNTIME)
@Documented
public @interface FrequencyLimits {
/** * limit the frequency of the annotation array */
FrequencyLimit[] value();
}
Copy the code
Range refresh annotation
/** * Description: range frequency limit annotated by {@linkFrequencyLimitAspect} Implements * *@author xhsf
* @createThe 2020-12-18 then * /
@Target({ElementType.METHOD})
@Retention(RetentionPolicy.RUNTIME)
@Documented
@Repeatable(RangeRefreshFrequencyLimit.List.class)
public @interface RangeRefreshFrequencyLimit {
/** * limit the frequency of key, support EL expression, such as #{#user.phone} *@see#parameters() Support placeholder padding * such as value =" user:{0}:phone", parameters="#{#user.id}" will be converted to value =" user:#{#user.id}:phone" */
String key(a);
/** * Fill in the placeholder parameter */
String[] parameters() default {};
/** * Frequency */
long frequency(a);
/** * Refresh time */
long refreshTime(a);
/** * Time unit. The default value is seconds */
TimeUnit timeUnit(a) default TimeUnit.SECONDS;
/** * Error message when the token fails to be obtained. EL expression */ is supported
String errorMessage(a) default "Too many request.";
/** * Description: Frequency limit annotation array **@author xhsf
* @createThe 2020-12-18 then * /
@Target({ElementType.METHOD})
@Retention(RetentionPolicy.RUNTIME)
@Documented
@interface List {
/** * limit the frequency of the annotation array */RangeRefreshFrequencyLimit[] value(); }}Copy the code
FrequencyLimitAspect aspect implementation class
This is implemented using FrequencyLimiter, and in case of an error the Result object is the same as in the project (you can throw an exception or wrap other objects depending on your needs).
/** * Description: Frequency limited section, with {@linkFixedDelayRefreshFrequencyLimit}, {@link FixedPointRefreshFrequencyLimit}、
* {@linkRangeRefreshFrequencyLimit frequency * *} can be convenient to use@author xhsf
* @create2020/12/18 as * /
@Aspect
public class FrequencyLimitAspect {
/** * frequency limiter */
private final FrequencyLimiter frequencyLimiter;
public FrequencyLimitAspect(FrequencyLimiter frequencyLimiter) {
this.frequencyLimiter = frequencyLimiter;
}
Limit the frequency of requests **@errorCodeTooManyRequests: too frequent * *@param joinPoint ProceedingJoinPoint
* @return Object
*/
@Around("@annotation(FixedDelayRefreshFrequencyLimit.List) || @annotation(FixedDelayRefreshFrequencyLimit) " + "|| @annotation(FixedPointRefreshFrequencyLimit.List) || @annotation(FixedPointRefreshFrequencyLimit) " + "|| @annotation(RangeRefreshFrequencyLimit.List) || @annotation(RangeRefreshFrequencyLimit)")
public Object isAllowed(ProceedingJoinPoint joinPoint) throws Throwable {
List<Annotation> frequencyLimits = getFrequencyLimits(joinPoint);
int notAllowIndex = isAllowed(joinPoint, frequencyLimits);
if(notAllowIndex ! = -1) {
String errorMessage = getErrorMessage(joinPoint, frequencyLimits.get(notAllowIndex));
return Result.fail(ErrorCodeEnum.TOO_MANY_REQUESTS, errorMessage);
}
// Execute the business logic
return joinPoint.proceed();
}
/** whether to allow **@param joinPoint ProceedingJoinPoint
* @param frequencyLimits List<Annotation>
* @return-1 indicates yes. Other values indicate the subscript (*/) of the failure to obtain
private int isAllowed(ProceedingJoinPoint joinPoint, List<Annotation> frequencyLimits) {
List<String> keys = new ArrayList<>(frequencyLimits.size());
String[] args = new String[frequencyLimits.size() * 3 + 1];
Date now = new Date();
long currentTime = now.getTime();
args[frequencyLimits.size() * 3] = String.valueOf(currentTime);
for (int i = 0; i < frequencyLimits.size(); i++) {
// Range refresh frequency limit
if (frequencyLimits.get(i) instanceof RangeRefreshFrequencyLimit) {
RangeRefreshFrequencyLimit rangeRefreshFrequencyLimit =
(RangeRefreshFrequencyLimit) frequencyLimits.get(i);
keys.add(getKey(joinPoint, rangeRefreshFrequencyLimit.key(), rangeRefreshFrequencyLimit.parameters()));
args[i * 3] = String.valueOf(rangeRefreshFrequencyLimit.frequency());
args[i * 3 + 1] = String.valueOf(FrequencyLimiterUtils.getExpireAt(
rangeRefreshFrequencyLimit.refreshTime(), rangeRefreshFrequencyLimit.timeUnit(), currentTime));
args[i * 3 + 2] = FrequencyLimitType.RANGE_REFRESH.name();
}
// Fixed time point refresh frequency limit
else if (frequencyLimits.get(i) instanceof FixedPointRefreshFrequencyLimit) {
FixedPointRefreshFrequencyLimit fixedPointRefreshFrequencyLimit =
(FixedPointRefreshFrequencyLimit) frequencyLimits.get(i);
keys.add(getKey(joinPoint, fixedPointRefreshFrequencyLimit.key(),
fixedPointRefreshFrequencyLimit.parameters()));
args[i * 3] = String.valueOf(fixedPointRefreshFrequencyLimit.frequency());
args[i * 3 + 1] = String.valueOf(FrequencyLimiterUtils.getExpireAt(
fixedPointRefreshFrequencyLimit.cron(), now));
args[i * 3 + 2] = FrequencyLimitType.FIXED_POINT_REFRESH.name();
}
// Fixed delay refresh frequency limit
else {
FixedDelayRefreshFrequencyLimit fixedDelayRefreshFrequencyLimit =
(FixedDelayRefreshFrequencyLimit) frequencyLimits.get(i);
keys.add(getKey(joinPoint, fixedDelayRefreshFrequencyLimit.key(),
fixedDelayRefreshFrequencyLimit.parameters()));
args[i * 3] = String.valueOf(fixedDelayRefreshFrequencyLimit.frequency());
args[i * 3 + 1] = String.valueOf(FrequencyLimiterUtils.getExpireAt(
fixedDelayRefreshFrequencyLimit.refreshTime(), fixedDelayRefreshFrequencyLimit.timeUnit(),
currentTime));
args[i * 3 + 2] = FrequencyLimitType.FIXED_DELAY_REFRESH.name(); }}// Determine whether to allow
return frequencyLimiter.isAllowed(keys, args);
}
/** * Get the list of frequency limit annotations **@param joinPoint ProceedingJoinPoint
* @return List<Annotation>
*/
private List<Annotation> getFrequencyLimits(ProceedingJoinPoint joinPoint) {
Method method;
try {
MethodSignature methodSignature = (MethodSignature) joinPoint.getSignature();
method = joinPoint.getTarget()
.getClass()
.getMethod(methodSignature.getName(), methodSignature.getParameterTypes());
Annotation[] rangeRefreshFrequencyLimits =
method.getAnnotationsByType(RangeRefreshFrequencyLimit.class);
Annotation[] fixedPointRefreshFrequencyLimits =
method.getAnnotationsByType(FixedPointRefreshFrequencyLimit.class);
Annotation[] fixedDelayRefreshFrequencyLimits =
method.getAnnotationsByType(FixedDelayRefreshFrequencyLimit.class);
List<Annotation> frequencyLimits = new ArrayList<>(rangeRefreshFrequencyLimits.length
+ fixedPointRefreshFrequencyLimits.length + fixedDelayRefreshFrequencyLimits.length);
frequencyLimits.addAll(Arrays.asList(rangeRefreshFrequencyLimits));
frequencyLimits.addAll(Arrays.asList(fixedPointRefreshFrequencyLimits));
frequencyLimits.addAll(Arrays.asList(fixedDelayRefreshFrequencyLimits));
return frequencyLimits;
} catch (NoSuchMethodException ignored) {
}
return new ArrayList<>();
}
/** * Get error message **@param joinPoint ProceedingJoinPoint
* @param frequencyLimit frequencyLimit
* @returnError message */
private String getErrorMessage(ProceedingJoinPoint joinPoint, Annotation frequencyLimit) {
String errorMessageExpression;
if (frequencyLimit instanceof RangeRefreshFrequencyLimit) {
errorMessageExpression = ((RangeRefreshFrequencyLimit) frequencyLimit).errorMessage();
} else if (frequencyLimit instanceof FixedPointRefreshFrequencyLimit) {
errorMessageExpression = ((FixedPointRefreshFrequencyLimit) frequencyLimit).errorMessage();
} else {
errorMessageExpression = ((FixedDelayRefreshFrequencyLimit) frequencyLimit).errorMessage();
}
return SpELUtils.getExpressionValue(errorMessageExpression, joinPoint);
}
/** * Get the key for limiting frequency **@param joinPoint ProceedingJoinPoint
* @param key Key
* @param parameters parameters
* @returnThe limit of the frequency key * /
private String getKey(ProceedingJoinPoint joinPoint, String key, Object[] parameters) {
// Construct key expressions
String keyExpression = key;
// Fill in the parameters, if any
if (parameters.length > 0) {
keyExpression = MessageFormat.format(key, parameters);
}
/ / get keys
returnSpELUtils.getExpressionValue(keyExpression, joinPoint); }}Copy the code
FrequencyLimiterUtils
/** * Description: Frequency limiter tool class **@author xhsf
* @create2020/12/22 19:09 * /
public class FrequencyLimiterUtils {
/** * Get expiration time from cron expression **@paramCron Cron expression *@paramNow Current time *@returnExpiration time */
public static long getExpireAt(String cron, Date now) {
return CronUtils.next(cron, now).getTime();
}
/** * Obtain the expiration time from time, timeUnit, and currentTime **@paramRefreshTime refreshTime *@paramTimeUnit timeUnit *@paramCurrentTime currentTime *@returnExpiration time */
public static long getExpireAt(long refreshTime, TimeUnit timeUnit, long currentTime) {
returnTimeoutUtils.toMillis(refreshTime, timeUnit) + currentTime; }}Copy the code
CronUtils
/** * Description: Cron expression utility class **@author xhsf
* @create2020/12/22 * /
public class CronUtils {
/** * Cache the CronSequenceGenerator for cron expressions */
private static final Map<String, CronSequenceGenerator> cronSequenceGeneratorMap = new HashMap<>();
/** * Gets the timestamp of the next cron expression@paramCron Cron expression *@paramNow Current time *@returnNext time */
public static Date next(String cron, Date now) {
CronSequenceGenerator cronSequenceGenerator = cronSequenceGeneratorMap.getOrDefault(
cron, cronSequenceGeneratorMap.put(cron, new CronSequenceGenerator(cron)));
returncronSequenceGenerator.next(now); }}Copy the code
SpELUtils
/** * Description: Spring Expression Language utility class **@author xhsf
* @create2020/12/22 19:14 * /
public class SpELUtils {
/** * EL expression parser */
private static final ExpressionParser expressionParser = new SpelExpressionParser();
/** * Get the value of the expression **@paramExpression Expression *@param joinPoint ProceedingJoinPoint
* @return value
*/
public static String getExpressionValue(String expression, ProceedingJoinPoint joinPoint) {
// Get the Map of the method parameters
String[] parameterNames = ((CodeSignature) joinPoint.getSignature()).getParameterNames();
Object[] parameterValues = joinPoint.getArgs();
Map<String, Object> parameterMap = new HashMap<>();
for (int i = 0; i < parameterNames.length; i++) {
parameterMap.put(parameterNames[i], parameterValues[i]);
}
// Parse the EL expression
return getExpressionValue(expression, parameterMap);
}
/** * Get the value of the EL expression **@paramElExpression EL Expression *@paramParameterMap Parameter name - Value Map *@returnThe value of the expression */
public static String getExpressionValue(String elExpression, Map<String, Object> parameterMap) {
Expression expression = expressionParser.parseExpression(elExpression, new TemplateParserContext());
EvaluationContext context = new StandardEvaluationContext();
for (Map.Entry<String, Object> entry : parameterMap.entrySet()) {
context.setVariable(entry.getKey(), entry.getValue());
}
returnexpression.getValue(context, String.class); }}Copy the code
Example of using annotations
// Max 2 times, refresh time 60 seconds
@RangeRefreshFrequencyLimit(key = "email:auth-code:#{#createAndSendEmailAuthCodePO.email}", frequency = 2, refreshTime = 60)
// Max 2 times in 60 seconds
@FixedDelayRefreshFrequencyLimit(key = "email:auth-code:#{#createAndSendEmailAuthCodePO.email}", frequency = 2, refreshTime = 60)
// Up to 10 times, the number of times [0, 5, 10, 15... 55] refreshes per hour
@FixedPointRefreshFrequencyLimit(key = "email:auth-code:#{#createAndSendEmailAuthCodePO.email}", frequency = 10, cron = "0 0/5 * * * *")
public Result<Void> createAndSendEmailAuthCode(CreateAndSendEmailAuthCodePO createAndSendEmailAuthCodePO) {
// Business code
}
Copy the code
Remember to register sections
/** **@param stringRedisTemplate StringRedisTemplate
* @return FrequencyLimiter
*/
@Bean
public FrequencyLimiter frequencyLimiter(StringRedisTemplate stringRedisTemplate) {
return new DefaultFrequencyLimiter(stringRedisTemplate);
}
/** * Frequency limiting section **@param frequencyLimiter FrequencyLimiter
* @return FrequencyLimitAspect
*/
@Bean
public FrequencyLimitAspect frequencyLimitAspect(FrequencyLimiter frequencyLimiter) {
return new FrequencyLimitAspect(frequencyLimiter);
}
Copy the code
Extension 3: Request arrival order issues
Solution to the idea of avoiding requests with timestamp parameters.
Range refresh frequency limit
Problem description
If request A and request B have the same key, request A’s expireAt is 12:23:01, request B’s expireAt is 12:23:03, but request B arrives in advance due to network delay or other reasons. At this point, the key expireAt is 12:23:03, but when request A arrives, the key expireAt is changed to 12:23:01. At 12:23:01, although the token of request B cannot be refreshed, because the key has expired, the token of request B will also be cleared, that is, the list corresponding to the key has been deleted. Originally, the number of requests that the user can make at 12:23:01 should be 1, but because request B’s token is cleared, the number of requests becomes 2.
The solution
Instead of passing expireAt directly, pass a timeout(refreshTime), then use the TIME command in Lua to get the current TIME, and add timeout as expireAt.
Fixed delay refresh frequency limit
Problem description
If the key does not exist, the request A for the corresponding key is sent at 11:59:50, and the expireAt is 12:00:00. However, due to network delay and other reasons, the request A does not arrive until 12:00:01. At this time, the frequency limit is not limited. Because the key expired immediately after PEXPIREAT was executed, the number of requests was restored to the maximum.
The solution
Instead of passing expireAt directly, pass timeout(delay) and use the PEXPIRE + timeout command in Lua to set the expiry time.
Fixed time point refresh frequency limit
Problem description
Same as fixed delay refresh frequency limit.
The solution
If you can parse cron expressions in Lua scripts, then this problem can be solved. However, we have not found a good library in Lua to parse cron, so we judge the value of expireAt, if less than the current TIME, directly reject the request.
This can lead to new problems. If the time point is too small, such as 0/1 * * * * * (one refresh time point per second), expireAt may fail all the time because it cannot keep up with the network transmission speed, so it is best not to set too small an interval. If small refresh intervals are required, use fixed delay refresh or range refresh instead.
Lua script after resolution
You also need to change the way the scope refresh and fixed delay refresh in the Aspect are computed with respect to time, and you no longer need to pass in the current time parameter.
--[[KEYS[I] -argv [(i-1) * 3 + 1] expireAt or refreshTime or delayTime ARGV[(i-1) * 3 + 2] * 3 + 3] Frequency limit type --]]
This function is called because the time function is called, so Redis only copies the write command to avoid master/slave inconsistency
redis.replicate_commands()
-- Record the key that has been obtained successfully, and the value is the operation that needs to be performed in case of failure
local tokenMap = {}
Get the current time
local now = redis.call('TIME')
local currentTime = tonumber(now[1]) * 1000 + math.ceil(tonumber(now[2) /1000)
The last key index to get success
local lastIndex = 0
-- Loop through each frequency limiting request
for i = 1, #KEYS do
-- Reject the request directly if the frequency is 0
local frequency = tonumber(ARGV[(i - 1) * 3 + 1])
if frequency == 0 then
break
end
-- Range refresh
if ARGV[(i - 1) * 3 + 3] = ='RANGE_REFRESH' then
Delete the first expired token
local expireTime = redis.call('LINDEX', KEYS[i], 0)
if expireTime and (tonumber(expireTime) <= currentTime) then
redis.call('LPOP', KEYS[i])
end
If the number of tokens is greater than or equal to frequency, break the token
if redis.call('LLEN', KEYS[i]) >= frequency then
break
end
Add expireAt as value to the list of keys and set the expiration time of the list
local expireAt = currentTime + tonumber(ARGV[(i - 1) * 3 + 2])
redis.call('RPUSH', KEYS[i], expireAt)
redis.call('PEXPIREAT', KEYS[i], expireAt)
tokenMap[KEYS[i]] = 'RPOP'
-- Fixed delay refresh
elseif ARGV[(i - 1) * 3 + 3] = ='FIXED_DELAY_REFRESH' then
-- Obtain the number of tokens corresponding to the key
local tokenNumbers = redis.call('GET', KEYS[i])
-- If the corresponding key exists and the number of keys is greater than or equal to frequency, directly break
if tokenNumbers and tonumber(tokenNumbers) >= frequency then
break
end
-- Increase the number of tokens and set the expiration time
redis.call('INCR', KEYS[i])
If the original key does not exist, set the expiration time
if not tokenNumbers then
redis.call('PEXPIRE', KEYS[i], ARGV[(i - 1) * 3 + 2])
end
tokenMap[KEYS[i]] = 'INCRBY'
-- Refresh at a fixed time point
else
-- expireAt less than the current time reject directly
local expireAt = tonumber(ARGV[(i - 1) * 3 + 2])
if expireAt <= currentTime then
break
end
-- Obtain the number of tokens corresponding to the key
local tokenNumbers = redis.call('GET', KEYS[i])
-- If the corresponding key exists and the number of keys is greater than or equal to frequency, directly break
if tokenNumbers and tonumber(tokenNumbers) >= frequency then
break
end
-- Increase the number of tokens and set the expiration time
redis.call('INCR', KEYS[i])
If the original key does not exist, set the expiration time
if not tokenNumbers then
redis.call('PEXPIREAT', KEYS[i], ARGV[(i - 1) * 3 + 2])
end
tokenMap[KEYS[i]] = 'INCRBY'
end
lastIndex = i
end
-- Determine whether all the finite frequencies are successful. If they fail, release the successful tokens
if lastIndex < #KEYS then
for key, token in pairs(tokenMap) do
if token == 'RPOP' then
redis.call('RPOP', key)
else
redis.call('INCRBY', key, - 1)
end
end
return lastIndex
end
return - 1
Copy the code
Time complexity analysis
Range of refreshing
Time complexity O(1), using LINDEX, LPOP, LLEN, RPUSH, PEXPIREAT command. The complexity of LINDEX is O(1) because LINDEX only requests the operation of obtaining the first element of the list once.
Fixed point in time refresh and fixed delay refresh
The time complexity is O(1), and only GET, INCR, PEXPIREAT are used.