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 usecronThe 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

FrequencyLimiterIs the core interface,DefaultFrequencyLimiterIs the concrete implementation class.FrequencyLimitAspectuseFrequencyLimiterThe implementation class to implement annotations using frequency limits.FixedPointRefreshFrequencyLimit,FixedDelayRefreshFrequencyLimit,RangeRefreshFrequencyLimitThe 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.